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
}
On Mon, 25 Jun 2007, Ben Chambers wrote:> 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 at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-Chris -- http://nondot.org/sabre/ http://llvm.org/
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
misreading things.
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!
On 6/26/07, Chris Lattner <sabre at nondot.org>
wrote:> On Mon, 25 Jun 2007, Ben Chambers wrote:
> > 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 at cs.uiuc.edu http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> -Chris
>
> --
> http://nondot.org/sabre/
> http://llvm.org/
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>