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