From ff41fc07b12bd7bf3c8cd238824b16b1066fe5a0 Mon Sep 17 00:00:00 2001 From: Clement Courbet Date: Wed, 6 Oct 2021 16:47:34 +0200 Subject: [PATCH] Revert "[AA] Teach BasicAA to recognize basic GEP range information." We have found a miscompile with this change, reverting while working on a reproducer. This reverts commit 455b60ccfbfdbb5d2b652666050544c31e6673b1. --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 36 +--- .../test/Analysis/BasicAA/assume-index-positive.ll | 4 +- llvm/test/Analysis/BasicAA/range.ll | 188 --------------------- llvm/test/Analysis/BasicAA/sequential-gep.ll | 4 +- 4 files changed, 9 insertions(+), 223 deletions(-) delete mode 100644 llvm/test/Analysis/BasicAA/range.ll diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index 4a54c33..6be3778 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -31,7 +31,6 @@ #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/Constant.h" -#include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" @@ -1317,24 +1316,13 @@ AliasResult BasicAAResult::aliasGEP( return AliasResult::NoAlias; if (V1Size.hasValue() && V2Size.hasValue()) { - // Try to determine the range of values for VarIndex. - // VarIndexRange is such that: - // (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) && - // VarIndexRange.contains(VarIndex) + // Try to determine whether abs(VarIndex) > 0. Optional MinAbsVarIndex; - Optional VarIndexRange; if (DecompGEP1.VarIndices.size() == 1) { - // VarIndex = Scale*V. + // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale). const VariableGEPIndex &Var = DecompGEP1.VarIndices[0]; - if (isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) { - // If V != 0 then abs(VarIndex) >= abs(Scale). + if (isKnownNonZero(Var.Val.V, DL, 0, &AC, Var.CxtI, DT)) MinAbsVarIndex = Var.Scale.abs(); - } - ConstantRange R = Var.Val.evaluateWith( - computeConstantRange(Var.Val.V, true, &AC, Var.CxtI)); - if (!R.isFullSet() && !R.isEmptySet()) - VarIndexRange = R.sextOrTrunc(Var.Scale.getBitWidth()) - .multiply(ConstantRange(Var.Scale)); } else if (DecompGEP1.VarIndices.size() == 2) { // VarIndex = Scale*V0 + (-Scale)*V1. // If V0 != V1 then abs(VarIndex) >= abs(Scale). @@ -1353,26 +1341,12 @@ AliasResult BasicAAResult::aliasGEP( // The constant offset will have added at least +/-MinAbsVarIndex to it. APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex; APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex; - // We know that Offset <= OffsetLo || Offset >= OffsetHi + // Check that an access at OffsetLo or lower, and an access at OffsetHi + // or higher both do not alias. if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) && OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue())) return AliasResult::NoAlias; } - - if (VarIndexRange) { - ConstantRange OffsetRange = - VarIndexRange->add(ConstantRange(DecompGEP1.Offset)); - - // We know that Offset >= MinOffset. - // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias. - if (OffsetRange.getSignedMin().sge(V2Size.getValue())) - return AliasResult::NoAlias; - - // We know that Offset <= MaxOffset. - // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias. - if (OffsetRange.getSignedMax().sle(-V1Size.getValue())) - return AliasResult::NoAlias; - } } if (constantOffsetHeuristic(DecompGEP1, V1Size, V2Size, &AC, DT)) diff --git a/llvm/test/Analysis/BasicAA/assume-index-positive.ll b/llvm/test/Analysis/BasicAA/assume-index-positive.ll index bbe7263..54eb34a 100644 --- a/llvm/test/Analysis/BasicAA/assume-index-positive.ll +++ b/llvm/test/Analysis/BasicAA/assume-index-positive.ll @@ -59,9 +59,9 @@ define void @test2(double* %ptr, i32 %skip) { define void @test3(double* %ptr, i32 %skip) { ; CHECK-LABEL: Function: test3: 4 pointers, 1 call sites ; CHECK-NEXT: MustAlias: <6 x double>* %col.ptr.1, double* %ptr -; CHECK-NEXT: NoAlias: double* %col.ptr.2, double* %ptr +; CHECK-NEXT: MayAlias: double* %col.ptr.2, double* %ptr ; CHECK-NEXT: MayAlias: <6 x double>* %col.ptr.1, double* %col.ptr.2 -; CHECK-NEXT: NoAlias: <6 x double>* %col.ptr.2.cast, double* %ptr +; CHECK-NEXT: MayAlias: <6 x double>* %col.ptr.2.cast, double* %ptr ; CHECK-NEXT: MayAlias: <6 x double>* %col.ptr.1, <6 x double>* %col.ptr.2.cast ; CHECK-NEXT: MustAlias: <6 x double>* %col.ptr.2.cast, double* %col.ptr.2 ; CHECK-NEXT: NoModRef: Ptr: double* %ptr <-> call void @llvm.assume(i1 %gt) diff --git a/llvm/test/Analysis/BasicAA/range.ll b/llvm/test/Analysis/BasicAA/range.ll deleted file mode 100644 index 5a3c09b..0000000 --- a/llvm/test/Analysis/BasicAA/range.ll +++ /dev/null @@ -1,188 +0,0 @@ -; RUN: opt < %s -basic-aa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s - -%struct.S = type { i32, [2 x i32], i32 } -%struct.S2 = type { i32, [4 x i32], [4 x i32] } - -; CHECK: Function: t1 -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @t1(%struct.S* %s) { - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1 - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0 - ret void -} - -; CHECK: Function: t2_fwd -; CHECK: MayAlias: i32* %gep1, i32* %gep2 -define void @t2_fwd(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0 - ret void -} - -; CHECK: Function: t2_rev -; CHECK: MayAlias: i32* %gep1, i32* %gep2 -define void @t2_rev(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 0 - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - ret void -} - -; CHECK: Function: t3_fwd -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @t3_fwd(%struct.S* %s, i32* %q) { - %knownzero = load i32, i32* %q, !range !1 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1 - ret void -} - -; CHECK: Function: t3_rev -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @t3_rev(%struct.S* %s, i32* %q) { - %knownzero = load i32, i32* %q, !range !1 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 1 - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %knownzero - ret void -} - -; CHECK: Function: member_after -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @member_after(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2 - ret void -} - -; CHECK: Function: member_after_rev -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @member_after_rev(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 2 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - ret void -} - -; CHECK: Function: member_before -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @member_before(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0 - ret void -} - -; CHECK: Function: member_before_rev -; CHECK: NoAlias: i32* %gep1, i32* %gep2 -define void @member_before_rev(%struct.S* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !0 - %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0 - %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1, i32 %in_array - ret void -} - -; CHECK: Function: t5 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 4): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2 -define void @t5(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !3 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 0 - ret void -} - -; CHECK: Function: t6 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 16): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2 -define void @t6(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !3 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 3 - ret void -} - -; CHECK: Function: t7 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 20): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2 -define void @t7(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !4 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 0 - ret void -} - -; CHECK: Function: t8 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 24): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2 -define void @t8(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !4 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 1 - ret void -} - -; CHECK: Function: t9 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 20): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: NoAlias: i32* %gep1, i32* %gep2 -define void @t9(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !5 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 0 - ret void -} - -; CHECK: Function: t10 -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %q -; CHECK-NEXT: MayAlias: %struct.S2* %s, i32* %gep1 -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %q -; CHECK-NEXT: PartialAlias (off 4): %struct.S2* %s, i32* %gep2 -; CHECK-NEXT: MayAlias: i32* %gep2, i32* %q -; CHECK-NEXT: MayAlias: i32* %gep1, i32* %gep2 -define void @t10(%struct.S2* %s, i32* %q) { - %in_array = load i32, i32* %q, !range !5 - %gep1 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 2, i32 %in_array - %gep2 = getelementptr inbounds %struct.S2, %struct.S2* %s, i64 0, i32 1, i32 0 - ret void -} - -; CHECK: Function: zeroext_index -; CHECK-NEXT: MayAlias: [256 x i32]* %s, i8* %q -; CHECK-NEXT: MayAlias: [256 x i32]* %s, i32* %gep -; CHECK-NEXT: MayAlias: i32* %gep, i8* %q -define void @zeroext_index([256 x i32]* %s, i8* %q) { - %a = load i8, i8* %q, !range !6 - %in_array = zext i8 %a to i32 - %gep = getelementptr inbounds [256 x i32], [256 x i32]* %s, i64 0, i32 %in_array - ret void -} - - -!0 = !{ i32 0, i32 2 } -!1 = !{ i32 0, i32 1 } -!2 = !{ i32 1, i32 2 } -!3 = !{ i32 -2, i32 0 } -!4 = !{ i32 1, i32 536870911 } -!5 = !{ i32 -536870911, i32 4 } -!6 = !{ i8 -2, i8 0 } diff --git a/llvm/test/Analysis/BasicAA/sequential-gep.ll b/llvm/test/Analysis/BasicAA/sequential-gep.ll index 27fec52..d7a1af0 100644 --- a/llvm/test/Analysis/BasicAA/sequential-gep.ll +++ b/llvm/test/Analysis/BasicAA/sequential-gep.ll @@ -134,7 +134,7 @@ define void @non_zero_index_simple(i32* %p, i32* %q) { } ; CHECK-LABEL: non_zero_index_with_offset -; CHECK: NoAlias: i32* %gep, i32* %p +; CHECK: MayAlias: i32* %gep, i32* %p ; CHECK: NoAlias: i16* %gep.16, i32* %p define void @non_zero_index_with_offset(i32* %p, i32* %q) { %knownnonzero = load i32, i32* %q, !range !0 @@ -157,4 +157,4 @@ define void @non_zero_index_assume(i32* %p, i32 %knownnonzero) { declare void @llvm.assume(i1) -!0 = !{ i32 1, i32 0 } +!0 = !{ i32 1, i32 5 } -- 2.7.4