1 | //===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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 | /// This file defines a set of templates that efficiently compute a dominator |
11 | /// tree over a generic graph. This is used typically in LLVM for fast |
12 | /// dominance queries on the CFG, but is fully generic w.r.t. the underlying |
13 | /// graph types. |
14 | /// |
15 | /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements |
16 | /// on the graph's NodeRef. The NodeRef should be a pointer and, |
17 | /// either NodeRef->getParent() must return the parent node that is also a |
18 | /// pointer or DomTreeNodeTraits needs to be specialized. |
19 | /// |
20 | /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits. |
21 | /// |
22 | //===----------------------------------------------------------------------===// |
23 | |
24 | #ifndef LLVM_SUPPORT_GENERICDOMTREE_H |
25 | #define LLVM_SUPPORT_GENERICDOMTREE_H |
26 | |
27 | #include "llvm/ADT/DenseMap.h" |
28 | #include "llvm/ADT/GraphTraits.h" |
29 | #include "llvm/ADT/STLExtras.h" |
30 | #include "llvm/ADT/SmallPtrSet.h" |
31 | #include "llvm/ADT/SmallVector.h" |
32 | #include "llvm/Support/CFGDiff.h" |
33 | #include "llvm/Support/CFGUpdate.h" |
34 | #include "llvm/Support/raw_ostream.h" |
35 | #include <algorithm> |
36 | #include <cassert> |
37 | #include <cstddef> |
38 | #include <iterator> |
39 | #include <memory> |
40 | #include <type_traits> |
41 | #include <utility> |
42 | |
43 | namespace llvm { |
44 | |
45 | template <typename NodeT, bool IsPostDom> |
46 | class DominatorTreeBase; |
47 | |
48 | namespace DomTreeBuilder { |
49 | template <typename DomTreeT> |
50 | struct SemiNCAInfo; |
51 | } // namespace DomTreeBuilder |
52 | |
53 | /// Base class for the actual dominator tree node. |
54 | template <class NodeT> class DomTreeNodeBase { |
55 | friend class PostDominatorTree; |
56 | friend class DominatorTreeBase<NodeT, false>; |
57 | friend class DominatorTreeBase<NodeT, true>; |
58 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>; |
59 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>; |
60 | |
61 | NodeT *TheBB; |
62 | DomTreeNodeBase *IDom; |
63 | unsigned Level; |
64 | SmallVector<DomTreeNodeBase *, 4> Children; |
65 | mutable unsigned DFSNumIn = ~0; |
66 | mutable unsigned DFSNumOut = ~0; |
67 | |
68 | public: |
69 | DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) |
70 | : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} |
71 | |
72 | using iterator = typename SmallVector<DomTreeNodeBase *, 4>::iterator; |
73 | using const_iterator = |
74 | typename SmallVector<DomTreeNodeBase *, 4>::const_iterator; |
75 | |
76 | iterator begin() { return Children.begin(); } |
77 | iterator end() { return Children.end(); } |
78 | const_iterator begin() const { return Children.begin(); } |
79 | const_iterator end() const { return Children.end(); } |
80 | |
81 | DomTreeNodeBase *const &back() const { return Children.back(); } |
82 | DomTreeNodeBase *&back() { return Children.back(); } |
83 | |
84 | iterator_range<iterator> children() { return make_range(begin(), end()); } |
85 | iterator_range<const_iterator> children() const { |
86 | return make_range(begin(), end()); |
87 | } |
88 | |
89 | NodeT *getBlock() const { return TheBB; } |
90 | DomTreeNodeBase *getIDom() const { return IDom; } |
91 | unsigned getLevel() const { return Level; } |
92 | |
93 | std::unique_ptr<DomTreeNodeBase> addChild( |
94 | std::unique_ptr<DomTreeNodeBase> C) { |
95 | Children.push_back(C.get()); |
96 | return C; |
97 | } |
98 | |
99 | bool isLeaf() const { return Children.empty(); } |
100 | size_t getNumChildren() const { return Children.size(); } |
101 | |
102 | void clearAllChildren() { Children.clear(); } |
103 | |
104 | bool compare(const DomTreeNodeBase *Other) const { |
105 | if (getNumChildren() != Other->getNumChildren()) |
106 | return true; |
107 | |
108 | if (Level != Other->Level) return true; |
109 | |
110 | SmallPtrSet<const NodeT *, 4> OtherChildren; |
111 | for (const DomTreeNodeBase *I : *Other) { |
112 | const NodeT *Nd = I->getBlock(); |
113 | OtherChildren.insert(Nd); |
114 | } |
115 | |
116 | for (const DomTreeNodeBase *I : *this) { |
117 | const NodeT *N = I->getBlock(); |
118 | if (OtherChildren.count(N) == 0) |
119 | return true; |
120 | } |
121 | return false; |
122 | } |
123 | |
124 | void setIDom(DomTreeNodeBase *NewIDom) { |
125 | assert(IDom && "No immediate dominator?" ); |
126 | if (IDom == NewIDom) return; |
127 | |
128 | auto I = find(IDom->Children, this); |
129 | assert(I != IDom->Children.end() && |
130 | "Not in immediate dominator children set!" ); |
131 | // I am no longer your child... |
132 | IDom->Children.erase(I); |
133 | |
134 | // Switch to new dominator |
135 | IDom = NewIDom; |
136 | IDom->Children.push_back(this); |
137 | |
138 | UpdateLevel(); |
139 | } |
140 | |
141 | /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes |
142 | /// in the dominator tree. They are only guaranteed valid if |
143 | /// updateDFSNumbers() has been called. |
144 | unsigned getDFSNumIn() const { return DFSNumIn; } |
145 | unsigned getDFSNumOut() const { return DFSNumOut; } |
146 | |
147 | private: |
148 | // Return true if this node is dominated by other. Use this only if DFS info |
149 | // is valid. |
150 | bool DominatedBy(const DomTreeNodeBase *other) const { |
151 | return this->DFSNumIn >= other->DFSNumIn && |
152 | this->DFSNumOut <= other->DFSNumOut; |
153 | } |
154 | |
155 | void UpdateLevel() { |
156 | assert(IDom); |
157 | if (Level == IDom->Level + 1) return; |
158 | |
159 | SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; |
160 | |
161 | while (!WorkStack.empty()) { |
162 | DomTreeNodeBase *Current = WorkStack.pop_back_val(); |
163 | Current->Level = Current->IDom->Level + 1; |
164 | |
165 | for (DomTreeNodeBase *C : *Current) { |
166 | assert(C->IDom); |
167 | if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); |
168 | } |
169 | } |
170 | } |
171 | }; |
172 | |
173 | template <class NodeT> |
174 | raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { |
175 | if (Node->getBlock()) |
176 | Node->getBlock()->printAsOperand(O, false); |
177 | else |
178 | O << " <<exit node>>" ; |
179 | |
180 | O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" |
181 | << Node->getLevel() << "]\n" ; |
182 | |
183 | return O; |
184 | } |
185 | |
186 | template <class NodeT> |
187 | void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, |
188 | unsigned Lev) { |
189 | O.indent(NumSpaces: 2 * Lev) << "[" << Lev << "] " << N; |
190 | for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), |
191 | E = N->end(); |
192 | I != E; ++I) |
193 | PrintDomTree<NodeT>(*I, O, Lev + 1); |
194 | } |
195 | |
196 | namespace DomTreeBuilder { |
197 | // The routines below are provided in a separate header but referenced here. |
198 | template <typename DomTreeT> |
199 | void Calculate(DomTreeT &DT); |
200 | |
201 | template <typename DomTreeT> |
202 | void CalculateWithUpdates(DomTreeT &DT, |
203 | ArrayRef<typename DomTreeT::UpdateType> Updates); |
204 | |
205 | template <typename DomTreeT> |
206 | void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, |
207 | typename DomTreeT::NodePtr To); |
208 | |
209 | template <typename DomTreeT> |
210 | void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, |
211 | typename DomTreeT::NodePtr To); |
212 | |
213 | template <typename DomTreeT> |
214 | void ApplyUpdates(DomTreeT &DT, |
215 | GraphDiff<typename DomTreeT::NodePtr, |
216 | DomTreeT::IsPostDominator> &PreViewCFG, |
217 | GraphDiff<typename DomTreeT::NodePtr, |
218 | DomTreeT::IsPostDominator> *PostViewCFG); |
219 | |
220 | template <typename DomTreeT> |
221 | bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL); |
222 | } // namespace DomTreeBuilder |
223 | |
224 | /// Default DomTreeNode traits for NodeT. The default implementation assume a |
225 | /// Function-like NodeT. Can be specialized to support different node types. |
226 | template <typename NodeT> struct DomTreeNodeTraits { |
227 | using NodeType = NodeT; |
228 | using NodePtr = NodeT *; |
229 | using ParentPtr = decltype(std::declval<NodePtr>()->getParent()); |
230 | static_assert(std::is_pointer_v<ParentPtr>, |
231 | "Currently NodeT's parent must be a pointer type" ); |
232 | using ParentType = std::remove_pointer_t<ParentPtr>; |
233 | |
234 | static NodeT *getEntryNode(ParentPtr Parent) { return &Parent->front(); } |
235 | static ParentPtr getParent(NodePtr BB) { return BB->getParent(); } |
236 | }; |
237 | |
238 | /// Core dominator tree base class. |
239 | /// |
240 | /// This class is a generic template over graph nodes. It is instantiated for |
241 | /// various graphs in the LLVM IR or in the code generator. |
242 | template <typename NodeT, bool IsPostDom> |
243 | class DominatorTreeBase { |
244 | public: |
245 | static_assert(std::is_pointer_v<typename GraphTraits<NodeT *>::NodeRef>, |
246 | "Currently DominatorTreeBase supports only pointer nodes" ); |
247 | using NodeTrait = DomTreeNodeTraits<NodeT>; |
248 | using NodeType = typename NodeTrait::NodeType; |
249 | using NodePtr = typename NodeTrait::NodePtr; |
250 | using ParentPtr = typename NodeTrait::ParentPtr; |
251 | static_assert(std::is_pointer_v<ParentPtr>, |
252 | "Currently NodeT's parent must be a pointer type" ); |
253 | using ParentType = std::remove_pointer_t<ParentPtr>; |
254 | static constexpr bool IsPostDominator = IsPostDom; |
255 | |
256 | using UpdateType = cfg::Update<NodePtr>; |
257 | using UpdateKind = cfg::UpdateKind; |
258 | static constexpr UpdateKind Insert = UpdateKind::Insert; |
259 | static constexpr UpdateKind Delete = UpdateKind::Delete; |
260 | |
261 | enum class VerificationLevel { Fast, Basic, Full }; |
262 | |
263 | protected: |
264 | // Dominators always have a single root, postdominators can have more. |
265 | SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots; |
266 | |
267 | using DomTreeNodeMapType = |
268 | DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; |
269 | DomTreeNodeMapType DomTreeNodes; |
270 | DomTreeNodeBase<NodeT> *RootNode = nullptr; |
271 | ParentPtr Parent = nullptr; |
272 | |
273 | mutable bool DFSInfoValid = false; |
274 | mutable unsigned int SlowQueries = 0; |
275 | |
276 | friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>; |
277 | |
278 | public: |
279 | DominatorTreeBase() = default; |
280 | |
281 | DominatorTreeBase(DominatorTreeBase &&Arg) |
282 | : Roots(std::move(Arg.Roots)), |
283 | DomTreeNodes(std::move(Arg.DomTreeNodes)), |
284 | RootNode(Arg.RootNode), |
285 | Parent(Arg.Parent), |
286 | DFSInfoValid(Arg.DFSInfoValid), |
287 | SlowQueries(Arg.SlowQueries) { |
288 | Arg.wipe(); |
289 | } |
290 | |
291 | DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { |
292 | Roots = std::move(RHS.Roots); |
293 | DomTreeNodes = std::move(RHS.DomTreeNodes); |
294 | RootNode = RHS.RootNode; |
295 | Parent = RHS.Parent; |
296 | DFSInfoValid = RHS.DFSInfoValid; |
297 | SlowQueries = RHS.SlowQueries; |
298 | RHS.wipe(); |
299 | return *this; |
300 | } |
301 | |
302 | DominatorTreeBase(const DominatorTreeBase &) = delete; |
303 | DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; |
304 | |
305 | /// Iteration over roots. |
306 | /// |
307 | /// This may include multiple blocks if we are computing post dominators. |
308 | /// For forward dominators, this will always be a single block (the entry |
309 | /// block). |
310 | using root_iterator = typename SmallVectorImpl<NodeT *>::iterator; |
311 | using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator; |
312 | |
313 | root_iterator root_begin() { return Roots.begin(); } |
314 | const_root_iterator root_begin() const { return Roots.begin(); } |
315 | root_iterator root_end() { return Roots.end(); } |
316 | const_root_iterator root_end() const { return Roots.end(); } |
317 | |
318 | size_t root_size() const { return Roots.size(); } |
319 | |
320 | iterator_range<root_iterator> roots() { |
321 | return make_range(root_begin(), root_end()); |
322 | } |
323 | iterator_range<const_root_iterator> roots() const { |
324 | return make_range(root_begin(), root_end()); |
325 | } |
326 | |
327 | /// isPostDominator - Returns true if analysis based of postdoms |
328 | /// |
329 | bool isPostDominator() const { return IsPostDominator; } |
330 | |
331 | /// compare - Return false if the other dominator tree base matches this |
332 | /// dominator tree base. Otherwise return true. |
333 | bool compare(const DominatorTreeBase &Other) const { |
334 | if (Parent != Other.Parent) return true; |
335 | |
336 | if (Roots.size() != Other.Roots.size()) |
337 | return true; |
338 | |
339 | if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin())) |
340 | return true; |
341 | |
342 | const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; |
343 | if (DomTreeNodes.size() != OtherDomTreeNodes.size()) |
344 | return true; |
345 | |
346 | for (const auto &DomTreeNode : DomTreeNodes) { |
347 | NodeT *BB = DomTreeNode.first; |
348 | typename DomTreeNodeMapType::const_iterator OI = |
349 | OtherDomTreeNodes.find(BB); |
350 | if (OI == OtherDomTreeNodes.end()) |
351 | return true; |
352 | |
353 | DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second; |
354 | DomTreeNodeBase<NodeT> &OtherNd = *OI->second; |
355 | |
356 | if (MyNd.compare(&OtherNd)) |
357 | return true; |
358 | } |
359 | |
360 | return false; |
361 | } |
362 | |
363 | /// getNode - return the (Post)DominatorTree node for the specified basic |
364 | /// block. This is the same as using operator[] on this class. The result |
365 | /// may (but is not required to) be null for a forward (backwards) |
366 | /// statically unreachable block. |
367 | DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const { |
368 | auto I = DomTreeNodes.find(BB); |
369 | if (I != DomTreeNodes.end()) |
370 | return I->second.get(); |
371 | return nullptr; |
372 | } |
373 | |
374 | /// See getNode. |
375 | DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const { |
376 | return getNode(BB); |
377 | } |
378 | |
379 | /// getRootNode - This returns the entry node for the CFG of the function. If |
380 | /// this tree represents the post-dominance relations for a function, however, |
381 | /// this root may be a node with the block == NULL. This is the case when |
382 | /// there are multiple exit nodes from a particular function. Consumers of |
383 | /// post-dominance information must be capable of dealing with this |
384 | /// possibility. |
385 | /// |
386 | DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } |
387 | const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } |
388 | |
389 | /// Get all nodes dominated by R, including R itself. |
390 | void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { |
391 | Result.clear(); |
392 | const DomTreeNodeBase<NodeT> *RN = getNode(BB: R); |
393 | if (!RN) |
394 | return; // If R is unreachable, it will not be present in the DOM tree. |
395 | SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; |
396 | WL.push_back(RN); |
397 | |
398 | while (!WL.empty()) { |
399 | const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); |
400 | Result.push_back(N->getBlock()); |
401 | WL.append(N->begin(), N->end()); |
402 | } |
403 | } |
404 | |
405 | /// properlyDominates - Returns true iff A dominates B and A != B. |
406 | /// Note that this is not a constant time operation! |
407 | /// |
408 | bool properlyDominates(const DomTreeNodeBase<NodeT> *A, |
409 | const DomTreeNodeBase<NodeT> *B) const { |
410 | if (!A || !B) |
411 | return false; |
412 | if (A == B) |
413 | return false; |
414 | return dominates(A, B); |
415 | } |
416 | |
417 | bool properlyDominates(const NodeT *A, const NodeT *B) const; |
418 | |
419 | /// isReachableFromEntry - Return true if A is dominated by the entry |
420 | /// block of the function containing it. |
421 | bool isReachableFromEntry(const NodeT *A) const { |
422 | assert(!this->isPostDominator() && |
423 | "This is not implemented for post dominators" ); |
424 | return isReachableFromEntry(getNode(BB: const_cast<NodeT *>(A))); |
425 | } |
426 | |
427 | bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; } |
428 | |
429 | /// dominates - Returns true iff A dominates B. Note that this is not a |
430 | /// constant time operation! |
431 | /// |
432 | bool dominates(const DomTreeNodeBase<NodeT> *A, |
433 | const DomTreeNodeBase<NodeT> *B) const { |
434 | // A node trivially dominates itself. |
435 | if (B == A) |
436 | return true; |
437 | |
438 | // An unreachable node is dominated by anything. |
439 | if (!isReachableFromEntry(B)) |
440 | return true; |
441 | |
442 | // And dominates nothing. |
443 | if (!isReachableFromEntry(A)) |
444 | return false; |
445 | |
446 | if (B->getIDom() == A) return true; |
447 | |
448 | if (A->getIDom() == B) return false; |
449 | |
450 | // A can only dominate B if it is higher in the tree. |
451 | if (A->getLevel() >= B->getLevel()) return false; |
452 | |
453 | // Compare the result of the tree walk and the dfs numbers, if expensive |
454 | // checks are enabled. |
455 | #ifdef EXPENSIVE_CHECKS |
456 | assert((!DFSInfoValid || |
457 | (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && |
458 | "Tree walk disagrees with dfs numbers!" ); |
459 | #endif |
460 | |
461 | if (DFSInfoValid) |
462 | return B->DominatedBy(A); |
463 | |
464 | // If we end up with too many slow queries, just update the |
465 | // DFS numbers on the theory that we are going to keep querying. |
466 | SlowQueries++; |
467 | if (SlowQueries > 32) { |
468 | updateDFSNumbers(); |
469 | return B->DominatedBy(A); |
470 | } |
471 | |
472 | return dominatedBySlowTreeWalk(A, B); |
473 | } |
474 | |
475 | bool dominates(const NodeT *A, const NodeT *B) const; |
476 | |
477 | NodeT *getRoot() const { |
478 | assert(this->Roots.size() == 1 && "Should always have entry node!" ); |
479 | return this->Roots[0]; |
480 | } |
481 | |
482 | /// Find nearest common dominator basic block for basic block A and B. A and B |
483 | /// must have tree nodes. |
484 | NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { |
485 | assert(A && B && "Pointers are not valid" ); |
486 | assert(NodeTrait::getParent(A) == NodeTrait::getParent(B) && |
487 | "Two blocks are not in same function" ); |
488 | |
489 | // If either A or B is a entry block then it is nearest common dominator |
490 | // (for forward-dominators). |
491 | if (!isPostDominator()) { |
492 | NodeT &Entry = |
493 | *DomTreeNodeTraits<NodeT>::getEntryNode(NodeTrait::getParent(A)); |
494 | if (A == &Entry || B == &Entry) |
495 | return &Entry; |
496 | } |
497 | |
498 | DomTreeNodeBase<NodeT> *NodeA = getNode(BB: A); |
499 | DomTreeNodeBase<NodeT> *NodeB = getNode(BB: B); |
500 | assert(NodeA && "A must be in the tree" ); |
501 | assert(NodeB && "B must be in the tree" ); |
502 | |
503 | // Use level information to go up the tree until the levels match. Then |
504 | // continue going up til we arrive at the same node. |
505 | while (NodeA != NodeB) { |
506 | if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); |
507 | |
508 | NodeA = NodeA->IDom; |
509 | } |
510 | |
511 | return NodeA->getBlock(); |
512 | } |
513 | |
514 | const NodeT *findNearestCommonDominator(const NodeT *A, |
515 | const NodeT *B) const { |
516 | // Cast away the const qualifiers here. This is ok since |
517 | // const is re-introduced on the return type. |
518 | return findNearestCommonDominator(const_cast<NodeT *>(A), |
519 | const_cast<NodeT *>(B)); |
520 | } |
521 | |
522 | bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const { |
523 | return isPostDominator() && !A->getBlock(); |
524 | } |
525 | |
526 | //===--------------------------------------------------------------------===// |
527 | // API to update (Post)DominatorTree information based on modifications to |
528 | // the CFG... |
529 | |
530 | /// Inform the dominator tree about a sequence of CFG edge insertions and |
531 | /// deletions and perform a batch update on the tree. |
532 | /// |
533 | /// This function should be used when there were multiple CFG updates after |
534 | /// the last dominator tree update. It takes care of performing the updates |
535 | /// in sync with the CFG and optimizes away the redundant operations that |
536 | /// cancel each other. |
537 | /// The functions expects the sequence of updates to be balanced. Eg.: |
538 | /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because |
539 | /// logically it results in a single insertions. |
540 | /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make |
541 | /// sense to insert the same edge twice. |
542 | /// |
543 | /// What's more, the functions assumes that it's safe to ask every node in the |
544 | /// CFG about its children and inverse children. This implies that deletions |
545 | /// of CFG edges must not delete the CFG nodes before calling this function. |
546 | /// |
547 | /// The applyUpdates function can reorder the updates and remove redundant |
548 | /// ones internally (as long as it is done in a deterministic fashion). The |
549 | /// batch updater is also able to detect sequences of zero and exactly one |
550 | /// update -- it's optimized to do less work in these cases. |
551 | /// |
552 | /// Note that for postdominators it automatically takes care of applying |
553 | /// updates on reverse edges internally (so there's no need to swap the |
554 | /// From and To pointers when constructing DominatorTree::UpdateType). |
555 | /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T> |
556 | /// with the same template parameter T. |
557 | /// |
558 | /// \param Updates An ordered sequence of updates to perform. The current CFG |
559 | /// and the reverse of these updates provides the pre-view of the CFG. |
560 | /// |
561 | void applyUpdates(ArrayRef<UpdateType> Updates) { |
562 | GraphDiff<NodePtr, IsPostDominator> PreViewCFG( |
563 | Updates, /*ReverseApplyUpdates=*/true); |
564 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr); |
565 | } |
566 | |
567 | /// \param Updates An ordered sequence of updates to perform. The current CFG |
568 | /// and the reverse of these updates provides the pre-view of the CFG. |
569 | /// \param PostViewUpdates An ordered sequence of update to perform in order |
570 | /// to obtain a post-view of the CFG. The DT will be updated assuming the |
571 | /// obtained PostViewCFG is the desired end state. |
572 | void applyUpdates(ArrayRef<UpdateType> Updates, |
573 | ArrayRef<UpdateType> PostViewUpdates) { |
574 | if (Updates.empty()) { |
575 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); |
576 | DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG); |
577 | } else { |
578 | // PreViewCFG needs to merge Updates and PostViewCFG. The updates in |
579 | // Updates need to be reversed, and match the direction in PostViewCFG. |
580 | // The PostViewCFG is created with updates reversed (equivalent to changes |
581 | // made to the CFG), so the PreViewCFG needs all the updates reverse |
582 | // applied. |
583 | SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end()); |
584 | append_range(AllUpdates, PostViewUpdates); |
585 | GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates, |
586 | /*ReverseApplyUpdates=*/true); |
587 | GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates); |
588 | DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG); |
589 | } |
590 | } |
591 | |
592 | /// Inform the dominator tree about a CFG edge insertion and update the tree. |
593 | /// |
594 | /// This function has to be called just before or just after making the update |
595 | /// on the actual CFG. There cannot be any other updates that the dominator |
596 | /// tree doesn't know about. |
597 | /// |
598 | /// Note that for postdominators it automatically takes care of inserting |
599 | /// a reverse edge internally (so there's no need to swap the parameters). |
600 | /// |
601 | void insertEdge(NodeT *From, NodeT *To) { |
602 | assert(From); |
603 | assert(To); |
604 | assert(NodeTrait::getParent(From) == Parent); |
605 | assert(NodeTrait::getParent(To) == Parent); |
606 | DomTreeBuilder::InsertEdge(*this, From, To); |
607 | } |
608 | |
609 | /// Inform the dominator tree about a CFG edge deletion and update the tree. |
610 | /// |
611 | /// This function has to be called just after making the update on the actual |
612 | /// CFG. An internal functions checks if the edge doesn't exist in the CFG in |
613 | /// DEBUG mode. There cannot be any other updates that the |
614 | /// dominator tree doesn't know about. |
615 | /// |
616 | /// Note that for postdominators it automatically takes care of deleting |
617 | /// a reverse edge internally (so there's no need to swap the parameters). |
618 | /// |
619 | void deleteEdge(NodeT *From, NodeT *To) { |
620 | assert(From); |
621 | assert(To); |
622 | assert(NodeTrait::getParent(From) == Parent); |
623 | assert(NodeTrait::getParent(To) == Parent); |
624 | DomTreeBuilder::DeleteEdge(*this, From, To); |
625 | } |
626 | |
627 | /// Add a new node to the dominator tree information. |
628 | /// |
629 | /// This creates a new node as a child of DomBB dominator node, linking it |
630 | /// into the children list of the immediate dominator. |
631 | /// |
632 | /// \param BB New node in CFG. |
633 | /// \param DomBB CFG node that is dominator for BB. |
634 | /// \returns New dominator tree node that represents new CFG node. |
635 | /// |
636 | DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { |
637 | assert(getNode(BB) == nullptr && "Block already in dominator tree!" ); |
638 | DomTreeNodeBase<NodeT> *IDomNode = getNode(BB: DomBB); |
639 | assert(IDomNode && "Not immediate dominator specified for block!" ); |
640 | DFSInfoValid = false; |
641 | return createChild(BB, IDom: IDomNode); |
642 | } |
643 | |
644 | /// Add a new node to the forward dominator tree and make it a new root. |
645 | /// |
646 | /// \param BB New node in CFG. |
647 | /// \returns New dominator tree node that represents new CFG node. |
648 | /// |
649 | DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) { |
650 | assert(getNode(BB) == nullptr && "Block already in dominator tree!" ); |
651 | assert(!this->isPostDominator() && |
652 | "Cannot change root of post-dominator tree" ); |
653 | DFSInfoValid = false; |
654 | DomTreeNodeBase<NodeT> *NewNode = createNode(BB); |
655 | if (Roots.empty()) { |
656 | addRoot(BB); |
657 | } else { |
658 | assert(Roots.size() == 1); |
659 | NodeT *OldRoot = Roots.front(); |
660 | auto &OldNode = DomTreeNodes[OldRoot]; |
661 | OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); |
662 | OldNode->IDom = NewNode; |
663 | OldNode->UpdateLevel(); |
664 | Roots[0] = BB; |
665 | } |
666 | return RootNode = NewNode; |
667 | } |
668 | |
669 | /// changeImmediateDominator - This method is used to update the dominator |
670 | /// tree information when a node's immediate dominator changes. |
671 | /// |
672 | void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, |
673 | DomTreeNodeBase<NodeT> *NewIDom) { |
674 | assert(N && NewIDom && "Cannot change null node pointers!" ); |
675 | DFSInfoValid = false; |
676 | N->setIDom(NewIDom); |
677 | } |
678 | |
679 | void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { |
680 | changeImmediateDominator(getNode(BB), getNode(BB: NewBB)); |
681 | } |
682 | |
683 | /// eraseNode - Removes a node from the dominator tree. Block must not |
684 | /// dominate any other blocks. Removes node from its immediate dominator's |
685 | /// children list. Deletes dominator node associated with basic block BB. |
686 | void eraseNode(NodeT *BB) { |
687 | DomTreeNodeBase<NodeT> *Node = getNode(BB); |
688 | assert(Node && "Removing node that isn't in dominator tree." ); |
689 | assert(Node->isLeaf() && "Node is not a leaf node." ); |
690 | |
691 | DFSInfoValid = false; |
692 | |
693 | // Remove node from immediate dominator's children list. |
694 | DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); |
695 | if (IDom) { |
696 | const auto I = find(IDom->Children, Node); |
697 | assert(I != IDom->Children.end() && |
698 | "Not in immediate dominator children set!" ); |
699 | // I am no longer your child... |
700 | IDom->Children.erase(I); |
701 | } |
702 | |
703 | DomTreeNodes.erase(BB); |
704 | |
705 | if (!IsPostDom) return; |
706 | |
707 | // Remember to update PostDominatorTree roots. |
708 | auto RIt = llvm::find(Roots, BB); |
709 | if (RIt != Roots.end()) { |
710 | std::swap(*RIt, Roots.back()); |
711 | Roots.pop_back(); |
712 | } |
713 | } |
714 | |
715 | /// splitBlock - BB is split and now it has one successor. Update dominator |
716 | /// tree to reflect this change. |
717 | void splitBlock(NodeT *NewBB) { |
718 | if (IsPostDominator) |
719 | Split<Inverse<NodeT *>>(NewBB); |
720 | else |
721 | Split<NodeT *>(NewBB); |
722 | } |
723 | |
724 | /// print - Convert to human readable form |
725 | /// |
726 | void print(raw_ostream &O) const { |
727 | O << "=============================--------------------------------\n" ; |
728 | if (IsPostDominator) |
729 | O << "Inorder PostDominator Tree: " ; |
730 | else |
731 | O << "Inorder Dominator Tree: " ; |
732 | if (!DFSInfoValid) |
733 | O << "DFSNumbers invalid: " << SlowQueries << " slow queries." ; |
734 | O << "\n" ; |
735 | |
736 | // The postdom tree can have a null root if there are no returns. |
737 | if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); |
738 | O << "Roots: " ; |
739 | for (const NodePtr Block : Roots) { |
740 | Block->printAsOperand(O, false); |
741 | O << " " ; |
742 | } |
743 | O << "\n" ; |
744 | } |
745 | |
746 | public: |
747 | /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking |
748 | /// dominator tree in dfs order. |
749 | void updateDFSNumbers() const { |
750 | if (DFSInfoValid) { |
751 | SlowQueries = 0; |
752 | return; |
753 | } |
754 | |
755 | SmallVector<std::pair<const DomTreeNodeBase<NodeT> *, |
756 | typename DomTreeNodeBase<NodeT>::const_iterator>, |
757 | 32> WorkStack; |
758 | |
759 | const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); |
760 | assert((!Parent || ThisRoot) && "Empty constructed DomTree" ); |
761 | if (!ThisRoot) |
762 | return; |
763 | |
764 | // Both dominators and postdominators have a single root node. In the case |
765 | // case of PostDominatorTree, this node is a virtual root. |
766 | WorkStack.push_back({ThisRoot, ThisRoot->begin()}); |
767 | |
768 | unsigned DFSNum = 0; |
769 | ThisRoot->DFSNumIn = DFSNum++; |
770 | |
771 | while (!WorkStack.empty()) { |
772 | const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; |
773 | const auto ChildIt = WorkStack.back().second; |
774 | |
775 | // If we visited all of the children of this node, "recurse" back up the |
776 | // stack setting the DFOutNum. |
777 | if (ChildIt == Node->end()) { |
778 | Node->DFSNumOut = DFSNum++; |
779 | WorkStack.pop_back(); |
780 | } else { |
781 | // Otherwise, recursively visit this child. |
782 | const DomTreeNodeBase<NodeT> *Child = *ChildIt; |
783 | ++WorkStack.back().second; |
784 | |
785 | WorkStack.push_back({Child, Child->begin()}); |
786 | Child->DFSNumIn = DFSNum++; |
787 | } |
788 | } |
789 | |
790 | SlowQueries = 0; |
791 | DFSInfoValid = true; |
792 | } |
793 | |
794 | /// recalculate - compute a dominator tree for the given function |
795 | void recalculate(ParentType &Func) { |
796 | Parent = &Func; |
797 | DomTreeBuilder::Calculate(*this); |
798 | } |
799 | |
800 | void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) { |
801 | Parent = &Func; |
802 | DomTreeBuilder::CalculateWithUpdates(*this, Updates); |
803 | } |
804 | |
805 | /// verify - checks if the tree is correct. There are 3 level of verification: |
806 | /// - Full -- verifies if the tree is correct by making sure all the |
807 | /// properties (including the parent and the sibling property) |
808 | /// hold. |
809 | /// Takes O(N^3) time. |
810 | /// |
811 | /// - Basic -- checks if the tree is correct, but compares it to a freshly |
812 | /// constructed tree instead of checking the sibling property. |
813 | /// Takes O(N^2) time. |
814 | /// |
815 | /// - Fast -- checks basic tree structure and compares it with a freshly |
816 | /// constructed tree. |
817 | /// Takes O(N^2) time worst case, but is faster in practise (same |
818 | /// as tree construction). |
819 | bool verify(VerificationLevel VL = VerificationLevel::Full) const { |
820 | return DomTreeBuilder::Verify(*this, VL); |
821 | } |
822 | |
823 | void reset() { |
824 | DomTreeNodes.clear(); |
825 | Roots.clear(); |
826 | RootNode = nullptr; |
827 | Parent = nullptr; |
828 | DFSInfoValid = false; |
829 | SlowQueries = 0; |
830 | } |
831 | |
832 | protected: |
833 | void addRoot(NodeT *BB) { this->Roots.push_back(BB); } |
834 | |
835 | DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) { |
836 | return (DomTreeNodes[BB] = IDom->addChild( |
837 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom))) |
838 | .get(); |
839 | } |
840 | |
841 | DomTreeNodeBase<NodeT> *createNode(NodeT *BB) { |
842 | return (DomTreeNodes[BB] = |
843 | std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)) |
844 | .get(); |
845 | } |
846 | |
847 | // NewBB is split and now it has one successor. Update dominator tree to |
848 | // reflect this change. |
849 | template <class N> |
850 | void Split(typename GraphTraits<N>::NodeRef NewBB) { |
851 | using GraphT = GraphTraits<N>; |
852 | using NodeRef = typename GraphT::NodeRef; |
853 | assert(llvm::hasSingleElement(children<N>(NewBB)) && |
854 | "NewBB should have a single successor!" ); |
855 | NodeRef NewBBSucc = *GraphT::child_begin(NewBB); |
856 | |
857 | SmallVector<NodeRef, 4> PredBlocks(inverse_children<N>(NewBB)); |
858 | |
859 | assert(!PredBlocks.empty() && "No predblocks?" ); |
860 | |
861 | bool NewBBDominatesNewBBSucc = true; |
862 | for (auto *Pred : inverse_children<N>(NewBBSucc)) { |
863 | if (Pred != NewBB && !dominates(NewBBSucc, Pred) && |
864 | isReachableFromEntry(Pred)) { |
865 | NewBBDominatesNewBBSucc = false; |
866 | break; |
867 | } |
868 | } |
869 | |
870 | // Find NewBB's immediate dominator and create new dominator tree node for |
871 | // NewBB. |
872 | NodeT *NewBBIDom = nullptr; |
873 | unsigned i = 0; |
874 | for (i = 0; i < PredBlocks.size(); ++i) |
875 | if (isReachableFromEntry(PredBlocks[i])) { |
876 | NewBBIDom = PredBlocks[i]; |
877 | break; |
878 | } |
879 | |
880 | // It's possible that none of the predecessors of NewBB are reachable; |
881 | // in that case, NewBB itself is unreachable, so nothing needs to be |
882 | // changed. |
883 | if (!NewBBIDom) return; |
884 | |
885 | for (i = i + 1; i < PredBlocks.size(); ++i) { |
886 | if (isReachableFromEntry(PredBlocks[i])) |
887 | NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); |
888 | } |
889 | |
890 | // Create the new dominator tree node... and set the idom of NewBB. |
891 | DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(BB: NewBB, DomBB: NewBBIDom); |
892 | |
893 | // If NewBB strictly dominates other blocks, then it is now the immediate |
894 | // dominator of NewBBSucc. Update the dominator tree as appropriate. |
895 | if (NewBBDominatesNewBBSucc) { |
896 | DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(BB: NewBBSucc); |
897 | changeImmediateDominator(NewBBSuccNode, NewBBNode); |
898 | } |
899 | } |
900 | |
901 | private: |
902 | bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, |
903 | const DomTreeNodeBase<NodeT> *B) const { |
904 | assert(A != B); |
905 | assert(isReachableFromEntry(B)); |
906 | assert(isReachableFromEntry(A)); |
907 | |
908 | const unsigned ALevel = A->getLevel(); |
909 | const DomTreeNodeBase<NodeT> *IDom; |
910 | |
911 | // Don't walk nodes above A's subtree. When we reach A's level, we must |
912 | // either find A or be in some other subtree not dominated by A. |
913 | while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel) |
914 | B = IDom; // Walk up the tree |
915 | |
916 | return B == A; |
917 | } |
918 | |
919 | /// Wipe this tree's state without releasing any resources. |
920 | /// |
921 | /// This is essentially a post-move helper only. It leaves the object in an |
922 | /// assignable and destroyable state, but otherwise invalid. |
923 | void wipe() { |
924 | DomTreeNodes.clear(); |
925 | RootNode = nullptr; |
926 | Parent = nullptr; |
927 | } |
928 | }; |
929 | |
930 | template <typename T> |
931 | using DomTreeBase = DominatorTreeBase<T, false>; |
932 | |
933 | template <typename T> |
934 | using PostDomTreeBase = DominatorTreeBase<T, true>; |
935 | |
936 | // These two functions are declared out of line as a workaround for building |
937 | // with old (< r147295) versions of clang because of pr11642. |
938 | template <typename NodeT, bool IsPostDom> |
939 | bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A, |
940 | const NodeT *B) const { |
941 | if (A == B) |
942 | return true; |
943 | |
944 | // Cast away the const qualifiers here. This is ok since |
945 | // this function doesn't actually return the values returned |
946 | // from getNode. |
947 | return dominates(getNode(BB: const_cast<NodeT *>(A)), |
948 | getNode(BB: const_cast<NodeT *>(B))); |
949 | } |
950 | template <typename NodeT, bool IsPostDom> |
951 | bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates( |
952 | const NodeT *A, const NodeT *B) const { |
953 | if (A == B) |
954 | return false; |
955 | |
956 | // Cast away the const qualifiers here. This is ok since |
957 | // this function doesn't actually return the values returned |
958 | // from getNode. |
959 | return dominates(getNode(BB: const_cast<NodeT *>(A)), |
960 | getNode(BB: const_cast<NodeT *>(B))); |
961 | } |
962 | |
963 | } // end namespace llvm |
964 | |
965 | #endif // LLVM_SUPPORT_GENERICDOMTREE_H |
966 | |