[LLVMdev] Alias Analysis Semantics

[Daniel Berlin]

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
>