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