Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -481,11 +481,19 @@ /// 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. + /// + /// One of the exceptions is when a CFG deletion makes a region + /// forward-unreachable and there is a CFG insertion of an edge that begins + /// above that region. In this case, it is fine to perform that operations and + /// inform the DomTree about them both at the end. + /// It is also 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: lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- lib/Transforms/Scalar/LoopDeletion.cpp +++ lib/Transforms/Scalar/LoopDeletion.cpp @@ -239,7 +239,6 @@ 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. @@ -276,25 +275,22 @@ ++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(); - } + // Update the dominator tree. Disconnect the loop by bypassing the loop body. + // + // This is a special use of the incremental API when a deletion and an + // insertion bypass some region, making it unreachable. In this case, it is + // valid to bundle the updates and inform the DT about both the deletion and + // insertion at the same time, because the incremental algorithm won't be able + // to notice that there was an edge insertion, as it doesn't walk above the + // loop header's subtree and can't possibly discover an outgoing edge from the + // preheader. + DT.deleteEdge(Preheader, L->getHeader()); + DT.insertEdge(Preheader, ExitBlock); + + // 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: unittests/IR/DominatorTreeTest.cpp =================================================================== --- unittests/IR/DominatorTreeTest.cpp +++ unittests/IR/DominatorTreeTest.cpp @@ -529,6 +529,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 a multiple deletions and + // inform the DominatorTree about them of 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"}, @@ -564,6 +594,31 @@ } } +TEST(DominatorTree, ChainedDeletionInsertion) { + CFGHolder Holder; + std::vector Arcs = {{"0", "1"}, {"1", "2"}, {"2", "2"}, + {"2", "3"}, {"3", "1"}, {"3", "4"}}; + + // It is possible to perform a deletion and an insertion in the CFG, and then + // inform the DominatorTree about both of them at the same time, if the + // sequence of the updates bypasses some (newly) unreachable region. + std::vector Updates = {{Delete, {"1", "2"}}, + {Insert, {"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.insertEdge(B.getOrAddBlock("1"), B.getOrAddBlock("3")); + + EXPECT_TRUE(DT.verify()); + EXPECT_EQ(DT.getNode(B.getOrAddBlock("2")), nullptr); +} + TEST(DominatorTree, InsertDeleteExhaustive) { std::vector Arcs = { {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},