Hi! I'm currently working on developing a new technique for alias
analysis and wish to know how to compare it's results to the results
that LLVM gets. The algorithm I have operates on LLVM assembly (I
wrote the analysis in Haskell, so unfortunately I can't embed it into
LLVM very easily). I tried using the option to print alias sets, but
I'm not quite sure how to interpret the results (or even if this is an
accurate measure of the alias information provided by LLVM. I took a
simple program (shown below) and compiled it with llvm-gcc -O0 (I
didn't want it to optimize away the code). The output I got (using
-basicaa -anders-aa -show-alias-sets) is also shown below.

I guess what confuses me is that it doesn't seem like it was able to
figure out that *b = a. Am I looking at this wrong? Is there a more
accurate way of getting the alias information out of the pass?

Thanks,
Ben Chambers

Output:
AliasSet[0x601e70,2] may alias, Mod/Ref Pointers: (i32* %a, 4),
(i32* %tmp1, 4)
AliasSet[0x601ea0,1] must alias, Mod/Ref Pointers: (i32** %b, 4)
AliasSet[0x601f10,1] must alias, Mod/Ref Pointers: (i32* %tmp, 4)
AliasSet[0x601f60,1] must alias, Mod/Ref Pointers: (i32* %retval, 4)

Input:

int main() {
int a = 5;
int* b = &a;
return *b;
}

Assembly:

define i32 @main() {
entry:
%retval = alloca i32, align 4 ; <i32*> [#uses=2]
%tmp = alloca i32, align 4 ; <i32*> [#uses=2]
%a = alloca i32, align 4 ; <i32*> [#uses=2]
%b = alloca i32*, align 4 ; <i32**> [#uses=2]
"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
store i32 5, i32* %a
store i32* %a, i32** %b
%tmp1 = load i32** %b ; <i32*> [#uses=1]
%tmp2 = load i32* %tmp1 ; <i32> [#uses=1]
store i32 %tmp2, i32* %tmp
%tmp3 = load i32* %tmp ; <i32> [#uses=1]
store i32 %tmp3, i32* %retval
br label %return

return: ; preds = %entry
%retval4 = load i32* %retval ; <i32> [#uses=1]
ret i32 %retval4
}

I guess what confuses me is that it doesn't seem like it was able to
figure out that *b = a. Am I looking at this wrong? Is there a more
accurate way of getting the alias information out of the pass?

The answer is to not look at the alias sets. I'd suggest looking at the raw results of alias queries. To do this, use the -aa-eval pass with the -print-all-alias-modref-info option. The alias set builder uses unification to build the sets, so it will give you less precise information than the raw queries do.

-Chris

Thanks,
Ben Chambers

Output:
AliasSet[0x601e70,2] may alias, Mod/Ref Pointers: (i32* %a, 4),
(i32* %tmp1, 4)
AliasSet[0x601ea0,1] must alias, Mod/Ref Pointers: (i32** %b, 4)
AliasSet[0x601f10,1] must alias, Mod/Ref Pointers: (i32* %tmp, 4)
AliasSet[0x601f60,1] must alias, Mod/Ref Pointers: (i32* %retval, 4)

Input:

int main() {
int a = 5;
int* b = &a;
return *b;
}

Assembly:

define i32 @main() {
entry:
%retval = alloca i32, align 4 ; <i32*> [#uses=2]
%tmp = alloca i32, align 4 ; <i32*> [#uses=2]
%a = alloca i32, align 4 ; <i32*> [#uses=2]
%b = alloca i32*, align 4 ; <i32**> [#uses=2]
"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
store i32 5, i32* %a
store i32* %a, i32** %b
%tmp1 = load i32** %b ; <i32*> [#uses=1]
%tmp2 = load i32* %tmp1 ; <i32> [#uses=1]
store i32 %tmp2, i32* %tmp
%tmp3 = load i32* %tmp ; <i32> [#uses=1]
store i32 %tmp3, i32* %retval
br label %return

return: ; preds = %entry
%retval4 = load i32* %retval ; <i32> [#uses=1]
ret i32 %retval4
}
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

Thanks, that's a lot more like the output I was expecting. But, I'm
now wondering if I'm doing something wrong because the output confuses
me.

When run on the program:

int main() {
int a = 5;
int* b = &a;
int* c = &a;
return *b;
}

I would expect to see either b may alias c or b must alias c. But, it
doesn't even appear in the list. Furthermore, I would expect to see
**b (may/must) alias *c, but it instead says that this isn't true. Am
I not running the right passes (I used -basicaa -anders-aa) or am I

Results:

Function: main: 6 pointers, 0 call sites
NoAlias: i32* %retval, i32* %tmp
NoAlias: i32* %a, i32* %tmp
NoAlias: i32* %a, i32* %retval
NoAlias: i32** %b, i32* %tmp
NoAlias: i32** %b, i32* %retval
NoAlias: i32** %b, i32* %a
NoAlias: i32** %c, i32* %tmp
NoAlias: i32** %c, i32* %retval
NoAlias: i32** %c, i32* %a
NoAlias: i32** %c, i32** %b
NoAlias: i32* %tmp1, i32* %tmp
NoAlias: i32* %tmp1, i32* %retval
MayAlias: i32* %tmp1, i32* %a
NoAlias: i32* %tmp1, i32** %b
NoAlias: i32* %tmp1, i32** %c
===== Alias Analysis Evaluator Report =====
15 Total Alias Queries Performed
14 no alias responses (93.3%)
1 may alias responses (6.6%)
0 must alias responses (0.0%)
Alias Analysis Evaluator Pointer Alias Summary: 93%/6%/0%
Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!

Thanks, that's a lot more like the output I was expecting. But, I'm
now wondering if I'm doing something wrong because the output confuses
me.

It won't make a lot of sense to you unless you look at the LLVM IR. In particular "%a" represents the address of a, not its contents.

-Chris

When run on the program:

int main() {
int a = 5;
int* b = &a;
int* c = &a;
return *b;
}

I would expect to see either b may alias c or b must alias c. But, it
doesn't even appear in the list. Furthermore, I would expect to see
**b (may/must) alias *c, but it instead says that this isn't true. Am
I not running the right passes (I used -basicaa -anders-aa) or am I

Results:

Function: main: 6 pointers, 0 call sites
NoAlias: i32* %retval, i32* %tmp
NoAlias: i32* %a, i32* %tmp
NoAlias: i32* %a, i32* %retval
NoAlias: i32** %b, i32* %tmp
NoAlias: i32** %b, i32* %retval
NoAlias: i32** %b, i32* %a
NoAlias: i32** %c, i32* %tmp
NoAlias: i32** %c, i32* %retval
NoAlias: i32** %c, i32* %a
NoAlias: i32** %c, i32** %b
NoAlias: i32* %tmp1, i32* %tmp
NoAlias: i32* %tmp1, i32* %retval
MayAlias: i32* %tmp1, i32* %a
NoAlias: i32* %tmp1, i32** %b
NoAlias: i32* %tmp1, i32** %c
===== Alias Analysis Evaluator Report =====
15 Total Alias Queries Performed
14 no alias responses (93.3%)
1 may alias responses (6.6%)
0 must alias responses (0.0%)
Alias Analysis Evaluator Pointer Alias Summary: 93%/6%/0%
Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!

I guess what confuses me is that it doesn't seem like it was able to
figure out that *b = a. Am I looking at this wrong? Is there a more
accurate way of getting the alias information out of the pass?

The answer is to not look at the alias sets. I'd suggest looking at the
raw results of alias queries. To do this, use the -aa-eval pass with the
-print-all-alias-modref-info option. The alias set builder uses
unification to build the sets, so it will give you less precise
information than the raw queries do.

-Chris

Thanks,
Ben Chambers

Output:
AliasSet[0x601e70,2] may alias, Mod/Ref Pointers: (i32* %a, 4),
(i32* %tmp1, 4)
AliasSet[0x601ea0,1] must alias, Mod/Ref Pointers: (i32** %b, 4)
AliasSet[0x601f10,1] must alias, Mod/Ref Pointers: (i32* %tmp, 4)
AliasSet[0x601f60,1] must alias, Mod/Ref Pointers: (i32* %retval, 4)

Input:

int main() {
int a = 5;
int* b = &a;
return *b;
}

Assembly:

define i32 @main() {
entry:
%retval = alloca i32, align 4 ; <i32*> [#uses=2]
%tmp = alloca i32, align 4 ; <i32*> [#uses=2]
%a = alloca i32, align 4 ; <i32*> [#uses=2]
%b = alloca i32*, align 4 ; <i32**> [#uses=2]
"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
store i32 5, i32* %a
store i32* %a, i32** %b
%tmp1 = load i32** %b ; <i32*> [#uses=1]
%tmp2 = load i32* %tmp1 ; <i32> [#uses=1]
store i32 %tmp2, i32* %tmp
%tmp3 = load i32* %tmp ; <i32> [#uses=1]
store i32 %tmp3, i32* %retval
br label %return

return: ; preds = %entry
%retval4 = load i32* %retval ; <i32> [#uses=1]
ret i32 %retval4
}
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris

--
Chris Lattner's Homepage
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-Chris