RetroSearch Browse

Thu Jan 22 17:20:46 PST 2015 · http://lists.llvm.org/pipermail/llvm-dev/2015-January/081036.html

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

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://lists.llvm.org/pipermail/llvm-dev/2015-January/081036.html below:

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