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

> 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/0c575009/attachment.html>

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>

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>