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

[Taewook Oh via llvm-dev]

Thanks for comments. Here's the bug report: https://llvm.org/bugs/show_bug.cgi?id=27478

From: Hal Finkel <hfinkel at anl.gov<mailto:hfinkel at anl.gov>>
Date: Wednesday, April 20, 2016 at 9:20 PM
To: Taewook Oh <twoh at fb.com<mailto:twoh at fb.com>>
Cc: via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
Subject: Re: [llvm-dev] (BasicAA) PartialAlias between different fields of a structure, intentional?


________________________________
From: "Taewook Oh via llvm-dev" <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>
To: "via llvm-dev" <llvm-dev at lists.llvm.org<mailto: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<mailto: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/20160422/e8bd9fb8/attachment.html>