diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -31,6 +31,7 @@ #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" @@ -1212,13 +1213,24 @@ return AliasResult::NoAlias; if (V1Size.hasValue() && V2Size.hasValue()) { - // Try to determine whether abs(VarIndex) > 0. + // Try to determine the range of values for VarIndex. + // VarIndexRange is such that: + // (VarIndex <= -MinAbsVarIndex || MinAbsVarIndex <= VarIndex) && + // VarIndexRange.contains(VarIndex) Optional MinAbsVarIndex; + Optional VarIndexRange; if (DecompGEP1.VarIndices.size() == 1) { - // VarIndex = Scale*V. If V != 0 then abs(VarIndex) >= abs(Scale). + // VarIndex = Scale*V. const VariableGEPIndex &Var = DecompGEP1.VarIndices[0]; - if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT)) + if (isKnownNonZero(Var.V, DL, 0, &AC, Var.CxtI, DT)) { + // If V != 0 then abs(VarIndex) >= abs(Scale). MinAbsVarIndex = Var.Scale.abs(); + } + ConstantRange R = computeConstantRange(Var.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). @@ -1236,12 +1248,28 @@ // The constant offset will have added at least +/-MinAbsVarIndex to it. APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex; APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex; - // Check that an access at OffsetLo or lower, and an access at OffsetHi - // or higher both do not alias. + // We know that Offset <= OffsetLo || Offset >= OffsetHi 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.VarIndices, V1Size, V2Size, diff --git a/llvm/test/Analysis/BasicAA/assume-index-positive.ll b/llvm/test/Analysis/BasicAA/assume-index-positive.ll --- a/llvm/test/Analysis/BasicAA/assume-index-positive.ll +++ b/llvm/test/Analysis/BasicAA/assume-index-positive.ll @@ -59,9 +59,9 @@ 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: MayAlias: double* %col.ptr.2, double* %ptr +; CHECK-NEXT: NoAlias: double* %col.ptr.2, double* %ptr ; CHECK-NEXT: MayAlias: <6 x double>* %col.ptr.1, double* %col.ptr.2 -; CHECK-NEXT: MayAlias: <6 x double>* %col.ptr.2.cast, double* %ptr +; CHECK-NEXT: NoAlias: <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 new file mode 100644 --- /dev/null +++ b/llvm/test/Analysis/BasicAA/range.ll @@ -0,0 +1,178 @@ +; 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] } + +declare i32 @llvm.annotation.i32(i32, i8*, i8*, 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 +} + +!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 } diff --git a/llvm/test/Analysis/BasicAA/sequential-gep.ll b/llvm/test/Analysis/BasicAA/sequential-gep.ll --- a/llvm/test/Analysis/BasicAA/sequential-gep.ll +++ b/llvm/test/Analysis/BasicAA/sequential-gep.ll @@ -124,24 +124,24 @@ ; CHECK-LABEL: non_zero_index_simple ; CHECK: NoAlias: i32* %gep, i32* %p ; CHECK: NoAlias: i16* %gep.16, i32* %p -; CHECK: MayAlias: i32* %p, i64* %gep.64 +; CHECK: NoAlias: i32* %p, i64* %gep.64 define void @non_zero_index_simple(i32* %p, i32* %q) { - %knownnonzero = load i32, i32* %q, !range !0 - %gep = getelementptr i32, i32* %p, i32 %knownnonzero + %known_in_1_5 = load i32, i32* %q, !range !0 + %gep = getelementptr i32, i32* %p, i32 %known_in_1_5 %gep.16 = bitcast i32* %gep to i16* %gep.64 = bitcast i32* %gep to i64* ret void } ; CHECK-LABEL: non_zero_index_with_offset -; CHECK: MayAlias: i32* %gep, i32* %p +; CHECK: NoAlias: 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 + %known_in_1_5 = load i32, i32* %q, !range !0 %p.8 = bitcast i32* %p to i8* %p.off.8 = getelementptr i8, i8* %p.8, i32 2 %p.off = bitcast i8* %p.off.8 to i32* - %gep = getelementptr i32, i32* %p.off, i32 %knownnonzero + %gep = getelementptr i32, i32* %p.off, i32 %known_in_1_5 %gep.16 = bitcast i32* %gep to i16* ret void }