Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -41,6 +41,10 @@ using BBDomTree = DomTreeBase; using BBPostDomTree = PostDomTreeBase; +extern template struct Update; + +using BBUpdates = ArrayRef>; + extern template void Calculate(BBDomTree &DT); extern template void Calculate(BBPostDomTree &DT); @@ -56,6 +60,9 @@ BasicBlock *From, BasicBlock *To); +extern template void ApplyUpdates(BBDomTree &DT, BBUpdates); +extern template void ApplyUpdates(BBPostDomTree &DT, BBUpdates); + extern template bool Verify(const BBDomTree &DT); extern template bool Verify(const BBPostDomTree &DT); } // namespace DomTreeBuilder Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -24,12 +24,6 @@ #ifndef LLVM_SUPPORT_GENERICDOMTREE_H #define LLVM_SUPPORT_GENERICDOMTREE_H -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/raw_ostream.h" #include #include #include @@ -38,6 +32,13 @@ #include #include #include +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/raw_ostream.h" namespace llvm { @@ -45,7 +46,7 @@ class DominatorTreeBase; namespace DomTreeBuilder { -template +template struct SemiNCAInfo; } // namespace DomTreeBuilder @@ -190,14 +191,48 @@ template void Calculate(DomTreeT &DT); -template +template void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To); -template +template void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To); +// UpdateKind and Update are used by the batch update API and it's easiest to +// define them here. +enum class UpdateKind : unsigned char { Insert, Delete }; + +template +struct Update { + using NodeKindPair = PointerIntPair; + + NodePtr From; + NodeKindPair ToAndKind; + + Update(UpdateKind Kind, NodePtr From, NodePtr To) + : From(From), ToAndKind(To, Kind) {} + + UpdateKind getKind() const { return ToAndKind.getInt(); } + NodePtr getFrom() const { return From; } + NodePtr getTo() const { return ToAndKind.getPointer(); } + bool operator==(const Update &RHS) const { + return From == RHS.From && ToAndKind == RHS.ToAndKind; + } + + friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) { + OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete "); + U.getFrom()->printAsOperand(OS, false); + OS << " -> "; + U.getTo()->printAsOperand(OS, false); + return OS; + } +}; + +template +void ApplyUpdates(DomTreeT &DT, + ArrayRef Updates); + template bool Verify(const DomTreeT &DT); } // namespace DomTreeBuilder @@ -219,6 +254,11 @@ using ParentType = typename std::remove_pointer::type; static constexpr bool IsPostDominator = IsPostDom; + using UpdateType = DomTreeBuilder::Update; + using UpdateKind = DomTreeBuilder::UpdateKind; + static constexpr UpdateKind Insert = UpdateKind::Insert; + static constexpr UpdateKind Delete = UpdateKind::Delete; + protected: // Dominators always have a single root, postdominators can have more. SmallVector Roots; @@ -463,6 +503,39 @@ // API to update (Post)DominatorTree information based on modifications to // the CFG... + /// Inform the dominator tree about a sequence of CFG edge insertions and + /// deletions and perform a batch update on the tree. + /// + /// This function should be used when there were multiple CFG updates after + /// the last dominator tree update. It takes care of performing the updates + /// in sync with the CFG and optimizes away the redundant operations that + /// cancel each other. + /// The functions expects the sequence of updates to be balanced. Eg.: + /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because + /// logically it results in a single insertions. + /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make + /// sense to insert the same edge twice. + /// + /// What's more, the functions assumes that it's safe to ask every node in the + /// CFG about its children and inverse children. This implies that deletions + /// of CFG edges must not delete the CFG nodes before calling this function. + /// + /// Batch updates should be generally faster when performing longer sequences + /// of updates than calling insertEdge/deleteEdge manually multiple times, as + /// they can reorder the updates and remove redundant ones internally. + /// + /// Note that for postdominators it automatically takes care of applying + /// updates on reverse edges internally (so there's no need to swap the + /// From and To pointers when constructing DominatorTree::UpdateType). + /// The type of updates is the same for DomTreeBase and PostDomTreeBase + /// with the same template parameter T. + /// + /// \param Updates An unordered sequence of updates to perform. + /// + void applyUpdates(ArrayRef Updates) { + DomTreeBuilder::ApplyUpdates(*this, Updates); + } + /// 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 @@ -487,11 +560,6 @@ /// 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). /// @@ -669,7 +737,6 @@ /// recalculate - compute a dominator tree for the given function void recalculate(ParentType &Func) { - reset(); Parent = &Func; DomTreeBuilder::Calculate(*this); } Index: include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- include/llvm/Support/GenericDomTreeConstruction.h +++ include/llvm/Support/GenericDomTreeConstruction.h @@ -34,8 +34,10 @@ #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H #include +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/Debug.h" #include "llvm/Support/GenericDomTree.h" @@ -45,20 +47,6 @@ namespace llvm { namespace DomTreeBuilder { -template -struct ChildrenGetter { - static auto Get(NodePtr N) -> decltype(reverse(children(N))) { - return reverse(children(N)); - } -}; - -template -struct ChildrenGetter { - static auto Get(NodePtr N) -> decltype(inverse_children(N)) { - return inverse_children(N); - } -}; - template struct SemiNCAInfo { using NodePtr = typename DomTreeT::NodePtr; @@ -82,11 +70,100 @@ std::vector NumToNode = {nullptr}; DenseMap NodeToInfo; + using UpdateT = typename DomTreeT::UpdateType; + struct BatchUpdateInfo { + SmallVector Updates; + using NodePtrAndKind = PointerIntPair; + + // In order to be able to walk a CFG that is out of sync with the CFG + // DominatorTree last knew about, use the list of updates to reconstruct + // previous CFG versions of the current CFG. For each node, we store a set + // of its virtually added/deleted future successors and predecessors. + // Note that these children are from the future relative to what the + // DominatorTree knows about -- using them to gets us some snapshot of the + // CFG from the past (relative to the state of the CFG). + DenseMap> FutureSuccessors; + DenseMap> FuturePredecessors; + // Remembers if the whole tree was recalculated at some point during the + // current batch update. + bool IsRecalculated = false; + }; + + BatchUpdateInfo *BatchUpdates; + using BatchUpdatePtr = BatchUpdateInfo *; + + // If BUI is a nullptr, then there's no batch update in progress. + SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {} + void clear() { NumToNode = {nullptr}; // Restore to initial state with a dummy start node. NodeToInfo.clear(); + // Don't reset the pointer to BatchUpdateInfo here -- if there's an update + // in progress, we need this information to continue it. } + template + struct ChildrenGetter { + using ResultTy = SmallVector; + + static ResultTy Get(NodePtr N, std::integral_constant) { + auto RChildren = reverse(children(N)); + return ResultTy(RChildren.begin(), RChildren.end()); + } + + static ResultTy Get(NodePtr N, std::integral_constant) { + auto IChildren = inverse_children(N); + return ResultTy(IChildren.begin(), IChildren.end()); + } + + using Tag = std::integral_constant; + + // The function below is the core part of the batch updater. It allows the + // Depth Based Search algorithm to perform incremental updates in lockstep + // with updates to the CFG. We emulated lockstep CFG updates by getting its + // next snapshots by reverse-applying future updates. + static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) { + ResultTy Res = Get(N, Tag()); + // If there's no batch update in progress, simply return node's children. + if (!BUI) return Res; + + // CFG children are actually its *most current* children, and we have to + // reverse-apply the future updates to get the node's children at the + // point in time the update was performed. + auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors + : BUI->FutureSuccessors; + auto FCIt = FutureChildren.find(N); + if (FCIt == FutureChildren.end()) return Res; + + for (auto ChildAndKind : FCIt->second) { + const NodePtr Child = ChildAndKind.getPointer(); + const UpdateKind UK = ChildAndKind.getInt(); + + // Reverse-apply the future update. + if (UK == UpdateKind::Insert) { + // If there's an insertion in the future, it means that the edge must + // exist in the current CFG, but was not present in it before. + auto RIt = llvm::find(Res, Child); + assert(RIt != Res.end() && "Expected child not found in the CFG"); + DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> " + << BlockNamePrinter(Child) << "\n"); + std::swap(*RIt, Res.back()); + Res.pop_back(); + } else { + // If there's an deletion in the future, it means that the edge cannot + // exist in the current CFG, but existed in it before. + assert(llvm::find(Res, Child) == Res.end() && + "Unexpected child found in the CFG"); + DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N) + << " -> " << BlockNamePrinter(Child) << "\n"); + Res.push_back(Child); + } + } + + return Res; + } + }; + NodePtr getIDom(NodePtr BB) const { auto InfoIt = NodeToInfo.find(BB); if (InfoIt == NodeToInfo.end()) return nullptr; @@ -154,7 +231,8 @@ NumToNode.push_back(BB); constexpr bool Direction = IsReverse != IsPostDom; // XOR. - for (const NodePtr Succ : ChildrenGetter::Get(BB)) { + for (const NodePtr Succ : + ChildrenGetter::Get(BB, BatchUpdates)) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect // RerverseChildren. @@ -281,10 +359,9 @@ // For postdominators, nodes with no forward successors are trivial roots that // are always selected as tree roots. Roots with forward successors correspond // to CFG nodes within infinite loops. - static bool HasForwardSuccessors(const NodePtr N) { + static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) { assert(N && "N must be a valid node"); - using TraitsTy = GraphTraits; - return TraitsTy::child_begin(N) != TraitsTy::child_end(N); + return !ChildrenGetter::Get(N, BUI).empty(); } static NodePtr GetEntryNode(const DomTreeT &DT) { @@ -295,7 +372,7 @@ // Finds all roots without relaying on the set of roots already stored in the // tree. // We define roots to be some non-redundant set of the CFG nodes - static RootsT FindRoots(const DomTreeT &DT) { + static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) { assert(DT.Parent && "Parent pointer is not set"); RootsT Roots; @@ -305,7 +382,7 @@ return Roots; } - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); // PostDominatorTree always has a virtual root. SNCA.addVirtualRoot(); @@ -316,10 +393,15 @@ // Step #1: Find all the trivial roots that are going to will definitely // remain tree roots. unsigned Total = 0; + // It may happen that there are some new nodes in the CFG that are result of + // the ongoing batch update, but we cannot really pretend that they don't + // exist -- we won't see any outgoing or incoming edges to them, so it's + // fine to discover them here, as they would end up appearing in the CFG at + // some point anyway. for (const NodePtr N : nodes(DT.Parent)) { ++Total; // If it has no *successors*, it is definitely a root. - if (!HasForwardSuccessors(N)) { + if (!HasForwardSuccessors(N, BUI)) { Roots.push_back(N); // Run DFS not to walk this part of CFG later. Num = SNCA.runDFS(N, Num, AlwaysDescend, 1); @@ -398,7 +480,7 @@ assert((Total + 1 == Num) && "Everything should have been visited"); // Step #3: If we found some non-trivial roots, make them non-redundant. - if (HasNonTrivialRoots) RemoveRedundantRoots(DT, Roots); + if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots); DEBUG(dbgs() << "Found roots: "); DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " "); @@ -415,16 +497,17 @@ // the non-trivial roots are reverse-reachable from other non-trivial roots, // which makes them redundant. This function removes them from the set of // input roots. - static void RemoveRedundantRoots(const DomTreeT &DT, RootsT &Roots) { + static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, + RootsT &Roots) { assert(IsPostDom && "This function is for postdominators only"); DEBUG(dbgs() << "Removing redundant roots\n"); - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); for (unsigned i = 0; i < Roots.size(); ++i) { auto &Root = Roots[i]; // Trivial roots are always non-redundant. - if (!HasForwardSuccessors(Root)) continue; + if (!HasForwardSuccessors(Root, BUI)) continue; DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root) << " remains a root\n"); SNCA.clear(); @@ -466,13 +549,23 @@ for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0); } - void calculateFromScratch(DomTreeT &DT) { + static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) { + auto *Parent = DT.Parent; + DT.reset(); + DT.Parent = Parent; + SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree, + // there's no point doing it incrementally. + // Step #0: Number blocks in depth-first order and initialize variables used // in later stages of the algorithm. - DT.Roots = FindRoots(DT); - doFullDFSWalk(DT, AlwaysDescend); + DT.Roots = FindRoots(DT, nullptr); + SNCA.doFullDFSWalk(DT, AlwaysDescend); - runSemiNCA(DT); + SNCA.runSemiNCA(DT); + if (BUI) { + BUI->IsRecalculated = true; + DEBUG(dbgs() << "DomTree recalculated, skipping future batch updates\n"); + } if (DT.Roots.empty()) return; @@ -484,7 +577,7 @@ DT.RootNode = (DT.DomTreeNodes[Root] = llvm::make_unique>(Root, nullptr)) .get(); - attachNewSubtree(DT, DT.RootNode); + SNCA.attachNewSubtree(DT, DT.RootNode); } void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { @@ -541,7 +634,8 @@ SmallVector VisitedNotAffectedQueue; }; - static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { + static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, + const NodePtr From, const NodePtr To) { assert((From || IsPostDom) && "From has to be a valid CFG node or a virtual root"); assert(To && "Cannot be a nullptr"); @@ -566,14 +660,15 @@ const TreeNodePtr ToTN = DT.getNode(To); if (!ToTN) - InsertUnreachable(DT, FromTN, To); + InsertUnreachable(DT, BUI, FromTN, To); else - InsertReachable(DT, FromTN, ToTN); + InsertReachable(DT, BUI, FromTN, ToTN); } // Determines if some existing root becomes reverse-reachable after the // insertion. Rebuilds the whole tree if that situation happens. - static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const TreeNodePtr From, + static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr From, const TreeNodePtr To) { assert(IsPostDom && "This function is only for postdominators"); // Destination node is not attached to the virtual root, so it cannot be a @@ -587,22 +682,24 @@ DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To) << " is no longer a root\n\t\tRebuilding the tree!!!\n"); - DT.recalculate(*DT.Parent); + CalculateFromScratch(DT, BUI); return true; } // Updates the set of roots after insertion or deletion. This ensures that // roots are the same when after a series of updates and when the tree would // be built from scratch. - static void UpdateRootsAfterUpdate(DomTreeT &DT) { + static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) { assert(IsPostDom && "This function is only for postdominators"); // The tree has only trivial roots -- nothing to update. - if (std::none_of(DT.Roots.begin(), DT.Roots.end(), HasForwardSuccessors)) + if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) { + return HasForwardSuccessors(N, BUI); + })) return; // Recalculate the set of roots. - DT.Roots = FindRoots(DT); + DT.Roots = FindRoots(DT, BUI); for (const NodePtr R : DT.Roots) { const TreeNodePtr TN = DT.getNode(R); // A CFG node was selected as a tree root, but the corresponding tree node @@ -617,18 +714,18 @@ // It should be possible to rotate the subtree instead of recalculating // the whole tree, but this situation happens extremely rarely in // practice. - DT.recalculate(*DT.Parent); + CalculateFromScratch(DT, BUI); return; } } } // Handles insertion to a node already in the dominator tree. - static void InsertReachable(DomTreeT &DT, const TreeNodePtr From, - const TreeNodePtr To) { + static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr From, const TreeNodePtr To) { DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock()) << " -> " << BlockNamePrinter(To->getBlock()) << "\n"); - if (IsPostDom && UpdateRootsBeforeInsertion(DT, From, To)) return; + if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return; // DT.findNCD expects both pointers to be valid. When From is a virtual // root, then its CFG block pointer is a nullptr, so we have to 'compute' // the NCD manually. @@ -664,23 +761,23 @@ II.AffectedQueue.push_back(CurrentNode); // Discover and collect affected successors of the current node. - VisitInsertion(DT, CurrentNode, CurrentNode->getLevel(), NCD, II); + VisitInsertion(DT, BUI, CurrentNode, CurrentNode->getLevel(), NCD, II); } // Finish by updating immediate dominators and levels. - UpdateInsertion(DT, NCD, II); + UpdateInsertion(DT, BUI, 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) { + static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, + 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())) { + ChildrenGetter::Get(TN->getBlock(), BUI)) { const TreeNodePtr SuccTN = DT.getNode(Succ); assert(SuccTN && "Unreachable successor found at reachable insertion"); const unsigned SuccLevel = SuccTN->getLevel(); @@ -698,7 +795,7 @@ << BlockNamePrinter(Succ) << "\n"); II.Visited.insert(SuccTN); II.VisitedNotAffectedQueue.push_back(SuccTN); - VisitInsertion(DT, SuccTN, RootLevel, NCD, II); + VisitInsertion(DT, BUI, 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"); @@ -709,8 +806,8 @@ } // Updates immediate dominators and levels after insertion. - static void UpdateInsertion(DomTreeT &DT, const TreeNodePtr NCD, - InsertionInfo &II) { + static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr NCD, InsertionInfo &II) { DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n"); for (const TreeNodePtr TN : II.AffectedQueue) { @@ -720,7 +817,7 @@ } UpdateLevelsAfterInsertion(II); - if (IsPostDom) UpdateRootsAfterUpdate(DT); + if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); } static void UpdateLevelsAfterInsertion(InsertionInfo &II) { @@ -735,15 +832,15 @@ } // Handles insertion to previously unreachable nodes. - static void InsertUnreachable(DomTreeT &DT, const TreeNodePtr From, - const NodePtr To) { + static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, + 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); + ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable); DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From) << " -> (prev unreachable) " << BlockNamePrinter(To) << "\n"); @@ -756,15 +853,16 @@ DEBUG(dbgs() << "\tInserting discovered connecting edge " << BlockNamePrinter(Edge.first) << " -> " << BlockNamePrinter(Edge.second) << "\n"); - InsertReachable(DT, DT.getNode(Edge.first), Edge.second); + InsertReachable(DT, BUI, 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, + DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, + const TreeNodePtr Incoming, SmallVectorImpl> - &DiscoveredConnectingEdges) { + &DiscoveredConnectingEdges) { assert(!DT.getNode(Root) && "Root must not be reachable"); // Visit only previously unreachable nodes. @@ -777,7 +875,7 @@ return false; }; - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); SNCA.runDFS(Root, 0, UnreachableDescender, 0); SNCA.runSemiNCA(DT); SNCA.attachNewSubtree(DT, Incoming); @@ -786,7 +884,8 @@ DEBUG(DT.print(dbgs())); } - static void DeleteEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { + static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, + const NodePtr From, const NodePtr To) { assert(From && To && "Cannot disconnect nullptrs"); DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> " << BlockNamePrinter(To) << "\n"); @@ -795,8 +894,8 @@ // Ensure that the edge was in fact deleted from the CFG before informing // the DomTree about it. // The check is O(N), so run it only in debug configuration. - auto IsSuccessor = [](const NodePtr SuccCandidate, const NodePtr Of) { - auto Successors = ChildrenGetter::Get(Of); + auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) { + auto Successors = ChildrenGetter::Get(Of, BUI); return llvm::find(Successors, SuccCandidate) != Successors.end(); }; (void)IsSuccessor; @@ -826,16 +925,17 @@ // 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); + if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) + DeleteReachable(DT, BUI, FromTN, ToTN); else - DeleteUnreachable(DT, ToTN); + DeleteUnreachable(DT, BUI, ToTN); - if (IsPostDom) UpdateRootsAfterUpdate(DT); + if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); } // Handles deletions that leave destination nodes reachable. - static void DeleteReachable(DomTreeT &DT, const TreeNodePtr FromTN, + static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr FromTN, const TreeNodePtr ToTN) { DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN) << " -> " << BlockNamePrinter(ToTN) << "\n"); @@ -853,7 +953,7 @@ // scratch. if (!PrevIDomSubTree) { DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); - DT.recalculate(*DT.Parent); + CalculateFromScratch(DT, BUI); return; } @@ -865,7 +965,7 @@ DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n"); - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); SNCA.runDFS(ToIDom, 0, DescendBelow, 0); DEBUG(dbgs() << "\tRunning Semi-NCA\n"); SNCA.runSemiNCA(DT, Level); @@ -874,10 +974,11 @@ // 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) { + static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr TN) { DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN) << "\n"); for (const NodePtr Pred : - ChildrenGetter::Get(TN->getBlock())) { + ChildrenGetter::Get(TN->getBlock(), BUI)) { DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); if (!DT.getNode(Pred)) continue; @@ -897,7 +998,8 @@ // 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) { + static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, + const TreeNodePtr ToTN) { DEBUG(dbgs() << "Deleting unreachable subtree " << BlockNamePrinter(ToTN) << "\n"); assert(ToTN); @@ -910,7 +1012,7 @@ DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n"); DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN) << "\n"); DT.Roots.push_back(ToTN->getBlock()); - InsertReachable(DT, DT.getNode(nullptr), ToTN); + InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN); return; } @@ -929,7 +1031,7 @@ return false; }; - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); unsigned LastDFSNum = SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0); @@ -954,7 +1056,7 @@ // 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); + CalculateFromScratch(DT, BUI); return; } @@ -1009,6 +1111,126 @@ DT.DomTreeNodes.erase(TN->getBlock()); } + //~~ + //===--------------------- DomTree Batch Updater --------------------------=== + //~~ + + static void ApplyUpdates(DomTreeT &DT, ArrayRef Updates) { + BatchUpdateInfo BUI; + LegalizeUpdates(Updates, BUI.Updates); + + const size_t NumLegalized = BUI.Updates.size(); + BUI.FutureSuccessors.reserve(NumLegalized); + BUI.FuturePredecessors.reserve(NumLegalized); + + // Use the legalized future updates to initialize future successors and + // predecessors. Note that these sets will only decrease size over time, as + // the next CFG snapshots slowly approach the actual (current) CFG. + for (UpdateT &U : BUI.Updates) { + BUI.FutureSuccessors[U.getFrom()].insert({U.getTo(), U.getKind()}); + BUI.FuturePredecessors[U.getTo()].insert({U.getFrom(), U.getKind()}); + } + + DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n"); + DEBUG(if (NumLegalized < 32) for (const auto &U + : reverse(BUI.Updates)) dbgs() + << '\t' << U << "\n"); + DEBUG(dbgs() << "\n"); + + // If the DominatorTree was recalculated at some point, stop the batch + // updates. Full recalculations ignore batch updates and look at the actual + // CFG. + for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i) + ApplyNextUpdate(DT, BUI); + } + + // This function serves double purpose: + // a) It removes redundant updates, which makes it easier to reverse-apply + // them when traversing CFG. + // b) It optimizes away updates that cancel each other out, as the end result + // is the same. + // + // It relies on the property of the incremental updates that says that the + // order of updates doesn't matter. This allows us to reorder them and end up + // with the exact same DomTree every time. + // + // Following the same logic, the function doesn't care about the order of + // input updates, so it's OK to pass it an unordered sequence of updates, that + // doesn't make sense when applied sequentially, eg. performing double + // insertions or deletions and then doing an opposite update. + // + // In the future, it should be possible to schedule updates in way that + // minimizes the amount of work needed done during incremental updates. + static void LegalizeUpdates(ArrayRef AllUpdates, + SmallVectorImpl &Result) { + DEBUG(dbgs() << "Legalizing " << AllUpdates.size() << " updates\n"); + // Count the total number of inserions of each edge. + // Each insertion adds 1 and deletion subtracts 1. The end number should be + // one of {-1 (deletion), 0 (NOP), +1 (insertion)}. Otherwise, the sequence + // of updates contains multiple updates of the same kind and we assert for + // that case. + SmallDenseMap, int, 4> Operations; + Operations.reserve(AllUpdates.size()); + + for (const auto &U : AllUpdates) { + NodePtr From = U.getFrom(); + NodePtr To = U.getTo(); + if (IsPostDom) std::swap(From, To); // Reverse edge for postdominators. + + Operations[{From, To}] += (U.getKind() == UpdateKind::Insert ? 1 : -1); + } + + Result.clear(); + Result.reserve(Operations.size()); + for (auto &Op : Operations) { + const int NumInsertions = Op.second; + assert(std::abs(NumInsertions) <= 1 && "Unbalanced operations!"); + if (NumInsertions == 0) continue; + const UpdateKind UK = + NumInsertions > 0 ? UpdateKind::Insert : UpdateKind::Delete; + Result.push_back({UK, Op.first.first, Op.first.second}); + } + + // Make the order consistent by not relying on pointer values within the + // set. Reuse the old Operations map. + // In the future, we should sort by something else to minimize the amount + // of work needed to perform the series of updates. + for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) { + const auto &U = AllUpdates[i]; + if (!IsPostDom) + Operations[{U.getFrom(), U.getTo()}] = int(i); + else + Operations[{U.getTo(), U.getFrom()}] = int(i); + } + + std::sort(Result.begin(), Result.end(), + [&Operations](const UpdateT &A, const UpdateT &B) { + return Operations[{A.getFrom(), A.getTo()}] > + Operations[{B.getFrom(), B.getTo()}]; + }); + } + + static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) { + assert(!BUI.Updates.empty() && "No updates to apply!"); + UpdateT CurrentUpdate = BUI.Updates.pop_back_val(); + DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n"); + + // Move to the next snapshot of the CFG by removing the reverse-applied + // current update. + auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()]; + FS.erase({CurrentUpdate.getTo(), CurrentUpdate.getKind()}); + if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom()); + + auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()]; + FP.erase({CurrentUpdate.getFrom(), CurrentUpdate.getKind()}); + if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo()); + + if (CurrentUpdate.getKind() == UpdateKind::Insert) + InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); + else + DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo()); + } + //~~ //===--------------- DomTree correctness verification ---------------------=== //~~ @@ -1038,7 +1260,7 @@ } } - RootsT ComputedRoots = FindRoots(DT); + RootsT ComputedRoots = FindRoots(DT, nullptr); if (DT.Roots.size() != ComputedRoots.size() || !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), ComputedRoots.begin())) { @@ -1265,27 +1487,32 @@ template void Calculate(DomTreeT &DT) { - SemiNCAInfo SNCA; - SNCA.calculateFromScratch(DT); + SemiNCAInfo::CalculateFromScratch(DT, nullptr); } 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); + SemiNCAInfo::InsertEdge(DT, nullptr, From, To); } 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); + SemiNCAInfo::DeleteEdge(DT, nullptr, From, To); +} + +template +void ApplyUpdates(DomTreeT &DT, + ArrayRef Updates) { + SemiNCAInfo::ApplyUpdates(DT, Updates); } template bool Verify(const DomTreeT &DT) { - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(nullptr); return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) && SNCA.verifySiblingProperty(DT); Index: lib/IR/Dominators.cpp =================================================================== --- lib/IR/Dominators.cpp +++ lib/IR/Dominators.cpp @@ -64,6 +64,8 @@ template class llvm::DominatorTreeBase; // DomTreeBase template class llvm::DominatorTreeBase; // PostDomTreeBase +template struct llvm::DomTreeBuilder::Update; + template void llvm::DomTreeBuilder::Calculate( DomTreeBuilder::BBDomTree &DT); template void llvm::DomTreeBuilder::Calculate( @@ -79,6 +81,11 @@ template void llvm::DomTreeBuilder::DeleteEdge( DomTreeBuilder::BBPostDomTree &DT, BasicBlock *From, BasicBlock *To); +template void llvm::DomTreeBuilder::ApplyUpdates( + DomTreeBuilder::BBDomTree &DT, DomTreeBuilder::BBUpdates); +template void llvm::DomTreeBuilder::ApplyUpdates( + DomTreeBuilder::BBPostDomTree &DT, DomTreeBuilder::BBUpdates); + template bool llvm::DomTreeBuilder::Verify( const DomTreeBuilder::BBDomTree &DT); template bool llvm::DomTreeBuilder::Verify( @@ -312,6 +319,9 @@ print(errs()); errs() << "\nActual:\n"; OtherDT.print(errs()); + errs() << "\nCFG:\n"; + F.print(errs()); + errs().flush(); abort(); } } Index: unittests/IR/CMakeLists.txt =================================================================== --- unittests/IR/CMakeLists.txt +++ unittests/IR/CMakeLists.txt @@ -16,6 +16,7 @@ DebugInfoTest.cpp DebugTypeODRUniquingTest.cpp DominatorTreeTest.cpp + DominatorTreeBatchUpdatesTest.cpp FunctionTest.cpp PassBuilderCallbacksTest.cpp IRBuilderTest.cpp Index: unittests/IR/DominatorTreeBatchUpdatesTest.cpp =================================================================== --- /dev/null +++ unittests/IR/DominatorTreeBatchUpdatesTest.cpp @@ -0,0 +1,260 @@ +//===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include +#include "CFGBuilder.h" +#include "gtest/gtest.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/IR/Dominators.h" +#include "llvm/Support/GenericDomTreeConstruction.h" + +#define DEBUG_TYPE "batch-update-tests" + +using namespace llvm; + +namespace { +const auto CFGInsert = CFGBuilder::ActionKind::Insert; +const auto CFGDelete = CFGBuilder::ActionKind::Delete; + +struct PostDomTree : PostDomTreeBase { + PostDomTree(Function &F) { recalculate(F); } +}; + +using DomUpdate = DominatorTree::UpdateType; +static_assert( + std::is_same::value, + "Trees differing only in IsPostDom should have the same update types"); +using DomSNCA = DomTreeBuilder::SemiNCAInfo; +using PostDomSNCA = DomTreeBuilder::SemiNCAInfo; +const auto Insert = DominatorTree::Insert; +const auto Delete = DominatorTree::Delete; + +std::vector ToDomUpdates(CFGBuilder &B, + std::vector &In) { + std::vector Res; + Res.reserve(In.size()); + + for (const auto &CFGU : In) + Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete, + B.getOrAddBlock(CFGU.Edge.From), + B.getOrAddBlock(CFGU.Edge.To)}); + return Res; +} +} // namespace + +TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) { + CFGHolder Holder; + CFGBuilder Builder(Holder.F, {{"A", "B"}}, {}); + + BasicBlock *A = Builder.getOrAddBlock("A"); + BasicBlock *B = Builder.getOrAddBlock("B"); + BasicBlock *C = Builder.getOrAddBlock("C"); + BasicBlock *D = Builder.getOrAddBlock("D"); + + std::vector Updates = { + {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, + {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; + SmallVector Legalized; + DomSNCA::LegalizeUpdates(Updates, Legalized); + DEBUG(dbgs() << "Legalized updates:\t"); + DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); + DEBUG(dbgs() << "\n"); + EXPECT_EQ(Legalized.size(), 3UL); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, C}), Legalized.end()); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, B, D}), Legalized.end()); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, A, B}), Legalized.end()); +} + +TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) { + CFGHolder Holder; + CFGBuilder Builder(Holder.F, {{"A", "B"}}, {}); + + BasicBlock *A = Builder.getOrAddBlock("A"); + BasicBlock *B = Builder.getOrAddBlock("B"); + BasicBlock *C = Builder.getOrAddBlock("C"); + BasicBlock *D = Builder.getOrAddBlock("D"); + + std::vector Updates = { + {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C}, + {Insert, B, D}, {Delete, C, D}, {Delete, A, B}}; + SmallVector Legalized; + PostDomSNCA::LegalizeUpdates(Updates, Legalized); + DEBUG(dbgs() << "Legalized postdom updates:\t"); + DEBUG(for (auto &U : Legalized) dbgs() << U << ", "); + DEBUG(dbgs() << "\n"); + EXPECT_EQ(Legalized.size(), 3UL); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, C, B}), Legalized.end()); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Insert, D, B}), Legalized.end()); + EXPECT_NE(llvm::find(Legalized, DomUpdate{Delete, B, A}), Legalized.end()); +} + +TEST(DominatorTreeBatchUpdates, SingleInsertion) { + CFGHolder Holder; + CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}}); + + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(DT.verify()); + + BasicBlock *B = Builder.getOrAddBlock("B"); + BasicBlock *C = Builder.getOrAddBlock("C"); + std::vector Updates = {{Insert, B, C}}; + + ASSERT_TRUE(Builder.applyUpdate()); + + DT.applyUpdates(Updates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(Updates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, SingleDeletion) { + CFGHolder Holder; + CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}}, + {{CFGDelete, {"B", "C"}}}); + + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(DT.verify()); + + BasicBlock *B = Builder.getOrAddBlock("B"); + BasicBlock *C = Builder.getOrAddBlock("C"); + std::vector Updates = {{Delete, B, C}}; + + ASSERT_TRUE(Builder.applyUpdate()); + + DT.applyUpdates(Updates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(Updates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, FewInsertion) { + std::vector CFGUpdates = {{CFGInsert, {"B", "C"}}, + {CFGInsert, {"C", "B"}}, + {CFGInsert, {"C", "D"}}, + {CFGInsert, {"D", "E"}}}; + + CFGHolder Holder; + CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates); + + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + BasicBlock *B = Builder.getOrAddBlock("B"); + BasicBlock *C = Builder.getOrAddBlock("C"); + BasicBlock *D = Builder.getOrAddBlock("D"); + BasicBlock *E = Builder.getOrAddBlock("E"); + + std::vector Updates = { + {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}}; + + while (Builder.applyUpdate()) + ; + + DT.applyUpdates(Updates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(Updates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, FewDeletions) { + std::vector CFGUpdates = {{CFGDelete, {"B", "C"}}, + {CFGDelete, {"C", "B"}}, + {CFGDelete, {"B", "D"}}, + {CFGDelete, {"D", "E"}}}; + + CFGHolder Holder; + CFGBuilder Builder( + Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}}, + CFGUpdates); + + DominatorTree DT(*Holder.F); + EXPECT_TRUE(DT.verify()); + PostDomTree PDT(*Holder.F); + EXPECT_TRUE(PDT.verify()); + + auto Updates = ToDomUpdates(Builder, CFGUpdates); + + while (Builder.applyUpdate()) + ; + + DT.applyUpdates(Updates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(Updates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, 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 = { + {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}}, + {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}}, + {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}}, + {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}}, + {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}}, + {CFGDelete, {"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()); + + while (B.applyUpdate()) + ; + + auto DomUpdates = ToDomUpdates(B, Updates); + DT.applyUpdates(DomUpdates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(DomUpdates); + EXPECT_TRUE(PDT.verify()); +} + +TEST(DominatorTreeBatchUpdates, 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 = { + {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}}, + {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}}, + {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}}, + {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}}, + {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}}, + {CFGDelete, {"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()); + + while (B.applyUpdate()) + ; + + auto DomUpdates = ToDomUpdates(B, Updates); + DT.applyUpdates(DomUpdates); + EXPECT_TRUE(DT.verify()); + PDT.applyUpdates(DomUpdates); + EXPECT_TRUE(PDT.verify()); + } +}