summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Transforms/Utils/LoopUtils.h5
-rw-r--r--llvm/lib/Transforms/Scalar/LICM.cpp3
-rw-r--r--llvm/lib/Transforms/Utils/LCSSA.cpp49
-rw-r--r--llvm/lib/Transforms/Utils/LoopUnroll.cpp2
-rw-r--r--llvm/test/Transforms/LCSSA/indirectbr.ll40
5 files changed, 83 insertions, 16 deletions
diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
index fdae80df12b..35d121a791a 100644
--- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h
+++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h
@@ -49,7 +49,8 @@ bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
/// If ScalarEvolution is passed in, it will be preserved.
///
/// Returns true if any modifications are made to the loop.
-bool formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE = nullptr);
+bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
+ ScalarEvolution *SE = nullptr);
/// \brief Put a loop nest into LCSSA form.
///
@@ -60,7 +61,7 @@ bool formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE = nullptr);
/// If ScalarEvolution is passed in, it will be preserved.
///
/// Returns true if any modifications are made to the loop.
-bool formLCSSARecursively(Loop &L, DominatorTree &DT,
+bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
ScalarEvolution *SE = nullptr);
}
diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp
index 99725b5f738..f07158a6cb1 100644
--- a/llvm/lib/Transforms/Scalar/LICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LICM.cpp
@@ -316,7 +316,8 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
// SSAUpdater strategy during promotion that was LCSSA aware and reformed
// it as it went.
if (Changed)
- formLCSSARecursively(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>());
+ formLCSSARecursively(*L, *DT, LI,
+ getAnalysisIfAvailable<ScalarEvolution>());
}
// Check that neither this loop nor its parent have had LCSSA broken. LICM is
diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp
index 51a3d9c1fce..3f9b702c5b9 100644
--- a/llvm/lib/Transforms/Utils/LCSSA.cpp
+++ b/llvm/lib/Transforms/Utils/LCSSA.cpp
@@ -61,7 +61,7 @@ static bool isExitBlock(BasicBlock *BB,
/// uses.
static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
const SmallVectorImpl<BasicBlock *> &ExitBlocks,
- PredIteratorCache &PredCache) {
+ PredIteratorCache &PredCache, LoopInfo *LI) {
SmallVector<Use *, 16> UsesToRewrite;
BasicBlock *InstBB = Inst.getParent();
@@ -94,6 +94,7 @@ static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
DomTreeNode *DomNode = DT.getNode(DomBB);
SmallVector<PHINode *, 16> AddedPHIs;
+ SmallVector<PHINode *, 8> PostProcessPHIs;
SSAUpdater SSAUpdate;
SSAUpdate.Initialize(Inst.getType(), Inst.getName());
@@ -131,6 +132,18 @@ static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
// Remember that this phi makes the value alive in this block.
SSAUpdate.AddAvailableValue(ExitBB, PN);
+
+ // LoopSimplify might fail to simplify some loops (e.g. when indirect
+ // branches are involved). In such situations, it might happen that an exit
+ // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create
+ // PHIs in such an exit block, we are also inserting PHIs into L2's header.
+ // This could break LCSSA form for L2 because these inserted PHIs can also
+ // have uses outside of L2. Remember all PHIs in such situation as to
+ // revisit than later on. FIXME: Remove this if indirectbr support into
+ // LoopSimplify gets improved.
+ if (auto *OtherLoop = LI->getLoopFor(ExitBB))
+ if (!L.contains(OtherLoop))
+ PostProcessPHIs.push_back(PN);
}
// Rewrite all uses outside the loop in terms of the new PHIs we just
@@ -157,6 +170,25 @@ static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
SSAUpdate.RewriteUse(*UsesToRewrite[i]);
}
+ // Post process PHI instructions that were inserted into another disjoint loop
+ // and update their exits properly.
+ for (auto *I : PostProcessPHIs) {
+ if (I->use_empty())
+ continue;
+
+ BasicBlock *PHIBB = I->getParent();
+ Loop *OtherLoop = LI->getLoopFor(PHIBB);
+ SmallVector<BasicBlock *, 8> EBs;
+ OtherLoop->getExitBlocks(EBs);
+ if (EBs.empty())
+ continue;
+
+ // Recurse and re-process each PHI instruction. FIXME: we should really
+ // convert this entire thing to a worklist approach where we process a
+ // vector of instructions...
+ processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI);
+ }
+
// Remove PHI nodes that did not have any uses rewritten.
for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
if (AddedPHIs[i]->use_empty())
@@ -180,7 +212,8 @@ blockDominatesAnExit(BasicBlock *BB,
return false;
}
-bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
+bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
+ ScalarEvolution *SE) {
bool Changed = false;
// Get the set of exiting blocks.
@@ -212,7 +245,7 @@ bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
!isa<PHINode>(I->user_back())))
continue;
- Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache);
+ Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache, LI);
}
}
@@ -228,15 +261,15 @@ bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
}
/// Process a loop nest depth first.
-bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT,
+bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
ScalarEvolution *SE) {
bool Changed = false;
// Recurse depth-first through inner loops.
- for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
- Changed |= formLCSSARecursively(**LI, DT, SE);
+ for (Loop::iterator I = L.begin(), E = L.end(); I != E; ++I)
+ Changed |= formLCSSARecursively(**I, DT, LI, SE);
- Changed |= formLCSSA(L, DT, SE);
+ Changed |= formLCSSA(L, DT, LI, SE);
return Changed;
}
@@ -291,7 +324,7 @@ bool LCSSA::runOnFunction(Function &F) {
// Simplify each loop nest in the function.
for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
- Changed |= formLCSSARecursively(**I, *DT, SE);
+ Changed |= formLCSSARecursively(**I, *DT, LI, SE);
return Changed;
}
diff --git a/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
index 0e1baa1299c..f6766603ed7 100644
--- a/llvm/lib/Transforms/Utils/LoopUnroll.cpp
+++ b/llvm/lib/Transforms/Utils/LoopUnroll.cpp
@@ -544,7 +544,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
while (OuterL->getParentLoop() != LatchLoop)
OuterL = OuterL->getParentLoop();
- formLCSSARecursively(*OuterL, *DT, SE);
+ formLCSSARecursively(*OuterL, *DT, LI, SE);
}
}
diff --git a/llvm/test/Transforms/LCSSA/indirectbr.ll b/llvm/test/Transforms/LCSSA/indirectbr.ll
index 96564486e82..345395bee01 100644
--- a/llvm/test/Transforms/LCSSA/indirectbr.ll
+++ b/llvm/test/Transforms/LCSSA/indirectbr.ll
@@ -1,11 +1,11 @@
-; RUN: opt < %s -lcssa -verify-loop-info -verify-dom-info -disable-output
-; PR5437
+; RUN: opt < %s -loop-simplify -lcssa -verify-loop-info -verify-dom-info -S | FileCheck %s
; LCSSA should work correctly in the case of an indirectbr that exits
; the loop, and the loop has exits with predecessors not within the loop
; (and btw these edges are unsplittable due to the indirectbr).
-
-define i32 @js_Interpret() nounwind {
+; PR5437
+define i32 @test0() nounwind {
+; CHECK-LABEL: @test0
entry:
br i1 undef, label %"4", label %"3"
@@ -540,3 +540,35 @@ entry:
"1862": ; preds = %"1836", %"692"
unreachable
}
+
+; An exit for Loop L1 may be the header of a disjoint Loop L2. Thus, when we
+; create PHIs in one of such exits we are also inserting PHIs in L2 header. This
+; could break LCSSA form for L2 because these inserted PHIs can also have uses
+; in L2 exits. Test that we don't assert/crash on that.
+define void @test1() {
+; CHECK-LABEL: @test1
+ br label %lab1
+
+lab1:
+ %tmp21 = add i32 undef, 677038203
+ br i1 undef, label %lab2, label %exit
+
+lab2:
+ indirectbr i8* undef, [label %lab1, label %lab3]
+
+lab3:
+; CHECK: %tmp21.lcssa1 = phi i32 [ %tmp21.lcssa1, %lab4 ], [ %tmp21, %lab2 ]
+ %tmp12 = phi i32 [ %tmp21, %lab2 ], [ %tmp12, %lab4 ]
+ br i1 undef, label %lab5, label %lab4
+
+lab4:
+ br label %lab3
+
+lab5:
+; CHECK: %tmp21.lcssa1.lcssa = phi i32 [ %tmp21.lcssa1, %lab3 ]
+ %tmp15 = add i32 %tmp12, undef
+ br label %exit
+
+exit:
+ ret void
+}
OpenPOWER on IntegriCloud