summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--include/llvm/Analysis/LoopInfo.h19
-rw-r--r--lib/Analysis/ScalarEvolution.cpp19
-rw-r--r--lib/Transforms/Scalar/LoopUnswitch.cpp13
-rw-r--r--lib/Transforms/Utils/LoopSimplify.cpp30
-rw-r--r--test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll28
5 files changed, 72 insertions, 37 deletions
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 326b9d2..482c0fc 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -1020,6 +1020,25 @@ public:
void removeBlock(BasicBlock *BB) {
LI.removeBlock(BB);
}
+
+ /// replacementPreservesLCSSAForm - Returns true if replacing From with To
+ /// everywhere is guaranteed to preserve LCSSA form.
+ bool replacementPreservesLCSSAForm(Instruction *From, Value *To) {
+ // Preserving LCSSA form is only problematic if the replacing value is an
+ // instruction.
+ Instruction *I = dyn_cast<Instruction>(To);
+ if (!I) return true;
+ // If the instruction is not defined in a loop then it can safely replace
+ // anything.
+ Loop *ToLoop = getLoopFor(I->getParent());
+ if (!ToLoop) return true;
+ // If the replacing instruction is defined in the same loop as the original
+ // instruction, or in a loop that contains it as an inner loop, then using
+ // it as a replacement will not break LCSSA form.
+ Loop *FromLoop = getLoopFor(From->getParent());
+ if (ToLoop->contains(FromLoop)) return true;
+ return false;
+ }
};
diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp
index 04ec67f..9db46a8 100644
--- a/lib/Analysis/ScalarEvolution.cpp
+++ b/lib/Analysis/ScalarEvolution.cpp
@@ -2768,25 +2768,10 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
// PHI's incoming blocks are in a different loop, in which case doing so
// risks breaking LCSSA form. Instcombine would normally zap these, but
// it doesn't have DominatorTree information, so it may miss cases.
- if (Value *V = SimplifyInstruction(PN, TD, DT)) {
- Instruction *I = dyn_cast<Instruction>(V);
- // Only instructions are problematic for preserving LCSSA form.
- if (!I)
+ if (Value *V = SimplifyInstruction(PN, TD, DT))
+ if (LI->replacementPreservesLCSSAForm(PN, V))
return getSCEV(V);
- // If the instruction is not defined in a loop, then it can be used freely.
- Loop *ILoop = LI->getLoopFor(I->getParent());
- if (!ILoop)
- return getSCEV(I);
-
- // If the instruction is defined in the same loop as the phi node, or in a
- // loop that contains the phi node loop as an inner loop, then using it as
- // a replacement for the phi node will not break LCSSA form.
- Loop *PNLoop = LI->getLoopFor(PN->getParent());
- if (ILoop->contains(PNLoop))
- return getSCEV(I);
- }
-
// If it's not a loop phi, we can't handle it yet.
return getUnknown(PN);
}
diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index 009ee7b..2eaeb43 100644
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -990,15 +990,16 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) {
++NumSimplify;
continue;
}
-
+
// See if instruction simplification can hack this up. This is common for
// things like "select false, X, Y" after unswitching made the condition be
// 'false'.
- if (Value *V = SimplifyInstruction(I, 0, DT)) {
- ReplaceUsesOfWith(I, V, Worklist, L, LPM);
- continue;
- }
-
+ if (Value *V = SimplifyInstruction(I, 0, DT))
+ if (LI->replacementPreservesLCSSAForm(I, V)) {
+ ReplaceUsesOfWith(I, V, Worklist, L, LPM);
+ continue;
+ }
+
// Special case hacks that appear commonly in unswitched code.
if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
if (BI->isUnconditional()) {
diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index 320223c..f77a583 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -269,11 +269,12 @@ ReprocessLoop:
PHINode *PN;
for (BasicBlock::iterator I = L->getHeader()->begin();
(PN = dyn_cast<PHINode>(I++)); )
- if (Value *V = SimplifyInstruction(PN, 0, DT)) {
- if (AA) AA->deleteValue(PN);
- PN->replaceAllUsesWith(V);
- PN->eraseFromParent();
- }
+ if (Value *V = SimplifyInstruction(PN, 0, DT))
+ if (LI->replacementPreservesLCSSAForm(PN, V)) {
+ if (AA) AA->deleteValue(PN);
+ PN->replaceAllUsesWith(V);
+ PN->eraseFromParent();
+ }
// If this loop has multiple exits and the exits all go to the same
// block, attempt to merge the exits. This helps several passes, such
@@ -445,17 +446,18 @@ static void AddBlockAndPredsToSet(BasicBlock *InputBB, BasicBlock *StopBlock,
/// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
/// PHI node that tells us how to partition the loops.
static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorTree *DT,
- AliasAnalysis *AA) {
+ AliasAnalysis *AA, LoopInfo *LI) {
for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
PHINode *PN = cast<PHINode>(I);
++I;
- if (Value *V = SimplifyInstruction(PN, 0, DT)) {
- // This is a degenerate PHI already, don't modify it!
- PN->replaceAllUsesWith(V);
- if (AA) AA->deleteValue(PN);
- PN->eraseFromParent();
- continue;
- }
+ if (Value *V = SimplifyInstruction(PN, 0, DT))
+ if (LI->replacementPreservesLCSSAForm(PN, V)) {
+ // This is a degenerate PHI already, don't modify it!
+ PN->replaceAllUsesWith(V);
+ if (AA) AA->deleteValue(PN);
+ PN->eraseFromParent();
+ continue;
+ }
// Scan this PHI node looking for a use of the PHI node by itself.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
@@ -523,7 +525,7 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
/// created.
///
Loop *LoopSimplify::SeparateNestedLoop(Loop *L, LPPassManager &LPM) {
- PHINode *PN = FindPHIToPartitionLoops(L, DT, AA);
+ PHINode *PN = FindPHIToPartitionLoops(L, DT, AA, LI);
if (PN == 0) return 0; // No known way to partition.
// Pull out all predecessors that have varying values in the loop. This
diff --git a/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll b/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll
new file mode 100644
index 0000000..a976d18
--- /dev/null
+++ b/test/Transforms/LoopUnswitch/2010-11-18-LCSSA.ll
@@ -0,0 +1,28 @@
+; RUN: opt < %s -loop-unswitch
+; PR8622
+@g_38 = external global i32, align 4
+
+define void @func_67(i32 %p_68.coerce) nounwind {
+entry:
+ br i1 true, label %for.end12, label %bb.nph
+
+bb.nph: ; preds = %entry
+ %g_38.promoted = load i32* @g_38
+ br label %for.body
+
+for.body: ; preds = %for.cond, %bb.nph
+ %tobool.i = icmp eq i32 %p_68.coerce, 1
+ %xor4.i = xor i32 %p_68.coerce, 1
+ %call1 = select i1 %tobool.i, i32 0, i32 %xor4.i
+ br label %for.cond
+
+for.cond: ; preds = %for.body
+ br i1 true, label %for.cond.for.end12_crit_edge, label %for.body
+
+for.cond.for.end12_crit_edge: ; preds = %for.cond
+ store i32 %call1, i32* @g_38
+ br label %for.end12
+
+for.end12: ; preds = %for.cond.for.end12_crit_edge, %entry
+ ret void
+}