1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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
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 /// NodeRef->getParent() must return the parent node that is also a pointer.
19 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
21 //===----------------------------------------------------------------------===//
23 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
24 #define LLVM_SUPPORT_GENERICDOMTREE_H
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/GraphTraits.h"
28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/Support/CFGUpdate.h"
32 #include "llvm/Support/raw_ostream.h"
38 #include <type_traits>
44 template <typename NodeT, bool IsPostDom>
45 class DominatorTreeBase;
47 namespace DomTreeBuilder {
48 template <typename DomTreeT>
50 } // namespace DomTreeBuilder
52 /// Base class for the actual dominator tree node.
53 template <class NodeT> class DomTreeNodeBase {
54 friend class PostDominatorTree;
55 friend class DominatorTreeBase<NodeT, false>;
56 friend class DominatorTreeBase<NodeT, true>;
57 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
58 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
61 DomTreeNodeBase *IDom;
63 std::vector<DomTreeNodeBase *> Children;
64 mutable unsigned DFSNumIn = ~0;
65 mutable unsigned DFSNumOut = ~0;
68 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
69 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
71 using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
72 using const_iterator =
73 typename std::vector<DomTreeNodeBase *>::const_iterator;
75 iterator begin() { return Children.begin(); }
76 iterator end() { return Children.end(); }
77 const_iterator begin() const { return Children.begin(); }
78 const_iterator end() const { return Children.end(); }
80 DomTreeNodeBase *const &back() const { return Children.back(); }
81 DomTreeNodeBase *&back() { return Children.back(); }
83 iterator_range<iterator> children() { return make_range(begin(), end()); }
84 iterator_range<const_iterator> children() const {
85 return make_range(begin(), end());
88 NodeT *getBlock() const { return TheBB; }
89 DomTreeNodeBase *getIDom() const { return IDom; }
90 unsigned getLevel() const { return Level; }
92 std::unique_ptr<DomTreeNodeBase> addChild(
93 std::unique_ptr<DomTreeNodeBase> C) {
94 Children.push_back(C.get());
98 bool isLeaf() const { return Children.empty(); }
99 size_t getNumChildren() const { return Children.size(); }
101 void clearAllChildren() { Children.clear(); }
103 bool compare(const DomTreeNodeBase *Other) const {
104 if (getNumChildren() != Other->getNumChildren())
107 if (Level != Other->Level) return true;
109 SmallPtrSet<const NodeT *, 4> OtherChildren;
110 for (const DomTreeNodeBase *I : *Other) {
111 const NodeT *Nd = I->getBlock();
112 OtherChildren.insert(Nd);
115 for (const DomTreeNodeBase *I : *this) {
116 const NodeT *N = I->getBlock();
117 if (OtherChildren.count(N) == 0)
123 void setIDom(DomTreeNodeBase *NewIDom) {
124 assert(IDom && "No immediate dominator?");
125 if (IDom == NewIDom) return;
127 auto I = find(IDom->Children, this);
128 assert(I != IDom->Children.end() &&
129 "Not in immediate dominator children set!");
130 // I am no longer your child...
131 IDom->Children.erase(I);
133 // Switch to new dominator
135 IDom->Children.push_back(this);
140 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
141 /// in the dominator tree. They are only guaranteed valid if
142 /// updateDFSNumbers() has been called.
143 unsigned getDFSNumIn() const { return DFSNumIn; }
144 unsigned getDFSNumOut() const { return DFSNumOut; }
147 // Return true if this node is dominated by other. Use this only if DFS info
149 bool DominatedBy(const DomTreeNodeBase *other) const {
150 return this->DFSNumIn >= other->DFSNumIn &&
151 this->DFSNumOut <= other->DFSNumOut;
156 if (Level == IDom->Level + 1) return;
158 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
160 while (!WorkStack.empty()) {
161 DomTreeNodeBase *Current = WorkStack.pop_back_val();
162 Current->Level = Current->IDom->Level + 1;
164 for (DomTreeNodeBase *C : *Current) {
166 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
172 template <class NodeT>
173 raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
174 if (Node->getBlock())
175 Node->getBlock()->printAsOperand(O, false);
177 O << " <<exit node>>";
179 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
180 << Node->getLevel() << "]\n";
185 template <class NodeT>
186 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
188 O.indent(2 * Lev) << "[" << Lev << "] " << N;
189 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
192 PrintDomTree<NodeT>(*I, O, Lev + 1);
195 namespace DomTreeBuilder {
196 // The routines below are provided in a separate header but referenced here.
197 template <typename DomTreeT>
198 void Calculate(DomTreeT &DT);
200 template <typename DomTreeT>
201 void CalculateWithUpdates(DomTreeT &DT,
202 ArrayRef<typename DomTreeT::UpdateType> Updates);
204 template <typename DomTreeT>
205 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
206 typename DomTreeT::NodePtr To);
208 template <typename DomTreeT>
209 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
210 typename DomTreeT::NodePtr To);
212 template <typename DomTreeT>
213 void ApplyUpdates(DomTreeT &DT,
214 ArrayRef<typename DomTreeT::UpdateType> Updates);
216 template <typename DomTreeT>
217 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
218 } // namespace DomTreeBuilder
220 /// Core dominator tree base class.
222 /// This class is a generic template over graph nodes. It is instantiated for
223 /// various graphs in the LLVM IR or in the code generator.
224 template <typename NodeT, bool IsPostDom>
225 class DominatorTreeBase {
227 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
228 "Currently DominatorTreeBase supports only pointer nodes");
229 using NodeType = NodeT;
230 using NodePtr = NodeT *;
231 using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
232 static_assert(std::is_pointer<ParentPtr>::value,
233 "Currently NodeT's parent must be a pointer type");
234 using ParentType = std::remove_pointer_t<ParentPtr>;
235 static constexpr bool IsPostDominator = IsPostDom;
237 using UpdateType = cfg::Update<NodePtr>;
238 using UpdateKind = cfg::UpdateKind;
239 static constexpr UpdateKind Insert = UpdateKind::Insert;
240 static constexpr UpdateKind Delete = UpdateKind::Delete;
242 enum class VerificationLevel { Fast, Basic, Full };
245 // Dominators always have a single root, postdominators can have more.
246 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
248 using DomTreeNodeMapType =
249 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
250 DomTreeNodeMapType DomTreeNodes;
251 DomTreeNodeBase<NodeT> *RootNode = nullptr;
252 ParentPtr Parent = nullptr;
254 mutable bool DFSInfoValid = false;
255 mutable unsigned int SlowQueries = 0;
257 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
260 DominatorTreeBase() {}
262 DominatorTreeBase(DominatorTreeBase &&Arg)
263 : Roots(std::move(Arg.Roots)),
264 DomTreeNodes(std::move(Arg.DomTreeNodes)),
265 RootNode(Arg.RootNode),
267 DFSInfoValid(Arg.DFSInfoValid),
268 SlowQueries(Arg.SlowQueries) {
272 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
273 Roots = std::move(RHS.Roots);
274 DomTreeNodes = std::move(RHS.DomTreeNodes);
275 RootNode = RHS.RootNode;
277 DFSInfoValid = RHS.DFSInfoValid;
278 SlowQueries = RHS.SlowQueries;
283 DominatorTreeBase(const DominatorTreeBase &) = delete;
284 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
286 /// Iteration over roots.
288 /// This may include multiple blocks if we are computing post dominators.
289 /// For forward dominators, this will always be a single block (the entry
291 using root_iterator = typename SmallVectorImpl<NodeT *>::iterator;
292 using const_root_iterator = typename SmallVectorImpl<NodeT *>::const_iterator;
294 root_iterator root_begin() { return Roots.begin(); }
295 const_root_iterator root_begin() const { return Roots.begin(); }
296 root_iterator root_end() { return Roots.end(); }
297 const_root_iterator root_end() const { return Roots.end(); }
299 size_t root_size() const { return Roots.size(); }
301 iterator_range<root_iterator> roots() {
302 return make_range(root_begin(), root_end());
304 iterator_range<const_root_iterator> roots() const {
305 return make_range(root_begin(), root_end());
308 /// isPostDominator - Returns true if analysis based of postdoms
310 bool isPostDominator() const { return IsPostDominator; }
312 /// compare - Return false if the other dominator tree base matches this
313 /// dominator tree base. Otherwise return true.
314 bool compare(const DominatorTreeBase &Other) const {
315 if (Parent != Other.Parent) return true;
317 if (Roots.size() != Other.Roots.size())
320 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
323 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
324 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
327 for (const auto &DomTreeNode : DomTreeNodes) {
328 NodeT *BB = DomTreeNode.first;
329 typename DomTreeNodeMapType::const_iterator OI =
330 OtherDomTreeNodes.find(BB);
331 if (OI == OtherDomTreeNodes.end())
334 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
335 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
337 if (MyNd.compare(&OtherNd))
344 /// getNode - return the (Post)DominatorTree node for the specified basic
345 /// block. This is the same as using operator[] on this class. The result
346 /// may (but is not required to) be null for a forward (backwards)
347 /// statically unreachable block.
348 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
349 auto I = DomTreeNodes.find(BB);
350 if (I != DomTreeNodes.end())
351 return I->second.get();
356 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
360 /// getRootNode - This returns the entry node for the CFG of the function. If
361 /// this tree represents the post-dominance relations for a function, however,
362 /// this root may be a node with the block == NULL. This is the case when
363 /// there are multiple exit nodes from a particular function. Consumers of
364 /// post-dominance information must be capable of dealing with this
367 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
368 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
370 /// Get all nodes dominated by R, including R itself.
371 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
373 const DomTreeNodeBase<NodeT> *RN = getNode(R);
375 return; // If R is unreachable, it will not be present in the DOM tree.
376 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
379 while (!WL.empty()) {
380 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
381 Result.push_back(N->getBlock());
382 WL.append(N->begin(), N->end());
386 /// properlyDominates - Returns true iff A dominates B and A != B.
387 /// Note that this is not a constant time operation!
389 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
390 const DomTreeNodeBase<NodeT> *B) const {
395 return dominates(A, B);
398 bool properlyDominates(const NodeT *A, const NodeT *B) const;
400 /// isReachableFromEntry - Return true if A is dominated by the entry
401 /// block of the function containing it.
402 bool isReachableFromEntry(const NodeT *A) const {
403 assert(!this->isPostDominator() &&
404 "This is not implemented for post dominators");
405 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
408 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
410 /// dominates - Returns true iff A dominates B. Note that this is not a
411 /// constant time operation!
413 bool dominates(const DomTreeNodeBase<NodeT> *A,
414 const DomTreeNodeBase<NodeT> *B) const {
415 // A node trivially dominates itself.
419 // An unreachable node is dominated by anything.
420 if (!isReachableFromEntry(B))
423 // And dominates nothing.
424 if (!isReachableFromEntry(A))
427 if (B->getIDom() == A) return true;
429 if (A->getIDom() == B) return false;
431 // A can only dominate B if it is higher in the tree.
432 if (A->getLevel() >= B->getLevel()) return false;
434 // Compare the result of the tree walk and the dfs numbers, if expensive
435 // checks are enabled.
436 #ifdef EXPENSIVE_CHECKS
437 assert((!DFSInfoValid ||
438 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
439 "Tree walk disagrees with dfs numbers!");
443 return B->DominatedBy(A);
445 // If we end up with too many slow queries, just update the
446 // DFS numbers on the theory that we are going to keep querying.
448 if (SlowQueries > 32) {
450 return B->DominatedBy(A);
453 return dominatedBySlowTreeWalk(A, B);
456 bool dominates(const NodeT *A, const NodeT *B) const;
458 NodeT *getRoot() const {
459 assert(this->Roots.size() == 1 && "Should always have entry node!");
460 return this->Roots[0];
463 /// findNearestCommonDominator - Find nearest common dominator basic block
464 /// for basic block A and B. If there is no such block then return nullptr.
465 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
466 assert(A && B && "Pointers are not valid");
467 assert(A->getParent() == B->getParent() &&
468 "Two blocks are not in same function");
470 // If either A or B is a entry block then it is nearest common dominator
471 // (for forward-dominators).
472 if (!isPostDominator()) {
473 NodeT &Entry = A->getParent()->front();
474 if (A == &Entry || B == &Entry)
478 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
479 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
481 if (!NodeA || !NodeB) return nullptr;
483 // Use level information to go up the tree until the levels match. Then
484 // continue going up til we arrive at the same node.
485 while (NodeA && NodeA != NodeB) {
486 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
491 return NodeA ? NodeA->getBlock() : nullptr;
494 const NodeT *findNearestCommonDominator(const NodeT *A,
495 const NodeT *B) const {
496 // Cast away the const qualifiers here. This is ok since
497 // const is re-introduced on the return type.
498 return findNearestCommonDominator(const_cast<NodeT *>(A),
499 const_cast<NodeT *>(B));
502 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
503 return isPostDominator() && !A->getBlock();
506 //===--------------------------------------------------------------------===//
507 // API to update (Post)DominatorTree information based on modifications to
510 /// Inform the dominator tree about a sequence of CFG edge insertions and
511 /// deletions and perform a batch update on the tree.
513 /// This function should be used when there were multiple CFG updates after
514 /// the last dominator tree update. It takes care of performing the updates
515 /// in sync with the CFG and optimizes away the redundant operations that
516 /// cancel each other.
517 /// The functions expects the sequence of updates to be balanced. Eg.:
518 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
519 /// logically it results in a single insertions.
520 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
521 /// sense to insert the same edge twice.
523 /// What's more, the functions assumes that it's safe to ask every node in the
524 /// CFG about its children and inverse children. This implies that deletions
525 /// of CFG edges must not delete the CFG nodes before calling this function.
527 /// The applyUpdates function can reorder the updates and remove redundant
528 /// ones internally. The batch updater is also able to detect sequences of
529 /// zero and exactly one update -- it's optimized to do less work in these
532 /// Note that for postdominators it automatically takes care of applying
533 /// updates on reverse edges internally (so there's no need to swap the
534 /// From and To pointers when constructing DominatorTree::UpdateType).
535 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
536 /// with the same template parameter T.
538 /// \param Updates An unordered sequence of updates to perform.
540 void applyUpdates(ArrayRef<UpdateType> Updates) {
541 DomTreeBuilder::ApplyUpdates(*this, Updates);
544 /// Inform the dominator tree about a CFG edge insertion and update the tree.
546 /// This function has to be called just before or just after making the update
547 /// on the actual CFG. There cannot be any other updates that the dominator
548 /// tree doesn't know about.
550 /// Note that for postdominators it automatically takes care of inserting
551 /// a reverse edge internally (so there's no need to swap the parameters).
553 void insertEdge(NodeT *From, NodeT *To) {
556 assert(From->getParent() == Parent);
557 assert(To->getParent() == Parent);
558 DomTreeBuilder::InsertEdge(*this, From, To);
561 /// Inform the dominator tree about a CFG edge deletion and update the tree.
563 /// This function has to be called just after making the update on the actual
564 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
565 /// DEBUG mode. There cannot be any other updates that the
566 /// dominator tree doesn't know about.
568 /// Note that for postdominators it automatically takes care of deleting
569 /// a reverse edge internally (so there's no need to swap the parameters).
571 void deleteEdge(NodeT *From, NodeT *To) {
574 assert(From->getParent() == Parent);
575 assert(To->getParent() == Parent);
576 DomTreeBuilder::DeleteEdge(*this, From, To);
579 /// Add a new node to the dominator tree information.
581 /// This creates a new node as a child of DomBB dominator node, linking it
582 /// into the children list of the immediate dominator.
584 /// \param BB New node in CFG.
585 /// \param DomBB CFG node that is dominator for BB.
586 /// \returns New dominator tree node that represents new CFG node.
588 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
589 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
590 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
591 assert(IDomNode && "Not immediate dominator specified for block!");
592 DFSInfoValid = false;
593 return createChild(BB, IDomNode);
596 /// Add a new node to the forward dominator tree and make it a new root.
598 /// \param BB New node in CFG.
599 /// \returns New dominator tree node that represents new CFG node.
601 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
602 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
603 assert(!this->isPostDominator() &&
604 "Cannot change root of post-dominator tree");
605 DFSInfoValid = false;
606 DomTreeNodeBase<NodeT> *NewNode = createNode(BB);
610 assert(Roots.size() == 1);
611 NodeT *OldRoot = Roots.front();
612 auto &OldNode = DomTreeNodes[OldRoot];
613 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
614 OldNode->IDom = NewNode;
615 OldNode->UpdateLevel();
618 return RootNode = NewNode;
621 /// changeImmediateDominator - This method is used to update the dominator
622 /// tree information when a node's immediate dominator changes.
624 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
625 DomTreeNodeBase<NodeT> *NewIDom) {
626 assert(N && NewIDom && "Cannot change null node pointers!");
627 DFSInfoValid = false;
631 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
632 changeImmediateDominator(getNode(BB), getNode(NewBB));
635 /// eraseNode - Removes a node from the dominator tree. Block must not
636 /// dominate any other blocks. Removes node from its immediate dominator's
637 /// children list. Deletes dominator node associated with basic block BB.
638 void eraseNode(NodeT *BB) {
639 DomTreeNodeBase<NodeT> *Node = getNode(BB);
640 assert(Node && "Removing node that isn't in dominator tree.");
641 assert(Node->isLeaf() && "Node is not a leaf node.");
643 DFSInfoValid = false;
645 // Remove node from immediate dominator's children list.
646 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
648 const auto I = find(IDom->Children, Node);
649 assert(I != IDom->Children.end() &&
650 "Not in immediate dominator children set!");
651 // I am no longer your child...
652 IDom->Children.erase(I);
655 DomTreeNodes.erase(BB);
657 if (!IsPostDom) return;
659 // Remember to update PostDominatorTree roots.
660 auto RIt = llvm::find(Roots, BB);
661 if (RIt != Roots.end()) {
662 std::swap(*RIt, Roots.back());
667 /// splitBlock - BB is split and now it has one successor. Update dominator
668 /// tree to reflect this change.
669 void splitBlock(NodeT *NewBB) {
671 Split<Inverse<NodeT *>>(NewBB);
673 Split<NodeT *>(NewBB);
676 /// print - Convert to human readable form
678 void print(raw_ostream &O) const {
679 O << "=============================--------------------------------\n";
681 O << "Inorder PostDominator Tree: ";
683 O << "Inorder Dominator Tree: ";
685 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
688 // The postdom tree can have a null root if there are no returns.
689 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
691 for (const NodePtr Block : Roots) {
692 Block->printAsOperand(O, false);
699 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
700 /// dominator tree in dfs order.
701 void updateDFSNumbers() const {
707 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
708 typename DomTreeNodeBase<NodeT>::const_iterator>,
711 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
712 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
716 // Both dominators and postdominators have a single root node. In the case
717 // case of PostDominatorTree, this node is a virtual root.
718 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
721 ThisRoot->DFSNumIn = DFSNum++;
723 while (!WorkStack.empty()) {
724 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
725 const auto ChildIt = WorkStack.back().second;
727 // If we visited all of the children of this node, "recurse" back up the
728 // stack setting the DFOutNum.
729 if (ChildIt == Node->end()) {
730 Node->DFSNumOut = DFSNum++;
731 WorkStack.pop_back();
733 // Otherwise, recursively visit this child.
734 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
735 ++WorkStack.back().second;
737 WorkStack.push_back({Child, Child->begin()});
738 Child->DFSNumIn = DFSNum++;
746 /// recalculate - compute a dominator tree for the given function
747 void recalculate(ParentType &Func) {
749 DomTreeBuilder::Calculate(*this);
752 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
754 DomTreeBuilder::CalculateWithUpdates(*this, Updates);
757 /// verify - checks if the tree is correct. There are 3 level of verification:
758 /// - Full -- verifies if the tree is correct by making sure all the
759 /// properties (including the parent and the sibling property)
761 /// Takes O(N^3) time.
763 /// - Basic -- checks if the tree is correct, but compares it to a freshly
764 /// constructed tree instead of checking the sibling property.
765 /// Takes O(N^2) time.
767 /// - Fast -- checks basic tree structure and compares it with a freshly
768 /// constructed tree.
769 /// Takes O(N^2) time worst case, but is faster in practise (same
770 /// as tree construction).
771 bool verify(VerificationLevel VL = VerificationLevel::Full) const {
772 return DomTreeBuilder::Verify(*this, VL);
776 DomTreeNodes.clear();
780 DFSInfoValid = false;
785 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
787 DomTreeNodeBase<NodeT> *createChild(NodeT *BB, DomTreeNodeBase<NodeT> *IDom) {
788 return (DomTreeNodes[BB] = IDom->addChild(
789 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
793 DomTreeNodeBase<NodeT> *createNode(NodeT *BB) {
794 return (DomTreeNodes[BB] =
795 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
799 // NewBB is split and now it has one successor. Update dominator tree to
800 // reflect this change.
802 void Split(typename GraphTraits<N>::NodeRef NewBB) {
803 using GraphT = GraphTraits<N>;
804 using NodeRef = typename GraphT::NodeRef;
805 assert(std::distance(GraphT::child_begin(NewBB),
806 GraphT::child_end(NewBB)) == 1 &&
807 "NewBB should have a single successor!");
808 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
810 std::vector<NodeRef> PredBlocks;
811 for (auto Pred : children<Inverse<N>>(NewBB))
812 PredBlocks.push_back(Pred);
814 assert(!PredBlocks.empty() && "No predblocks?");
816 bool NewBBDominatesNewBBSucc = true;
817 for (auto Pred : children<Inverse<N>>(NewBBSucc)) {
818 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
819 isReachableFromEntry(Pred)) {
820 NewBBDominatesNewBBSucc = false;
825 // Find NewBB's immediate dominator and create new dominator tree node for
827 NodeT *NewBBIDom = nullptr;
829 for (i = 0; i < PredBlocks.size(); ++i)
830 if (isReachableFromEntry(PredBlocks[i])) {
831 NewBBIDom = PredBlocks[i];
835 // It's possible that none of the predecessors of NewBB are reachable;
836 // in that case, NewBB itself is unreachable, so nothing needs to be
838 if (!NewBBIDom) return;
840 for (i = i + 1; i < PredBlocks.size(); ++i) {
841 if (isReachableFromEntry(PredBlocks[i]))
842 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
845 // Create the new dominator tree node... and set the idom of NewBB.
846 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
848 // If NewBB strictly dominates other blocks, then it is now the immediate
849 // dominator of NewBBSucc. Update the dominator tree as appropriate.
850 if (NewBBDominatesNewBBSucc) {
851 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
852 changeImmediateDominator(NewBBSuccNode, NewBBNode);
857 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
858 const DomTreeNodeBase<NodeT> *B) const {
860 assert(isReachableFromEntry(B));
861 assert(isReachableFromEntry(A));
863 const unsigned ALevel = A->getLevel();
864 const DomTreeNodeBase<NodeT> *IDom;
866 // Don't walk nodes above A's subtree. When we reach A's level, we must
867 // either find A or be in some other subtree not dominated by A.
868 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
869 B = IDom; // Walk up the tree
874 /// Wipe this tree's state without releasing any resources.
876 /// This is essentially a post-move helper only. It leaves the object in an
877 /// assignable and destroyable state, but otherwise invalid.
879 DomTreeNodes.clear();
885 template <typename T>
886 using DomTreeBase = DominatorTreeBase<T, false>;
888 template <typename T>
889 using PostDomTreeBase = DominatorTreeBase<T, true>;
891 // These two functions are declared out of line as a workaround for building
892 // with old (< r147295) versions of clang because of pr11642.
893 template <typename NodeT, bool IsPostDom>
894 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
895 const NodeT *B) const {
899 // Cast away the const qualifiers here. This is ok since
900 // this function doesn't actually return the values returned
902 return dominates(getNode(const_cast<NodeT *>(A)),
903 getNode(const_cast<NodeT *>(B)));
905 template <typename NodeT, bool IsPostDom>
906 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
907 const NodeT *A, const NodeT *B) const {
911 // Cast away the const qualifiers here. This is ok since
912 // this function doesn't actually return the values returned
914 return dominates(getNode(const_cast<NodeT *>(A)),
915 getNode(const_cast<NodeT *>(B)));
918 } // end namespace llvm
920 #endif // LLVM_SUPPORT_GENERICDOMTREE_H