[LLVMdev] question about enabling cfl-aa and collecting a57 numbers

[Hal Finkel]

----- 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