llvm dev - Aug 2014 - [LLVMdev] Alias Analysis Semantics

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>

On Wed, Aug 13, 2014 at 8:35 PM, Jeremy Salwen <jeremysalwen at gmail.com>
wrote:
> 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.
Sorry, yes, i was thinking of a different interface.
> 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.
The actual standard low level interface is:

virtual AliasResult alias(const Location &LocA, const Location &LocB);
(There is a value wrapper for this)

I think part of the confusion here is that you keep redefining
pointers and expecting the results of queries to change.

Outside of globals, LLVM is in SSA form.  Thus, these are queries will
end up being about specific pointers that will only be defined once.
In all of your examples, you have asked about local variables.  These
local variables will be put in SSA.  Every time you redefine the
pointer value, it will generate a new definition that is separate from
the old ones.
If you transform your examples above into globals, you may get
different answers.


>
> 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..
Yes, sorry, I was thinking of the MemoryDependence interface, which
does give you that information.
AliasAnalysis does not.
>
> 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?
Since you seem to be having trouble going all the way down the rabbit
hole here, let me take a different approach.

In this example, A[i] is not an LLVM location or value *.
You will never see A[i] in the LLVM IR to query about.
You will see two pointers as this:
   %i.0 = phi i32 [ 0, %4 ], [ %11, %10 ]
   %8 = sext i32 %i.0 to i64
   %9 = getelementptr inbounds i32* %2, i64 %8
   store i32 5, i32* %9, align 4

and
 %16 = getelementptr inbounds i32* %2, i64 4
   %17 = load i32* %16, align 4

The query will be alias(%9, %16)

In this case, it cannot prove it is MustAlias, but it is actually MustAlias.
It will, however, return MayAlias because it is not powerful enough to prove it.

If you want to know what llvm *does* in any situation, i would use:
opt  -scev-aa -tbaa -basicaa -aa-eval -print-no-aliases
-print-may-aliases -print-must-aliases

However, note that this will not give you "what could it answer" only
"what does it answer", which is very different.

On Thu, Aug 14, 2014 at 6:37 AM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Wed, Aug 13, 2014 at 8:35 PM, Jeremy Salwen <jeremysalwen at
gmail.com> wrote:
>> 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.
> Sorry, yes, i was thinking of a different interface.
>
>> 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.
>
> The actual standard low level interface is:
>
> virtual AliasResult alias(const Location &LocA, const Location
&LocB);
> (There is a value wrapper for this)
>
> I think part of the confusion here is that you keep redefining
> pointers and expecting the results of queries to change.
>
> Outside of globals, LLVM is in SSA form.  Thus, these are queries will
> end up being about specific pointers that will only be defined once.
> In all of your examples, you have asked about local variables.  These
> local variables will be put in SSA.  Every time you redefine the
> pointer value, it will generate a new definition that is separate from
> the old ones.
> If you transform your examples above into globals, you may get
> different answers.
>
>
>
>>
>> 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..
> Yes, sorry, I was thinking of the MemoryDependence interface, which
> does give you that information.
> AliasAnalysis does not.
>
>>
>> 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?
> Since you seem to be having trouble going all the way down the rabbit
> hole here, let me take a different approach.
>
> In this example, A[i] is not an LLVM location or value *.
> You will never see A[i] in the LLVM IR to query about.
> You will see two pointers as this:
>    %i.0 = phi i32 [ 0, %4 ], [ %11, %10 ]
>    %8 = sext i32 %i.0 to i64
>    %9 = getelementptr inbounds i32* %2, i64 %8
>    store i32 5, i32* %9, align 4
>
> and
>  %16 = getelementptr inbounds i32* %2, i64 4
>    %17 = load i32* %16, align 4
>
> The query will be alias(%9, %16)
>
> In this case, it cannot prove it is MustAlias, but it is actually
MustAlias.
> It will, however, return MayAlias because it is not powerful enough to
prove it.
Sigh, too early in the morning, pasted the right output, wrote the
answer while looking at the wrong pass output.
These two pointers will always be MayAlias.
LLVM later actually deletes the loop, and transforms the above into a
memset + a load from memset, and ends up with two mustalias pointers
in that case.