Mikael Holmén via llvm-dev
2016-Apr-21 08:30 UTC
[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
>
Hal Finkel via llvm-dev
2016-Apr-21 18:31 UTC
[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?
----- Original Message -----> From: "Mikael Holmén" <mikael.holmen at ericsson.com> > To: "Hal Finkel" <hfinkel at anl.gov>, "Taewook Oh" <twoh at fb.com> > Cc: "via llvm-dev" <llvm-dev at lists.llvm.org> > Sent: Thursday, April 21, 2016 3:30:03 AM > Subject: Re: [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.That's weird, and also a bug. Maybe just an off-by-one error somewhere. Please file a bug on this too! Thanks again, Hal> > 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 > > > >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Mikael Holmén via llvm-dev
2016-Apr-22 05:56 UTC
[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?
Hi, On 04/21/2016 08:31 PM, Hal Finkel wrote:> ----- Original Message ----- >> From: "Mikael Holmén" <mikael.holmen at ericsson.com> >> To: "Hal Finkel" <hfinkel at anl.gov>, "Taewook Oh" <twoh at fb.com> >> Cc: "via llvm-dev" <llvm-dev at lists.llvm.org> >> Sent: Thursday, April 21, 2016 3:30:03 AM >> Subject: Re: [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. > > That's weird, and also a bug. Maybe just an off-by-one error somewhere. Please file a bug on this too!Alright, here we go: https://llvm.org/bugs/show_bug.cgi?id=27467 Regards, Mikael> > Thanks again, > Hal > >> >> 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 >>> >> >> >