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

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

Eli Friedman

2012-Sep-21 22:18 UTC

[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

Welson Sun

2012-Sep-21 22:22 UTC

head link

[LLVMdev] Alias Analysis accuracy

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


On Fri, Sep 21, 2012 at 3:18 PM, Eli Friedman <eli.friedman at
gmail.com>wrote:
> 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
>


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

Arnold Schwaighofer

2012-Sep-21 22:47 UTC

head link

[LLVMdev] Alias Analysis accuracy

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.

On Fri, Sep 21, 2012 at 5:22 PM, Welson Sun <welson.sun at gmail.com>
wrote:> 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
>
>
> On Fri, Sep 21, 2012 at 3:18 PM, Eli Friedman <eli.friedman at
gmail.com>
> wrote:
>>
>> 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
>
>
>
>
> --
> Welson
>
> Phone: (408) 418-8385
> Email:  welson.sun at gmail.com
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Welson Sun

2012-Sep-21 22:49 UTC

head link

[LLVMdev] Alias Analysis accuracy

Great! That makes sense! Thank you!

On Fri, Sep 21, 2012 at 3:43 PM, Arnold Schwaighofer <
arnold.schwaighofer at gmail.com> wrote:
> 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.
>
> On Fri, Sep 21, 2012 at 5:22 PM, Welson Sun <welson.sun at gmail.com>
wrote:
> > 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
> >
>


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

Reasonably Related Threads

Search for more possibly parallel 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

Reasonably Related Threads