[DependenceAnalysis] Fix incorrect analysis of wrapping AddRec expressions #154982
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
@llvm/pr-subscribers-llvm-transforms @llvm/pr-subscribers-llvm-analysis Author: Sebastian Pop (sebpop) ChangesFixes GitHub issue #148435 where {false,+,true} patterns reported The issue occurs when AddRec expressions in narrow types create cyclic The fix detects potential wrapping by checking if step × iteration_count Add wrapping detection in checkSubscript() with fallback to exact and max Patch is 21.09 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/154982.diff 7 Files Affected:
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index 167845ce646b9..1f84ce991fdfc 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1337,6 +1337,11 @@ class ScalarEvolution {
/// sharpen it.
LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags);
+ /// Check if this AddRec expression may wrap, making it non-affine.
+ /// Wrapping AddRecs create cyclic patterns that violate linearity assumptions.
+ /// Returns true if definitely wraps, false if definitely safe, nullopt if unknown.
+ LLVM_ABI std::optional<bool> mayAddRecWrap(const SCEVAddRecExpr *AddRec);
+
class LoopGuards {
DenseMap<const SCEV *, const SCEV *> RewriteMap;
bool PreserveNUW = false;
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index f33e04e804e3d..e9e568227bf43 100644
--- a/llvm/lib/Analysis/DependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/DependenceAnalysis.cpp
@@ -873,6 +873,9 @@ void DependenceInfo::collectCommonLoops(const SCEV *Expression,
SmallBitVector &Loops) const {
while (LoopNest) {
unsigned Level = LoopNest->getLoopDepth();
+ LLVM_DEBUG(dbgs() << "MaxLevels = " << MaxLevels << "\n");
+ LLVM_DEBUG(dbgs() << "Level = " << Level << "\n");
+ assert(Level <= MaxLevels && "Level larger than MaxLevels.");
if (Level <= CommonLevels && !SE->isLoopInvariant(Expression, LoopNest))
Loops.set(Level);
LoopNest = LoopNest->getParentLoop();
@@ -959,6 +962,25 @@ bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
if (!AddRec)
return isLoopInvariant(Expr, LoopNest);
+ const SCEV *Step = AddRec->getStepRecurrence(*SE);
+ if (!isLoopInvariant(Step, LoopNest))
+ return false;
+
+ // Check if this AddRec expression may wrap, making it non-affine.
+ std::optional<bool> MayWrap = SE->mayAddRecWrap(AddRec);
+ // Conservative: reject if unknown or definitely wraps.
+ if (MayWrap.value_or(true)) {
+ Type *Ty = AddRec->getType();
+ unsigned BitWidth = Ty->getScalarSizeInBits();
+ // Domain-specific knowledge for array access functions: wider types are
+ // extremely unlikely to wrap because having an array allocated with more
+ // than 2^32 bytes (such that we can observe the wrap-around without causing
+ // undefined behavior from out-of-bounds access) is not realistic.
+ if (BitWidth <= 32)
+ // Types with bit width shorter than 32 may wrap.
+ return false;
+ }
+
// The AddRec must depend on one of the containing loops. Otherwise,
// mapSrcLoop and mapDstLoop return indices outside the intended range. This
// can happen when a subscript in one loop references an IV from a sibling
@@ -970,14 +992,16 @@ bool DependenceInfo::checkSubscript(const SCEV *Expr, const Loop *LoopNest,
if (!L)
return false;
+ unsigned Level = IsSrc ? mapSrcLoop(L) : mapDstLoop(L);
+ // Check that the mapped loop index is within bounds for the SmallBitVector.
+ // This can happen when loop depths exceed MaxLevels due to the mapping
+ // algorithm.
+
+ LLVM_DEBUG(dbgs() << "MaxLevels = " << MaxLevels << "\n");
+ LLVM_DEBUG(dbgs() << "Level = " << Level << "\n");
+ assert(Level <= MaxLevels && "Level larger than MaxLevels.");
+ Loops.set(Level);
const SCEV *Start = AddRec->getStart();
- const SCEV *Step = AddRec->getStepRecurrence(*SE);
- if (!isLoopInvariant(Step, LoopNest))
- return false;
- if (IsSrc)
- Loops.set(mapSrcLoop(AddRec->getLoop()));
- else
- Loops.set(mapDstLoop(AddRec->getLoop()));
return checkSubscript(Start, LoopNest, Loops, IsSrc);
}
@@ -2281,8 +2305,14 @@ bool DependenceInfo::testSIV(const SCEV *Src, const SCEV *Dst, unsigned &Level,
Result, NewConstraint) ||
gcdMIVtest(Src, Dst, Result);
}
- llvm_unreachable("SIV test expected at least one AddRec");
- return false;
+ // If neither expression is an AddRec, this means propagation has simplified
+ // them to non-AddRec forms. In this case, fall back to ZIV analysis since
+ // the expressions are effectively loop-invariant.
+ LLVM_DEBUG(dbgs() << " falling back to ZIV test due to no AddRec\n");
+ // Set to first valid level to avoid Level=0 causing DV[-1] access.
+ // See comment in establishNestingLevels.
+ Level = 1;
+ return testZIV(Src, Dst, Result);
}
// testRDIV -
@@ -2343,8 +2373,13 @@ bool DependenceInfo::testRDIV(const SCEV *Src, const SCEV *Dst,
SrcLoop = DstAddRec->getLoop();
} else
llvm_unreachable("RDIV reached by surprising SCEVs");
- } else
- llvm_unreachable("RDIV expected at least one AddRec");
+ } else {
+ // If neither expression is an AddRec, this means propagation has simplified
+ // them to non-AddRec forms. Fall back to ZIV analysis since the expressions
+ // are effectively loop-invariant.
+ LLVM_DEBUG(dbgs() << " RDIV falling back to ZIV test due to no AddRec\n");
+ return testZIV(Src, Dst, Result);
+ }
return exactRDIVtest(SrcCoeff, DstCoeff, SrcConst, DstConst, SrcLoop, DstLoop,
Result) ||
gcdMIVtest(Src, Dst, Result) ||
@@ -3821,7 +3856,7 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst,
break;
case Subscript::SIV: {
LLVM_DEBUG(dbgs() << ", SIV\n");
- unsigned Level;
+ unsigned Level = 0;
const SCEV *SplitIter = nullptr;
if (testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
SplitIter))
@@ -3872,12 +3907,17 @@ DependenceInfo::depends(Instruction *Src, Instruction *Dst,
for (unsigned SJ : Sivs.set_bits()) {
LLVM_DEBUG(dbgs() << "testing subscript " << SJ << ", SIV\n");
// SJ is an SIV subscript that's part of the current coupled group
- unsigned Level;
+ unsigned Level = 0;
const SCEV *SplitIter = nullptr;
LLVM_DEBUG(dbgs() << "SIV\n");
if (testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
SplitIter))
return nullptr;
+
+ LLVM_DEBUG(dbgs() << "MaxLevels = " << MaxLevels << "\n");
+ LLVM_DEBUG(dbgs() << "Level = " << Level << "\n");
+ assert(Level <= MaxLevels && "Level larger than MaxLevels.");
+
ConstrainedLevels.set(Level);
if (intersectConstraints(&Constraints[Level], &NewConstraint)) {
if (Constraints[Level].isEmpty()) {
@@ -4155,7 +4195,7 @@ const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
for (unsigned SI : Separable.set_bits()) {
switch (Pair[SI].Classification) {
case Subscript::SIV: {
- unsigned Level;
+ unsigned Level = 0;
const SCEV *SplitIter = nullptr;
(void)testSIV(Pair[SI].Src, Pair[SI].Dst, Level, Result, NewConstraint,
SplitIter);
@@ -4195,12 +4235,17 @@ const SCEV *DependenceInfo::getSplitIteration(const Dependence &Dep,
bool Changed = false;
for (unsigned SJ : Sivs.set_bits()) {
// SJ is an SIV subscript that's part of the current coupled group
- unsigned Level;
+ unsigned Level = 0;
const SCEV *SplitIter = nullptr;
(void)testSIV(Pair[SJ].Src, Pair[SJ].Dst, Level, Result, NewConstraint,
SplitIter);
if (Level == SplitLevel && SplitIter)
return SplitIter;
+
+ LLVM_DEBUG(dbgs() << "MaxLevels = " << MaxLevels << "\n");
+ LLVM_DEBUG(dbgs() << "Level = " << Level << "\n");
+ assert(Level <= MaxLevels && "Level larger than MaxLevels.");
+
ConstrainedLevels.set(Level);
if (intersectConstraints(&Constraints[Level], &NewConstraint))
Changed = true;
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index d2c445f1ffaa0..3508d0d3b64aa 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -6439,6 +6439,127 @@ void ScalarEvolution::setNoWrapFlags(SCEVAddRecExpr *AddRec,
}
}
+std::optional<bool>
+ScalarEvolution::mayAddRecWrap(const SCEVAddRecExpr *AddRec) {
+ Type *Ty = AddRec->getType();
+
+ // Pointer AddRec expressions do not wrap in the arithmetic sense.
+ if (Ty->isPointerTy())
+ return false;
+
+ // Step 1: Check existing no-wrap flags from SCEV construction.
+ if (AddRec->hasNoSelfWrap() || AddRec->hasNoUnsignedWrap() ||
+ AddRec->hasNoSignedWrap()) {
+ LLVM_DEBUG(dbgs() << "\t\tAddRec has no-wrap flags: " << *AddRec << "\n");
+ return false;
+ }
+
+ // Step 2: Try to prove no-wrap using constant range analysis.
+ // Uses the same logic as proveNoWrapViaConstantRanges.
+ if (AddRec->isAffine()) {
+ const Loop *Loop = AddRec->getLoop();
+ const SCEV *BECount = getConstantMaxBackedgeTakenCount(Loop);
+ if (const SCEVConstant *BECountMax = dyn_cast<SCEVConstant>(BECount)) {
+ ConstantRange StepCR = getSignedRange(AddRec->getStepRecurrence(*this));
+ const APInt &BECountAP = BECountMax->getAPInt();
+ unsigned NoOverflowBitWidth =
+ BECountAP.getActiveBits() + StepCR.getMinSignedBits();
+ if (NoOverflowBitWidth <= getTypeSizeInBits(AddRec->getType())) {
+ LLVM_DEBUG(dbgs() << "\t\tConstant range analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+ }
+ }
+
+ // Step 3: Try to prove using signed/unsigned range containment.
+ // Uses the range containment checks from proveNoWrapViaConstantRanges.
+ if (AddRec->isAffine()) {
+ using OBO = OverflowingBinaryOperator;
+
+ // Check unsigned wrap.
+ ConstantRange AddRecRange = getUnsignedRange(AddRec);
+ ConstantRange IncRange = getUnsignedRange(AddRec->getStepRecurrence(*this));
+
+ auto NUWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+ Instruction::Add, IncRange, OBO::NoUnsignedWrap);
+ if (NUWRegion.contains(AddRecRange)) {
+ LLVM_DEBUG(dbgs() << "\t\tUnsigned range analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+
+ // Check signed wrap.
+ ConstantRange SignedAddRecRange = getSignedRange(AddRec);
+ ConstantRange SignedIncRange =
+ getSignedRange(AddRec->getStepRecurrence(*this));
+
+ auto NSWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+ Instruction::Add, SignedIncRange, OBO::NoSignedWrap);
+ if (NSWRegion.contains(SignedAddRecRange)) {
+ LLVM_DEBUG(dbgs() << "\t\tSigned range analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+ }
+
+ // Step 4: Try induction-based proving methods.
+ // Call the existing sophisticated analysis methods.
+ SCEV::NoWrapFlags ProvenFlags = proveNoWrapViaConstantRanges(AddRec);
+ if (hasFlags(ProvenFlags, SCEV::FlagNW) ||
+ hasFlags(ProvenFlags, SCEV::FlagNUW) ||
+ hasFlags(ProvenFlags, SCEV::FlagNSW)) {
+ LLVM_DEBUG(dbgs() << "\t\tAdvanced constant range analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+
+ ProvenFlags = proveNoSignedWrapViaInduction(AddRec);
+ if (hasFlags(ProvenFlags, SCEV::FlagNSW)) {
+ LLVM_DEBUG(dbgs() << "\t\tSigned induction analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+
+ ProvenFlags = proveNoUnsignedWrapViaInduction(AddRec);
+ if (hasFlags(ProvenFlags, SCEV::FlagNUW)) {
+ LLVM_DEBUG(dbgs() << "\t\tUnsigned induction analysis proves no-wrap: "
+ << *AddRec << "\n");
+ return false;
+ }
+
+ // Step 5: Fallback to explicit step * iteration calculation for narrow types.
+ const SCEV *Step = AddRec->getStepRecurrence(*this);
+ const SCEVConstant *ConstStep = dyn_cast<SCEVConstant>(Step);
+ if (!ConstStep)
+ return std::nullopt;
+
+ const Loop *Loop = AddRec->getLoop();
+ if (!hasLoopInvariantBackedgeTakenCount(Loop))
+ return std::nullopt;
+
+ const SCEV *BTC = getBackedgeTakenCount(Loop);
+ const SCEVConstant *ConstBTC = dyn_cast<SCEVConstant>(BTC);
+ if (!ConstBTC)
+ return std::nullopt;
+
+ // Explicit calculation: will step * iterations exceed type range?
+ APInt StepVal = ConstStep->getAPInt();
+ APInt BTCVal = ConstBTC->getAPInt();
+
+ bool Overflow = false;
+ APInt Product = StepVal.zext(64).umul_ov(BTCVal.zext(64), Overflow);
+
+ unsigned BitWidth = Ty->getScalarSizeInBits();
+ if (Overflow || Product.getZExtValue() >= (1ULL << BitWidth)) {
+ LLVM_DEBUG(dbgs() << "\t\tExplicit calculation proves wrapping: " << *AddRec
+ << "\n");
+ return true;
+ }
+
+ return false;
+}
+
ConstantRange ScalarEvolution::
getRangeForUnknownRecurrence(const SCEVUnknown *U) {
const DataLayout &DL = getDataLayout();
diff --git a/llvm/test/Analysis/DependenceAnalysis/PR148435.ll b/llvm/test/Analysis/DependenceAnalysis/PR148435.ll
new file mode 100644
index 0000000000000..30ade36b03fc0
--- /dev/null
+++ b/llvm/test/Analysis/DependenceAnalysis/PR148435.ll
@@ -0,0 +1,94 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -disable-output "-passes=print<da>" 2>&1 | FileCheck %s
+
+; Test case for bug #148435 - SIV test assertion failure.
+; This test ensures that testSIV handles the case where neither Src nor Dst
+; expressions contain AddRec after propagation, which can happen when
+; constraints simplify the expressions to non-AddRec forms.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-Fn32"
+target triple = "aarch64-unknown-linux-gnu"
+
+define void @_Z1cb(ptr %a) {
+; CHECK-LABEL: '_Z1cb'
+; CHECK-NEXT: Src: store i8 0, ptr %arrayidx9, align 1 --> Dst: store i8 0, ptr %arrayidx9, align 1
+; CHECK-NEXT: da analyze - output [*]!
+;
+entry:
+ br label %for.body
+
+for.cond.cleanup.loopexit: ; preds = %for.body
+ ret void
+
+for.body: ; preds = %for.body, %entry
+ %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for.body ]
+ %idxprom = and i64 %indvars.iv23, 1
+ %arrayidx9 = getelementptr inbounds [0 x [12 x [12 x i8]]], ptr %a, i64 0, i64 %idxprom, i64 0, i64 %indvars.iv23
+ store i8 0, ptr %arrayidx9, align 1
+ %indvars.iv.next24 = add i64 %indvars.iv23, 1
+ %exitcond.not = icmp eq i64 %indvars.iv.next24, 0
+ br i1 %exitcond.not, label %for.cond.cleanup.loopexit, label %for.body
+}
+
+@a = external global [0 x [12 x [12 x i8]]], align 1
+
+define void @test_siv_no_addrec(i1 %d, i32 %b) {
+; CHECK-LABEL: 'test_siv_no_addrec'
+; CHECK-NEXT: Src: store i8 0, ptr %arrayidx7, align 1 --> Dst: store i8 0, ptr %arrayidx7, align 1
+; CHECK-NEXT: da analyze - output [* *]!
+;
+entry:
+ %conv.val = select i1 %d, i16 1, i16 0
+ br label %for.cond
+
+for.cond: ; preds = %for.inc8, %entry
+ %e.0 = phi i32 [ %b, %entry ], [ %inc9, %for.inc8 ]
+ %cmp = icmp ult i32 %e.0, 10
+ br i1 %cmp, label %for.cond1, label %for.end10
+
+for.cond1: ; preds = %for.inc, %for.cond
+ %f.0 = phi i16 [ %conv.val, %for.cond ], [ %add, %for.inc ]
+ %cmp2 = icmp slt i16 %f.0, 10
+ br i1 %cmp2, label %for.body4, label %for.inc8
+
+for.body4: ; preds = %for.cond1
+ %sub = add i32 %e.0, -3
+ %idxprom = zext i32 %sub to i64
+ %idxprom5 = sext i16 %f.0 to i64
+ %idxprom6 = zext i32 %e.0 to i64
+ %arrayidx7 = getelementptr inbounds [0 x [12 x [12 x i8]]], ptr @a, i64 0, i64 %idxprom, i64 %idxprom5, i64 %idxprom6
+ store i8 0, ptr %arrayidx7, align 1
+ br label %for.inc
+
+for.inc: ; preds = %for.body4
+ %add = add i16 %f.0, 2
+ br label %for.cond1
+
+for.inc8: ; preds = %for.cond1
+ %inc9 = add i32 %e.0, 1
+ br label %for.cond
+
+for.end10: ; preds = %for.cond
+ ret void
+}
+
+define void @f1(ptr %a) {
+; CHECK-LABEL: 'f1'
+; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1
+; CHECK-NEXT: da analyze - output [*]!
+;
+entry:
+ br label %loop
+
+loop:
+ %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+ %and = and i64 %i, 1
+ %idx = getelementptr inbounds [4 x [4 x i8]], ptr %a, i64 0, i64 %and, i64 %and
+ store i8 0, ptr %idx
+ %i.next = add i64 %i, 1
+ %exitcond.not = icmp slt i64 %i.next, 8
+ br i1 %exitcond.not, label %loop, label %exit
+
+exit:
+ ret void
+}
diff --git a/llvm/test/Analysis/DependenceAnalysis/bounds-check.ll b/llvm/test/Analysis/DependenceAnalysis/bounds-check.ll
new file mode 100644
index 0000000000000..dca86e5e55643
--- /dev/null
+++ b/llvm/test/Analysis/DependenceAnalysis/bounds-check.ll
@@ -0,0 +1,29 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -disable-output "-passes=print<da>" 2>&1 | FileCheck %s
+
+; Test case for SmallBitVector bounds checking bug in DependenceAnalysis.
+; This test ensures that loop index mapping functions don't cause out-of-bounds
+; access to SmallBitVector when loop depths exceed MaxLevels.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+
+define void @bounds_check_test(ptr %a) {
+; CHECK-LABEL: 'bounds_check_test'
+; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1
+; CHECK-NEXT: da analyze - none!
+;
+entry:
+ br label %loop
+
+loop:
+ %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+ %and = and i64 %i, 1 ; Creates index 0 or 1
+ %idx = getelementptr inbounds [4 x [4 x i8]], ptr %a, i64 0, i64 %and, i64 %i
+ store i8 0, ptr %idx
+ %i.next = add i64 %i, 1
+ %exitcond.not = icmp slt i64 %i.next, 4
+ br i1 %exitcond.not, label %loop, label %exit
+
+exit:
+ ret void
+}
diff --git a/llvm/test/Analysis/DependenceAnalysis/wrapping-addrec.ll b/llvm/test/Analysis/DependenceAnalysis/wrapping-addrec.ll
new file mode 100644
index 0000000000000..d32e5225f4e29
--- /dev/null
+++ b/llvm/test/Analysis/DependenceAnalysis/wrapping-addrec.ll
@@ -0,0 +1,36 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -disable-output "-passes=print<da>" 2>&1 | FileCheck %s
+
+; Test case for wrapping AddRec detection in DependenceAnalysis.
+; This ensures that AddRec expressions that wrap (creating cyclic rather than
+; linear patterns) are rejected from SIV analysis and treated conservatively.
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+
+
+
+; This test case has a clear dependence pattern that was incorrectly reported as "none!"
+; The issue: {false,+,true} in i1 arithmetic creates pattern (0,1,0,1,0,1,...).
+; - i=0: a[0][0][0], i=1: a[0][1][1], i=2: a[0][0][0], i=3: a[0][1][1], ...
+; - Clear dependencies at distances 2, 4, 6 between iterations accessing same locations.
+; - Strong SIV test was missing these due to treating wrapping pattern as linear.
+define void @test_wrapping_i1_addrec(ptr %a) {
+; CHECK-LABEL: 'test_wrapping_i1_addrec'
+; CHECK-NEXT: Src: store i8 0, ptr %idx, align 1 --> Dst: store i8 0, ptr %idx, align 1
+; CHECK-NEXT: da analyze - output [*]!
+;
+entry:
+ br label %loop
+
+loop:
+ %i = phi i64 [ 0, %entry ], [ %i.next, %loop ]
+ %and = and i64 %i, 1
+ %idx = getelementptr inbounds [4 x [4 x i8]], ptr %a, i64 0, i64 %and, i64 %and
+ store i8 0, ptr %idx
+ %i.next = add i64 %i, 1
+ %exitcond.not = icmp slt i64 %i.next, 8
+ br i1 %exitcond.not, label %loop, label %exit
+
+exit:
+ ret void
+}
diff --git a/llvm/test/Analysis/DependenceAnalysis/wrapping-maxbtc.ll b/llvm/test/Analysis/DependenceAnalysis/wrapping-maxbtc.ll
new file mode 100644
index 0000000000000..213d8f425b9ed
--- /dev/null
+++ b/llvm/test/Analysis/DependenceAnalysis/wrapping-maxbtc.ll
@@ -0,0 +1,35 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -disable-output "-passes=print<da>" 2>&1 | FileCheck %s
+
+; Test case for wrapping AddRec detection using constant max backedge taken count.
+; This ensures that wrapping detection works even when exact BTC is not available
+; but we can get a conservativ...
[truncated]
|
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
Fixes GitHub issue llvm#148435 where testSIV() would hit an assertion failure when neither Src nor Dst expressions contain AddRec after constraint propagation. This can occur when propagation simplifies expressions to non-AddRec forms. The subscript is effectively a zero induction variable. The fix falls back to ZIV analysis in this case, treating the simplified expressions as loop-invariant, which is the correct behavior when all induction variable references have been eliminated through propagation. The patch also fixes a MIV case that may decay into a ZIV test. Add missing NonLinear case to switch statements in propagation code to prevent 'bad subscript classification' crash when subscripts are reclassified as NonLinear after constraint propagation. Add regression test to prevent future occurrences of this issue.
kasuga-fj
reviewed
Aug 22, 2025
nikic
reviewed
Aug 23, 2025
| @@ -1337,6 +1337,12 @@ class ScalarEvolution { | |||
| /// sharpen it. | |||
| LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags); | |||
|
|
|||
| /// Check if this AddRec expression may wrap, making it non-affine. | |||
There was a problem hiding this comment.
Suggested change
| /// Check if this AddRec expression may wrap, making it non-affine. | |
| /// Check if this AddRec expression may wrap. |
SCEV uses the term "affine" to refer to recurrences with loop invariant step (in other words, two operand addrecs). Let's avoid muddying the terminology between affine and wrapping.
There was a problem hiding this comment.
Not fixed (but the suggested change has already been committed??).
Looks like there was a mistake in the git operation.
There was a problem hiding this comment.
Fixed in my local git.
|
|
||
| // Step 1: Check existing no-wrap flags from SCEV construction. | ||
| if (AddRec->hasNoSelfWrap() || AddRec->hasNoUnsignedWrap() || | ||
| AddRec->hasNoSignedWrap()) { |
There was a problem hiding this comment.
hasNoSelfWrap() implies the other two. But then your SCEVWrapPredicate requires both nusw and nsw. Also, nusw is a pointer property, but you exclude those above. Overall I'm left confused which property you actually need for DA. Is it nw, nsw, nuw, nusw or some combination thereof?
There was a problem hiding this comment.
SCEVWrapPredicate requires both nusw and nsw
I fixed SCEVWrapPredicate to only require the existing wrap flags, and if the AddRec does not have wrap flags, then NUSW for pointer types and NSSW for integers.
which property you actually need for DA
we need to ensure AddRec expressions don't create cyclic patterns that violate linearity assumptions. So NW is enough as it is set whenever either NUW or NSW are set. Thus fixed in the above code avoiding 2 flag checks.
There was a problem hiding this comment.
NW is insufficient. DA handles affine format expressions and expects their "monotonicity". Things are getting complicated because signed and unsigned interpretations are mixed up in DA.
Overall I'm left confused which property you actually need for DA. Is it nw, nsw, nuw, nusw or some combination thereof?
This is a good question, and I don't think this is simple enough to be answered easily. The only thing now I'm certain of is that "NW is not sufficient".
…ce tests Previously, predicates were collected using a local `Assume` vector. This patch: 1. Removes local `Assume` vector, uses class member `Assumptions` instead. 2. Adds a `getNonRedundantAssumptions()` helper for deduplication. 3. Extends predicate collection to all dependence tests.
Previously, LAA would incorrectly classify Write-After-Write dependencies
with negative distances as safe Forward dependencies, allowing inappropriate
vectorization of loops with bidirectional WAW dependencies.
The issue occurred in loops like:
for(int i = 0; i < n; ++i) {
A[(i+1)*4] = 10; // First store
A[i] = 100; // Second store
}
The dependence distance from first store to second store is negative:
{-16,+,-12}. However, this represents a bidirectional WAW dependency
that DependenceAnalysis would report as 'output [<>]!', indicating
dependency in both directions.
This patch fixes LAA to properly detect WAW dependencies with negative
distances as unsafe, preventing incorrect vectorization.
The fix adds a check specifically for Write-After-Write dependencies
before the general negative distance handling, ensuring they are
classified as Unknown (unsafe) rather than Forward (safe).
A proper fix, not implemented here because it would be a major rework of LAA,
is to implement bidirectional dependence checking that computes distances
in both directions and detects inconsistent direction vectors.
SCEV was losing NSW flags during AddRec operations, causing Dependence Analysis to add unnecessary runtime assumptions for inbounds GEPs. This patch fixes getAddExpr: when combining AddRecs from the same loop, preserve compatible NSW/NUW flags from input AddRecs instead of always using FlagAnyWrap.
SCEV was losing NSW flags during AddRec operations, causing Dependence Analysis to add unnecessary runtime assumptions for inbounds GEPs. This patch fixes getMulExpr: when multiplying AddRecs by constants, preserve NSW flags that were explicitly requested from inbounds GEP operations. The overflow check was too conservative and cleared flags even when they were explicitly requested via OrigFlags.
SCEV was losing NSW flags during AddRec operations, causing Dependence Analysis
to add unnecessary runtime assumptions for inbounds GEPs.
This patch fixes getGEPExpr: inherit flags from index expressions when GEP has
no explicit flags, allowing NSW flags from AddRec indices to propagate to the
final GEP result.
This eliminates spurious runtime assumptions in DA for expressions like
{0,+,(4 * %N * %M)} derived from inbounds GEPs, allowing proper dependence
analysis without conservative runtime checks.
You can test this locally with the following command:git diff -U0 --pickaxe-regex -S '([^a-zA-Z0-9#_-]undef[^a-zA-Z0-9_-]|UndefValue::get)' 'HEAD~1' HEAD llvm/test/Analysis/DependenceAnalysis/PR148435.ll llvm/test/Analysis/DependenceAnalysis/bounds-check.ll llvm/test/Analysis/DependenceAnalysis/scev-nsw-flags-enable-analysis.ll llvm/test/Analysis/DependenceAnalysis/wrapping-addrec-1.ll llvm/test/Analysis/DependenceAnalysis/wrapping-addrec.ll llvm/test/Analysis/DependenceAnalysis/wrapping-maxbtc.ll llvm/test/Analysis/LoopAccessAnalysis/waw-negative-dependence.ll llvm/test/Analysis/ScalarEvolution/gep-nsw-flag-preservation.ll llvm/include/llvm/Analysis/DependenceAnalysis.h llvm/include/llvm/Analysis/ScalarEvolution.h llvm/lib/Analysis/DependenceAnalysis.cpp llvm/lib/Analysis/LoopAccessAnalysis.cpp llvm/lib/Analysis/ScalarEvolution.cpp llvm/test/Analysis/DDG/basic-a.ll llvm/test/Analysis/DDG/basic-b.ll llvm/test/Analysis/Delinearization/a.ll llvm/test/Analysis/Delinearization/constant_functions_multi_dim.ll llvm/test/Analysis/Delinearization/fixed_size_array.ll llvm/test/Analysis/Delinearization/himeno_1.ll llvm/test/Analysis/Delinearization/himeno_2.ll llvm/test/Analysis/Delinearization/iv_times_constant_in_subscript.ll llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_nts_3d.ll llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll llvm/test/Analysis/Delinearization/multidim_only_ivs_2d.ll llvm/test/Analysis/Delinearization/multidim_only_ivs_2d_nested.ll llvm/test/Analysis/Delinearization/multidim_only_ivs_3d.ll llvm/test/Analysis/Delinearization/multidim_only_ivs_3d_cast.ll llvm/test/Analysis/Delinearization/multidim_two_accesses_different_delinearization.ll llvm/test/Analysis/DependenceAnalysis/DADelin.ll llvm/test/Analysis/DependenceAnalysis/MIVCheckConst.ll llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheck.ll llvm/test/Analysis/LoopAccessAnalysis/depend_diff_types.ll llvm/test/Analysis/LoopAccessAnalysis/different-access-types-rt-checks.ll llvm/test/Analysis/LoopAccessAnalysis/evaluate-at-symbolic-max-backedge-taken-count-may-wrap.ll llvm/test/Analysis/LoopAccessAnalysis/forward-loop-carried.ll llvm/test/Analysis/LoopAccessAnalysis/forward-loop-independent.ll llvm/test/Analysis/LoopAccessAnalysis/loops-with-indirect-reads-and-writes.ll llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll llvm/test/Analysis/LoopAccessAnalysis/retry-runtime-checks-after-dependence-analysis-forked-pointers.ll llvm/test/Analysis/LoopAccessAnalysis/retry-runtime-checks-after-dependence-analysis.ll llvm/test/Analysis/LoopAccessAnalysis/symbolic-stride.ll llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info.ll llvm/test/Analysis/ScalarEvolution/max-expr-cache.ll llvm/test/Analysis/ScalarEvolution/nsw.ll llvm/test/Analysis/ScalarEvolution/ptrtoint.ll llvm/test/Analysis/ScalarEvolution/trip-count-scalable-stride.ll llvm/test/Transforms/LoopIdiom/memset-runtime-debug.ll llvm/test/Transforms/LoopStrengthReduce/lsr-term-fold-negative-testcase.ll llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll llvm/test/Transforms/LoopVectorize/AArch64/sve-interleaved-accesses.ll llvm/test/Transforms/LoopVectorize/interleaved-accesses.llThe following files introduce new uses of undef:
Undef is now deprecated and should only be used in the rare cases where no replacement is possible. For example, a load of uninitialized memory yields In tests, avoid using For example, this is considered a bad practice: define void @fn() {
...
br i1 undef, ...
}Please use the following instead: define void @fn(i1 %cond) {
...
br i1 %cond, ...
}Please refer to the Undefined Behavior Manual for more information. |
kasuga-fj
reviewed
Aug 24, 2025
There was a problem hiding this comment.
Even if the changes on SCEV side were correct, I think DA side would still be incorrect. As I mentioned in another reply, NW is insufficient.
I believe #154527 is the right direction, although it's only a first step towards addressing the underlying issue -- DA doesn't account for SCEV's wrapping behavior.
| @@ -1337,6 +1337,12 @@ class ScalarEvolution { | |||
| /// sharpen it. | |||
| LLVM_ABI void setNoWrapFlags(SCEVAddRecExpr *AddRec, SCEV::NoWrapFlags Flags); | |||
|
|
|||
| /// Check if this AddRec expression may wrap, making it non-affine. | |||
There was a problem hiding this comment.
Not fixed (but the suggested change has already been committed??).
Looks like there was a mistake in the git operation.
| @@ -168,7 +168,7 @@ test2.for.body: ; preds = %entry, %test2 | |||
| %add = fadd float %0, %1 | |||
| %arrayidx2 = getelementptr inbounds float, ptr %a, i64 %i.02 | |||
| store float %add, ptr %arrayidx2, align 4 | |||
| %inc = add i64 %i.02, 1 | |||
There was a problem hiding this comment.
Why is it correct to add nsw? The pseudo code in the above says %n is unsigned.
As for the other tests, I generally think it's not a good idea to modify the IR.
There was a problem hiding this comment.
This change preserves the pattern of the test that deals with building the DDG and the shape of the DDG.
I'm all ears if you have another shorter way (less than 2 lines change) to preserve the pattern that the test was written for.
|
|
||
| // Step 1: Check existing no-wrap flags from SCEV construction. | ||
| if (AddRec->hasNoSelfWrap() || AddRec->hasNoUnsignedWrap() || | ||
| AddRec->hasNoSignedWrap()) { |
There was a problem hiding this comment.
NW is insufficient. DA handles affine format expressions and expects their "monotonicity". Things are getting complicated because signed and unsigned interpretations are mixed up in DA.
Overall I'm left confused which property you actually need for DA. Is it nw, nsw, nuw, nusw or some combination thereof?
This is a good question, and I don't think this is simple enough to be answered easily. The only thing now I'm certain of is that "NW is not sufficient".
…sions Fixes GitHub issue llvm#148435 where {false,+,true} patterns reported "da analyze - none!" instead of correct "da analyze - output [*]!". The issue occurs when AddRec expressions in narrow types create cyclic patterns (e.g., {false,+,true} in i1 arithmetic: 0,1,0,1,0,1...) that violate SIV analysis assumptions of linear, non-wrapping recurrences. The fix detects potential wrapping by checking if step × iteration_count exceeds the type's representable range, then classifies such expressions as NonLinear for conservative analysis.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Fixes GitHub issue #148435 where {false,+,true} patterns reported
"da analyze - none!" instead of correct "da analyze - output [*]!".
The issue occurs when AddRec expressions in narrow types create cyclic
patterns (e.g., {false,+,true} in i1 arithmetic: 0,1,0,1,0,1...) that
violate SIV analysis assumptions of linear, non-wrapping recurrences.
The fix detects potential wrapping by checking if step × iteration_count
exceeds the type's representable range, then classifies such expressions
as NonLinear for conservative analysis.
Add wrapping detection in checkSubscript() with fallback to exact and max
backedge taken count for variable bounds.