summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Support/GenericDomTree.h14
-rw-r--r--llvm/lib/Transforms/Scalar/LoopDeletion.cpp61
-rw-r--r--llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll56
-rw-r--r--llvm/unittests/IR/DominatorTreeTest.cpp30
4 files changed, 136 insertions, 25 deletions
diff --git a/llvm/include/llvm/Support/GenericDomTree.h b/llvm/include/llvm/Support/GenericDomTree.h
index 8e5e4123002..6f9a6805f4f 100644
--- a/llvm/include/llvm/Support/GenericDomTree.h
+++ b/llvm/include/llvm/Support/GenericDomTree.h
@@ -481,11 +481,15 @@ class DominatorTreeBase {
/// Inform the dominator tree about a CFG edge deletion and update the tree.
///
- /// This function has to be called just after making the update
- /// on the actual CFG. There cannot be any other updates that the dominator
- /// tree doesn't know about. The only exception is when the deletion that the
- /// tree is informed about makes some (dominator) subtree unreachable -- in
- /// this case, it is fine to perform deletions within this subtree.
+ /// This function has to be called just after making the update on the actual
+ /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
+ /// DEBUG mode. There cannot be any other updates that the
+ /// dominator tree doesn't know about.
+ ///
+ /// However, it is fine to perform multiple CFG deletions that make different
+ /// subtrees forward-unreachable and to inform the DomTree about them all at
+ /// the same time, as the incremental algorithm doesn't walk the tree above
+ /// the NearestCommonDominator of a deleted edge
///
/// Note that for postdominators it automatically takes care of deleting
/// a reverse edge internally (so there's no need to swap the parameters).
diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
index ac4dd44a0e9..cf452aa6396 100644
--- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp
@@ -239,17 +239,44 @@ static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
auto *ExitBlock = L->getUniqueExitBlock();
assert(ExitBlock && "Should have a unique exit block!");
-
assert(L->hasDedicatedExits() && "Loop should have dedicated exits!");
- // Connect the preheader directly to the exit block.
+ auto *OldBr = dyn_cast<BranchInst>(Preheader->getTerminator());
+ assert(OldBr && "Preheader must end with a branch");
+ assert(OldBr->isUnconditional() && "Preheader must have a single successor");
+ // Connect the preheader to the exit block. Keep the old edge to the header
+ // around to perform the dominator tree update in two separate steps
+ // -- #1 insertion of the edge preheader -> exit and #2 deletion of the edge
+ // preheader -> header.
+ //
+ //
+ // 0. Preheader 1. Preheader 2. Preheader
+ // | | | |
+ // V | V |
+ // Header <--\ | Header <--\ | Header <--\
+ // | | | | | | | | | | |
+ // | V | | | V | | | V |
+ // | Body --/ | | Body --/ | | Body --/
+ // V V V V V
+ // Exit Exit Exit
+ //
+ // By doing this is two separate steps we can perform the dominator tree
+ // update without using the batch update API.
+ //
// Even when the loop is never executed, we cannot remove the edge from the
// source block to the exit block. Consider the case where the unexecuted loop
// branches back to an outer loop. If we deleted the loop and removed the edge
// coming to this inner loop, this will break the outer loop structure (by
// deleting the backedge of the outer loop). If the outer loop is indeed a
// non-loop, it will be deleted in a future iteration of loop deletion pass.
- Preheader->getTerminator()->replaceUsesOfWith(L->getHeader(), ExitBlock);
+ IRBuilder<> Builder(OldBr);
+ Builder.CreateCondBr(Builder.getFalse(), L->getHeader(), ExitBlock);
+ // Remove the old branch. The conditional branch becomes a new terminator.
+ OldBr->eraseFromParent();
+
+ // Update the dominator tree by informing it about the new edge from the
+ // preheader to the exit.
+ DT.insertEdge(Preheader, ExitBlock);
// Rewrite phis in the exit block to get their inputs from the Preheader
// instead of the exiting block.
@@ -276,25 +303,19 @@ static void deleteDeadLoop(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
++BI;
}
- // Update the dominator tree and remove the instructions and blocks that will
- // be deleted from the reference counting scheme.
- SmallVector<DomTreeNode*, 8> ChildNodes;
- for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end();
- LI != LE; ++LI) {
- // Move all of the block's children to be children of the Preheader, which
- // allows us to remove the domtree entry for the block.
- ChildNodes.insert(ChildNodes.begin(), DT[*LI]->begin(), DT[*LI]->end());
- for (DomTreeNode *ChildNode : ChildNodes) {
- DT.changeImmediateDominator(ChildNode, DT[Preheader]);
- }
+ // Disconnect the loop body by branching directly to its exit.
+ Builder.SetInsertPoint(Preheader->getTerminator());
+ Builder.CreateBr(ExitBlock);
+ // Remove the old branch.
+ Preheader->getTerminator()->eraseFromParent();
- ChildNodes.clear();
- DT.eraseNode(*LI);
+ // Inform the dominator tree about the removed edge.
+ DT.deleteEdge(Preheader, L->getHeader());
- // Remove the block from the reference counting scheme, so that we can
- // delete it freely later.
- (*LI)->dropAllReferences();
- }
+ // Remove the block from the reference counting scheme, so that we can
+ // delete it freely later.
+ for (auto *Block : L->blocks())
+ Block->dropAllReferences();
// Erase the instructions and the blocks without having to worry
// about ordering because we already dropped the references.
diff --git a/llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll b/llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll
new file mode 100644
index 00000000000..ad4e434c11d
--- /dev/null
+++ b/llvm/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll
@@ -0,0 +1,56 @@
+; RUN: opt < %s -loop-deletion -S
+; RUN: opt < %s -loop-deletion -analyze -domtree 2>&1 | FileCheck -check-prefix=DT %s
+; RUN: opt < %s -loop-deletion -analyze -verify-dom-info
+
+; CHECK: for.body
+; CHECK-NOT: for.cond1
+
+; Verify only the important parts of the DomTree.
+; DT: [1] %entry
+; DT: [2] %for.cond
+; DT: [3] %lbl63A679E5
+; DT: [3] %for.cond9
+; DT: [3] %lbl64774A9B
+; DT: [3] %for.body
+; DT: [4] %for.cond3.loopexit
+
+define i32 @fn1() {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %entry
+ br i1 undef, label %lbl63A679E5, label %for.body
+
+for.body: ; preds = %for.cond
+ br label %for.cond1
+
+for.cond1: ; preds = %for.cond1, %for.body
+ br i1 undef, label %for.cond1, label %for.cond3.loopexit
+
+for.cond3.loopexit: ; preds = %for.cond1
+ br label %for.cond3
+
+for.cond3: ; preds = %for.cond9, %for.cond3.loopexit
+ br i1 undef, label %for.body4, label %for.cond17
+
+for.body4: ; preds = %for.cond3
+ br label %for.cond5
+
+for.cond5: ; preds = %lbl63A679E5, %for.body4
+ br label %for.cond9
+
+lbl63A679E5: ; preds = %for.cond
+ br label %for.cond5
+
+for.cond9: ; preds = %for.end14.split, %for.cond5
+ br i1 undef, label %for.cond3, label %lbl64774A9B
+
+lbl64774A9B: ; preds = %for.cond17, %for.cond9
+ br label %for.end14.split
+
+for.end14.split: ; preds = %lbl64774A9B
+ br label %for.cond9
+
+for.cond17: ; preds = %for.cond3
+ br label %lbl64774A9B
+}
diff --git a/llvm/unittests/IR/DominatorTreeTest.cpp b/llvm/unittests/IR/DominatorTreeTest.cpp
index 5856d5539a0..da5d5025e23 100644
--- a/llvm/unittests/IR/DominatorTreeTest.cpp
+++ b/llvm/unittests/IR/DominatorTreeTest.cpp
@@ -797,6 +797,36 @@ TEST(DominatorTree, DeleteUnreachable) {
}
}
+TEST(DominatorTree, DeletionsInSubtrees) {
+ CFGHolder Holder;
+ std::vector<CFGBuilder::Arc> Arcs = {{"0", "1"}, {"1", "2"}, {"1", "3"},
+ {"1", "6"}, {"3", "4"}, {"2", "5"},
+ {"5", "2"}};
+
+ // It is possible to perform multiple deletions and inform the
+ // DominatorTree about them at the same time, if the all of the
+ // deletions happen in different subtrees.
+ std::vector<CFGBuilder::Update> Updates = {{Delete, {"1", "2"}},
+ {Delete, {"1", "3"}}};
+ CFGBuilder B(Holder.F, Arcs, Updates);
+ DominatorTree DT(*Holder.F);
+ EXPECT_TRUE(DT.verify());
+
+ Optional<CFGBuilder::Update> LastUpdate;
+ while ((LastUpdate = B.applyUpdate()))
+ ;
+
+ DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("2"));
+ DT.deleteEdge(B.getOrAddBlock("1"), B.getOrAddBlock("3"));
+
+ EXPECT_TRUE(DT.verify());
+ EXPECT_EQ(DT.getNode(B.getOrAddBlock("2")), nullptr);
+ EXPECT_EQ(DT.getNode(B.getOrAddBlock("3")), nullptr);
+ EXPECT_EQ(DT.getNode(B.getOrAddBlock("4")), nullptr);
+ EXPECT_EQ(DT.getNode(B.getOrAddBlock("5")), nullptr);
+ EXPECT_NE(DT.getNode(B.getOrAddBlock("6")), nullptr);
+}
+
TEST(DominatorTree, InsertDelete) {
std::vector<CFGBuilder::Arc> Arcs = {
{"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},
OpenPOWER on IntegriCloud