Alina Sbirlea via llvm-dev
2019-Mar-05 06:22 UTC
[llvm-dev] RFC: Contained stateful AliasAnalysis
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/20190304/32c6bd0b/attachment.html>
Alina Sbirlea via llvm-dev
2019-Mar-05 23:14 UTC
[llvm-dev] RFC: Contained stateful AliasAnalysis
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/20190305/da9fbcd4/attachment.html>
Alina Sbirlea via llvm-dev
2019-Mar-13 19:37 UTC
[llvm-dev] RFC: Contained stateful AliasAnalysis
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>