From 9bc7e543b4ef5eef2be2325204db20073fc18e36 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Mon, 25 Oct 2021 18:47:51 +0200 Subject: [PATCH] [BasicAA] Make range check more precise Make the range check more precise by calculating the range of potentially accessed bytes for both accesses and checking whether their intersection is empty. In that case there can be no overlap between the accesses and the result is NoAlias. This is more powerful than the previous approach, because it can deal with sign-wrapped ranges. In the test case the original range is [-1, INT_MAX] but becomes [0, INT_MIN] after applying the offset. This is a wrapping range, so getSignedMin/getSignedMax will treat it as a full range. However, the range excludes the elements [INT_MIN+1, -1], which is enough to prove NoAlias with an access at offset -1. Differential Revision: https://reviews.llvm.org/D112486 --- llvm/lib/Analysis/BasicAliasAnalysis.cpp | 26 +++++++++++++------------- llvm/test/Analysis/BasicAA/range.ll | 4 ++-- 2 files changed, 15 insertions(+), 15 deletions(-) diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index f0e5d65..0305732 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1252,7 +1252,7 @@ AliasResult BasicAAResult::aliasGEP( APInt GCD; bool AllNonNegative = DecompGEP1.Offset.isNonNegative(); bool AllNonPositive = DecompGEP1.Offset.isNonPositive(); - ConstantRange Range = ConstantRange(DecompGEP1.Offset); + ConstantRange OffsetRange = ConstantRange(DecompGEP1.Offset); for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { const VariableGEPIndex &Index = DecompGEP1.VarIndices[i]; const APInt &Scale = Index.Scale; @@ -1277,12 +1277,12 @@ AliasResult BasicAAResult::aliasGEP( (SignKnownOne && Scale.isNonNegative()); } - assert(Range.getBitWidth() == Scale.getBitWidth() && + assert(OffsetRange.getBitWidth() == Scale.getBitWidth() && "Bit widths are normalized to MaxPointerSize"); - Range = Range.add(Index.Val + OffsetRange = OffsetRange.add(Index.Val .evaluateWith(computeConstantRange( Index.Val.V, true, &AC, Index.CxtI)) - .sextOrTrunc(Range.getBitWidth()) + .sextOrTrunc(OffsetRange.getBitWidth()) .smul_fast(ConstantRange(Scale))); } @@ -1315,15 +1315,15 @@ AliasResult BasicAAResult::aliasGEP( (-DecompGEP1.Offset).uge(V1Size.getValue())) return AliasResult::NoAlias; - if (!Range.isEmptySet()) { - // We know that Offset >= MinOffset. - // (MinOffset >= V2Size) => (Offset >= V2Size) => NoAlias. - if (V2Size.hasValue() && Range.getSignedMin().sge(V2Size.getValue())) - return AliasResult::NoAlias; - - // We know that Offset <= MaxOffset. - // (MaxOffset <= -V1Size) => (Offset <= -V1Size) => NoAlias. - if (V1Size.hasValue() && Range.getSignedMax().sle(-V1Size.getValue())) + if (V1Size.hasValue() && V2Size.hasValue()) { + // Compute ranges of potentially accessed bytes for both accesses. If the + // interseciton is empty, there can be no overlap. + unsigned BW = OffsetRange.getBitWidth(); + ConstantRange Range1 = OffsetRange.add( + ConstantRange(APInt(BW, 0), APInt(BW, V1Size.getValue()))); + ConstantRange Range2 = + ConstantRange(APInt(BW, 0), APInt(BW, V2Size.getValue())); + if (Range1.intersectWith(Range2).isEmptySet()) return AliasResult::NoAlias; } diff --git a/llvm/test/Analysis/BasicAA/range.ll b/llvm/test/Analysis/BasicAA/range.ll index 6bdb7cc..8953320 100644 --- a/llvm/test/Analysis/BasicAA/range.ll +++ b/llvm/test/Analysis/BasicAA/range.ll @@ -196,13 +196,13 @@ define void @multiple(i32* %p, i32* %o1_ptr, i32* %o2_ptr) { ret void } -; TODO: p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow. +; p.neg1 and p.o.1 don't alias, even though the addition o+1 may overflow. ; While it makes INT_MIN a possible offset, offset -1 is not possible. ; CHECK-LABEL: Function: benign_overflow ; CHECK: MayAlias: i8* %p, i8* %p.o ; CHECK: MayAlias: i8* %p.neg1, i8* %p.o ; CHECK: MayAlias: i8* %p, i8* %p.o.1 -; CHECK: MayAlias: i8* %p.neg1, i8* %p.o.1 +; CHECK: NoAlias: i8* %p.neg1, i8* %p.o.1 ; CHECK: NoAlias: i8* %p.o, i8* %p.o.1 define void @benign_overflow(i8* %p, i64 %o) { %c = icmp sge i64 %o, -1 -- 2.7.4