[llvm-dev] RFC: Contained stateful AliasAnalysis

[Alina Sbirlea via llvm-dev]

I believe the patch <https://reviews.llvm.org/D59315> is now a reasonable
prototype. Please let me know what you think.

Thanks,
Alina

On Wed, Mar 13, 2019 at 12:37 PM Alina Sbirlea <alina.sbirlea at gmail.com>
wrote:

> Following an offline discussion (+cc), here's a second prototype attempt:
> https://reviews.llvm.org/D59315.
>
> There are a lot of discussion points on things to improve. I tried to list
> some in the summary and the patch comments.
>
> Thanks,
> Alina
>
>
> On Tue, Mar 5, 2019 at 3:14 PM Alina Sbirlea <alina.sbirlea at gmail.com>
> wrote:
>
>> Here's one simplest extension that keeps some temporary caches:
>> https://reviews.llvm.org/D58999.
>>
>> What's the best way to discuss this in more depth? (irc, meetup?)
>>
>> Thanks a lot!
>> Alina
>>
>>
>> On Mon, Mar 4, 2019 at 10:22 PM Alina Sbirlea <alina.sbirlea at gmail.com>
>> wrote:
>>
>>> Hi Hal,
>>>
>>> Yes, the "internal" caches AA would be valid as long as the IR is not
>>> mutated. Are you suggesting keeping them? It's possible, but it will be
>>> very tricky to ensure they are cleared at the right times and they will
>>> likely be prone to adding hidden bugs.
>>> I don't have strong indications currently that keeping such information
>>> would be useful by other users, other than MemorySSA, and only at build
>>> time, so I'd rather not sign up for updating/invalidating such internal
>>> caches.
>>>
>>> MemorySSA itself can be viewed as a cache, but you can view it as
>>> storing different information than what AA computes internally. e.g.
>>> MemorySSA will not remember "is this pointer captured". But, while building
>>> MemorySSA, there are a lot of queries asking if a pointer is captured.
>>> With MemorySSA we know we benefit from reusing the info it stores, so
>>> having passes update it makes sense.
>>>
>>> Does that makes sense, or did I misunderstand your question?
>>>
>>> Alina
>>>
>>>
>>> On Mon, Mar 4, 2019 at 5:23 PM Finkel, Hal J. <hfinkel at anl.gov> wrote:
>>>
>>>>
>>>> On 3/4/19 7:08 PM, Alina Sbirlea via llvm-dev wrote:
>>>>
>>>> TL;DR: I'm looking to have AliasAnalysis passes have the ability keep a
>>>> temporary cache when no transformations are performed.
>>>>
>>>> I'm interested to first and foremost clarify what is the best way to
>>>> even start such an infrastructure change, such that it is not abused (or
>>>> even available) by other passes. We certainly don't want to keep arbitrary
>>>> caches in all passes.
>>>> Would making this a feature used exclusively by MemorySSA make sense?
>>>> Only from other Analysis?
>>>>
>>>> The usecases I have stem from BasicAA and TBAA being used to build
>>>> MemorySSA.
>>>> MemorySSA is essentially a cache itself, and we're building it with a
>>>> stateless tool.
>>>> We know that while building MemorySSA, there are no changes in the
>>>> program, and yet, there is info that is computed again and again.
>>>>
>>>> One example is this patch: D57627 <https://reviews.llvm.org/D57627>.
>>>> The patch adds a cache for PointerMayBeCaptured, which is cleared
>>>> after every alias() call, in order to keep BasicAA stateless. In the
>>>> example given in the patch, not clearing the isCapturedCache reduces
>>>> compile times by another second. In some pathological cases I'm looking at,
>>>> not-clearing this cache halves compile times (from 8s to 4s).
>>>> There are a few other examples such as TBAA's getLeastCommonType and
>>>> BasicAA's DecomposeGEP.
>>>>
>>>> Ideally we'd would have something along the lines of:
>>>> void keepCaches()
>>>> void clearCaches(),
>>>> with the first one called just before building MemorySSA, and the
>>>> second one called afterwards.
>>>>
>>>> Again, I'm looking into how to make this available but also contain the
>>>> lifespan of these internal caches to only "as long as it takes for this
>>>> other analysis pass to be built".
>>>>
>>>>
>>>> Why then? Isn't the information valid so long as the IR is not mutated?
>>>>
>>>>  -Hal
>>>>
>>>>
>>>>
>>>> Suggestions and feedback are most welcome!
>>>>
>>>> Thanks,
>>>> Alina
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing listllvm-dev at lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>> --
>>>> Hal Finkel
>>>> Lead, Compiler Technology and Programming Languages
>>>> Leadership Computing Facility
>>>> Argonne National Laboratory
>>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190315/89dec61c/attachment.html>