[LLVMdev] Alias Analysis Semantics

[Jeremy Salwen]

Thanks Daniel!

I think you've cleared up some of my misconceptions, but I still am a bit
confused about some of the corner cases.

Suppose we had something like this


std::vector<int> A(100);
> int* x,y;
> x=&A[0];
>
for(int i=0; i<100; i++) {
>    y=&A[i];
>    *y=*x;
>    x=&A[i+1];
> }
>


Would the load and store instructions be MustAlias?  I think what it boils
down to is the distinction between static instructions and dynamic
instructions and how they are handled by alias analysis.

I originally interpreted MustAlias as saying /all/ dynamic instructions A
must alias with /all/ dynamic instructions B.  However, you're saying that
this is not the case. So it seems to me that instead we are only checking
if certain dynamic instructions alias.  It's not clear to me how the
dynamic instructions are matched up.  For example, in the above code, you
could match up the instructions by execution count, and find that they
never alias.  Or you could match up each dynamic load with the most recent
dynamic store, in which case they May/Must alias (depending on how you look
at it).  This is what I mean by aliasing model.

I'm also a bit unclear how this case would be handled:

std::vector<int> A(100);
> int* x,y;
> x=&A[0];
>
for(int i=0; i<100; i++) {
>    A[i]=5;
> }
> int z=A[2];
>

MayAlias? MustAlias? NeverAlias?  It depends on which dynamic instructions
the semantics refer to.

Thank you,
Jeremy


On Wed, Aug 13, 2014 at 5:22 PM, Daniel Berlin <dberlin at dberlin.org> wrote:

> On Wed, Aug 13, 2014 at 1:39 PM, Jeremy Salwen <jeremysalwen at gmail.com>
> wrote:
> > Hello all,
> >
> > I've read the documentation on alias analysis, and I think I understand
> it
> > literally, but I just want to be sure, because it seems a bit strange.
> >
> > As it says on this web page,
> >
> >> The MayAlias response is used whenever the two pointers might refer to
> the
> >> same object.
> >>
> >> The PartialAlias response is used when the two memory objects are known
> to
> >> be overlapping in some way, but do not start at the same address.
> >>
> >> The MustAlias response may only be returned if the two memory objects
> are
> >> guaranteed to always start at exactly the same location. A MustAlias
> >> response implies that the pointers compare equal.
> >
> > Reading this, it seems the "MustAlias" result is exceptionally strong.
> Yes.
>
> >
> > Consider this loop
> >
> >> std::vector<int> A(100);
> >> int* x,y;
> >>
> >> for(int i=0; i<100; i++) {
> >>    x=&A[i];
> >>    y=&A[i];
> >>    *y=*x;
> >> }
> >
> >
> > Here it seems obvious that the load and store on the last line must
> "alias"
> > in some sense, but the load and store in fact have different values
> between
> > different iterations of the loop, so if we interpret "always start at
> > exactly the same location" literally, that would mean "mustalias" is
> false
> I think one of us reads that sentence "wrong" :)
> The two memory objects here are "x" and "y". They are guaranteed to
> always start at the same location, and are pointer equal.
> Thus, they are MustAlias.
> I don't think "guaranteed to always start at the same location" meant
> "each individual pointer is guaranteed to always have the same value
> over the lifetime of the program".   If so, must-alias would be a
> proxy for loop-invariant + a bunch of other stuff, and you'd be able
> to simply do replacement of values if they mustalias. But you can't.
>
> In LLVM, a MustAlias b does not imply that the values of a and b
> individually do not change, but that "a and b" are pointer equal
> always.
>
>
> What I describe is how, AFAICT, it is implemented in all of the alias
> passes.
> For example, SCEVAA, which actually computes the recurrences for these
> loop expressions, has this:
>   // This is ScalarEvolutionAliasAnalysis. Get the SCEVs!
>    const SCEV *AS = SE->getSCEV(const_cast<Value *>(LocA.Ptr));
>    const SCEV *BS = SE->getSCEV(const_cast<Value *>(LocB.Ptr));
>
>    // If they evaluate to the same expression, it's a MustAlias.
>    if (AS == BS) return MustAlias;
>
>
> IE if the two recurrences for the pointers are equal, it's a mustalias.
>
> This should return mustalias for x and y above.
>
>
> >
> > Is MustAlias considering only the most recent execution?
>
> At least as defined, MustAlias should be an invariant that holds over
> the lifetime of the program.
> This is not a flow-sensitive or context-sensitive result.
>
>
> >  Or is it only
> > considering within the same iteration of a loop?  Does MustAlias use the
> > same aliasing model as the other results?
>
> What do you mean by aliasing model?
>
> >
> > Thank you for clearing this up for me.
> >
> > Jeremy
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140813/7ab5fefe/attachment.html>