Index: llvm/trunk/include/llvm/IR/Dominators.h =================================================================== --- llvm/trunk/include/llvm/IR/Dominators.h +++ llvm/trunk/include/llvm/IR/Dominators.h @@ -45,6 +45,12 @@ extern template void Calculate(BBPostDomTree &DT, Function &F); +extern template void InsertEdge(BBDomTree &DT, BasicBlock *From, + BasicBlock *To); +extern template void InsertEdge(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 @@ -44,11 +44,18 @@ template class DominatorTreeBase; +namespace DomTreeBuilder { +template +struct SemiNCAInfo; +} // namespace DomTreeBuilder + /// \brief Base class for the actual dominator tree node. template class DomTreeNodeBase { friend struct PostDominatorTree; friend class DominatorTreeBase; friend class DominatorTreeBase; + friend struct DomTreeBuilder::SemiNCAInfo>; + friend struct DomTreeBuilder::SemiNCAInfo>; NodeT *TheBB; DomTreeNodeBase *IDom; @@ -179,14 +186,14 @@ } namespace DomTreeBuilder { -template -struct SemiNCAInfo; - -// The calculate routine is provided in a separate header but referenced here. +// The routines below are provided in a separate header but referenced here. template void Calculate(DomTreeT &DT, FuncT &F); -// The verify function is provided in a separate header but referenced here. +template +void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To); + template bool Verify(const DomTreeT &DT); } // namespace DomTreeBuilder @@ -441,6 +448,20 @@ // API to update (Post)DominatorTree information based on modifications to // the CFG... + /// Inform the dominator tree about a CFG edge insertion and update the tree. + /// + /// 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); + DomTreeBuilder::InsertEdge(*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 Index: llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h @@ -20,11 +20,20 @@ /// out that the theoretically slower O(n*log(n)) implementation is actually /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. /// +/// The file uses the Depth Based Search algorithm to perform incremental +/// upates (insertion and deletions). The implemented algorithm is based on this +/// publication: +/// +/// An Experimental Study of Dynamic Dominators +/// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10: +/// https://arxiv.org/pdf/1604.02711.pdf +/// //===----------------------------------------------------------------------===// #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H +#include #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/Debug.h" @@ -54,6 +63,7 @@ using NodePtr = typename DomTreeT::NodePtr; using NodeT = typename DomTreeT::NodeType; using TreeNodePtr = DomTreeNodeBase *; + static constexpr bool IsPostDom = DomTreeT::IsPostDominator; // Information record used by Semi-NCA during tree construction. struct InfoRec { @@ -198,6 +208,7 @@ return VInInfo.Label; } + // This function requires DFS to be run before calling it. void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) { const unsigned NextDFSNum(NumToNode.size()); // Initialize IDoms to spanning tree parents. @@ -315,6 +326,199 @@ } } + // Helper struct used during edge insertions. + struct InsertionInfo { + using BucketElementTy = std::pair; + struct DecreasingLevel { + bool operator()(const BucketElementTy &First, + const BucketElementTy &Second) const { + return First.first > Second.first; + } + }; + + std::priority_queue, + DecreasingLevel> + Bucket; // Queue of tree nodes sorted by level in descending order. + SmallDenseSet Affected; + SmallDenseSet Visited; + SmallVector AffectedQueue; + SmallVector VisitedNotAffectedQueue; + }; + + static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { + assert(From && To && "Cannot connect nullptrs"); + DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> " + << BlockNamePrinter(To) << "\n"); + const TreeNodePtr FromTN = DT.getNode(From); + + // Ignore edges from unreachable nodes. + if (!FromTN) return; + + DT.DFSInfoValid = false; + + const TreeNodePtr ToTN = DT.getNode(To); + if (!ToTN) + InsertUnreachable(DT, FromTN, To); + else + InsertReachable(DT, FromTN, ToTN); + } + + // Handles insertion to a node already in the dominator tree. + static void InsertReachable(DomTreeT &DT, const TreeNodePtr From, + const TreeNodePtr To) { + DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) + << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); + const NodePtr NCDBlock = + DT.findNearestCommonDominator(From->getBlock(), To->getBlock()); + assert(NCDBlock || DT.isPostDominator()); + const TreeNodePtr NCD = DT.getNode(NCDBlock); + assert(NCD); + + DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n"); + const TreeNodePtr ToIDom = To->getIDom(); + + // Nothing affected -- NCA property holds. + // (Based on the lemma 2.5 from the second paper.) + if (NCD == To || NCD == ToIDom) return; + + // Identify and collect affected nodes. + InsertionInfo II; + DEBUG(dbgs() << "Marking " << BlockNamePrinter(To) << " as affected\n"); + II.Affected.insert(To); + const unsigned ToLevel = To->getLevel(); + DEBUG(dbgs() << "Putting " << BlockNamePrinter(To) << " into a Bucket\n"); + II.Bucket.push({ToLevel, To}); + + while (!II.Bucket.empty()) { + const TreeNodePtr CurrentNode = II.Bucket.top().second; + II.Bucket.pop(); + DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: " + << BlockNamePrinter(CurrentNode) << "\n"); + II.Visited.insert(CurrentNode); + II.AffectedQueue.push_back(CurrentNode); + + // Discover and collect affected successors of the current node. + VisitInsertion(DT, CurrentNode, ToLevel, NCD, II); + } + + // Finish by updating immediate dominators and levels. + UpdateInsertion(DT, NCD, II); + } + + // Visits an affected node and collect its affected successors. + static void VisitInsertion(DomTreeT &DT, const TreeNodePtr TN, + const unsigned RootLevel, const TreeNodePtr NCD, + InsertionInfo &II) { + const unsigned NCDLevel = NCD->getLevel(); + DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << "\n"); + + assert(TN->getBlock()); + for (const NodePtr Succ : + ChildrenGetter::Get(TN->getBlock())) { + const TreeNodePtr SuccTN = DT.getNode(Succ); + assert(SuccTN && "Unreachable successor found at reachable insertion"); + const unsigned SuccLevel = SuccTN->getLevel(); + + DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ) + << ", level = " << SuccLevel << "\n"); + + // Succ dominated by subtree From -- not affected. + // (Based on the lemma 2.5 from the second paper.) + if (SuccLevel > RootLevel) { + DEBUG(dbgs() << "\t\tDominated by subtree From\n"); + if (II.Visited.count(SuccTN) != 0) continue; + + DEBUG(dbgs() << "\t\tMarking visited not affected " + << BlockNamePrinter(Succ) << "\n"); + II.Visited.insert(SuccTN); + II.VisitedNotAffectedQueue.push_back(SuccTN); + VisitInsertion(DT, SuccTN, RootLevel, NCD, II); + } else if ((SuccLevel > NCDLevel + 1) && II.Affected.count(SuccTN) == 0) { + DEBUG(dbgs() << "\t\tMarking affected and adding " + << BlockNamePrinter(Succ) << " to a Bucket\n"); + II.Affected.insert(SuccTN); + II.Bucket.push({SuccLevel, SuccTN}); + } + } + } + + // Updates immediate dominators and levels after insertion. + static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD, + InsertionInfo &II) { + DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n"); + + for (const TreeNodePtr TN : II.AffectedQueue) { + DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN) + << ") = " << BlockNamePrinter(NCD) << "\n"); + TN->setIDom(NCD); + } + + UpdateLevelsAfterInsertion(II); + } + + static void UpdateLevelsAfterInsertion(InsertionInfo &II) { + DEBUG(dbgs() << "Updating levels for visited but not affected nodes\n"); + + for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) { + DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = (" + << BlockNamePrinter(TN->getIDom()) << ") " + << TN->getIDom()->getLevel() << " + 1\n"); + TN->UpdateLevel(); + } + } + + // Handles insertion to previousely unreachable nodes. + static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From, + const NodePtr To) { + DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From) + << " -> (unreachable) " << BlockNamePrinter(To) << "\n"); + + // Collect discovered edges to already reachable nodes. + SmallVector, 8> DiscoveredEdgesToReachable; + // Discover and connect nodes that became reachable with the insertion. + ComputeUnreachableDominators(DT, To, From, DiscoveredEdgesToReachable); + + DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From) + << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n"); + + DEBUG(DT.print(dbgs())); + + // Used the discovered edges and inset discovered connecting (incoming) + // edges. + for (const auto &Edge : DiscoveredEdgesToReachable) { + DEBUG(dbgs() << "\tInserting discovered connecting edge " + << BlockNamePrinter(Edge.first) << " -> " + << BlockNamePrinter(Edge.second) << "\n"); + InsertReachable(DT, DT.getNode(Edge.first), Edge.second); + } + } + + // Connects nodes that become reachable with an insertion. + static void ComputeUnreachableDominators( + DomTreeT &DT, const NodePtr Root, const TreeNodePtr Incoming, + SmallVectorImpl> + &DiscoveredConnectingEdges) { + assert(!DT.getNode(Root) && "Root must not be reachable"); + + // Visit only previously unreachable nodes. + auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From, + NodePtr To) { + const TreeNodePtr ToTN = DT.getNode(To); + if (!ToTN) return true; + + DiscoveredConnectingEdges.push_back({From, ToTN}); + return false; + }; + + SemiNCAInfo SNCA; + SNCA.runDFS(Root, 0, UnreachableDescender, 0); + SNCA.runSemiNCA(DT); + SNCA.attachNewSubtree(DT, Incoming); + + DEBUG(dbgs() << "After adding unreachable nodes\n"); + DEBUG(DT.print(dbgs())); + } + // Checks if the tree contains all reachable nodes in the input graph. bool verifyReachability(const DomTreeT &DT) { clear(); @@ -528,6 +732,13 @@ } template +void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, + typename DomTreeT::NodePtr To) { + if (DT.isPostDominator()) std::swap(From, To); + SemiNCAInfo::InsertEdge(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 @@ -71,6 +71,11 @@ llvm::DomTreeBuilder::Calculate( DomTreeBuilder::BBPostDomTree &DT, Function &F); +template void llvm::DomTreeBuilder::InsertEdge( + DomTreeBuilder::BBDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::InsertEdge( + 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 @@ -15,6 +15,7 @@ #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/Support/SourceMgr.h" +#include "CFGBuilder.h" #include "gtest/gtest.h" using namespace llvm; @@ -323,3 +324,127 @@ EXPECT_FALSE(DT->dominates(Edge_BB0_BB1_b, BB2)); }); } + +namespace { +const auto Insert = CFGBuilder::ActionKind::Insert; + +bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { + return std::tie(A.Action, A.Edge.From, A.Edge.To) < + std::tie(B.Action, B.Edge.From, B.Edge.To); +}; +} // namespace + +TEST(DominatorTree, InsertReachable) { + CFGHolder Holder; + 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, {"12", "10"}}, + {Insert, {"10", "9"}}, + {Insert, {"7", "6"}}, + {Insert, {"7", "5"}}}; + 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, Insert); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.insertEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.insertEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, InsertUnreachable) { + CFGHolder Holder; + std::vector Arcs = {{"1", "2"}, {"2", "3"}, {"3", "4"}, + {"5", "6"}, {"5", "7"}, {"3", "8"}, + {"9", "10"}, {"11", "12"}}; + + std::vector Updates = {{Insert, {"4", "5"}}, + {Insert, {"8", "9"}}, + {Insert, {"10", "12"}}, + {Insert, {"10", "11"}}}; + 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, Insert); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.insertEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.insertEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, InsertMixed) { + CFGHolder Holder; + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, + {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; + + std::vector Updates = { + {Insert, {"4", "5"}}, {Insert, {"2", "5"}}, {Insert, {"10", "9"}}, + {Insert, {"12", "10"}}, {Insert, {"12", "10"}}, {Insert, {"7", "8"}}, + {Insert, {"7", "5"}}}; + 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, Insert); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.insertEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.insertEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } +} + +TEST(DominatorTree, InsertPermut) { + std::vector Arcs = { + {"1", "2"}, {"2", "3"}, {"3", "4"}, {"5", "6"}, {"5", "7"}, + {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}, {"7", "3"}}; + + std::vector Updates = {{Insert, {"4", "5"}}, + {Insert, {"2", "5"}}, + {Insert, {"10", "9"}}, + {Insert, {"12", "10"}}}; + + while (std::next_permutation(Updates.begin(), Updates.end(), CompUpdates)) { + 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())) { + EXPECT_EQ(LastUpdate->Action, Insert); + BasicBlock *From = B.getOrAddBlock(LastUpdate->Edge.From); + BasicBlock *To = B.getOrAddBlock(LastUpdate->Edge.To); + DT.insertEdge(From, To); + EXPECT_TRUE(DT.verify()); + PDT.insertEdge(From, To); + EXPECT_TRUE(PDT.verify()); + } + } +}