llvm dev - Jun 2007 - [LLVMdev] Question about Alias Analysis

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
>