[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
Daniel Berlin
dberlin at dberlin.org
Thu Jan 22 17:27:57 PST 2015
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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150123/7d2057d9/attachment.html>
More information about the llvm-dev
mailing list