Alias Analysis accuracy

dragonware · September 21, 2012, 9:35pm

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

Eli_Friedman1 · September 21, 2012, 9:40pm

You have a function which takes three arbitrary "int*"; how exactly do
you expect the compiler to determine an aliasing relationship?

-Eli

Krzysztof_Parzyszek · September 21, 2012, 9:46pm

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

and so you can call this function with the same array for all parameters.

-K

dragonware · September 21, 2012, 9:49pm

Yeah. Is there a way to specify noalias between these arguments?

yxsamliu · September 21, 2012, 9:52pm

I think you may add restrict type qualifier.

Sam

dragonware · September 21, 2012, 9:57pm

Can you give an example? And is this limited to C (not C++) only?

dragonware · September 21, 2012, 10:08pm

OK, with the restrict type qualifier, it is a little bit better:

The IR’s function signature becomes:

define void @foo(i32* noalias %a, i32* noalias %b, i32* noalias %c) nounwind {

Now the AA result:

Function: foo: 13 pointers, 0 call sites
NoAlias: i32* %a, i32* %b
NoAlias: i32* %a, i32* %c
NoAlias: 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

a, b and c are no longer alias, as expected. However, they all may alias to %0. I guess basicaa doesn’t handle data flow analysis?

Krzysztof_Parzyszek · September 21, 2012, 10:16pm

What is %0? Can you paste the whole IR for foo?

-K

Eli_Friedman1 · September 21, 2012, 10:18pm

No. Try running mem2reg.

-Eli

dragonware · September 21, 2012, 10:20pm

The body of the IR is the same as in the first email.

dragonware · September 21, 2012, 10:22pm

Here is the result of running mem2reg then basicaa, it is even worse: (%a should be alias to %0, and partial alias to %3)

opt -mem2reg -basicaa -aa-eval -print-all-alias-modref-info < foo.s > /dev/null
Function: foo: 6 pointers, 0 call sites
NoAlias: i32* %a, i32* %b
NoAlias: i32* %a, i32* %c
NoAlias: i32* %b, i32* %c
PartialAlias: i32* %1, i32* %a
NoAlias: i32* %1, i32* %b
NoAlias: i32* %1, i32* %c
NoAlias: i32* %4, i32* %a
PartialAlias: i32* %4, i32* %b
NoAlias: i32* %4, i32* %c
NoAlias: i32* %1, i32* %4
NoAlias: i32* %8, i32* %a
NoAlias: i32* %8, i32* %b
PartialAlias: i32* %8, i32* %c
NoAlias: i32* %1, i32* %8
NoAlias: i32* %4, i32* %8

Arnold_Schwaighofer · September 21, 2012, 10:47pm

You see the result for running basicaa after mem2reg.

The IR after mem2reg will look like (you can look at it by doing
-mem2reg -basicaa -aa-eval -print-all-alias-modref-info < test.ll
-print-after-all)

define void @_Z3fooPiS_S_(i32* noalias %a, i32* noalias %b, i32*
noalias %c) nounwind {
entry:
%"alloca point" = bitcast i32 0 to i32
br label %bb1

bb: ; preds = %bb1
  %0 = sext i32 %i.0 to i64
  %1 = getelementptr inbounds i32* %a, i64 %0
  %2 = load i32* %1, align 1
  %3 = sext i32 %i.0 to i64
  %4 = getelementptr inbounds i32* %b, i64 %3
  %5 = load i32* %4, align 1
  %6 = add nsw i32 %2, %5
  %7 = sext i32 %i.0 to i64
  %8 = getelementptr inbounds i32* %c, i64 %7
  store i32 %6, i32* %8, align 1
  %9 = add nsw i32 %i.0, 1
  br label %bb1

bb1: ; preds = %bb, %entry
  %i.0 = phi i32 [ 0, %entry ], [ %9, %bb ]
  %10 = icmp sle i32 %i.0, 9
  br i1 %10, label %bb, label %bb2

bb2: ; preds = %bb1
br label %return

return: ; preds = %bb2
ret void
}

The results your are getting are correct.

dragonware · September 21, 2012, 10:49pm

Great! That makes sense! Thank you!

Topic		Replies	Views
Optimization issues (Alias Analysis?) LLVM Dev List Archives	3	77	July 6, 2016
Wrong AliasAnalysis::getModRefInfo result LLVM Dev List Archives	4	67	February 16, 2012
Question about Alias Analysis LLVM Dev List Archives	3	73	June 27, 2007
Optimization Problem LLVM Dev List Archives	2	84	April 29, 2019
AliasAnalysis Doubt. LLVM Dev List Archives	1	77	September 20, 2010

Alias Analysis accuracy

Related Topics