diff options
Diffstat (limited to 'include/llvm/Support/GenericDomTreeConstruction.h')
| -rw-r--r-- | include/llvm/Support/GenericDomTreeConstruction.h | 1008 |
1 files changed, 818 insertions, 190 deletions
diff --git a/include/llvm/Support/GenericDomTreeConstruction.h b/include/llvm/Support/GenericDomTreeConstruction.h index be90afa4c3c8..8f801662d0fb 100644 --- a/include/llvm/Support/GenericDomTreeConstruction.h +++ b/include/llvm/Support/GenericDomTreeConstruction.h @@ -21,8 +21,8 @@ /// 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: +/// updates (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: @@ -34,8 +34,10 @@ #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H #include <queue> +#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,25 +47,12 @@ namespace llvm { namespace DomTreeBuilder { -template <typename NodePtr, bool Inverse> -struct ChildrenGetter { - static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) { - return reverse(children<NodePtr>(N)); - } -}; - -template <typename NodePtr> -struct ChildrenGetter<NodePtr, true> { - static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) { - return inverse_children<NodePtr>(N); - } -}; - template <typename DomTreeT> struct SemiNCAInfo { using NodePtr = typename DomTreeT::NodePtr; using NodeT = typename DomTreeT::NodeType; using TreeNodePtr = DomTreeNodeBase<NodeT> *; + using RootsT = decltype(DomTreeT::Roots); static constexpr bool IsPostDom = DomTreeT::IsPostDominator; // Information record used by Semi-NCA during tree construction. @@ -81,11 +70,99 @@ struct SemiNCAInfo { std::vector<NodePtr> NumToNode = {nullptr}; DenseMap<NodePtr, InfoRec> NodeToInfo; + using UpdateT = typename DomTreeT::UpdateType; + struct BatchUpdateInfo { + SmallVector<UpdateT, 4> Updates; + using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>; + + // 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<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> FutureSuccessors; + DenseMap<NodePtr, SmallDenseSet<NodePtrAndKind, 4>> 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 <bool Inverse> + struct ChildrenGetter { + using ResultTy = SmallVector<NodePtr, 8>; + + static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) { + auto RChildren = reverse(children<NodePtr>(N)); + return ResultTy(RChildren.begin(), RChildren.end()); + } + + static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) { + auto IChildren = inverse_children<NodePtr>(N); + return ResultTy(IChildren.begin(), IChildren.end()); + } + + using Tag = std::integral_constant<bool, Inverse>; + + // 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. + assert(llvm::find(Res, Child) != Res.end() + && "Expected child not found in the CFG"); + Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end()); + DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> " + << BlockNamePrinter(Child) << "\n"); + } 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; @@ -131,7 +208,11 @@ struct SemiNCAInfo { // Custom DFS implementation which can skip nodes based on a provided // predicate. It also collects ReverseChildren so that we don't have to spend // time getting predecessors in SemiNCA. - template <bool Inverse, typename DescendCondition> + // + // If IsReverse is set to true, the DFS walk will be performed backwards + // relative to IsPostDom -- using reverse edges for dominators and forward + // edges for postdominators. + template <bool IsReverse = false, typename DescendCondition> unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum) { assert(V); @@ -148,10 +229,12 @@ struct SemiNCAInfo { BBInfo.Label = BB; NumToNode.push_back(BB); - for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) { + constexpr bool Direction = IsReverse != IsPostDom; // XOR. + for (const NodePtr Succ : + ChildrenGetter<Direction>::Get(BB, BatchUpdates)) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect - // RerverseChildren. + // ReverseChildren. if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) { if (Succ != BB) SIT->second.ReverseChildren.push_back(BB); continue; @@ -256,51 +339,244 @@ struct SemiNCAInfo { } } - template <typename DescendCondition> - unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { - unsigned Num = 0; + // PostDominatorTree always has a virtual root that represents a virtual CFG + // node that serves as a single exit from the function. All the other exits + // (CFG nodes with terminators and nodes in infinite loops are logically + // connected to this virtual CFG exit node). + // This functions maps a nullptr CFG node to the virtual root tree node. + void addVirtualRoot() { + assert(IsPostDom && "Only postdominators have a virtual root"); + assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed"); - if (DT.Roots.size() > 1) { - auto &BBInfo = NodeToInfo[nullptr]; - BBInfo.DFSNum = BBInfo.Semi = ++Num; - BBInfo.Label = nullptr; + auto &BBInfo = NodeToInfo[nullptr]; + BBInfo.DFSNum = BBInfo.Semi = 1; + BBInfo.Label = nullptr; - NumToNode.push_back(nullptr); // NumToNode[n] = V; + NumToNode.push_back(nullptr); // NumToNode[1] = nullptr; + } + + // 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, BatchUpdatePtr BUI) { + assert(N && "N must be a valid node"); + return !ChildrenGetter<false>::Get(N, BUI).empty(); + } + + static NodePtr GetEntryNode(const DomTreeT &DT) { + assert(DT.Parent && "Parent not set"); + return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent); + } + + // 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, BatchUpdatePtr BUI) { + assert(DT.Parent && "Parent pointer is not set"); + RootsT Roots; + + // For dominators, function entry CFG node is always a tree root node. + if (!IsPostDom) { + Roots.push_back(GetEntryNode(DT)); + return Roots; } - if (DT.isPostDominator()) { - for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1); - } else { - assert(DT.Roots.size() == 1); - Num = runDFS<false>(DT.Roots[0], Num, DC, Num); + SemiNCAInfo SNCA(BUI); + + // PostDominatorTree always has a virtual root. + SNCA.addVirtualRoot(); + unsigned Num = 1; + + DEBUG(dbgs() << "\t\tLooking for trivial roots\n"); + + // 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, BUI)) { + Roots.push_back(N); + // Run DFS not to walk this part of CFG later. + Num = SNCA.runDFS(N, Num, AlwaysDescend, 1); + DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N) + << "\n"); + DEBUG(dbgs() << "Last visited node: " + << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n"); + } } - return Num; + DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n"); + + // Step #2: Find all non-trivial root candidates. Those are CFG nodes that + // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG + // nodes in infinite loops). + bool HasNonTrivialRoots = false; + // Accounting for the virtual exit, see if we had any reverse-unreachable + // nodes. + if (Total + 1 != Num) { + HasNonTrivialRoots = true; + // Make another DFS pass over all other nodes to find the + // reverse-unreachable blocks, and find the furthest paths we'll be able + // to make. + // Note that this looks N^2, but it's really 2N worst case, if every node + // is unreachable. This is because we are still going to only visit each + // unreachable node once, we may just visit it in two directions, + // depending on how lucky we get. + SmallPtrSet<NodePtr, 4> ConnectToExitBlock; + for (const NodePtr I : nodes(DT.Parent)) { + if (SNCA.NodeToInfo.count(I) == 0) { + DEBUG(dbgs() << "\t\t\tVisiting node " << BlockNamePrinter(I) + << "\n"); + // Find the furthest away we can get by following successors, then + // follow them in reverse. This gives us some reasonable answer about + // the post-dom tree inside any infinite loop. In particular, it + // guarantees we get to the farthest away point along *some* + // path. This also matches the GCC's behavior. + // If we really wanted a totally complete picture of dominance inside + // this infinite loop, we could do it with SCC-like algorithms to find + // the lowest and highest points in the infinite loop. In theory, it + // would be nice to give the canonical backedge for the loop, but it's + // expensive and does not always lead to a minimal set of roots. + DEBUG(dbgs() << "\t\t\tRunning forward DFS\n"); + + const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num); + const NodePtr FurthestAway = SNCA.NumToNode[NewNum]; + DEBUG(dbgs() << "\t\t\tFound a new furthest away node " + << "(non-trivial root): " + << BlockNamePrinter(FurthestAway) << "\n"); + ConnectToExitBlock.insert(FurthestAway); + Roots.push_back(FurthestAway); + DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: " + << NewNum << "\n\t\t\tRemoving DFS info\n"); + for (unsigned i = NewNum; i > Num; --i) { + const NodePtr N = SNCA.NumToNode[i]; + DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for " + << BlockNamePrinter(N) << "\n"); + SNCA.NodeToInfo.erase(N); + SNCA.NumToNode.pop_back(); + } + const unsigned PrevNum = Num; + DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n"); + Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1); + for (unsigned i = PrevNum + 1; i <= Num; ++i) + DEBUG(dbgs() << "\t\t\t\tfound node " + << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); + } + } + } + + DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n"); + DEBUG(dbgs() << "Discovered CFG nodes:\n"); + DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs() + << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n"); + + 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, BUI, Roots); + + DEBUG(dbgs() << "Found roots: "); + DEBUG(for (auto *Root : Roots) dbgs() << BlockNamePrinter(Root) << " "); + DEBUG(dbgs() << "\n"); + + return Roots; } - void calculateFromScratch(DomTreeT &DT, const unsigned NumBlocks) { + // This function only makes sense for postdominators. + // We define roots to be some set of CFG nodes where (reverse) DFS walks have + // to start in order to visit all the CFG nodes (including the + // reverse-unreachable ones). + // When the search for non-trivial roots is done it may happen that some of + // 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, BatchUpdatePtr BUI, + RootsT &Roots) { + assert(IsPostDom && "This function is for postdominators only"); + DEBUG(dbgs() << "Removing redundant roots\n"); + + SemiNCAInfo SNCA(BUI); + + for (unsigned i = 0; i < Roots.size(); ++i) { + auto &Root = Roots[i]; + // Trivial roots are always non-redundant. + if (!HasForwardSuccessors(Root, BUI)) continue; + DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root) + << " remains a root\n"); + SNCA.clear(); + // Do a forward walk looking for the other roots. + const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0); + // Skip the start node and begin from the second one (note that DFS uses + // 1-based indexing). + for (unsigned x = 2; x <= Num; ++x) { + const NodePtr N = SNCA.NumToNode[x]; + // If we wound another root in a (forward) DFS walk, remove the current + // root from the set of roots, as it is reverse-reachable from the other + // one. + if (llvm::find(Roots, N) != Roots.end()) { + DEBUG(dbgs() << "\tForward DFS walk found another root " + << BlockNamePrinter(N) << "\n\tRemoving root " + << BlockNamePrinter(Root) << "\n"); + std::swap(Root, Roots.back()); + Roots.pop_back(); + + // Root at the back takes the current root's place. + // Start the next loop iteration with the same index. + --i; + break; + } + } + } + } + + template <typename DescendCondition> + void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) { + if (!IsPostDom) { + assert(DT.Roots.size() == 1 && "Dominators should have a singe root"); + runDFS(DT.Roots[0], 0, DC, 0); + return; + } + + addVirtualRoot(); + unsigned Num = 1; + for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0); + } + + 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. - const unsigned LastDFSNum = 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; - // Add a node for the root. This node might be the actual root, if there is - // one exit block, or it may be the virtual exit (denoted by - // (BasicBlock *)0) which postdominates all real exits if there are multiple - // exit blocks, or an infinite loop. - // It might be that some blocks did not get a DFS number (e.g., blocks of - // infinite loops). In these cases an artificial exit node is required. - const bool MultipleRoots = DT.Roots.size() > 1 || (DT.isPostDominator() && - LastDFSNum != NumBlocks); - NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr; + // Add a node for the root. If the tree is a PostDominatorTree it will be + // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates + // all real exits (including multiple exit blocks, infinite loops). + NodePtr Root = IsPostDom ? nullptr : DT.Roots[0]; DT.RootNode = (DT.DomTreeNodes[Root] = llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr)) .get(); - attachNewSubtree(DT, DT.RootNode); + SNCA.attachNewSubtree(DT, DT.RootNode); } void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) { @@ -317,11 +593,11 @@ struct SemiNCAInfo { NodePtr ImmDom = getIDom(W); - // Get or calculate the node for the immediate dominator + // Get or calculate the node for the immediate dominator. TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT); // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode + // IDomNode. DT.DomTreeNodes[W] = IDomNode->addChild( llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode)); } @@ -357,31 +633,105 @@ struct SemiNCAInfo { SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue; }; - static void InsertEdge(DomTreeT &DT, const NodePtr From, const NodePtr To) { - assert(From && To && "Cannot connect nullptrs"); + 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"); DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> " << BlockNamePrinter(To) << "\n"); - const TreeNodePtr FromTN = DT.getNode(From); - - // Ignore edges from unreachable nodes. - if (!FromTN) return; + TreeNodePtr FromTN = DT.getNode(From); + + if (!FromTN) { + // Ignore edges from unreachable nodes for (forward) dominators. + if (!IsPostDom) return; + + // The unreachable node becomes a new root -- a tree node for it. + TreeNodePtr VirtualRoot = DT.getNode(nullptr); + FromTN = + (DT.DomTreeNodes[From] = VirtualRoot->addChild( + llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot))) + .get(); + DT.Roots.push_back(From); + } DT.DFSInfoValid = false; 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 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 + // root. + if (!DT.isVirtualRoot(To->getIDom())) return false; + + auto RIt = llvm::find(DT.Roots, To->getBlock()); + if (RIt == DT.Roots.end()) + return false; // To is not a root, nothing to update. + + DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To) + << " is no longer a root\n\t\tRebuilding the tree!!!\n"); + + 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, 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(), [BUI](const NodePtr N) { + return HasForwardSuccessors(N, BUI); + })) + return; + + // Recalculate the set of roots. + 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 + // is not connected to the virtual root. This is because the incremental + // algorithm does not really know or use the set of roots and can make a + // different (implicit) decision about which nodes within an infinite loop + // becomes a root. + if (DT.isVirtualRoot(TN->getIDom())) { + DEBUG(dbgs() << "Root " << BlockNamePrinter(R) + << " is not virtual root's child\n" + << "The entire tree needs to be rebuilt\n"); + // It should be possible to rotate the subtree instead of recalculating + // the whole tree, but this situation happens extremely rarely in + // practice. + 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, 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. const NodePtr NCDBlock = - DT.findNearestCommonDominator(From->getBlock(), To->getBlock()); + (From->getBlock() && To->getBlock()) + ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock()) + : nullptr; assert(NCDBlock || DT.isPostDominator()); const TreeNodePtr NCD = DT.getNode(NCDBlock); assert(NCD); @@ -410,53 +760,61 @@ struct SemiNCAInfo { 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<NodePtr, IsPostDom>::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}); + SmallVector<TreeNodePtr, 8> Stack = {TN}; + assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!"); + + do { + TreeNodePtr Next = Stack.pop_back_val(); + + for (const NodePtr Succ : + ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) { + 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); + Stack.push_back(SuccTN); + } 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}); + } } - } + } while (!Stack.empty()); } // 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) { @@ -466,6 +824,7 @@ struct SemiNCAInfo { } UpdateLevelsAfterInsertion(II); + if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI); } static void UpdateLevelsAfterInsertion(InsertionInfo &II) { @@ -480,36 +839,35 @@ struct SemiNCAInfo { } // 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<std::pair<NodePtr, TreeNodePtr>, 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"); - 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); + 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<std::pair<NodePtr, TreeNodePtr>> - &DiscoveredConnectingEdges) { + &DiscoveredConnectingEdges) { assert(!DT.getNode(Root) && "Root must not be reachable"); // Visit only previously unreachable nodes. @@ -522,50 +880,16 @@ struct SemiNCAInfo { return false; }; - SemiNCAInfo SNCA; - SNCA.runDFS<IsPostDom>(Root, 0, UnreachableDescender, 0); + SemiNCAInfo SNCA(BUI); + 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(); - doFullDFSWalk(DT, AlwaysDescend); - - for (auto &NodeToTN : DT.DomTreeNodes) { - const TreeNodePtr TN = NodeToTN.second.get(); - const NodePtr BB = TN->getBlock(); - - // Virtual root has a corresponding virtual CFG node. - if (DT.isVirtualRoot(TN)) continue; - - if (NodeToInfo.count(BB) == 0) { - errs() << "DomTree node " << BlockNamePrinter(BB) - << " not found by DFS walk!\n"; - errs().flush(); - - return false; - } - } - - for (const NodePtr N : NumToNode) { - if (N && !DT.getNode(N)) { - errs() << "CFG node " << BlockNamePrinter(N) - << " not found in the DomTree!\n"; - errs().flush(); - - return false; - } - } - - return true; - } - - 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"); @@ -574,8 +898,8 @@ struct SemiNCAInfo { // 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<NodePtr, IsPostDom>::Get(Of); + auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) { + auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI); return llvm::find(Successors, SuccCandidate) != Successors.end(); }; (void)IsSuccessor; @@ -587,27 +911,37 @@ struct SemiNCAInfo { if (!FromTN) return; const TreeNodePtr ToTN = DT.getNode(To); - assert(ToTN && "To already unreachable -- there is no edge to delete"); + if (!ToTN) { + DEBUG(dbgs() << "\tTo (" << BlockNamePrinter(To) + << ") already unreachable -- there is no edge to delete\n"); + return; + } + const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To); const TreeNodePtr NCD = DT.getNode(NCDBlock); // To dominates From -- nothing to do. if (ToTN == NCD) return; + DT.DFSInfoValid = false; + 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); + if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN)) + DeleteReachable(DT, BUI, FromTN, ToTN); else - DeleteUnreachable(DT, ToTN); + DeleteUnreachable(DT, BUI, ToTN); + + 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"); @@ -625,7 +959,7 @@ struct SemiNCAInfo { // scratch. if (!PrevIDomSubTree) { DEBUG(dbgs() << "The entire tree needs to be rebuilt\n"); - DT.recalculate(*DT.Parent); + CalculateFromScratch(DT, BUI); return; } @@ -637,8 +971,8 @@ struct SemiNCAInfo { DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN) << "\n"); - SemiNCAInfo SNCA; - SNCA.runDFS<IsPostDom>(ToIDom, 0, DescendBelow, 0); + SemiNCAInfo SNCA(BUI); + SNCA.runDFS(ToIDom, 0, DescendBelow, 0); DEBUG(dbgs() << "\tRunning Semi-NCA\n"); SNCA.runSemiNCA(DT, Level); SNCA.reattachExistingSubtree(DT, PrevIDomSubTree); @@ -646,10 +980,11 @@ struct SemiNCAInfo { // 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<NodePtr, !IsPostDom>::Get(TN->getBlock())) { + ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) { DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n"); if (!DT.getNode(Pred)) continue; @@ -669,12 +1004,24 @@ struct SemiNCAInfo { // 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); assert(ToTN->getBlock()); + if (IsPostDom) { + // Deletion makes a region reverse-unreachable and creates a new root. + // Simulate that by inserting an edge from the virtual root to ToTN and + // adding it as a new root. + 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, BUI, DT.getNode(nullptr), ToTN); + return; + } + SmallVector<NodePtr, 16> AffectedQueue; const unsigned Level = ToTN->getLevel(); @@ -690,13 +1037,13 @@ struct SemiNCAInfo { return false; }; - SemiNCAInfo SNCA; + SemiNCAInfo SNCA(BUI); unsigned LastDFSNum = - SNCA.runDFS<IsPostDom>(ToTN->getBlock(), 0, DescendAndCollect, 0); + SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0); TreeNodePtr MinNode = ToTN; - // Identify the top of the subtree to rebuilt by finding the NCD of all + // Identify the top of the subtree to rebuild by finding the NCD of all // the affected nodes. for (const NodePtr N : AffectedQueue) { const TreeNodePtr TN = DT.getNode(N); @@ -715,7 +1062,7 @@ struct SemiNCAInfo { // 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; } @@ -744,7 +1091,7 @@ struct SemiNCAInfo { const TreeNodePtr ToTN = DT.getNode(To); return ToTN && ToTN->getLevel() > MinLevel; }; - SNCA.runDFS<IsPostDom>(MinNode->getBlock(), 0, DescendBelow, 0); + SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0); DEBUG(dbgs() << "Previous IDom(MinNode) = " << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n"); @@ -771,9 +1118,222 @@ struct SemiNCAInfo { } //~~ + //===--------------------- DomTree Batch Updater --------------------------=== + //~~ + + static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) { + const size_t NumUpdates = Updates.size(); + if (NumUpdates == 0) + return; + + // Take the fast path for a single update and avoid running the batch update + // machinery. + if (NumUpdates == 1) { + const auto &Update = Updates.front(); + if (Update.getKind() == UpdateKind::Insert) + DT.insertEdge(Update.getFrom(), Update.getTo()); + else + DT.deleteEdge(Update.getFrom(), Update.getTo()); + + return; + } + + 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<UpdateT> AllUpdates, + SmallVectorImpl<UpdateT> &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<std::pair<NodePtr, NodePtr>, 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 ---------------------=== //~~ + // Check if the tree has correct roots. A DominatorTree always has a single + // root which is the function's entry node. A PostDominatorTree can have + // multiple roots - one for each node with no successors and for infinite + // loops. + bool verifyRoots(const DomTreeT &DT) { + if (!DT.Parent && !DT.Roots.empty()) { + errs() << "Tree has no parent but has roots!\n"; + errs().flush(); + return false; + } + + if (!IsPostDom) { + if (DT.Roots.empty()) { + errs() << "Tree doesn't have a root!\n"; + errs().flush(); + return false; + } + + if (DT.getRoot() != GetEntryNode(DT)) { + errs() << "Tree's root is not its parent's entry node!\n"; + errs().flush(); + return false; + } + } + + RootsT ComputedRoots = FindRoots(DT, nullptr); + if (DT.Roots.size() != ComputedRoots.size() || + !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), + ComputedRoots.begin())) { + errs() << "Tree has different roots than freshly computed ones!\n"; + errs() << "\tPDT roots: "; + for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", "; + errs() << "\n\tComputed roots: "; + for (const NodePtr N : ComputedRoots) + errs() << BlockNamePrinter(N) << ", "; + errs() << "\n"; + errs().flush(); + return false; + } + + return true; + } + + // Checks if the tree contains all reachable nodes in the input graph. + bool verifyReachability(const DomTreeT &DT) { + clear(); + doFullDFSWalk(DT, AlwaysDescend); + + for (auto &NodeToTN : DT.DomTreeNodes) { + const TreeNodePtr TN = NodeToTN.second.get(); + const NodePtr BB = TN->getBlock(); + + // Virtual root has a corresponding virtual CFG node. + if (DT.isVirtualRoot(TN)) continue; + + if (NodeToInfo.count(BB) == 0) { + errs() << "DomTree node " << BlockNamePrinter(BB) + << " not found by DFS walk!\n"; + errs().flush(); + + return false; + } + } + + for (const NodePtr N : NumToNode) { + if (N && !DT.getNode(N)) { + errs() << "CFG node " << BlockNamePrinter(N) + << " not found in the DomTree!\n"; + errs().flush(); + + return false; + } + } + + return true; + } + // 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) { @@ -805,35 +1365,97 @@ struct SemiNCAInfo { return true; } - // Checks if for every edge From -> To in the graph - // NCD(From, To) == IDom(To) or To. - bool verifyNCD(const DomTreeT &DT) { - clear(); - doFullDFSWalk(DT, AlwaysDescend); + // Check if the computed DFS numbers are correct. Note that DFS info may not + // be valid, and when that is the case, we don't verify the numbers. + static bool VerifyDFSNumbers(const DomTreeT &DT) { + if (!DT.DFSInfoValid || !DT.Parent) + return true; - for (auto &BlockToInfo : NodeToInfo) { - auto &Info = BlockToInfo.second; + const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0]; + const TreeNodePtr Root = DT.getNode(RootBB); - const NodePtr From = NumToNode[Info.Parent]; - if (!From) continue; + auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) { + errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", " + << TN->getDFSNumOut() << '}'; + }; - const NodePtr To = BlockToInfo.first; - const TreeNodePtr ToTN = DT.getNode(To); - assert(ToTN); - - const NodePtr NCD = DT.findNearestCommonDominator(From, To); - const TreeNodePtr NCDTN = DT.getNode(NCD); - const TreeNodePtr ToIDom = ToTN->getIDom(); - if (NCDTN != ToTN && NCDTN != ToIDom) { - errs() << "NearestCommonDominator verification failed:\n\tNCD(From:" - << BlockNamePrinter(From) << ", To:" << BlockNamePrinter(To) - << ") = " << BlockNamePrinter(NCD) - << ",\t (should be To or IDom[To]: " << BlockNamePrinter(ToIDom) - << ")\n"; + // Verify the root's DFS In number. Although DFS numbering would also work + // if we started from some other value, we assume 0-based numbering. + if (Root->getDFSNumIn() != 0) { + errs() << "DFSIn number for the tree root is not:\n\t"; + PrintNodeAndDFSNums(Root); + errs() << '\n'; + errs().flush(); + return false; + } + + // For each tree node verify if children's DFS numbers cover their parent's + // DFS numbers with no gaps. + for (const auto &NodeToTN : DT.DomTreeNodes) { + const TreeNodePtr Node = NodeToTN.second.get(); + + // Handle tree leaves. + if (Node->getChildren().empty()) { + if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) { + errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t"; + PrintNodeAndDFSNums(Node); + errs() << '\n'; + errs().flush(); + return false; + } + + continue; + } + + // Make a copy and sort it such that it is possible to check if there are + // no gaps between DFS numbers of adjacent children. + SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end()); + std::sort(Children.begin(), Children.end(), + [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) { + return Ch1->getDFSNumIn() < Ch2->getDFSNumIn(); + }); + + auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums]( + const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) { + assert(FirstCh); + + errs() << "Incorrect DFS numbers for:\n\tParent "; + PrintNodeAndDFSNums(Node); + + errs() << "\n\tChild "; + PrintNodeAndDFSNums(FirstCh); + + if (SecondCh) { + errs() << "\n\tSecond child "; + PrintNodeAndDFSNums(SecondCh); + } + + errs() << "\nAll children: "; + for (const TreeNodePtr Ch : Children) { + PrintNodeAndDFSNums(Ch); + errs() << ", "; + } + + errs() << '\n'; errs().flush(); + }; + if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) { + PrintChildrenError(Children.front(), nullptr); return false; } + + if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) { + PrintChildrenError(Children.back(), nullptr); + return false; + } + + for (size_t i = 0, e = Children.size() - 1; i != e; ++i) { + if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) { + PrintChildrenError(Children[i], Children[i + 1]); + return false; + } + } } return true; @@ -888,6 +1510,8 @@ struct SemiNCAInfo { const NodePtr BB = TN->getBlock(); if (!BB || TN->getChildren().empty()) continue; + DEBUG(dbgs() << "Verifying parent property of node " + << BlockNamePrinter(TN) << "\n"); clear(); doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) { return From != BB && To != BB; @@ -945,33 +1569,37 @@ struct SemiNCAInfo { } }; - -template <class DomTreeT, class FuncT> -void Calculate(DomTreeT &DT, FuncT &F) { - SemiNCAInfo<DomTreeT> SNCA; - SNCA.calculateFromScratch(DT, GraphTraits<FuncT *>::size(&F)); +template <class DomTreeT> +void Calculate(DomTreeT &DT) { + SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr); } template <class DomTreeT> void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To) { if (DT.isPostDominator()) std::swap(From, To); - SemiNCAInfo<DomTreeT>::InsertEdge(DT, From, To); + SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To); } template <class DomTreeT> void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To) { if (DT.isPostDominator()) std::swap(From, To); - SemiNCAInfo<DomTreeT>::DeleteEdge(DT, From, To); + SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To); +} + +template <class DomTreeT> +void ApplyUpdates(DomTreeT &DT, + ArrayRef<typename DomTreeT::UpdateType> Updates) { + SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates); } template <class DomTreeT> bool Verify(const DomTreeT &DT) { - SemiNCAInfo<DomTreeT> SNCA; - return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) && - SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) && - SNCA.verifySiblingProperty(DT); + SemiNCAInfo<DomTreeT> SNCA(nullptr); + return SNCA.verifyRoots(DT) && SNCA.verifyReachability(DT) && + SNCA.VerifyLevels(DT) && SNCA.verifyParentProperty(DT) && + SNCA.verifySiblingProperty(DT) && SNCA.VerifyDFSNumbers(DT); } } // namespace DomTreeBuilder |