[LLVMdev] Alias Analysis Semantics

[Daniel Berlin]

Let me take your previous example in an attempt to hopefully explain why
"dynamic instructions" do not matter to the answer:
You asked about:
> 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];
>> }
>

This is not what it looks like in LLVM.

In LLVM, it looks like this:

std::vector<int> A(100);
> int* x,y;
>

>
x_1=GEP A, 0, 0
>
for(int i=0; i<100; i++) {
>
    i_2 = phi (0, i_3)
    x_2 = phi(x_1, x_3)
    y_1 = GEP A, 0, i_2
    temp = load x_2
    store y_1, temp
    temp2 = add i_2, 1
    x_3 = GEP A, 0, temp2
    i_3 = add i_2, 1
}

As you can see, every time you redefine the value of the pointer x to a new
value, it gets a new name.

alias(x_1, y_1) = mayalias
alias(x_2, y_1) = mustalias
alias(x_3, y_1) = mayalias


The only interesting question, IMHO, is whether alias(x_3,y_1) is MayAlias
or NoAlias.
x_2 clearly has the same value as y_1 at all times throughout the program.




On Thu, Aug 14, 2014 at 6:54 AM, Daniel Berlin <dberlin at dberlin.org> wrote:

> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140814/31da76ef/attachment.html>