[InstCombine] Signed saturation patterns
[llvm-complete.git] / include / llvm / Support / GenericDomTreeConstruction.h
blob7c0278e8770eede1475640405facd42d1763a57d
1 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// Generic dominator tree construction - This file provides routines to
11 /// construct immediate dominator information for a flow-graph based on the
12 /// Semi-NCA algorithm described in this dissertation:
13 ///
14 /// Linear-Time Algorithms for Dominators and Related Problems
15 /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
16 /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
17 ///
18 /// Semi-NCA algorithm runs in O(n^2) worst-case time but usually slightly
19 /// faster than Simple Lengauer-Tarjan in practice.
20 ///
21 /// O(n^2) worst cases happen when the computation of nearest common ancestors
22 /// requires O(n) average time, which is very unlikely in real world. If this
23 /// ever turns out to be an issue, consider implementing a hybrid algorithm.
24 ///
25 /// The file uses the Depth Based Search algorithm to perform incremental
26 /// updates (insertion and deletions). The implemented algorithm is based on
27 /// this publication:
28 ///
29 /// An Experimental Study of Dynamic Dominators
30 /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
31 /// https://arxiv.org/pdf/1604.02711.pdf
32 ///
33 //===----------------------------------------------------------------------===//
35 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
36 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38 #include <queue>
39 #include "llvm/ADT/ArrayRef.h"
40 #include "llvm/ADT/DenseSet.h"
41 #include "llvm/ADT/DepthFirstIterator.h"
42 #include "llvm/ADT/PointerIntPair.h"
43 #include "llvm/ADT/SmallPtrSet.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/GenericDomTree.h"
47 #define DEBUG_TYPE "dom-tree-builder"
49 namespace llvm {
50 namespace DomTreeBuilder {
52 template <typename DomTreeT>
53 struct SemiNCAInfo {
54 using NodePtr = typename DomTreeT::NodePtr;
55 using NodeT = typename DomTreeT::NodeType;
56 using TreeNodePtr = DomTreeNodeBase<NodeT> *;
57 using RootsT = decltype(DomTreeT::Roots);
58 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
60 // Information record used by Semi-NCA during tree construction.
61 struct InfoRec {
62 unsigned DFSNum = 0;
63 unsigned Parent = 0;
64 unsigned Semi = 0;
65 NodePtr Label = nullptr;
66 NodePtr IDom = nullptr;
67 SmallVector<NodePtr, 2> ReverseChildren;
70 // Number to node mapping is 1-based. Initialize the mapping to start with
71 // a dummy element.
72 std::vector<NodePtr> NumToNode = {nullptr};
73 DenseMap<NodePtr, InfoRec> NodeToInfo;
75 using UpdateT = typename DomTreeT::UpdateType;
76 using UpdateKind = typename DomTreeT::UpdateKind;
77 struct BatchUpdateInfo {
78 SmallVector<UpdateT, 4> Updates;
79 using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
81 // In order to be able to walk a CFG that is out of sync with the CFG
82 // DominatorTree last knew about, use the list of updates to reconstruct
83 // previous CFG versions of the current CFG. For each node, we store a set
84 // of its virtually added/deleted future successors and predecessors.
85 // Note that these children are from the future relative to what the
86 // DominatorTree knows about -- using them to gets us some snapshot of the
87 // CFG from the past (relative to the state of the CFG).
88 DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
89 DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
90 // Remembers if the whole tree was recalculated at some point during the
91 // current batch update.
92 bool IsRecalculated = false;
95 BatchUpdateInfo *BatchUpdates;
96 using BatchUpdatePtr = BatchUpdateInfo *;
98 // If BUI is a nullptr, then there's no batch update in progress.
99 SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
101 void clear() {
102 NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
103 NodeToInfo.clear();
104 // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
105 // in progress, we need this information to continue it.
108 template <bool Inverse>
109 struct ChildrenGetter {
110 using ResultTy = SmallVector<NodePtr, 8>;
112 static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
113 auto RChildren = reverse(children<NodePtr>(N));
114 return ResultTy(RChildren.begin(), RChildren.end());
117 static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
118 auto IChildren = inverse_children<NodePtr>(N);
119 return ResultTy(IChildren.begin(), IChildren.end());
122 using Tag = std::integral_constant<bool, Inverse>;
124 // The function below is the core part of the batch updater. It allows the
125 // Depth Based Search algorithm to perform incremental updates in lockstep
126 // with updates to the CFG. We emulated lockstep CFG updates by getting its
127 // next snapshots by reverse-applying future updates.
128 static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
129 ResultTy Res = Get(N, Tag());
130 // If there's no batch update in progress, simply return node's children.
131 if (!BUI) return Res;
133 // CFG children are actually its *most current* children, and we have to
134 // reverse-apply the future updates to get the node's children at the
135 // point in time the update was performed.
136 auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
137 : BUI->FutureSuccessors;
138 auto FCIt = FutureChildren.find(N);
139 if (FCIt == FutureChildren.end()) return Res;
141 for (auto ChildAndKind : FCIt->second) {
142 const NodePtr Child = ChildAndKind.getPointer();
143 const UpdateKind UK = ChildAndKind.getInt();
145 // Reverse-apply the future update.
146 if (UK == UpdateKind::Insert) {
147 // If there's an insertion in the future, it means that the edge must
148 // exist in the current CFG, but was not present in it before.
149 assert(llvm::find(Res, Child) != Res.end()
150 && "Expected child not found in the CFG");
151 Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
152 LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
153 << BlockNamePrinter(Child) << "\n");
154 } else {
155 // If there's an deletion in the future, it means that the edge cannot
156 // exist in the current CFG, but existed in it before.
157 assert(llvm::find(Res, Child) == Res.end() &&
158 "Unexpected child found in the CFG");
159 LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
160 << " -> " << BlockNamePrinter(Child) << "\n");
161 Res.push_back(Child);
165 return Res;
169 NodePtr getIDom(NodePtr BB) const {
170 auto InfoIt = NodeToInfo.find(BB);
171 if (InfoIt == NodeToInfo.end()) return nullptr;
173 return InfoIt->second.IDom;
176 TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
177 if (TreeNodePtr Node = DT.getNode(BB)) return Node;
179 // Haven't calculated this node yet? Get or calculate the node for the
180 // immediate dominator.
181 NodePtr IDom = getIDom(BB);
183 assert(IDom || DT.DomTreeNodes[nullptr]);
184 TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
186 // Add a new tree node for this NodeT, and link it as a child of
187 // IDomNode
188 return (DT.DomTreeNodes[BB] = IDomNode->addChild(
189 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
190 .get();
193 static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
195 struct BlockNamePrinter {
196 NodePtr N;
198 BlockNamePrinter(NodePtr Block) : N(Block) {}
199 BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
201 friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
202 if (!BP.N)
203 O << "nullptr";
204 else
205 BP.N->printAsOperand(O, false);
207 return O;
211 // Custom DFS implementation which can skip nodes based on a provided
212 // predicate. It also collects ReverseChildren so that we don't have to spend
213 // time getting predecessors in SemiNCA.
215 // If IsReverse is set to true, the DFS walk will be performed backwards
216 // relative to IsPostDom -- using reverse edges for dominators and forward
217 // edges for postdominators.
218 template <bool IsReverse = false, typename DescendCondition>
219 unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
220 unsigned AttachToNum) {
221 assert(V);
222 SmallVector<NodePtr, 64> WorkList = {V};
223 if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
225 while (!WorkList.empty()) {
226 const NodePtr BB = WorkList.pop_back_val();
227 auto &BBInfo = NodeToInfo[BB];
229 // Visited nodes always have positive DFS numbers.
230 if (BBInfo.DFSNum != 0) continue;
231 BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
232 BBInfo.Label = BB;
233 NumToNode.push_back(BB);
235 constexpr bool Direction = IsReverse != IsPostDom; // XOR.
236 for (const NodePtr Succ :
237 ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
238 const auto SIT = NodeToInfo.find(Succ);
239 // Don't visit nodes more than once but remember to collect
240 // ReverseChildren.
241 if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
242 if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
243 continue;
246 if (!Condition(BB, Succ)) continue;
248 // It's fine to add Succ to the map, because we know that it will be
249 // visited later.
250 auto &SuccInfo = NodeToInfo[Succ];
251 WorkList.push_back(Succ);
252 SuccInfo.Parent = LastNum;
253 SuccInfo.ReverseChildren.push_back(BB);
257 return LastNum;
260 // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum
261 // of sdom(U), where U > W and there is a virtual forest path from U to V. The
262 // virtual forest consists of linked edges of processed vertices.
264 // We can follow Parent pointers (virtual forest edges) to determine the
265 // ancestor U with minimum sdom(U). But it is slow and thus we employ the path
266 // compression technique to speed up to O(m*log(n)). Theoretically the virtual
267 // forest can be organized as balanced trees to achieve almost linear
268 // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size
269 // and Child) and is unlikely to be faster than the simple implementation.
271 // For each vertex V, its Label points to the vertex with the minimal sdom(U)
272 // (Semi) in its path from V (included) to NodeToInfo[V].Parent (excluded).
273 NodePtr eval(NodePtr V, unsigned LastLinked,
274 SmallVectorImpl<InfoRec *> &Stack) {
275 InfoRec *VInfo = &NodeToInfo[V];
276 if (VInfo->Parent < LastLinked)
277 return VInfo->Label;
279 // Store ancestors except the last (root of a virtual tree) into a stack.
280 assert(Stack.empty());
281 do {
282 Stack.push_back(VInfo);
283 VInfo = &NodeToInfo[NumToNode[VInfo->Parent]];
284 } while (VInfo->Parent >= LastLinked);
286 // Path compression. Point each vertex's Parent to the root and update its
287 // Label if any of its ancestors (PInfo->Label) has a smaller Semi.
288 const InfoRec *PInfo = VInfo;
289 const InfoRec *PLabelInfo = &NodeToInfo[PInfo->Label];
290 do {
291 VInfo = Stack.pop_back_val();
292 VInfo->Parent = PInfo->Parent;
293 const InfoRec *VLabelInfo = &NodeToInfo[VInfo->Label];
294 if (PLabelInfo->Semi < VLabelInfo->Semi)
295 VInfo->Label = PInfo->Label;
296 else
297 PLabelInfo = VLabelInfo;
298 PInfo = VInfo;
299 } while (!Stack.empty());
300 return VInfo->Label;
303 // This function requires DFS to be run before calling it.
304 void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
305 const unsigned NextDFSNum(NumToNode.size());
306 // Initialize IDoms to spanning tree parents.
307 for (unsigned i = 1; i < NextDFSNum; ++i) {
308 const NodePtr V = NumToNode[i];
309 auto &VInfo = NodeToInfo[V];
310 VInfo.IDom = NumToNode[VInfo.Parent];
313 // Step #1: Calculate the semidominators of all vertices.
314 SmallVector<InfoRec *, 32> EvalStack;
315 for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
316 NodePtr W = NumToNode[i];
317 auto &WInfo = NodeToInfo[W];
319 // Initialize the semi dominator to point to the parent node.
320 WInfo.Semi = WInfo.Parent;
321 for (const auto &N : WInfo.ReverseChildren) {
322 if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
323 continue;
325 const TreeNodePtr TN = DT.getNode(N);
326 // Skip predecessors whose level is above the subtree we are processing.
327 if (TN && TN->getLevel() < MinLevel)
328 continue;
330 unsigned SemiU = NodeToInfo[eval(N, i + 1, EvalStack)].Semi;
331 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
335 // Step #2: Explicitly define the immediate dominator of each vertex.
336 // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
337 // Note that the parents were stored in IDoms and later got invalidated
338 // during path compression in Eval.
339 for (unsigned i = 2; i < NextDFSNum; ++i) {
340 const NodePtr W = NumToNode[i];
341 auto &WInfo = NodeToInfo[W];
342 const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
343 NodePtr WIDomCandidate = WInfo.IDom;
344 while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
345 WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
347 WInfo.IDom = WIDomCandidate;
351 // PostDominatorTree always has a virtual root that represents a virtual CFG
352 // node that serves as a single exit from the function. All the other exits
353 // (CFG nodes with terminators and nodes in infinite loops are logically
354 // connected to this virtual CFG exit node).
355 // This functions maps a nullptr CFG node to the virtual root tree node.
356 void addVirtualRoot() {
357 assert(IsPostDom && "Only postdominators have a virtual root");
358 assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
360 auto &BBInfo = NodeToInfo[nullptr];
361 BBInfo.DFSNum = BBInfo.Semi = 1;
362 BBInfo.Label = nullptr;
364 NumToNode.push_back(nullptr); // NumToNode[1] = nullptr;
367 // For postdominators, nodes with no forward successors are trivial roots that
368 // are always selected as tree roots. Roots with forward successors correspond
369 // to CFG nodes within infinite loops.
370 static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
371 assert(N && "N must be a valid node");
372 return !ChildrenGetter<false>::Get(N, BUI).empty();
375 static NodePtr GetEntryNode(const DomTreeT &DT) {
376 assert(DT.Parent && "Parent not set");
377 return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
380 // Finds all roots without relaying on the set of roots already stored in the
381 // tree.
382 // We define roots to be some non-redundant set of the CFG nodes
383 static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
384 assert(DT.Parent && "Parent pointer is not set");
385 RootsT Roots;
387 // For dominators, function entry CFG node is always a tree root node.
388 if (!IsPostDom) {
389 Roots.push_back(GetEntryNode(DT));
390 return Roots;
393 SemiNCAInfo SNCA(BUI);
395 // PostDominatorTree always has a virtual root.
396 SNCA.addVirtualRoot();
397 unsigned Num = 1;
399 LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
401 // Step #1: Find all the trivial roots that are going to will definitely
402 // remain tree roots.
403 unsigned Total = 0;
404 // It may happen that there are some new nodes in the CFG that are result of
405 // the ongoing batch update, but we cannot really pretend that they don't
406 // exist -- we won't see any outgoing or incoming edges to them, so it's
407 // fine to discover them here, as they would end up appearing in the CFG at
408 // some point anyway.
409 for (const NodePtr N : nodes(DT.Parent)) {
410 ++Total;
411 // If it has no *successors*, it is definitely a root.
412 if (!HasForwardSuccessors(N, BUI)) {
413 Roots.push_back(N);
414 // Run DFS not to walk this part of CFG later.
415 Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
416 LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
417 << "\n");
418 LLVM_DEBUG(dbgs() << "Last visited node: "
419 << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
423 LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
425 // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
426 // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
427 // nodes in infinite loops).
428 bool HasNonTrivialRoots = false;
429 // Accounting for the virtual exit, see if we had any reverse-unreachable
430 // nodes.
431 if (Total + 1 != Num) {
432 HasNonTrivialRoots = true;
433 // Make another DFS pass over all other nodes to find the
434 // reverse-unreachable blocks, and find the furthest paths we'll be able
435 // to make.
436 // Note that this looks N^2, but it's really 2N worst case, if every node
437 // is unreachable. This is because we are still going to only visit each
438 // unreachable node once, we may just visit it in two directions,
439 // depending on how lucky we get.
440 SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
441 for (const NodePtr I : nodes(DT.Parent)) {
442 if (SNCA.NodeToInfo.count(I) == 0) {
443 LLVM_DEBUG(dbgs()
444 << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
445 // Find the furthest away we can get by following successors, then
446 // follow them in reverse. This gives us some reasonable answer about
447 // the post-dom tree inside any infinite loop. In particular, it
448 // guarantees we get to the farthest away point along *some*
449 // path. This also matches the GCC's behavior.
450 // If we really wanted a totally complete picture of dominance inside
451 // this infinite loop, we could do it with SCC-like algorithms to find
452 // the lowest and highest points in the infinite loop. In theory, it
453 // would be nice to give the canonical backedge for the loop, but it's
454 // expensive and does not always lead to a minimal set of roots.
455 LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
457 const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
458 const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
459 LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
460 << "(non-trivial root): "
461 << BlockNamePrinter(FurthestAway) << "\n");
462 ConnectToExitBlock.insert(FurthestAway);
463 Roots.push_back(FurthestAway);
464 LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
465 << NewNum << "\n\t\t\tRemoving DFS info\n");
466 for (unsigned i = NewNum; i > Num; --i) {
467 const NodePtr N = SNCA.NumToNode[i];
468 LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
469 << BlockNamePrinter(N) << "\n");
470 SNCA.NodeToInfo.erase(N);
471 SNCA.NumToNode.pop_back();
473 const unsigned PrevNum = Num;
474 LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
475 Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
476 for (unsigned i = PrevNum + 1; i <= Num; ++i)
477 LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
478 << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
483 LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
484 LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
485 LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
486 << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
488 assert((Total + 1 == Num) && "Everything should have been visited");
490 // Step #3: If we found some non-trivial roots, make them non-redundant.
491 if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
493 LLVM_DEBUG(dbgs() << "Found roots: ");
494 LLVM_DEBUG(for (auto *Root
495 : Roots) dbgs()
496 << BlockNamePrinter(Root) << " ");
497 LLVM_DEBUG(dbgs() << "\n");
499 return Roots;
502 // This function only makes sense for postdominators.
503 // We define roots to be some set of CFG nodes where (reverse) DFS walks have
504 // to start in order to visit all the CFG nodes (including the
505 // reverse-unreachable ones).
506 // When the search for non-trivial roots is done it may happen that some of
507 // the non-trivial roots are reverse-reachable from other non-trivial roots,
508 // which makes them redundant. This function removes them from the set of
509 // input roots.
510 static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
511 RootsT &Roots) {
512 assert(IsPostDom && "This function is for postdominators only");
513 LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
515 SemiNCAInfo SNCA(BUI);
517 for (unsigned i = 0; i < Roots.size(); ++i) {
518 auto &Root = Roots[i];
519 // Trivial roots are always non-redundant.
520 if (!HasForwardSuccessors(Root, BUI)) continue;
521 LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
522 << " remains a root\n");
523 SNCA.clear();
524 // Do a forward walk looking for the other roots.
525 const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
526 // Skip the start node and begin from the second one (note that DFS uses
527 // 1-based indexing).
528 for (unsigned x = 2; x <= Num; ++x) {
529 const NodePtr N = SNCA.NumToNode[x];
530 // If we wound another root in a (forward) DFS walk, remove the current
531 // root from the set of roots, as it is reverse-reachable from the other
532 // one.
533 if (llvm::find(Roots, N) != Roots.end()) {
534 LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
535 << BlockNamePrinter(N) << "\n\tRemoving root "
536 << BlockNamePrinter(Root) << "\n");
537 std::swap(Root, Roots.back());
538 Roots.pop_back();
540 // Root at the back takes the current root's place.
541 // Start the next loop iteration with the same index.
542 --i;
543 break;
549 template <typename DescendCondition>
550 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
551 if (!IsPostDom) {
552 assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
553 runDFS(DT.Roots[0], 0, DC, 0);
554 return;
557 addVirtualRoot();
558 unsigned Num = 1;
559 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
562 static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
563 auto *Parent = DT.Parent;
564 DT.reset();
565 DT.Parent = Parent;
566 SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree,
567 // there's no point doing it incrementally.
569 // Step #0: Number blocks in depth-first order and initialize variables used
570 // in later stages of the algorithm.
571 DT.Roots = FindRoots(DT, nullptr);
572 SNCA.doFullDFSWalk(DT, AlwaysDescend);
574 SNCA.runSemiNCA(DT);
575 if (BUI) {
576 BUI->IsRecalculated = true;
577 LLVM_DEBUG(
578 dbgs() << "DomTree recalculated, skipping future batch updates\n");
581 if (DT.Roots.empty()) return;
583 // Add a node for the root. If the tree is a PostDominatorTree it will be
584 // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
585 // all real exits (including multiple exit blocks, infinite loops).
586 NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
588 DT.RootNode = (DT.DomTreeNodes[Root] =
589 std::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
590 .get();
591 SNCA.attachNewSubtree(DT, DT.RootNode);
594 void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
595 // Attach the first unreachable block to AttachTo.
596 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
597 // Loop over all of the discovered blocks in the function...
598 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
599 NodePtr W = NumToNode[i];
600 LLVM_DEBUG(dbgs() << "\tdiscovered a new reachable node "
601 << BlockNamePrinter(W) << "\n");
603 // Don't replace this with 'count', the insertion side effect is important
604 if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
606 NodePtr ImmDom = getIDom(W);
608 // Get or calculate the node for the immediate dominator.
609 TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
611 // Add a new tree node for this BasicBlock, and link it as a child of
612 // IDomNode.
613 DT.DomTreeNodes[W] = IDomNode->addChild(
614 std::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
618 void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
619 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
620 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
621 const NodePtr N = NumToNode[i];
622 const TreeNodePtr TN = DT.getNode(N);
623 assert(TN);
624 const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
625 TN->setIDom(NewIDom);
629 // Helper struct used during edge insertions.
630 struct InsertionInfo {
631 struct Compare {
632 bool operator()(TreeNodePtr LHS, TreeNodePtr RHS) const {
633 return LHS->getLevel() < RHS->getLevel();
637 // Bucket queue of tree nodes ordered by descending level. For simplicity,
638 // we use a priority_queue here.
639 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
640 Compare>
641 Bucket;
642 SmallDenseSet<TreeNodePtr, 8> Visited;
643 SmallVector<TreeNodePtr, 8> Affected;
644 #ifndef NDEBUG
645 SmallVector<TreeNodePtr, 8> VisitedUnaffected;
646 #endif
649 static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
650 const NodePtr From, const NodePtr To) {
651 assert((From || IsPostDom) &&
652 "From has to be a valid CFG node or a virtual root");
653 assert(To && "Cannot be a nullptr");
654 LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
655 << BlockNamePrinter(To) << "\n");
656 TreeNodePtr FromTN = DT.getNode(From);
658 if (!FromTN) {
659 // Ignore edges from unreachable nodes for (forward) dominators.
660 if (!IsPostDom) return;
662 // The unreachable node becomes a new root -- a tree node for it.
663 TreeNodePtr VirtualRoot = DT.getNode(nullptr);
664 FromTN =
665 (DT.DomTreeNodes[From] = VirtualRoot->addChild(
666 std::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
667 .get();
668 DT.Roots.push_back(From);
671 DT.DFSInfoValid = false;
673 const TreeNodePtr ToTN = DT.getNode(To);
674 if (!ToTN)
675 InsertUnreachable(DT, BUI, FromTN, To);
676 else
677 InsertReachable(DT, BUI, FromTN, ToTN);
680 // Determines if some existing root becomes reverse-reachable after the
681 // insertion. Rebuilds the whole tree if that situation happens.
682 static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
683 const TreeNodePtr From,
684 const TreeNodePtr To) {
685 assert(IsPostDom && "This function is only for postdominators");
686 // Destination node is not attached to the virtual root, so it cannot be a
687 // root.
688 if (!DT.isVirtualRoot(To->getIDom())) return false;
690 auto RIt = llvm::find(DT.Roots, To->getBlock());
691 if (RIt == DT.Roots.end())
692 return false; // To is not a root, nothing to update.
694 LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
695 << " is no longer a root\n\t\tRebuilding the tree!!!\n");
697 CalculateFromScratch(DT, BUI);
698 return true;
701 static bool isPermutation(const SmallVectorImpl<NodePtr> &A,
702 const SmallVectorImpl<NodePtr> &B) {
703 if (A.size() != B.size())
704 return false;
705 SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end());
706 for (NodePtr N : B)
707 if (Set.count(N) == 0)
708 return false;
709 return true;
712 // Updates the set of roots after insertion or deletion. This ensures that
713 // roots are the same when after a series of updates and when the tree would
714 // be built from scratch.
715 static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
716 assert(IsPostDom && "This function is only for postdominators");
718 // The tree has only trivial roots -- nothing to update.
719 if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
720 return HasForwardSuccessors(N, BUI);
722 return;
724 // Recalculate the set of roots.
725 RootsT Roots = FindRoots(DT, BUI);
726 if (!isPermutation(DT.Roots, Roots)) {
727 // The roots chosen in the CFG have changed. This is because the
728 // incremental algorithm does not really know or use the set of roots and
729 // can make a different (implicit) decision about which node within an
730 // infinite loop becomes a root.
732 LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
733 << "The entire tree needs to be rebuilt\n");
734 // It may be possible to update the tree without recalculating it, but
735 // we do not know yet how to do it, and it happens rarely in practise.
736 CalculateFromScratch(DT, BUI);
740 // Handles insertion to a node already in the dominator tree.
741 static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
742 const TreeNodePtr From, const TreeNodePtr To) {
743 LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
744 << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
745 if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
746 // DT.findNCD expects both pointers to be valid. When From is a virtual
747 // root, then its CFG block pointer is a nullptr, so we have to 'compute'
748 // the NCD manually.
749 const NodePtr NCDBlock =
750 (From->getBlock() && To->getBlock())
751 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
752 : nullptr;
753 assert(NCDBlock || DT.isPostDominator());
754 const TreeNodePtr NCD = DT.getNode(NCDBlock);
755 assert(NCD);
757 LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
758 const unsigned NCDLevel = NCD->getLevel();
760 // Based on Lemma 2.5 from the second paper, after insertion of (From,To), v
761 // is affected iff depth(NCD)+1 < depth(v) && a path P from To to v exists
762 // where every w on P s.t. depth(v) <= depth(w)
764 // This reduces to a widest path problem (maximizing the depth of the
765 // minimum vertex in the path) which can be solved by a modified version of
766 // Dijkstra with a bucket queue (named depth-based search in the paper).
768 // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing
769 // affected if this does not hold.
770 if (NCDLevel + 1 >= To->getLevel())
771 return;
773 InsertionInfo II;
774 SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel;
775 II.Bucket.push(To);
776 II.Visited.insert(To);
778 while (!II.Bucket.empty()) {
779 TreeNodePtr TN = II.Bucket.top();
780 II.Bucket.pop();
781 II.Affected.push_back(TN);
783 const unsigned CurrentLevel = TN->getLevel();
784 LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) <<
785 "as affected, CurrentLevel " << CurrentLevel << "\n");
787 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
789 while (true) {
790 // Unlike regular Dijkstra, we have an inner loop to expand more
791 // vertices. The first iteration is for the (affected) vertex popped
792 // from II.Bucket and the rest are for vertices in
793 // UnaffectedOnCurrentLevel, which may eventually expand to affected
794 // vertices.
796 // Invariant: there is an optimal path from `To` to TN with the minimum
797 // depth being CurrentLevel.
798 for (const NodePtr Succ :
799 ChildrenGetter<IsPostDom>::Get(TN->getBlock(), BUI)) {
800 const TreeNodePtr SuccTN = DT.getNode(Succ);
801 assert(SuccTN &&
802 "Unreachable successor found at reachable insertion");
803 const unsigned SuccLevel = SuccTN->getLevel();
805 LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
806 << ", level = " << SuccLevel << "\n");
808 // There is an optimal path from `To` to Succ with the minimum depth
809 // being min(CurrentLevel, SuccLevel).
811 // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected
812 // and no affected vertex may be reached by a path passing through it.
813 // Stop here. Also, Succ may be visited by other predecessors but the
814 // first visit has the optimal path. Stop if Succ has been visited.
815 if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
816 continue;
818 if (SuccLevel > CurrentLevel) {
819 // Succ is unaffected but it may (transitively) expand to affected
820 // vertices. Store it in UnaffectedOnCurrentLevel.
821 LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
822 << BlockNamePrinter(Succ) << "\n");
823 UnaffectedOnCurrentLevel.push_back(SuccTN);
824 #ifndef NDEBUG
825 II.VisitedUnaffected.push_back(SuccTN);
826 #endif
827 } else {
828 // The condition is satisfied (Succ is affected). Add Succ to the
829 // bucket queue.
830 LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ)
831 << " to a Bucket\n");
832 II.Bucket.push(SuccTN);
836 if (UnaffectedOnCurrentLevel.empty())
837 break;
838 TN = UnaffectedOnCurrentLevel.pop_back_val();
839 LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
843 // Finish by updating immediate dominators and levels.
844 UpdateInsertion(DT, BUI, NCD, II);
847 // Updates immediate dominators and levels after insertion.
848 static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
849 const TreeNodePtr NCD, InsertionInfo &II) {
850 LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
852 for (const TreeNodePtr TN : II.Affected) {
853 LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
854 << ") = " << BlockNamePrinter(NCD) << "\n");
855 TN->setIDom(NCD);
858 #ifndef NDEBUG
859 for (const TreeNodePtr TN : II.VisitedUnaffected)
860 assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 &&
861 "TN should have been updated by an affected ancestor");
862 #endif
864 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
867 // Handles insertion to previously unreachable nodes.
868 static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
869 const TreeNodePtr From, const NodePtr To) {
870 LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
871 << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
873 // Collect discovered edges to already reachable nodes.
874 SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
875 // Discover and connect nodes that became reachable with the insertion.
876 ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
878 LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
879 << " -> (prev unreachable) " << BlockNamePrinter(To)
880 << "\n");
882 // Used the discovered edges and inset discovered connecting (incoming)
883 // edges.
884 for (const auto &Edge : DiscoveredEdgesToReachable) {
885 LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
886 << BlockNamePrinter(Edge.first) << " -> "
887 << BlockNamePrinter(Edge.second) << "\n");
888 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
892 // Connects nodes that become reachable with an insertion.
893 static void ComputeUnreachableDominators(
894 DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
895 const TreeNodePtr Incoming,
896 SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
897 &DiscoveredConnectingEdges) {
898 assert(!DT.getNode(Root) && "Root must not be reachable");
900 // Visit only previously unreachable nodes.
901 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
902 NodePtr To) {
903 const TreeNodePtr ToTN = DT.getNode(To);
904 if (!ToTN) return true;
906 DiscoveredConnectingEdges.push_back({From, ToTN});
907 return false;
910 SemiNCAInfo SNCA(BUI);
911 SNCA.runDFS(Root, 0, UnreachableDescender, 0);
912 SNCA.runSemiNCA(DT);
913 SNCA.attachNewSubtree(DT, Incoming);
915 LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
918 static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
919 const NodePtr From, const NodePtr To) {
920 assert(From && To && "Cannot disconnect nullptrs");
921 LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
922 << BlockNamePrinter(To) << "\n");
924 #ifndef NDEBUG
925 // Ensure that the edge was in fact deleted from the CFG before informing
926 // the DomTree about it.
927 // The check is O(N), so run it only in debug configuration.
928 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
929 auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
930 return llvm::find(Successors, SuccCandidate) != Successors.end();
932 (void)IsSuccessor;
933 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
934 #endif
936 const TreeNodePtr FromTN = DT.getNode(From);
937 // Deletion in an unreachable subtree -- nothing to do.
938 if (!FromTN) return;
940 const TreeNodePtr ToTN = DT.getNode(To);
941 if (!ToTN) {
942 LLVM_DEBUG(
943 dbgs() << "\tTo (" << BlockNamePrinter(To)
944 << ") already unreachable -- there is no edge to delete\n");
945 return;
948 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
949 const TreeNodePtr NCD = DT.getNode(NCDBlock);
951 // If To dominates From -- nothing to do.
952 if (ToTN != NCD) {
953 DT.DFSInfoValid = false;
955 const TreeNodePtr ToIDom = ToTN->getIDom();
956 LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
957 << BlockNamePrinter(ToIDom) << "\n");
959 // To remains reachable after deletion.
960 // (Based on the caption under Figure 4. from the second paper.)
961 if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
962 DeleteReachable(DT, BUI, FromTN, ToTN);
963 else
964 DeleteUnreachable(DT, BUI, ToTN);
967 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
970 // Handles deletions that leave destination nodes reachable.
971 static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
972 const TreeNodePtr FromTN,
973 const TreeNodePtr ToTN) {
974 LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
975 << " -> " << BlockNamePrinter(ToTN) << "\n");
976 LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
978 // Find the top of the subtree that needs to be rebuilt.
979 // (Based on the lemma 2.6 from the second paper.)
980 const NodePtr ToIDom =
981 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
982 assert(ToIDom || DT.isPostDominator());
983 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
984 assert(ToIDomTN);
985 const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
986 // Top of the subtree to rebuild is the root node. Rebuild the tree from
987 // scratch.
988 if (!PrevIDomSubTree) {
989 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
990 CalculateFromScratch(DT, BUI);
991 return;
994 // Only visit nodes in the subtree starting at To.
995 const unsigned Level = ToIDomTN->getLevel();
996 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
997 return DT.getNode(To)->getLevel() > Level;
1000 LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
1001 << "\n");
1003 SemiNCAInfo SNCA(BUI);
1004 SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1005 LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1006 SNCA.runSemiNCA(DT, Level);
1007 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1010 // Checks if a node has proper support, as defined on the page 3 and later
1011 // explained on the page 7 of the second paper.
1012 static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1013 const TreeNodePtr TN) {
1014 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1015 << "\n");
1016 for (const NodePtr Pred :
1017 ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
1018 LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1019 if (!DT.getNode(Pred)) continue;
1021 const NodePtr Support =
1022 DT.findNearestCommonDominator(TN->getBlock(), Pred);
1023 LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1024 if (Support != TN->getBlock()) {
1025 LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1026 << " is reachable from support "
1027 << BlockNamePrinter(Support) << "\n");
1028 return true;
1032 return false;
1035 // Handle deletions that make destination node unreachable.
1036 // (Based on the lemma 2.7 from the second paper.)
1037 static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1038 const TreeNodePtr ToTN) {
1039 LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1040 << BlockNamePrinter(ToTN) << "\n");
1041 assert(ToTN);
1042 assert(ToTN->getBlock());
1044 if (IsPostDom) {
1045 // Deletion makes a region reverse-unreachable and creates a new root.
1046 // Simulate that by inserting an edge from the virtual root to ToTN and
1047 // adding it as a new root.
1048 LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1049 LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1050 << "\n");
1051 DT.Roots.push_back(ToTN->getBlock());
1052 InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1053 return;
1056 SmallVector<NodePtr, 16> AffectedQueue;
1057 const unsigned Level = ToTN->getLevel();
1059 // Traverse destination node's descendants with greater level in the tree
1060 // and collect visited nodes.
1061 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1062 const TreeNodePtr TN = DT.getNode(To);
1063 assert(TN);
1064 if (TN->getLevel() > Level) return true;
1065 if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
1066 AffectedQueue.push_back(To);
1068 return false;
1071 SemiNCAInfo SNCA(BUI);
1072 unsigned LastDFSNum =
1073 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1075 TreeNodePtr MinNode = ToTN;
1077 // Identify the top of the subtree to rebuild by finding the NCD of all
1078 // the affected nodes.
1079 for (const NodePtr N : AffectedQueue) {
1080 const TreeNodePtr TN = DT.getNode(N);
1081 const NodePtr NCDBlock =
1082 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1083 assert(NCDBlock || DT.isPostDominator());
1084 const TreeNodePtr NCD = DT.getNode(NCDBlock);
1085 assert(NCD);
1087 LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1088 << " with NCD = " << BlockNamePrinter(NCD)
1089 << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1090 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1093 // Root reached, rebuild the whole tree from scratch.
1094 if (!MinNode->getIDom()) {
1095 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1096 CalculateFromScratch(DT, BUI);
1097 return;
1100 // Erase the unreachable subtree in reverse preorder to process all children
1101 // before deleting their parent.
1102 for (unsigned i = LastDFSNum; i > 0; --i) {
1103 const NodePtr N = SNCA.NumToNode[i];
1104 const TreeNodePtr TN = DT.getNode(N);
1105 LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1107 EraseNode(DT, TN);
1110 // The affected subtree start at the To node -- there's no extra work to do.
1111 if (MinNode == ToTN) return;
1113 LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1114 << BlockNamePrinter(MinNode) << "\n");
1115 const unsigned MinLevel = MinNode->getLevel();
1116 const TreeNodePtr PrevIDom = MinNode->getIDom();
1117 assert(PrevIDom);
1118 SNCA.clear();
1120 // Identify nodes that remain in the affected subtree.
1121 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1122 const TreeNodePtr ToTN = DT.getNode(To);
1123 return ToTN && ToTN->getLevel() > MinLevel;
1125 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1127 LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1128 << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1130 // Rebuild the remaining part of affected subtree.
1131 SNCA.runSemiNCA(DT, MinLevel);
1132 SNCA.reattachExistingSubtree(DT, PrevIDom);
1135 // Removes leaf tree nodes from the dominator tree.
1136 static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1137 assert(TN);
1138 assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1140 const TreeNodePtr IDom = TN->getIDom();
1141 assert(IDom);
1143 auto ChIt = llvm::find(IDom->Children, TN);
1144 assert(ChIt != IDom->Children.end());
1145 std::swap(*ChIt, IDom->Children.back());
1146 IDom->Children.pop_back();
1148 DT.DomTreeNodes.erase(TN->getBlock());
1151 //~~
1152 //===--------------------- DomTree Batch Updater --------------------------===
1153 //~~
1155 static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
1156 const size_t NumUpdates = Updates.size();
1157 if (NumUpdates == 0)
1158 return;
1160 // Take the fast path for a single update and avoid running the batch update
1161 // machinery.
1162 if (NumUpdates == 1) {
1163 const auto &Update = Updates.front();
1164 if (Update.getKind() == UpdateKind::Insert)
1165 DT.insertEdge(Update.getFrom(), Update.getTo());
1166 else
1167 DT.deleteEdge(Update.getFrom(), Update.getTo());
1169 return;
1172 BatchUpdateInfo BUI;
1173 LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1174 cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
1176 const size_t NumLegalized = BUI.Updates.size();
1177 BUI.FutureSuccessors.reserve(NumLegalized);
1178 BUI.FuturePredecessors.reserve(NumLegalized);
1180 // Use the legalized future updates to initialize future successors and
1181 // predecessors. Note that these sets will only decrease size over time, as
1182 // the next CFG snapshots slowly approach the actual (current) CFG.
1183 for (UpdateT &U : BUI.Updates) {
1184 BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1185 BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1188 #if 0
1189 // FIXME: The LLVM_DEBUG macro only plays well with a modular
1190 // build of LLVM when the header is marked as textual, but doing
1191 // so causes redefinition errors.
1192 LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
1193 LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
1194 : reverse(BUI.Updates)) {
1195 dbgs() << "\t";
1196 U.dump();
1197 dbgs() << "\n";
1199 LLVM_DEBUG(dbgs() << "\n");
1200 #endif
1202 // Recalculate the DominatorTree when the number of updates
1203 // exceeds a threshold, which usually makes direct updating slower than
1204 // recalculation. We select this threshold proportional to the
1205 // size of the DominatorTree. The constant is selected
1206 // by choosing the one with an acceptable performance on some real-world
1207 // inputs.
1209 // Make unittests of the incremental algorithm work
1210 if (DT.DomTreeNodes.size() <= 100) {
1211 if (NumLegalized > DT.DomTreeNodes.size())
1212 CalculateFromScratch(DT, &BUI);
1213 } else if (NumLegalized > DT.DomTreeNodes.size() / 40)
1214 CalculateFromScratch(DT, &BUI);
1216 // If the DominatorTree was recalculated at some point, stop the batch
1217 // updates. Full recalculations ignore batch updates and look at the actual
1218 // CFG.
1219 for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
1220 ApplyNextUpdate(DT, BUI);
1223 static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1224 assert(!BUI.Updates.empty() && "No updates to apply!");
1225 UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
1226 #if 0
1227 // FIXME: The LLVM_DEBUG macro only plays well with a modular
1228 // build of LLVM when the header is marked as textual, but doing
1229 // so causes redefinition errors.
1230 LLVM_DEBUG(dbgs() << "Applying update: ");
1231 LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1232 #endif
1234 // Move to the next snapshot of the CFG by removing the reverse-applied
1235 // current update. Since updates are performed in the same order they are
1236 // legalized it's sufficient to pop the last item here.
1237 auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
1238 assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
1239 FS.back().getInt() == CurrentUpdate.getKind());
1240 FS.pop_back();
1241 if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
1243 auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
1244 assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
1245 FP.back().getInt() == CurrentUpdate.getKind());
1246 FP.pop_back();
1247 if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
1249 if (CurrentUpdate.getKind() == UpdateKind::Insert)
1250 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1251 else
1252 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1255 //~~
1256 //===--------------- DomTree correctness verification ---------------------===
1257 //~~
1259 // Check if the tree has correct roots. A DominatorTree always has a single
1260 // root which is the function's entry node. A PostDominatorTree can have
1261 // multiple roots - one for each node with no successors and for infinite
1262 // loops.
1263 // Running time: O(N).
1264 bool verifyRoots(const DomTreeT &DT) {
1265 if (!DT.Parent && !DT.Roots.empty()) {
1266 errs() << "Tree has no parent but has roots!\n";
1267 errs().flush();
1268 return false;
1271 if (!IsPostDom) {
1272 if (DT.Roots.empty()) {
1273 errs() << "Tree doesn't have a root!\n";
1274 errs().flush();
1275 return false;
1278 if (DT.getRoot() != GetEntryNode(DT)) {
1279 errs() << "Tree's root is not its parent's entry node!\n";
1280 errs().flush();
1281 return false;
1285 RootsT ComputedRoots = FindRoots(DT, nullptr);
1286 if (!isPermutation(DT.Roots, ComputedRoots)) {
1287 errs() << "Tree has different roots than freshly computed ones!\n";
1288 errs() << "\tPDT roots: ";
1289 for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1290 errs() << "\n\tComputed roots: ";
1291 for (const NodePtr N : ComputedRoots)
1292 errs() << BlockNamePrinter(N) << ", ";
1293 errs() << "\n";
1294 errs().flush();
1295 return false;
1298 return true;
1301 // Checks if the tree contains all reachable nodes in the input graph.
1302 // Running time: O(N).
1303 bool verifyReachability(const DomTreeT &DT) {
1304 clear();
1305 doFullDFSWalk(DT, AlwaysDescend);
1307 for (auto &NodeToTN : DT.DomTreeNodes) {
1308 const TreeNodePtr TN = NodeToTN.second.get();
1309 const NodePtr BB = TN->getBlock();
1311 // Virtual root has a corresponding virtual CFG node.
1312 if (DT.isVirtualRoot(TN)) continue;
1314 if (NodeToInfo.count(BB) == 0) {
1315 errs() << "DomTree node " << BlockNamePrinter(BB)
1316 << " not found by DFS walk!\n";
1317 errs().flush();
1319 return false;
1323 for (const NodePtr N : NumToNode) {
1324 if (N && !DT.getNode(N)) {
1325 errs() << "CFG node " << BlockNamePrinter(N)
1326 << " not found in the DomTree!\n";
1327 errs().flush();
1329 return false;
1333 return true;
1336 // Check if for every parent with a level L in the tree all of its children
1337 // have level L + 1.
1338 // Running time: O(N).
1339 static bool VerifyLevels(const DomTreeT &DT) {
1340 for (auto &NodeToTN : DT.DomTreeNodes) {
1341 const TreeNodePtr TN = NodeToTN.second.get();
1342 const NodePtr BB = TN->getBlock();
1343 if (!BB) continue;
1345 const TreeNodePtr IDom = TN->getIDom();
1346 if (!IDom && TN->getLevel() != 0) {
1347 errs() << "Node without an IDom " << BlockNamePrinter(BB)
1348 << " has a nonzero level " << TN->getLevel() << "!\n";
1349 errs().flush();
1351 return false;
1354 if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1355 errs() << "Node " << BlockNamePrinter(BB) << " has level "
1356 << TN->getLevel() << " while its IDom "
1357 << BlockNamePrinter(IDom->getBlock()) << " has level "
1358 << IDom->getLevel() << "!\n";
1359 errs().flush();
1361 return false;
1365 return true;
1368 // Check if the computed DFS numbers are correct. Note that DFS info may not
1369 // be valid, and when that is the case, we don't verify the numbers.
1370 // Running time: O(N log(N)).
1371 static bool VerifyDFSNumbers(const DomTreeT &DT) {
1372 if (!DT.DFSInfoValid || !DT.Parent)
1373 return true;
1375 const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
1376 const TreeNodePtr Root = DT.getNode(RootBB);
1378 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1379 errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1380 << TN->getDFSNumOut() << '}';
1383 // Verify the root's DFS In number. Although DFS numbering would also work
1384 // if we started from some other value, we assume 0-based numbering.
1385 if (Root->getDFSNumIn() != 0) {
1386 errs() << "DFSIn number for the tree root is not:\n\t";
1387 PrintNodeAndDFSNums(Root);
1388 errs() << '\n';
1389 errs().flush();
1390 return false;
1393 // For each tree node verify if children's DFS numbers cover their parent's
1394 // DFS numbers with no gaps.
1395 for (const auto &NodeToTN : DT.DomTreeNodes) {
1396 const TreeNodePtr Node = NodeToTN.second.get();
1398 // Handle tree leaves.
1399 if (Node->getChildren().empty()) {
1400 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1401 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1402 PrintNodeAndDFSNums(Node);
1403 errs() << '\n';
1404 errs().flush();
1405 return false;
1408 continue;
1411 // Make a copy and sort it such that it is possible to check if there are
1412 // no gaps between DFS numbers of adjacent children.
1413 SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1414 llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1415 return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1418 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1419 const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1420 assert(FirstCh);
1422 errs() << "Incorrect DFS numbers for:\n\tParent ";
1423 PrintNodeAndDFSNums(Node);
1425 errs() << "\n\tChild ";
1426 PrintNodeAndDFSNums(FirstCh);
1428 if (SecondCh) {
1429 errs() << "\n\tSecond child ";
1430 PrintNodeAndDFSNums(SecondCh);
1433 errs() << "\nAll children: ";
1434 for (const TreeNodePtr Ch : Children) {
1435 PrintNodeAndDFSNums(Ch);
1436 errs() << ", ";
1439 errs() << '\n';
1440 errs().flush();
1443 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1444 PrintChildrenError(Children.front(), nullptr);
1445 return false;
1448 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1449 PrintChildrenError(Children.back(), nullptr);
1450 return false;
1453 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1454 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1455 PrintChildrenError(Children[i], Children[i + 1]);
1456 return false;
1461 return true;
1464 // The below routines verify the correctness of the dominator tree relative to
1465 // the CFG it's coming from. A tree is a dominator tree iff it has two
1466 // properties, called the parent property and the sibling property. Tarjan
1467 // and Lengauer prove (but don't explicitly name) the properties as part of
1468 // the proofs in their 1972 paper, but the proofs are mostly part of proving
1469 // things about semidominators and idoms, and some of them are simply asserted
1470 // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1471 // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1472 // directed bipolar orders, and independent spanning trees" by Loukas
1473 // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1474 // and Vertex-Disjoint Paths " by the same authors.
1476 // A very simple and direct explanation of these properties can be found in
1477 // "An Experimental Study of Dynamic Dominators", found at
1478 // https://arxiv.org/abs/1604.02711
1480 // The easiest way to think of the parent property is that it's a requirement
1481 // of being a dominator. Let's just take immediate dominators. For PARENT to
1482 // be an immediate dominator of CHILD, all paths in the CFG must go through
1483 // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1484 // out of the CFG, there should be no paths to CHILD that are reachable. If
1485 // there are, then you now have a path from PARENT to CHILD that goes around
1486 // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1487 // a dominator of CHILD (let alone an immediate one).
1489 // The sibling property is similar. It says that for each pair of sibling
1490 // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1491 // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1492 // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1493 // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1494 // RIGHT, not a sibling.
1496 // It is possible to verify the parent and sibling properties in
1497 // linear time, but the algorithms are complex. Instead, we do it in a
1498 // straightforward N^2 and N^3 way below, using direct path reachability.
1500 // Checks if the tree has the parent property: if for all edges from V to W in
1501 // the input graph, such that V is reachable, the parent of W in the tree is
1502 // an ancestor of V in the tree.
1503 // Running time: O(N^2).
1505 // This means that if a node gets disconnected from the graph, then all of
1506 // the nodes it dominated previously will now become unreachable.
1507 bool verifyParentProperty(const DomTreeT &DT) {
1508 for (auto &NodeToTN : DT.DomTreeNodes) {
1509 const TreeNodePtr TN = NodeToTN.second.get();
1510 const NodePtr BB = TN->getBlock();
1511 if (!BB || TN->getChildren().empty()) continue;
1513 LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1514 << BlockNamePrinter(TN) << "\n");
1515 clear();
1516 doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1517 return From != BB && To != BB;
1520 for (TreeNodePtr Child : TN->getChildren())
1521 if (NodeToInfo.count(Child->getBlock()) != 0) {
1522 errs() << "Child " << BlockNamePrinter(Child)
1523 << " reachable after its parent " << BlockNamePrinter(BB)
1524 << " is removed!\n";
1525 errs().flush();
1527 return false;
1531 return true;
1534 // Check if the tree has sibling property: if a node V does not dominate a
1535 // node W for all siblings V and W in the tree.
1536 // Running time: O(N^3).
1538 // This means that if a node gets disconnected from the graph, then all of its
1539 // siblings will now still be reachable.
1540 bool verifySiblingProperty(const DomTreeT &DT) {
1541 for (auto &NodeToTN : DT.DomTreeNodes) {
1542 const TreeNodePtr TN = NodeToTN.second.get();
1543 const NodePtr BB = TN->getBlock();
1544 if (!BB || TN->getChildren().empty()) continue;
1546 const auto &Siblings = TN->getChildren();
1547 for (const TreeNodePtr N : Siblings) {
1548 clear();
1549 NodePtr BBN = N->getBlock();
1550 doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1551 return From != BBN && To != BBN;
1554 for (const TreeNodePtr S : Siblings) {
1555 if (S == N) continue;
1557 if (NodeToInfo.count(S->getBlock()) == 0) {
1558 errs() << "Node " << BlockNamePrinter(S)
1559 << " not reachable when its sibling " << BlockNamePrinter(N)
1560 << " is removed!\n";
1561 errs().flush();
1563 return false;
1569 return true;
1572 // Check if the given tree is the same as a freshly computed one for the same
1573 // Parent.
1574 // Running time: O(N^2), but faster in practise (same as tree construction).
1576 // Note that this does not check if that the tree construction algorithm is
1577 // correct and should be only used for fast (but possibly unsound)
1578 // verification.
1579 static bool IsSameAsFreshTree(const DomTreeT &DT) {
1580 DomTreeT FreshTree;
1581 FreshTree.recalculate(*DT.Parent);
1582 const bool Different = DT.compare(FreshTree);
1584 if (Different) {
1585 errs() << (DT.isPostDominator() ? "Post" : "")
1586 << "DominatorTree is different than a freshly computed one!\n"
1587 << "\tCurrent:\n";
1588 DT.print(errs());
1589 errs() << "\n\tFreshly computed tree:\n";
1590 FreshTree.print(errs());
1591 errs().flush();
1594 return !Different;
1598 template <class DomTreeT>
1599 void Calculate(DomTreeT &DT) {
1600 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
1603 template <typename DomTreeT>
1604 void CalculateWithUpdates(DomTreeT &DT,
1605 ArrayRef<typename DomTreeT::UpdateType> Updates) {
1606 // TODO: Move BUI creation in common method, reuse in ApplyUpdates.
1607 typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI;
1608 LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1609 cfg::LegalizeUpdates<typename DomTreeT::NodePtr>(Updates, BUI.Updates,
1610 DomTreeT::IsPostDominator);
1611 const size_t NumLegalized = BUI.Updates.size();
1612 BUI.FutureSuccessors.reserve(NumLegalized);
1613 BUI.FuturePredecessors.reserve(NumLegalized);
1614 for (auto &U : BUI.Updates) {
1615 BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1616 BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1619 SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI);
1622 template <class DomTreeT>
1623 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1624 typename DomTreeT::NodePtr To) {
1625 if (DT.isPostDominator()) std::swap(From, To);
1626 SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1629 template <class DomTreeT>
1630 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1631 typename DomTreeT::NodePtr To) {
1632 if (DT.isPostDominator()) std::swap(From, To);
1633 SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1636 template <class DomTreeT>
1637 void ApplyUpdates(DomTreeT &DT,
1638 ArrayRef<typename DomTreeT::UpdateType> Updates) {
1639 SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
1642 template <class DomTreeT>
1643 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1644 SemiNCAInfo<DomTreeT> SNCA(nullptr);
1646 // Simplist check is to compare against a new tree. This will also
1647 // usefully print the old and new trees, if they are different.
1648 if (!SNCA.IsSameAsFreshTree(DT))
1649 return false;
1651 // Common checks to verify the properties of the tree. O(N log N) at worst
1652 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1653 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1654 return false;
1656 // Extra checks depending on VerificationLevel. Up to O(N^3)
1657 if (VL == DomTreeT::VerificationLevel::Basic ||
1658 VL == DomTreeT::VerificationLevel::Full)
1659 if (!SNCA.verifyParentProperty(DT))
1660 return false;
1661 if (VL == DomTreeT::VerificationLevel::Full)
1662 if (!SNCA.verifySiblingProperty(DT))
1663 return false;
1665 return true;
1668 } // namespace DomTreeBuilder
1669 } // namespace llvm
1671 #undef DEBUG_TYPE
1673 #endif