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

[Hal Finkel via llvm-dev]

----- 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 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 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160420/fa971161/attachment.html>