thr3ads.net - llvm dev - [LLVMdev] Alias Analysis accuracy [Sep 2012]

If this information is useful, please help other people find it:
Share via:

Welson Sun

2012-Sep-21 21:35 UTC

[LLVMdev] Alias Analysis accuracy

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>

Eli Friedman

2012-Sep-21 21:40 UTC

head link

[LLVMdev] Alias Analysis accuracy

On Fri, Sep 21, 2012 at 2:35 PM, Welson Sun <welson.sun at gmail.com>
wrote:> 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];
> }
> 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.
You have a function which takes three arbitrary "int*"; how exactly do
you expect the compiler to determine an aliasing relationship?

-Eli

Krzysztof Parzyszek

2012-Sep-21 21:46 UTC

head link

[LLVMdev] Alias Analysis accuracy

On 9/21/2012 4:35 PM, Welson Sun wrote:> 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];
> }
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

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

Welson Sun

2012-Sep-21 21:49 UTC

head link

[LLVMdev] Alias Analysis accuracy

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

On Fri, Sep 21, 2012 at 2:46 PM, Krzysztof Parzyszek <
kparzysz at codeaurora.org> wrote:
> On 9/21/2012 4:35 PM, Welson Sun wrote:
>
>> 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];
>> }
>>
>
> 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
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by The Linux Foundation
> ______________________________**_________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>
http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>


-- 
Welson

Phone: (408) 418-8385
Email:  welson.sun at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120921/956f5b49/attachment.html>

Possibly Parallel Threads

Search for more reasonably related threads

llvm dev - Sep 2012 - [LLVMdev] Alias Analysis accuracy

[LLVMdev] Alias Analysis accuracy

[LLVMdev] Alias Analysis accuracy

[LLVMdev] Alias Analysis accuracy

[LLVMdev] Alias Analysis accuracy

Possibly Parallel Threads