summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/IVUsers.h3
-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
-rw-r--r--test/Transforms/LoopStrengthReduce/2012-03-15-nopreheader.ll50
6 files changed, 115 insertions, 18 deletions
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index 2a3bb9bc48..11d2cf0ac7 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -145,7 +145,8 @@ public:
/// 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 AddUsersIfInteresting(Instruction *I);
+ bool AddUsersIfInteresting(Instruction *I,
+ SmallPtrSet<Loop*,16> &SimpleLoopNests);
IVStrideUse &AddUser(Instruction *User, Value *Operand);
diff --git a/lib/Analysis/IVUsers.cpp b/lib/Analysis/IVUsers.cpp
index cad22f8f1a..c598b72c0d 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 d1e57e101b..490617a0c8 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 6768860caa..82d918eeef 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 20eef3c0dc..e00565d5f9 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;
diff --git a/test/Transforms/LoopStrengthReduce/2012-03-15-nopreheader.ll b/test/Transforms/LoopStrengthReduce/2012-03-15-nopreheader.ll
new file mode 100644
index 0000000000..207e9d74f5
--- /dev/null
+++ b/test/Transforms/LoopStrengthReduce/2012-03-15-nopreheader.ll
@@ -0,0 +1,50 @@
+; RUN: opt -loop-reduce -S < %s | FileCheck %s
+;
+; <rdar://problem/11049788> Segmentation fault: 11 in LoopStrengthReduce
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-apple-darwin10.0.0"
+
+; IVUsers should not consider tmp128 a valid user because it is not in a
+; simplified loop nest.
+; CHECK: @nopreheader
+; CHECK: for.cond:
+; CHECK: %tmp128 = add i64 %0, %indvar65
+define void @nopreheader(i8* %cmd) nounwind ssp {
+entry:
+ indirectbr i8* undef, [label %while.cond]
+
+while.cond: ; preds = %while.body, %entry
+ %0 = phi i64 [ %indvar.next48, %while.body ], [ 0, %entry ]
+ indirectbr i8* undef, [label %while.end, label %while.body]
+
+while.body: ; preds = %lor.rhs, %lor.lhs.false17, %lor.lhs.false11, %lor.lhs.false, %land.rhs
+ %indvar.next48 = add i64 %0, 1
+ indirectbr i8* undef, [label %while.cond]
+
+while.end: ; preds = %lor.rhs, %while.cond
+ indirectbr i8* undef, [label %if.end152]
+
+if.end152: ; preds = %lor.lhs.false144, %if.end110
+ indirectbr i8* undef, [label %lor.lhs.false184, label %for.cond]
+
+lor.lhs.false184: ; preds = %lor.lhs.false177
+ indirectbr i8* undef, [label %return, label %for.cond]
+
+for.cond: ; preds = %for.inc, %lor.lhs.false184, %if.end152
+ %indvar65 = phi i64 [ %indvar.next66, %for.inc ], [ 0, %lor.lhs.false184 ], [ 0, %if.end152 ]
+ %tmp128 = add i64 %0, %indvar65
+ %s.4 = getelementptr i8* %cmd, i64 %tmp128
+ %tmp195 = load i8* %s.4, align 1
+ indirectbr i8* undef, [label %return, label %land.rhs198]
+
+land.rhs198: ; preds = %for.cond
+ indirectbr i8* undef, [label %return, label %for.inc]
+
+for.inc: ; preds = %lor.rhs234, %land.lhs.true228, %land.lhs.true216, %land.lhs.true204
+ %indvar.next66 = add i64 %indvar65, 1
+ indirectbr i8* undef, [label %for.cond]
+
+return: ; preds = %if.end677, %doshell, %if.then96
+ ret void
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-27 22:11:04 +0000