llvm dev - Jan 2015 - [LLVMdev] question about enabling cfl-aa and collecting a57 numbers

No, i mean the actual store instruction looks like "store i16 %conv22, i16*
getelementptr inbounds ([16 x i16]* @pA, i64 0, i64 12), align 2, !tbaa !1"

Not that the pointer operand comes from a GEP, but it is a constantexpr,
whose opcode is GEP.

It sucks that there is such a complex thing to be handled as a store
operand directly , but such is life  ...

CFL-AA  *should* treat this like an assignment to GEP operand, not like a
normal store, which is *x = y. This is really *(&GEP operand) = y.

But currently, it does nothing right here :)

I haven't tracked down entirely what is happening, but for sure,
visitStoreInst doesn't do the right thing in this case.
Fixing that still gives a wrong result, i haven't started to track down
what *else* is going on here.

I suspect either more ConstantExpr related bugs, or  the global attribute
is not being fully propagated around or something.



On Fri Jan 23 2015 at 4:45:34 PM Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Daniel Berlin" <dberlin at dberlin.org>
> > To: "Ana Pazos" <apazos at codeaurora.org>,
"George Burgess IV" <
> george.burgess.iv at gmail.com>
> > Cc: "Jiangning Liu" <Jiangning.Liu at arm.com>,
"LLVM Developers Mailing
> List" <llvmdev at cs.uiuc.edu>, "Hal Finkel"
> > <hfinkel at anl.gov>
> > Sent: Friday, January 23, 2015 5:09:06 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
a57
> numbers
> >
> >
> > Without the patch is also returns the wrong answer for all of these,
> > it just doesn't cause LICM to promote because it returns
> > PartialAlias (which is still wrong).
> >
> >
> > We return may-alias instead, and now suddenly it's happy to
promote
> > them.
> >
> >
> > The broken noalias results exist both before and after my patch:
> >
> >
> > ===== Alias Analysis Evaluator Report ====> > 521 Total Alias
Queries Performed
> > 176 no alias responses (33.7%)
> > - 334 may alias responses (64.1%)
> > - 10 partial alias responses (1.9%)
> > + 344 may alias responses (66.0%)
> > + 0 partial alias responses (0.0%)
> > 1 must alias responses (0.1%)
> >
> >
> >
> >
> > I suspect this is all caused by a different set of bugs:
> >
> >
> > 1. visitStoreInst does not appear to handle the case of value being a
> > GEP properly (Personally, i had no idea this was allowed ...)
> >
>
> You mean that the value being stored is a pointer value coming from a GEP?
> Why would that be special (compared to any other way of generating a
> pointer value, inttoptr for example)?
>
> >
> > It should somehow call into the visitGEP code, but it doesn't.
> >
> >
> > Thus, it never assigns anything into the value of the global.
> > 2. Something is either busted in querying or in attributes for stores
> > that have geps directly as their pointer value.
> >
> >
> >
> >
> >
> > I will work up a separate patch for this issue unless someone thinks
> > i should shoehorn it into the existing patch.
> >
> >
>
> A separate patch is good.
>
> Thanks again,
> Hal
>
> >
> >
> >
> >
> >
> >
> >
> > On Fri Jan 23 2015 at 12:52:02 PM Ana Pazos < apazos at
codeaurora.org >
> > wrote:
> >
> >
> >
> >
> >
> >
> > Hi Daniel,
> >
> >
> >
> > There are correctness issues with the latest patch (from Wed
> > 1/21/2015 11:10 AM with “Updated testcases to have MayAlias/note
> > issues as FIXME”).
> >
> >
> >
> > I looked at one of the failures and it has to do with disambiguating
> > array indexes.
> >
> >
> >
> > With CFL AA enabled, LICM promotion is sinking stores outside of the
> > loop incorrectly. If I disable LICM promotion, the tests pass.
> >
> >
> >
> > Find attached a reduced test case.
> >
> >
> >
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm
> > -use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 1)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 2)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 3)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 4)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 5)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 6)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 7)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 8)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 9)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 10)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 11)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 12)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 13)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 14)
> >
> > LICM: Promoting value stored to in loop: i16* getelementptr inbounds
> > ([16 x i16]* @pA, i64 0, i64 15)
> >
> > LICM sinking instruction: %conv32 = trunc i32 %add31 to i16
> >
> > LICM sinking instruction: %add31 = sub nsw i32 %conv18, %conv17
> >
> > LICM sinking instruction: %conv22 = trunc i32 %sub to i16
> >
> > LICM sinking instruction: %sub = sub nsw i32 %conv17, %conv18
> >
> > LICM sinking instruction: %conv19 = trunc i32 %add to i16
> >
> >
> >
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm
> > –use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm -mllvm
> > -disable-licm-promotion
> >
> > ok
> >
> >
> >
> > If you look at the .ll file, you notice that pointer p alias with pA:
> >
> >
> >
> > %p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 0), %for.body ], [ %incdec.ptr49, %for.body48 ]
> >
> > …
> >
> > for.body48: ; preds = %for.cond45
> >
> > %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1
> >
> >
> >
> > CFL AA disambiguates p, pA[0], but not the other indexes (coming from
> > incdec.ptr49 updates):
> >
> > MayAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 0), align 2, !tbaa !1
> >
> > NoAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 1), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 2), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 3), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 4), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 5), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 6), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 7), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 8), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 9), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 10), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 11), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 12), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 13), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 14), align 2, !tbaa !1
> >
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 15), align 2, !tbaa !1
> >
> >
> >
> > Basic AA disambiguates them all:
> >
> > opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases
> > -print-may-aliases -disable-output test2.ll
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 0), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 1), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 2), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 3), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 4), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 5), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 6), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 7), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 8), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 9), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 10), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 11), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 12), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 13), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 14), align 2, !tbaa !1
> >
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 15), align 2, !tbaa !1
> >
> >
> >
> > Thanks,
> >
> > Ana.
> >
> >
> >
> >
> >
> > From: llvmdev-bounces at cs.uiuc.edu [mailto: llvmdev-bounces at cs.
> > uiuc.edu ] On Behalf Of George Burgess IV
> > Sent: Thursday, January 22, 2015 5:47 PM
> > To: Daniel Berlin
> > Cc: Jiangning Liu; LLVM Developers Mailing List
> >
> >
> >
> >
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
> > a57 numbers
> >
> >
> >
> >
> >
> >
> > Works for me
> >
> >
> >
> >
> >
> > On Thu, Jan 22, 2015 at 8:27 PM, Daniel Berlin < dberlin at
dberlin.org
> > > wrote:
> >
> >
> >
> >
> > We should use graph edges, so we can do something better at set build
> > time :)
> >
> >
> >
> >
> >
> >
> > On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> >
> >
> >
> >
> > > Should we be added an edge from the inttoptr to all other pointer
> > > values? Is there a better way?
> >
> >
> >
> >
> >
> >
> > We can add a special "Unknown" StratifiedAttr and query it
before
> > anything else, i.e:
> >
> >
> >
> >
> >
> > // in CFLAliasAnalysis::query, as the first potential return
> >
> >
> > if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])
> >
> >
> > return MayAlias;
> >
> >
> >
> >
> >
> > The only *potential* issue with this approach would be that in the
> > following code segment:
> >
> >
> >
> >
> >
> > void fn() {
> >
> >
> > int *foo = (int*)rand();
> >
> >
> > int *bar = new int;
> >
> >
> > int **baz = rand() ? &foo : &bar;
> >
> >
> > int value = **baz;
> >
> >
> > }
> >
> >
> >
> >
> >
> > The stratified sets would look like:
> >
> >
> > {value} is below {foo, bar} is below {baz}.
> >
> >
> >
> >
> >
> > Potential issue: The sets {foo, bar} and {value} would be marked with
> > the "Unknown" attribute, while {baz} would have no
attributes. I
> > can't immediately think of a case where {baz} lacking
"Unknown"
> > would be harmful, but if such a case exists, then we may need a
> > different approach.
> >
> >
> >
> >
> >
> >
> > George
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel < hfinkel at anl.gov
>
> > wrote:
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > From: "Daniel Berlin" < dberlin at dberlin.org >
> > To: "Hal Finkel" < hfinkel at anl.gov >
> > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"George Burgess IV" <
> > george.burgess.iv at gmail.com >, "LLVM Developers
> > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick
Lewycky" <
> > nlewycky at google.com >
> > Sent: Wednesday, January 21, 2015 3:48:25 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
> > a57 numbers
> >
> > On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < hfinkel at anl.gov
>
> > wrote:
> >
> > ----- Original Message -----
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"George Burgess IV"
> > > < george.burgess.iv at gmail.com >, "LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick
Lewycky" <
> > > nlewycky at google.com >
> > > Sent: Wednesday, January 21, 2015 1:10:07 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting a57 numbers
> > >
> > > Updated testcases to have MayAlias/note issues as FIXME.
> > >
> >
> > Okay, thanks! This LGTM, but we should probably split the delegation
> > fixes from the others and commit as two separate patches (especially
> > because Ana noted some potential miscompiles caused by the other
> > improvements).
> >
> >
> >
> > I think she mentioned the miscompiles due to us returning
> > partialalias. But in any case, i 'm happy to, but just to note
they
> > are all required to get the LICM issue fixed :)
> >
> >
> > Okay, please do that and commit them.
> >
> >
> >
> >
> >
> >
> > Regarding this:
> >
> > @@ -768,7 +774,10 @@ static Optional<StratifiedAttr>
> > valueToAttrIndex(Value *Val) {
> > return AttrGlobalIndex;
> >
> > if (auto *Arg = dyn_cast<Argument>(Val))
> > - if (!Arg->hasNoAliasAttr())
> > + // Only pointer arguments should have the argument attribute,
> > + // because things can't escape through scalars without us seeing
a
> > + // cast, and thus, interaction with them doesn't matter.
> > + if (!Arg->hasNoAliasAttr() &&
Arg->getType()->isPointerTy())
> > return argNumberToAttrIndex(Arg-> getArgNo());
> > return NoneType();
> > }
> >
> > when we do see the inttoptr case, we add an edge from the source to
> > the destination.
> >
> >
> > Correct.
> >
> >
> > If we've not noted potential aliasing of the non-pointer-typed
> > argument, then does this end up looking like a unique global?
> >
> >
> >
> > No. It will end up looking like something that points to nothing.
> > Even without this change, it will end up looking like something that
> > points to nothing, it will just have an attribute that says
> > "argument". :)
> >
> >
> > Okay, fair enough.
> >
> >
> >
> >
> >
> > You can come up with cases where even with this attribute set, it
> > will get the wrong answer. It just happens to have code that,
> > through luck, gets the right answer in a lot of cases:
> >
> > (That is this code:
> >
> >
> > if (AttrsA.any() && AttrsB.any())
> > return AliasAnalysis::MayAlias;
> > )
> >
> >
> > So there is a bug here, but it's not caused by this code.
> >
> >
> > The bug here is that we can't ever know what happens as the result
of
> > inttoptr. We never do math, and the tracking we do is never going to
> > be sufficient to determine the range of possible pointers for an
> > inttoptr in all cases (in theory, it could point to anything
> > anywhere in the program. If we knew the sizes of *all* objects, and
> > any binary operator performed on it was evaluable, we could do a
> > little better. If we knew the value came from a ptrtoint, we could
> > do better, etc).
> > Same with ptrtoint.
> >
> >
> > The result of both of these instructions should start to be "we
have
> > no idea what the pointer that comes from inttoptr or goes to
> > ptrtoint points to", and we should return mayalias for anything
that
> > interacts with them.
> > We don't do that right now.
> > We are just hiding it mildly well.
> >
> >
> > Should we be added an edge from the inttoptr to all other pointer
> > values? Is there a better way?
> >
> >
> >
> >
> >
> >
> >
> >
> > Speaking of which, the code has checks for global variables in
> > several places. Do these need to be for globals that are not aliases
> > and don't have weak linkage?
> >
> >
> >
> > It's more a question of whether they are in SSA form than if they
are
> > globals.
> >
> >
> > It's effectively using Globals/Arguments as a way to say
"don't know"
> > in some cases, where it should really just say "don't
know".
> >
> >
> > There is a bunch of code i now have marked for cleanup and bugfixes
> > around these issues (constant vs global handling, handling of
> > non-pointer values, etc).
> >
> >
> > Okay, thanks!
> >
> >
> >
> >
> >
> > As mentioned, the above is necessary to fix the LICM issue (and is
> > correct, even if somewhere else is wrong. For reference, GCC does
> > the identical thing to what i'm saying :P), but i'm happy to
move it
> > to a separate fix (that includes fixes for the other
> > argument/unknown related issues) if you like.
> >
> >
> >
> >
> > Generically speaking, I'd prefer the fixes to be broken up as much
as
> > practical. Please go ahead and commit them.
> >
> > -Hal
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > Thanks again,
> > Hal
> >
> > >
> > >
> > >
> > >
> > > On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel < hfinkel at
anl.gov >
> > > wrote:
> > >
> > >
> > > ----- Original Message -----
> > > > From: "Daniel Berlin" < dberlin at dberlin.org
>
> > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com
>, "George Burgess
> > > > IV"
> > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > nlewycky at google.com >
> > > > Sent: Tuesday, January 20, 2015 1:48:44 PM
> > > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > > collecting a57 numbers
> > > >
> > > > So, I can make all these testcases work, but it's a
little tricky
> > > > (it
> > > > involves tracking some things, like GEP byte range, and then
> > > > checking bases and using getObjectSize, much like BasicAA
does).
> > > >
> > > >
> > > > Because i really don't want to put that much "not
well tested"
> > > > code
> > > > in a bugfix, and honestly, i'm not sure we will catch
any cases
> > > > here
> > > > that BasicAA does not, i've attached a change to XFAIL
these
> > > > testcases, and updated the code to return MayAlias.
> > >
> > > Okay. I think you might as well just update the test cases to
want
> > > MayAlias, and put a FIXME comment explaining that they could be
> > > PartialAlias. As far as I know, there is no code in LLVM that
> > > really
> > > handles a PartialAlias differently than a MayAlias or MustAlias,
> > > and
> > > so while there may be some benefit here, I'm not sure it will
be
> > > worth the effort.
> > >
> > > >
> > > > I will build and test a patch to get these back to
PartialAlias,
> > > > but
> > > > this patch will at least get us to not be "giving wrong
answers".
> > > > I
> > > > will also see if we catch anything with it that BasicAA does
not,
> > > > because if we don't, it doesn't seem worth it to me.
> > >
> > > My guess is that BasicAA will get almost all of the interesting
> > > PartialAlias cases, and as I said, we essentially ignore them
> > > anyway.
> > >
> > > As a side note, there is this one place in lib/Analysis/
> > > MemoryDependenceAnalysis.cpp that could use some attention:
> > >
> > > #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting
> > > loads
> > > // in terms of clobbering loads, but since it does this by
looking
> > > // at the clobbering load directly, it doesn't know about any
> > > // phi translation that may have happened along the way.
> > >
> > > // If we have a partial alias, then return this as a clobber for
> > > the
> > > // client to handle.
> > > if (R == AliasAnalysis::PartialAlias)
> > > return MemDepResult::getClobber(Inst) ;
> > > #endif
> > >
> > > >
> > > >
> > > > Conservative new patch attached.
> > > >
> > > >
> > > >
> > > > (Note that i still updated the testcases, because we will
*never*
> > > > be
> > > > able to legally return PartialAlias as they were written)
> > > >
> > >
> > > Yes, sounds good.
> > >
> > > -Hal
> > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin <
> > > > dberlin at dberlin.org
> > > > > wrote:
> > > >
> > > >
> > > >
> > > > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel < hfinkel at
anl.gov >
> > > > wrote:
> > > >
> > > >
> > > > ----- Original Message -----
> > > > > From: "Daniel Berlin" < dberlin at
dberlin.org >
> > > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > > Cc: "Jiangning Liu" < Jiangning.Liu at
arm.com >, "George Burgess
> > > > > IV"
> > > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > > nlewycky at google.com >
> > > > > Sent: Saturday, January 17, 2015 1:08:10 PM
> > > > > Subject: Re: [LLVMdev] question about enabling cfl-aa
and
> > > > > collecting a57 numbers
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel <
hfinkel at anl.gov
> > > > > >
> > > > > wrote:
> > > > >
> > > > >
> > > > > Hi Danny,
> > > > >
> > > > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis
so that
> > > > > // BasicAliasAnalysis wins if they disagree. This is
intended
> > > > > to
> > > > > help
> > > > > // support "obvious" type-punning idioms.
> > > > > - if (UseCFLAA)
> > > > > - addPass( createCFLAliasAnalysisPass());
> > > > > addPass( createTypeBasedAliasAnalysisPa ss());
> > > > > addPass( createScopedNoAliasAAPass());
> > > > > + if (UseCFLAA)
> > > > > + addPass( createCFLAliasAnalysisPass());
> > > > > addPass( createBasicAliasAnalysisPass() );
> > > > >
> > > > > Do we really want to change the order here? I had
originally
> > > > > placed
> > > > > it after the metadata-based passes thinking that the
> > > > > compile-time
> > > > > would be better (guessing that the metadata queries
would be
> > > > > faster
> > > > > than the CFL queries, so if the metadata could quickly
return a
> > > > > NoAlias, then we'd cut out unecessary CFL queries).
Perhaps
> > > > > this
> > > > > is
> > > > > an irrelevant effect, but we should have some
documented
> > > > > rationale.
> > > > >
> > > > >
> > > > >
> > > > > Yeah, this was a mistake (Chandler had suggested it was
right
> > > > > earlier, but we were both wrong :P)
> > > > >
> > > > >
> > > > >
> > > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > > -define i8 @test0(i8* %base, i1 %x) {
> > > > > +define i8 @test0(i1 %x) {
> > > > > entry:
> > > > > + %base = alloca i8, align 4
> > > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > > br i1 %x, label %red, label %green
> > > > > red:
> > > > > @@ -25,8 +26,9 @@ green:
> > > > > }
> > > > >
> > > > > why should this return PartialAlias? %ohi does
partially
> > > > > overlap,
> > > > > so
> > > > > this correct, but what happens when the overlap is
partial or
> > > > > control dependent?
> > > > > So, after talking with some people offline, they
convinced me
> > > > > in
> > > > > SSA
> > > > > form, the name would change in these situations, and
the only
> > > > > situations you can get into trouble is with things
"based on
> > > > > pointer
> > > > > arguments" (because you have no idea what their
initial state
> > > > > is),
> > > > > or "globals" (because they are not in SSA
form)
> > > > > I could not come up with a case otherwise
> > > >
> > > > Okay; that part of the code could really use some more
> > > > commentary.
> > > > I'd really appreciate it if you should put these
thoughts in
> > > > written
> > > > form that could be added as comments.
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > Will do
> > > >
> > > >
> > > >
> > > > > But i'm welcome to hear if you think this is wrong.
> > > > >
> > > > > FWIW: I bootstrapped/tested the compiler with an assert
that
> > > > > triggered if CFL-AA was going to return PartialAlias
and
> > > > > BasicAA
> > > > > would have returned NoAlias, and it did not trigger
with this
> > > > > change.
> > > > >
> > > > >
> > > > > (It would have triggered before this set of changes)
> > > > >
> > > > > Not proof of course, but it at least tells me it's
not
> > > > > "obviously
> > > > > wrong" :)
> > > > >
> > > > >
> > > >
> > > > That's good :) -- but, not exactly what I was concerned
about.
> > > > Our
> > > > general convention has been that PartialAlias is a
"strong"
> > > > result,
> > > > like MustAlias, but implies that AA has proved that only a
> > > > partial
> > > > overlap will occur.
> > > >
> > > > So, in this test case we get the right result:
> > > >
> > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > define i8 @test0(i1 %x) {
> > > > entry:
> > > > %base = alloca i8, align 4
> > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > br i1 %x, label %red, label %green
> > > > red:
> > > > br label %green
> > > > green:
> > > > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
> > > > store i8 0, i8* %phi
> > > >
> > > > %bigbase0 = bitcast i8* %base to i16*
> > > > store i16 -1, i16* %bigbase0
> > > >
> > > > %loaded = load i8* %phi
> > > > ret i8 %loaded
> > > > }
> > > >
> > > > because %phi will have a partial overlap with %bigbase0, the
only
> > > > uncertainty is whether the overlap is with the low byte or
the
> > > > high
> > > > byte. But if I modify the test to be this:
> > > >
> > > > define i8 @test0x(i1 %x) {
> > > > entry:
> > > > %base = alloca i8, align 4
> > > > %baseplustwo = getelementptr i8* %base, i64 2
> > > > br i1 %x, label %red, label %green
> > > > red:
> > > > br label %green
> > > > green:
> > > > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
> > > > store i8 0, i8* %phi
> > > >
> > > > %bigbase0 = bitcast i8* %base to i16*
> > > > store i16 -1, i16* %bigbase0
> > > >
> > > > %loaded = load i8* %phi
> > > > ret i8 %loaded
> > > > }
> > > >
> > > > I still get this result:
> > > > PartialAlias: i16* %bigbase0, i8* %phi
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > but now %phi might not overlap %bigbase0 at all (although,
when
> > > > it
> > > > does, there is a partial overlap), so we should just return
> > > > MayAlias
> > > > (perhaps without delegation because this is a definitive
> > > > result?).
> > > >
> > > >
> > > >
> > > >
> > > > Yeah, i have to do some size checking, let me see if we have
the
> > > > info
> > > > and i'll update the patch.
> > > >
> > > >
> > > >
> > > >
> > > > Otherwise, my view is that we should always delegate
MayAlias,
> > > > because we have no idea what order the passes are in or what
pass
> > > > someone has inserted where :)
> > > >
> > > >
> > > > (WIW: I believe the same about everything except MustAlias
and
> > > > NoAlias, but currently we don't delegate PartialAlias.
> > > > We claim PartialAlias is a definitive result, but it really
> > > > isn't.
> > > > Right now we have TBAA that will give NoAlias results on
things
> > > > other
> > > > passes claim are PartialAlias, and that result is correct.
That's
> > > > just in our default, we have no idea what other people do.
Even
> > > > if
> > > > you ignore TBAA, plenty of other compilers have
noalias/mustalias
> > > > metadata that would have the same effect.
> > >
> > > --
> > > Hal Finkel
> > > Assistant Computational Scientist
> > > Leadership Computing Facility
> > > Argonne National Laboratory
> > >
> >
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> >
> >
> > --
> >
> >
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> >
> >
> >
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150124/727c006e/attachment.html>

----- Original Message -----
> From: "Daniel Berlin" <dberlin at dberlin.org>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Jiangning Liu" <Jiangning.Liu at arm.com>, "LLVM
Developers Mailing List" <llvmdev at cs.uiuc.edu>, "Ana
Pazos"
> <apazos at codeaurora.org>, "George Burgess IV"
<george.burgess.iv at gmail.com>
> Sent: Friday, January 23, 2015 7:14:24 PM
> Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting a57
numbers
> 
> 
> No, i mean the actual store instruction looks like "store i16
> %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> 12), align 2, !tbaa !1"
> 
> 
> Not that the pointer operand comes from a GEP, but it is a
> constantexpr, whose opcode is GEP.
Ah, yep. We have ConstantExpr analogs for just about everything. ;)
> 
> 
> It sucks that there is such a complex thing to be handled as a store
> operand directly , but such is life ...
> 
> 
> CFL-AA *should* treat this like an assignment to GEP operand, not
> like a normal store, which is *x = y. This is really *(&GEP operand)
> = y.
> 
> 
> But currently, it does nothing right here :)
> 
> 
> I haven't tracked down entirely what is happening, but for sure,
> visitStoreInst doesn't do the right thing in this case.
> Fixing that still gives a wrong result, i haven't started to track
> down what *else* is going on here.
> 
> 
> I suspect either more ConstantExpr related bugs, or the global
> attribute is not being fully propagated around or something.
> 
Fair enough.

 -Hal
> 
> 
> 
> 
> 
> On Fri Jan 23 2015 at 4:45:34 PM Hal Finkel < hfinkel at anl.gov >
> wrote:
> 
> 
> ----- Original Message -----
> > From: "Daniel Berlin" < dberlin at dberlin.org >
> > To: "Ana Pazos" < apazos at codeaurora.org >,
"George Burgess IV" <
> > george.burgess.iv at gmail.com >
> > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"LLVM Developers
> > Mailing List" < llvmdev at cs.uiuc.edu >, "Hal
Finkel"
> > < hfinkel at anl.gov >
> > Sent: Friday, January 23, 2015 5:09:06 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting a57 numbers
> > 
> > 
> > Without the patch is also returns the wrong answer for all of
> > these,
> > it just doesn't cause LICM to promote because it returns
> > PartialAlias (which is still wrong).
> > 
> > 
> > We return may-alias instead, and now suddenly it's happy to
promote
> > them.
> > 
> > 
> > The broken noalias results exist both before and after my patch:
> > 
> > 
> > ===== Alias Analysis Evaluator Report ====> > 521 Total Alias
Queries Performed
> > 176 no alias responses (33.7%)
> > - 334 may alias responses (64.1%)
> > - 10 partial alias responses (1.9%)
> > + 344 may alias responses (66.0%)
> > + 0 partial alias responses (0.0%)
> > 1 must alias responses (0.1%)
> > 
> > 
> > 
> > 
> > I suspect this is all caused by a different set of bugs:
> > 
> > 
> > 1. visitStoreInst does not appear to handle the case of value being
> > a
> > GEP properly (Personally, i had no idea this was allowed ...)
> > 
> 
> You mean that the value being stored is a pointer value coming from a
> GEP? Why would that be special (compared to any other way of
> generating a pointer value, inttoptr for example)?
> 
> > 
> > It should somehow call into the visitGEP code, but it doesn't.
> > 
> > 
> > Thus, it never assigns anything into the value of the global.
> > 2. Something is either busted in querying or in attributes for
> > stores
> > that have geps directly as their pointer value.
> > 
> > 
> > 
> > 
> > 
> > I will work up a separate patch for this issue unless someone
> > thinks
> > i should shoehorn it into the existing patch.
> > 
> > 
> 
> A separate patch is good.
> 
> Thanks again,
> Hal
> 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > On Fri Jan 23 2015 at 12:52:02 PM Ana Pazos < apazos at
codeaurora.org
> > >
> > wrote:
> > 
> > 
> > 
> > 
> > 
> > 
> > Hi Daniel,
> > 
> > 
> > 
> > There are correctness issues with the latest patch (from Wed
> > 1/21/2015 11:10 AM with “Updated testcases to have MayAlias/note
> > issues as FIXME”).
> > 
> > 
> > 
> > I looked at one of the failures and it has to do with
> > disambiguating
> > array indexes.
> > 
> > 
> > 
> > With CFL AA enabled, LICM promotion is sinking stores outside of
> > the
> > loop incorrectly. If I disable LICM promotion, the tests pass.
> > 
> > 
> > 
> > Find attached a reduced test case.
> > 
> > 
> > 
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm
> > -use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 1)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 2)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 3)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 4)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 5)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 6)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 7)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 8)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 9)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 10)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 11)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 12)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 13)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 14)
> > 
> > LICM: Promoting value stored to in loop: i16* getelementptr
> > inbounds
> > ([16 x i16]* @pA, i64 0, i64 15)
> > 
> > LICM sinking instruction: %conv32 = trunc i32 %add31 to i16
> > 
> > LICM sinking instruction: %add31 = sub nsw i32 %conv18, %conv17
> > 
> > LICM sinking instruction: %conv22 = trunc i32 %sub to i16
> > 
> > LICM sinking instruction: %sub = sub nsw i32 %conv17, %conv18
> > 
> > LICM sinking instruction: %conv19 = trunc i32 %add to i16
> > 
> > 
> > 
> > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast -mllvm
> > –use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm -mllvm
> > -disable-licm-promotion
> > 
> > ok
> > 
> > 
> > 
> > If you look at the .ll file, you notice that pointer p alias with
> > pA:
> > 
> > 
> > 
> > %p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0,
> > i64
> > 0), %for.body ], [ %incdec.ptr49, %for.body48 ]
> > 
> > …
> > 
> > for.body48: ; preds = %for.cond45
> > 
> > %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1
> > 
> > 
> > 
> > CFL AA disambiguates p, pA[0], but not the other indexes (coming
> > from
> > incdec.ptr49 updates):
> > 
> > MayAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 0), align 2, !tbaa !1
> > 
> > NoAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 1), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 2), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 3), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 4), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 5), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 6), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 7), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 8), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 9), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 10), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 11), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 12), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 13), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 14), align 2, !tbaa !1
> > 
> > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 15), align 2, !tbaa !1
> > 
> > 
> > 
> > Basic AA disambiguates them all:
> > 
> > opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases
> > -print-may-aliases -disable-output test2.ll
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 0), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 1), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 2), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 3), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 4), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 5), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 6), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 7), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 8), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 9), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 10), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 11), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 12), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 13), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 14), align 2, !tbaa !1
> > 
> > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store i16
> > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 15), align 2, !tbaa !1
> > 
> > 
> > 
> > Thanks,
> > 
> > Ana.
> > 
> > 
> > 
> > 
> > 
> > From: llvmdev-bounces at cs.uiuc.edu [mailto: llvmdev-bounces at cs.
> > uiuc.edu ] On Behalf Of George Burgess IV
> > Sent: Thursday, January 22, 2015 5:47 PM
> > To: Daniel Berlin
> > Cc: Jiangning Liu; LLVM Developers Mailing List
> > 
> > 
> > 
> > 
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting
> > a57 numbers
> > 
> > 
> > 
> > 
> > 
> > 
> > Works for me
> > 
> > 
> > 
> > 
> > 
> > On Thu, Jan 22, 2015 at 8:27 PM, Daniel Berlin <
> > dberlin at dberlin.org
> > > wrote:
> > 
> > 
> > 
> > 
> > We should use graph edges, so we can do something better at set
> > build
> > time :)
> > 
> > 
> > 
> > 
> > 
> > 
> > On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <
> > george.burgess.iv at gmail.com > wrote:
> > 
> > 
> > 
> > 
> > > Should we be added an edge from the inttoptr to all other pointer
> > > values? Is there a better way?
> > 
> > 
> > 
> > 
> > 
> > 
> > We can add a special "Unknown" StratifiedAttr and query it
before
> > anything else, i.e:
> > 
> > 
> > 
> > 
> > 
> > // in CFLAliasAnalysis::query, as the first potential return
> > 
> > 
> > if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])
> > 
> > 
> > return MayAlias;
> > 
> > 
> > 
> > 
> > 
> > The only *potential* issue with this approach would be that in the
> > following code segment:
> > 
> > 
> > 
> > 
> > 
> > void fn() {
> > 
> > 
> > int *foo = (int*)rand();
> > 
> > 
> > int *bar = new int;
> > 
> > 
> > int **baz = rand() ? &foo : &bar;
> > 
> > 
> > int value = **baz;
> > 
> > 
> > }
> > 
> > 
> > 
> > 
> > 
> > The stratified sets would look like:
> > 
> > 
> > {value} is below {foo, bar} is below {baz}.
> > 
> > 
> > 
> > 
> > 
> > Potential issue: The sets {foo, bar} and {value} would be marked
> > with
> > the "Unknown" attribute, while {baz} would have no
attributes. I
> > can't immediately think of a case where {baz} lacking
"Unknown"
> > would be harmful, but if such a case exists, then we may need a
> > different approach.
> > 
> > 
> > 
> > 
> > 
> > 
> > George
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel < hfinkel at anl.gov
>
> > wrote:
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > From: "Daniel Berlin" < dberlin at dberlin.org >
> > To: "Hal Finkel" < hfinkel at anl.gov >
> > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"George Burgess IV"
> > <
> > george.burgess.iv at gmail.com >, "LLVM Developers
> > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick
Lewycky" <
> > nlewycky at google.com >
> > Sent: Wednesday, January 21, 2015 3:48:25 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > collecting
> > a57 numbers
> > 
> > On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < hfinkel at anl.gov
>
> > wrote:
> > 
> > ----- Original Message -----
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"George Burgess
> > > IV"
> > > < george.burgess.iv at gmail.com >, "LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick
Lewycky" <
> > > nlewycky at google.com >
> > > Sent: Wednesday, January 21, 2015 1:10:07 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting a57 numbers
> > > 
> > > Updated testcases to have MayAlias/note issues as FIXME.
> > > 
> > 
> > Okay, thanks! This LGTM, but we should probably split the
> > delegation
> > fixes from the others and commit as two separate patches
> > (especially
> > because Ana noted some potential miscompiles caused by the other
> > improvements).
> > 
> > 
> > 
> > I think she mentioned the miscompiles due to us returning
> > partialalias. But in any case, i 'm happy to, but just to note
they
> > are all required to get the LICM issue fixed :)
> > 
> > 
> > Okay, please do that and commit them.
> > 
> > 
> > 
> > 
> > 
> > 
> > Regarding this:
> > 
> > @@ -768,7 +774,10 @@ static Optional<StratifiedAttr>
> > valueToAttrIndex(Value *Val) {
> > return AttrGlobalIndex;
> > 
> > if (auto *Arg = dyn_cast<Argument>(Val))
> > - if (!Arg->hasNoAliasAttr())
> > + // Only pointer arguments should have the argument attribute,
> > + // because things can't escape through scalars without us seeing
> > a
> > + // cast, and thus, interaction with them doesn't matter.
> > + if (!Arg->hasNoAliasAttr() &&
Arg->getType()->isPointerTy())
> > return argNumberToAttrIndex(Arg-> getArgNo());
> > return NoneType();
> > }
> > 
> > when we do see the inttoptr case, we add an edge from the source to
> > the destination.
> > 
> > 
> > Correct.
> > 
> > 
> > If we've not noted potential aliasing of the non-pointer-typed
> > argument, then does this end up looking like a unique global?
> > 
> > 
> > 
> > No. It will end up looking like something that points to nothing.
> > Even without this change, it will end up looking like something
> > that
> > points to nothing, it will just have an attribute that says
> > "argument". :)
> > 
> > 
> > Okay, fair enough.
> > 
> > 
> > 
> > 
> > 
> > You can come up with cases where even with this attribute set, it
> > will get the wrong answer. It just happens to have code that,
> > through luck, gets the right answer in a lot of cases:
> > 
> > (That is this code:
> > 
> > 
> > if (AttrsA.any() && AttrsB.any())
> > return AliasAnalysis::MayAlias;
> > )
> > 
> > 
> > So there is a bug here, but it's not caused by this code.
> > 
> > 
> > The bug here is that we can't ever know what happens as the result
> > of
> > inttoptr. We never do math, and the tracking we do is never going
> > to
> > be sufficient to determine the range of possible pointers for an
> > inttoptr in all cases (in theory, it could point to anything
> > anywhere in the program. If we knew the sizes of *all* objects, and
> > any binary operator performed on it was evaluable, we could do a
> > little better. If we knew the value came from a ptrtoint, we could
> > do better, etc).
> > Same with ptrtoint.
> > 
> > 
> > The result of both of these instructions should start to be "we
> > have
> > no idea what the pointer that comes from inttoptr or goes to
> > ptrtoint points to", and we should return mayalias for anything
> > that
> > interacts with them.
> > We don't do that right now.
> > We are just hiding it mildly well.
> > 
> > 
> > Should we be added an edge from the inttoptr to all other pointer
> > values? Is there a better way?
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > Speaking of which, the code has checks for global variables in
> > several places. Do these need to be for globals that are not
> > aliases
> > and don't have weak linkage?
> > 
> > 
> > 
> > It's more a question of whether they are in SSA form than if they
> > are
> > globals.
> > 
> > 
> > It's effectively using Globals/Arguments as a way to say
"don't
> > know"
> > in some cases, where it should really just say "don't
know".
> > 
> > 
> > There is a bunch of code i now have marked for cleanup and bugfixes
> > around these issues (constant vs global handling, handling of
> > non-pointer values, etc).
> > 
> > 
> > Okay, thanks!
> > 
> > 
> > 
> > 
> > 
> > As mentioned, the above is necessary to fix the LICM issue (and is
> > correct, even if somewhere else is wrong. For reference, GCC does
> > the identical thing to what i'm saying :P), but i'm happy to
move
> > it
> > to a separate fix (that includes fixes for the other
> > argument/unknown related issues) if you like.
> > 
> > 
> > 
> > 
> > Generically speaking, I'd prefer the fixes to be broken up as much
> > as
> > practical. Please go ahead and commit them.
> > 
> > -Hal
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > Thanks again,
> > Hal
> > 
> > > 
> > > 
> > > 
> > > 
> > > On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel < hfinkel at
anl.gov >
> > > wrote:
> > > 
> > > 
> > > ----- Original Message -----
> > > > From: "Daniel Berlin" < dberlin at dberlin.org
>
> > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com
>, "George Burgess
> > > > IV"
> > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > nlewycky at google.com >
> > > > Sent: Tuesday, January 20, 2015 1:48:44 PM
> > > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > > collecting a57 numbers
> > > > 
> > > > So, I can make all these testcases work, but it's a
little
> > > > tricky
> > > > (it
> > > > involves tracking some things, like GEP byte range, and then
> > > > checking bases and using getObjectSize, much like BasicAA
> > > > does).
> > > > 
> > > > 
> > > > Because i really don't want to put that much "not
well tested"
> > > > code
> > > > in a bugfix, and honestly, i'm not sure we will catch
any cases
> > > > here
> > > > that BasicAA does not, i've attached a change to XFAIL
these
> > > > testcases, and updated the code to return MayAlias.
> > > 
> > > Okay. I think you might as well just update the test cases to
> > > want
> > > MayAlias, and put a FIXME comment explaining that they could be
> > > PartialAlias. As far as I know, there is no code in LLVM that
> > > really
> > > handles a PartialAlias differently than a MayAlias or MustAlias,
> > > and
> > > so while there may be some benefit here, I'm not sure it will
be
> > > worth the effort.
> > > 
> > > > 
> > > > I will build and test a patch to get these back to
> > > > PartialAlias,
> > > > but
> > > > this patch will at least get us to not be "giving wrong
> > > > answers".
> > > > I
> > > > will also see if we catch anything with it that BasicAA does
> > > > not,
> > > > because if we don't, it doesn't seem worth it to me.
> > > 
> > > My guess is that BasicAA will get almost all of the interesting
> > > PartialAlias cases, and as I said, we essentially ignore them
> > > anyway.
> > > 
> > > As a side note, there is this one place in lib/Analysis/
> > > MemoryDependenceAnalysis.cpp that could use some attention:
> > > 
> > > #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting
> > > loads
> > > // in terms of clobbering loads, but since it does this by
> > > looking
> > > // at the clobbering load directly, it doesn't know about any
> > > // phi translation that may have happened along the way.
> > > 
> > > // If we have a partial alias, then return this as a clobber for
> > > the
> > > // client to handle.
> > > if (R == AliasAnalysis::PartialAlias)
> > > return MemDepResult::getClobber(Inst) ;
> > > #endif
> > > 
> > > > 
> > > > 
> > > > Conservative new patch attached.
> > > > 
> > > > 
> > > > 
> > > > (Note that i still updated the testcases, because we will
> > > > *never*
> > > > be
> > > > able to legally return PartialAlias as they were written)
> > > > 
> > > 
> > > Yes, sounds good.
> > > 
> > > -Hal
> > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin <
> > > > dberlin at dberlin.org
> > > > > wrote:
> > > > 
> > > > 
> > > > 
> > > > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel < hfinkel at
anl.gov >
> > > > wrote:
> > > > 
> > > > 
> > > > ----- Original Message -----
> > > > > From: "Daniel Berlin" < dberlin at
dberlin.org >
> > > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > > Cc: "Jiangning Liu" < Jiangning.Liu at
arm.com >, "George
> > > > > Burgess
> > > > > IV"
> > > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > > nlewycky at google.com >
> > > > > Sent: Saturday, January 17, 2015 1:08:10 PM
> > > > > Subject: Re: [LLVMdev] question about enabling cfl-aa
and
> > > > > collecting a57 numbers
> > > > > 
> > > > > 
> > > > > 
> > > > > 
> > > > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel <
> > > > > hfinkel at anl.gov
> > > > > > 
> > > > > wrote:
> > > > > 
> > > > > 
> > > > > Hi Danny,
> > > > > 
> > > > > // Add TypeBasedAliasAnalysis before BasicAliasAnalysis
so
> > > > > that
> > > > > // BasicAliasAnalysis wins if they disagree. This is
intended
> > > > > to
> > > > > help
> > > > > // support "obvious" type-punning idioms.
> > > > > - if (UseCFLAA)
> > > > > - addPass( createCFLAliasAnalysisPass());
> > > > > addPass( createTypeBasedAliasAnalysisPa ss());
> > > > > addPass( createScopedNoAliasAAPass());
> > > > > + if (UseCFLAA)
> > > > > + addPass( createCFLAliasAnalysisPass());
> > > > > addPass( createBasicAliasAnalysisPass() );
> > > > > 
> > > > > Do we really want to change the order here? I had
originally
> > > > > placed
> > > > > it after the metadata-based passes thinking that the
> > > > > compile-time
> > > > > would be better (guessing that the metadata queries
would be
> > > > > faster
> > > > > than the CFL queries, so if the metadata could quickly
return
> > > > > a
> > > > > NoAlias, then we'd cut out unecessary CFL queries).
Perhaps
> > > > > this
> > > > > is
> > > > > an irrelevant effect, but we should have some
documented
> > > > > rationale.
> > > > > 
> > > > > 
> > > > > 
> > > > > Yeah, this was a mistake (Chandler had suggested it was
right
> > > > > earlier, but we were both wrong :P)
> > > > > 
> > > > > 
> > > > > 
> > > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > > -define i8 @test0(i8* %base, i1 %x) {
> > > > > +define i8 @test0(i1 %x) {
> > > > > entry:
> > > > > + %base = alloca i8, align 4
> > > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > > br i1 %x, label %red, label %green
> > > > > red:
> > > > > @@ -25,8 +26,9 @@ green:
> > > > > }
> > > > > 
> > > > > why should this return PartialAlias? %ohi does
partially
> > > > > overlap,
> > > > > so
> > > > > this correct, but what happens when the overlap is
partial or
> > > > > control dependent?
> > > > > So, after talking with some people offline, they
convinced me
> > > > > in
> > > > > SSA
> > > > > form, the name would change in these situations, and
the only
> > > > > situations you can get into trouble is with things
"based on
> > > > > pointer
> > > > > arguments" (because you have no idea what their
initial state
> > > > > is),
> > > > > or "globals" (because they are not in SSA
form)
> > > > > I could not come up with a case otherwise
> > > > 
> > > > Okay; that part of the code could really use some more
> > > > commentary.
> > > > I'd really appreciate it if you should put these
thoughts in
> > > > written
> > > > form that could be added as comments.
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > Will do
> > > > 
> > > > 
> > > > 
> > > > > But i'm welcome to hear if you think this is wrong.
> > > > > 
> > > > > FWIW: I bootstrapped/tested the compiler with an assert
that
> > > > > triggered if CFL-AA was going to return PartialAlias
and
> > > > > BasicAA
> > > > > would have returned NoAlias, and it did not trigger
with this
> > > > > change.
> > > > > 
> > > > > 
> > > > > (It would have triggered before this set of changes)
> > > > > 
> > > > > Not proof of course, but it at least tells me it's
not
> > > > > "obviously
> > > > > wrong" :)
> > > > > 
> > > > > 
> > > > 
> > > > That's good :) -- but, not exactly what I was concerned
about.
> > > > Our
> > > > general convention has been that PartialAlias is a
"strong"
> > > > result,
> > > > like MustAlias, but implies that AA has proved that only a
> > > > partial
> > > > overlap will occur.
> > > > 
> > > > So, in this test case we get the right result:
> > > > 
> > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > define i8 @test0(i1 %x) {
> > > > entry:
> > > > %base = alloca i8, align 4
> > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > br i1 %x, label %red, label %green
> > > > red:
> > > > br label %green
> > > > green:
> > > > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry ]
> > > > store i8 0, i8* %phi
> > > > 
> > > > %bigbase0 = bitcast i8* %base to i16*
> > > > store i16 -1, i16* %bigbase0
> > > > 
> > > > %loaded = load i8* %phi
> > > > ret i8 %loaded
> > > > }
> > > > 
> > > > because %phi will have a partial overlap with %bigbase0, the
> > > > only
> > > > uncertainty is whether the overlap is with the low byte or
the
> > > > high
> > > > byte. But if I modify the test to be this:
> > > > 
> > > > define i8 @test0x(i1 %x) {
> > > > entry:
> > > > %base = alloca i8, align 4
> > > > %baseplustwo = getelementptr i8* %base, i64 2
> > > > br i1 %x, label %red, label %green
> > > > red:
> > > > br label %green
> > > > green:
> > > > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry ]
> > > > store i8 0, i8* %phi
> > > > 
> > > > %bigbase0 = bitcast i8* %base to i16*
> > > > store i16 -1, i16* %bigbase0
> > > > 
> > > > %loaded = load i8* %phi
> > > > ret i8 %loaded
> > > > }
> > > > 
> > > > I still get this result:
> > > > PartialAlias: i16* %bigbase0, i8* %phi
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > 
> > > > but now %phi might not overlap %bigbase0 at all (although,
when
> > > > it
> > > > does, there is a partial overlap), so we should just return
> > > > MayAlias
> > > > (perhaps without delegation because this is a definitive
> > > > result?).
> > > > 
> > > > 
> > > > 
> > > > 
> > > > Yeah, i have to do some size checking, let me see if we have
> > > > the
> > > > info
> > > > and i'll update the patch.
> > > > 
> > > > 
> > > > 
> > > > 
> > > > Otherwise, my view is that we should always delegate
MayAlias,
> > > > because we have no idea what order the passes are in or what
> > > > pass
> > > > someone has inserted where :)
> > > > 
> > > > 
> > > > (WIW: I believe the same about everything except MustAlias
and
> > > > NoAlias, but currently we don't delegate PartialAlias.
> > > > We claim PartialAlias is a definitive result, but it really
> > > > isn't.
> > > > Right now we have TBAA that will give NoAlias results on
things
> > > > other
> > > > passes claim are PartialAlias, and that result is correct.
> > > > That's
> > > > just in our default, we have no idea what other people do.
Even
> > > > if
> > > > you ignore TBAA, plenty of other compilers have
> > > > noalias/mustalias
> > > > metadata that would have the same effect.
> > > 
> > > --
> > > Hal Finkel
> > > Assistant Computational Scientist
> > > Leadership Computing Facility
> > > Argonne National Laboratory
> > > 
> > 
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> > 
> > 
> > --
> > 
> > 
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> > 
> > 
> > 
> > 
> 
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> Fixing that still gives a wrong result, i haven't started to track down
what *else* is going on here.

Running with the attached diff + a modified buildGraphFrom to handle the
constexpr GEPs, we seem to flag everything in test2.ll (conservatively)
correctly.

Is `store` the only place we can expect to see these constexpr analogs, or
is just about anywhere fair game?

George

On Fri, Jan 23, 2015 at 8:18 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> ----- Original Message -----
> > From: "Daniel Berlin" <dberlin at dberlin.org>
> > To: "Hal Finkel" <hfinkel at anl.gov>
> > Cc: "Jiangning Liu" <Jiangning.Liu at arm.com>,
"LLVM Developers Mailing
> List" <llvmdev at cs.uiuc.edu>, "Ana Pazos"
> > <apazos at codeaurora.org>, "George Burgess IV" <
> george.burgess.iv at gmail.com>
> > Sent: Friday, January 23, 2015 7:14:24 PM
> > Subject: Re: [LLVMdev] question about enabling cfl-aa and collecting
a57
> numbers
> >
> >
> > No, i mean the actual store instruction looks like "store i16
> > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > 12), align 2, !tbaa !1"
> >
> >
> > Not that the pointer operand comes from a GEP, but it is a
> > constantexpr, whose opcode is GEP.
>
> Ah, yep. We have ConstantExpr analogs for just about everything. ;)
>
> >
> >
> > It sucks that there is such a complex thing to be handled as a store
> > operand directly , but such is life ...
> >
> >
> > CFL-AA *should* treat this like an assignment to GEP operand, not
> > like a normal store, which is *x = y. This is really *(&GEP
operand)
> > = y.
> >
> >
> > But currently, it does nothing right here :)
> >
> >
> > I haven't tracked down entirely what is happening, but for sure,
> > visitStoreInst doesn't do the right thing in this case.
> > Fixing that still gives a wrong result, i haven't started to track
> > down what *else* is going on here.
> >
> >
> > I suspect either more ConstantExpr related bugs, or the global
> > attribute is not being fully propagated around or something.
> >
>
> Fair enough.
>
>  -Hal
>
> >
> >
> >
> >
> >
> > On Fri Jan 23 2015 at 4:45:34 PM Hal Finkel < hfinkel at anl.gov
>
> > wrote:
> >
> >
> > ----- Original Message -----
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > > To: "Ana Pazos" < apazos at codeaurora.org >,
"George Burgess IV" <
> > > george.burgess.iv at gmail.com >
> > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >, "Hal
Finkel"
> > > < hfinkel at anl.gov >
> > > Sent: Friday, January 23, 2015 5:09:06 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting a57 numbers
> > >
> > >
> > > Without the patch is also returns the wrong answer for all of
> > > these,
> > > it just doesn't cause LICM to promote because it returns
> > > PartialAlias (which is still wrong).
> > >
> > >
> > > We return may-alias instead, and now suddenly it's happy to
promote
> > > them.
> > >
> > >
> > > The broken noalias results exist both before and after my patch:
> > >
> > >
> > > ===== Alias Analysis Evaluator Report ====> > > 521
Total Alias Queries Performed
> > > 176 no alias responses (33.7%)
> > > - 334 may alias responses (64.1%)
> > > - 10 partial alias responses (1.9%)
> > > + 344 may alias responses (66.0%)
> > > + 0 partial alias responses (0.0%)
> > > 1 must alias responses (0.1%)
> > >
> > >
> > >
> > >
> > > I suspect this is all caused by a different set of bugs:
> > >
> > >
> > > 1. visitStoreInst does not appear to handle the case of value
being
> > > a
> > > GEP properly (Personally, i had no idea this was allowed ...)
> > >
> >
> > You mean that the value being stored is a pointer value coming from a
> > GEP? Why would that be special (compared to any other way of
> > generating a pointer value, inttoptr for example)?
> >
> > >
> > > It should somehow call into the visitGEP code, but it
doesn't.
> > >
> > >
> > > Thus, it never assigns anything into the value of the global.
> > > 2. Something is either busted in querying or in attributes for
> > > stores
> > > that have geps directly as their pointer value.
> > >
> > >
> > >
> > >
> > >
> > > I will work up a separate patch for this issue unless someone
> > > thinks
> > > i should shoehorn it into the existing patch.
> > >
> > >
> >
> > A separate patch is good.
> >
> > Thanks again,
> > Hal
> >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > On Fri Jan 23 2015 at 12:52:02 PM Ana Pazos < apazos at
codeaurora.org
> > > >
> > > wrote:
> > >
> > >
> > >
> > >
> > >
> > >
> > > Hi Daniel,
> > >
> > >
> > >
> > > There are correctness issues with the latest patch (from Wed
> > > 1/21/2015 11:10 AM with “Updated testcases to have MayAlias/note
> > > issues as FIXME”).
> > >
> > >
> > >
> > > I looked at one of the failures and it has to do with
> > > disambiguating
> > > array indexes.
> > >
> > >
> > >
> > > With CFL AA enabled, LICM promotion is sinking stores outside of
> > > the
> > > loop incorrectly. If I disable LICM promotion, the tests pass.
> > >
> > >
> > >
> > > Find attached a reduced test case.
> > >
> > >
> > >
> > > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast
-mllvm
> > > -use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 1)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 2)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 3)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 4)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 5)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 6)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 7)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 8)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 9)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 10)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 11)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 12)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 13)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 14)
> > >
> > > LICM: Promoting value stored to in loop: i16* getelementptr
> > > inbounds
> > > ([16 x i16]* @pA, i64 0, i64 15)
> > >
> > > LICM sinking instruction: %conv32 = trunc i32 %add31 to i16
> > >
> > > LICM sinking instruction: %add31 = sub nsw i32 %conv18, %conv17
> > >
> > > LICM sinking instruction: %conv22 = trunc i32 %sub to i16
> > >
> > > LICM sinking instruction: %sub = sub nsw i32 %conv17, %conv18
> > >
> > > LICM sinking instruction: %conv19 = trunc i32 %add to i16
> > >
> > >
> > >
> > > clang -c --target=aarch64-linux-gnu -mcpu=cortex-a57 -Ofast
-mllvm
> > > –use-cfl-aa -S test2.c -o test2out -mllvm -debug-only=licm -mllvm
> > > -disable-licm-promotion
> > >
> > > ok
> > >
> > >
> > >
> > > If you look at the .ll file, you notice that pointer p alias with
> > > pA:
> > >
> > >
> > >
> > > %p.0 = phi i16* [ getelementptr inbounds ([16 x i16]* @pA, i64 0,
> > > i64
> > > 0), %for.body ], [ %incdec.ptr49, %for.body48 ]
> > >
> > > …
> > >
> > > for.body48: ; preds = %for.cond45
> > >
> > > %incdec.ptr49 = getelementptr inbounds i16* %p.0, i64 1
> > >
> > >
> > >
> > > CFL AA disambiguates p, pA[0], but not the other indexes (coming
> > > from
> > > incdec.ptr49 updates):
> > >
> > > MayAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 0), align 2, !tbaa !1
> > >
> > > NoAlias : %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 1), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 2), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 3), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 4), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 5), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 6), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 7), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 8), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 9), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 10), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 11), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 12), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 13), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 14), align 2, !tbaa !1
> > >
> > > NoAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 15), align 2, !tbaa !1
> > >
> > >
> > >
> > > Basic AA disambiguates them all:
> > >
> > > opt -basicaa -aa-eval -evaluate-aa-metadata -print-no-aliases
> > > -print-may-aliases -disable-output test2.ll
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 0), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 1), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 2), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 3), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 4), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 5), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 6), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 7), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 8), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 9), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 10), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 11), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv22, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 12), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv27, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 13), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv19, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 14), align 2, !tbaa !1
> > >
> > > MayAlias: %3 = load i16* %p.0, align 2, !tbaa !1 <-> store
i16
> > > %conv32, i16* getelementptr inbounds ([16 x i16]* @pA, i64 0, i64
> > > 15), align 2, !tbaa !1
> > >
> > >
> > >
> > > Thanks,
> > >
> > > Ana.
> > >
> > >
> > >
> > >
> > >
> > > From: llvmdev-bounces at cs.uiuc.edu [mailto: llvmdev-bounces at
cs.
> > > uiuc.edu ] On Behalf Of George Burgess IV
> > > Sent: Thursday, January 22, 2015 5:47 PM
> > > To: Daniel Berlin
> > > Cc: Jiangning Liu; LLVM Developers Mailing List
> > >
> > >
> > >
> > >
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting
> > > a57 numbers
> > >
> > >
> > >
> > >
> > >
> > >
> > > Works for me
> > >
> > >
> > >
> > >
> > >
> > > On Thu, Jan 22, 2015 at 8:27 PM, Daniel Berlin <
> > > dberlin at dberlin.org
> > > > wrote:
> > >
> > >
> > >
> > >
> > > We should use graph edges, so we can do something better at set
> > > build
> > > time :)
> > >
> > >
> > >
> > >
> > >
> > >
> > > On Thu Jan 22 2015 at 5:20:46 PM George Burgess IV <
> > > george.burgess.iv at gmail.com > wrote:
> > >
> > >
> > >
> > >
> > > > Should we be added an edge from the inttoptr to all other
pointer
> > > > values? Is there a better way?
> > >
> > >
> > >
> > >
> > >
> > >
> > > We can add a special "Unknown" StratifiedAttr and query
it before
> > > anything else, i.e:
> > >
> > >
> > >
> > >
> > >
> > > // in CFLAliasAnalysis::query, as the first potential return
> > >
> > >
> > > if (AttrsA[AttrUnknown] || AttrsB[AttrUnknown])
> > >
> > >
> > > return MayAlias;
> > >
> > >
> > >
> > >
> > >
> > > The only *potential* issue with this approach would be that in
the
> > > following code segment:
> > >
> > >
> > >
> > >
> > >
> > > void fn() {
> > >
> > >
> > > int *foo = (int*)rand();
> > >
> > >
> > > int *bar = new int;
> > >
> > >
> > > int **baz = rand() ? &foo : &bar;
> > >
> > >
> > > int value = **baz;
> > >
> > >
> > > }
> > >
> > >
> > >
> > >
> > >
> > > The stratified sets would look like:
> > >
> > >
> > > {value} is below {foo, bar} is below {baz}.
> > >
> > >
> > >
> > >
> > >
> > > Potential issue: The sets {foo, bar} and {value} would be marked
> > > with
> > > the "Unknown" attribute, while {baz} would have no
attributes. I
> > > can't immediately think of a case where {baz} lacking
"Unknown"
> > > would be harmful, but if such a case exists, then we may need a
> > > different approach.
> > >
> > >
> > >
> > >
> > >
> > >
> > > George
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > On Thu, Jan 22, 2015 at 8:03 PM, Hal Finkel < hfinkel at
anl.gov >
> > > wrote:
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > From: "Daniel Berlin" < dberlin at dberlin.org >
> > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com >,
"George Burgess IV"
> > > <
> > > george.burgess.iv at gmail.com >, "LLVM Developers
> > > Mailing List" < llvmdev at cs.uiuc.edu >, "Nick
Lewycky" <
> > > nlewycky at google.com >
> > > Sent: Wednesday, January 21, 2015 3:48:25 PM
> > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > collecting
> > > a57 numbers
> > >
> > > On Wed Jan 21 2015 at 12:30:50 PM Hal Finkel < hfinkel at
anl.gov >
> > > wrote:
> > >
> > > ----- Original Message -----
> > > > From: "Daniel Berlin" < dberlin at dberlin.org
>
> > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > Cc: "Jiangning Liu" < Jiangning.Liu at arm.com
>, "George Burgess
> > > > IV"
> > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > nlewycky at google.com >
> > > > Sent: Wednesday, January 21, 2015 1:10:07 PM
> > > > Subject: Re: [LLVMdev] question about enabling cfl-aa and
> > > > collecting a57 numbers
> > > >
> > > > Updated testcases to have MayAlias/note issues as FIXME.
> > > >
> > >
> > > Okay, thanks! This LGTM, but we should probably split the
> > > delegation
> > > fixes from the others and commit as two separate patches
> > > (especially
> > > because Ana noted some potential miscompiles caused by the other
> > > improvements).
> > >
> > >
> > >
> > > I think she mentioned the miscompiles due to us returning
> > > partialalias. But in any case, i 'm happy to, but just to
note they
> > > are all required to get the LICM issue fixed :)
> > >
> > >
> > > Okay, please do that and commit them.
> > >
> > >
> > >
> > >
> > >
> > >
> > > Regarding this:
> > >
> > > @@ -768,7 +774,10 @@ static Optional<StratifiedAttr>
> > > valueToAttrIndex(Value *Val) {
> > > return AttrGlobalIndex;
> > >
> > > if (auto *Arg = dyn_cast<Argument>(Val))
> > > - if (!Arg->hasNoAliasAttr())
> > > + // Only pointer arguments should have the argument attribute,
> > > + // because things can't escape through scalars without us
seeing
> > > a
> > > + // cast, and thus, interaction with them doesn't matter.
> > > + if (!Arg->hasNoAliasAttr() &&
Arg->getType()->isPointerTy())
> > > return argNumberToAttrIndex(Arg-> getArgNo());
> > > return NoneType();
> > > }
> > >
> > > when we do see the inttoptr case, we add an edge from the source
to
> > > the destination.
> > >
> > >
> > > Correct.
> > >
> > >
> > > If we've not noted potential aliasing of the
non-pointer-typed
> > > argument, then does this end up looking like a unique global?
> > >
> > >
> > >
> > > No. It will end up looking like something that points to nothing.
> > > Even without this change, it will end up looking like something
> > > that
> > > points to nothing, it will just have an attribute that says
> > > "argument". :)
> > >
> > >
> > > Okay, fair enough.
> > >
> > >
> > >
> > >
> > >
> > > You can come up with cases where even with this attribute set, it
> > > will get the wrong answer. It just happens to have code that,
> > > through luck, gets the right answer in a lot of cases:
> > >
> > > (That is this code:
> > >
> > >
> > > if (AttrsA.any() && AttrsB.any())
> > > return AliasAnalysis::MayAlias;
> > > )
> > >
> > >
> > > So there is a bug here, but it's not caused by this code.
> > >
> > >
> > > The bug here is that we can't ever know what happens as the
result
> > > of
> > > inttoptr. We never do math, and the tracking we do is never going
> > > to
> > > be sufficient to determine the range of possible pointers for an
> > > inttoptr in all cases (in theory, it could point to anything
> > > anywhere in the program. If we knew the sizes of *all* objects,
and
> > > any binary operator performed on it was evaluable, we could do a
> > > little better. If we knew the value came from a ptrtoint, we
could
> > > do better, etc).
> > > Same with ptrtoint.
> > >
> > >
> > > The result of both of these instructions should start to be
"we
> > > have
> > > no idea what the pointer that comes from inttoptr or goes to
> > > ptrtoint points to", and we should return mayalias for
anything
> > > that
> > > interacts with them.
> > > We don't do that right now.
> > > We are just hiding it mildly well.
> > >
> > >
> > > Should we be added an edge from the inttoptr to all other pointer
> > > values? Is there a better way?
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > Speaking of which, the code has checks for global variables in
> > > several places. Do these need to be for globals that are not
> > > aliases
> > > and don't have weak linkage?
> > >
> > >
> > >
> > > It's more a question of whether they are in SSA form than if
they
> > > are
> > > globals.
> > >
> > >
> > > It's effectively using Globals/Arguments as a way to say
"don't
> > > know"
> > > in some cases, where it should really just say "don't
know".
> > >
> > >
> > > There is a bunch of code i now have marked for cleanup and
bugfixes
> > > around these issues (constant vs global handling, handling of
> > > non-pointer values, etc).
> > >
> > >
> > > Okay, thanks!
> > >
> > >
> > >
> > >
> > >
> > > As mentioned, the above is necessary to fix the LICM issue (and
is
> > > correct, even if somewhere else is wrong. For reference, GCC does
> > > the identical thing to what i'm saying :P), but i'm happy
to move
> > > it
> > > to a separate fix (that includes fixes for the other
> > > argument/unknown related issues) if you like.
> > >
> > >
> > >
> > >
> > > Generically speaking, I'd prefer the fixes to be broken up as
much
> > > as
> > > practical. Please go ahead and commit them.
> > >
> > > -Hal
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > Thanks again,
> > > Hal
> > >
> > > >
> > > >
> > > >
> > > >
> > > > On Tue Jan 20 2015 at 3:54:10 PM Hal Finkel < hfinkel at
anl.gov >
> > > > wrote:
> > > >
> > > >
> > > > ----- Original Message -----
> > > > > From: "Daniel Berlin" < dberlin at
dberlin.org >
> > > > > To: "Hal Finkel" < hfinkel at anl.gov >
> > > > > Cc: "Jiangning Liu" < Jiangning.Liu at
arm.com >, "George Burgess
> > > > > IV"
> > > > > < george.burgess.iv at gmail.com >, "LLVM
Developers
> > > > > Mailing List" < llvmdev at cs.uiuc.edu >,
"Nick Lewycky" <
> > > > > nlewycky at google.com >
> > > > > Sent: Tuesday, January 20, 2015 1:48:44 PM
> > > > > Subject: Re: [LLVMdev] question about enabling cfl-aa
and
> > > > > collecting a57 numbers
> > > > >
> > > > > So, I can make all these testcases work, but it's a
little
> > > > > tricky
> > > > > (it
> > > > > involves tracking some things, like GEP byte range, and
then
> > > > > checking bases and using getObjectSize, much like
BasicAA
> > > > > does).
> > > > >
> > > > >
> > > > > Because i really don't want to put that much
"not well tested"
> > > > > code
> > > > > in a bugfix, and honestly, i'm not sure we will
catch any cases
> > > > > here
> > > > > that BasicAA does not, i've attached a change to
XFAIL these
> > > > > testcases, and updated the code to return MayAlias.
> > > >
> > > > Okay. I think you might as well just update the test cases
to
> > > > want
> > > > MayAlias, and put a FIXME comment explaining that they could
be
> > > > PartialAlias. As far as I know, there is no code in LLVM
that
> > > > really
> > > > handles a PartialAlias differently than a MayAlias or
MustAlias,
> > > > and
> > > > so while there may be some benefit here, I'm not sure it
will be
> > > > worth the effort.
> > > >
> > > > >
> > > > > I will build and test a patch to get these back to
> > > > > PartialAlias,
> > > > > but
> > > > > this patch will at least get us to not be "giving
wrong
> > > > > answers".
> > > > > I
> > > > > will also see if we catch anything with it that BasicAA
does
> > > > > not,
> > > > > because if we don't, it doesn't seem worth it
to me.
> > > >
> > > > My guess is that BasicAA will get almost all of the
interesting
> > > > PartialAlias cases, and as I said, we essentially ignore
them
> > > > anyway.
> > > >
> > > > As a side note, there is this one place in lib/Analysis/
> > > > MemoryDependenceAnalysis.cpp that could use some attention:
> > > >
> > > > #if 0 // FIXME: Temporarily disabled. GVN is cleverly
rewriting
> > > > loads
> > > > // in terms of clobbering loads, but since it does this by
> > > > looking
> > > > // at the clobbering load directly, it doesn't know
about any
> > > > // phi translation that may have happened along the way.
> > > >
> > > > // If we have a partial alias, then return this as a clobber
for
> > > > the
> > > > // client to handle.
> > > > if (R == AliasAnalysis::PartialAlias)
> > > > return MemDepResult::getClobber(Inst) ;
> > > > #endif
> > > >
> > > > >
> > > > >
> > > > > Conservative new patch attached.
> > > > >
> > > > >
> > > > >
> > > > > (Note that i still updated the testcases, because we
will
> > > > > *never*
> > > > > be
> > > > > able to legally return PartialAlias as they were
written)
> > > > >
> > > >
> > > > Yes, sounds good.
> > > >
> > > > -Hal
> > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > On Sun Jan 18 2015 at 2:12:47 PM Daniel Berlin <
> > > > > dberlin at dberlin.org
> > > > > > wrote:
> > > > >
> > > > >
> > > > >
> > > > > On Sat Jan 17 2015 at 3:15:27 PM Hal Finkel <
hfinkel at anl.gov >
> > > > > wrote:
> > > > >
> > > > >
> > > > > ----- Original Message -----
> > > > > > From: "Daniel Berlin" < dberlin at
dberlin.org >
> > > > > > To: "Hal Finkel" < hfinkel at anl.gov
>
> > > > > > Cc: "Jiangning Liu" < Jiangning.Liu
at arm.com >, "George
> > > > > > Burgess
> > > > > > IV"
> > > > > > < george.burgess.iv at gmail.com >,
"LLVM Developers
> > > > > > Mailing List" < llvmdev at cs.uiuc.edu
>, "Nick Lewycky" <
> > > > > > nlewycky at google.com >
> > > > > > Sent: Saturday, January 17, 2015 1:08:10 PM
> > > > > > Subject: Re: [LLVMdev] question about enabling
cfl-aa and
> > > > > > collecting a57 numbers
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > > > > > On Sat Jan 17 2015 at 12:03:33 AM Hal Finkel <
> > > > > > hfinkel at anl.gov
> > > > > > >
> > > > > > wrote:
> > > > > >
> > > > > >
> > > > > > Hi Danny,
> > > > > >
> > > > > > // Add TypeBasedAliasAnalysis before
BasicAliasAnalysis so
> > > > > > that
> > > > > > // BasicAliasAnalysis wins if they disagree. This
is intended
> > > > > > to
> > > > > > help
> > > > > > // support "obvious" type-punning
idioms.
> > > > > > - if (UseCFLAA)
> > > > > > - addPass( createCFLAliasAnalysisPass());
> > > > > > addPass( createTypeBasedAliasAnalysisPa ss());
> > > > > > addPass( createScopedNoAliasAAPass());
> > > > > > + if (UseCFLAA)
> > > > > > + addPass( createCFLAliasAnalysisPass());
> > > > > > addPass( createBasicAliasAnalysisPass() );
> > > > > >
> > > > > > Do we really want to change the order here? I had
originally
> > > > > > placed
> > > > > > it after the metadata-based passes thinking that
the
> > > > > > compile-time
> > > > > > would be better (guessing that the metadata
queries would be
> > > > > > faster
> > > > > > than the CFL queries, so if the metadata could
quickly return
> > > > > > a
> > > > > > NoAlias, then we'd cut out unecessary CFL
queries). Perhaps
> > > > > > this
> > > > > > is
> > > > > > an irrelevant effect, but we should have some
documented
> > > > > > rationale.
> > > > > >
> > > > > >
> > > > > >
> > > > > > Yeah, this was a mistake (Chandler had suggested
it was right
> > > > > > earlier, but we were both wrong :P)
> > > > > >
> > > > > >
> > > > > >
> > > > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > > > -define i8 @test0(i8* %base, i1 %x) {
> > > > > > +define i8 @test0(i1 %x) {
> > > > > > entry:
> > > > > > + %base = alloca i8, align 4
> > > > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > > > br i1 %x, label %red, label %green
> > > > > > red:
> > > > > > @@ -25,8 +26,9 @@ green:
> > > > > > }
> > > > > >
> > > > > > why should this return PartialAlias? %ohi does
partially
> > > > > > overlap,
> > > > > > so
> > > > > > this correct, but what happens when the overlap is
partial or
> > > > > > control dependent?
> > > > > > So, after talking with some people offline, they
convinced me
> > > > > > in
> > > > > > SSA
> > > > > > form, the name would change in these situations,
and the only
> > > > > > situations you can get into trouble is with things
"based on
> > > > > > pointer
> > > > > > arguments" (because you have no idea what
their initial state
> > > > > > is),
> > > > > > or "globals" (because they are not in
SSA form)
> > > > > > I could not come up with a case otherwise
> > > > >
> > > > > Okay; that part of the code could really use some more
> > > > > commentary.
> > > > > I'd really appreciate it if you should put these
thoughts in
> > > > > written
> > > > > form that could be added as comments.
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > Will do
> > > > >
> > > > >
> > > > >
> > > > > > But i'm welcome to hear if you think this is
wrong.
> > > > > >
> > > > > > FWIW: I bootstrapped/tested the compiler with an
assert that
> > > > > > triggered if CFL-AA was going to return
PartialAlias and
> > > > > > BasicAA
> > > > > > would have returned NoAlias, and it did not
trigger with this
> > > > > > change.
> > > > > >
> > > > > >
> > > > > > (It would have triggered before this set of
changes)
> > > > > >
> > > > > > Not proof of course, but it at least tells me
it's not
> > > > > > "obviously
> > > > > > wrong" :)
> > > > > >
> > > > > >
> > > > >
> > > > > That's good :) -- but, not exactly what I was
concerned about.
> > > > > Our
> > > > > general convention has been that PartialAlias is a
"strong"
> > > > > result,
> > > > > like MustAlias, but implies that AA has proved that
only a
> > > > > partial
> > > > > overlap will occur.
> > > > >
> > > > > So, in this test case we get the right result:
> > > > >
> > > > > ; CHECK: PartialAlias: i16* %bigbase0, i8* %phi
> > > > > define i8 @test0(i1 %x) {
> > > > > entry:
> > > > > %base = alloca i8, align 4
> > > > > %baseplusone = getelementptr i8* %base, i64 1
> > > > > br i1 %x, label %red, label %green
> > > > > red:
> > > > > br label %green
> > > > > green:
> > > > > %phi = phi i8* [ %baseplusone, %red ], [ %base, %entry
]
> > > > > store i8 0, i8* %phi
> > > > >
> > > > > %bigbase0 = bitcast i8* %base to i16*
> > > > > store i16 -1, i16* %bigbase0
> > > > >
> > > > > %loaded = load i8* %phi
> > > > > ret i8 %loaded
> > > > > }
> > > > >
> > > > > because %phi will have a partial overlap with
%bigbase0, the
> > > > > only
> > > > > uncertainty is whether the overlap is with the low byte
or the
> > > > > high
> > > > > byte. But if I modify the test to be this:
> > > > >
> > > > > define i8 @test0x(i1 %x) {
> > > > > entry:
> > > > > %base = alloca i8, align 4
> > > > > %baseplustwo = getelementptr i8* %base, i64 2
> > > > > br i1 %x, label %red, label %green
> > > > > red:
> > > > > br label %green
> > > > > green:
> > > > > %phi = phi i8* [ %baseplustwo, %red ], [ %base, %entry
]
> > > > > store i8 0, i8* %phi
> > > > >
> > > > > %bigbase0 = bitcast i8* %base to i16*
> > > > > store i16 -1, i16* %bigbase0
> > > > >
> > > > > %loaded = load i8* %phi
> > > > > ret i8 %loaded
> > > > > }
> > > > >
> > > > > I still get this result:
> > > > > PartialAlias: i16* %bigbase0, i8* %phi
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > but now %phi might not overlap %bigbase0 at all
(although, when
> > > > > it
> > > > > does, there is a partial overlap), so we should just
return
> > > > > MayAlias
> > > > > (perhaps without delegation because this is a
definitive
> > > > > result?).
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > Yeah, i have to do some size checking, let me see if we
have
> > > > > the
> > > > > info
> > > > > and i'll update the patch.
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > Otherwise, my view is that we should always delegate
MayAlias,
> > > > > because we have no idea what order the passes are in or
what
> > > > > pass
> > > > > someone has inserted where :)
> > > > >
> > > > >
> > > > > (WIW: I believe the same about everything except
MustAlias and
> > > > > NoAlias, but currently we don't delegate
PartialAlias.
> > > > > We claim PartialAlias is a definitive result, but it
really
> > > > > isn't.
> > > > > Right now we have TBAA that will give NoAlias results
on things
> > > > > other
> > > > > passes claim are PartialAlias, and that result is
correct.
> > > > > That's
> > > > > just in our default, we have no idea what other people
do. Even
> > > > > if
> > > > > you ignore TBAA, plenty of other compilers have
> > > > > noalias/mustalias
> > > > > metadata that would have the same effect.
> > > >
> > > > --
> > > > Hal Finkel
> > > > Assistant Computational Scientist
> > > > Leadership Computing Facility
> > > > Argonne National Laboratory
> > > >
> > >
> > > --
> > > Hal Finkel
> > > Assistant Computational Scientist
> > > Leadership Computing Facility
> > > Argonne National Laboratory
> > >
> > >
> > > --
> > >
> > >
> > > Hal Finkel
> > > Assistant Computational Scientist
> > > Leadership Computing Facility
> > > Argonne National Laboratory
> > >
> > >
> > >
> > >
> >
> > --
> > Hal Finkel
> > Assistant Computational Scientist
> > Leadership Computing Facility
> > Argonne National Laboratory
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150125/518bd316/attachment.html>
-------------- next part --------------
diff --git a/lib/Analysis/CFLAliasAnalysis.cpp
b/lib/Analysis/CFLAliasAnalysis.cpp
index 9783671..4286c94 100644
--- a/lib/Analysis/CFLAliasAnalysis.cpp
+++ b/lib/Analysis/CFLAliasAnalysis.cpp
@@ -862,6 +862,19 @@ static void buildGraphFrom(CFLAliasAnalysis &Analysis,
Function *Fn,
   }
 }
 
+static bool canSkipAddingToSets(Value* Val) {
+  // Constants can share instances, which may falsely unify multiple
+  // sets, e.g. in
+  // store i32* null, i32** %ptr1
+  // store i32* null, i32** %ptr2
+  // clearly ptr1 and ptr2 should not be unified into the same set, so
+  // we should filter out the (potentially shared) instance to
+  // i32* null.
+  return isa<Constant>(Val) &&
+         !isa<GlobalValue>(Val) &&
+         !isa<ConstantExpr>(Val);
+}
+
 static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn)
{
   NodeMapT Map;
   GraphT Graph;
@@ -893,7 +906,7 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis
&Analysis, Function *Fn) {
     while (!Worklist.empty()) {
       auto Node = Worklist.pop_back_val();
       auto *CurValue = findValueOrDie(Node);
-      if (isa<Constant>(CurValue) &&
!isa<GlobalValue>(CurValue))
+      if (canSkipAddingToSets(CurValue))
         continue;
 
       for (const auto &EdgeTuple : Graph.edgesFor(Node)) {
@@ -902,7 +915,7 @@ static FunctionInfo buildSetsFrom(CFLAliasAnalysis
&Analysis, Function *Fn) {
         auto &OtherNode = std::get<1>(EdgeTuple);
         auto *OtherValue = findValueOrDie(OtherNode);
 
-        if (isa<Constant>(OtherValue) &&
!isa<GlobalValue>(OtherValue))
+        if (canSkipAddingToSets(OtherValue))
           continue;
 
         bool Added;