[llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Thu Apr 21 11:31:24 PDT 2016
----- 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
More information about the llvm-dev
mailing list