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

Mikael Holmén via llvm-dev llvm-dev at lists.llvm.org
Thu Apr 21 22:56:44 PDT 2016


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
>>>
>>
>>
>



More information about the llvm-dev mailing list