Chandler Carruth
2015-Jan-16 21:11 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
I'm pretty sure I had the ordering of the passes backwards. The previous ordering is correct. Sorry for the confusion. The last alias analysis created is the first one queried. It delegates to the previous alias analysis created. At least, that is my reading of this (very confusing) code. The most frustrating aspect of this is that it means the delegation behavior of CFL shouldn't have mattered at all because BasicAA ran first... However BasicAA does do its own caching, so who knows. On Fri, Jan 16, 2015 at 12:22 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> Okay, overnight i ran a ton of tests on this patch, and it seems right. > Nick, Hal, can you review it? > > I've reattached it for simplicity > > > On Thu, Jan 15, 2015 at 3:05 PM, Daniel Berlin <dberlin at dberlin.org> > wrote: > >> >> >> On Thu, Jan 15, 2015 at 1:26 PM, Nick Lewycky <nlewycky at google.com> >> wrote: >> >>> On 15 January 2015 at 13:10, Daniel Berlin <dberlin at dberlin.org> wrote: >>> >>>> Yes. >>>> I've attached an updated patch that does the following: >>>> >>>> 1. Fixes the partialalias of globals/arguments >>>> 2. Enables partialalias for cases where nothing has been unified to a >>>> global/argument >>>> 3. Fixes that select was unifying the condition to the other pieces >>>> (the condition does not need to be processed :P). This was causing >>>> unnecessary aliasing. >>>> >>> >>> Consider this: >>> >>> void *p = ...; >>> uintptr_t i = p; >>> uintptr_t j = 0; >>> for (int a = 0; a < sizeof(uintptr_t); ++a) { >>> j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0; >>> j <<= 1; >>> } >>> void *q = j; >>> >>> alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the >>> equivalent LLVM IR. Please don't make me rewrite my example in LLVM IR.) >>> >>> Agreed :) >> >> But after chatting with you, i think we both agree that this change does >> not affect. >> I probably should not have said "the condition does not need to be >> processed". It would be more accurate to say "the reference to a condition >> in a select instruction, by itself, does not cause aliasing" >> >> What happens now is: >> >> given %4 = select %1, %2, %3 >> >> we do >> aliasset(%4) += %1 >> aliasset(%4) += %2 >> aliasset(%4) += %3 >> >> The first one is unnecessary. >> There can be no alias caused simply because it is referenced in condition >> of the select. >> >>> We still need to process what %1 refers to (and we do). >> >> >> To make this empirical, in your example, we get the right answer in >> CFL-AA. >> >> Interestingly, i'll point out that basic-aa says: >> NoAlias: i8* %p, i8** %q >> NoAlias: i8** %p.addr, i8** %q >> >> (I translated your case as best i can :P) >> >> So you may want to implement it for real if you think it's supposed to be >> handled right in basic-aa, because I don't believe it is :) >> >> > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/0bc511ff/attachment.html>
Daniel Berlin
2015-Jan-16 21:35 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
As we chatted about offline, i think we all agree this ordering is completely and utterly broken (right now it's BasicAA,ScopedAA, TBAA, CFLAA), and that BasicAA should really be going last. But this is also currently deliberate to "support type punning".[1] But i'm not in for fixing that right now, and it doesn't change that CFLAA was not delegating properly, and doesn't change how to fix this CFLAA bug :) Patch updated to revert ordering changes and attached [1] I know you have some ideas on how to fix this, but actually, I wonder if it wouldn't be better to move deliberate type punning into it's own AliasAnalysis, where the behavior will be both obvious and hopefully written well. Then we can just run that at the top of the stack. Certainly, your way was easier :) On Fri Jan 16 2015 at 1:11:46 PM Chandler Carruth <chandlerc at google.com> wrote:> I'm pretty sure I had the ordering of the passes backwards. The previous > ordering is correct. Sorry for the confusion. > > The last alias analysis created is the first one queried. It delegates to > the previous alias analysis created. At least, that is my reading of this > (very confusing) code. > > The most frustrating aspect of this is that it means the delegation > behavior of CFL shouldn't have mattered at all because BasicAA ran first... > However BasicAA does do its own caching, so who knows. > > On Fri, Jan 16, 2015 at 12:22 PM, Daniel Berlin <dberlin at dberlin.org> > wrote: > >> Okay, overnight i ran a ton of tests on this patch, and it seems right. >> Nick, Hal, can you review it? >> >> I've reattached it for simplicity >> >> >> On Thu, Jan 15, 2015 at 3:05 PM, Daniel Berlin <dberlin at dberlin.org> >> wrote: >> >>> >>> >>> On Thu, Jan 15, 2015 at 1:26 PM, Nick Lewycky <nlewycky at google.com> >>> wrote: >>> >>>> On 15 January 2015 at 13:10, Daniel Berlin <dberlin at dberlin.org> wrote: >>>> >>>>> Yes. >>>>> I've attached an updated patch that does the following: >>>>> >>>>> 1. Fixes the partialalias of globals/arguments >>>>> 2. Enables partialalias for cases where nothing has been unified to a >>>>> global/argument >>>>> 3. Fixes that select was unifying the condition to the other pieces >>>>> (the condition does not need to be processed :P). This was causing >>>>> unnecessary aliasing. >>>>> >>>> >>>> Consider this: >>>> >>>> void *p = ...; >>>> uintptr_t i = p; >>>> uintptr_t j = 0; >>>> for (int a = 0; a < sizeof(uintptr_t); ++a) { >>>> j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0; >>>> j <<= 1; >>>> } >>>> void *q = j; >>>> >>>> alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the >>>> equivalent LLVM IR. Please don't make me rewrite my example in LLVM IR.) >>>> >>>> Agreed :) >>> >>> But after chatting with you, i think we both agree that this change does >>> not affect. >>> I probably should not have said "the condition does not need to be >>> processed". It would be more accurate to say "the reference to a condition >>> in a select instruction, by itself, does not cause aliasing" >>> >>> What happens now is: >>> >>> given %4 = select %1, %2, %3 >>> >>> we do >>> aliasset(%4) += %1 >>> aliasset(%4) += %2 >>> aliasset(%4) += %3 >>> >>> The first one is unnecessary. >>> There can be no alias caused simply because it is referenced in >>> condition of the select. >>> >>>> We still need to process what %1 refers to (and we do). >>> >>> >>> To make this empirical, in your example, we get the right answer in >>> CFL-AA. >>> >>> Interestingly, i'll point out that basic-aa says: >>> NoAlias: i8* %p, i8** %q >>> NoAlias: i8** %p.addr, i8** %q >>> >>> (I translated your case as best i can :P) >>> >>> So you may want to implement it for real if you think it's supposed to >>> be handled right in basic-aa, because I don't believe it is :) >>> >>> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >>-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/17cc9970/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: cflaafix.diff Type: application/octet-stream Size: 4853 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/17cc9970/attachment.obj>
Xinliang David Li
2015-Jan-16 22:31 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
A couple of general comments. There are two types of alias info : analysis based and assertion based. For analysis based alias analysis, the ordering has a slight impact on compiler time. To make the query faster, it is conceivably better to put the one with the highest chances to give definitive answers (NoAlias, MustAlias, PartialMusAlias) first. Assertion based alias (TypeAA, restrict etc) is a different animal because we want the opportunity to detect user errors ( give warning or correct it). However unless we expect the MayAlias result from downstream alias to be able to override the NoAlias result from TypeAA, it may be ok to just put TypeAA the last in the pipe, i.e., violations of typeAA have already been caught as Must/Partial Aliases in upstream alias info providers (of course, we won't be able to warn user in this pipeline). David On Fri, Jan 16, 2015 at 1:35 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> As we chatted about offline, i think we all agree this ordering is > completely and utterly broken > (right now it's BasicAA,ScopedAA, TBAA, CFLAA), and that BasicAA should > really be going last. > But this is also currently deliberate to "support type punning".[1] > > But i'm not in for fixing that right now, and it doesn't change that CFLAA > was not delegating properly, and doesn't change how to fix this CFLAA bug :) > > Patch updated to revert ordering changes and attached > > [1] I know you have some ideas on how to fix this, but actually, I wonder > if it wouldn't be better to move deliberate type punning into it's own > AliasAnalysis, where the behavior will be both obvious and hopefully > written well. Then we can just run that at the top of the stack. > Certainly, your way was easier :) > > > On Fri Jan 16 2015 at 1:11:46 PM Chandler Carruth <chandlerc at google.com> > wrote: > >> I'm pretty sure I had the ordering of the passes backwards. The previous >> ordering is correct. Sorry for the confusion. >> >> The last alias analysis created is the first one queried. It delegates to >> the previous alias analysis created. At least, that is my reading of this >> (very confusing) code. >> >> The most frustrating aspect of this is that it means the delegation >> behavior of CFL shouldn't have mattered at all because BasicAA ran first... >> However BasicAA does do its own caching, so who knows. >> >> On Fri, Jan 16, 2015 at 12:22 PM, Daniel Berlin <dberlin at dberlin.org> >> wrote: >> >>> Okay, overnight i ran a ton of tests on this patch, and it seems right. >>> Nick, Hal, can you review it? >>> >>> I've reattached it for simplicity >>> >>> >>> On Thu, Jan 15, 2015 at 3:05 PM, Daniel Berlin <dberlin at dberlin.org> >>> wrote: >>> >>>> >>>> >>>> On Thu, Jan 15, 2015 at 1:26 PM, Nick Lewycky <nlewycky at google.com> >>>> wrote: >>>> >>>>> On 15 January 2015 at 13:10, Daniel Berlin <dberlin at dberlin.org> >>>>> wrote: >>>>> >>>>>> Yes. >>>>>> I've attached an updated patch that does the following: >>>>>> >>>>>> 1. Fixes the partialalias of globals/arguments >>>>>> 2. Enables partialalias for cases where nothing has been unified to a >>>>>> global/argument >>>>>> 3. Fixes that select was unifying the condition to the other pieces >>>>>> (the condition does not need to be processed :P). This was causing >>>>>> unnecessary aliasing. >>>>>> >>>>> >>>>> Consider this: >>>>> >>>>> void *p = ...; >>>>> uintptr_t i = p; >>>>> uintptr_t j = 0; >>>>> for (int a = 0; a < sizeof(uintptr_t); ++a) { >>>>> j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0; >>>>> j <<= 1; >>>>> } >>>>> void *q = j; >>>>> >>>>> alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the >>>>> equivalent LLVM IR. Please don't make me rewrite my example in LLVM IR.) >>>>> >>>>> Agreed :) >>>> >>>> But after chatting with you, i think we both agree that this change >>>> does not affect. >>>> I probably should not have said "the condition does not need to be >>>> processed". It would be more accurate to say "the reference to a condition >>>> in a select instruction, by itself, does not cause aliasing" >>>> >>>> What happens now is: >>>> >>>> given %4 = select %1, %2, %3 >>>> >>>> we do >>>> aliasset(%4) += %1 >>>> aliasset(%4) += %2 >>>> aliasset(%4) += %3 >>>> >>>> The first one is unnecessary. >>>> There can be no alias caused simply because it is referenced in >>>> condition of the select. >>>> >>>>> We still need to process what %1 refers to (and we do). >>>> >>>> >>>> To make this empirical, in your example, we get the right answer in >>>> CFL-AA. >>>> >>>> Interestingly, i'll point out that basic-aa says: >>>> NoAlias: i8* %p, i8** %q >>>> NoAlias: i8** %p.addr, i8** %q >>>> >>>> (I translated your case as best i can :P) >>>> >>>> So you may want to implement it for real if you think it's supposed to >>>> be handled right in basic-aa, because I don't believe it is :) >>>> >>>> >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >>> > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150116/8fe5dad5/attachment.html>
Hal Finkel
2015-Jan-17 07:34 UTC
[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
----- Original Message -----> From: "Daniel Berlin" <dberlin at dberlin.org> > To: "Chandler Carruth" <chandlerc at google.com> > Cc: "George Burgess IV" <george.burgess.iv at gmail.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu>, > "Jiangning Liu" <Jiangning.Liu at arm.com> > Sent: Friday, January 16, 2015 3:35:18 PM > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57 numbers > > > As we chatted about offline, i think we all agree this ordering is > completely and utterly broken > (right now it's BasicAA,ScopedAA, TBAA, CFLAA), and that BasicAA > should really be going last. > But this is also currently deliberate to "support type punning".[1] > > > > But i'm not in for fixing that right now, and it doesn't change that > CFLAA was not delegating properly, and doesn't change how to fix > this CFLAA bug :) > > > Patch updated to revert ordering changes and attached > > > [1] I know you have some ideas on how to fix this, but actually, I > wonder if it wouldn't be better to move deliberate type punning into > it's own AliasAnalysis, where the behavior will be both obvious and > hopefully written well. Then we can just run that at the top of the > stack. Certainly, your way was easier :)Wouldn't such a pass look a lot like BasicAA, perhaps minus the PHI-speculation bits? I worry that, once SROA, etc. get their hands on strucure accesses, structure-element type punning looks a lot like the general case that BasicAA currently handles. -Hal> > > > On Fri Jan 16 2015 at 1:11:46 PM Chandler Carruth < > chandlerc at google.com > wrote: > > > > I'm pretty sure I had the ordering of the passes backwards. The > previous ordering is correct. Sorry for the confusion. > > > The last alias analysis created is the first one queried. It > delegates to the previous alias analysis created. At least, that is > my reading of this (very confusing) code. > > > The most frustrating aspect of this is that it means the delegation > behavior of CFL shouldn't have mattered at all because BasicAA ran > first... However BasicAA does do its own caching, so who knows. > > > > > On Fri, Jan 16, 2015 at 12:22 PM, Daniel Berlin < dberlin at dberlin.org > > wrote: > > > > > > Okay, overnight i ran a ton of tests on this patch, and it seems > right. > Nick, Hal, can you review it? > > > I've reattached it for simplicity > > > > > > > On Thu, Jan 15, 2015 at 3:05 PM, Daniel Berlin < dberlin at dberlin.org > > wrote: > > > > > > > > On Thu, Jan 15, 2015 at 1:26 PM, Nick Lewycky < nlewycky at google.com > > wrote: > > > > > > On 15 January 2015 at 13:10, Daniel Berlin < dberlin at dberlin.org > > wrote: > > > > Yes. > I've attached an updated patch that does the following: > > > 1. Fixes the partialalias of globals/arguments > 2. Enables partialalias for cases where nothing has been unified to a > global/argument > 3. Fixes that select was unifying the condition to the other pieces > (the condition does not need to be processed :P). This was causing > unnecessary aliasing. > > > Consider this: > > > > void *p = ...; > uintptr_t i = p; > uintptr_t j = 0; > for (int a = 0; a < sizeof(uintptr_t); ++a) { > j = i >> (sizeof(uintptr_t) - a - 1) ? 1 : 0; > j <<= 1; > } > void *q = j; > > > alias(p, q) isn't NoAlias. (Okay, it kinda is in C++, but not in the > equivalent LLVM IR. Please don't make me rewrite my example in LLVM > IR.) > > > Agreed :) > > > But after chatting with you, i think we both agree that this change > does not affect. > I probably should not have said "the condition does not need to be > processed". It would be more accurate to say "the reference to a > condition in a select instruction, by itself, does not cause > aliasing" > > > What happens now is: > > > given %4 = select %1, %2, %3 > > > we do > aliasset(%4) += %1 > aliasset(%4) += %2 > aliasset(%4) += %3 > > The first one is unnecessary. > There can be no alias caused simply because it is referenced in > condition of the select. > > > > > > We still need to process what %1 refers to (and we do). > > > > > To make this empirical, in your example, we get the right answer in > CFL-AA. > > > Interestingly, i'll point out that basic-aa says: > > NoAlias: i8* %p, i8** %q > NoAlias: i8** %p.addr, i8** %q > > > (I translated your case as best i can :P) > > > So you may want to implement it for real if you think it's supposed > to be handled right in basic-aa, because I don't believe it is :) > > > > > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory