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:
From: "Taewook Oh via llvm-dev" <llvm-dev@lists.llvm.org>
To: "via llvm-dev" <llvm-dev@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
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
From: "Mikael Holmén" <mikael.holmen@ericsson.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "Taewook Oh" <twoh@fb.com>
Cc: "via llvm-dev" <llvm-dev@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 1we 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
Hi,
From: "Mikael Holmén" <mikael.holmen@ericsson.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "Taewook Oh" <twoh@fb.com>
Cc: "via llvm-dev" <llvm-dev@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 1we 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