[LLVMdev] Alias Analysis Semantics

[Daniel Berlin]

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