[LLVMdev] Alias Analysis Semantics

[Daniel Berlin]

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.