thr3ads.net - llvm dev - [llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional? [Apr 2016]

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

Taewook Oh via llvm-dev

2016-Apr-15 20:22 UTC

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

Hello all,

I observed that BasicAA alias query returns PartialAlias between different
fields of a structure. Following is the test program and
-print–all-alias-modref-info output:

---

; test.ll
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%"type" = type { [10 x i32], i64 }

define void @test(%"type"* %base) {
entry:
  %int =       getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 1
  %arr_first = getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 0
  %arr_last =  getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 9
  %arr_oob =   getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 10 ; out-of-bound access
  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %inc, %loop ]

  %arr_index = getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 %index

  %inc = add i64 %index, 1
  %cmp = icmp ult i64 %inc, 10
  br i1 %cmp, label %loop, label %exit

exit:
  ret void
}

; opt < test.ll –basicaa -aa–eval -print-all-alias-modref-info
-disable-output

  PartialAlias: %type* %base,     i64* %int
  MustAlias:    %type* %base,     i32* %arr_first
  NoAlias:      i32* %arr_first,  i64* %int
  PartialAlias: %type*            %base, i32* %arr_last
  NoAlias:      i32* %arr_last,   i64* %int
  NoAlias:      i32* %arr_first,  i32* %arr_last
  PartialAlias: %type* %base,     i32* %arr_oob
  MustAlias:    i32* %arr_oob,    i64* %int
  NoAlias:      i32* %arr_first,  i32* %arr_oob
  NoAlias:      i32* %arr_last,   i32* %arr_oob
  PartialAlias: %type* %base,     i32* %arr_index
  PartialAlias: i32* %arr_index,  i64* %int
  PartialAlias: i32* %arr_first,  i32* %arr_index
  PartialAlias: i32* %arr_index,  i32* %arr_last
  PartialAlias: i32* %arr_index,  i32* %arr_oob
===== Alias Analysis Evaluator Report ====  15 Total Alias Queries Performed
  5 no alias responses (33.3%)
  0 may alias responses (0.0%)
  8 partial alias responses (53.3%)
  2 must alias responses (13.3%)
  Alias Analysis Evaluator Pointer Alias Summary: 33%/0%/53%/13%
  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!

---

As you can see, BasicAA query returns PartialAlias for %arr_index and %int. Does
anyone know if it is by design to be conservative in case of undefined behavior
(such as out-of-bound array access)? It seems that gcc-4.9 alias analysis tells
that there is no alias between %arr_index and %int.

Thanks,
Taewook
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160415/0795f33a/attachment.html>

Hal Finkel via llvm-dev

2016-Apr-21 02:20 UTC

head link

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

----- Original Message -----
> From: "Taewook Oh via llvm-dev" <llvm-dev at
lists.llvm.org>
> To: "via llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Friday, April 15, 2016 3:22:27 PM
> Subject: [llvm-dev] (BasicAA) PartialAlias between different fields
> of a structure, intentional?
> Hello all,
> I observed that BasicAA alias query returns PartialAlias between
> different fields of a structure. Following is the test program and
> -print–all-alias-modref-info output:
> ---
> ; test.ll
> target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
> target triple = "x86_64-unknown-linux-gnu"
> %"type" = type { [10 x i32], i64 }
> define void @test(%"type"* %base) {
> entry:
> %int = getelementptr inbounds %"type", %"type"* %base,
i64 0, i32 1
> %arr_first = getelementptr inbounds %"type", %"type"*
%base, i64 0,
> i32 0, i64 0
> %arr_last = getelementptr inbounds %"type", %"type"*
%base, i64 0,
> i32 0, i64 9
> %arr_oob = getelementptr inbounds %"type", %"type"*
%base, i64 0, i32
> 0, i64 10 ; out-of-bound accessThis is okay. Even for an inbounds GEP, addressing one-past-the-end of the array
is allowed.
> br label %loop
> loop:
> %index = phi i64 [ 0, %entry ], [ %inc, %loop ]
> %arr_index = getelementptr inbounds %"type", %"type"*
%base, i64 0,
> i32 0, i64 %index
> %inc = add i64 %index, 1
> %cmp = icmp ult i64 %inc, 10
> br i1 %cmp, label %loop, label %exit
> exit:
> ret void
> }
> ; opt < test.ll –basicaa -aa–eval -print-all-alias-modref-info
> -disable-output
> PartialAlias: %type* %base, i64* %int
> MustAlias: %type* %base, i32* %arr_first
> NoAlias: i32* %arr_first, i64* %int
> PartialAlias: %type* %base, i32* %arr_last
> NoAlias: i32* %arr_last, i64* %int
> NoAlias: i32* %arr_first, i32* %arr_last
> PartialAlias: %type* %base, i32* %arr_oob
> MustAlias: i32* %arr_oob, i64* %int
> NoAlias: i32* %arr_first, i32* %arr_oob
> NoAlias: i32* %arr_last, i32* %arr_oob
> PartialAlias: %type* %base, i32* %arr_index
> PartialAlias: i32* %arr_index, i64* %int
> PartialAlias: i32* %arr_first, i32* %arr_index
> PartialAlias: i32* %arr_index, i32* %arr_last
> PartialAlias: i32* %arr_index, i32* %arr_oob
> ===== Alias Analysis Evaluator Report ====> 15 Total Alias Queries
Performed
> 5 no alias responses (33.3%)
> 0 may alias responses (0.0%)
> 8 partial alias responses (53.3%)
> 2 must alias responses (13.3%)
> Alias Analysis Evaluator Pointer Alias Summary: 33%/0%/53%/13%
> Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!
> ---
> As you can see, BasicAA query returns PartialAlias for %arr_index and
> %int. Does anyone know if it is by design to be conservative in case
> of undefined behavior (such as out-of-bound array access)? It seems
> that gcc-4.9 alias analysis tells that there is no alias between
> %arr_index and %int.Please file a bug report: 

1. This is a correctness bug because the result should not be PartialAlias, but
MayAlias. PartialAlias should be returned only in cases where we can prove there
is a partial overlap. In this case, we can't.

2. We're also missing an analysis opportunity here. We should be able to
prove that %index is never greater than 9, which should be enough to provide a
NoAlias result.

As a test, you might try running with -scev-aa and see if that gets this case. 

-Hal 
> Thanks,
> Taewook
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/fa971161/attachment.html>

Mikael Holmén via llvm-dev

2016-Apr-21 08:30 UTC

head link

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

Hi,

We've seen a similar case recently, where BasicAA returns PartialAlias 
for the access of two different fields of a structure.

We noticed this since Lint complained about it when checking for 
aliasing beteen "noalias" attributed parameters:

opt -S -lint ./alias.ll

gave

Unusual: noalias argument aliases another argument

on the (silly) function:

%rec7 = type { i16, i16, i16 }

define void @fn1(i16* noalias %p1.1.par, i16* noalias %p2.2.par) {
%s.3 = alloca %rec7
%_tmp1 = getelementptr %rec7, %rec7* %s.3, i16 0, i32 1
%_tmp2 = getelementptr %rec7, %rec7* %s.3, i16 0, i32 2
call void @fn1(i16* %_tmp1, i16* %_tmp2)

ret void
}

If accessing fields 0 and 1 instead, with

%_tmp1 = getelementptr %rec7, %rec7* %s.3, i16 0, i32 0
%_tmp2 = getelementptr %rec7, %rec7* %s.3, i16 0, i32 1

we don't see the Lint complaint.

Regards,
Mikael

On 04/21/2016 04:20 AM, Hal Finkel via llvm-dev wrote:>
> ------------------------------------------------------------------------
>
>     *From: *"Taewook Oh via llvm-dev" <llvm-dev at
lists.llvm.org>
>     *To: *"via llvm-dev" <llvm-dev at lists.llvm.org>
>     *Sent: *Friday, April 15, 2016 3:22:27 PM
>     *Subject: *[llvm-dev] (BasicAA) PartialAlias between different
>     fields of a structure, intentional?
>
>     Hello all,
>
>     I observed that BasicAA alias query returns PartialAlias between
>     different fields of a structure. Following is the test program and
>     -print–all-alias-modref-info output:
>
>     ---
>
>     ; test.ll
>     target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
>     target triple = "x86_64-unknown-linux-gnu"
>
>     %"type" = type { [10 x i32], i64 }
>
>     define void @test(%"type"* %base) {
>     entry:
>        %int =       getelementptr inbounds %"type",
%"type"* %base, i64
>     0, i32 1
>        %arr_first = getelementptr inbounds %"type",
%"type"* %base, i64
>     0, i32 0, i64 0
>        %arr_last =  getelementptr inbounds %"type",
%"type"* %base, i64
>     0, i32 0, i64 9
>        %arr_oob =   getelementptr inbounds %"type",
%"type"* %base, i64
>     0, i32 0, i64 10 ; out-of-bound access
>
> This is okay. Even for an inbounds GEP, addressing one-past-the-end of
> the array is allowed.
>
>        br label %loop
>
>     loop:
>        %index = phi i64 [ 0, %entry ], [ %inc, %loop ]
>
>        %arr_index = getelementptr inbounds %"type",
%"type"* %base, i64
>     0, i32 0, i64 %index
>
>        %inc = add i64 %index, 1
>        %cmp = icmp ult i64 %inc, 10
>        br i1 %cmp, label %loop, label %exit
>
>     exit:
>        ret void
>     }
>
>     ; opt < test.ll –basicaa -aa–eval -print-all-alias-modref-info
>     -disable-output
>
>        PartialAlias: %type* %base,     i64* %int
>        MustAlias:    %type* %base,     i32* %arr_first
>        NoAlias:      i32* %arr_first,  i64* %int
>        PartialAlias: %type*            %base, i32* %arr_last
>        NoAlias:      i32* %arr_last,   i64* %int
>        NoAlias:      i32* %arr_first,  i32* %arr_last
>        PartialAlias: %type* %base,     i32* %arr_oob
>        MustAlias:    i32* %arr_oob,    i64* %int
>        NoAlias:      i32* %arr_first,  i32* %arr_oob
>        NoAlias:      i32* %arr_last,   i32* %arr_oob
>        PartialAlias: %type* %base,     i32* %arr_index
>        PartialAlias: i32* %arr_index,  i64* %int
>        PartialAlias: i32* %arr_first,  i32* %arr_index
>        PartialAlias: i32* %arr_index,  i32* %arr_last
>        PartialAlias: i32* %arr_index,  i32* %arr_oob
>     ===== Alias Analysis Evaluator Report ====>        15 Total Alias
Queries Performed
>        5 no alias responses (33.3%)
>        0 may alias responses (0.0%)
>        8 partial alias responses (53.3%)
>        2 must alias responses (13.3%)
>        Alias Analysis Evaluator Pointer Alias Summary: 33%/0%/53%/13%
>        Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!
>
>     ---
>
>     As you can see, BasicAA query returns PartialAlias for %arr_index
>     and %int. Does anyone know if it is by design to be conservative in
>     case of undefined behavior (such as out-of-bound array access)? It
>     seems that gcc-4.9 alias analysis tells that there is no alias
>     between %arr_index and %int.
>
> Please file a bug report:
>
>   1. This is a correctness bug because the result should not be
> PartialAlias, but MayAlias. PartialAlias should be returned only in
> cases where we can prove there is a partial overlap. In this case, we
can't.
>
>   2. We're also missing an analysis opportunity here. We should be able
> to prove that %index is never greater than 9, which should be enough to
> provide a NoAlias result.
>
> As a test, you might try running with -scev-aa and see if that gets this
> case.
>
>   -Hal
>
>
>     Thanks,
>     Taewook
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Taewook Oh via llvm-dev

2016-Apr-22 15:13 UTC

head link

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

Thanks for comments. Here's the bug report:
https://llvm.org/bugs/show_bug.cgi?id=27478

From: Hal Finkel <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>
Date: Wednesday, April 20, 2016 at 9:20 PM
To: Taewook Oh <twoh at fb.com<mailto:twoh at fb.com>>
Cc: via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>
Subject: Re: [llvm-dev] (BasicAA) PartialAlias between different fields of a
structure, intentional?

________________________________
From: "Taewook Oh via llvm-dev" <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
To: "via llvm-dev" <llvm-dev at lists.llvm.org<mailto:llvm-dev
at lists.llvm.org>>
Sent: Friday, April 15, 2016 3:22:27 PM
Subject: [llvm-dev] (BasicAA) PartialAlias between different fields of a
structure, intentional?

Hello all,

I observed that BasicAA alias query returns PartialAlias between different
fields of a structure. Following is the test program and
-print–all-alias-modref-info output:

---

; test.ll
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%"type" = type { [10 x i32], i64 }

define void @test(%"type"* %base) {
entry:
  %int =       getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 1
  %arr_first = getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 0
  %arr_last =  getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 9
  %arr_oob =   getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 10 ; out-of-bound access
This is okay. Even for an inbounds GEP, addressing one-past-the-end of the array
is allowed.

  br label %loop

loop:
  %index = phi i64 [ 0, %entry ], [ %inc, %loop ]

  %arr_index = getelementptr inbounds %"type", %"type"*
%base, i64 0, i32 0, i64 %index

  %inc = add i64 %index, 1
  %cmp = icmp ult i64 %inc, 10
  br i1 %cmp, label %loop, label %exit

exit:
  ret void
}

; opt < test.ll –basicaa -aa–eval -print-all-alias-modref-info
-disable-output

  PartialAlias: %type* %base,     i64* %int
  MustAlias:    %type* %base,     i32* %arr_first
  NoAlias:      i32* %arr_first,  i64* %int
  PartialAlias: %type*            %base, i32* %arr_last
  NoAlias:      i32* %arr_last,   i64* %int
  NoAlias:      i32* %arr_first,  i32* %arr_last
  PartialAlias: %type* %base,     i32* %arr_oob
  MustAlias:    i32* %arr_oob,    i64* %int
  NoAlias:      i32* %arr_first,  i32* %arr_oob
  NoAlias:      i32* %arr_last,   i32* %arr_oob
  PartialAlias: %type* %base,     i32* %arr_index
  PartialAlias: i32* %arr_index,  i64* %int
  PartialAlias: i32* %arr_first,  i32* %arr_index
  PartialAlias: i32* %arr_index,  i32* %arr_last
  PartialAlias: i32* %arr_index,  i32* %arr_oob
===== Alias Analysis Evaluator Report ====  15 Total Alias Queries Performed
  5 no alias responses (33.3%)
  0 may alias responses (0.0%)
  8 partial alias responses (53.3%)
  2 must alias responses (13.3%)
  Alias Analysis Evaluator Pointer Alias Summary: 33%/0%/53%/13%
  Alias Analysis Mod/Ref Evaluator Summary: no mod/ref!

---

As you can see, BasicAA query returns PartialAlias for %arr_index and %int. Does
anyone know if it is by design to be conservative in case of undefined behavior
(such as out-of-bound array access)? It seems that gcc-4.9 alias analysis tells
that there is no alias between %arr_index and %int.
Please file a bug report:

 1. This is a correctness bug because the result should not be PartialAlias, but
MayAlias. PartialAlias should be returned only in cases where we can prove there
is a partial overlap. In this case, we can't.

 2. We're also missing an analysis opportunity here. We should be able to
prove that %index is never greater than 9, which should be enough to provide a
NoAlias result.

As a test, you might try running with -scev-aa and see if that gets this case.

 -Hal

Thanks,
Taewook

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160422/e8bd9fb8/attachment.html>

Reasonably Related Threads

Search for more apparently analagous threads

llvm dev - Apr 2016 - (BasicAA) PartialAlias between different fields of a structure, intentional?

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?

Reasonably Related Threads