summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Analysis/IVUsers.cpp46
-rw-r--r--lib/Transforms/Scalar/IndVarSimplify.cpp13
-rw-r--r--lib/Transforms/Scalar/LoopStrengthReduce.cpp15
-rw-r--r--lib/Transforms/Utils/SimplifyIndVar.cpp6
4 files changed, 63 insertions, 17 deletions
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index cad22f8..c598b72 100644
--- a/lib/Analysis/IVUsers.cpp
+++ b/lib/Analysis/IVUsers.cpp
@@ -79,10 +79,30 @@ static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L,
return false;
}
+/// Return true if this loop and all loop headers that dominate it are in
+/// simplified form.
+static bool isSimplifiedLoopNest(Loop *L, const DominatorTree *DT,
+ const LoopInfo *LI) {
+ if (!L->isLoopSimplifyForm())
+ return false;
+
+ for (DomTreeNode *Rung = DT->getNode(L->getLoopPreheader());
+ Rung; Rung = Rung->getIDom()) {
+ BasicBlock *BB = Rung->getBlock();
+ const Loop *DomLoop = LI->getLoopFor(BB);
+ if (DomLoop && DomLoop->getHeader() == BB) {
+ if (!DomLoop->isLoopSimplifyForm())
+ return false;
+ }
+ }
+ return true;
+}
+
/// AddUsersIfInteresting - Inspect the specified instruction. If it is a
/// reducible SCEV, recursively add its users to the IVUsesByStride set and
/// return true. Otherwise, return false.
-bool IVUsers::AddUsersIfInteresting(Instruction *I) {
+bool IVUsers::AddUsersIfInteresting(Instruction *I,
+ SmallPtrSet<Loop*,16> &SimpleLoopNests) {
// Add this IV user to the Processed set before returning false to ensure that
// all IV users are members of the set. See IVUsers::isIVUserOrOperand.
if (!Processed.insert(I))
@@ -117,6 +137,16 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
if (isa<PHINode>(User) && Processed.count(User))
continue;
+ Loop *UserLoop = LI->getLoopFor(User->getParent());
+
+ // Only consider IVUsers that are dominated by simplified loop
+ // headers. Otherwise, SCEVExpander will crash.
+ if (UserLoop && !SimpleLoopNests.count(UserLoop)) {
+ if (!isSimplifiedLoopNest(UserLoop, DT, LI))
+ return false;
+ SimpleLoopNests.insert(UserLoop);
+ }
+
// Descend recursively, but not into PHI nodes outside the current loop.
// It's important to see the entire expression outside the loop to get
// choices that depend on addressing mode use right, although we won't
@@ -124,14 +154,15 @@ bool IVUsers::AddUsersIfInteresting(Instruction *I) {
// If User is already in Processed, we don't want to recurse into it again,
// but do want to record a second reference in the same instruction.
bool AddUserToIVUsers = false;
- if (LI->getLoopFor(User->getParent()) != L) {
+ if (UserLoop != L) {
if (isa<PHINode>(User) || Processed.count(User) ||
- !AddUsersIfInteresting(User)) {
+ !AddUsersIfInteresting(User, SimpleLoopNests)) {
DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
<< " OF SCEV: " << *ISE << '\n');
AddUserToIVUsers = true;
}
- } else if (Processed.count(User) || !AddUsersIfInteresting(User)) {
+ } else if (Processed.count(User)
+ || !AddUsersIfInteresting(User, SimpleLoopNests)) {
DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
<< " OF SCEV: " << *ISE << '\n');
AddUserToIVUsers = true;
@@ -180,11 +211,16 @@ bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
SE = &getAnalysis<ScalarEvolution>();
TD = getAnalysisIfAvailable<TargetData>();
+ // SCEVExpander can only handle users that are dominated by simplified loop
+ // entries. Keep track of all loops that are only dominated by other simple
+ // loops so we don't traverse the domtree for each user.
+ SmallPtrSet<Loop*,16> SimpleLoopNests;
+
// Find all uses of induction variables in this loop, and categorize
// them by stride. Start by finding all of the PHI nodes in the header for
// this loop. If they are induction variables, inspect their uses.
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
- (void)AddUsersIfInteresting(I);
+ (void)AddUsersIfInteresting(I, SimpleLoopNests);
return false;
}
diff --git a/lib/Transforms/Scalar/IndVarSimplify.cpp b/lib/Transforms/Scalar/IndVarSimplify.cpp
index d1e57e1..490617a 100644
--- a/lib/Transforms/Scalar/IndVarSimplify.cpp
+++ b/lib/Transforms/Scalar/IndVarSimplify.cpp
@@ -450,8 +450,10 @@ void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) {
}
// Add a new IVUsers entry for the newly-created integer PHI.
- if (IU)
- IU->AddUsersIfInteresting(NewPHI);
+ if (IU) {
+ SmallPtrSet<Loop*, 16> SimplifiedLoopNests;
+ IU->AddUsersIfInteresting(NewPHI, SimplifiedLoopNests);
+ }
Changed = true;
}
@@ -1967,8 +1969,11 @@ bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
// loop exit test instruction.
if (IU && NewICmp) {
ICmpInst *NewICmpInst = dyn_cast<ICmpInst>(NewICmp);
- if (NewICmpInst)
- IU->AddUsersIfInteresting(cast<Instruction>(NewICmpInst->getOperand(0)));
+ if (NewICmpInst) {
+ SmallPtrSet<Loop*, 16> SimplifiedLoopNests;
+ IU->AddUsersIfInteresting(cast<Instruction>(NewICmpInst->getOperand(0)),
+ SimplifiedLoopNests);
+ }
}
// Clean up dead instructions.
Changed |= DeleteDeadPHIs(L->getHeader());
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 6768860..82d918e 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -4534,22 +4534,25 @@ LSRInstance::LSRInstance(const TargetLowering *tli, Loop *l, Pass *P)
if (!L->isLoopSimplifyForm())
return;
+ // If there's no interesting work to be done, bail early.
+ if (IU.empty()) return;
+
+#ifndef NDEBUG
// All dominating loops must have preheaders, or SCEVExpander may not be able
// to materialize an AddRecExpr whose Start is an outer AddRecExpr.
//
- // FIXME: This is a little absurd. I think LoopSimplify should be taught
- // to create a preheader under any circumstance.
+ // IVUsers analysis should only create users that are dominated by simple loop
+ // headers. Since this loop should dominate all of its users, its user list
+ // should be empty if this loop itself is not within a simple loop nest.
for (DomTreeNode *Rung = DT.getNode(L->getLoopPreheader());
Rung; Rung = Rung->getIDom()) {
BasicBlock *BB = Rung->getBlock();
const Loop *DomLoop = LI.getLoopFor(BB);
if (DomLoop && DomLoop->getHeader() == BB) {
- if (!DomLoop->getLoopPreheader())
- return;
+ assert(DomLoop->getLoopPreheader() && "LSR needs a simplified loop nest");
}
}
- // If there's no interesting work to be done, bail early.
- if (IU.empty()) return;
+#endif // DEBUG
DEBUG(dbgs() << "\nLSR on loop ";
WriteAsOperand(dbgs(), L->getHeader(), /*PrintType=*/false);
diff --git a/lib/Transforms/Utils/SimplifyIndVar.cpp b/lib/Transforms/Utils/SimplifyIndVar.cpp
index 20eef3c..e00565d 100644
--- a/lib/Transforms/Utils/SimplifyIndVar.cpp
+++ b/lib/Transforms/Utils/SimplifyIndVar.cpp
@@ -231,8 +231,10 @@ void SimplifyIndvar::eliminateIVRemainder(BinaryOperator *Rem,
// Inform IVUsers about the new users.
if (IU) {
- if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0)))
- IU->AddUsersIfInteresting(I);
+ if (Instruction *I = dyn_cast<Instruction>(Rem->getOperand(0))) {
+ SmallPtrSet<Loop*, 16> SimplifiedLoopNests;
+ IU->AddUsersIfInteresting(I, SimplifiedLoopNests);
+ }
}
DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem << '\n');
++NumElimRem;
generated by cgit v1.1 at 2025-06-07 19:19:40 +0000