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:57 UTC

[LLVMdev] Alias Analysis accuracy

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

On Fri, Sep 21, 2012 at 2:52 PM, Liu, Yaxun (Sam) <Yaxun.Liu at amd.com>
wrote:
>  I think you may add restrict type qualifier.****
>
> ** **
>
> Sam****
>
> ** **
>
> *From:* llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu] *On
> Behalf Of *Welson Sun
> *Sent:* Friday, September 21, 2012 5:50 PM
> *To:* Krzysztof Parzyszek
> *Cc:* llvmdev at cs.uiuc.edu
> *Subject:* Re: [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****
>
>
>
> ****
>
> ** **
>
> --
> Welson****
>
> ** **
>
> Phone: (408) 418-8385****
>
> Email:  welson.sun at gmail.com****
>
> ** **
>
> ** **
>


-- 
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/e443bd98/attachment.html>

Welson Sun

2012-Sep-21 22:08 UTC

head link

[LLVMdev] Alias Analysis accuracy

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?


On Fri, Sep 21, 2012 at 2:57 PM, Welson Sun <welson.sun at gmail.com>
wrote:
> Can you give an example? And is this limited to C (not C++) only?
>
>
> On Fri, Sep 21, 2012 at 2:52 PM, Liu, Yaxun (Sam) <Yaxun.Liu at
amd.com>wrote:
>
>>  I think you may add restrict type qualifier.****
>>
>> ** **
>>
>> Sam****
>>
>> ** **
>>
>> *From:* llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at
cs.uiuc.edu]
>> *On Behalf Of *Welson Sun
>> *Sent:* Friday, September 21, 2012 5:50 PM
>> *To:* Krzysztof Parzyszek
>> *Cc:* llvmdev at cs.uiuc.edu
>> *Subject:* Re: [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****
>>
>>
>>
>> ****
>>
>> ** **
>>
>> --
>> Welson****
>>
>> ** **
>>
>> Phone: (408) 418-8385****
>>
>> Email:  welson.sun at gmail.com****
>>
>> ** **
>>
>> ** **
>>
>
>
>
> --
> Welson
>
> Phone: (408) 418-8385
> Email:  welson.sun at gmail.com
>
>
>

-- 
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/4b223997/attachment.html>

Krzysztof Parzyszek

2012-Sep-21 22:16 UTC

head link

[LLVMdev] Alias Analysis accuracy

On 9/21/2012 5:08 PM, Welson Sun wrote:> OK, with the restrict type qualifier, it is a little bit better:
>
> 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?
What is %0?  Can you paste the whole IR for foo?

-K

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

Eli Friedman

2012-Sep-21 22:18 UTC

head link

[LLVMdev] Alias Analysis accuracy

On Fri, Sep 21, 2012 at 3:08 PM, Welson Sun <welson.sun at gmail.com>
wrote:> 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?
No.  Try running mem2reg.

-Eli

Apparently Analagous Threads

Search for more apparently analagous 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

Apparently Analagous Threads