Index: llvm/trunk/include/llvm/Support/GenericDomTree.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTree.h +++ llvm/trunk/include/llvm/Support/GenericDomTree.h @@ -481,11 +481,15 @@ /// 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). Index: llvm/trunk/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopDeletion.cpp @@ -239,17 +239,44 @@ 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(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 @@ ++BI; } - // Update the dominator tree and remove the instructions and blocks that will - // be deleted from the reference counting scheme. - SmallVector 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]); - } - - ChildNodes.clear(); - DT.eraseNode(*LI); - - // Remove the block from the reference counting scheme, so that we can - // delete it freely later. - (*LI)->dropAllReferences(); - } + // Disconnect the loop body by branching directly to its exit. + Builder.SetInsertPoint(Preheader->getTerminator()); + Builder.CreateBr(ExitBlock); + // Remove the old branch. + Preheader->getTerminator()->eraseFromParent(); + + // 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. + 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. Index: llvm/trunk/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll =================================================================== --- llvm/trunk/test/Transforms/LoopDeletion/2017-07-11-incremental-dt.ll +++ llvm/trunk/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 +} Index: llvm/trunk/unittests/IR/DominatorTreeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/DominatorTreeTest.cpp +++ llvm/trunk/unittests/IR/DominatorTreeTest.cpp @@ -797,6 +797,36 @@ } } +TEST(DominatorTree, DeletionsInSubtrees) { + CFGHolder Holder; + std::vector 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 Updates = {{Delete, {"1", "2"}}, + {Delete, {"1", "3"}}}; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + + Optional 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 Arcs = { {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},