LLVM 17.0.0git
GenericDomTreeConstruction.h
Go to the documentation of this file.
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/// [1] 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/// that uses SLT to perform full constructions and SemiNCA for incremental
25/// updates.
26///
27/// The file uses the Depth Based Search algorithm to perform incremental
28/// updates (insertion and deletions). The implemented algorithm is based on
29/// this publication:
30///
31/// [2] An Experimental Study of Dynamic Dominators
32/// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
33/// https://arxiv.org/pdf/1604.02711.pdf
34///
35//===----------------------------------------------------------------------===//
36
37#ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
38#define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
39
40#include "llvm/ADT/ArrayRef.h"
41#include "llvm/ADT/DenseSet.h"
45#include "llvm/Support/Debug.h"
47#include <optional>
48#include <queue>
49
50#define DEBUG_TYPE "dom-tree-builder"
51
52namespace llvm {
53namespace DomTreeBuilder {
54
55template <typename DomTreeT>
57 using NodePtr = typename DomTreeT::NodePtr;
58 using NodeT = typename DomTreeT::NodeType;
60 using RootsT = decltype(DomTreeT::Roots);
61 static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
63
64 // Information record used by Semi-NCA during tree construction.
65 struct InfoRec {
66 unsigned DFSNum = 0;
67 unsigned Parent = 0;
68 unsigned Semi = 0;
69 NodePtr Label = nullptr;
70 NodePtr IDom = nullptr;
72 };
73
74 // Number to node mapping is 1-based. Initialize the mapping to start with
75 // a dummy element.
76 std::vector<NodePtr> NumToNode = {nullptr};
78
79 using UpdateT = typename DomTreeT::UpdateType;
80 using UpdateKind = typename DomTreeT::UpdateKind;
82 // Note: Updates inside PreViewCFG are already legalized.
85 NumLegalized(PreViewCFG.getNumLegalizedUpdates()) {}
86
87 // Remembers if the whole tree was recalculated at some point during the
88 // current batch update.
89 bool IsRecalculated = false;
92 const size_t NumLegalized;
93 };
94
97
98 // If BUI is a nullptr, then there's no batch update in progress.
100
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.
106 }
107
108 template <bool Inversed>
110 if (BUI)
111 return BUI->PreViewCFG.template getChildren<Inversed>(N);
112 return getChildren<Inversed>(N);
113 }
114
115 template <bool Inversed>
117 using DirectedNodeT =
118 std::conditional_t<Inversed, Inverse<NodePtr>, NodePtr>;
119 auto R = children<DirectedNodeT>(N);
120 SmallVector<NodePtr, 8> Res(detail::reverse_if<!Inversed>(R));
121
122 // Remove nullptr children for clang.
123 llvm::erase_value(Res, nullptr);
124 return Res;
125 }
126
128 auto InfoIt = NodeToInfo.find(BB);
129 if (InfoIt == NodeToInfo.end()) return nullptr;
130
131 return InfoIt->second.IDom;
132 }
133
135 if (TreeNodePtr Node = DT.getNode(BB)) return Node;
136
137 // Haven't calculated this node yet? Get or calculate the node for the
138 // immediate dominator.
139 NodePtr IDom = getIDom(BB);
140
141 assert(IDom || DT.DomTreeNodes[nullptr]);
142 TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
143
144 // Add a new tree node for this NodeT, and link it as a child of
145 // IDomNode
146 return DT.createChild(BB, IDomNode);
147 }
148
149 static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
150
153
155 BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
156
158 if (!BP.N)
159 O << "nullptr";
160 else
161 BP.N->printAsOperand(O, false);
162
163 return O;
164 }
165 };
166
168
169 // Custom DFS implementation which can skip nodes based on a provided
170 // predicate. It also collects ReverseChildren so that we don't have to spend
171 // time getting predecessors in SemiNCA.
172 //
173 // If IsReverse is set to true, the DFS walk will be performed backwards
174 // relative to IsPostDom -- using reverse edges for dominators and forward
175 // edges for postdominators.
176 //
177 // If SuccOrder is specified then in this order the DFS traverses the children
178 // otherwise the order is implied by the results of getChildren().
179 template <bool IsReverse = false, typename DescendCondition>
180 unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
181 unsigned AttachToNum,
182 const NodeOrderMap *SuccOrder = nullptr) {
183 assert(V);
184 SmallVector<NodePtr, 64> WorkList = {V};
185 if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
186
187 while (!WorkList.empty()) {
188 const NodePtr BB = WorkList.pop_back_val();
189 auto &BBInfo = NodeToInfo[BB];
190
191 // Visited nodes always have positive DFS numbers.
192 if (BBInfo.DFSNum != 0) continue;
193 BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
194 BBInfo.Label = BB;
195 NumToNode.push_back(BB);
196
197 constexpr bool Direction = IsReverse != IsPostDom; // XOR.
198 auto Successors = getChildren<Direction>(BB, BatchUpdates);
199 if (SuccOrder && Successors.size() > 1)
201 Successors.begin(), Successors.end(), [=](NodePtr A, NodePtr B) {
202 return SuccOrder->find(A)->second < SuccOrder->find(B)->second;
203 });
204
205 for (const NodePtr Succ : Successors) {
206 const auto SIT = NodeToInfo.find(Succ);
207 // Don't visit nodes more than once but remember to collect
208 // ReverseChildren.
209 if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
210 if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
211 continue;
212 }
213
214 if (!Condition(BB, Succ)) continue;
215
216 // It's fine to add Succ to the map, because we know that it will be
217 // visited later.
218 auto &SuccInfo = NodeToInfo[Succ];
219 WorkList.push_back(Succ);
220 SuccInfo.Parent = LastNum;
221 SuccInfo.ReverseChildren.push_back(BB);
222 }
223 }
224
225 return LastNum;
226 }
227
228 // V is a predecessor of W. eval() returns V if V < W, otherwise the minimum
229 // of sdom(U), where U > W and there is a virtual forest path from U to V. The
230 // virtual forest consists of linked edges of processed vertices.
231 //
232 // We can follow Parent pointers (virtual forest edges) to determine the
233 // ancestor U with minimum sdom(U). But it is slow and thus we employ the path
234 // compression technique to speed up to O(m*log(n)). Theoretically the virtual
235 // forest can be organized as balanced trees to achieve almost linear
236 // O(m*alpha(m,n)) running time. But it requires two auxiliary arrays (Size
237 // and Child) and is unlikely to be faster than the simple implementation.
238 //
239 // For each vertex V, its Label points to the vertex with the minimal sdom(U)
240 // (Semi) in its path from V (included) to NodeToInfo[V].Parent (excluded).
241 NodePtr eval(NodePtr V, unsigned LastLinked,
243 InfoRec *VInfo = &NodeToInfo[V];
244 if (VInfo->Parent < LastLinked)
245 return VInfo->Label;
246
247 // Store ancestors except the last (root of a virtual tree) into a stack.
248 assert(Stack.empty());
249 do {
250 Stack.push_back(VInfo);
251 VInfo = &NodeToInfo[NumToNode[VInfo->Parent]];
252 } while (VInfo->Parent >= LastLinked);
253
254 // Path compression. Point each vertex's Parent to the root and update its
255 // Label if any of its ancestors (PInfo->Label) has a smaller Semi.
256 const InfoRec *PInfo = VInfo;
257 const InfoRec *PLabelInfo = &NodeToInfo[PInfo->Label];
258 do {
259 VInfo = Stack.pop_back_val();
260 VInfo->Parent = PInfo->Parent;
261 const InfoRec *VLabelInfo = &NodeToInfo[VInfo->Label];
262 if (PLabelInfo->Semi < VLabelInfo->Semi)
263 VInfo->Label = PInfo->Label;
264 else
265 PLabelInfo = VLabelInfo;
266 PInfo = VInfo;
267 } while (!Stack.empty());
268 return VInfo->Label;
269 }
270
271 // This function requires DFS to be run before calling it.
272 void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
273 const unsigned NextDFSNum(NumToNode.size());
274 // Initialize IDoms to spanning tree parents.
275 for (unsigned i = 1; i < NextDFSNum; ++i) {
276 const NodePtr V = NumToNode[i];
277 auto &VInfo = NodeToInfo[V];
278 VInfo.IDom = NumToNode[VInfo.Parent];
279 }
280
281 // Step #1: Calculate the semidominators of all vertices.
283 for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
284 NodePtr W = NumToNode[i];
285 auto &WInfo = NodeToInfo[W];
286
287 // Initialize the semi dominator to point to the parent node.
288 WInfo.Semi = WInfo.Parent;
289 for (const auto &N : WInfo.ReverseChildren) {
290 if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
291 continue;
292
293 const TreeNodePtr TN = DT.getNode(N);
294 // Skip predecessors whose level is above the subtree we are processing.
295 if (TN && TN->getLevel() < MinLevel)
296 continue;
297
298 unsigned SemiU = NodeToInfo[eval(N, i + 1, EvalStack)].Semi;
299 if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
300 }
301 }
302
303 // Step #2: Explicitly define the immediate dominator of each vertex.
304 // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
305 // Note that the parents were stored in IDoms and later got invalidated
306 // during path compression in Eval.
307 for (unsigned i = 2; i < NextDFSNum; ++i) {
308 const NodePtr W = NumToNode[i];
309 auto &WInfo = NodeToInfo[W];
310 const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
311 NodePtr WIDomCandidate = WInfo.IDom;
312 while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
313 WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
314
315 WInfo.IDom = WIDomCandidate;
316 }
317 }
318
319 // PostDominatorTree always has a virtual root that represents a virtual CFG
320 // node that serves as a single exit from the function. All the other exits
321 // (CFG nodes with terminators and nodes in infinite loops are logically
322 // connected to this virtual CFG exit node).
323 // This functions maps a nullptr CFG node to the virtual root tree node.
325 assert(IsPostDom && "Only postdominators have a virtual root");
326 assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
327
328 auto &BBInfo = NodeToInfo[nullptr];
329 BBInfo.DFSNum = BBInfo.Semi = 1;
330 BBInfo.Label = nullptr;
331
332 NumToNode.push_back(nullptr); // NumToNode[1] = nullptr;
333 }
334
335 // For postdominators, nodes with no forward successors are trivial roots that
336 // are always selected as tree roots. Roots with forward successors correspond
337 // to CFG nodes within infinite loops.
339 assert(N && "N must be a valid node");
340 return !getChildren<false>(N, BUI).empty();
341 }
342
343 static NodePtr GetEntryNode(const DomTreeT &DT) {
344 assert(DT.Parent && "Parent not set");
346 }
347
348 // Finds all roots without relaying on the set of roots already stored in the
349 // tree.
350 // We define roots to be some non-redundant set of the CFG nodes
351 static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
352 assert(DT.Parent && "Parent pointer is not set");
353 RootsT Roots;
354
355 // For dominators, function entry CFG node is always a tree root node.
356 if (!IsPostDom) {
357 Roots.push_back(GetEntryNode(DT));
358 return Roots;
359 }
360
361 SemiNCAInfo SNCA(BUI);
362
363 // PostDominatorTree always has a virtual root.
364 SNCA.addVirtualRoot();
365 unsigned Num = 1;
366
367 LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
368
369 // Step #1: Find all the trivial roots that are going to will definitely
370 // remain tree roots.
371 unsigned Total = 0;
372 // It may happen that there are some new nodes in the CFG that are result of
373 // the ongoing batch update, but we cannot really pretend that they don't
374 // exist -- we won't see any outgoing or incoming edges to them, so it's
375 // fine to discover them here, as they would end up appearing in the CFG at
376 // some point anyway.
377 for (const NodePtr N : nodes(DT.Parent)) {
378 ++Total;
379 // If it has no *successors*, it is definitely a root.
380 if (!HasForwardSuccessors(N, BUI)) {
381 Roots.push_back(N);
382 // Run DFS not to walk this part of CFG later.
383 Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
384 LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
385 << "\n");
386 LLVM_DEBUG(dbgs() << "Last visited node: "
387 << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
388 }
389 }
390
391 LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
392
393 // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
394 // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
395 // nodes in infinite loops).
396 bool HasNonTrivialRoots = false;
397 // Accounting for the virtual exit, see if we had any reverse-unreachable
398 // nodes.
399 if (Total + 1 != Num) {
400 HasNonTrivialRoots = true;
401
402 // SuccOrder is the order of blocks in the function. It is needed to make
403 // the calculation of the FurthestAway node and the whole PostDomTree
404 // immune to swap successors transformation (e.g. canonicalizing branch
405 // predicates). SuccOrder is initialized lazily only for successors of
406 // reverse unreachable nodes.
407 std::optional<NodeOrderMap> SuccOrder;
408 auto InitSuccOrderOnce = [&]() {
409 SuccOrder = NodeOrderMap();
410 for (const auto Node : nodes(DT.Parent))
411 if (SNCA.NodeToInfo.count(Node) == 0)
412 for (const auto Succ : getChildren<false>(Node, SNCA.BatchUpdates))
413 SuccOrder->try_emplace(Succ, 0);
414
415 // Add mapping for all entries of SuccOrder.
416 unsigned NodeNum = 0;
417 for (const auto Node : nodes(DT.Parent)) {
418 ++NodeNum;
419 auto Order = SuccOrder->find(Node);
420 if (Order != SuccOrder->end()) {
421 assert(Order->second == 0);
422 Order->second = NodeNum;
423 }
424 }
425 };
426
427 // Make another DFS pass over all other nodes to find the
428 // reverse-unreachable blocks, and find the furthest paths we'll be able
429 // to make.
430 // Note that this looks N^2, but it's really 2N worst case, if every node
431 // is unreachable. This is because we are still going to only visit each
432 // unreachable node once, we may just visit it in two directions,
433 // depending on how lucky we get.
434 for (const NodePtr I : nodes(DT.Parent)) {
435 if (SNCA.NodeToInfo.count(I) == 0) {
437 << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
438 // Find the furthest away we can get by following successors, then
439 // follow them in reverse. This gives us some reasonable answer about
440 // the post-dom tree inside any infinite loop. In particular, it
441 // guarantees we get to the farthest away point along *some*
442 // path. This also matches the GCC's behavior.
443 // If we really wanted a totally complete picture of dominance inside
444 // this infinite loop, we could do it with SCC-like algorithms to find
445 // the lowest and highest points in the infinite loop. In theory, it
446 // would be nice to give the canonical backedge for the loop, but it's
447 // expensive and does not always lead to a minimal set of roots.
448 LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
449
450 if (!SuccOrder)
451 InitSuccOrderOnce();
452 assert(SuccOrder);
453
454 const unsigned NewNum =
455 SNCA.runDFS<true>(I, Num, AlwaysDescend, Num, &*SuccOrder);
456 const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
457 LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
458 << "(non-trivial root): "
459 << BlockNamePrinter(FurthestAway) << "\n");
460 Roots.push_back(FurthestAway);
461 LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
462 << NewNum << "\n\t\t\tRemoving DFS info\n");
463 for (unsigned i = NewNum; i > Num; --i) {
464 const NodePtr N = SNCA.NumToNode[i];
465 LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
466 << BlockNamePrinter(N) << "\n");
467 SNCA.NodeToInfo.erase(N);
468 SNCA.NumToNode.pop_back();
469 }
470 const unsigned PrevNum = Num;
471 LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
472 Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
473 for (unsigned i = PrevNum + 1; i <= Num; ++i)
474 LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
475 << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
476 }
477 }
478 }
479
480 LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
481 LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
482 LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
483 << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
484
485 assert((Total + 1 == Num) && "Everything should have been visited");
486
487 // Step #3: If we found some non-trivial roots, make them non-redundant.
488 if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
489
490 LLVM_DEBUG(dbgs() << "Found roots: ");
491 LLVM_DEBUG(for (auto *Root
492 : Roots) dbgs()
493 << BlockNamePrinter(Root) << " ");
494 LLVM_DEBUG(dbgs() << "\n");
495
496 return Roots;
497 }
498
499 // This function only makes sense for postdominators.
500 // We define roots to be some set of CFG nodes where (reverse) DFS walks have
501 // to start in order to visit all the CFG nodes (including the
502 // reverse-unreachable ones).
503 // When the search for non-trivial roots is done it may happen that some of
504 // the non-trivial roots are reverse-reachable from other non-trivial roots,
505 // which makes them redundant. This function removes them from the set of
506 // input roots.
507 static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
508 RootsT &Roots) {
509 assert(IsPostDom && "This function is for postdominators only");
510 LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
511
512 SemiNCAInfo SNCA(BUI);
513
514 for (unsigned i = 0; i < Roots.size(); ++i) {
515 auto &Root = Roots[i];
516 // Trivial roots are always non-redundant.
517 if (!HasForwardSuccessors(Root, BUI)) continue;
518 LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
519 << " remains a root\n");
520 SNCA.clear();
521 // Do a forward walk looking for the other roots.
522 const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
523 // Skip the start node and begin from the second one (note that DFS uses
524 // 1-based indexing).
525 for (unsigned x = 2; x <= Num; ++x) {
526 const NodePtr N = SNCA.NumToNode[x];
527 // If we wound another root in a (forward) DFS walk, remove the current
528 // root from the set of roots, as it is reverse-reachable from the other
529 // one.
530 if (llvm::is_contained(Roots, N)) {
531 LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
532 << BlockNamePrinter(N) << "\n\tRemoving root "
533 << BlockNamePrinter(Root) << "\n");
534 std::swap(Root, Roots.back());
535 Roots.pop_back();
536
537 // Root at the back takes the current root's place.
538 // Start the next loop iteration with the same index.
539 --i;
540 break;
541 }
542 }
543 }
544 }
545
546 template <typename DescendCondition>
547 void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
548 if (!IsPostDom) {
549 assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
550 runDFS(DT.Roots[0], 0, DC, 0);
551 return;
552 }
553
555 unsigned Num = 1;
556 for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
557 }
558
559 static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
560 auto *Parent = DT.Parent;
561 DT.reset();
562 DT.Parent = Parent;
563 // If the update is using the actual CFG, BUI is null. If it's using a view,
564 // BUI is non-null and the PreCFGView is used. When calculating from
565 // scratch, make the PreViewCFG equal to the PostCFGView, so Post is used.
566 BatchUpdatePtr PostViewBUI = nullptr;
567 if (BUI && BUI->PostViewCFG) {
568 BUI->PreViewCFG = *BUI->PostViewCFG;
569 PostViewBUI = BUI;
570 }
571 // This is rebuilding the whole tree, not incrementally, but PostViewBUI is
572 // used in case the caller needs a DT update with a CFGView.
573 SemiNCAInfo SNCA(PostViewBUI);
574
575 // Step #0: Number blocks in depth-first order and initialize variables used
576 // in later stages of the algorithm.
577 DT.Roots = FindRoots(DT, PostViewBUI);
579
580 SNCA.runSemiNCA(DT);
581 if (BUI) {
582 BUI->IsRecalculated = true;
584 dbgs() << "DomTree recalculated, skipping future batch updates\n");
585 }
586
587 if (DT.Roots.empty()) return;
588
589 // Add a node for the root. If the tree is a PostDominatorTree it will be
590 // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
591 // all real exits (including multiple exit blocks, infinite loops).
592 NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
593
594 DT.RootNode = DT.createNode(Root);
595 SNCA.attachNewSubtree(DT, DT.RootNode);
596 }
597
598 void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
599 // Attach the first unreachable block to AttachTo.
600 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
601 // Loop over all of the discovered blocks in the function...
602 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
603 NodePtr W = NumToNode[i];
604
605 // Don't replace this with 'count', the insertion side effect is important
606 if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
607
608 NodePtr ImmDom = getIDom(W);
609
610 // Get or calculate the node for the immediate dominator.
611 TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
612
613 // Add a new tree node for this BasicBlock, and link it as a child of
614 // IDomNode.
615 DT.createChild(W, IDomNode);
616 }
617 }
618
619 void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
620 NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
621 for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
622 const NodePtr N = NumToNode[i];
623 const TreeNodePtr TN = DT.getNode(N);
624 assert(TN);
625 const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
626 TN->setIDom(NewIDom);
627 }
628 }
629
630 // Helper struct used during edge insertions.
632 struct Compare {
634 return LHS->getLevel() < RHS->getLevel();
635 }
636 };
637
638 // Bucket queue of tree nodes ordered by descending level. For simplicity,
639 // we use a priority_queue here.
640 std::priority_queue<TreeNodePtr, SmallVector<TreeNodePtr, 8>,
641 Compare>
645#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
646 SmallVector<TreeNodePtr, 8> VisitedUnaffected;
647#endif
648 };
649
650 static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
651 const NodePtr From, const NodePtr To) {
652 assert((From || IsPostDom) &&
653 "From has to be a valid CFG node or a virtual root");
654 assert(To && "Cannot be a nullptr");
655 LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
656 << BlockNamePrinter(To) << "\n");
657 TreeNodePtr FromTN = DT.getNode(From);
658
659 if (!FromTN) {
660 // Ignore edges from unreachable nodes for (forward) dominators.
661 if (!IsPostDom) return;
662
663 // The unreachable node becomes a new root -- a tree node for it.
664 TreeNodePtr VirtualRoot = DT.getNode(nullptr);
665 FromTN = DT.createChild(From, VirtualRoot);
666 DT.Roots.push_back(From);
667 }
668
669 DT.DFSInfoValid = false;
670
671 const TreeNodePtr ToTN = DT.getNode(To);
672 if (!ToTN)
673 InsertUnreachable(DT, BUI, FromTN, To);
674 else
675 InsertReachable(DT, BUI, FromTN, ToTN);
676 }
677
678 // Determines if some existing root becomes reverse-reachable after the
679 // insertion. Rebuilds the whole tree if that situation happens.
680 static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
681 const TreeNodePtr From,
682 const TreeNodePtr To) {
683 assert(IsPostDom && "This function is only for postdominators");
684 // Destination node is not attached to the virtual root, so it cannot be a
685 // root.
686 if (!DT.isVirtualRoot(To->getIDom())) return false;
687
688 if (!llvm::is_contained(DT.Roots, To->getBlock()))
689 return false; // To is not a root, nothing to update.
690
691 LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
692 << " is no longer a root\n\t\tRebuilding the tree!!!\n");
693
694 CalculateFromScratch(DT, BUI);
695 return true;
696 }
697
700 if (A.size() != B.size())
701 return false;
702 SmallPtrSet<NodePtr, 4> Set(A.begin(), A.end());
703 for (NodePtr N : B)
704 if (Set.count(N) == 0)
705 return false;
706 return true;
707 }
708
709 // Updates the set of roots after insertion or deletion. This ensures that
710 // roots are the same when after a series of updates and when the tree would
711 // be built from scratch.
712 static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
713 assert(IsPostDom && "This function is only for postdominators");
714
715 // The tree has only trivial roots -- nothing to update.
716 if (llvm::none_of(DT.Roots, [BUI](const NodePtr N) {
717 return HasForwardSuccessors(N, BUI);
718 }))
719 return;
720
721 // Recalculate the set of roots.
722 RootsT Roots = FindRoots(DT, BUI);
723 if (!isPermutation(DT.Roots, Roots)) {
724 // The roots chosen in the CFG have changed. This is because the
725 // incremental algorithm does not really know or use the set of roots and
726 // can make a different (implicit) decision about which node within an
727 // infinite loop becomes a root.
728
729 LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
730 << "The entire tree needs to be rebuilt\n");
731 // It may be possible to update the tree without recalculating it, but
732 // we do not know yet how to do it, and it happens rarely in practice.
733 CalculateFromScratch(DT, BUI);
734 }
735 }
736
737 // Handles insertion to a node already in the dominator tree.
738 static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
739 const TreeNodePtr From, const TreeNodePtr To) {
740 LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
741 << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
742 if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
743 // DT.findNCD expects both pointers to be valid. When From is a virtual
744 // root, then its CFG block pointer is a nullptr, so we have to 'compute'
745 // the NCD manually.
746 const NodePtr NCDBlock =
747 (From->getBlock() && To->getBlock())
748 ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
749 : nullptr;
750 assert(NCDBlock || DT.isPostDominator());
751 const TreeNodePtr NCD = DT.getNode(NCDBlock);
752 assert(NCD);
753
754 LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
755 const unsigned NCDLevel = NCD->getLevel();
756
757 // Based on Lemma 2.5 from [2], after insertion of (From,To), v is affected
758 // iff depth(NCD)+1 < depth(v) && a path P from To to v exists where every
759 // w on P s.t. depth(v) <= depth(w)
760 //
761 // This reduces to a widest path problem (maximizing the depth of the
762 // minimum vertex in the path) which can be solved by a modified version of
763 // Dijkstra with a bucket queue (named depth-based search in [2]).
764
765 // To is in the path, so depth(NCD)+1 < depth(v) <= depth(To). Nothing
766 // affected if this does not hold.
767 if (NCDLevel + 1 >= To->getLevel())
768 return;
769
770 InsertionInfo II;
771 SmallVector<TreeNodePtr, 8> UnaffectedOnCurrentLevel;
772 II.Bucket.push(To);
773 II.Visited.insert(To);
774
775 while (!II.Bucket.empty()) {
776 TreeNodePtr TN = II.Bucket.top();
777 II.Bucket.pop();
778 II.Affected.push_back(TN);
779
780 const unsigned CurrentLevel = TN->getLevel();
781 LLVM_DEBUG(dbgs() << "Mark " << BlockNamePrinter(TN) <<
782 "as affected, CurrentLevel " << CurrentLevel << "\n");
783
784 assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
785
786 while (true) {
787 // Unlike regular Dijkstra, we have an inner loop to expand more
788 // vertices. The first iteration is for the (affected) vertex popped
789 // from II.Bucket and the rest are for vertices in
790 // UnaffectedOnCurrentLevel, which may eventually expand to affected
791 // vertices.
792 //
793 // Invariant: there is an optimal path from `To` to TN with the minimum
794 // depth being CurrentLevel.
795 for (const NodePtr Succ : getChildren<IsPostDom>(TN->getBlock(), BUI)) {
796 const TreeNodePtr SuccTN = DT.getNode(Succ);
797 assert(SuccTN &&
798 "Unreachable successor found at reachable insertion");
799 const unsigned SuccLevel = SuccTN->getLevel();
800
801 LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
802 << ", level = " << SuccLevel << "\n");
803
804 // There is an optimal path from `To` to Succ with the minimum depth
805 // being min(CurrentLevel, SuccLevel).
806 //
807 // If depth(NCD)+1 < depth(Succ) is not satisfied, Succ is unaffected
808 // and no affected vertex may be reached by a path passing through it.
809 // Stop here. Also, Succ may be visited by other predecessors but the
810 // first visit has the optimal path. Stop if Succ has been visited.
811 if (SuccLevel <= NCDLevel + 1 || !II.Visited.insert(SuccTN).second)
812 continue;
813
814 if (SuccLevel > CurrentLevel) {
815 // Succ is unaffected but it may (transitively) expand to affected
816 // vertices. Store it in UnaffectedOnCurrentLevel.
817 LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
818 << BlockNamePrinter(Succ) << "\n");
819 UnaffectedOnCurrentLevel.push_back(SuccTN);
820#ifndef NDEBUG
821 II.VisitedUnaffected.push_back(SuccTN);
822#endif
823 } else {
824 // The condition is satisfied (Succ is affected). Add Succ to the
825 // bucket queue.
826 LLVM_DEBUG(dbgs() << "\t\tAdd " << BlockNamePrinter(Succ)
827 << " to a Bucket\n");
828 II.Bucket.push(SuccTN);
829 }
830 }
831
832 if (UnaffectedOnCurrentLevel.empty())
833 break;
834 TN = UnaffectedOnCurrentLevel.pop_back_val();
835 LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(TN) << "\n");
836 }
837 }
838
839 // Finish by updating immediate dominators and levels.
840 UpdateInsertion(DT, BUI, NCD, II);
841 }
842
843 // Updates immediate dominators and levels after insertion.
844 static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
845 const TreeNodePtr NCD, InsertionInfo &II) {
846 LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
847
848 for (const TreeNodePtr TN : II.Affected) {
849 LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
850 << ") = " << BlockNamePrinter(NCD) << "\n");
851 TN->setIDom(NCD);
852 }
853
854#if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)
855 for (const TreeNodePtr TN : II.VisitedUnaffected)
856 assert(TN->getLevel() == TN->getIDom()->getLevel() + 1 &&
857 "TN should have been updated by an affected ancestor");
858#endif
859
860 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
861 }
862
863 // Handles insertion to previously unreachable nodes.
864 static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
865 const TreeNodePtr From, const NodePtr To) {
866 LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
867 << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
868
869 // Collect discovered edges to already reachable nodes.
870 SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
871 // Discover and connect nodes that became reachable with the insertion.
872 ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
873
874 LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
875 << " -> (prev unreachable) " << BlockNamePrinter(To)
876 << "\n");
877
878 // Used the discovered edges and inset discovered connecting (incoming)
879 // edges.
880 for (const auto &Edge : DiscoveredEdgesToReachable) {
881 LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
882 << BlockNamePrinter(Edge.first) << " -> "
883 << BlockNamePrinter(Edge.second) << "\n");
884 InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
885 }
886 }
887
888 // Connects nodes that become reachable with an insertion.
890 DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
891 const TreeNodePtr Incoming,
892 SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
893 &DiscoveredConnectingEdges) {
894 assert(!DT.getNode(Root) && "Root must not be reachable");
895
896 // Visit only previously unreachable nodes.
897 auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
898 NodePtr To) {
899 const TreeNodePtr ToTN = DT.getNode(To);
900 if (!ToTN) return true;
901
902 DiscoveredConnectingEdges.push_back({From, ToTN});
903 return false;
904 };
905
906 SemiNCAInfo SNCA(BUI);
907 SNCA.runDFS(Root, 0, UnreachableDescender, 0);
908 SNCA.runSemiNCA(DT);
909 SNCA.attachNewSubtree(DT, Incoming);
910
911 LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
912 }
913
914 static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
915 const NodePtr From, const NodePtr To) {
916 assert(From && To && "Cannot disconnect nullptrs");
917 LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
918 << BlockNamePrinter(To) << "\n");
919
920#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
921 // Ensure that the edge was in fact deleted from the CFG before informing
922 // the DomTree about it.
923 // The check is O(N), so run it only in debug configuration.
924 auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
925 auto Successors = getChildren<IsPostDom>(Of, BUI);
926 return llvm::is_contained(Successors, SuccCandidate);
927 };
928 (void)IsSuccessor;
929 assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
930#endif
931
932 const TreeNodePtr FromTN = DT.getNode(From);
933 // Deletion in an unreachable subtree -- nothing to do.
934 if (!FromTN) return;
935
936 const TreeNodePtr ToTN = DT.getNode(To);
937 if (!ToTN) {
939 dbgs() << "\tTo (" << BlockNamePrinter(To)
940 << ") already unreachable -- there is no edge to delete\n");
941 return;
942 }
943
944 const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
945 const TreeNodePtr NCD = DT.getNode(NCDBlock);
946
947 // If To dominates From -- nothing to do.
948 if (ToTN != NCD) {
949 DT.DFSInfoValid = false;
950
951 const TreeNodePtr ToIDom = ToTN->getIDom();
952 LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
953 << BlockNamePrinter(ToIDom) << "\n");
954
955 // To remains reachable after deletion.
956 // (Based on the caption under Figure 4. from [2].)
957 if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
958 DeleteReachable(DT, BUI, FromTN, ToTN);
959 else
960 DeleteUnreachable(DT, BUI, ToTN);
961 }
962
963 if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
964 }
965
966 // Handles deletions that leave destination nodes reachable.
967 static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
968 const TreeNodePtr FromTN,
969 const TreeNodePtr ToTN) {
970 LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
971 << " -> " << BlockNamePrinter(ToTN) << "\n");
972 LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
973
974 // Find the top of the subtree that needs to be rebuilt.
975 // (Based on the lemma 2.6 from [2].)
976 const NodePtr ToIDom =
977 DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
978 assert(ToIDom || DT.isPostDominator());
979 const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
980 assert(ToIDomTN);
981 const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
982 // Top of the subtree to rebuild is the root node. Rebuild the tree from
983 // scratch.
984 if (!PrevIDomSubTree) {
985 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
986 CalculateFromScratch(DT, BUI);
987 return;
988 }
989
990 // Only visit nodes in the subtree starting at To.
991 const unsigned Level = ToIDomTN->getLevel();
992 auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
993 return DT.getNode(To)->getLevel() > Level;
994 };
995
996 LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
997 << "\n");
998
999 SemiNCAInfo SNCA(BUI);
1000 SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1001 LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1002 SNCA.runSemiNCA(DT, Level);
1003 SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1004 }
1005
1006 // Checks if a node has proper support, as defined on the page 3 and later
1007 // explained on the page 7 of [2].
1008 static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1009 const TreeNodePtr TN) {
1010 LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1011 << "\n");
1012 auto TNB = TN->getBlock();
1013 for (const NodePtr Pred : getChildren<!IsPostDom>(TNB, BUI)) {
1014 LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1015 if (!DT.getNode(Pred)) continue;
1016
1017 const NodePtr Support = DT.findNearestCommonDominator(TNB, Pred);
1018 LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1019 if (Support != TNB) {
1020 LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1021 << " is reachable from support "
1022 << BlockNamePrinter(Support) << "\n");
1023 return true;
1024 }
1025 }
1026
1027 return false;
1028 }
1029
1030 // Handle deletions that make destination node unreachable.
1031 // (Based on the lemma 2.7 from the [2].)
1032 static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1033 const TreeNodePtr ToTN) {
1034 LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1035 << BlockNamePrinter(ToTN) << "\n");
1036 assert(ToTN);
1037 assert(ToTN->getBlock());
1038
1039 if (IsPostDom) {
1040 // Deletion makes a region reverse-unreachable and creates a new root.
1041 // Simulate that by inserting an edge from the virtual root to ToTN and
1042 // adding it as a new root.
1043 LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1044 LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1045 << "\n");
1046 DT.Roots.push_back(ToTN->getBlock());
1047 InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1048 return;
1049 }
1050
1051 SmallVector<NodePtr, 16> AffectedQueue;
1052 const unsigned Level = ToTN->getLevel();
1053
1054 // Traverse destination node's descendants with greater level in the tree
1055 // and collect visited nodes.
1056 auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1057 const TreeNodePtr TN = DT.getNode(To);
1058 assert(TN);
1059 if (TN->getLevel() > Level) return true;
1060 if (!llvm::is_contained(AffectedQueue, To))
1061 AffectedQueue.push_back(To);
1062
1063 return false;
1064 };
1065
1066 SemiNCAInfo SNCA(BUI);
1067 unsigned LastDFSNum =
1068 SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1069
1070 TreeNodePtr MinNode = ToTN;
1071
1072 // Identify the top of the subtree to rebuild by finding the NCD of all
1073 // the affected nodes.
1074 for (const NodePtr N : AffectedQueue) {
1075 const TreeNodePtr TN = DT.getNode(N);
1076 const NodePtr NCDBlock =
1077 DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1078 assert(NCDBlock || DT.isPostDominator());
1079 const TreeNodePtr NCD = DT.getNode(NCDBlock);
1080 assert(NCD);
1081
1082 LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1083 << " with NCD = " << BlockNamePrinter(NCD)
1084 << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1085 if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1086 }
1087
1088 // Root reached, rebuild the whole tree from scratch.
1089 if (!MinNode->getIDom()) {
1090 LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1091 CalculateFromScratch(DT, BUI);
1092 return;
1093 }
1094
1095 // Erase the unreachable subtree in reverse preorder to process all children
1096 // before deleting their parent.
1097 for (unsigned i = LastDFSNum; i > 0; --i) {
1098 const NodePtr N = SNCA.NumToNode[i];
1099 const TreeNodePtr TN = DT.getNode(N);
1100 LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1101
1102 EraseNode(DT, TN);
1103 }
1104
1105 // The affected subtree start at the To node -- there's no extra work to do.
1106 if (MinNode == ToTN) return;
1107
1108 LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1109 << BlockNamePrinter(MinNode) << "\n");
1110 const unsigned MinLevel = MinNode->getLevel();
1111 const TreeNodePtr PrevIDom = MinNode->getIDom();
1112 assert(PrevIDom);
1113 SNCA.clear();
1114
1115 // Identify nodes that remain in the affected subtree.
1116 auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1117 const TreeNodePtr ToTN = DT.getNode(To);
1118 return ToTN && ToTN->getLevel() > MinLevel;
1119 };
1120 SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1121
1122 LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1123 << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1124
1125 // Rebuild the remaining part of affected subtree.
1126 SNCA.runSemiNCA(DT, MinLevel);
1127 SNCA.reattachExistingSubtree(DT, PrevIDom);
1128 }
1129
1130 // Removes leaf tree nodes from the dominator tree.
1131 static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1132 assert(TN);
1133 assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1134
1135 const TreeNodePtr IDom = TN->getIDom();
1136 assert(IDom);
1137
1138 auto ChIt = llvm::find(IDom->Children, TN);
1139 assert(ChIt != IDom->Children.end());
1140 std::swap(*ChIt, IDom->Children.back());
1141 IDom->Children.pop_back();
1142
1143 DT.DomTreeNodes.erase(TN->getBlock());
1144 }
1145
1146 //~~
1147 //===--------------------- DomTree Batch Updater --------------------------===
1148 //~~
1149
1150 static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG,
1151 GraphDiffT *PostViewCFG) {
1152 // Note: the PostViewCFG is only used when computing from scratch. It's data
1153 // should already included in the PreViewCFG for incremental updates.
1154 const size_t NumUpdates = PreViewCFG.getNumLegalizedUpdates();
1155 if (NumUpdates == 0)
1156 return;
1157
1158 // Take the fast path for a single update and avoid running the batch update
1159 // machinery.
1160 if (NumUpdates == 1) {
1161 UpdateT Update = PreViewCFG.popUpdateForIncrementalUpdates();
1162 if (!PostViewCFG) {
1163 if (Update.getKind() == UpdateKind::Insert)
1164 InsertEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
1165 else
1166 DeleteEdge(DT, /*BUI=*/nullptr, Update.getFrom(), Update.getTo());
1167 } else {
1168 BatchUpdateInfo BUI(*PostViewCFG, PostViewCFG);
1169 if (Update.getKind() == UpdateKind::Insert)
1170 InsertEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1171 else
1172 DeleteEdge(DT, &BUI, Update.getFrom(), Update.getTo());
1173 }
1174 return;
1175 }
1176
1177 BatchUpdateInfo BUI(PreViewCFG, PostViewCFG);
1178 // Recalculate the DominatorTree when the number of updates
1179 // exceeds a threshold, which usually makes direct updating slower than
1180 // recalculation. We select this threshold proportional to the
1181 // size of the DominatorTree. The constant is selected
1182 // by choosing the one with an acceptable performance on some real-world
1183 // inputs.
1184
1185 // Make unittests of the incremental algorithm work
1186 if (DT.DomTreeNodes.size() <= 100) {
1187 if (BUI.NumLegalized > DT.DomTreeNodes.size())
1188 CalculateFromScratch(DT, &BUI);
1189 } else if (BUI.NumLegalized > DT.DomTreeNodes.size() / 40)
1190 CalculateFromScratch(DT, &BUI);
1191
1192 // If the DominatorTree was recalculated at some point, stop the batch
1193 // updates. Full recalculations ignore batch updates and look at the actual
1194 // CFG.
1195 for (size_t i = 0; i < BUI.NumLegalized && !BUI.IsRecalculated; ++i)
1196 ApplyNextUpdate(DT, BUI);
1197 }
1198
1199 static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1200 // Popping the next update, will move the PreViewCFG to the next snapshot.
1202#if 0
1203 // FIXME: The LLVM_DEBUG macro only plays well with a modular
1204 // build of LLVM when the header is marked as textual, but doing
1205 // so causes redefinition errors.
1206 LLVM_DEBUG(dbgs() << "Applying update: ");
1207 LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1208#endif
1209
1210 if (CurrentUpdate.getKind() == UpdateKind::Insert)
1211 InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1212 else
1213 DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1214 }
1215
1216 //~~
1217 //===--------------- DomTree correctness verification ---------------------===
1218 //~~
1219
1220 // Check if the tree has correct roots. A DominatorTree always has a single
1221 // root which is the function's entry node. A PostDominatorTree can have
1222 // multiple roots - one for each node with no successors and for infinite
1223 // loops.
1224 // Running time: O(N).
1225 bool verifyRoots(const DomTreeT &DT) {
1226 if (!DT.Parent && !DT.Roots.empty()) {
1227 errs() << "Tree has no parent but has roots!\n";
1228 errs().flush();
1229 return false;
1230 }
1231
1232 if (!IsPostDom) {
1233 if (DT.Roots.empty()) {
1234 errs() << "Tree doesn't have a root!\n";
1235 errs().flush();
1236 return false;
1237 }
1238
1239 if (DT.getRoot() != GetEntryNode(DT)) {
1240 errs() << "Tree's root is not its parent's entry node!\n";
1241 errs().flush();
1242 return false;
1243 }
1244 }
1245
1246 RootsT ComputedRoots = FindRoots(DT, nullptr);
1247 if (!isPermutation(DT.Roots, ComputedRoots)) {
1248 errs() << "Tree has different roots than freshly computed ones!\n";
1249 errs() << "\tPDT roots: ";
1250 for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1251 errs() << "\n\tComputed roots: ";
1252 for (const NodePtr N : ComputedRoots)
1253 errs() << BlockNamePrinter(N) << ", ";
1254 errs() << "\n";
1255 errs().flush();
1256 return false;
1257 }
1258
1259 return true;
1260 }
1261
1262 // Checks if the tree contains all reachable nodes in the input graph.
1263 // Running time: O(N).
1264 bool verifyReachability(const DomTreeT &DT) {
1265 clear();
1267
1268 for (auto &NodeToTN : DT.DomTreeNodes) {
1269 const TreeNodePtr TN = NodeToTN.second.get();
1270 const NodePtr BB = TN->getBlock();
1271
1272 // Virtual root has a corresponding virtual CFG node.
1273 if (DT.isVirtualRoot(TN)) continue;
1274
1275 if (NodeToInfo.count(BB) == 0) {
1276 errs() << "DomTree node " << BlockNamePrinter(BB)
1277 << " not found by DFS walk!\n";
1278 errs().flush();
1279
1280 return false;
1281 }
1282 }
1283
1284 for (const NodePtr N : NumToNode) {
1285 if (N && !DT.getNode(N)) {
1286 errs() << "CFG node " << BlockNamePrinter(N)
1287 << " not found in the DomTree!\n";
1288 errs().flush();
1289
1290 return false;
1291 }
1292 }
1293
1294 return true;
1295 }
1296
1297 // Check if for every parent with a level L in the tree all of its children
1298 // have level L + 1.
1299 // Running time: O(N).
1300 static bool VerifyLevels(const DomTreeT &DT) {
1301 for (auto &NodeToTN : DT.DomTreeNodes) {
1302 const TreeNodePtr TN = NodeToTN.second.get();
1303 const NodePtr BB = TN->getBlock();
1304 if (!BB) continue;
1305
1306 const TreeNodePtr IDom = TN->getIDom();
1307 if (!IDom && TN->getLevel() != 0) {
1308 errs() << "Node without an IDom " << BlockNamePrinter(BB)
1309 << " has a nonzero level " << TN->getLevel() << "!\n";
1310 errs().flush();
1311
1312 return false;
1313 }
1314
1315 if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1316 errs() << "Node " << BlockNamePrinter(BB) << " has level "
1317 << TN->getLevel() << " while its IDom "
1318 << BlockNamePrinter(IDom->getBlock()) << " has level "
1319 << IDom->getLevel() << "!\n";
1320 errs().flush();
1321
1322 return false;
1323 }
1324 }
1325
1326 return true;
1327 }
1328
1329 // Check if the computed DFS numbers are correct. Note that DFS info may not
1330 // be valid, and when that is the case, we don't verify the numbers.
1331 // Running time: O(N log(N)).
1332 static bool VerifyDFSNumbers(const DomTreeT &DT) {
1333 if (!DT.DFSInfoValid || !DT.Parent)
1334 return true;
1335
1336 const NodePtr RootBB = IsPostDom ? nullptr : *DT.root_begin();
1337 const TreeNodePtr Root = DT.getNode(RootBB);
1338
1339 auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1340 errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1341 << TN->getDFSNumOut() << '}';
1342 };
1343
1344 // Verify the root's DFS In number. Although DFS numbering would also work
1345 // if we started from some other value, we assume 0-based numbering.
1346 if (Root->getDFSNumIn() != 0) {
1347 errs() << "DFSIn number for the tree root is not:\n\t";
1348 PrintNodeAndDFSNums(Root);
1349 errs() << '\n';
1350 errs().flush();
1351 return false;
1352 }
1353
1354 // For each tree node verify if children's DFS numbers cover their parent's
1355 // DFS numbers with no gaps.
1356 for (const auto &NodeToTN : DT.DomTreeNodes) {
1357 const TreeNodePtr Node = NodeToTN.second.get();
1358
1359 // Handle tree leaves.
1360 if (Node->isLeaf()) {
1361 if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1362 errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1363 PrintNodeAndDFSNums(Node);
1364 errs() << '\n';
1365 errs().flush();
1366 return false;
1367 }
1368
1369 continue;
1370 }
1371
1372 // Make a copy and sort it such that it is possible to check if there are
1373 // no gaps between DFS numbers of adjacent children.
1374 SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1375 llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1376 return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1377 });
1378
1379 auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1380 const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1381 assert(FirstCh);
1382
1383 errs() << "Incorrect DFS numbers for:\n\tParent ";
1384 PrintNodeAndDFSNums(Node);
1385
1386 errs() << "\n\tChild ";
1387 PrintNodeAndDFSNums(FirstCh);
1388
1389 if (SecondCh) {
1390 errs() << "\n\tSecond child ";
1391 PrintNodeAndDFSNums(SecondCh);
1392 }
1393
1394 errs() << "\nAll children: ";
1395 for (const TreeNodePtr Ch : Children) {
1396 PrintNodeAndDFSNums(Ch);
1397 errs() << ", ";
1398 }
1399
1400 errs() << '\n';
1401 errs().flush();
1402 };
1403
1404 if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1405 PrintChildrenError(Children.front(), nullptr);
1406 return false;
1407 }
1408
1409 if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1410 PrintChildrenError(Children.back(), nullptr);
1411 return false;
1412 }
1413
1414 for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1415 if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1416 PrintChildrenError(Children[i], Children[i + 1]);
1417 return false;
1418 }
1419 }
1420 }
1421
1422 return true;
1423 }
1424
1425 // The below routines verify the correctness of the dominator tree relative to
1426 // the CFG it's coming from. A tree is a dominator tree iff it has two
1427 // properties, called the parent property and the sibling property. Tarjan
1428 // and Lengauer prove (but don't explicitly name) the properties as part of
1429 // the proofs in their 1972 paper, but the proofs are mostly part of proving
1430 // things about semidominators and idoms, and some of them are simply asserted
1431 // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1432 // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1433 // directed bipolar orders, and independent spanning trees" by Loukas
1434 // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1435 // and Vertex-Disjoint Paths " by the same authors.
1436
1437 // A very simple and direct explanation of these properties can be found in
1438 // "An Experimental Study of Dynamic Dominators", found at
1439 // https://arxiv.org/abs/1604.02711
1440
1441 // The easiest way to think of the parent property is that it's a requirement
1442 // of being a dominator. Let's just take immediate dominators. For PARENT to
1443 // be an immediate dominator of CHILD, all paths in the CFG must go through
1444 // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1445 // out of the CFG, there should be no paths to CHILD that are reachable. If
1446 // there are, then you now have a path from PARENT to CHILD that goes around
1447 // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1448 // a dominator of CHILD (let alone an immediate one).
1449
1450 // The sibling property is similar. It says that for each pair of sibling
1451 // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1452 // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1453 // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1454 // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1455 // RIGHT, not a sibling.
1456
1457 // It is possible to verify the parent and sibling properties in linear time,
1458 // but the algorithms are complex. Instead, we do it in a straightforward
1459 // N^2 and N^3 way below, using direct path reachability.
1460
1461 // Checks if the tree has the parent property: if for all edges from V to W in
1462 // the input graph, such that V is reachable, the parent of W in the tree is
1463 // an ancestor of V in the tree.
1464 // Running time: O(N^2).
1465 //
1466 // This means that if a node gets disconnected from the graph, then all of
1467 // the nodes it dominated previously will now become unreachable.
1468 bool verifyParentProperty(const DomTreeT &DT) {
1469 for (auto &NodeToTN : DT.DomTreeNodes) {
1470 const TreeNodePtr TN = NodeToTN.second.get();
1471 const NodePtr BB = TN->getBlock();
1472 if (!BB || TN->isLeaf())
1473 continue;
1474
1475 LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1476 << BlockNamePrinter(TN) << "\n");
1477 clear();
1478 doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1479 return From != BB && To != BB;
1480 });
1481
1482 for (TreeNodePtr Child : TN->children())
1483 if (NodeToInfo.count(Child->getBlock()) != 0) {
1484 errs() << "Child " << BlockNamePrinter(Child)
1485 << " reachable after its parent " << BlockNamePrinter(BB)
1486 << " is removed!\n";
1487 errs().flush();
1488
1489 return false;
1490 }
1491 }
1492
1493 return true;
1494 }
1495
1496 // Check if the tree has sibling property: if a node V does not dominate a
1497 // node W for all siblings V and W in the tree.
1498 // Running time: O(N^3).
1499 //
1500 // This means that if a node gets disconnected from the graph, then all of its
1501 // siblings will now still be reachable.
1502 bool verifySiblingProperty(const DomTreeT &DT) {
1503 for (auto &NodeToTN : DT.DomTreeNodes) {
1504 const TreeNodePtr TN = NodeToTN.second.get();
1505 const NodePtr BB = TN->getBlock();
1506 if (!BB || TN->isLeaf())
1507 continue;
1508
1509 for (const TreeNodePtr N : TN->children()) {
1510 clear();
1511 NodePtr BBN = N->getBlock();
1512 doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1513 return From != BBN && To != BBN;
1514 });
1515
1516 for (const TreeNodePtr S : TN->children()) {
1517 if (S == N) continue;
1518
1519 if (NodeToInfo.count(S->getBlock()) == 0) {
1520 errs() << "Node " << BlockNamePrinter(S)
1521 << " not reachable when its sibling " << BlockNamePrinter(N)
1522 << " is removed!\n";
1523 errs().flush();
1524
1525 return false;
1526 }
1527 }
1528 }
1529 }
1530
1531 return true;
1532 }
1533
1534 // Check if the given tree is the same as a freshly computed one for the same
1535 // Parent.
1536 // Running time: O(N^2), but faster in practice (same as tree construction).
1537 //
1538 // Note that this does not check if that the tree construction algorithm is
1539 // correct and should be only used for fast (but possibly unsound)
1540 // verification.
1541 static bool IsSameAsFreshTree(const DomTreeT &DT) {
1542 DomTreeT FreshTree;
1543 FreshTree.recalculate(*DT.Parent);
1544 const bool Different = DT.compare(FreshTree);
1545
1546 if (Different) {
1547 errs() << (DT.isPostDominator() ? "Post" : "")
1548 << "DominatorTree is different than a freshly computed one!\n"
1549 << "\tCurrent:\n";
1550 DT.print(errs());
1551 errs() << "\n\tFreshly computed tree:\n";
1552 FreshTree.print(errs());
1553 errs().flush();
1554 }
1555
1556 return !Different;
1557 }
1558};
1559
1560template <class DomTreeT>
1561void Calculate(DomTreeT &DT) {
1563}
1564
1565template <typename DomTreeT>
1566void CalculateWithUpdates(DomTreeT &DT,
1568 // FIXME: Updated to use the PreViewCFG and behave the same as until now.
1569 // This behavior is however incorrect; this actually needs the PostViewCFG.
1571 Updates, /*ReverseApplyUpdates=*/true);
1572 typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI(PreViewCFG);
1574}
1575
1576template <class DomTreeT>
1577void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1578 typename DomTreeT::NodePtr To) {
1579 if (DT.isPostDominator()) std::swap(From, To);
1580 SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1581}
1582
1583template <class DomTreeT>
1584void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1585 typename DomTreeT::NodePtr To) {
1586 if (DT.isPostDominator()) std::swap(From, To);
1587 SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1588}
1589
1590template <class DomTreeT>
1591void ApplyUpdates(DomTreeT &DT,
1592 GraphDiff<typename DomTreeT::NodePtr,
1593 DomTreeT::IsPostDominator> &PreViewCFG,
1594 GraphDiff<typename DomTreeT::NodePtr,
1595 DomTreeT::IsPostDominator> *PostViewCFG) {
1596 SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, PreViewCFG, PostViewCFG);
1597}
1598
1599template <class DomTreeT>
1600bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1601 SemiNCAInfo<DomTreeT> SNCA(nullptr);
1602
1603 // Simplist check is to compare against a new tree. This will also
1604 // usefully print the old and new trees, if they are different.
1605 if (!SNCA.IsSameAsFreshTree(DT))
1606 return false;
1607
1608 // Common checks to verify the properties of the tree. O(N log N) at worst.
1609 if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1610 !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1611 return false;
1612
1613 // Extra checks depending on VerificationLevel. Up to O(N^3).
1614 if (VL == DomTreeT::VerificationLevel::Basic ||
1615 VL == DomTreeT::VerificationLevel::Full)
1616 if (!SNCA.verifyParentProperty(DT))
1617 return false;
1618 if (VL == DomTreeT::VerificationLevel::Full)
1619 if (!SNCA.verifySiblingProperty(DT))
1620 return false;
1621
1622 return true;
1623}
1624
1625} // namespace DomTreeBuilder
1626} // namespace llvm
1627
1628#undef DEBUG_TYPE
1629
1630#endif
Unify divergent function exit nodes
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines a set of templates that efficiently compute a dominator tree over a generic graph.
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
#define I(x, y, z)
Definition: MD5.cpp:58
ppc ctr loops PowerPC CTR Loops Verify
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
Base class for the actual dominator tree node.
iterator_range< iterator > children()
void setIDom(DomTreeNodeBase *NewIDom)
DomTreeNodeBase * getIDom() const
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
size_t getNumChildren() const
NodeT * getBlock() const
unsigned getLevel() const
cfg::Update< NodePtr > popUpdateForIncrementalUpdates()
Definition: CFGDiff.h:113
unsigned getNumLegalizedUpdates() const
Definition: CFGDiff.h:111
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:290
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
bool empty() const
Definition: SmallVector.h:94
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1839
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1833
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2121
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
BatchUpdateInfo(GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG=nullptr)
friend raw_ostream & operator<<(raw_ostream &O, const BlockNamePrinter &BP)
std::priority_queue< TreeNodePtr, SmallVector< TreeNodePtr, 8 >, Compare > Bucket
static SmallVector< NodePtr, 8 > getChildren(NodePtr N)
static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr NCD, InsertionInfo &II)
static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)
void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC)
DenseMap< NodePtr, unsigned > NodeOrderMap
static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI)
static SmallVector< NodePtr, 8 > getChildren(NodePtr N, BatchUpdatePtr BUI)
static void ComputeUnreachableDominators(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root, const TreeNodePtr Incoming, SmallVectorImpl< std::pair< NodePtr, TreeNodePtr > > &DiscoveredConnectingEdges)
static bool VerifyLevels(const DomTreeT &DT)
static bool IsSameAsFreshTree(const DomTreeT &DT)
static void EraseNode(DomTreeT &DT, const TreeNodePtr TN)
static void ApplyUpdates(DomTreeT &DT, GraphDiffT &PreViewCFG, GraphDiffT *PostViewCFG)
void runSemiNCA(DomTreeT &DT, const unsigned MinLevel=0)
typename DomTreeT::UpdateKind UpdateKind
static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
static NodePtr GetEntryNode(const DomTreeT &DT)
static bool AlwaysDescend(NodePtr, NodePtr)
static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI)
unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, unsigned AttachToNum, const NodeOrderMap *SuccOrder=nullptr)
static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr FromTN, const TreeNodePtr ToTN)
static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI, RootsT &Roots)
static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr TN)
static bool isPermutation(const SmallVectorImpl< NodePtr > &A, const SmallVectorImpl< NodePtr > &B)
static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI)
TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT)
typename DomTreeT::UpdateType UpdateT
static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const TreeNodePtr To)
static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI)
static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr From, const NodePtr To)
static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI)
DenseMap< NodePtr, InfoRec > NodeToInfo
static bool VerifyDFSNumbers(const DomTreeT &DT)
static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI, const TreeNodePtr ToTN)
void attachNewSubtree(DomTreeT &DT, const TreeNodePtr AttachTo)
NodePtr eval(NodePtr V, unsigned LastLinked, SmallVectorImpl< InfoRec * > &Stack)
static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr From, const NodePtr To)