Index: llvm/trunk/include/llvm/IR/Dominators.h =================================================================== --- llvm/trunk/include/llvm/IR/Dominators.h +++ llvm/trunk/include/llvm/IR/Dominators.h @@ -51,6 +51,12 @@ BasicBlock *From, BasicBlock *To); +extern template void DeleteEdge(BBDomTree &DT, BasicBlock *From, + BasicBlock *To); +extern template void DeleteEdge(BBPostDomTree &DT, + BasicBlock *From, + BasicBlock *To); + extern template bool Verify(const BBDomTree &DT); extern template bool Verify(const BBPostDomTree &DT); } // namespace DomTreeBuilder Index: llvm/trunk/include/llvm/Support/GenericDomTree.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTree.h +++ llvm/trunk/include/llvm/Support/GenericDomTree.h @@ -194,6 +194,10 @@ void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To); +template +void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To); + template bool Verify(const DomTreeT &DT); } // namespace DomTreeBuilder @@ -211,6 +215,8 @@ DenseMap>>; DomTreeNodeMapType DomTreeNodes; DomTreeNodeBase *RootNode; + using ParentPtr = decltype(std::declval()->getParent()); + ParentPtr Parent = nullptr; mutable bool DFSInfoValid = false; mutable unsigned int SlowQueries = 0; @@ -229,18 +235,20 @@ DominatorTreeBase(DominatorTreeBase &&Arg) : Roots(std::move(Arg.Roots)), DomTreeNodes(std::move(Arg.DomTreeNodes)), - RootNode(std::move(Arg.RootNode)), - DFSInfoValid(std::move(Arg.DFSInfoValid)), - SlowQueries(std::move(Arg.SlowQueries)) { + RootNode(Arg.RootNode), + Parent(Arg.Parent), + DFSInfoValid(Arg.DFSInfoValid), + SlowQueries(Arg.SlowQueries) { Arg.wipe(); } DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { Roots = std::move(RHS.Roots); DomTreeNodes = std::move(RHS.DomTreeNodes); - RootNode = std::move(RHS.RootNode); - DFSInfoValid = std::move(RHS.DFSInfoValid); - SlowQueries = std::move(RHS.SlowQueries); + RootNode = RHS.RootNode; + Parent = RHS.Parent; + DFSInfoValid = RHS.DFSInfoValid; + SlowQueries = RHS.SlowQueries; RHS.wipe(); return *this; } @@ -261,6 +269,7 @@ /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(const DominatorTreeBase &Other) const { + if (Parent != Other.Parent) return true; const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; if (DomTreeNodes.size() != OtherDomTreeNodes.size()) @@ -453,15 +462,37 @@ /// This function has to be called just before or just after making the update /// on the actual CFG. There cannot be any other updates that the dominator /// tree doesn't know about. + /// /// Note that for postdominators it automatically takes care of inserting /// a reverse edge internally (so there's no need to swap the parameters). /// void insertEdge(NodeT *From, NodeT *To) { assert(From); assert(To); + assert(From->getParent() == Parent); + assert(To->getParent() == Parent); DomTreeBuilder::InsertEdge(*this, From, To); } + /// 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 (domominator) subtree unreachable -- in + /// this case, it is fine to perform deletions within this subtree. + /// + /// Note that for postdominators it automatically takes care of deleting + /// a reverse edge internally (so there's no need to swap the parameters). + /// + void deleteEdge(NodeT *From, NodeT *To) { + assert(From); + assert(To); + assert(From->getParent() == Parent); + assert(To->getParent() == Parent); + DomTreeBuilder::DeleteEdge(*this, From, To); + } + /// Add a new node to the dominator tree information. /// /// This creates a new node as a child of DomBB dominator node, linking it @@ -622,6 +653,7 @@ template void recalculate(FT &F) { using TraitsTy = GraphTraits; reset(); + Parent = &F; if (!IsPostDominator) { // Initialize root @@ -647,6 +679,7 @@ DomTreeNodes.clear(); Roots.clear(); RootNode = nullptr; + Parent = nullptr; DFSInfoValid = false; SlowQueries = 0; } @@ -728,6 +761,7 @@ void wipe() { DomTreeNodes.clear(); RootNode = nullptr; + Parent = nullptr; } }; Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h @@ -106,7 +106,7 @@ // Add a new tree node for this NodeT, and link it as a child of // IDomNode return (DT.DomTreeNodes[BB] = IDomNode->addChild( - llvm::make_unique>(BB, IDomNode))) + llvm::make_unique>(BB, IDomNode))) .get(); } @@ -327,6 +327,17 @@ } } + void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) { + NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock(); + for (size_t i = 1, e = NumToNode.size(); i != e; ++i) { + const NodePtr N = NumToNode[i]; + const TreeNodePtr TN = DT.getNode(N); + assert(TN); + const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom); + TN->setIDom(NewIDom); + } + } + // Helper struct used during edge insertions. struct InsertionInfo { using BucketElementTy = std::pair; @@ -338,7 +349,7 @@ }; std::priority_queue, - DecreasingLevel> + DecreasingLevel> Bucket; // Queue of tree nodes sorted by level in descending order. SmallDenseSet Affected; SmallDenseSet Visited; @@ -415,7 +426,7 @@ assert(TN->getBlock()); for (const NodePtr Succ : - ChildrenGetter::Get(TN->getBlock())) { + ChildrenGetter::Get(TN->getBlock())) { const TreeNodePtr SuccTN = DT.getNode(Succ); assert(SuccTN && "Unreachable successor found at reachable insertion"); const unsigned SuccLevel = SuccTN->getLevel(); @@ -468,7 +479,7 @@ } } - // Handles insertion to previousely unreachable nodes. + // Handles insertion to previously unreachable nodes. static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From, const NodePtr To) { DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From) @@ -498,7 +509,7 @@ static void ComputeUnreachableDominators( DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl> - &DiscoveredConnectingEdges) { + &DiscoveredConnectingEdges) { assert(!DT.getNode(Root) && "Root must not be reachable"); // Visit only previously unreachable nodes. @@ -554,6 +565,201 @@ return true; } + static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { + assert(From && To && "Cannot disconnect nullptrs"); + DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> " + << BlockNamePrinter(To) << "\n"); + const TreeNodePtr FromTN = DT.getNode(From); + // Deletion in an unreachable subtree -- nothing to do. + if (!FromTN) return; + + const TreeNodePtr ToTN = DT.getNode(To); + const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); + const TreeNodePtr NCD = DT.getNode(NCDBlock); + + // To dominates From -- nothing to do. + if (ToTN == NCD) return; + + const TreeNodePtr ToIDom = ToTN->getIDom(); + DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom " + << BlockNamePrinter(ToIDom) << "\n"); + + // To remains reachable after deletion. + // (Based on the caption under Figure 4. from the second paper.) + if (FromTN != ToIDom || HasProperSupport(DT, ToTN)) + DeleteReachable(DT, FromTN, ToTN); + else + DeleteUnreachable(DT, ToTN); + } + + // Handles deletions that leave destination nodes reachable. + static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN, + const TreeNodePtr ToTN) { + DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> " + << BlockNamePrinter(ToTN) << "\n"); + DEBUG(dbgs() << "\tRebuilding subtree\n"); + + // Find the top of the subtree that needs to be rebuilt. + // (Based on the lemma 2.6 from the second paper.) + const NodePtr ToIDom = + DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock()); + assert(ToIDom || DT.isPostDominator()); + const TreeNodePtr ToIDomTN = DT.getNode(ToIDom); + assert(ToIDomTN); + const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom(); + // Top of the subtree to rebuild is the root node. Rebuild the tree from + // scratch. + if (!PrevIDomSubTree) { + DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); + DT.recalculate(*DT.Parent); + return; + } + + // Only visit nodes in the subtree starting at To. + const unsigned Level = ToIDomTN->getLevel(); + auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) { + return DT.getNode(To)->getLevel() > Level; + }; + + DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n"); + + SemiNCAInfo SNCA; + SNCA.runDFS(ToIDom, 0, DescendBelow, 0); + DEBUG(dbgs() << "\tRunning Semi-NCA\n"); + SNCA.runSemiNCA(DT, Level); + SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); + } + + // Checks if a node has proper support, as defined on the page 3 and later + // explained on the page 7 of the second paper. + static bool HasProperSupport(DomTreeT &DT, const TreeNodePtr TN) { + DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n"); + for (const NodePtr Pred : + ChildrenGetter::Get(TN->getBlock())) { + DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); + if (!DT.getNode(Pred)) continue; + + const NodePtr Support = + DT.findNearestCommonDominator(TN->getBlock(), Pred); + DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n"); + if (Support != TN->getBlock()) { + DEBUG(dbgs() << "\t" << BlockNamePrinter(TN) + << " is reachable from support " + << BlockNamePrinter(Support) << "\n"); + return true; + } + } + + return false; + } + + // Handle deletions that make destination node unreachable. + // (Based on the lemma 2.7 from the second paper.) + static void DeleteUnreachable(DomTreeT &DT, const TreeNodePtr ToTN) { + DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN) + << "\n"); + assert(ToTN); + assert(ToTN->getBlock()); + + SmallVector AffectedQueue; + const unsigned Level = ToTN->getLevel(); + + // Traverse destination node's descendants with greater level in the tree + // and collect visited nodes. + auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) { + const TreeNodePtr TN = DT.getNode(To); + assert(TN); + if (TN->getLevel() > Level) return true; + if (llvm::find(AffectedQueue, To) == AffectedQueue.end()) + AffectedQueue.push_back(To); + + return false; + }; + + SemiNCAInfo SNCA; + unsigned LastDFSNum = + SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0); + + TreeNodePtr MinNode = ToTN; + + // Identify the top of the subtree to rebuilt by finding the NCD of all + // the affected nodes. + for (const NodePtr N : AffectedQueue) { + const TreeNodePtr TN = DT.getNode(N); + const NodePtr NCDBlock = + DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock()); + assert(NCDBlock || DT.isPostDominator()); + const TreeNodePtr NCD = DT.getNode(NCDBlock); + assert(NCD); + + DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN) + << " with NCD = " << BlockNamePrinter(NCD) + << ", MinNode =" << BlockNamePrinter(MinNode) << "\n"); + if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD; + } + + // Root reached, rebuild the whole tree from scratch. + if (!MinNode->getIDom()) { + DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); + DT.recalculate(*DT.Parent); + return; + } + + // Erase the unreachable subtree in reverse preorder to process all children + // before deleting their parent. + for (unsigned i = LastDFSNum; i > 0; --i) { + const NodePtr N = SNCA.NumToNode[i]; + const TreeNodePtr TN = DT.getNode(N); + DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n"); + + EraseNode(DT, TN); + } + + // The affected subtree start at the To node -- there's no extra work to do. + if (MinNode == ToTN) return; + + DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = " + << BlockNamePrinter(MinNode) << "\n"); + const unsigned MinLevel = MinNode->getLevel(); + const TreeNodePtr PrevIDom = MinNode->getIDom(); + assert(PrevIDom); + SNCA.clear(); + + // Identify nodes that remain in the affected subtree. + auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) { + const TreeNodePtr ToTN = DT.getNode(To); + return ToTN && ToTN->getLevel() > MinLevel; + }; + SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0); + + DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom) + << "\nRunning Semi-NCA\n"); + + // Rebuild the remaining part of affected subtree. + SNCA.runSemiNCA(DT, MinLevel); + SNCA.reattachExistingSubtree(DT, PrevIDom); + } + + // Removes leaf tree nodes from the dominator tree. + static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) { + assert(TN); + assert(TN->getNumChildren() == 0 && "Not a tree leaf"); + + const TreeNodePtr IDom = TN->getIDom(); + assert(IDom); + + auto ChIt = llvm::find(IDom->Children, TN); + assert(ChIt != IDom->Children.end()); + std::swap(*ChIt, IDom->Children.back()); + IDom->Children.pop_back(); + + DT.DomTreeNodes.erase(TN->getBlock()); + } + + //~~ + //===--------------- DomTree correctness verification ---------------------=== + //~~ + // Check if for every parent with a level L in the tree all of its children // have level L + 1. static bool VerifyLevels(const DomTreeT &DT) { @@ -740,6 +946,13 @@ } template +void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To) { + if (DT.isPostDominator()) std::swap(From, To); + SemiNCAInfo::DeleteEdge(DT, From, To); +} + +template bool Verify(const DomTreeT &DT) { SemiNCAInfo SNCA; return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && Index: llvm/trunk/lib/IR/Dominators.cpp =================================================================== --- llvm/trunk/lib/IR/Dominators.cpp +++ llvm/trunk/lib/IR/Dominators.cpp @@ -76,6 +76,11 @@ template void llvm::DomTreeBuilder::InsertEdge( DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::DeleteEdge( + DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::DeleteEdge( + DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); + template bool llvm::DomTreeBuilder::Verify( const DomTreeBuilder::BBDomTree &DT); template bool llvm::DomTreeBuilder::Verify( Index: llvm/trunk/unittests/IR/DominatorTreeTest.cpp =================================================================== --- llvm/trunk/unittests/IR/DominatorTreeTest.cpp +++ llvm/trunk/unittests/IR/DominatorTreeTest.cpp @@ -327,6 +327,7 @@ namespace { const auto Insert = CFGBuilder::ActionKind::Insert; +const auto Delete = CFGBuilder::ActionKind::Delete; bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { return std::tie(A.Action, A.Edge.From, A.Edge.To) < @@ -448,3 +449,129 @@ } } } + +TEST(DominatorTree, DeleteReachable) { + CFGHolder Holder; + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"2", "4"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, + {"5", "7"}, {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; + + std::vector Updates = { + {Delete, {"2", "4"}}, {Delete, {"7", "8"}}, {Delete, {"10", "2"}}}; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + Optional LastUpdate; + while ((LastUpdate = B.applyUpdate())) { + EXPECT_EQ(LastUpdate->Action, Delete); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.deleteEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.deleteEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, DeleteUnreachable) { + CFGHolder Holder; + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, + {"7", "8"}, {"3", "8"}, {"8", "9"}, {"9", "10"}, {"10", "2"}}; + + std::vector Updates = { + {Delete, {"8", "9"}}, {Delete, {"7", "8"}}, {Delete, {"3", "4"}}}; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + Optional LastUpdate; + while ((LastUpdate = B.applyUpdate())) { + EXPECT_EQ(LastUpdate->Action, Delete); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.deleteEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.deleteEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, InsertDelete) { + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, + {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; + + std::vector Updates = { + {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, + {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, + {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, + {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; + + CFGHolder Holder; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + Optional LastUpdate; + while ((LastUpdate = B.applyUpdate())) { + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + if (LastUpdate->Action == Insert) { + DT.insertEdge(From, To); + PDT.insertEdge(From, To); + } else { + DT.deleteEdge(From, To); + PDT.deleteEdge(From, To); + } + + EXPECT_TRUE(DT.verify()); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, InsertDeleteExhaustive) { + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"}, + {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}}; + + std::vector Updates = { + {Insert, {"2", "4"}}, {Insert, {"12", "10"}}, {Insert, {"10", "9"}}, + {Insert, {"7", "6"}}, {Insert, {"7", "5"}}, {Delete, {"3", "8"}}, + {Insert, {"10", "7"}}, {Insert, {"2", "8"}}, {Delete, {"3", "4"}}, + {Delete, {"8", "9"}}, {Delete, {"11", "12"}}}; + + std::mt19937 Generator(0); + for (unsigned i = 0; i < 16; ++i) { + std::shuffle(Updates.begin(), Updates.end(), Generator); + CFGHolder Holder; + CFGBuilder B(Holder.F, Arcs, Updates); + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + Optional LastUpdate; + while ((LastUpdate = B.applyUpdate())) { + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + if (LastUpdate->Action == Insert) { + DT.insertEdge(From, To); + PDT.insertEdge(From, To); + } else { + DT.deleteEdge(From, To); + PDT.deleteEdge(From, To); + } + + EXPECT_TRUE(DT.verify()); + EXPECT_TRUE(PDT.verify()); + } + } +}