[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