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