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

Hal Finkel hfinkel at anl.gov
Fri Jan 23 16:45:30 PST 2015


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




More information about the llvm-dev mailing list