[LLVMdev] question about enabling cfl-aa and collecting a57 numbers
George Burgess IV
george.burgess.iv at gmail.com
Thu Jan 22 17:46:45 PST 2015
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
>>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150122/c6d82b4e/attachment.html>
More information about the llvm-dev
mailing list