[ScalarEvolution] Limit recursion in getRangeRef for PHI nodes. #152823
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
llvmbot
added
llvm:analysis
|
@llvm/pr-subscribers-llvm-analysis @llvm/pr-subscribers-llvm-transforms Author: Eli Friedman (efriedma-quic) ChangesRestrict PHI nodes that getRangeRef is allowed to recursively examine so we don't need a "visited" set. And fix createSCEVIter so it creates all the relevant SCEV nodes before getRangeRef tries to examine them. The tests that are affected have induction variables that aren't AddRecs. (Other cases are theoretically affected, but don't seem to show up in our tests.) Patch is 28.95 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/152823.diff 11 Files Affected:
diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h
index 167845ce646b9..0ba707e12666f 100644
--- a/llvm/include/llvm/Analysis/ScalarEvolution.h
+++ b/llvm/include/llvm/Analysis/ScalarEvolution.h
@@ -1500,12 +1500,6 @@ class ScalarEvolution {
/// Mark predicate values currently being processed by isImpliedCond.
SmallPtrSet<const Value *, 6> PendingLoopPredicates;
- /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
- SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
-
- /// Mark SCEVUnknown Phis currently being processed by getRangeRefIter.
- SmallPtrSet<const PHINode *, 6> PendingPhiRangesIter;
-
// Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
SmallPtrSet<const PHINode *, 6> PendingMerges;
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 0990a0daac80c..98f4cf40a5718 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5963,7 +5963,9 @@ static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge,
return false;
}
-const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+static bool getOperandsForSelectLikePHI(DominatorTree &DT, PHINode *PN,
+ Value *&Cond, Value *&LHS,
+ Value *&RHS) {
auto IsReachable =
[&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };
if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
@@ -5983,29 +5985,23 @@ const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
assert(IDom && "At least the entry block should dominate PN");
auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
- Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
-
- if (BI && BI->isConditional() &&
- BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
- properlyDominates(getSCEV(LHS), PN->getParent()) &&
- properlyDominates(getSCEV(RHS), PN->getParent()))
- return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
+ return BI && BI->isConditional() &&
+ BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS);
}
+ return false;
+}
+
+const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
+ Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+ if (getOperandsForSelectLikePHI(DT, PN, Cond, LHS, RHS) &&
+ properlyDominates(getSCEV(LHS), PN->getParent()) &&
+ properlyDominates(getSCEV(RHS), PN->getParent()))
+ return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
return nullptr;
}
-/// Returns SCEV for the first operand of a phi if all phi operands have
-/// identical opcodes and operands
-/// eg.
-/// a: %add = %a + %b
-/// br %c
-/// b: %add1 = %a + %b
-/// br %c
-/// c: %phi = phi [%add, a], [%add1, b]
-/// scev(%phi) => scev(%add)
-const SCEV *
-ScalarEvolution::createNodeForPHIWithIdenticalOperands(PHINode *PN) {
+static BinaryOperator *getCommonInstForPHI(PHINode *PN) {
BinaryOperator *CommonInst = nullptr;
// Check if instructions are identical.
for (Value *Incoming : PN->incoming_values()) {
@@ -6020,6 +6016,21 @@ ScalarEvolution::createNodeForPHIWithIdenticalOperands(PHINode *PN) {
CommonInst = IncomingInst;
}
}
+ return CommonInst;
+}
+
+/// Returns SCEV for the first operand of a phi if all phi operands have
+/// identical opcodes and operands
+/// eg.
+/// a: %add = %a + %b
+/// br %c
+/// b: %add1 = %a + %b
+/// br %c
+/// c: %phi = phi [%add, a], [%add1, b]
+/// scev(%phi) => scev(%add)
+const SCEV *
+ScalarEvolution::createNodeForPHIWithIdenticalOperands(PHINode *PN) {
+ BinaryOperator *CommonInst = getCommonInstForPHI(PN);
if (!CommonInst)
return nullptr;
@@ -6544,6 +6555,28 @@ getRangeForUnknownRecurrence(const SCEVUnknown *U) {
return FullSet;
}
+// The goal of this function is to check if recursively visiting the operands
+// of this PHI might lead to an infinite loop. If we do see such a loop,
+// there's no good way to break it, so we avoid analyzing such cases.
+//
+// getRangeRef previously used a visited set to avoid infinite loops, but this
+// caused other issues: the result was dependent on the order of getRangeRef
+// calls, and the interaction with createSCEVIter could cause a stack overflow
+// in some cases (see issue #148253).
+//
+// FIXME: The way this is implemented is overly conservative.
+static bool RangeRefPHIAllowedOperands(DominatorTree &DT, PHINode *PH) {
+ Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+ if (getOperandsForSelectLikePHI(DT, PH, Cond, LHS, RHS))
+ return true;
+
+ if (all_of(PH->operands(),
+ [&](Value *Operand) { return DT.dominates(Operand, PH); }))
+ return true;
+
+ return false;
+}
+
const ConstantRange &
ScalarEvolution::getRangeRefIter(const SCEV *S,
ScalarEvolution::RangeSignHint SignHint) {
@@ -6599,8 +6632,8 @@ ScalarEvolution::getRangeRefIter(const SCEV *S,
continue;
}
// `SCEVUnknown`'s require special treatment.
- if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue())) {
- if (!PendingPhiRangesIter.insert(P).second)
+ if (PHINode *P = dyn_cast<PHINode>(UnknownS->getValue())) {
+ if (!RangeRefPHIAllowedOperands(DT, P))
continue;
for (auto &Op : reverse(P->operands()))
AddToWorklist(getSCEV(Op));
@@ -6613,10 +6646,6 @@ ScalarEvolution::getRangeRefIter(const SCEV *S,
// their users in most cases.
for (const SCEV *P : reverse(drop_begin(WorkList))) {
getRangeRef(P, SignHint);
-
- if (auto *UnknownS = dyn_cast<SCEVUnknown>(P))
- if (const PHINode *P = dyn_cast<PHINode>(UnknownS->getValue()))
- PendingPhiRangesIter.erase(P);
}
}
@@ -6926,8 +6955,13 @@ const ConstantRange &ScalarEvolution::getRangeRef(
// A range of Phi is a subset of union of all ranges of its input.
if (PHINode *Phi = dyn_cast<PHINode>(V)) {
+ // SCEVExpander sometimes creates SCEVUnknowns that are secretly
+ // AddRecs; return the range for the corresponding AddRec.
+ if (auto *AR = dyn_cast<SCEVAddRecExpr>(getSCEV(V)))
+ return getRangeRef(AR, SignHint, Depth + 1);
+
// Make sure that we do not run over cycled Phis.
- if (PendingPhiRanges.insert(Phi).second) {
+ if (RangeRefPHIAllowedOperands(DT, Phi)) {
ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);
for (const auto &Op : Phi->operands()) {
@@ -6939,9 +6973,6 @@ const ConstantRange &ScalarEvolution::getRangeRef(
}
ConservativeResult =
ConservativeResult.intersectWith(RangeFromOps, RangeType);
- bool Erased = PendingPhiRanges.erase(Phi);
- assert(Erased && "Failed to erase Phi properly?");
- (void)Erased;
}
}
@@ -7612,7 +7643,55 @@ ScalarEvolution::getOperandsToCreate(Value *V, SmallVectorImpl<Value *> &Ops) {
return getUnknown(V);
case Instruction::PHI:
- // Keep constructing SCEVs' for phis recursively for now.
+ // getNodeForPHI has four ways to turn a PHI into a SCEV; retrieve the
+ // relevant nodes for each of them.
+ //
+ // The first is just to call simplifyInstruction, and get something back
+ // that isn't a PHI.
+ if (Value *V = simplifyInstruction(
+ cast<PHINode>(U),
+ {getDataLayout(), &TLI, &DT, &AC, /*CtxI=*/nullptr,
+ /*UseInstrInfo=*/true, /*CanUseUndef=*/false})) {
+ assert(V);
+ Ops.push_back(V);
+ return nullptr;
+ }
+ // The second is createNodeForPHIWithIdenticalOperands: this looks for
+ // operands which all perform the same operation, but haven't been
+ // CSE'ed for whatever reason.
+ if (BinaryOperator *BO = getCommonInstForPHI(cast<PHINode>(U))) {
+ assert(BO);
+ Ops.push_back(BO);
+ return nullptr;
+ }
+ // The third is createNodeFromSelectLikePHI; this takes a PHI which
+ // is equivalent to a select, and analyzes it like a select.
+ {
+ Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
+ if (getOperandsForSelectLikePHI(DT, cast<PHINode>(U), Cond, LHS, RHS)) {
+ assert(Cond);
+ assert(LHS);
+ assert(RHS);
+ if (auto *CondICmp = dyn_cast<ICmpInst>(Cond)) {
+ Ops.push_back(CondICmp->getOperand(0));
+ Ops.push_back(CondICmp->getOperand(1));
+ }
+ Ops.push_back(Cond);
+ Ops.push_back(LHS);
+ Ops.push_back(RHS);
+ return nullptr;
+ }
+ }
+ // The fourth way is createAddRecFromPHI. It's complicated to handle here,
+ // so just construct it recursively.
+ //
+ // In addition to getNodeForPHI, also construct nodes which might be needed
+ // by getRangeRef.
+ if (RangeRefPHIAllowedOperands(DT, cast<PHINode>(U))) {
+ for (Value *V : cast<PHINode>(U)->operands())
+ Ops.push_back(V);
+ return nullptr;
+ }
return nullptr;
case Instruction::Select: {
@@ -13683,7 +13762,6 @@ ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
DT(Arg.DT), LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
ValueExprMap(std::move(Arg.ValueExprMap)),
PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
- PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
PendingMerges(std::move(Arg.PendingMerges)),
ConstantMultipleCache(std::move(Arg.ConstantMultipleCache)),
BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
@@ -13726,7 +13804,6 @@ ScalarEvolution::~ScalarEvolution() {
PredicatedBackedgeTakenCounts.clear();
assert(PendingLoopPredicates.empty() && "isImpliedCond garbage");
- assert(PendingPhiRanges.empty() && "getRangeRef garbage");
assert(PendingMerges.empty() && "isImpliedViaMerge garbage");
assert(!WalkingBEDominatingConds && "isLoopBackedgeGuardedByCond garbage!");
assert(!ProvingSplitPredicate && "ProvingSplitPredicate garbage!");
diff --git a/llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll b/llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll
index aab2c49e2973d..fad5c3a144e17 100644
--- a/llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll
+++ b/llvm/test/Analysis/ScalarEvolution/addrec-computed-during-addrec-calculation.ll
@@ -12,19 +12,19 @@ define void @test(ptr %p) {
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ]
; CHECK-NEXT: --> %iv U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Invariant, %loop3: Invariant }
; CHECK-NEXT: %iv2 = phi i32 [ %iv, %loop.header ], [ %iv2.next, %loop2 ]
-; CHECK-NEXT: --> {%iv,+,1}<%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop2: Computable, %loop.header: Variant }
+; CHECK-NEXT: --> {%iv,+,1}<nsw><%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop2: Computable, %loop.header: Variant }
; CHECK-NEXT: %iv2.next = add i32 %iv2, 1
-; CHECK-NEXT: --> {(1 + %iv),+,1}<%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop2: Computable, %loop.header: Variant }
+; CHECK-NEXT: --> {(1 + %iv),+,1}<nw><%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop2: Computable, %loop.header: Variant }
; CHECK-NEXT: %v = load i32, ptr %p, align 4
; CHECK-NEXT: --> %v U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop2: Variant, %loop.header: Variant }
; CHECK-NEXT: %iv2.ext = sext i32 %iv2 to i64
-; CHECK-NEXT: --> (sext i32 {%iv,+,1}<%loop2> to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Computable, %loop3: Invariant }
+; CHECK-NEXT: --> {(sext i32 %iv to i64),+,1}<nsw><%loop2> U: [-2147483648,6442450943) S: [-2147483648,6442450943) Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Computable, %loop3: Invariant }
; CHECK-NEXT: %iv3 = phi i64 [ %iv2.ext, %loop2.end ], [ %iv3.next, %loop3 ]
-; CHECK-NEXT: --> {(sext i32 {%iv,+,1}<%loop2> to i64),+,1}<nsw><%loop3> U: [-2147483648,2147483648) S: [-2147483648,2147483648) Exits: (sext i32 {%iv,+,1}<%loop2> to i64) LoopDispositions: { %loop3: Computable, %loop.header: Variant }
+; CHECK-NEXT: --> {{\{\{}}(sext i32 %iv to i64),+,1}<nsw><%loop2>,+,1}<nsw><%loop3> U: [-2147483648,6442450943) S: [-2147483648,6442450943) Exits: {(sext i32 %iv to i64),+,1}<nsw><%loop2> LoopDispositions: { %loop3: Computable, %loop.header: Variant }
; CHECK-NEXT: %iv3.next = add nsw i64 %iv3, 1
-; CHECK-NEXT: --> {(1 + (sext i32 {%iv,+,1}<%loop2> to i64))<nsw>,+,1}<nsw><%loop3> U: [-2147483647,2147483649) S: [-2147483647,2147483649) Exits: (1 + (sext i32 {%iv,+,1}<%loop2> to i64))<nsw> LoopDispositions: { %loop3: Computable, %loop.header: Variant }
+; CHECK-NEXT: --> {{\{\{}}(1 + (sext i32 %iv to i64))<nsw>,+,1}<nsw><%loop2>,+,1}<nsw><%loop3> U: [-2147483647,6442450944) S: [-2147483647,6442450944) Exits: {(1 + (sext i32 %iv to i64))<nsw>,+,1}<nsw><%loop2> LoopDispositions: { %loop3: Computable, %loop.header: Variant }
; CHECK-NEXT: %iv.next = trunc i64 %iv3 to i32
-; CHECK-NEXT: --> {{\{\{}}%iv,+,1}<%loop2>,+,1}<%loop3> U: full-set S: full-set --> {%iv,+,1}<%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Variant, %loop3: Computable }
+; CHECK-NEXT: --> {{\{\{}}%iv,+,1}<nsw><%loop2>,+,1}<%loop3> U: full-set S: full-set --> {%iv,+,1}<nsw><%loop2> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop.header: Variant, %loop2: Variant, %loop3: Computable }
; CHECK-NEXT: Determining loop execution counts for: @test
; CHECK-NEXT: Loop %loop2: Unpredictable backedge-taken count.
; CHECK-NEXT: Loop %loop2: constant max backedge-taken count is i32 -1
diff --git a/llvm/test/Analysis/ScalarEvolution/outer_phi.ll b/llvm/test/Analysis/ScalarEvolution/outer_phi.ll
index e4a9753b24054..f4dc712f02220 100644
--- a/llvm/test/Analysis/ScalarEvolution/outer_phi.ll
+++ b/llvm/test/Analysis/ScalarEvolution/outer_phi.ll
@@ -7,7 +7,7 @@ define i32 @test_01(i32 %a, i32 %b) {
; CHECK-LABEL: 'test_01'
; CHECK-NEXT: Classifying expressions for: @test_01
; CHECK-NEXT: %outer.iv = phi i32 [ 0, %entry ], [ %iv.next, %outer.backedge ]
-; CHECK-NEXT: --> %outer.iv U: [0,-2147483647) S: [0,-2147483647) Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
+; CHECK-NEXT: --> %outer.iv U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %outer: Variant, %inner: Invariant }
; CHECK-NEXT: %iv = phi i32 [ 0, %outer ], [ %iv.next, %inner.backedge ]
; CHECK-NEXT: --> {0,+,1}<nuw><nsw><%inner> U: [0,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %inner: Computable, %outer: Variant }
; CHECK-NEXT: %iv.next = add nuw nsw i32 %iv, 1
diff --git a/llvm/test/Analysis/ScalarEvolution/pr123550.ll b/llvm/test/Analysis/ScalarEvolution/pr123550.ll
index 709da00935ef3..196f03cad51cd 100644
--- a/llvm/test/Analysis/ScalarEvolution/pr123550.ll
+++ b/llvm/test/Analysis/ScalarEvolution/pr123550.ll
@@ -6,7 +6,7 @@ define i32 @test() {
; CHECK-LABEL: 'test'
; CHECK-NEXT: Classifying expressions for: @test
; CHECK-NEXT: %phi = phi i32 [ -173, %bb ], [ %sub, %loop ]
-; CHECK-NEXT: --> %phi U: [-173,1) S: [-173,1) Exits: -173 LoopDispositions: { %loop: Variant }
+; CHECK-NEXT: --> %phi U: [-256,256) S: [-256,256) Exits: -173 LoopDispositions: { %loop: Variant }
; CHECK-NEXT: %iv2 = phi i32 [ 1, %bb ], [ %iv2.inc, %loop ]
; CHECK-NEXT: --> {1,+,1}<nuw><nsw><%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
; CHECK-NEXT: %srem = srem i32 729259140, %phi
diff --git a/llvm/test/Analysis/ScalarEvolution/pr49856.ll b/llvm/test/Analysis/ScalarEvolution/pr49856.ll
index 751677f1f9f80..ec62f57cc5bb2 100644
--- a/llvm/test/Analysis/ScalarEvolution/pr49856.ll
+++ b/llvm/test/Analysis/ScalarEvolution/pr49856.ll
@@ -5,7 +5,7 @@ define void @test() {
; CHECK-LABEL: 'test'
; CHECK-NEXT: Classifying expressions for: @test
; CHECK-NEXT: %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
-; CHECK-NEXT: --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT: --> %tmp U: [0,-2147483648) S: [0,-2147483648)
; CHECK-NEXT: %tmp2 = add nuw nsw i32 %tmp, 1
; CHECK-NEXT: --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
; CHECK-NEXT: Determining loop execution counts for: @test
diff --git a/llvm/test/Analysis/ScalarEvolution/pr58402-large-number-of-zext-exprs.ll b/llvm/test/Analysis/ScalarEvolution/pr58402-large-number-of-zext-exprs.ll
index c79befac2fb1d..0bedc20661633 100644
--- a/llvm/test/Analysis/ScalarEvolution/pr58402-large-number-of-zext-exprs.ll
+++ b/llvm/test/Analysis/ScalarEvolution/pr58402-large-number-of-zext-exprs.ll
@@ -5,7 +5,7 @@ define i32 @pr58402_large_number_of_zext(ptr %dst) {
; CHECK-LABEL: 'pr58402_large_number_of_zext'
; CHECK-NEXT: Classifying expressions for: @pr58402_large_number_of_zext
; CHECK-NEXT: %d.0 = phi i32 [ 0, %entry ], [ %add7.15, %header ]
-; CHECK-NEXT: --> %d.0 U: [0,65) S: [0,65) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT: --> %d.0 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %header: Variant }
; CHECK-NEXT: %b.0 = phi i32 [ 59, %entry ], [ %b.0, %header ]
; CHECK-NEXT: --> 59 U: [59,60) S: [59,60) Exits: 59 LoopDispositions: { %header: Invariant }
; CHECK-NEXT: %conv.neg = sext i1 %cmp to i32
diff --git a/llvm/test/Analysis/ScalarEvolution/ranges.ll b/llvm/test/Analysis/ScalarEvolution/ranges.ll
index cf9d999a6a1ff..cf54b1e63ad39 100644
--- a/llvm/test/Analysis/ScalarEvolution/ranges.ll
+++ b/llvm/test/Analysis/ScalarEvolution/ranges.ll
@@ -308,7 +308,7 @@ define void @mul_6(i32 %n) {
; CHECK-LABEL: 'mul_6'
; CHECK-NEXT: Classifying expressions for: @mul_6
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-; CHECK-NEXT: --> %iv U: [0,-1) S: [-2147483648,2147483645) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT: --> %iv U: [0,-1) S: [-2147483648,2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: %iv.inc = mul nuw i32 %iv, 6
; CHECK-NEXT: --> (6 * %iv) U: [0,-3) S: [-2147483648,2147483645) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: Determining loop execution counts for: @mul_6
@@ -358,7 +358,7 @@ define void @mul_8(i32 %n) {
; CHECK-LABEL: 'mul_8'
; CHECK-NEXT: Classifying expressions for: @mul_8
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-; CHECK-NEXT: --> %iv U: [0,-7) S: [-2147483648,2147483585) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT: --> %iv U: [0,-7) S: [-2147483648,2147483641) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: %iv.inc = mul nuw i32 %iv, 8
; CHECK-NEXT: --> (8 * %iv) U: [0,-63) S: [-2147483648,2147483585) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: Determining loop execution counts for: @mul_8
@@ -408,7 +408,7 @@ define void @mul_10(i32 %n) {
; CHECK-LABEL: 'mul_10'
; CHECK-NEXT: Classifying expressions for: @mul_10
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-; CHECK-NEXT: --> %iv U: [0,-1) S: [-2147483648,2147483645) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT: --> %iv U: [0,-1) S: [-2147483648,2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: %iv.inc = mul nuw i32 %iv, 10
; CHECK-NEXT: --> (10 * %iv) U: [0,-3) S: [-2147483648,2147483645) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: Determining loop execution counts for: @mul_10
@@ -433,7 +433,7 @@ define void @mul_8_wrap(i32 %n) {
; CHECK-LABEL: 'mul_8_wrap'
; CHECK-NEXT: Classifying expressions for: @mul_8_wrap
; CHECK-NEXT: %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
-; CHECK-NEXT: --> %iv U: [0,-7) S: [-2147483648,2147483585) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT: --> %iv U: [0,-7) S: [-2147483648,2147483641) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
; CHECK-NEXT: %iv.inc = mul i32 %iv, ...
[truncated]
|
|
I've run some internal benchmarks with this change and didn't see any significant impact on the scores, so this one looks the best out of the alternatives so far. I wonder if some tests can be handled in similar way or if it'll unnecessarily complicate things. |
efriedma-quic
commented
Aug 12, 2025
There was a problem hiding this comment.
The thing I'm most unhappy about with the current draft is the implementation of RangeRefPHIAllowedOperands; the way it's currently written is much narrower than it should be. Basically, we just want to check that the PHI node isn't in a loop header. But we also need to check for irreducible control flow, and I can't think of any way to do that cheaply with the information we currently cache.
I'm not sure what's going on with create-induction-resume.ll; I don't think it's an unanalyzable recurrence thing. Maybe worth another look.
addrec-computed-during-addrec-calculation.ll is technically an improvement... but the computed range for the one unanalyzable PHI doesn't change. I think the improvement comes directly from removing the recursive getSCEV() call in getRangeRef.
I think the other regressions shown in the test changes aren't practically relevant. If we care, we could implement a dedicated algorithm for analyzing recurrences. Basically, if a PHI node is in a loop header, use a specialized algorithm to analyze it. But I don't think we need it; it shouldn't come up frequently in practice.
So basically you want something like CycleInfo? What kind of check do you need if PHI is in irreducible control flow? Just that it isn't part of any cycle? What scenarios the current check rejects that you want to support? |
|
I guess the minimum is that recursively visiting operands to the PHI, stopping at loop header PHIs, doesn't visit the PHI itself. Irreducible control flow is relevant mostly because LoopInfo doesn't track any information about irreducible cycles. The things that are currently rejected that I'd like to handle are just slightly more complicated control flow, like a switch, or nested if statements. I don't care about handling arbitrarily complicated cases, but the current check trips over pretty simple cases. |
|
@efriedma-quic Yeah, don't think it's possible to do without a DFS traversal somewhere. Can probably be pruned using DTs, but still. |
efriedma-quic
force-pushed
the
scev-getrangeref-recursion
branch
from
1f02eb7 to
b555cf3
Compare
efriedma-quic
changed the title
Restrict PHI nodes that getRangeRef is allowed to recursively examine so we don't need a "visited" set. And fix createSCEVIter so it creates all the relevant SCEV nodes before getRangeRef tries to examine them. The tests that are affected have induction variables that aren't AddRecs. (Other cases are theoretically affected, but don't seem to show up in our tests.)
efriedma-quic
force-pushed
the
scev-getrangeref-recursion
branch
from
b555cf3 to
d24f558
Compare
|
As discussed on #148253, this seems like the way forward... and I don't see any easy way to improve RangeRefPHIAllowedOperands, so I guess we can just go with this as-is? |
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.
Restrict PHI nodes that getRangeRef is allowed to recursively examine so we don't need a "visited" set. And fix createSCEVIter so it creates all the relevant SCEV nodes before getRangeRef tries to examine them.
The tests that are affected have induction variables that aren't AddRecs. (Other cases are theoretically affected, but don't seem to show up in our tests.)