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

[Mikael Holmén via llvm-dev]

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
>