[llvm-dev] RFC: Contained stateful AliasAnalysis

[Alina Sbirlea via llvm-dev]

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/20190313/293d8eba/attachment.html>