1 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// Generic dominator tree construction - This file provides routines to
12 /// construct immediate dominator information for a flow-graph based on the
13 /// Semi-NCA algorithm described in this dissertation:
15 /// Linear-Time Algorithms for Dominators and Related Problems
16 /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
17 /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
19 /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
20 /// out that the theoretically slower O(n*log(n)) implementation is actually
21 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
23 /// The file uses the Depth Based Search algorithm to perform incremental
24 /// updates (insertion and deletions). The implemented algorithm is based on
27 /// An Experimental Study of Dynamic Dominators
28 /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
29 /// https://arxiv.org/pdf/1604.02711.pdf
31 //===----------------------------------------------------------------------===//
33 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
34 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
37 #include "llvm/ADT/ArrayRef.h"
38 #include "llvm/ADT/DenseSet.h"
39 #include "llvm/ADT/DepthFirstIterator.h"
40 #include "llvm/ADT/PointerIntPair.h"
41 #include "llvm/ADT/SmallPtrSet.h"
42 #include "llvm/Support/Debug.h"
43 #include "llvm/Support/GenericDomTree.h"
45 #define DEBUG_TYPE "dom-tree-builder"
48 namespace DomTreeBuilder {
50 template <typename DomTreeT>
52 using NodePtr = typename DomTreeT::NodePtr;
53 using NodeT = typename DomTreeT::NodeType;
54 using TreeNodePtr = DomTreeNodeBase<NodeT> *;
55 using RootsT = decltype(DomTreeT::Roots);
56 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
58 // Information record used by Semi-NCA during tree construction.
63 NodePtr Label = nullptr;
64 NodePtr IDom = nullptr;
65 SmallVector<NodePtr, 2> ReverseChildren;
68 // Number to node mapping is 1-based. Initialize the mapping to start with
70 std::vector<NodePtr> NumToNode = {nullptr};
71 DenseMap<NodePtr, InfoRec> NodeToInfo;
73 using UpdateT = typename DomTreeT::UpdateType;
74 using UpdateKind = typename DomTreeT::UpdateKind;
75 struct BatchUpdateInfo {
76 SmallVector<UpdateT, 4> Updates;
77 using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
79 // In order to be able to walk a CFG that is out of sync with the CFG
80 // DominatorTree last knew about, use the list of updates to reconstruct
81 // previous CFG versions of the current CFG. For each node, we store a set
82 // of its virtually added/deleted future successors and predecessors.
83 // Note that these children are from the future relative to what the
84 // DominatorTree knows about -- using them to gets us some snapshot of the
85 // CFG from the past (relative to the state of the CFG).
86 DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
87 DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
88 // Remembers if the whole tree was recalculated at some point during the
89 // current batch update.
90 bool IsRecalculated = false;
93 BatchUpdateInfo *BatchUpdates;
94 using BatchUpdatePtr = BatchUpdateInfo *;
96 // If BUI is a nullptr, then there's no batch update in progress.
97 SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
100 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
102 // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
103 // in progress, we need this information to continue it.
106 template <bool Inverse>
107 struct ChildrenGetter {
108 using ResultTy = SmallVector<NodePtr, 8>;
110 static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
111 auto RChildren = reverse(children<NodePtr>(N));
112 return ResultTy(RChildren.begin(), RChildren.end());
115 static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
116 auto IChildren = inverse_children<NodePtr>(N);
117 return ResultTy(IChildren.begin(), IChildren.end());
120 using Tag = std::integral_constant<bool, Inverse>;
122 // The function below is the core part of the batch updater. It allows the
123 // Depth Based Search algorithm to perform incremental updates in lockstep
124 // with updates to the CFG. We emulated lockstep CFG updates by getting its
125 // next snapshots by reverse-applying future updates.
126 static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
127 ResultTy Res = Get(N, Tag());
128 // If there's no batch update in progress, simply return node's children.
129 if (!BUI) return Res;
131 // CFG children are actually its *most current* children, and we have to
132 // reverse-apply the future updates to get the node's children at the
133 // point in time the update was performed.
134 auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
135 : BUI->FutureSuccessors;
136 auto FCIt = FutureChildren.find(N);
137 if (FCIt == FutureChildren.end()) return Res;
139 for (auto ChildAndKind : FCIt->second) {
140 const NodePtr Child = ChildAndKind.getPointer();
141 const UpdateKind UK = ChildAndKind.getInt();
143 // Reverse-apply the future update.
144 if (UK == UpdateKind::Insert) {
145 // If there's an insertion in the future, it means that the edge must
146 // exist in the current CFG, but was not present in it before.
147 assert(llvm::find(Res, Child) != Res.end()
148 && "Expected child not found in the CFG");
149 Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
150 LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
151 << BlockNamePrinter(Child) << "\n");
153 // If there's an deletion in the future, it means that the edge cannot
154 // exist in the current CFG, but existed in it before.
155 assert(llvm::find(Res, Child) == Res.end() &&
156 "Unexpected child found in the CFG");
157 LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
158 << " -> " << BlockNamePrinter(Child) << "\n");
159 Res.push_back(Child);
167 NodePtr getIDom(NodePtr BB) const {
168 auto InfoIt = NodeToInfo.find(BB);
169 if (InfoIt == NodeToInfo.end()) return nullptr;
171 return InfoIt->second.IDom;
174 TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
175 if (TreeNodePtr Node = DT.getNode(BB)) return Node;
177 // Haven't calculated this node yet? Get or calculate the node for the
178 // immediate dominator.
179 NodePtr IDom = getIDom(BB);
181 assert(IDom || DT.DomTreeNodes[nullptr]);
182 TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
184 // Add a new tree node for this NodeT, and link it as a child of
186 return (DT.DomTreeNodes[BB] = IDomNode->addChild(
187 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
191 static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
193 struct BlockNamePrinter {
196 BlockNamePrinter(NodePtr Block) : N(Block) {}
197 BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
199 friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
203 BP.N->printAsOperand(O, false);
209 // Custom DFS implementation which can skip nodes based on a provided
210 // predicate. It also collects ReverseChildren so that we don't have to spend
211 // time getting predecessors in SemiNCA.
213 // If IsReverse is set to true, the DFS walk will be performed backwards
214 // relative to IsPostDom -- using reverse edges for dominators and forward
215 // edges for postdominators.
216 template <bool IsReverse = false, typename DescendCondition>
217 unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
218 unsigned AttachToNum) {
220 SmallVector<NodePtr, 64> WorkList = {V};
221 if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
223 while (!WorkList.empty()) {
224 const NodePtr BB = WorkList.pop_back_val();
225 auto &BBInfo = NodeToInfo[BB];
227 // Visited nodes always have positive DFS numbers.
228 if (BBInfo.DFSNum != 0) continue;
229 BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
231 NumToNode.push_back(BB);
233 constexpr bool Direction = IsReverse != IsPostDom; // XOR.
234 for (const NodePtr Succ :
235 ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
236 const auto SIT = NodeToInfo.find(Succ);
237 // Don't visit nodes more than once but remember to collect
239 if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
240 if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
244 if (!Condition(BB, Succ)) continue;
246 // It's fine to add Succ to the map, because we know that it will be
248 auto &SuccInfo = NodeToInfo[Succ];
249 WorkList.push_back(Succ);
250 SuccInfo.Parent = LastNum;
251 SuccInfo.ReverseChildren.push_back(BB);
258 NodePtr eval(NodePtr VIn, unsigned LastLinked) {
259 auto &VInInfo = NodeToInfo[VIn];
260 if (VInInfo.DFSNum < LastLinked)
263 SmallVector<NodePtr, 32> Work;
264 SmallPtrSet<NodePtr, 32> Visited;
266 if (VInInfo.Parent >= LastLinked)
269 while (!Work.empty()) {
270 NodePtr V = Work.back();
271 auto &VInfo = NodeToInfo[V];
272 NodePtr VAncestor = NumToNode[VInfo.Parent];
274 // Process Ancestor first
275 if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
276 Work.push_back(VAncestor);
281 // Update VInfo based on Ancestor info
282 if (VInfo.Parent < LastLinked)
285 auto &VAInfo = NodeToInfo[VAncestor];
286 NodePtr VAncestorLabel = VAInfo.Label;
287 NodePtr VLabel = VInfo.Label;
288 if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
289 VInfo.Label = VAncestorLabel;
290 VInfo.Parent = VAInfo.Parent;
293 return VInInfo.Label;
296 // This function requires DFS to be run before calling it.
297 void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
298 const unsigned NextDFSNum(NumToNode.size());
299 // Initialize IDoms to spanning tree parents.
300 for (unsigned i = 1; i < NextDFSNum; ++i) {
301 const NodePtr V = NumToNode[i];
302 auto &VInfo = NodeToInfo[V];
303 VInfo.IDom = NumToNode[VInfo.Parent];
306 // Step #1: Calculate the semidominators of all vertices.
307 for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
308 NodePtr W = NumToNode[i];
309 auto &WInfo = NodeToInfo[W];
311 // Initialize the semi dominator to point to the parent node.
312 WInfo.Semi = WInfo.Parent;
313 for (const auto &N : WInfo.ReverseChildren) {
314 if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
317 const TreeNodePtr TN = DT.getNode(N);
318 // Skip predecessors whose level is above the subtree we are processing.
319 if (TN && TN->getLevel() < MinLevel)
322 unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
323 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
327 // Step #2: Explicitly define the immediate dominator of each vertex.
328 // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
329 // Note that the parents were stored in IDoms and later got invalidated
330 // during path compression in Eval.
331 for (unsigned i = 2; i < NextDFSNum; ++i) {
332 const NodePtr W = NumToNode[i];
333 auto &WInfo = NodeToInfo[W];
334 const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
335 NodePtr WIDomCandidate = WInfo.IDom;
336 while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
337 WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
339 WInfo.IDom = WIDomCandidate;
343 // PostDominatorTree always has a virtual root that represents a virtual CFG
344 // node that serves as a single exit from the function. All the other exits
345 // (CFG nodes with terminators and nodes in infinite loops are logically
346 // connected to this virtual CFG exit node).
347 // This functions maps a nullptr CFG node to the virtual root tree node.
348 void addVirtualRoot() {
349 assert(IsPostDom && "Only postdominators have a virtual root");
350 assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
352 auto &BBInfo = NodeToInfo[nullptr];
353 BBInfo.DFSNum = BBInfo.Semi = 1;
354 BBInfo.Label = nullptr;
356 NumToNode.push_back(nullptr); // NumToNode[1] = nullptr;
359 // For postdominators, nodes with no forward successors are trivial roots that
360 // are always selected as tree roots. Roots with forward successors correspond
361 // to CFG nodes within infinite loops.
362 static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
363 assert(N && "N must be a valid node");
364 return !ChildrenGetter<false>::Get(N, BUI).empty();
367 static NodePtr GetEntryNode(const DomTreeT &DT) {
368 assert(DT.Parent && "Parent not set");
369 return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
372 // Finds all roots without relaying on the set of roots already stored in the
374 // We define roots to be some non-redundant set of the CFG nodes
375 static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
376 assert(DT.Parent && "Parent pointer is not set");
379 // For dominators, function entry CFG node is always a tree root node.
381 Roots.push_back(GetEntryNode(DT));
385 SemiNCAInfo SNCA(BUI);
387 // PostDominatorTree always has a virtual root.
388 SNCA.addVirtualRoot();
391 LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
393 // Step #1: Find all the trivial roots that are going to will definitely
394 // remain tree roots.
396 // It may happen that there are some new nodes in the CFG that are result of
397 // the ongoing batch update, but we cannot really pretend that they don't
398 // exist -- we won't see any outgoing or incoming edges to them, so it's
399 // fine to discover them here, as they would end up appearing in the CFG at
400 // some point anyway.
401 for (const NodePtr N : nodes(DT.Parent)) {
403 // If it has no *successors*, it is definitely a root.
404 if (!HasForwardSuccessors(N, BUI)) {
406 // Run DFS not to walk this part of CFG later.
407 Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
408 LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
410 LLVM_DEBUG(dbgs() << "Last visited node: "
411 << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
415 LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
417 // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
418 // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
419 // nodes in infinite loops).
420 bool HasNonTrivialRoots = false;
421 // Accounting for the virtual exit, see if we had any reverse-unreachable
423 if (Total + 1 != Num) {
424 HasNonTrivialRoots = true;
425 // Make another DFS pass over all other nodes to find the
426 // reverse-unreachable blocks, and find the furthest paths we'll be able
428 // Note that this looks N^2, but it's really 2N worst case, if every node
429 // is unreachable. This is because we are still going to only visit each
430 // unreachable node once, we may just visit it in two directions,
431 // depending on how lucky we get.
432 SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
433 for (const NodePtr I : nodes(DT.Parent)) {
434 if (SNCA.NodeToInfo.count(I) == 0) {
436 << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
437 // Find the furthest away we can get by following successors, then
438 // follow them in reverse. This gives us some reasonable answer about
439 // the post-dom tree inside any infinite loop. In particular, it
440 // guarantees we get to the farthest away point along *some*
441 // path. This also matches the GCC's behavior.
442 // If we really wanted a totally complete picture of dominance inside
443 // this infinite loop, we could do it with SCC-like algorithms to find
444 // the lowest and highest points in the infinite loop. In theory, it
445 // would be nice to give the canonical backedge for the loop, but it's
446 // expensive and does not always lead to a minimal set of roots.
447 LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
449 const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
450 const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
451 LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
452 << "(non-trivial root): "
453 << BlockNamePrinter(FurthestAway) << "\n");
454 ConnectToExitBlock.insert(FurthestAway);
455 Roots.push_back(FurthestAway);
456 LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
457 << NewNum << "\n\t\t\tRemoving DFS info\n");
458 for (unsigned i = NewNum; i > Num; --i) {
459 const NodePtr N = SNCA.NumToNode[i];
460 LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
461 << BlockNamePrinter(N) << "\n");
462 SNCA.NodeToInfo.erase(N);
463 SNCA.NumToNode.pop_back();
465 const unsigned PrevNum = Num;
466 LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
467 Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
468 for (unsigned i = PrevNum + 1; i <= Num; ++i)
469 LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
470 << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
475 LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
476 LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
477 LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
478 << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
480 assert((Total + 1 == Num) && "Everything should have been visited");
482 // Step #3: If we found some non-trivial roots, make them non-redundant.
483 if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
485 LLVM_DEBUG(dbgs() << "Found roots: ");
486 LLVM_DEBUG(for (auto *Root
488 << BlockNamePrinter(Root) << " ");
489 LLVM_DEBUG(dbgs() << "\n");
494 // This function only makes sense for postdominators.
495 // We define roots to be some set of CFG nodes where (reverse) DFS walks have
496 // to start in order to visit all the CFG nodes (including the
497 // reverse-unreachable ones).
498 // When the search for non-trivial roots is done it may happen that some of
499 // the non-trivial roots are reverse-reachable from other non-trivial roots,
500 // which makes them redundant. This function removes them from the set of
502 static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
504 assert(IsPostDom && "This function is for postdominators only");
505 LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
507 SemiNCAInfo SNCA(BUI);
509 for (unsigned i = 0; i < Roots.size(); ++i) {
510 auto &Root = Roots[i];
511 // Trivial roots are always non-redundant.
512 if (!HasForwardSuccessors(Root, BUI)) continue;
513 LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
514 << " remains a root\n");
516 // Do a forward walk looking for the other roots.
517 const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
518 // Skip the start node and begin from the second one (note that DFS uses
519 // 1-based indexing).
520 for (unsigned x = 2; x <= Num; ++x) {
521 const NodePtr N = SNCA.NumToNode[x];
522 // If we wound another root in a (forward) DFS walk, remove the current
523 // root from the set of roots, as it is reverse-reachable from the other
525 if (llvm::find(Roots, N) != Roots.end()) {
526 LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
527 << BlockNamePrinter(N) << "\n\tRemoving root "
528 << BlockNamePrinter(Root) << "\n");
529 std::swap(Root, Roots.back());
532 // Root at the back takes the current root's place.
533 // Start the next loop iteration with the same index.
541 template <typename DescendCondition>
542 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
544 assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
545 runDFS(DT.Roots[0], 0, DC, 0);
551 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
554 static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
555 auto *Parent = DT.Parent;
558 SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree,
559 // there's no point doing it incrementally.
561 // Step #0: Number blocks in depth-first order and initialize variables used
562 // in later stages of the algorithm.
563 DT.Roots = FindRoots(DT, nullptr);
564 SNCA.doFullDFSWalk(DT, AlwaysDescend);
568 BUI->IsRecalculated = true;
570 dbgs() << "DomTree recalculated, skipping future batch updates\n");
573 if (DT.Roots.empty()) return;
575 // Add a node for the root. If the tree is a PostDominatorTree it will be
576 // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
577 // all real exits (including multiple exit blocks, infinite loops).
578 NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
580 DT.RootNode = (DT.DomTreeNodes[Root] =
581 llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
583 SNCA.attachNewSubtree(DT, DT.RootNode);
586 void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
587 // Attach the first unreachable block to AttachTo.
588 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
589 // Loop over all of the discovered blocks in the function...
590 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
591 NodePtr W = NumToNode[i];
592 LLVM_DEBUG(dbgs() << "\tdiscovered a new reachable node "
593 << BlockNamePrinter(W) << "\n");
595 // Don't replace this with 'count', the insertion side effect is important
596 if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
598 NodePtr ImmDom = getIDom(W);
600 // Get or calculate the node for the immediate dominator.
601 TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
603 // Add a new tree node for this BasicBlock, and link it as a child of
605 DT.DomTreeNodes[W] = IDomNode->addChild(
606 llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
610 void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
611 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
612 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
613 const NodePtr N = NumToNode[i];
614 const TreeNodePtr TN = DT.getNode(N);
616 const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
617 TN->setIDom(NewIDom);
621 // Helper struct used during edge insertions.
622 struct InsertionInfo {
623 using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
624 struct DecreasingLevel {
625 bool operator()(const BucketElementTy &First,
626 const BucketElementTy &Second) const {
627 return First.first > Second.first;
631 std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
633 Bucket; // Queue of tree nodes sorted by level in descending order.
634 SmallDenseSet<TreeNodePtr, 8> Affected;
635 SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
636 SmallVector<TreeNodePtr, 8> AffectedQueue;
637 SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
640 static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
641 const NodePtr From, const NodePtr To) {
642 assert((From || IsPostDom) &&
643 "From has to be a valid CFG node or a virtual root");
644 assert(To && "Cannot be a nullptr");
645 LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
646 << BlockNamePrinter(To) << "\n");
647 TreeNodePtr FromTN = DT.getNode(From);
650 // Ignore edges from unreachable nodes for (forward) dominators.
651 if (!IsPostDom) return;
653 // The unreachable node becomes a new root -- a tree node for it.
654 TreeNodePtr VirtualRoot = DT.getNode(nullptr);
656 (DT.DomTreeNodes[From] = VirtualRoot->addChild(
657 llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
659 DT.Roots.push_back(From);
662 DT.DFSInfoValid = false;
664 const TreeNodePtr ToTN = DT.getNode(To);
666 InsertUnreachable(DT, BUI, FromTN, To);
668 InsertReachable(DT, BUI, FromTN, ToTN);
671 // Determines if some existing root becomes reverse-reachable after the
672 // insertion. Rebuilds the whole tree if that situation happens.
673 static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
674 const TreeNodePtr From,
675 const TreeNodePtr To) {
676 assert(IsPostDom && "This function is only for postdominators");
677 // Destination node is not attached to the virtual root, so it cannot be a
679 if (!DT.isVirtualRoot(To->getIDom())) return false;
681 auto RIt = llvm::find(DT.Roots, To->getBlock());
682 if (RIt == DT.Roots.end())
683 return false; // To is not a root, nothing to update.
685 LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
686 << " is no longer a root\n\t\tRebuilding the tree!!!\n");
688 CalculateFromScratch(DT, BUI);
692 // Updates the set of roots after insertion or deletion. This ensures that
693 // roots are the same when after a series of updates and when the tree would
694 // be built from scratch.
695 static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
696 assert(IsPostDom && "This function is only for postdominators");
698 // The tree has only trivial roots -- nothing to update.
699 if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
700 return HasForwardSuccessors(N, BUI);
704 // Recalculate the set of roots.
705 auto Roots = FindRoots(DT, BUI);
706 if (DT.Roots.size() != Roots.size() ||
707 !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
708 // The roots chosen in the CFG have changed. This is because the
709 // incremental algorithm does not really know or use the set of roots and
710 // can make a different (implicit) decision about which node within an
711 // infinite loop becomes a root.
713 LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
714 << "The entire tree needs to be rebuilt\n");
715 // It may be possible to update the tree without recalculating it, but
716 // we do not know yet how to do it, and it happens rarely in practise.
717 CalculateFromScratch(DT, BUI);
722 // Handles insertion to a node already in the dominator tree.
723 static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
724 const TreeNodePtr From, const TreeNodePtr To) {
725 LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
726 << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
727 if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
728 // DT.findNCD expects both pointers to be valid. When From is a virtual
729 // root, then its CFG block pointer is a nullptr, so we have to 'compute'
731 const NodePtr NCDBlock =
732 (From->getBlock() && To->getBlock())
733 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
735 assert(NCDBlock || DT.isPostDominator());
736 const TreeNodePtr NCD = DT.getNode(NCDBlock);
739 LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
740 const TreeNodePtr ToIDom = To->getIDom();
742 // Nothing affected -- NCA property holds.
743 // (Based on the lemma 2.5 from the second paper.)
744 if (NCD == To || NCD == ToIDom) return;
746 // Identify and collect affected nodes.
748 LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
749 << " as affected\n");
750 II.Affected.insert(To);
751 const unsigned ToLevel = To->getLevel();
752 LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
753 << " into a Bucket\n");
754 II.Bucket.push({ToLevel, To});
756 while (!II.Bucket.empty()) {
757 const TreeNodePtr CurrentNode = II.Bucket.top().second;
758 const unsigned CurrentLevel = CurrentNode->getLevel();
760 LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
761 << BlockNamePrinter(CurrentNode) << "\n");
763 II.Visited.insert({CurrentNode, CurrentLevel});
764 II.AffectedQueue.push_back(CurrentNode);
766 // Discover and collect affected successors of the current node.
767 VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
770 // Finish by updating immediate dominators and levels.
771 UpdateInsertion(DT, BUI, NCD, II);
774 // Visits an affected node and collect its affected successors.
775 static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
776 const TreeNodePtr TN, const unsigned RootLevel,
777 const TreeNodePtr NCD, InsertionInfo &II) {
778 const unsigned NCDLevel = NCD->getLevel();
779 LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel "
780 << RootLevel << "\n");
782 SmallVector<TreeNodePtr, 8> Stack = {TN};
783 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
785 SmallPtrSet<TreeNodePtr, 8> Processed;
788 TreeNodePtr Next = Stack.pop_back_val();
789 LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
791 for (const NodePtr Succ :
792 ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
793 const TreeNodePtr SuccTN = DT.getNode(Succ);
794 assert(SuccTN && "Unreachable successor found at reachable insertion");
795 const unsigned SuccLevel = SuccTN->getLevel();
797 LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
798 << ", level = " << SuccLevel << "\n");
800 // Do not process the same node multiple times.
801 if (Processed.count(Next) > 0)
804 // Succ dominated by subtree From -- not affected.
805 // (Based on the lemma 2.5 from the second paper.)
806 if (SuccLevel > RootLevel) {
807 LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
808 if (II.Visited.count(SuccTN) != 0) {
809 LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
810 << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
811 << RootLevel << ")\n");
813 // A node can be necessary to visit again if we see it again at
814 // a lower level than before.
815 if (II.Visited[SuccTN] >= RootLevel)
819 LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
820 << BlockNamePrinter(Succ) << "\n");
821 II.Visited.insert({SuccTN, RootLevel});
822 II.VisitedNotAffectedQueue.push_back(SuccTN);
823 Stack.push_back(SuccTN);
824 } else if ((SuccLevel > NCDLevel + 1) &&
825 II.Affected.count(SuccTN) == 0) {
826 LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
827 << BlockNamePrinter(Succ) << " to a Bucket\n");
828 II.Affected.insert(SuccTN);
829 II.Bucket.push({SuccLevel, SuccTN});
833 Processed.insert(Next);
834 } while (!Stack.empty());
837 // Updates immediate dominators and levels after insertion.
838 static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
839 const TreeNodePtr NCD, InsertionInfo &II) {
840 LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
842 for (const TreeNodePtr TN : II.AffectedQueue) {
843 LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
844 << ") = " << BlockNamePrinter(NCD) << "\n");
848 UpdateLevelsAfterInsertion(II);
849 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
852 static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
854 dbgs() << "Updating levels for visited but not affected nodes\n");
856 for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
857 LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
858 << BlockNamePrinter(TN->getIDom()) << ") "
859 << TN->getIDom()->getLevel() << " + 1\n");
864 // Handles insertion to previously unreachable nodes.
865 static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
866 const TreeNodePtr From, const NodePtr To) {
867 LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
868 << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
870 // Collect discovered edges to already reachable nodes.
871 SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
872 // Discover and connect nodes that became reachable with the insertion.
873 ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
875 LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
876 << " -> (prev unreachable) " << BlockNamePrinter(To)
879 // Used the discovered edges and inset discovered connecting (incoming)
881 for (const auto &Edge : DiscoveredEdgesToReachable) {
882 LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
883 << BlockNamePrinter(Edge.first) << " -> "
884 << BlockNamePrinter(Edge.second) << "\n");
885 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
889 // Connects nodes that become reachable with an insertion.
890 static void ComputeUnreachableDominators(
891 DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
892 const TreeNodePtr Incoming,
893 SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
894 &DiscoveredConnectingEdges) {
895 assert(!DT.getNode(Root) && "Root must not be reachable");
897 // Visit only previously unreachable nodes.
898 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
900 const TreeNodePtr ToTN = DT.getNode(To);
901 if (!ToTN) return true;
903 DiscoveredConnectingEdges.push_back({From, ToTN});
907 SemiNCAInfo SNCA(BUI);
908 SNCA.runDFS(Root, 0, UnreachableDescender, 0);
910 SNCA.attachNewSubtree(DT, Incoming);
912 LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
915 static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
916 const NodePtr From, const NodePtr To) {
917 assert(From && To && "Cannot disconnect nullptrs");
918 LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
919 << BlockNamePrinter(To) << "\n");
922 // Ensure that the edge was in fact deleted from the CFG before informing
923 // the DomTree about it.
924 // The check is O(N), so run it only in debug configuration.
925 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
926 auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
927 return llvm::find(Successors, SuccCandidate) != Successors.end();
930 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
933 const TreeNodePtr FromTN = DT.getNode(From);
934 // Deletion in an unreachable subtree -- nothing to do.
937 const TreeNodePtr ToTN = DT.getNode(To);
940 dbgs() << "\tTo (" << BlockNamePrinter(To)
941 << ") already unreachable -- there is no edge to delete\n");
945 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
946 const TreeNodePtr NCD = DT.getNode(NCDBlock);
948 // If To dominates From -- nothing to do.
950 DT.DFSInfoValid = false;
952 const TreeNodePtr ToIDom = ToTN->getIDom();
953 LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
954 << BlockNamePrinter(ToIDom) << "\n");
956 // To remains reachable after deletion.
957 // (Based on the caption under Figure 4. from the second paper.)
958 if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
959 DeleteReachable(DT, BUI, FromTN, ToTN);
961 DeleteUnreachable(DT, BUI, ToTN);
964 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
967 // Handles deletions that leave destination nodes reachable.
968 static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
969 const TreeNodePtr FromTN,
970 const TreeNodePtr ToTN) {
971 LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
972 << " -> " << BlockNamePrinter(ToTN) << "\n");
973 LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
975 // Find the top of the subtree that needs to be rebuilt.
976 // (Based on the lemma 2.6 from the second paper.)
977 const NodePtr ToIDom =
978 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
979 assert(ToIDom || DT.isPostDominator());
980 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
982 const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
983 // Top of the subtree to rebuild is the root node. Rebuild the tree from
985 if (!PrevIDomSubTree) {
986 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
987 CalculateFromScratch(DT, BUI);
991 // Only visit nodes in the subtree starting at To.
992 const unsigned Level = ToIDomTN->getLevel();
993 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
994 return DT.getNode(To)->getLevel() > Level;
997 LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
1000 SemiNCAInfo SNCA(BUI);
1001 SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1002 LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1003 SNCA.runSemiNCA(DT, Level);
1004 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1007 // Checks if a node has proper support, as defined on the page 3 and later
1008 // explained on the page 7 of the second paper.
1009 static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1010 const TreeNodePtr TN) {
1011 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1013 for (const NodePtr Pred :
1014 ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
1015 LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1016 if (!DT.getNode(Pred)) continue;
1018 const NodePtr Support =
1019 DT.findNearestCommonDominator(TN->getBlock(), Pred);
1020 LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1021 if (Support != TN->getBlock()) {
1022 LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1023 << " is reachable from support "
1024 << BlockNamePrinter(Support) << "\n");
1032 // Handle deletions that make destination node unreachable.
1033 // (Based on the lemma 2.7 from the second paper.)
1034 static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1035 const TreeNodePtr ToTN) {
1036 LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1037 << BlockNamePrinter(ToTN) << "\n");
1039 assert(ToTN->getBlock());
1042 // Deletion makes a region reverse-unreachable and creates a new root.
1043 // Simulate that by inserting an edge from the virtual root to ToTN and
1044 // adding it as a new root.
1045 LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1046 LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1048 DT.Roots.push_back(ToTN->getBlock());
1049 InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1053 SmallVector<NodePtr, 16> AffectedQueue;
1054 const unsigned Level = ToTN->getLevel();
1056 // Traverse destination node's descendants with greater level in the tree
1057 // and collect visited nodes.
1058 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1059 const TreeNodePtr TN = DT.getNode(To);
1061 if (TN->getLevel() > Level) return true;
1062 if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
1063 AffectedQueue.push_back(To);
1068 SemiNCAInfo SNCA(BUI);
1069 unsigned LastDFSNum =
1070 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1072 TreeNodePtr MinNode = ToTN;
1074 // Identify the top of the subtree to rebuild by finding the NCD of all
1075 // the affected nodes.
1076 for (const NodePtr N : AffectedQueue) {
1077 const TreeNodePtr TN = DT.getNode(N);
1078 const NodePtr NCDBlock =
1079 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1080 assert(NCDBlock || DT.isPostDominator());
1081 const TreeNodePtr NCD = DT.getNode(NCDBlock);
1084 LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1085 << " with NCD = " << BlockNamePrinter(NCD)
1086 << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1087 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1090 // Root reached, rebuild the whole tree from scratch.
1091 if (!MinNode->getIDom()) {
1092 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1093 CalculateFromScratch(DT, BUI);
1097 // Erase the unreachable subtree in reverse preorder to process all children
1098 // before deleting their parent.
1099 for (unsigned i = LastDFSNum; i > 0; --i) {
1100 const NodePtr N = SNCA.NumToNode[i];
1101 const TreeNodePtr TN = DT.getNode(N);
1102 LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1107 // The affected subtree start at the To node -- there's no extra work to do.
1108 if (MinNode == ToTN) return;
1110 LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1111 << BlockNamePrinter(MinNode) << "\n");
1112 const unsigned MinLevel = MinNode->getLevel();
1113 const TreeNodePtr PrevIDom = MinNode->getIDom();
1117 // Identify nodes that remain in the affected subtree.
1118 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1119 const TreeNodePtr ToTN = DT.getNode(To);
1120 return ToTN && ToTN->getLevel() > MinLevel;
1122 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1124 LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1125 << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1127 // Rebuild the remaining part of affected subtree.
1128 SNCA.runSemiNCA(DT, MinLevel);
1129 SNCA.reattachExistingSubtree(DT, PrevIDom);
1132 // Removes leaf tree nodes from the dominator tree.
1133 static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1135 assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1137 const TreeNodePtr IDom = TN->getIDom();
1140 auto ChIt = llvm::find(IDom->Children, TN);
1141 assert(ChIt != IDom->Children.end());
1142 std::swap(*ChIt, IDom->Children.back());
1143 IDom->Children.pop_back();
1145 DT.DomTreeNodes.erase(TN->getBlock());
1149 //===--------------------- DomTree Batch Updater --------------------------===
1152 static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
1153 const size_t NumUpdates = Updates.size();
1154 if (NumUpdates == 0)
1157 // Take the fast path for a single update and avoid running the batch update
1159 if (NumUpdates == 1) {
1160 const auto &Update = Updates.front();
1161 if (Update.getKind() == UpdateKind::Insert)
1162 DT.insertEdge(Update.getFrom(), Update.getTo());
1164 DT.deleteEdge(Update.getFrom(), Update.getTo());
1169 BatchUpdateInfo BUI;
1170 LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1171 cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
1173 const size_t NumLegalized = BUI.Updates.size();
1174 BUI.FutureSuccessors.reserve(NumLegalized);
1175 BUI.FuturePredecessors.reserve(NumLegalized);
1177 // Use the legalized future updates to initialize future successors and
1178 // predecessors. Note that these sets will only decrease size over time, as
1179 // the next CFG snapshots slowly approach the actual (current) CFG.
1180 for (UpdateT &U : BUI.Updates) {
1181 BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1182 BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1185 LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
1186 LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
1187 : reverse(BUI.Updates)) {
1192 LLVM_DEBUG(dbgs() << "\n");
1194 // Recalculate the DominatorTree when the number of updates
1195 // exceeds a threshold, which usually makes direct updating slower than
1196 // recalculation. We select this threshold proportional to the
1197 // size of the DominatorTree. The constant is selected
1198 // by choosing the one with an acceptable performance on some real-world
1201 // Make unittests of the incremental algorithm work
1202 if (DT.DomTreeNodes.size() <= 100) {
1203 if (NumLegalized > DT.DomTreeNodes.size())
1204 CalculateFromScratch(DT, &BUI);
1205 } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
1206 CalculateFromScratch(DT, &BUI);
1208 // If the DominatorTree was recalculated at some point, stop the batch
1209 // updates. Full recalculations ignore batch updates and look at the actual
1211 for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
1212 ApplyNextUpdate(DT, BUI);
1215 static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1216 assert(!BUI.Updates.empty() && "No updates to apply!");
1217 UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
1218 LLVM_DEBUG(dbgs() << "Applying update: ");
1219 LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1221 // Move to the next snapshot of the CFG by removing the reverse-applied
1222 // current update. Since updates are performed in the same order they are
1223 // legalized it's sufficient to pop the last item here.
1224 auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
1225 assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
1226 FS.back().getInt() == CurrentUpdate.getKind());
1228 if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
1230 auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
1231 assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
1232 FP.back().getInt() == CurrentUpdate.getKind());
1234 if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
1236 if (CurrentUpdate.getKind() == UpdateKind::Insert)
1237 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1239 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1243 //===--------------- DomTree correctness verification ---------------------===
1246 // Check if the tree has correct roots. A DominatorTree always has a single
1247 // root which is the function's entry node. A PostDominatorTree can have
1248 // multiple roots - one for each node with no successors and for infinite
1250 // Running time: O(N).
1251 bool verifyRoots(const DomTreeT &DT) {
1252 if (!DT.Parent && !DT.Roots.empty()) {
1253 errs() << "Tree has no parent but has roots!\n";
1259 if (DT.Roots.empty()) {
1260 errs() << "Tree doesn't have a root!\n";
1265 if (DT.getRoot() != GetEntryNode(DT)) {
1266 errs() << "Tree's root is not its parent's entry node!\n";
1272 RootsT ComputedRoots = FindRoots(DT, nullptr);
1273 if (DT.Roots.size() != ComputedRoots.size() ||
1274 !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
1275 ComputedRoots.begin())) {
1276 errs() << "Tree has different roots than freshly computed ones!\n";
1277 errs() << "\tPDT roots: ";
1278 for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1279 errs() << "\n\tComputed roots: ";
1280 for (const NodePtr N : ComputedRoots)
1281 errs() << BlockNamePrinter(N) << ", ";
1290 // Checks if the tree contains all reachable nodes in the input graph.
1291 // Running time: O(N).
1292 bool verifyReachability(const DomTreeT &DT) {
1294 doFullDFSWalk(DT, AlwaysDescend);
1296 for (auto &NodeToTN : DT.DomTreeNodes) {
1297 const TreeNodePtr TN = NodeToTN.second.get();
1298 const NodePtr BB = TN->getBlock();
1300 // Virtual root has a corresponding virtual CFG node.
1301 if (DT.isVirtualRoot(TN)) continue;
1303 if (NodeToInfo.count(BB) == 0) {
1304 errs() << "DomTree node " << BlockNamePrinter(BB)
1305 << " not found by DFS walk!\n";
1312 for (const NodePtr N : NumToNode) {
1313 if (N && !DT.getNode(N)) {
1314 errs() << "CFG node " << BlockNamePrinter(N)
1315 << " not found in the DomTree!\n";
1325 // Check if for every parent with a level L in the tree all of its children
1326 // have level L + 1.
1327 // Running time: O(N).
1328 static bool VerifyLevels(const DomTreeT &DT) {
1329 for (auto &NodeToTN : DT.DomTreeNodes) {
1330 const TreeNodePtr TN = NodeToTN.second.get();
1331 const NodePtr BB = TN->getBlock();
1334 const TreeNodePtr IDom = TN->getIDom();
1335 if (!IDom && TN->getLevel() != 0) {
1336 errs() << "Node without an IDom " << BlockNamePrinter(BB)
1337 << " has a nonzero level " << TN->getLevel() << "!\n";
1343 if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1344 errs() << "Node " << BlockNamePrinter(BB) << " has level "
1345 << TN->getLevel() << " while its IDom "
1346 << BlockNamePrinter(IDom->getBlock()) << " has level "
1347 << IDom->getLevel() << "!\n";
1357 // Check if the computed DFS numbers are correct. Note that DFS info may not
1358 // be valid, and when that is the case, we don't verify the numbers.
1359 // Running time: O(N log(N)).
1360 static bool VerifyDFSNumbers(const DomTreeT &DT) {
1361 if (!DT.DFSInfoValid || !DT.Parent)
1364 const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
1365 const TreeNodePtr Root = DT.getNode(RootBB);
1367 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1368 errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1369 << TN->getDFSNumOut() << '}';
1372 // Verify the root's DFS In number. Although DFS numbering would also work
1373 // if we started from some other value, we assume 0-based numbering.
1374 if (Root->getDFSNumIn() != 0) {
1375 errs() << "DFSIn number for the tree root is not:\n\t";
1376 PrintNodeAndDFSNums(Root);
1382 // For each tree node verify if children's DFS numbers cover their parent's
1383 // DFS numbers with no gaps.
1384 for (const auto &NodeToTN : DT.DomTreeNodes) {
1385 const TreeNodePtr Node = NodeToTN.second.get();
1387 // Handle tree leaves.
1388 if (Node->getChildren().empty()) {
1389 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1390 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1391 PrintNodeAndDFSNums(Node);
1400 // Make a copy and sort it such that it is possible to check if there are
1401 // no gaps between DFS numbers of adjacent children.
1402 SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1403 llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1404 return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1407 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1408 const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1411 errs() << "Incorrect DFS numbers for:\n\tParent ";
1412 PrintNodeAndDFSNums(Node);
1414 errs() << "\n\tChild ";
1415 PrintNodeAndDFSNums(FirstCh);
1418 errs() << "\n\tSecond child ";
1419 PrintNodeAndDFSNums(SecondCh);
1422 errs() << "\nAll children: ";
1423 for (const TreeNodePtr Ch : Children) {
1424 PrintNodeAndDFSNums(Ch);
1432 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1433 PrintChildrenError(Children.front(), nullptr);
1437 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1438 PrintChildrenError(Children.back(), nullptr);
1442 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1443 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1444 PrintChildrenError(Children[i], Children[i + 1]);
1453 // The below routines verify the correctness of the dominator tree relative to
1454 // the CFG it's coming from. A tree is a dominator tree iff it has two
1455 // properties, called the parent property and the sibling property. Tarjan
1456 // and Lengauer prove (but don't explicitly name) the properties as part of
1457 // the proofs in their 1972 paper, but the proofs are mostly part of proving
1458 // things about semidominators and idoms, and some of them are simply asserted
1459 // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1460 // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1461 // directed bipolar orders, and independent spanning trees" by Loukas
1462 // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1463 // and Vertex-Disjoint Paths " by the same authors.
1465 // A very simple and direct explanation of these properties can be found in
1466 // "An Experimental Study of Dynamic Dominators", found at
1467 // https://arxiv.org/abs/1604.02711
1469 // The easiest way to think of the parent property is that it's a requirement
1470 // of being a dominator. Let's just take immediate dominators. For PARENT to
1471 // be an immediate dominator of CHILD, all paths in the CFG must go through
1472 // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1473 // out of the CFG, there should be no paths to CHILD that are reachable. If
1474 // there are, then you now have a path from PARENT to CHILD that goes around
1475 // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1476 // a dominator of CHILD (let alone an immediate one).
1478 // The sibling property is similar. It says that for each pair of sibling
1479 // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1480 // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1481 // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1482 // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1483 // RIGHT, not a sibling.
1485 // It is possible to verify the parent and sibling properties in
1486 // linear time, but the algorithms are complex. Instead, we do it in a
1487 // straightforward N^2 and N^3 way below, using direct path reachability.
1489 // Checks if the tree has the parent property: if for all edges from V to W in
1490 // the input graph, such that V is reachable, the parent of W in the tree is
1491 // an ancestor of V in the tree.
1492 // Running time: O(N^2).
1494 // This means that if a node gets disconnected from the graph, then all of
1495 // the nodes it dominated previously will now become unreachable.
1496 bool verifyParentProperty(const DomTreeT &DT) {
1497 for (auto &NodeToTN : DT.DomTreeNodes) {
1498 const TreeNodePtr TN = NodeToTN.second.get();
1499 const NodePtr BB = TN->getBlock();
1500 if (!BB || TN->getChildren().empty()) continue;
1502 LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1503 << BlockNamePrinter(TN) << "\n");
1505 doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1506 return From != BB && To != BB;
1509 for (TreeNodePtr Child : TN->getChildren())
1510 if (NodeToInfo.count(Child->getBlock()) != 0) {
1511 errs() << "Child " << BlockNamePrinter(Child)
1512 << " reachable after its parent " << BlockNamePrinter(BB)
1513 << " is removed!\n";
1523 // Check if the tree has sibling property: if a node V does not dominate a
1524 // node W for all siblings V and W in the tree.
1525 // Running time: O(N^3).
1527 // This means that if a node gets disconnected from the graph, then all of its
1528 // siblings will now still be reachable.
1529 bool verifySiblingProperty(const DomTreeT &DT) {
1530 for (auto &NodeToTN : DT.DomTreeNodes) {
1531 const TreeNodePtr TN = NodeToTN.second.get();
1532 const NodePtr BB = TN->getBlock();
1533 if (!BB || TN->getChildren().empty()) continue;
1535 const auto &Siblings = TN->getChildren();
1536 for (const TreeNodePtr N : Siblings) {
1538 NodePtr BBN = N->getBlock();
1539 doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1540 return From != BBN && To != BBN;
1543 for (const TreeNodePtr S : Siblings) {
1544 if (S == N) continue;
1546 if (NodeToInfo.count(S->getBlock()) == 0) {
1547 errs() << "Node " << BlockNamePrinter(S)
1548 << " not reachable when its sibling " << BlockNamePrinter(N)
1549 << " is removed!\n";
1561 // Check if the given tree is the same as a freshly computed one for the same
1563 // Running time: O(N^2), but faster in practise (same as tree construction).
1565 // Note that this does not check if that the tree construction algorithm is
1566 // correct and should be only used for fast (but possibly unsound)
1568 static bool IsSameAsFreshTree(const DomTreeT &DT) {
1570 FreshTree.recalculate(*DT.Parent);
1571 const bool Different = DT.compare(FreshTree);
1574 errs() << (DT.isPostDominator() ? "Post" : "")
1575 << "DominatorTree is different than a freshly computed one!\n"
1578 errs() << "\n\tFreshly computed tree:\n";
1579 FreshTree.print(errs());
1587 template <class DomTreeT>
1588 void Calculate(DomTreeT &DT) {
1589 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
1592 template <typename DomTreeT>
1593 void CalculateWithUpdates(DomTreeT &DT,
1594 ArrayRef<typename DomTreeT::UpdateType> Updates) {
1595 // TODO: Move BUI creation in common method, reuse in ApplyUpdates.
1596 typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI;
1597 LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1598 cfg::LegalizeUpdates<typename DomTreeT::NodePtr>(Updates, BUI.Updates,
1599 DomTreeT::IsPostDominator);
1600 const size_t NumLegalized = BUI.Updates.size();
1601 BUI.FutureSuccessors.reserve(NumLegalized);
1602 BUI.FuturePredecessors.reserve(NumLegalized);
1603 for (auto &U : BUI.Updates) {
1604 BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1605 BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1608 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI);
1611 template <class DomTreeT>
1612 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1613 typename DomTreeT::NodePtr To) {
1614 if (DT.isPostDominator()) std::swap(From, To);
1615 SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1618 template <class DomTreeT>
1619 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1620 typename DomTreeT::NodePtr To) {
1621 if (DT.isPostDominator()) std::swap(From, To);
1622 SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1625 template <class DomTreeT>
1626 void ApplyUpdates(DomTreeT &DT,
1627 ArrayRef<typename DomTreeT::UpdateType> Updates) {
1628 SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
1631 template <class DomTreeT>
1632 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1633 SemiNCAInfo<DomTreeT> SNCA(nullptr);
1635 // Simplist check is to compare against a new tree. This will also
1636 // usefully print the old and new trees, if they are different.
1637 if (!SNCA.IsSameAsFreshTree(DT))
1640 // Common checks to verify the properties of the tree. O(N log N) at worst
1641 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1642 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1645 // Extra checks depending on VerificationLevel. Up to O(N^3)
1646 if (VL == DomTreeT::VerificationLevel::Basic ||
1647 VL == DomTreeT::VerificationLevel::Full)
1648 if (!SNCA.verifyParentProperty(DT))
1650 if (VL == DomTreeT::VerificationLevel::Full)
1651 if (!SNCA.verifySiblingProperty(DT))
1657 } // namespace DomTreeBuilder