[LLVMdev] Alias Analysis Semantics

[Daniel Berlin]

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.