Dear LLVM,
<div><br></div><div>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:</div><div><div><br></div><div><font face="courier new, monospace">void foo(int a[SIZE], int b[SIZE], int c[SIZE])</font></div>
<div><font face="courier new, monospace">{</font></div><div><font face="courier new, monospace"> for(int i=0; i<SIZE; i++)</font></div><div><font face="courier new, monospace"> c[i] = a[i] + b[i];</font></div><div>
<font face="courier new, monospace">}</font></div></div><div><br></div><div>Here is the IR:</div><div><div><font face="courier new, monospace">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"</font></div>
<div><font face="courier new, monospace">target triple = "x86_64-unknown-linux-gnu"</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">define void @_Z3fooPiS_S_(i32* %a, i32* %b, i32* %c) nounwind {</font></div>
<div><font face="courier new, monospace">entry:</font></div><div><font face="courier new, monospace"> %a_addr = alloca i32*, align 8</font></div><div><font face="courier new, monospace"> %b_addr = alloca i32*, align 8</font></div>
<div><font face="courier new, monospace"> %c_addr = alloca i32*, align 8</font></div><div><font face="courier new, monospace"> %i = alloca i32</font></div><div><font face="courier new, monospace"> %"alloca point" = bitcast i32 0 to i32</font></div>
<div><font face="courier new, monospace"> store i32* %a, i32** %a_addr</font></div><div><font face="courier new, monospace"> store i32* %b, i32** %b_addr</font></div><div><font face="courier new, monospace"> store i32* %c, i32** %c_addr</font></div>
<div><font face="courier new, monospace"> store i32 0, i32* %i, align 4</font></div><div><font face="courier new, monospace"> br label %bb1</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">bb: ; preds = %bb1</font></div>
<div><font face="courier new, monospace"> %0 = load i32** %a_addr, align 8</font></div><div><font face="courier new, monospace"> %1 = load i32* %i, align 4</font></div><div><font face="courier new, monospace"> %2 = sext i32 %1 to i64</font></div>
<div><font face="courier new, monospace"> %3 = getelementptr inbounds i32* %0, i64 %2</font></div><div><font face="courier new, monospace"> %4 = load i32* %3, align 1</font></div><div><font face="courier new, monospace"> %5 = load i32** %b_addr, align 8</font></div>
<div><font face="courier new, monospace"> %6 = load i32* %i, align 4</font></div><div><font face="courier new, monospace"> %7 = sext i32 %6 to i64</font></div><div><font face="courier new, monospace"> %8 = getelementptr inbounds i32* %5, i64 %7</font></div>
<div><font face="courier new, monospace"> %9 = load i32* %8, align 1</font></div><div><font face="courier new, monospace"> %10 = add nsw i32 %4, %9</font></div><div><font face="courier new, monospace"> %11 = load i32** %c_addr, align 8</font></div>
<div><font face="courier new, monospace"> %12 = load i32* %i, align 4</font></div><div><font face="courier new, monospace"> %13 = sext i32 %12 to i64</font></div><div><font face="courier new, monospace"> %14 = getelementptr inbounds i32* %11, i64 %13</font></div>
<div><font face="courier new, monospace"> store i32 %10, i32* %14, align 1</font></div><div><font face="courier new, monospace"> %15 = load i32* %i, align 4</font></div><div><font face="courier new, monospace"> %16 = add nsw i32 %15, 1</font></div>
<div><font face="courier new, monospace"> store i32 %16, i32* %i, align 4</font></div><div><font face="courier new, monospace"> br label %bb1</font></div><div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">bb1: ; preds = %bb, %entry</font></div>
<div><font face="courier new, monospace"> %17 = load i32* %i, align 4</font></div><div><font face="courier new, monospace"> %18 = icmp sle i32 %17, 9</font></div><div><font face="courier new, monospace"> br i1 %18, label %bb, label %bb2</font></div>
<div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">bb2: ; preds = %bb1</font></div><div><font face="courier new, monospace"> br label %return</font></div>
<div><font face="courier new, monospace"><br></font></div><div><font face="courier new, monospace">return: ; preds = %bb2</font></div><div><font face="courier new, monospace"> ret void</font></div>
<div><font face="courier new, monospace">}</font></div></div><div><br></div><div>Now run: opt -basicaa -aa-eval -print-all-alias-modref-info < foo.s > /dev/null, you get this:</div><div><div><font face="courier new, monospace">Function: _Z3fooPiS_S_: 13 pointers, 0 call sites</font></div>
<div><span style="background-color:rgb(255,255,51)"><font face="courier new, monospace"> MayAlias: i32* %a, i32* %b</font></span></div><div><span style="background-color:rgb(255,255,51)"><font face="courier new, monospace"> MayAlias: i32* %a, i32* %c</font></span></div>
<div><span style="background-color:rgb(255,255,51)"><font face="courier new, monospace"> MayAlias: i32* %b, i32* %c</font></span></div><div><font face="courier new, monospace"> NoAlias: i32* %a, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %b, i32** %a_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %c, i32** %a_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %a, i32** %b_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %b, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %c, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32** %a_addr, i32** %b_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %a, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %b, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %c, i32** %c_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32** %a_addr, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32** %b_addr, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %a, i32* %i</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %b, i32* %i</font></div><div><font face="courier new, monospace"> NoAlias: i32* %c, i32* %i</font></div><div><font face="courier new, monospace"> NoAlias: i32* %i, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %i, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %i, i32** %c_addr</font></div><div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %a</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %c</font></div><div><font face="courier new, monospace"> NoAlias: i32* %0, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %0, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %0, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %0, i32* %i</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %3, i32* %a</font></div><div><font face="courier new, monospace"> MayAlias: i32* %3, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %3, i32* %c</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %3, i32** %a_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %3, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %3, i32** %c_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %3, i32* %i</font></div><div><font face="courier new, monospace"> PartialAlias: i32* %0, i32* %3</font></div><div><font face="courier new, monospace"> MayAlias: i32* %5, i32* %a</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %5, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %5, i32* %c</font></div><div><font face="courier new, monospace"> NoAlias: i32* %5, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %5, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %5, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %5, i32* %i</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %5</font></div><div><font face="courier new, monospace"> MayAlias: i32* %3, i32* %5</font></div><div><font face="courier new, monospace"> MayAlias: i32* %8, i32* %a</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %8, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %8, i32* %c</font></div><div><font face="courier new, monospace"> NoAlias: i32* %8, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %8, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %8, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %8, i32* %i</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %8</font></div><div><font face="courier new, monospace"> MayAlias: i32* %3, i32* %8</font></div><div><font face="courier new, monospace"> PartialAlias: i32* %5, i32* %8</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %a</font></div><div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %c</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %11, i32** %a_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %11, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %11, i32** %c_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %11, i32* %i</font></div><div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %11</font></div><div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %3</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %5</font></div><div><font face="courier new, monospace"> MayAlias: i32* %11, i32* %8</font></div><div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %a</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %b</font></div><div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %c</font></div><div><font face="courier new, monospace"> NoAlias: i32* %14, i32** %a_addr</font></div>
<div><font face="courier new, monospace"> NoAlias: i32* %14, i32** %b_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %14, i32** %c_addr</font></div><div><font face="courier new, monospace"> NoAlias: i32* %14, i32* %i</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %0, i32* %14</font></div><div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %3</font></div><div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %5</font></div>
<div><font face="courier new, monospace"> MayAlias: i32* %14, i32* %8</font></div><div><font face="courier new, monospace"> PartialAlias: i32* %11, i32* %14</font></div><div><font face="courier new, monospace">===== Alias Analysis Evaluator Report =====</font></div>
<div><font face="courier new, monospace"> 78 Total Alias Queries Performed</font></div><div><font face="courier new, monospace"> 42 no alias responses (53.8%)</font></div><div><font face="courier new, monospace"> 33 may alias responses (42.3%)</font></div>
<div><font face="courier new, monospace"> 3 partial alias responses (3.8%)</font></div><div><font face="courier new, monospace"> 0 must alias responses (0.0%)</font></div><div><font face="courier new, monospace"> Alias Analysis Evaluator Pointer Alias Summary: 53%/42%/3%/0%</font></div>
<div><font face="courier new, monospace"> Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!</font></div></div><div><br></div><div>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.</div>
<div><br></div><div><br></div><div>Thanks</div>