[DependenceAnalysis] Fix SIV test crash when no AddRec after propagation #154980
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-analysis Author: Sebastian Pop (sebpop) ChangesFixes GitHub issue #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. Full diff: https://github.com/llvm/llvm-project/pull/154980.diff 3 Files Affected:
diff --git a/llvm/lib/Analysis/DependenceAnalysis.cpp b/llvm/lib/Analysis/DependenceAnalysis.cpp
index f33e04e804e3d..b0baeb2262aba 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,10 @@ 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;
+
// 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 +977,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 +2290,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 +2358,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 +3841,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 +3892,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 +4180,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 +4220,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/test/Analysis/DependenceAnalysis/PR148435.ll b/llvm/test/Analysis/DependenceAnalysis/PR148435.ll
new file mode 100644
index 0000000000000..1633a91336f68
--- /dev/null
+++ b/llvm/test/Analysis/DependenceAnalysis/PR148435.ll
@@ -0,0 +1,95 @@
+; 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 - none!
+; Note: the second patch for PR148435 modifies the above CHECK to correct "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
+}
|
|
✅ 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
requested changes
Aug 22, 2025
Comment on lines
+2293
to
+2296
| // 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"); |
There was a problem hiding this comment.
The original issue triggers the assertion in the following condition. They are clearly not loop-invariants.
SIV
src = (sext i1 {false,+,true}<%loop> to i64)
dst = (sext i1 {false,+,true}<%loop> to i64)
SIV test expected at least one AddRec
UNREACHABLE executed at /root/llvm-project/llvm/lib/Analysis/DependenceAnalysis.cpp:2295!
There was a problem hiding this comment.
Constraint propagation simplifies the expressions into something that becomes loop invariant.
There was a problem hiding this comment.
Here's where the constraint propagation happens:
// Review the constraints, looking for opportunities
// to simplify a subscript pair (Src and Dst).
// Return true if some simplification occurs.
// If the simplification isn't exact (that is, if it is conservative
// in terms of dependence), set consistent to false.
// Corresponds to Figure 5 from the paper
//
// Practical Dependence Testing
// Goff, Kennedy, Tseng
// PLDI 1991
bool DependenceInfo::propagate(const SCEV *&Src, const SCEV *&Dst,
SmallBitVector &Loops,
SmallVectorImpl<Constraint> &Constraints,
bool &Consistent) {
[...]
if (Changed) {
// propagate, possibly creating new SIVs and ZIVs
if (propagate(Pair[SJ].Src, Pair[SJ].Dst, Pair[SJ].Loops,
Constraints, Result.Consistent)) {
Part of propagate is changing Src and Dst SCEVs whereas the classification remains the same as before constraint propagation.
The other way to fix this is to re-run classify after each call to propagate(). This would change much more than just a line.
Pair[P].Classification =
classifyPair(Pair[P].Src, LI->getLoopFor(Src->getParent()), Pair[P].Dst,
LI->getLoopFor(Dst->getParent()), Pair[P].Loops);
There was a problem hiding this comment.
No. The propagate function does nothing, as you can see from the debug output at https://godbolt.org/z/Ydvosr4qT.
I'm missing the context here. Are you speaking about this code: We don't know before the computation done by the constraint propagator whether the simplification ends up having zero induction variables. At the beginning we do pass in a subscript with a single IV which is correct. The propagation ends up simplifying the Src and Dst SCEVs. |
kasuga-fj
requested changes
Aug 24, 2025
There was a problem hiding this comment.
Do not delete the assertion. The assertion error is correct. The right approach is to stop passing non-AddRecExpr values to testSIV.
I'm missing the context here. Are you speaking about this code:
llvm_unreachable("SIV test expected at least one AddRec"); return false;
Yes. And as I wrote in another reply, the propagation is not relevant here. The correct approach is to stop the analysis at an earlier stage.
Comment on lines
+2293
to
+2296
| // 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"); |
There was a problem hiding this comment.
No. The propagate function does nothing, as you can see from the debug output at https://godbolt.org/z/Ydvosr4qT.
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 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.