Line data Source code
1 : //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : /// \file
10 : ///
11 : /// Generic dominator tree construction - This file provides routines to
12 : /// construct immediate dominator information for a flow-graph based on the
13 : /// Semi-NCA algorithm described in this dissertation:
14 : ///
15 : /// Linear-Time Algorithms for Dominators and Related Problems
16 : /// Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
17 : /// ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
18 : ///
19 : /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
20 : /// out that the theoretically slower O(n*log(n)) implementation is actually
21 : /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
22 : ///
23 : /// The file uses the Depth Based Search algorithm to perform incremental
24 : /// updates (insertion and deletions). The implemented algorithm is based on
25 : /// this publication:
26 : ///
27 : /// An Experimental Study of Dynamic Dominators
28 : /// Loukas Georgiadis, et al., April 12 2016, pp. 5-7, 9-10:
29 : /// https://arxiv.org/pdf/1604.02711.pdf
30 : ///
31 : //===----------------------------------------------------------------------===//
32 :
33 : #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
34 : #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
35 :
36 : #include <queue>
37 : #include "llvm/ADT/ArrayRef.h"
38 : #include "llvm/ADT/DenseSet.h"
39 : #include "llvm/ADT/DepthFirstIterator.h"
40 : #include "llvm/ADT/PointerIntPair.h"
41 : #include "llvm/ADT/SmallPtrSet.h"
42 : #include "llvm/Support/Debug.h"
43 : #include "llvm/Support/GenericDomTree.h"
44 :
45 : #define DEBUG_TYPE "dom-tree-builder"
46 :
47 : namespace llvm {
48 : namespace DomTreeBuilder {
49 :
50 : template <typename DomTreeT>
51 : struct SemiNCAInfo {
52 : using NodePtr = typename DomTreeT::NodePtr;
53 : using NodeT = typename DomTreeT::NodeType;
54 : using TreeNodePtr = DomTreeNodeBase<NodeT> *;
55 : using RootsT = decltype(DomTreeT::Roots);
56 : static constexpr bool IsPostDom = DomTreeT::IsPostDominator;
57 :
58 : // Information record used by Semi-NCA during tree construction.
59 39823678 : struct InfoRec {
60 : unsigned DFSNum = 0;
61 : unsigned Parent = 0;
62 : unsigned Semi = 0;
63 : NodePtr Label = nullptr;
64 : NodePtr IDom = nullptr;
65 : SmallVector<NodePtr, 2> ReverseChildren;
66 : };
67 :
68 : // Number to node mapping is 1-based. Initialize the mapping to start with
69 : // a dummy element.
70 : std::vector<NodePtr> NumToNode = {nullptr};
71 : DenseMap<NodePtr, InfoRec> NodeToInfo;
72 :
73 : using UpdateT = typename DomTreeT::UpdateType;
74 : using UpdateKind = typename DomTreeT::UpdateKind;
75 : struct BatchUpdateInfo {
76 : SmallVector<UpdateT, 4> Updates;
77 : using NodePtrAndKind = PointerIntPair<NodePtr, 1, UpdateKind>;
78 :
79 : // In order to be able to walk a CFG that is out of sync with the CFG
80 : // DominatorTree last knew about, use the list of updates to reconstruct
81 : // previous CFG versions of the current CFG. For each node, we store a set
82 : // of its virtually added/deleted future successors and predecessors.
83 : // Note that these children are from the future relative to what the
84 : // DominatorTree knows about -- using them to gets us some snapshot of the
85 : // CFG from the past (relative to the state of the CFG).
86 : DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FutureSuccessors;
87 : DenseMap<NodePtr, SmallVector<NodePtrAndKind, 4>> FuturePredecessors;
88 : // Remembers if the whole tree was recalculated at some point during the
89 : // current batch update.
90 : bool IsRecalculated = false;
91 : };
92 :
93 : BatchUpdateInfo *BatchUpdates;
94 : using BatchUpdatePtr = BatchUpdateInfo *;
95 :
96 : // If BUI is a nullptr, then there's no batch update in progress.
97 6104013 : SemiNCAInfo(BatchUpdatePtr BUI) : BatchUpdates(BUI) {}
98 :
99 18324 : void clear() {
100 18324 : NumToNode = {nullptr}; // Restore to initial state with a dummy start node.
101 18324 : NodeToInfo.clear();
102 : // Don't reset the pointer to BatchUpdateInfo here -- if there's an update
103 : // in progress, we need this information to continue it.
104 18324 : }
105 4541 :
106 4541 : template <bool Inverse>
107 4541 : struct ChildrenGetter {
108 : using ResultTy = SmallVector<NodePtr, 8>;
109 :
110 4541 : static ResultTy Get(NodePtr N, std::integral_constant<bool, false>) {
111 12598 : auto RChildren = reverse(children<NodePtr>(N));
112 12598 : return ResultTy(RChildren.begin(), RChildren.end());
113 12598 : }
114 :
115 0 : static ResultTy Get(NodePtr N, std::integral_constant<bool, true>) {
116 12598 : auto IChildren = inverse_children<NodePtr>(N);
117 2852329 : return ResultTy(IChildren.begin(), IChildren.end());
118 : }
119 :
120 : using Tag = std::integral_constant<bool, Inverse>;
121 :
122 0 : // The function below is the core part of the batch updater. It allows the
123 0 : // Depth Based Search algorithm to perform incremental updates in lockstep
124 0 : // with updates to the CFG. We emulated lockstep CFG updates by getting its
125 : // next snapshots by reverse-applying future updates.
126 10171412 : static ResultTy Get(NodePtr N, BatchUpdatePtr BUI) {
127 0 : ResultTy Res = Get(N, Tag());
128 0 : // If there's no batch update in progress, simply return node's children.
129 10171412 : if (!BUI) return Res;
130 0 :
131 0 : // CFG children are actually its *most current* children, and we have to
132 0 : // reverse-apply the future updates to get the node's children at the
133 : // point in time the update was performed.
134 0 : auto &FutureChildren = (Inverse != IsPostDom) ? BUI->FuturePredecessors
135 0 : : BUI->FutureSuccessors;
136 0 : auto FCIt = FutureChildren.find(N);
137 0 : if (FCIt == FutureChildren.end()) return Res;
138 :
139 0 : for (auto ChildAndKind : FCIt->second) {
140 0 : const NodePtr Child = ChildAndKind.getPointer();
141 0 : const UpdateKind UK = ChildAndKind.getInt();
142 :
143 0 : // Reverse-apply the future update.
144 0 : if (UK == UpdateKind::Insert) {
145 0 : // If there's an insertion in the future, it means that the edge must
146 : // exist in the current CFG, but was not present in it before.
147 : assert(llvm::find(Res, Child) != Res.end()
148 : && "Expected child not found in the CFG");
149 0 : Res.erase(std::remove(Res.begin(), Res.end(), Child), Res.end());
150 : LLVM_DEBUG(dbgs() << "\tHiding edge " << BlockNamePrinter(N) << " -> "
151 : << BlockNamePrinter(Child) << "\n");
152 : } else {
153 : // If there's an deletion in the future, it means that the edge cannot
154 16746158 : // exist in the current CFG, but existed in it before.
155 16746158 : assert(llvm::find(Res, Child) == Res.end() &&
156 : "Unexpected child found in the CFG");
157 16746158 : LLVM_DEBUG(dbgs() << "\tShowing virtual edge " << BlockNamePrinter(N)
158 : << " -> " << BlockNamePrinter(Child) << "\n");
159 0 : Res.push_back(Child);
160 : }
161 : }
162 2664021 :
163 : return Res;
164 2664021 : }
165 5516350 : };
166 :
167 958876 : NodePtr getIDom(NodePtr BB) const {
168 7755902 : auto InfoIt = NodeToInfo.find(BB);
169 4319610 : if (InfoIt == NodeToInfo.end()) return nullptr;
170 :
171 4319610 : return InfoIt->second.IDom;
172 583963 : }
173 0 :
174 4319610 : TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
175 8639220 : if (TreeNodePtr Node = DT.getNode(BB)) return Node;
176 0 :
177 221354 : // Haven't calculated this node yet? Get or calculate the node for the
178 0 : // immediate dominator.
179 0 : NodePtr IDom = getIDom(BB);
180 :
181 : assert(IDom || DT.DomTreeNodes[nullptr]);
182 0 : TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
183 0 :
184 : // Add a new tree node for this NodeT, and link it as a child of
185 : // IDomNode
186 0 : return (DT.DomTreeNodes[BB] = IDomNode->addChild(
187 362609 : llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
188 0 : .get();
189 : }
190 :
191 4571272 : static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
192 :
193 888845 : struct BlockNamePrinter {
194 888845 : NodePtr N;
195 :
196 888845 : BlockNamePrinter(NodePtr Block) : N(Block) {}
197 : BlockNamePrinter(TreeNodePtr TN) : N(TN ? TN->getBlock() : nullptr) {}
198 0 :
199 : friend raw_ostream &operator<<(raw_ostream &O, const BlockNamePrinter &BP) {
200 : if (!BP.N)
201 193 : O << "nullptr";
202 : else
203 193 : BP.N->printAsOperand(O, false);
204 1434556 :
205 : return O;
206 154 : }
207 1434447 : };
208 :
209 : // Custom DFS implementation which can skip nodes based on a provided
210 : // predicate. It also collects ReverseChildren so that we don't have to spend
211 84 : // time getting predecessors in SemiNCA.
212 0 : //
213 : // If IsReverse is set to true, the DFS walk will be performed backwards
214 0 : // relative to IsPostDom -- using reverse edges for dominators and forward
215 0 : // edges for postdominators.
216 48 : template <bool IsReverse = false, typename DescendCondition>
217 1565110 : unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
218 0 : unsigned AttachToNum) {
219 : assert(V);
220 1565110 : SmallVector<NodePtr, 64> WorkList = {V};
221 3130220 : if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
222 0 :
223 7701492 : while (!WorkList.empty()) {
224 6136382 : const NodePtr BB = WorkList.pop_back_val();
225 : auto &BBInfo = NodeToInfo[BB];
226 36 :
227 0 : // Visited nodes always have positive DFS numbers.
228 6136382 : if (BBInfo.DFSNum != 0) continue;
229 5884720 : BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
230 5884720 : BBInfo.Label = BB;
231 5884720 : NumToNode.push_back(BB);
232 15392462 :
233 15392462 : constexpr bool Direction = IsReverse != IsPostDom; // XOR.
234 17532580 : for (const NodePtr Succ :
235 15392462 : ChildrenGetter<Direction>::Get(BB, BatchUpdates)) {
236 5763140 : const auto SIT = NodeToInfo.find(Succ);
237 0 : // Don't visit nodes more than once but remember to collect
238 : // ReverseChildren.
239 5763140 : if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
240 3822055 : if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
241 1191868 : continue;
242 2630187 : }
243 2630187 :
244 4571272 : if (!Condition(BB, Succ)) continue;
245 929307 :
246 1992466 : // It's fine to add Succ to the map, because we know that it will be
247 1426165 : // visited later.
248 : auto &SuccInfo = NodeToInfo[Succ];
249 5997437 : WorkList.push_back(Succ);
250 5137573 : SuccInfo.Parent = LastNum;
251 4571272 : SuccInfo.ReverseChildren.push_back(BB);
252 1426165 : }
253 2852330 : }
254 :
255 1774162 : return LastNum;
256 : }
257 0 :
258 5724211 : NodePtr eval(NodePtr VIn, unsigned LastLinked) {
259 5724211 : auto &VInInfo = NodeToInfo[VIn];
260 5724211 : if (VInInfo.DFSNum < LastLinked)
261 4571272 : return VIn;
262 :
263 : SmallVector<NodePtr, 32> Work;
264 0 : SmallPtrSet<NodePtr, 32> Visited;
265 357249 :
266 1152939 : if (VInInfo.Parent >= LastLinked)
267 521732 : Work.push_back(VIn);
268 :
269 6186291 : while (!Work.empty()) {
270 3389042 : NodePtr V = Work.back();
271 430104 : auto &VInfo = NodeToInfo[V];
272 3819146 : NodePtr VAncestor = NumToNode[VInfo.Parent];
273 :
274 430104 : // Process Ancestor first
275 3389042 : if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
276 1433655 : Work.push_back(VAncestor);
277 1955387 : continue;
278 0 : }
279 264 : Work.pop_back();
280 :
281 264 : // Update VInfo based on Ancestor info
282 1955651 : if (VInfo.Parent < LastLinked)
283 0 : continue;
284 211 :
285 125 : auto &VAInfo = NodeToInfo[VAncestor];
286 1433655 : NodePtr VAncestorLabel = VAInfo.Label;
287 1433655 : NodePtr VLabel = VInfo.Label;
288 1433655 : if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
289 1297162 : VInfo.Label = VAncestorLabel;
290 1433655 : VInfo.Parent = VAInfo.Parent;
291 : }
292 :
293 1152939 : return VInInfo.Label;
294 89 : }
295 1348179 :
296 : // This function requires DFS to be run before calling it.
297 1565109 : void runSemiNCA(DomTreeT &DT, const unsigned MinLevel = 0) {
298 4478397 : const unsigned NextDFSNum(NumToNode.size());
299 2696358 : // Initialize IDoms to spanning tree parents.
300 7449828 : for (unsigned i = 1; i < NextDFSNum; ++i) {
301 10225386 : const NodePtr V = NumToNode[i];
302 8877208 : auto &VInfo = NodeToInfo[V];
303 11769438 : VInfo.IDom = NumToNode[VInfo.Parent];
304 36 : }
305 :
306 2992489 : // Step #1: Calculate the semidominators of all vertices.
307 8743431 : for (unsigned i = NextDFSNum - 1; i >= 2; --i) {
308 7178322 : NodePtr W = NumToNode[i];
309 7178322 : auto &WInfo = NodeToInfo[W];
310 34747 :
311 34747 : // Initialize the semi dominator to point to the parent node.
312 12334213 : WInfo.Semi = WInfo.Parent;
313 10078568 : for (const auto &N : WInfo.ReverseChildren) {
314 8021392 : if (NodeToInfo.count(N) == 0) // Skip unreachable predecessors.
315 0 : continue;
316 :
317 8021392 : const TreeNodePtr TN = DT.getNode(N);
318 686248 : // Skip predecessors whose level is above the subtree we are processing.
319 652871 : if (TN && TN->getLevel() < MinLevel)
320 33377 : continue;
321 33377 :
322 7368521 : unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
323 5753415 : if (SemiU < WInfo.Semi) WInfo.Semi = SemiU;
324 17453 : }
325 : }
326 :
327 1644310 : // Step #2: Explicitly define the immediate dominator of each vertex.
328 1661763 : // IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
329 1644310 : // Note that the parents were stored in IDoms and later got invalidated
330 : // during path compression in Eval.
331 5884720 : for (unsigned i = 2; i < NextDFSNum; ++i) {
332 4319610 : const NodePtr W = NumToNode[i];
333 5679953 : auto &WInfo = NodeToInfo[W];
334 4319610 : const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
335 4319610 : NodePtr WIDomCandidate = WInfo.IDom;
336 6578690 : while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
337 2259079 : WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
338 0 :
339 4319611 : WInfo.IDom = WIDomCandidate;
340 : }
341 1565110 : }
342 0 :
343 5288 : // PostDominatorTree always has a virtual root that represents a virtual CFG
344 : // node that serves as a single exit from the function. All the other exits
345 : // (CFG nodes with terminators and nodes in infinite loops are logically
346 0 : // connected to this virtual CFG exit node).
347 0 : // This functions maps a nullptr CFG node to the virtual root tree node.
348 0 : void addVirtualRoot() {
349 0 : assert(IsPostDom && "Only postdominators have a virtual root");
350 : assert(NumToNode.size() == 1 && "SNCAInfo must be freshly constructed");
351 :
352 10687364 : auto &BBInfo = NodeToInfo[nullptr];
353 10687364 : BBInfo.DFSNum = BBInfo.Semi = 1;
354 0 : BBInfo.Label = nullptr;
355 10687364 :
356 : NumToNode.push_back(nullptr); // NumToNode[1] = nullptr;
357 0 : }
358 10687364 :
359 21374728 : // For postdominators, nodes with no forward successors are trivial roots that
360 : // are always selected as tree roots. Roots with forward successors correspond
361 : // to CFG nodes within infinite loops.
362 0 : static bool HasForwardSuccessors(const NodePtr N, BatchUpdatePtr BUI) {
363 0 : assert(N && "N must be a valid node");
364 : return !ChildrenGetter<false>::Get(N, BUI).empty();
365 : }
366 0 :
367 0 : static NodePtr GetEntryNode(const DomTreeT &DT) {
368 0 : assert(DT.Parent && "Parent not set");
369 0 : return GraphTraits<typename DomTreeT::ParentPtr>::getEntryNode(DT.Parent);
370 0 : }
371 :
372 : // Finds all roots without relaying on the set of roots already stored in the
373 0 : // tree.
374 423042 : // We define roots to be some non-redundant set of the CFG nodes
375 846084 : static RootsT FindRoots(const DomTreeT &DT, BatchUpdatePtr BUI) {
376 : assert(DT.Parent && "Parent pointer is not set");
377 : RootsT Roots;
378 0 :
379 0 : // For dominators, function entry CFG node is always a tree root node.
380 : if (!IsPostDom) {
381 3130220 : Roots.push_back(GetEntryNode(DT));
382 0 : return Roots;
383 : }
384 :
385 : SemiNCAInfo SNCA(BUI);
386 0 :
387 0 : // PostDominatorTree always has a virtual root.
388 0 : SNCA.addVirtualRoot();
389 0 : unsigned Num = 1;
390 10264322 :
391 20528644 : LLVM_DEBUG(dbgs() << "\t\tLooking for trivial roots\n");
392 0 :
393 : // Step #1: Find all the trivial roots that are going to will definitely
394 0 : // remain tree roots.
395 0 : unsigned Total = 0;
396 : // It may happen that there are some new nodes in the CFG that are result of
397 0 : // the ongoing batch update, but we cannot really pretend that they don't
398 0 : // exist -- we won't see any outgoing or incoming edges to them, so it's
399 0 : // fine to discover them here, as they would end up appearing in the CFG at
400 : // some point anyway.
401 : for (const NodePtr N : nodes(DT.Parent)) {
402 0 : ++Total;
403 : // If it has no *successors*, it is definitely a root.
404 : if (!HasForwardSuccessors(N, BUI)) {
405 : Roots.push_back(N);
406 : // Run DFS not to walk this part of CFG later.
407 11112641 : Num = SNCA.runDFS(N, Num, AlwaysDescend, 1);
408 0 : LLVM_DEBUG(dbgs() << "Found a new trivial root: " << BlockNamePrinter(N)
409 0 : << "\n");
410 : LLVM_DEBUG(dbgs() << "Last visited node: "
411 : << BlockNamePrinter(SNCA.NumToNode[Num]) << "\n");
412 : }
413 0 : }
414 :
415 0 : LLVM_DEBUG(dbgs() << "\t\tLooking for non-trivial roots\n");
416 0 :
417 0 : // Step #2: Find all non-trivial root candidates. Those are CFG nodes that
418 0 : // are reverse-unreachable were not visited by previous DFS walks (i.e. CFG
419 0 : // nodes in infinite loops).
420 : bool HasNonTrivialRoots = false;
421 0 : // Accounting for the virtual exit, see if we had any reverse-unreachable
422 0 : // nodes.
423 0 : if (Total + 1 != Num) {
424 0 : HasNonTrivialRoots = true;
425 0 : // Make another DFS pass over all other nodes to find the
426 0 : // reverse-unreachable blocks, and find the furthest paths we'll be able
427 0 : // to make.
428 0 : // Note that this looks N^2, but it's really 2N worst case, if every node
429 0 : // is unreachable. This is because we are still going to only visit each
430 : // unreachable node once, we may just visit it in two directions,
431 0 : // depending on how lucky we get.
432 0 : SmallPtrSet<NodePtr, 4> ConnectToExitBlock;
433 0 : for (const NodePtr I : nodes(DT.Parent)) {
434 0 : if (SNCA.NodeToInfo.count(I) == 0) {
435 0 : LLVM_DEBUG(dbgs()
436 : << "\t\t\tVisiting node " << BlockNamePrinter(I) << "\n");
437 0 : // Find the furthest away we can get by following successors, then
438 0 : // follow them in reverse. This gives us some reasonable answer about
439 0 : // the post-dom tree inside any infinite loop. In particular, it
440 : // guarantees we get to the farthest away point along *some*
441 : // path. This also matches the GCC's behavior.
442 0 : // If we really wanted a totally complete picture of dominance inside
443 : // this infinite loop, we could do it with SCC-like algorithms to find
444 : // the lowest and highest points in the infinite loop. In theory, it
445 : // would be nice to give the canonical backedge for the loop, but it's
446 : // expensive and does not always lead to a minimal set of roots.
447 0 : LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n");
448 0 :
449 3432808 : const unsigned NewNum = SNCA.runDFS<true>(I, Num, AlwaysDescend, Num);
450 : const NodePtr FurthestAway = SNCA.NumToNode[NewNum];
451 : LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node "
452 3432808 : << "(non-trivial root): "
453 6865616 : << BlockNamePrinter(FurthestAway) << "\n");
454 : ConnectToExitBlock.insert(FurthestAway);
455 20538873 : Roots.push_back(FurthestAway);
456 17103695 : LLVM_DEBUG(dbgs() << "\t\t\tPrev DFSNum: " << Num << ", new DFSNum: "
457 : << NewNum << "\n\t\t\tRemoving DFS info\n");
458 2370 : for (unsigned i = NewNum; i > Num; --i) {
459 4740 : const NodePtr N = SNCA.NumToNode[i];
460 17103695 : LLVM_DEBUG(dbgs() << "\t\t\t\tRemoving DFS info for "
461 16024116 : << BlockNamePrinter(N) << "\n");
462 16021746 : SNCA.NodeToInfo.erase(N);
463 16013914 : SNCA.NumToNode.pop_back();
464 : }
465 : const unsigned PrevNum = Num;
466 49113453 : LLVM_DEBUG(dbgs() << "\t\t\tRunning reverse DFS\n");
467 6382 : Num = SNCA.runDFS(FurthestAway, Num, AlwaysDescend, 1);
468 17084175 : for (unsigned i = PrevNum + 1; i <= Num; ++i)
469 6382 : LLVM_DEBUG(dbgs() << "\t\t\t\tfound node "
470 : << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
471 17077793 : }
472 3326915 : }
473 3406906 : }
474 10965 :
475 : LLVM_DEBUG(dbgs() << "Total: " << Total << ", Num: " << Num << "\n");
476 13830005 : LLVM_DEBUG(dbgs() << "Discovered CFG nodes:\n");
477 10965 : LLVM_DEBUG(for (size_t i = 0; i <= Num; ++i) dbgs()
478 5503 : << i << ": " << BlockNamePrinter(SNCA.NumToNode[i]) << "\n");
479 5503 :
480 : assert((Total + 1 == Num) && "Everything should have been visited");
481 13670887 :
482 13676349 : // Step #3: If we found some non-trivial roots, make them non-redundant.
483 13670887 : if (HasNonTrivialRoots) RemoveRedundantRoots(DT, BUI, Roots);
484 :
485 : LLVM_DEBUG(dbgs() << "Found roots: ");
486 : LLVM_DEBUG(for (auto *Root
487 3438270 : : Roots) dbgs()
488 5462 : << BlockNamePrinter(Root) << " ");
489 5465 : LLVM_DEBUG(dbgs() << "\n");
490 :
491 : return Roots;
492 3 : }
493 2376 :
494 : // This function only makes sense for postdominators.
495 1345815 : // We define roots to be some set of CFG nodes where (reverse) DFS walks have
496 3 : // to start in order to visit all the CFG nodes (including the
497 : // reverse-unreachable ones).
498 1345809 : // When the search for non-trivial roots is done it may happen that some of
499 2691618 : // the non-trivial roots are reverse-reachable from other non-trivial roots,
500 3 : // which makes them redundant. This function removes them from the set of
501 4330468 : // input roots.
502 2984660 : static void RemoveRedundantRoots(const DomTreeT &DT, BatchUpdatePtr BUI,
503 3 : RootsT &Roots) {
504 : assert(IsPostDom && "This function is for postdominators only");
505 : LLVM_DEBUG(dbgs() << "Removing redundant roots\n");
506 2984663 :
507 2852330 : SemiNCAInfo SNCA(BUI);
508 2852330 :
509 2852330 : for (unsigned i = 0; i < Roots.size(); ++i) {
510 : auto &Root = Roots[i];
511 0 : // Trivial roots are always non-redundant.
512 7990874 : if (!HasForwardSuccessors(Root, BUI)) continue;
513 0 : LLVM_DEBUG(dbgs() << "\tChecking if " << BlockNamePrinter(Root)
514 2286216 : << " remains a root\n");
515 : SNCA.clear();
516 0 : // Do a forward walk looking for the other roots.
517 2286216 : const unsigned Num = SNCA.runDFS<true>(Root, 0, AlwaysDescend, 0);
518 647368 : // Skip the start node and begin from the second one (note that DFS uses
519 647368 : // 1-based indexing).
520 : for (unsigned x = 2; x <= Num; ++x) {
521 0 : const NodePtr N = SNCA.NumToNode[x];
522 1638848 : // If we wound another root in a (forward) DFS walk, remove the current
523 0 : // root from the set of roots, as it is reverse-reachable from the other
524 : // one.
525 : if (llvm::find(Roots, N) != Roots.end()) {
526 : LLVM_DEBUG(dbgs() << "\tForward DFS walk found another root "
527 1638851 : << BlockNamePrinter(N) << "\n\tRemoving root "
528 1638848 : << BlockNamePrinter(Root) << "\n");
529 1654756 : std::swap(Root, Roots.back());
530 : Roots.pop_back();
531 :
532 15908 : // Root at the back takes the current root's place.
533 1377624 : // Start the next loop iteration with the same index.
534 : --i;
535 610171 : break;
536 594263 : }
537 : }
538 0 : }
539 0 : }
540 594263 :
541 558878 : template <typename DescendCondition>
542 558878 : void doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
543 558878 : if (!IsPostDom) {
544 : assert(DT.Roots.size() == 1 && "Dominators should have a singe root");
545 1565109 : runDFS(DT.Roots[0], 0, DC, 0);
546 1861905 : return;
547 0 : }
548 744149 :
549 0 : addVirtualRoot();
550 : unsigned Num = 1;
551 744149 : for (const NodePtr Root : DT.Roots) Num = runDFS(Root, Num, DC, 0);
552 142242 : }
553 165794 :
554 1565110 : static void CalculateFromScratch(DomTreeT &DT, BatchUpdatePtr BUI) {
555 1565110 : auto *Parent = DT.Parent;
556 601907 : DT.reset();
557 1565110 : DT.Parent = Parent;
558 3130219 : SemiNCAInfo SNCA(nullptr); // Since we are rebuilding the whole tree,
559 0 : // there's no point doing it incrementally.
560 :
561 578355 : // Step #0: Number blocks in depth-first order and initialize variables used
562 578355 : // in later stages of the algorithm.
563 2143464 : DT.Roots = FindRoots(DT, nullptr);
564 : SNCA.doFullDFSWalk(DT, AlwaysDescend);
565 :
566 1565110 : SNCA.runSemiNCA(DT);
567 1581018 : if (BUI) {
568 0 : BUI->IsRecalculated = true;
569 5990 : LLVM_DEBUG(
570 : dbgs() << "DomTree recalculated, skipping future batch updates\n");
571 : }
572 5990 :
573 1577090 : if (DT.Roots.empty()) return;
574 :
575 27245 : // Add a node for the root. If the tree is a PostDominatorTree it will be
576 1148640 : // the virtual exit (denoted by (BasicBlock *) nullptr) which postdominates
577 1127385 : // all real exits (including multiple exit blocks, infinite loops).
578 2692495 : NodePtr Root = IsPostDom ? nullptr : DT.Roots[0];
579 819460 :
580 3151475 : DT.RootNode = (DT.DomTreeNodes[Root] =
581 20382 : llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
582 20382 : .get();
583 1585492 : SNCA.attachNewSubtree(DT, DT.RootNode);
584 307925 : }
585 181175 :
586 1627767 : void attachNewSubtree(DomTreeT& DT, const TreeNodePtr AttachTo) {
587 1442172 : // Attach the first unreachable block to AttachTo.
588 4286360 : NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
589 0 : // Loop over all of the discovered blocks in the function...
590 8584077 : for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
591 5906614 : NodePtr W = NumToNode[i];
592 4218 : LLVM_DEBUG(dbgs() << "\tdiscovered a new reachable node "
593 1140875 : << BlockNamePrinter(W) << "\n");
594 476536 :
595 657711 : // Don't replace this with 'count', the insertion side effect is important
596 5920071 : if (DT.DomTreeNodes[W]) continue; // Haven't calculated this node yet?
597 0 :
598 4319610 : NodePtr ImmDom = getIDom(W);
599 0 :
600 657711 : // Get or calculate the node for the immediate dominator.
601 4334875 : TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
602 15265 :
603 15265 : // Add a new tree node for this BasicBlock, and link it as a child of
604 476536 : // IDomNode.
605 9115756 : DT.DomTreeNodes[W] = IDomNode->addChild(
606 476536 : llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
607 316806 : }
608 2041645 : }
609 4985 :
610 : void reattachExistingSubtree(DomTreeT &DT, const TreeNodePtr AttachTo) {
611 307925 : NodeToInfo[NumToNode[1]].IDom = AttachTo->getBlock();
612 4985 : for (size_t i = 1, e = NumToNode.size(); i != e; ++i) {
613 9970 : const NodePtr N = NumToNode[i];
614 : const TreeNodePtr TN = DT.getNode(N);
615 617477 : assert(TN);
616 1209822 : const TreeNodePtr NewIDom = DT.getNode(NodeToInfo[N].IDom);
617 0 : TN->setIDom(NewIDom);
618 2620825 : }
619 2023495 : }
620 2038657 :
621 4061690 : // Helper struct used during edge insertions.
622 14700 : struct InsertionInfo {
623 14700 : using BucketElementTy = std::pair<unsigned, TreeNodePtr>;
624 0 : struct DecreasingLevel {
625 2023495 : bool operator()(const BucketElementTy &First,
626 1470876 : const BucketElementTy &Second) const {
627 1426165 : return First.first > Second.first;
628 15311 : }
629 : };
630 1426165 :
631 2568861 : std::priority_queue<BucketElementTy, SmallVector<BucketElementTy, 8>,
632 1130006 : DecreasingLevel>
633 5134 : Bucket; // Queue of tree nodes sorted by level in descending order.
634 0 : SmallDenseSet<TreeNodePtr, 8> Affected;
635 1127385 : SmallDenseMap<TreeNodePtr, unsigned, 8> Visited;
636 25380 : SmallVector<TreeNodePtr, 8> AffectedQueue;
637 0 : SmallVector<TreeNodePtr, 8> VisitedNotAffectedQueue;
638 : };
639 :
640 1127385 : static void InsertEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
641 1137562 : const NodePtr From, const NodePtr To) {
642 10177 : assert((From || IsPostDom) &&
643 10177 : "From has to be a valid CFG node or a virtual root");
644 0 : assert(To && "Cannot be a nullptr");
645 0 : LLVM_DEBUG(dbgs() << "Inserting edge " << BlockNamePrinter(From) << " -> "
646 0 : << BlockNamePrinter(To) << "\n");
647 4985 : TreeNodePtr FromTN = DT.getNode(From);
648 0 :
649 2025974 : if (!FromTN) {
650 1426165 : // Ignore edges from unreachable nodes for (forward) dominators.
651 1426165 : if (!IsPostDom) return;
652 1428644 :
653 1431123 : // The unreachable node becomes a new root -- a tree node for it.
654 1886241 : TreeNodePtr VirtualRoot = DT.getNode(nullptr);
655 479338 : FromTN =
656 16783 : (DT.DomTreeNodes[From] = VirtualRoot->addChild(
657 1426165 : llvm::make_unique<DomTreeNodeBase<NodeT>>(From, VirtualRoot)))
658 0 : .get();
659 597330 : DT.Roots.push_back(From);
660 16783 : }
661 16469 :
662 16469 : DT.DFSInfoValid = false;
663 16469 :
664 : const TreeNodePtr ToTN = DT.getNode(To);
665 0 : if (!ToTN)
666 1246279 : InsertUnreachable(DT, BUI, FromTN, To);
667 0 : else
668 18681 : InsertReachable(DT, BUI, FromTN, ToTN);
669 : }
670 1194660 :
671 1213341 : // Determines if some existing root becomes reverse-reachable after the
672 1196275 : // insertion. Rebuilds the whole tree if that situation happens.
673 4377 : static bool UpdateRootsBeforeInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
674 1194660 : const TreeNodePtr From,
675 1194660 : const TreeNodePtr To) {
676 34132 : assert(IsPostDom && "This function is only for postdominators");
677 0 : // Destination node is not attached to the virtual root, so it cannot be a
678 : // root.
679 : if (!DT.isVirtualRoot(To->getIDom())) return false;
680 1427981 :
681 14304 : auto RIt = llvm::find(DT.Roots, To->getBlock());
682 1442285 : if (RIt == DT.Roots.end())
683 14304 : return false; // To is not a root, nothing to update.
684 :
685 : LLVM_DEBUG(dbgs() << "\t\tAfter the insertion, " << BlockNamePrinter(To)
686 : << " is no longer a root\n\t\tRebuilding the tree!!!\n");
687 2479 :
688 : CalculateFromScratch(DT, BUI);
689 1739 : return true;
690 0 : }
691 0 :
692 1739 : // Updates the set of roots after insertion or deletion. This ensures that
693 600808 : // roots are the same when after a series of updates and when the tree would
694 0 : // be built from scratch.
695 9603 : static void UpdateRootsAfterUpdate(DomTreeT &DT, const BatchUpdatePtr BUI) {
696 7864 : assert(IsPostDom && "This function is only for postdominators");
697 0 :
698 : // The tree has only trivial roots -- nothing to update.
699 0 : if (std::none_of(DT.Roots.begin(), DT.Roots.end(), [BUI](const NodePtr N) {
700 7864 : return HasForwardSuccessors(N, BUI);
701 7754 : }))
702 7754 : return;
703 1202414 :
704 : // Recalculate the set of roots.
705 : auto Roots = FindRoots(DT, BUI);
706 621443 : if (DT.Roots.size() != Roots.size() ||
707 : !std::is_permutation(DT.Roots.begin(), DT.Roots.end(), Roots.begin())) {
708 8605 : // The roots chosen in the CFG have changed. This is because the
709 : // incremental algorithm does not really know or use the set of roots and
710 : // can make a different (implicit) decision about which node within an
711 8605 : // infinite loop becomes a root.
712 638 :
713 2480 : LLVM_DEBUG(dbgs() << "Roots are different in updated trees\n"
714 : << "The entire tree needs to be rebuilt\n");
715 : // It may be possible to update the tree without recalculating it, but
716 15934 : // we do not know yet how to do it, and it happens rarely in practise.
717 : CalculateFromScratch(DT, BUI);
718 : return;
719 2023495 : }
720 1426165 : }
721 6125 :
722 1432290 : // Handles insertion to a node already in the dominator tree.
723 677864 : static void InsertReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
724 : const TreeNodePtr From, const TreeNodePtr To) {
725 671739 : LLVM_DEBUG(dbgs() << "\tReachable " << BlockNamePrinter(From->getBlock())
726 : << " -> " << BlockNamePrinter(To->getBlock()) << "\n");
727 1739 : if (IsPostDom && UpdateRootsBeforeInsertion(DT, BUI, From, To)) return;
728 : // DT.findNCD expects both pointers to be valid. When From is a virtual
729 39 : // root, then its CFG block pointer is a nullptr, so we have to 'compute'
730 : // the NCD manually.
731 : const NodePtr NCDBlock =
732 39 : (From->getBlock() && To->getBlock())
733 78 : ? DT.findNearestCommonDominator(From->getBlock(), To->getBlock())
734 : : nullptr;
735 223 : assert(NCDBlock || DT.isPostDominator());
736 184 : const TreeNodePtr NCD = DT.getNode(NCDBlock);
737 : assert(NCD);
738 :
739 0 : LLVM_DEBUG(dbgs() << "\t\tNCA == " << BlockNamePrinter(NCD) << "\n");
740 184 : const TreeNodePtr ToIDom = To->getIDom();
741 597510 :
742 180 : // Nothing affected -- NCA property holds.
743 180 : // (Based on the lemma 2.5 from the second paper.)
744 : if (NCD == To || NCD == ToIDom) return;
745 :
746 543 : // Identify and collect affected nodes.
747 : InsertionInfo II;
748 183 : LLVM_DEBUG(dbgs() << "Marking " << BlockNamePrinter(To)
749 : << " as affected\n");
750 : II.Affected.insert(To);
751 7184 : const unsigned ToLevel = To->getLevel();
752 4750 : LLVM_DEBUG(dbgs() << "Putting " << BlockNamePrinter(To)
753 38 : << " into a Bucket\n");
754 : II.Bucket.push({ToLevel, To});
755 :
756 163 : while (!II.Bucket.empty()) {
757 : const TreeNodePtr CurrentNode = II.Bucket.top().second;
758 : const unsigned CurrentLevel = CurrentNode->getLevel();
759 : II.Bucket.pop();
760 : LLVM_DEBUG(dbgs() << "\tAdding to Visited and AffectedQueue: "
761 145 : << BlockNamePrinter(CurrentNode) << "\n");
762 145 :
763 145 : II.Visited.insert({CurrentNode, CurrentLevel});
764 : II.AffectedQueue.push_back(CurrentNode);
765 :
766 : // Discover and collect affected successors of the current node.
767 1224 : VisitInsertion(DT, BUI, CurrentNode, CurrentLevel, NCD, II);
768 1185 : }
769 8018 :
770 : // Finish by updating immediate dominators and levels.
771 : UpdateInsertion(DT, BUI, NCD, II);
772 9203 : }
773 17221 :
774 : // Visits an affected node and collect its affected successors.
775 771698 : static void VisitInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
776 768761 : const TreeNodePtr TN, const unsigned RootLevel,
777 3896 : const TreeNodePtr NCD, InsertionInfo &II) {
778 : const unsigned NCDLevel = NCD->getLevel();
779 : LLVM_DEBUG(dbgs() << "Visiting " << BlockNamePrinter(TN) << ", RootLevel "
780 767576 : << RootLevel << "\n");
781 716328 :
782 716328 : SmallVector<TreeNodePtr, 8> Stack = {TN};
783 716328 : assert(TN->getBlock() && II.Visited.count(TN) && "Preconditions!");
784 :
785 1185 : SmallPtrSet<TreeNodePtr, 8> Processed;
786 2404375 :
787 : do {
788 966818 : TreeNodePtr Next = Stack.pop_back_val();
789 : LLVM_DEBUG(dbgs() << " Next: " << BlockNamePrinter(Next) << "\n");
790 :
791 966818 : for (const NodePtr Succ :
792 195168 : ChildrenGetter<IsPostDom>::Get(Next->getBlock(), BUI)) {
793 211156 : const TreeNodePtr SuccTN = DT.getNode(Succ);
794 : assert(SuccTN && "Unreachable successor found at reachable insertion");
795 : const unsigned SuccLevel = SuccTN->getLevel();
796 771650 :
797 : LLVM_DEBUG(dbgs() << "\tSuccessor " << BlockNamePrinter(Succ)
798 : << ", level = " << SuccLevel << "\n");
799 :
800 : // Do not process the same node multiple times.
801 756748 : if (Processed.count(Next) > 0)
802 755662 : continue;
803 755662 :
804 : // Succ dominated by subtree From -- not affected.
805 : // (Based on the lemma 2.5 from the second paper.)
806 : if (SuccLevel > RootLevel) {
807 8018 : LLVM_DEBUG(dbgs() << "\t\tDominated by subtree From\n");
808 : if (II.Visited.count(SuccTN) != 0) {
809 25045 : LLVM_DEBUG(dbgs() << "\t\t\talready visited at level "
810 : << II.Visited[SuccTN] << "\n\t\t\tcurrent level "
811 : << RootLevel << ")\n");
812 25045 :
813 50090 : // A node can be necessary to visit again if we see it again at
814 : // a lower level than before.
815 658119 : if (II.Visited[SuccTN] >= RootLevel)
816 633074 : continue;
817 : }
818 :
819 : LLVM_DEBUG(dbgs() << "\t\tMarking visited not affected "
820 634160 : << BlockNamePrinter(Succ) << "\n");
821 596094 : II.Visited.insert({SuccTN, RootLevel});
822 596094 : II.VisitedNotAffectedQueue.push_back(SuccTN);
823 596094 : Stack.push_back(SuccTN);
824 : } else if ((SuccLevel > NCDLevel + 1) &&
825 2172 : II.Affected.count(SuccTN) == 0) {
826 1977931 : LLVM_DEBUG(dbgs() << "\t\tMarking affected and adding "
827 2902 : << BlockNamePrinter(Succ) << " to a Bucket\n");
828 785743 : II.Affected.insert(SuccTN);
829 : II.Bucket.push({SuccLevel, SuccTN});
830 1816 : }
831 785743 : }
832 148246 :
833 178899 : Processed.insert(Next);
834 : } while (!Stack.empty());
835 1185 : }
836 637497 :
837 : // Updates immediate dominators and levels after insertion.
838 2417 : static void UpdateInsertion(DomTreeT &DT, const BatchUpdatePtr BUI,
839 2542 : const TreeNodePtr NCD, InsertionInfo &II) {
840 : LLVM_DEBUG(dbgs() << "Updating NCD = " << BlockNamePrinter(NCD) << "\n");
841 608029 :
842 608029 : for (const TreeNodePtr TN : II.AffectedQueue) {
843 609300 : LLVM_DEBUG(dbgs() << "\tIDom(" << BlockNamePrinter(TN)
844 : << ") = " << BlockNamePrinter(NCD) << "\n");
845 : TN->setIDom(NCD);
846 : }
847 25045 :
848 : UpdateLevelsAfterInsertion(II);
849 14306 : if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
850 : }
851 :
852 14345 : static void UpdateLevelsAfterInsertion(InsertionInfo &II) {
853 28651 : LLVM_DEBUG(
854 : dbgs() << "Updating levels for visited but not affected nodes\n");
855 598796 :
856 584490 : for (const TreeNodePtr TN : II.VisitedNotAffectedQueue) {
857 1086 : LLVM_DEBUG(dbgs() << "\tlevel(" << BlockNamePrinter(TN) << ") = ("
858 : << BlockNamePrinter(TN->getIDom()) << ") "
859 : << TN->getIDom()->getLevel() << " + 1\n");
860 1181820 : TN->UpdateLevel();
861 542225 : }
862 542225 : }
863 542225 :
864 : // Handles insertion to previously unreachable nodes.
865 : static void InsertUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
866 1851439 : const TreeNodePtr From, const NodePtr To) {
867 597330 : LLVM_DEBUG(dbgs() << "Inserting " << BlockNamePrinter(From)
868 766989 : << " -> (unreachable) " << BlockNamePrinter(To) << "\n");
869 1270215 :
870 : // Collect discovered edges to already reachable nodes.
871 766989 : SmallVector<std::pair<NodePtr, TreeNodePtr>, 8> DiscoveredEdgesToReachable;
872 171638 : // Discover and connect nodes that became reachable with the insertion.
873 196805 : ComputeUnreachableDominators(DT, BUI, To, From, DiscoveredEdgesToReachable);
874 :
875 : LLVM_DEBUG(dbgs() << "Inserted " << BlockNamePrinter(From)
876 595351 : << " -> (prev unreachable) " << BlockNamePrinter(To)
877 : << "\n");
878 0 :
879 : // Used the discovered edges and inset discovered connecting (incoming)
880 0 : // edges.
881 570184 : for (const auto &Edge : DiscoveredEdgesToReachable) {
882 570184 : LLVM_DEBUG(dbgs() << "\tInserting discovered connecting edge "
883 570184 : << BlockNamePrinter(Edge.first) << " -> "
884 : << BlockNamePrinter(Edge.second) << "\n");
885 : InsertReachable(DT, BUI, DT.getNode(Edge.first), Edge.second);
886 : }
887 14306 : }
888 :
889 784 : // Connects nodes that become reachable with an insertion.
890 : static void ComputeUnreachableDominators(
891 0 : DomTreeT &DT, const BatchUpdatePtr BUI, const NodePtr Root,
892 784 : const TreeNodePtr Incoming,
893 598898 : SmallVectorImpl<std::pair<NodePtr, TreeNodePtr>>
894 : &DiscoveredConnectingEdges) {
895 2704 : assert(!DT.getNode(Root) && "Root must not be reachable");
896 1920 :
897 : // Visit only previously unreachable nodes.
898 : auto UnreachableDescender = [&DT, &DiscoveredConnectingEdges](NodePtr From,
899 : NodePtr To) {
900 599250 : const TreeNodePtr ToTN = DT.getNode(To);
901 1869 : if (!ToTN) return true;
902 1272084 :
903 1869 : DiscoveredConnectingEdges.push_back({From, ToTN});
904 : return false;
905 597330 : };
906 603227 :
907 : SemiNCAInfo SNCA(BUI);
908 599489 : SNCA.runDFS(Root, 0, UnreachableDescender, 0);
909 1194660 : SNCA.runSemiNCA(DT);
910 : SNCA.attachNewSubtree(DT, Incoming);
911 2159 :
912 1023 : LLVM_DEBUG(dbgs() << "After adding unreachable nodes\n");
913 1023 : }
914 597330 :
915 597330 : static void DeleteEdge(DomTreeT &DT, const BatchUpdatePtr BUI,
916 1136 : const NodePtr From, const NodePtr To) {
917 597330 : assert(From && To && "Cannot disconnect nullptrs");
918 597330 : LLVM_DEBUG(dbgs() << "Deleting edge " << BlockNamePrinter(From) << " -> "
919 0 : << BlockNamePrinter(To) << "\n");
920 :
921 1136 : #ifndef NDEBUG
922 1136 : // Ensure that the edge was in fact deleted from the CFG before informing
923 1136 : // the DomTree about it.
924 597330 : // The check is O(N), so run it only in debug configuration.
925 0 : auto IsSuccessor = [BUI](const NodePtr SuccCandidate, const NodePtr Of) {
926 0 : auto Successors = ChildrenGetter<IsPostDom>::Get(Of, BUI);
927 784 : return llvm::find(Successors, SuccCandidate) != Successors.end();
928 : };
929 973099 : (void)IsSuccessor;
930 : assert(!IsSuccessor(To, From) && "Deleted edge still exists in the CFG!");
931 1194660 : #endif
932 375769 :
933 751538 : const TreeNodePtr FromTN = DT.getNode(From);
934 597330 : // Deletion in an unreachable subtree -- nothing to do.
935 1250074 : if (!FromTN) return;
936 874305 :
937 597330 : const TreeNodePtr ToTN = DT.getNode(To);
938 0 : if (!ToTN) {
939 1194660 : LLVM_DEBUG(
940 874305 : dbgs() << "\tTo (" << BlockNamePrinter(To)
941 3474191 : << ") already unreachable -- there is no edge to delete\n");
942 2876861 : return;
943 853366 : }
944 0 :
945 : const NodePtr NCDBlock = DT.findNearestCommonDominator(From, To);
946 2448553 : const TreeNodePtr NCD = DT.getNode(NCDBlock);
947 2023495 :
948 741821 : // If To dominates From -- nothing to do.
949 1426165 : if (ToTN != NCD) {
950 : DT.DFSInfoValid = false;
951 741821 :
952 1669450 : const TreeNodePtr ToIDom = ToTN->getIDom();
953 243285 : LLVM_DEBUG(dbgs() << "\tNCD " << BlockNamePrinter(NCD) << ", ToIDom "
954 0 : << BlockNamePrinter(ToIDom) << "\n");
955 :
956 3350866 : // To remains reachable after deletion.
957 : // (Based on the caption under Figure 4. from the second paper.)
958 : if (FromTN != ToIDom || HasProperSupport(DT, BUI, ToTN))
959 597330 : DeleteReachable(DT, BUI, FromTN, ToTN);
960 : else
961 498536 : DeleteUnreachable(DT, BUI, ToTN);
962 498536 : }
963 498536 :
964 0 : if (IsPostDom) UpdateRootsAfterUpdate(DT, BUI);
965 : }
966 0 :
967 375769 : // Handles deletions that leave destination nodes reachable.
968 0 : static void DeleteReachable(DomTreeT &DT, const BatchUpdatePtr BUI,
969 2977743 : const TreeNodePtr FromTN,
970 0 : const TreeNodePtr ToTN) {
971 0 : LLVM_DEBUG(dbgs() << "Deleting reachable " << BlockNamePrinter(FromTN)
972 2977743 : << " -> " << BlockNamePrinter(ToTN) << "\n");
973 5955486 : LLVM_DEBUG(dbgs() << "\tRebuilding subtree\n");
974 0 :
975 16568455 : // Find the top of the subtree that needs to be rebuilt.
976 13590712 : // (Based on the lemma 2.6 from the second paper.)
977 0 : const NodePtr ToIDom =
978 0 : DT.findNearestCommonDominator(FromTN->getBlock(), ToTN->getBlock());
979 : assert(ToIDom || DT.isPostDominator());
980 13590712 : const TreeNodePtr ToIDomTN = DT.getNode(ToIDom);
981 12685666 : assert(ToIDomTN);
982 12685666 : const TreeNodePtr PrevIDomSubTree = ToIDomTN->getIDom();
983 12685666 : // Top of the subtree to rebuild is the root node. Rebuild the tree from
984 : // scratch.
985 0 : if (!PrevIDomSubTree) {
986 38376773 : LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
987 : CalculateFromScratch(DT, BUI);
988 13005441 : return;
989 : }
990 :
991 13005441 : // Only visit nodes in the subtree starting at To.
992 2392472 : const unsigned Level = ToIDomTN->getLevel();
993 2392472 : auto DescendBelow = [Level, &DT](NodePtr, NodePtr To) {
994 : return DT.getNode(To)->getLevel() > Level;
995 : };
996 10612969 :
997 : LLVM_DEBUG(dbgs() << "\tTop of subtree: " << BlockNamePrinter(ToIDomTN)
998 0 : << "\n");
999 :
1000 0 : SemiNCAInfo SNCA(BUI);
1001 10612969 : SNCA.runDFS(ToIDom, 0, DescendBelow, 0);
1002 10612969 : LLVM_DEBUG(dbgs() << "\tRunning Semi-NCA\n");
1003 10612969 : SNCA.runSemiNCA(DT, Level);
1004 : SNCA.reattachExistingSubtree(DT, PrevIDomSubTree);
1005 : }
1006 :
1007 2977743 : // Checks if a node has proper support, as defined on the page 3 and later
1008 : // explained on the page 7 of the second paper.
1009 : static bool HasProperSupport(DomTreeT &DT, const BatchUpdatePtr BUI,
1010 15695826 : const TreeNodePtr TN) {
1011 15695826 : LLVM_DEBUG(dbgs() << "IsReachableFromIDom " << BlockNamePrinter(TN)
1012 15695826 : << "\n");
1013 12761254 : for (const NodePtr Pred :
1014 : ChildrenGetter<!IsPostDom>::Get(TN->getBlock(), BUI)) {
1015 : LLVM_DEBUG(dbgs() << "\tPred " << BlockNamePrinter(Pred) << "\n");
1016 0 : if (!DT.getNode(Pred)) continue;
1017 0 :
1018 2934572 : const NodePtr Support =
1019 1285442 : DT.findNearestCommonDominator(TN->getBlock(), Pred);
1020 0 : LLVM_DEBUG(dbgs() << "\tSupport " << BlockNamePrinter(Support) << "\n");
1021 12062706 : if (Support != TN->getBlock()) {
1022 9128134 : LLVM_DEBUG(dbgs() << "\t" << BlockNamePrinter(TN)
1023 0 : << " is reachable from support "
1024 9128134 : << BlockNamePrinter(Support) << "\n");
1025 : return true;
1026 0 : }
1027 9128134 : }
1028 3921346 :
1029 5206788 : return false;
1030 0 : }
1031 :
1032 0 : // Handle deletions that make destination node unreachable.
1033 0 : // (Based on the lemma 2.7 from the second paper.)
1034 5206788 : static void DeleteUnreachable(DomTreeT &DT, const BatchUpdatePtr BUI,
1035 : const TreeNodePtr ToTN) {
1036 : LLVM_DEBUG(dbgs() << "Deleting unreachable subtree "
1037 : << BlockNamePrinter(ToTN) << "\n");
1038 3921346 : assert(ToTN);
1039 3921346 : assert(ToTN->getBlock());
1040 3921346 :
1041 3561840 : if (IsPostDom) {
1042 3921346 : // Deletion makes a region reverse-unreachable and creates a new root.
1043 : // Simulate that by inserting an edge from the virtual root to ToTN and
1044 : // adding it as a new root.
1045 2934572 : LLVM_DEBUG(dbgs() << "\tDeletion made a region reverse-unreachable\n");
1046 0 : LLVM_DEBUG(dbgs() << "\tAdding new root " << BlockNamePrinter(ToTN)
1047 363744 : << "\n");
1048 363744 : DT.Roots.push_back(ToTN->getBlock());
1049 363744 : InsertReachable(DT, BUI, DT.getNode(nullptr), ToTN);
1050 246649 : return;
1051 0 : }
1052 :
1053 0 : SmallVector<NodePtr, 16> AffectedQueue;
1054 : const unsigned Level = ToTN->getLevel();
1055 117095 :
1056 63024 : // Traverse destination node's descendants with greater level in the tree
1057 0 : // and collect visited nodes.
1058 453621 : auto DescendAndCollect = [Level, &AffectedQueue, &DT](NodePtr, NodePtr To) {
1059 336526 : const TreeNodePtr TN = DT.getNode(To);
1060 : assert(TN);
1061 336526 : if (TN->getLevel() > Level) return true;
1062 : if (llvm::find(AffectedQueue, To) == AffectedQueue.end())
1063 : AffectedQueue.push_back(To);
1064 336526 :
1065 136751 : return false;
1066 199775 : };
1067 :
1068 0 : SemiNCAInfo SNCA(BUI);
1069 : unsigned LastDFSNum =
1070 : SNCA.runDFS(ToTN->getBlock(), 0, DescendAndCollect, 0);
1071 199775 :
1072 : TreeNodePtr MinNode = ToTN;
1073 :
1074 0 : // Identify the top of the subtree to rebuild by finding the NCD of all
1075 136751 : // the affected nodes.
1076 136751 : for (const NodePtr N : AffectedQueue) {
1077 136751 : const TreeNodePtr TN = DT.getNode(N);
1078 81224 : const NodePtr NCDBlock =
1079 136751 : DT.findNearestCommonDominator(TN->getBlock(), ToTN->getBlock());
1080 : assert(NCDBlock || DT.isPostDominator());
1081 0 : const TreeNodePtr NCD = DT.getNode(NCDBlock);
1082 117095 : assert(NCD);
1083 0 :
1084 15332082 : LLVM_DEBUG(dbgs() << "Processing affected node " << BlockNamePrinter(TN)
1085 15332082 : << " with NCD = " << BlockNamePrinter(NCD)
1086 15332082 : << ", MinNode =" << BlockNamePrinter(MinNode) << "\n");
1087 12514605 : if (NCD != TN && NCD->getLevel() < MinNode->getLevel()) MinNode = NCD;
1088 : }
1089 :
1090 0 : // Root reached, rebuild the whole tree from scratch.
1091 0 : if (!MinNode->getIDom()) {
1092 2817477 : LLVM_DEBUG(dbgs() << "The entire tree needs to be rebuilt\n");
1093 1222418 : CalculateFromScratch(DT, BUI);
1094 : return;
1095 11609085 : }
1096 8791608 :
1097 : // Erase the unreachable subtree in reverse preorder to process all children
1098 8791608 : // before deleting their parent.
1099 : for (unsigned i = LastDFSNum; i > 0; --i) {
1100 : const NodePtr N = SNCA.NumToNode[i];
1101 8791608 : const TreeNodePtr TN = DT.getNode(N);
1102 3784595 : LLVM_DEBUG(dbgs() << "Erasing node " << BlockNamePrinter(TN) << "\n");
1103 5007013 :
1104 : EraseNode(DT, TN);
1105 0 : }
1106 :
1107 0 : // The affected subtree start at the To node -- there's no extra work to do.
1108 5007013 : if (MinNode == ToTN) return;
1109 0 :
1110 : LLVM_DEBUG(dbgs() << "DeleteUnreachable: running DFS with MinNode = "
1111 : << BlockNamePrinter(MinNode) << "\n");
1112 3784595 : const unsigned MinLevel = MinNode->getLevel();
1113 3784595 : const TreeNodePtr PrevIDom = MinNode->getIDom();
1114 3784595 : assert(PrevIDom);
1115 3480616 : SNCA.clear();
1116 3784595 :
1117 : // Identify nodes that remain in the affected subtree.
1118 0 : auto DescendBelow = [MinLevel, &DT](NodePtr, NodePtr To) {
1119 2817477 : const TreeNodePtr ToTN = DT.getNode(To);
1120 : return ToTN && ToTN->getLevel() > MinLevel;
1121 0 : };
1122 0 : SNCA.runDFS(MinNode->getBlock(), 0, DescendBelow, 0);
1123 3170175 :
1124 6340350 : LLVM_DEBUG(dbgs() << "Previous IDom(MinNode) = "
1125 0 : << BlockNamePrinter(PrevIDom) << "\nRunning Semi-NCA\n");
1126 18248173 :
1127 15077998 : // Rebuild the remaining part of affected subtree.
1128 15077998 : SNCA.runSemiNCA(DT, MinLevel);
1129 30155996 : SNCA.reattachExistingSubtree(DT, PrevIDom);
1130 : }
1131 :
1132 : // Removes leaf tree nodes from the dominator tree.
1133 15077998 : static void EraseNode(DomTreeT &DT, const TreeNodePtr TN) {
1134 11907823 : assert(TN);
1135 11907823 : assert(TN->getNumChildren() == 0 && "Not a tree leaf");
1136 :
1137 : const TreeNodePtr IDom = TN->getIDom();
1138 11907823 : assert(IDom);
1139 27603649 :
1140 15695826 : auto ChIt = llvm::find(IDom->Children, TN);
1141 0 : assert(ChIt != IDom->Children.end());
1142 0 : std::swap(*ChIt, IDom->Children.back());
1143 15695826 : IDom->Children.pop_back();
1144 0 :
1145 1687325 : DT.DomTreeNodes.erase(TN->getBlock());
1146 0 : }
1147 :
1148 15695826 : //~~
1149 15695826 : //===--------------------- DomTree Batch Updater --------------------------===
1150 : //~~
1151 0 :
1152 0 : static void ApplyUpdates(DomTreeT &DT, ArrayRef<UpdateT> Updates) {
1153 0 : const size_t NumUpdates = Updates.size();
1154 : if (NumUpdates == 0)
1155 : return;
1156 :
1157 15077998 : // Take the fast path for a single update and avoid running the batch update
1158 11907823 : // machinery.
1159 11907823 : if (NumUpdates == 1) {
1160 11907823 : const auto &Update = Updates.front();
1161 11907823 : if (Update.getKind() == UpdateKind::Insert)
1162 17795324 : DT.insertEdge(Update.getFrom(), Update.getTo());
1163 5887501 : else
1164 0 : DT.deleteEdge(Update.getFrom(), Update.getTo());
1165 11907823 :
1166 0 : return;
1167 3170175 : }
1168 154562 :
1169 309124 : BatchUpdateInfo BUI;
1170 : LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1171 732304 : cfg::LegalizeUpdates<NodePtr>(Updates, BUI.Updates, IsPostDom);
1172 577742 :
1173 577742 : const size_t NumLegalized = BUI.Updates.size();
1174 1155484 : BUI.FutureSuccessors.reserve(NumLegalized);
1175 0 : BUI.FuturePredecessors.reserve(NumLegalized);
1176 0 :
1177 : // Use the legalized future updates to initialize future successors and
1178 577742 : // predecessors. Note that these sets will only decrease size over time, as
1179 423180 : // the next CFG snapshots slowly approach the actual (current) CFG.
1180 423180 : for (UpdateT &U : BUI.Updates) {
1181 0 : BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1182 0 : BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1183 423180 : }
1184 786924 :
1185 363744 : LLVM_DEBUG(dbgs() << "About to apply " << NumLegalized << " updates\n");
1186 0 : LLVM_DEBUG(if (NumLegalized < 32) for (const auto &U
1187 0 : : reverse(BUI.Updates)) {
1188 363744 : dbgs() << "\t";
1189 0 : U.dump();
1190 156 : dbgs() << "\n";
1191 0 : });
1192 0 : LLVM_DEBUG(dbgs() << "\n");
1193 363744 :
1194 363744 : // If the DominatorTree was recalculated at some point, stop the batch
1195 : // updates. Full recalculations ignore batch updates and look at the actual
1196 0 : // CFG.
1197 : for (size_t i = 0; i < NumLegalized && !BUI.IsRecalculated; ++i)
1198 : ApplyNextUpdate(DT, BUI);
1199 : }
1200 0 :
1201 0 : static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
1202 577742 : assert(!BUI.Updates.empty() && "No updates to apply!");
1203 423180 : UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
1204 423180 : LLVM_DEBUG(dbgs() << "Applying update: ");
1205 423180 : LLVM_DEBUG(CurrentUpdate.dump(); dbgs() << "\n");
1206 423180 :
1207 532753 : // Move to the next snapshot of the CFG by removing the reverse-applied
1208 109573 : // current update. Since updates are performed in the same order they are
1209 : // legalized it's sufficient to pop the last item here.
1210 423180 : auto &FS = BUI.FutureSuccessors[CurrentUpdate.getFrom()];
1211 0 : assert(FS.back().getPointer() == CurrentUpdate.getTo() &&
1212 154562 : FS.back().getInt() == CurrentUpdate.getKind());
1213 3015613 : FS.pop_back();
1214 6031226 : if (FS.empty()) BUI.FutureSuccessors.erase(CurrentUpdate.getFrom());
1215 :
1216 17515869 : auto &FP = BUI.FuturePredecessors[CurrentUpdate.getTo()];
1217 14500256 : assert(FP.back().getPointer() == CurrentUpdate.getFrom() &&
1218 14500256 : FP.back().getInt() == CurrentUpdate.getKind());
1219 29000512 : FP.pop_back();
1220 : if (FP.empty()) BUI.FuturePredecessors.erase(CurrentUpdate.getTo());
1221 :
1222 : if (CurrentUpdate.getKind() == UpdateKind::Insert)
1223 14500256 : InsertEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1224 11484643 : else
1225 11484643 : DeleteEdge(DT, &BUI, CurrentUpdate.getFrom(), CurrentUpdate.getTo());
1226 : }
1227 :
1228 11484643 : //~~
1229 26816725 : //===--------------- DomTree correctness verification ---------------------===
1230 15332082 : //~~
1231 0 :
1232 0 : // Check if the tree has correct roots. A DominatorTree always has a single
1233 15332082 : // root which is the function's entry node. A PostDominatorTree can have
1234 : // multiple roots - one for each node with no successors and for infinite
1235 1687169 : // loops.
1236 0 : // Running time: O(N).
1237 : bool verifyRoots(const DomTreeT &DT) {
1238 15332082 : if (!DT.Parent && !DT.Roots.empty()) {
1239 15332082 : errs() << "Tree has no parent but has roots!\n";
1240 : errs().flush();
1241 0 : return false;
1242 : }
1243 0 :
1244 : if (!IsPostDom) {
1245 0 : if (DT.Roots.empty()) {
1246 : errs() << "Tree doesn't have a root!\n";
1247 14500256 : errs().flush();
1248 11484643 : return false;
1249 11484643 : }
1250 11484643 :
1251 11484643 : if (DT.getRoot() != GetEntryNode(DT)) {
1252 17262571 : errs() << "Tree's root is not its parent's entry node!\n";
1253 5777928 : errs().flush();
1254 : return false;
1255 11484643 : }
1256 0 : }
1257 3015613 :
1258 0 : RootsT ComputedRoots = FindRoots(DT, nullptr);
1259 0 : if (DT.Roots.size() != ComputedRoots.size() ||
1260 0 : !std::is_permutation(DT.Roots.begin(), DT.Roots.end(),
1261 0 : ComputedRoots.begin())) {
1262 : errs() << "Tree has different roots than freshly computed ones!\n";
1263 : errs() << "\tPDT roots: ";
1264 313569 : for (const NodePtr N : DT.Roots) errs() << BlockNamePrinter(N) << ", ";
1265 0 : errs() << "\n\tComputed roots: ";
1266 0 : for (const NodePtr N : ComputedRoots)
1267 0 : errs() << BlockNamePrinter(N) << ", ";
1268 313569 : errs() << "\n";
1269 313569 : errs().flush();
1270 313569 : return false;
1271 0 : }
1272 313569 :
1273 313569 : return true;
1274 : }
1275 :
1276 : // Checks if the tree contains all reachable nodes in the input graph.
1277 : // Running time: O(N).
1278 428170 : bool verifyReachability(const DomTreeT &DT) {
1279 : clear();
1280 428170 : doFullDFSWalk(DT, AlwaysDescend);
1281 :
1282 : for (auto &NodeToTN : DT.DomTreeNodes) {
1283 0 : const TreeNodePtr TN = NodeToTN.second.get();
1284 : const NodePtr BB = TN->getBlock();
1285 0 :
1286 0 : // Virtual root has a corresponding virtual CFG node.
1287 : if (DT.isVirtualRoot(TN)) continue;
1288 :
1289 0 : if (NodeToInfo.count(BB) == 0) {
1290 : errs() << "DomTree node " << BlockNamePrinter(BB)
1291 154900 : << " not found by DFS walk!\n";
1292 : errs().flush();
1293 0 :
1294 : return false;
1295 : }
1296 0 : }
1297 5955124 :
1298 : for (const NodePtr N : NumToNode) {
1299 : if (N && !DT.getNode(N)) {
1300 0 : errs() << "CFG node " << BlockNamePrinter(N)
1301 309800 : << " not found in the DomTree!\n";
1302 : errs().flush();
1303 0 :
1304 154900 : return false;
1305 : }
1306 : }
1307 0 :
1308 0 : return true;
1309 0 : }
1310 0 :
1311 : // Check if for every parent with a level L in the tree all of its children
1312 0 : // have level L + 1.
1313 : // Running time: O(N).
1314 : static bool VerifyLevels(const DomTreeT &DT) {
1315 0 : for (auto &NodeToTN : DT.DomTreeNodes) {
1316 0 : const TreeNodePtr TN = NodeToTN.second.get();
1317 581730 : const NodePtr BB = TN->getBlock();
1318 426830 : if (!BB) continue;
1319 0 :
1320 426830 : const TreeNodePtr IDom = TN->getIDom();
1321 187559 : if (!IDom && TN->getLevel() != 0) {
1322 : errs() << "Node without an IDom " << BlockNamePrinter(BB)
1323 187559 : << " has a nonzero level " << TN->getLevel() << "!\n";
1324 : errs().flush();
1325 :
1326 0 : return false;
1327 : }
1328 0 :
1329 : if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
1330 : errs() << "Node " << BlockNamePrinter(BB) << " has level "
1331 : << TN->getLevel() << " while its IDom "
1332 : << BlockNamePrinter(IDom->getBlock()) << " has level "
1333 0 : << IDom->getLevel() << "!\n";
1334 : errs().flush();
1335 0 :
1336 0 : return false;
1337 : }
1338 0 : }
1339 154900 :
1340 : return true;
1341 : }
1342 :
1343 0 : // Check if the computed DFS numbers are correct. Note that DFS info may not
1344 0 : // be valid, and when that is the case, we don't verify the numbers.
1345 0 : // Running time: O(N log(N)).
1346 0 : static bool VerifyDFSNumbers(const DomTreeT &DT) {
1347 : if (!DT.DFSInfoValid || !DT.Parent)
1348 : return true;
1349 2537 :
1350 1800 : const NodePtr RootBB = IsPostDom ? nullptr : DT.getRoots()[0];
1351 0 : const TreeNodePtr Root = DT.getNode(RootBB);
1352 0 :
1353 : auto PrintNodeAndDFSNums = [](const TreeNodePtr TN) {
1354 0 : errs() << BlockNamePrinter(TN) << " {" << TN->getDFSNumIn() << ", "
1355 0 : << TN->getDFSNumOut() << '}';
1356 : };
1357 :
1358 0 : // Verify the root's DFS In number. Although DFS numbering would also work
1359 0 : // if we started from some other value, we assume 0-based numbering.
1360 0 : if (Root->getDFSNumIn() != 0) {
1361 0 : errs() << "DFSIn number for the tree root is not:\n\t";
1362 0 : PrintNodeAndDFSNums(Root);
1363 : errs() << '\n';
1364 0 : errs().flush();
1365 392 : return false;
1366 392 : }
1367 0 :
1368 : // For each tree node verify if children's DFS numbers cover their parent's
1369 0 : // DFS numbers with no gaps.
1370 392 : for (const auto &NodeToTN : DT.DomTreeNodes) {
1371 392 : const TreeNodePtr Node = NodeToTN.second.get();
1372 0 :
1373 : // Handle tree leaves.
1374 1482 : if (Node->getChildren().empty()) {
1375 1090 : if (Node->getDFSNumIn() + 1 != Node->getDFSNumOut()) {
1376 0 : errs() << "Tree leaf should have DFSOut = DFSIn + 1:\n\t";
1377 : PrintNodeAndDFSNums(Node);
1378 1090 : errs() << '\n';
1379 0 : errs().flush();
1380 0 : return false;
1381 : }
1382 :
1383 392 : continue;
1384 1431 : }
1385 0 :
1386 : // Make a copy and sort it such that it is possible to check if there are
1387 0 : // no gaps between DFS numbers of adjacent children.
1388 : SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
1389 : llvm::sort(Children, [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
1390 : return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
1391 : });
1392 0 :
1393 : auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
1394 : const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
1395 : assert(FirstCh);
1396 :
1397 : errs() << "Incorrect DFS numbers for:\n\tParent ";
1398 : PrintNodeAndDFSNums(Node);
1399 345 :
1400 0 : errs() << "\n\tChild ";
1401 : PrintNodeAndDFSNums(FirstCh);
1402 :
1403 : if (SecondCh) {
1404 : errs() << "\n\tSecond child ";
1405 : PrintNodeAndDFSNums(SecondCh);
1406 : }
1407 :
1408 0 : errs() << "\nAll children: ";
1409 154900 : for (const TreeNodePtr Ch : Children) {
1410 : PrintNodeAndDFSNums(Ch);
1411 : errs() << ", ";
1412 : }
1413 :
1414 : errs() << '\n';
1415 : errs().flush();
1416 0 : };
1417 :
1418 : if (Children.front()->getDFSNumIn() != Node->getDFSNumIn() + 1) {
1419 309800 : PrintChildrenError(Children.front(), nullptr);
1420 : return false;
1421 : }
1422 154900 :
1423 : if (Children.back()->getDFSNumOut() + 1 != Node->getDFSNumOut()) {
1424 : PrintChildrenError(Children.back(), nullptr);
1425 : return false;
1426 0 : }
1427 0 :
1428 : for (size_t i = 0, e = Children.size() - 1; i != e; ++i) {
1429 : if (Children[i]->getDFSNumOut() + 1 != Children[i + 1]->getDFSNumIn()) {
1430 : PrintChildrenError(Children[i], Children[i + 1]);
1431 : return false;
1432 : }
1433 : }
1434 0 : }
1435 581730 :
1436 426830 : return true;
1437 : }
1438 426830 :
1439 187559 : // The below routines verify the correctness of the dominator tree relative to
1440 : // the CFG it's coming from. A tree is a dominator tree iff it has two
1441 187559 : // properties, called the parent property and the sibling property. Tarjan
1442 : // and Lengauer prove (but don't explicitly name) the properties as part of
1443 : // the proofs in their 1972 paper, but the proofs are mostly part of proving
1444 : // things about semidominators and idoms, and some of them are simply asserted
1445 0 : // based on even earlier papers (see, e.g., lemma 2). Some papers refer to
1446 : // these properties as "valid" and "co-valid". See, e.g., "Dominators,
1447 : // directed bipolar orders, and independent spanning trees" by Loukas
1448 : // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
1449 0 : // and Vertex-Disjoint Paths " by the same authors.
1450 :
1451 0 : // A very simple and direct explanation of these properties can be found in
1452 0 : // "An Experimental Study of Dynamic Dominators", found at
1453 : // https://arxiv.org/abs/1604.02711
1454 :
1455 : // The easiest way to think of the parent property is that it's a requirement
1456 : // of being a dominator. Let's just take immediate dominators. For PARENT to
1457 154900 : // be an immediate dominator of CHILD, all paths in the CFG must go through
1458 0 : // PARENT before they hit CHILD. This implies that if you were to cut PARENT
1459 : // out of the CFG, there should be no paths to CHILD that are reachable. If
1460 : // there are, then you now have a path from PARENT to CHILD that goes around
1461 : // PARENT and still reaches CHILD, which by definition, means PARENT can't be
1462 0 : // a dominator of CHILD (let alone an immediate one).
1463 :
1464 : // The sibling property is similar. It says that for each pair of sibling
1465 : // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
1466 0 : // other. If sibling LEFT dominated sibling RIGHT, it means there are no
1467 2537 : // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
1468 1800 : // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
1469 : // RIGHT, not a sibling.
1470 :
1471 : // It is possible to verify the parent and sibling properties in
1472 : // linear time, but the algorithms are complex. Instead, we do it in a
1473 0 : // straightforward N^2 and N^3 way below, using direct path reachability.
1474 :
1475 : // Checks if the tree has the parent property: if for all edges from V to W in
1476 0 : // the input graph, such that V is reachable, the parent of W in the tree is
1477 : // an ancestor of V in the tree.
1478 : // Running time: O(N^2).
1479 : //
1480 0 : // This means that if a node gets disconnected from the graph, then all of
1481 : // the nodes it dominated previously will now become unreachable.
1482 : bool verifyParentProperty(const DomTreeT &DT) {
1483 392 : for (auto &NodeToTN : DT.DomTreeNodes) {
1484 392 : const TreeNodePtr TN = NodeToTN.second.get();
1485 : const NodePtr BB = TN->getBlock();
1486 0 : if (!BB || TN->getChildren().empty()) continue;
1487 0 :
1488 392 : LLVM_DEBUG(dbgs() << "Verifying parent property of node "
1489 392 : << BlockNamePrinter(TN) << "\n");
1490 : clear();
1491 0 : doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
1492 1482 : return From != BB && To != BB;
1493 1090 : });
1494 :
1495 0 : for (TreeNodePtr Child : TN->getChildren())
1496 1090 : if (NodeToInfo.count(Child->getBlock()) != 0) {
1497 : errs() << "Child " << BlockNamePrinter(Child)
1498 : << " reachable after its parent " << BlockNamePrinter(BB)
1499 : << " is removed!\n";
1500 : errs().flush();
1501 392 :
1502 1431 : return false;
1503 0 : }
1504 0 : }
1505 0 :
1506 0 : return true;
1507 : }
1508 :
1509 : // Check if the tree has sibling property: if a node V does not dominate a
1510 0 : // node W for all siblings V and W in the tree.
1511 0 : // Running time: O(N^3).
1512 0 : //
1513 0 : // This means that if a node gets disconnected from the graph, then all of its
1514 : // siblings will now still be reachable.
1515 0 : bool verifySiblingProperty(const DomTreeT &DT) {
1516 : for (auto &NodeToTN : DT.DomTreeNodes) {
1517 345 : const TreeNodePtr TN = NodeToTN.second.get();
1518 0 : const NodePtr BB = TN->getBlock();
1519 0 : if (!BB || TN->getChildren().empty()) continue;
1520 0 :
1521 : const auto &Siblings = TN->getChildren();
1522 0 : for (const TreeNodePtr N : Siblings) {
1523 : clear();
1524 0 : NodePtr BBN = N->getBlock();
1525 0 : doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
1526 0 : return From != BBN && To != BBN;
1527 0 : });
1528 :
1529 0 : for (const TreeNodePtr S : Siblings) {
1530 : if (S == N) continue;
1531 0 :
1532 0 : if (NodeToInfo.count(S->getBlock()) == 0) {
1533 0 : errs() << "Node " << BlockNamePrinter(S)
1534 : << " not reachable when its sibling " << BlockNamePrinter(N)
1535 : << " is removed!\n";
1536 : errs().flush();
1537 :
1538 0 : return false;
1539 0 : }
1540 0 : }
1541 : }
1542 : }
1543 :
1544 : return true;
1545 : }
1546 :
1547 : // Check if the given tree is the same as a freshly computed one for the same
1548 0 : // Parent.
1549 0 : // Running time: O(N^2), but faster in practise (same as tree construction).
1550 : //
1551 : // Note that this does not check if that the tree construction algorithm is
1552 0 : // correct and should be only used for fast (but possibly unsound)
1553 : // verification.
1554 : static bool IsSameAsFreshTree(const DomTreeT &DT) {
1555 0 : DomTreeT FreshTree;
1556 0 : FreshTree.recalculate(*DT.Parent);
1557 : const bool Different = DT.compare(FreshTree);
1558 :
1559 0 : if (Different) {
1560 : errs() << (DT.isPostDominator() ? "Post" : "")
1561 0 : << "DominatorTree is different than a freshly computed one!\n"
1562 : << "\tCurrent:\n";
1563 : DT.print(errs());
1564 : errs() << "\n\tFreshly computed tree:\n";
1565 0 : FreshTree.print(errs());
1566 : errs().flush();
1567 0 : }
1568 0 :
1569 : return !Different;
1570 : }
1571 0 : };
1572 0 :
1573 0 : template <class DomTreeT>
1574 7 : void Calculate(DomTreeT &DT) {
1575 186927 : SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, nullptr);
1576 7 : }
1577 0 :
1578 0 : template <typename DomTreeT>
1579 : void CalculateWithUpdates(DomTreeT &DT,
1580 0 : ArrayRef<typename DomTreeT::UpdateType> Updates) {
1581 0 : // TODO: Move BUI creation in common method, reuse in ApplyUpdates.
1582 : typename SemiNCAInfo<DomTreeT>::BatchUpdateInfo BUI;
1583 0 : LLVM_DEBUG(dbgs() << "Legalizing " << BUI.Updates.size() << " updates\n");
1584 0 : cfg::LegalizeUpdates<typename DomTreeT::NodePtr>(Updates, BUI.Updates,
1585 : DomTreeT::IsPostDominator);
1586 : const size_t NumLegalized = BUI.Updates.size();
1587 : BUI.FutureSuccessors.reserve(NumLegalized);
1588 0 : BUI.FuturePredecessors.reserve(NumLegalized);
1589 0 : for (auto &U : BUI.Updates) {
1590 0 : BUI.FutureSuccessors[U.getFrom()].push_back({U.getTo(), U.getKind()});
1591 0 : BUI.FuturePredecessors[U.getTo()].push_back({U.getFrom(), U.getKind()});
1592 0 : }
1593 :
1594 : SemiNCAInfo<DomTreeT>::CalculateFromScratch(DT, &BUI);
1595 0 : }
1596 0 :
1597 0 : template <class DomTreeT>
1598 0 : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1599 0 : typename DomTreeT::NodePtr To) {
1600 : if (DT.isPostDominator()) std::swap(From, To);
1601 : SemiNCAInfo<DomTreeT>::InsertEdge(DT, nullptr, From, To);
1602 : }
1603 0 :
1604 0 : template <class DomTreeT>
1605 0 : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
1606 0 : typename DomTreeT::NodePtr To) {
1607 : if (DT.isPostDominator()) std::swap(From, To);
1608 : SemiNCAInfo<DomTreeT>::DeleteEdge(DT, nullptr, From, To);
1609 0 : }
1610 0 :
1611 0 : template <class DomTreeT>
1612 0 : void ApplyUpdates(DomTreeT &DT,
1613 0 : ArrayRef<typename DomTreeT::UpdateType> Updates) {
1614 0 : SemiNCAInfo<DomTreeT>::ApplyUpdates(DT, Updates);
1615 0 : }
1616 0 :
1617 0 : template <class DomTreeT>
1618 0 : bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL) {
1619 0 : SemiNCAInfo<DomTreeT> SNCA(nullptr);
1620 0 :
1621 0 : // Simplist check is to compare against a new tree. This will also
1622 0 : // usefully print the old and new trees, if they are different.
1623 0 : if (!SNCA.IsSameAsFreshTree(DT))
1624 0 : return false;
1625 0 :
1626 0 : // Common checks to verify the properties of the tree. O(N log N) at worst
1627 0 : if (!SNCA.verifyRoots(DT) || !SNCA.verifyReachability(DT) ||
1628 0 : !SNCA.VerifyLevels(DT) || !SNCA.VerifyDFSNumbers(DT))
1629 0 : return false;
1630 0 :
1631 0 : // Extra checks depending on VerificationLevel. Up to O(N^3)
1632 : if (VL == DomTreeT::VerificationLevel::Basic ||
1633 0 : VL == DomTreeT::VerificationLevel::Full)
1634 : if (!SNCA.verifyParentProperty(DT))
1635 0 : return false;
1636 0 : if (VL == DomTreeT::VerificationLevel::Full)
1637 0 : if (!SNCA.verifySiblingProperty(DT))
1638 : return false;
1639 :
1640 0 : return true;
1641 0 : }
1642 0 :
1643 0 : } // namespace DomTreeBuilder
1644 : } // namespace llvm
1645 0 :
1646 : #undef DEBUG_TYPE
1647 0 :
1648 0 : #endif
|
