llvm dev - Feb 2010 - [LLVMdev] A very basic doubt about LLVM Alias Analysis

to compile it to bitcode I give the following command :

   llvm-gcc -emit-llvm -c -o s.bc s.c

and then I run different alias analysis passes like -anders-aa, -basicaa 
using following:

   opt -anders-aa -aa-eval -print-all-alias-modref-info  s.bc

 From this I get the following output:

Function: main: 8 pointers, 1 call sites
 NoAlias:    i32* %retval, i32** %j
 NoAlias:    i32* %retval, i32** %i
 NoAlias:    i32** %i, i32** %j
 NoAlias:    i32* %0, i32* %retval
 NoAlias:    i32* %0, i32** %j
 NoAlias:    i32* %0, i32** %i
 NoAlias:    i32* %2, i32* %retval
 NoAlias:    i32* %2, i32** %j
 NoAlias:    i32* %2, i32** %i
 NoAlias:    i32* %0, i32* %2
 NoAlias:    i32* %4, i32* %retval
 NoAlias:    i32* %4, i32** %j
 NoAlias:    i32* %4, i32** %i
 NoAlias:    i32* %0, i32* %4
 MayAlias:    i32* %2, i32* %4
 NoAlias:    i32* %k, i32* %retval
 NoAlias:    i32* %k, i32** %j
 NoAlias:    i32* %k, i32** %i
 NoAlias:    i32* %0, i32* %k
 MayAlias:    i32* %2, i32* %k
 MayAlias:    i32* %4, i32* %k
 NoAlias:    i32* %retval, i8* getelementptr inbounds ([9 x i8]* @.str, 
i32 0, i32 0)
 NoAlias:    i32** %j, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoAlias:    i32** %i, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoAlias:    i32* %0, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoAlias:    i32* %2, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoAlias:    i32* %4, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoAlias:    i32* %k, i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0)
 NoModRef:  Ptr: i32* %retval    <->  %6 = call i32 (i8*, ...)* 
@printf(i8* getelementptr inbounds ([9 x i8]* @.str, i32 0, i32 0), i32 
%5, i32 %3, i32 %1) nounwind ; <i32> [#uses=0]  NoModRef:  Ptr: i32** 
%j    <->  %6 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds 
([9 x i8]* @.str, i32 0, i32 0), i32 %5, i32 %3, i32 %1) nounwind ; 
<i32> [#uses=0]  NoModRef:  Ptr: i32** %i    <->  %6 = call i32
(i8*,
...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.str, i32 0, i32 
0), i32 %5, i32 %3, i32 %1) nounwind ; <i32> [#uses=0]  NoModRef:  Ptr: 
i32* %0    <->  %6 = call i32 (i8*, ...)* @printf(i8* getelementptr 
inbounds ([9 x i8]* @.str, i32 0, i32 0), i32 %5, i32 %3, i32 %1) 
nounwind ; <i32> [#uses=0]  NoModRef:  Ptr: i32* %2    <->  %6 =
call
i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.str, i32 
0, i32 0), i32 %5, i32 %3, i32 %1) nounwind ; <i32> [#uses=0]  
NoModRef:  Ptr: i32* %4    <->  %6 = call i32 (i8*, ...)* @printf(i8* 
getelementptr inbounds ([9 x i8]* @.str, i32 0, i32 0), i32 %5, i32 %3, 
i32 %1) nounwind ; <i32> [#uses=0]  NoModRef:  Ptr: i32* %k    <-> 
%6 =
call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* 
@.str, i32 0, i32 0), i32 %5, i32 %3, i32 %1) nounwind ; <i32> 
[#uses=0]  NoModRef:  Ptr: i8* getelementptr inbounds ([9 x i8]* @.str, 
i32 0, i32 0)    <->  %6 = call i32 (i8*, ...)* @printf(i8* 
getelementptr inbounds ([9 x i8]* @.str, i32 0, i32 0), i32 %5, i32 %3, 
i32 %1) nounwind ; <i32> [#uses=0]===== Alias Analysis Evaluator Report 
==== 28 Total Alias Queries Performed
 25 no alias responses (89.2%)
 3 may alias responses (10.7%)
 0 must alias responses (0.0%)
 Alias Analysis Evaluator Pointer Alias Summary: 89%/10%/0%
 8 Total ModRef Queries Performed
 8 no mod/ref responses (100.0%)
 0 mod responses (0.0%)
 0 ref responses (0.0%)
 0 mod & ref responses (0.0%)
 Alias Analysis Evaluator Mod/Ref Summary: 100%/0%/0%/0%



And here nowhere it shows even a may alias relation between i & j.
I am interpreting this by looking at No Alias/May Alias/Must Alias 
outputs shown infron of them. eg

 NoAlias:    i32** %i, i32** %j

I interpret it as no alias relation between i & j.



Duncan Sands wrote:
> Hi Ambika,
>
>> Oh m sorry for that mistake as I had points to in mind.
>> But still what about the following prog:
>>
>> int main()
>> {
>>        int *i,*j,k;
>>        i=&k;
>>        j=&k;
>>        k=4;
>>        printf("%d,%d,%d",*i,*j,k);
>>        return 0;
>> }
>>
>>
>> here too i dont get <i,j> alias each other.
>
> how are you compiling to bitcode, and how are you determining that alias
> analysis thinks they don't alias?
>
> Ciao,
>
> Duncan.

Hi Ambika,
> to compile it to bitcode I give the following command :
> 
>   llvm-gcc -emit-llvm -c -o s.bc s.c
> 
> and then I run different alias analysis passes like -anders-aa, -basicaa 
> using following:
> 
>   opt -anders-aa -aa-eval -print-all-alias-modref-info  s.bc
alias analysis will work poorly if you don't run any optimizers.
The alias analysis passes assume that at least some basic optimizations
have been done.  Try compiling like this:

   llvm-gcc -emit-llvm -c -o s.bc s.c -O1

Ciao,

Duncan.

>
>
>
> And here nowhere it shows even a may alias relation between i & j.
> I am interpreting this by looking at No Alias/May Alias/Must Alias
> outputs shown infron of them. eg
>
>  NoAlias:    i32** %i, i32** %j
>
> I interpret it as no alias relation between i & j.
Because the pointers being used aren't named i & j anymore.
 MayAlias:    i32* %2, i32* %4
 MayAlias:    i32* %2, i32* %k
 MayAlias:    i32* %4, i32* %k

  %2 = load i32** %j, align 4                     ; <i32*> [#uses=1]
  %4 = load i32** %i, align 4                     ; <i32*> [#uses=1]

>
> Because the pointers being used aren't named i & j anymore.
>  MayAlias:    i32* %2, i32* %4
>  MayAlias:    i32* %2, i32* %k
>  MayAlias:    i32* %4, i32* %k
>
>  %2 = load i32** %j, align 4                     ; <i32*> [#uses=1]
>  %4 = load i32** %i, align 4                     ; <i32*> [#uses=1]
>
In general, you can't expect the names of variables in the bitcode
will have any relationship to the names of variables in the source
program.
You can figure out the mapping using debug info, but expecting the
output of aa-eval and printing to tell you anything about the source
itself
is a bad idea.

Hi,

Using this option I do get all the vars as may alias ie

 MayAlias:    i32* %j.0, i32* %k
MayAlias:    i32* %i.0, i32* %k
MayAlias:    i32* %i.0, i32* %j.0

Is there any other analysis which will give them as must aliases.

Actually what I want to do is implement a flow sensitive points-to(not 
alias) analysis and then use that information for some optimizations 
like PRE.
Will that be possible?

Duncan Sands wrote:
> Hi Ambika,
>
>> to compile it to bitcode I give the following command :
>>
>>   llvm-gcc -emit-llvm -c -o s.bc s.c
>>
>> and then I run different alias analysis passes like -anders-aa, 
>> -basicaa using following:
>>
>>   opt -anders-aa -aa-eval -print-all-alias-modref-info  s.bc
>
> alias analysis will work poorly if you don't run any optimizers.
> The alias analysis passes assume that at least some basic optimizations
> have been done.  Try compiling like this:
>
>   llvm-gcc -emit-llvm -c -o s.bc s.c -O1
>
> Ciao,
>
> Duncan.