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