[LLVMdev] Alias Analysis accuracy

[Welson Sun]

Dear LLVM,

I would like to understand how to improve the LLVM alias analysis accuracy.
I am currently using llvmgcc 2.9 and llvm 3.0. Here is the C code:

void foo(int a[SIZE], int b[SIZE], int c[SIZE])
{
  for(int i=0; i<SIZE; i++)
    c[i] = a[i] + b[i];
}

Here is the IR:
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-f128:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

define void @_Z3fooPiS_S_(i32* %a, i32* %b, i32* %c) nounwind {
entry:
  %a_addr = alloca i32*, align 8
  %b_addr = alloca i32*, align 8
  %c_addr = alloca i32*, align 8
  %i = alloca i32
  %"alloca point" = bitcast i32 0 to i32
  store i32* %a, i32** %a_addr
  store i32* %b, i32** %b_addr
  store i32* %c, i32** %c_addr
  store i32 0, i32* %i, align 4
  br label %bb1

bb:                                               ; preds = %bb1
  %0 = load i32** %a_addr, align 8
  %1 = load i32* %i, align 4
  %2 = sext i32 %1 to i64
  %3 = getelementptr inbounds i32* %0, i64 %2
  %4 = load i32* %3, align 1
  %5 = load i32** %b_addr, align 8
  %6 = load i32* %i, align 4
  %7 = sext i32 %6 to i64
  %8 = getelementptr inbounds i32* %5, i64 %7
  %9 = load i32* %8, align 1
  %10 = add nsw i32 %4, %9
  %11 = load i32** %c_addr, align 8
  %12 = load i32* %i, align 4
  %13 = sext i32 %12 to i64
  %14 = getelementptr inbounds i32* %11, i64 %13
  store i32 %10, i32* %14, align 1
  %15 = load i32* %i, align 4
  %16 = add nsw i32 %15, 1
  store i32 %16, i32* %i, align 4
  br label %bb1

bb1:                                              ; preds = %bb, %entry
  %17 = load i32* %i, align 4
  %18 = icmp sle i32 %17, 9
  br i1 %18, label %bb, label %bb2

bb2:                                              ; preds = %bb1
  br label %return

return:                                           ; preds = %bb2
  ret void
}

Now run: opt -basicaa -aa-eval -print-all-alias-modref-info < foo.s >
/dev/null, you get this:
Function: _Z3fooPiS_S_: 13 pointers, 0 call sites
  MayAlias:     i32* %a, i32* %b
  MayAlias:     i32* %a, i32* %c
  MayAlias:     i32* %b, i32* %c
  NoAlias:      i32* %a, i32** %a_addr
  NoAlias:      i32* %b, i32** %a_addr
  NoAlias:      i32* %c, i32** %a_addr
  NoAlias:      i32* %a, i32** %b_addr
  NoAlias:      i32* %b, i32** %b_addr
  NoAlias:      i32* %c, i32** %b_addr
  NoAlias:      i32** %a_addr, i32** %b_addr
  NoAlias:      i32* %a, i32** %c_addr
  NoAlias:      i32* %b, i32** %c_addr
  NoAlias:      i32* %c, i32** %c_addr
  NoAlias:      i32** %a_addr, i32** %c_addr
  NoAlias:      i32** %b_addr, i32** %c_addr
  NoAlias:      i32* %a, i32* %i
  NoAlias:      i32* %b, i32* %i
  NoAlias:      i32* %c, i32* %i
  NoAlias:      i32* %i, i32** %a_addr
  NoAlias:      i32* %i, i32** %b_addr
  NoAlias:      i32* %i, i32** %c_addr
  MayAlias:     i32* %0, i32* %a
  MayAlias:     i32* %0, i32* %b
  MayAlias:     i32* %0, i32* %c
  NoAlias:      i32* %0, i32** %a_addr
  NoAlias:      i32* %0, i32** %b_addr
  NoAlias:      i32* %0, i32** %c_addr
  NoAlias:      i32* %0, i32* %i
  MayAlias:     i32* %3, i32* %a
  MayAlias:     i32* %3, i32* %b
  MayAlias:     i32* %3, i32* %c
  NoAlias:      i32* %3, i32** %a_addr
  NoAlias:      i32* %3, i32** %b_addr
  NoAlias:      i32* %3, i32** %c_addr
  NoAlias:      i32* %3, i32* %i
  PartialAlias: i32* %0, i32* %3
  MayAlias:     i32* %5, i32* %a
  MayAlias:     i32* %5, i32* %b
  MayAlias:     i32* %5, i32* %c
  NoAlias:      i32* %5, i32** %a_addr
  NoAlias:      i32* %5, i32** %b_addr
  NoAlias:      i32* %5, i32** %c_addr
  NoAlias:      i32* %5, i32* %i
  MayAlias:     i32* %0, i32* %5
  MayAlias:     i32* %3, i32* %5
  MayAlias:     i32* %8, i32* %a
  MayAlias:     i32* %8, i32* %b
  MayAlias:     i32* %8, i32* %c
  NoAlias:      i32* %8, i32** %a_addr
  NoAlias:      i32* %8, i32** %b_addr
  NoAlias:      i32* %8, i32** %c_addr
  NoAlias:      i32* %8, i32* %i
  MayAlias:     i32* %0, i32* %8
  MayAlias:     i32* %3, i32* %8
  PartialAlias: i32* %5, i32* %8
  MayAlias:     i32* %11, i32* %a
  MayAlias:     i32* %11, i32* %b
  MayAlias:     i32* %11, i32* %c
  NoAlias:      i32* %11, i32** %a_addr
  NoAlias:      i32* %11, i32** %b_addr
  NoAlias:      i32* %11, i32** %c_addr
  NoAlias:      i32* %11, i32* %i
  MayAlias:     i32* %0, i32* %11
  MayAlias:     i32* %11, i32* %3
  MayAlias:     i32* %11, i32* %5
  MayAlias:     i32* %11, i32* %8
  MayAlias:     i32* %14, i32* %a
  MayAlias:     i32* %14, i32* %b
  MayAlias:     i32* %14, i32* %c
  NoAlias:      i32* %14, i32** %a_addr
  NoAlias:      i32* %14, i32** %b_addr
  NoAlias:      i32* %14, i32** %c_addr
  NoAlias:      i32* %14, i32* %i
  MayAlias:     i32* %0, i32* %14
  MayAlias:     i32* %14, i32* %3
  MayAlias:     i32* %14, i32* %5
  MayAlias:     i32* %14, i32* %8
  PartialAlias: i32* %11, i32* %14
===== Alias Analysis Evaluator Report =====
  78 Total Alias Queries Performed
  42 no alias responses (53.8%)
  33 may alias responses (42.3%)
  3 partial alias responses (3.8%)
  0 must alias responses (0.0%)
  Alias Analysis Evaluator Pointer Alias Summary: 53%/42%/3%/0%
  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!

So, all a, b and c may alias? I guess I have to read the BasicAliasAnalysis
code to understand what is going on. But this is obviously too conservative
to be useful.


Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120921/643541b2/attachment.html>