[LLVMdev] Alias Analysis Semantics

[Jeremy Salwen]

Hey Daniel,

Thanks again for the help.  I'm still a bit confused about the interface to
the alias analysis.   It seems like we are talking about different
interfaces.  Has it changed from what the documentation says?  As far as I
can tell, the documentation takes a specific Value*, and no information
about which dynamic execution it is talking about.

When you say "Right. It's a query about specific loads and stores." it
sounds like you are saying that it does consider dynamic executions, and
that you can make queries about specific dynamic executions.  I can't seem
to find this option anywhere in the API..

Perhaps someone else could clear the confusion, because I feel like there
is a gap of communication.

For example, in this code what would the result be for the first store and
the first load?

#include <cstdio>
> #include <cstdlib>
> int main(int c, char** argv) {
>  int* A=(int*)malloc(100*sizeof(int));
>
>  if(c>1) {
>   for(int i=0; i<5; i++) {
>     A[i]=5;
>   }
>  } else {
>   A[1]=5;
>  }
>  printf("%d\n",A[4]);
>  free(A);
> }
>

MustAlias?  Because whenever they are executed, they do alias.  Or MayAlias?

Jeremy


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

> On Wed, Aug 13, 2014 at 2:52 PM, Jeremy Salwen <jeremysalwen at gmail.com>
> wrote:
> > 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?
> Yes. They always have the same pointer value at the point of *y = *x.
> Though note, in SSA form, you would likely end up with two or three
> x's (x_1 = &A[0], x_2 = phi(x_1, x_3), x_3 = &A[i+1]), and only
> mustalias(y, x_2) would be true.
>
>
> >  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.
>
> Right. It's a query about specific loads and stores.
>
> >  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.
>
> The question is what happens at the point of the load/store.  The
> queries you perform in LLVM are  about a specific load and a specific
> store.
>
> At the point of *y = *x, y MUSTALIAS x.
> There are other points this is not true, but that's not relevant to
> *this store* and *this load*.
>
> There is no generic query mechanism to ask "does this relationship
> hold over all points of the program" (and if there was, it would
> return false :P)
>
> >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.
> These are all MayAlias.
>
>
> >
> > 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/d2aa990b/attachment.html>