A very basic doubt about LLVM Alias Analysis

Hi,

I have a program like:

main() {
    int i,*k;
    k = &i;
    i=4;
    ......

}

then why dont i get {k -> i} ie k is aliased to i in any of the analysis.

If i want to get this then how can i get it.

thanks and regards,
Ambika

Hi ambika,

main() {
    int i,*k;
    k = &i;

then why dont i get {k -> i} ie k is aliased to i in any of the analysis.

only pointers can alias each other, and i is not a pointer.

Ciao,

Duncan.

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

Your example is too simple, i,j,k don't exist after running mem2reg.
And well, without running mem2reg i and j will be stack variables, so
you need to look for the value that is loaded from them.
That is the real pointer:
  AliasSet[0x0x1631400,3] may alias, Mod/Ref Pointers: (i32* %k, 4),
(i32* %tmp, 4), (i32* %tmp2, 4)

Here %tmp is i ( %tmp = load i32** %i ), %tmp2 is j ( %tmp2 = load
i32** %j).

If you make it a bit more complicated:
int main(int argc, char **argv)
{
        int *i=0,*j=0,k;
        if (argc > 1) {
          i=&k;
        } else {
          j=&k;
        }
        k=4;
        printf("%d,%d,%d,%p,%p",*i,*j,k,i,j);
        return 0;
}

Then you get this:
  AliasSet[0x0xb8e6a0,3] may alias, Mod/Ref Pointers: (i32* %k, 4),
(i32* %i.0, 4), (i32* %j.0, 4)

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

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.

I tried the program u mentioned but still did not get the result you are getting. I think there must be some mistake in compiling.
The commands which I am using are :

To create bc file:

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

and to get alias result :

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

Török Edwin wrote:

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,

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.

at -O1 these variables are entirely eliminated here. I'm surprised
they aren't eliminated for you.

Ciao,

Duncan.

PS:

$ cat ambika.c
int main()
{
        int *i,*j,k;
        i=&k;
        j=&k;
        k=4;
        printf("%d,%d,%d",*i,*j,k);
        return 0;
}
$ llvm-gcc -S -O1 -emit-llvm -o - ambika.c
ambika.c: In function ‘main’:
ambika.c:7: warning: incompatible implicit declaration of built-in function ‘printf’
; ModuleID = 'ambika.c'
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

@.str = private constant [9 x i8] c"%d,%d,%d\00", align 1 ; <[9 x i8]*> [#uses=1]

define i32 @main() nounwind {
entry:
   %0 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.str, i64 0, i64 0), i32 4, i32 4, i32 4) nounwind ; <i32> [#uses=0]
   ret i32 0
}

declare i32 @printf(i8* nocapture, ...) nounwind

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?

Hi,

I actually used the example mentioned by Török

int main(int argc, char **argv)
{
        int *i=0,*j=0,k;
        if (argc > 1) {
          i=&k;
        } else {
          j=&k;
        }
        k=4;
        printf("%d,%d,%d,%p,%p",*i,*j,k,i,j);
        return 0;
}

Duncan Sands wrote: