1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file defines a set of templates that efficiently compute a dominator
12 /// tree over a generic graph. This is used typically in LLVM for fast
13 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
16 /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
17 /// on the graph's NodeRef. The NodeRef should be a pointer and,
18 /// NodeRef->getParent() must return the parent node that is also a pointer.
20 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
22 //===----------------------------------------------------------------------===//
24 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
25 #define LLVM_SUPPORT_GENERICDOMTREE_H
32 #include <type_traits>
35 #include "llvm/ADT/DenseMap.h"
36 #include "llvm/ADT/GraphTraits.h"
37 #include "llvm/ADT/PointerIntPair.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/Support/raw_ostream.h"
45 template <typename NodeT, bool IsPostDom>
46 class DominatorTreeBase;
48 namespace DomTreeBuilder {
49 template <typename DomTreeT>
51 } // namespace DomTreeBuilder
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>>;
62 DomTreeNodeBase *IDom;
64 std::vector<DomTreeNodeBase *> Children;
65 mutable unsigned DFSNumIn = ~0;
66 mutable unsigned DFSNumOut = ~0;
69 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
70 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
72 using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
73 using const_iterator =
74 typename std::vector<DomTreeNodeBase *>::const_iterator;
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(); }
81 NodeT *getBlock() const { return TheBB; }
82 DomTreeNodeBase *getIDom() const { return IDom; }
83 unsigned getLevel() const { return Level; }
85 const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
87 std::unique_ptr<DomTreeNodeBase> addChild(
88 std::unique_ptr<DomTreeNodeBase> C) {
89 Children.push_back(C.get());
93 size_t getNumChildren() const { return Children.size(); }
95 void clearAllChildren() { Children.clear(); }
97 bool compare(const DomTreeNodeBase *Other) const {
98 if (getNumChildren() != Other->getNumChildren())
101 if (Level != Other->Level) return true;
103 SmallPtrSet<const NodeT *, 4> OtherChildren;
104 for (const DomTreeNodeBase *I : *Other) {
105 const NodeT *Nd = I->getBlock();
106 OtherChildren.insert(Nd);
109 for (const DomTreeNodeBase *I : *this) {
110 const NodeT *N = I->getBlock();
111 if (OtherChildren.count(N) == 0)
117 void setIDom(DomTreeNodeBase *NewIDom) {
118 assert(IDom && "No immediate dominator?");
119 if (IDom == NewIDom) return;
121 auto I = find(IDom->Children, this);
122 assert(I != IDom->Children.end() &&
123 "Not in immediate dominator children set!");
124 // I am no longer your child...
125 IDom->Children.erase(I);
127 // Switch to new dominator
129 IDom->Children.push_back(this);
134 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
135 /// in the dominator tree. They are only guaranteed valid if
136 /// updateDFSNumbers() has been called.
137 unsigned getDFSNumIn() const { return DFSNumIn; }
138 unsigned getDFSNumOut() const { return DFSNumOut; }
141 // Return true if this node is dominated by other. Use this only if DFS info
143 bool DominatedBy(const DomTreeNodeBase *other) const {
144 return this->DFSNumIn >= other->DFSNumIn &&
145 this->DFSNumOut <= other->DFSNumOut;
150 if (Level == IDom->Level + 1) return;
152 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
154 while (!WorkStack.empty()) {
155 DomTreeNodeBase *Current = WorkStack.pop_back_val();
156 Current->Level = Current->IDom->Level + 1;
158 for (DomTreeNodeBase *C : *Current) {
160 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
166 template <class NodeT>
167 raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
168 if (Node->getBlock())
169 Node->getBlock()->printAsOperand(O, false);
171 O << " <<exit node>>";
173 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174 << Node->getLevel() << "]\n";
179 template <class NodeT>
180 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
182 O.indent(2 * Lev) << "[" << Lev << "] " << N;
183 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
186 PrintDomTree<NodeT>(*I, O, Lev + 1);
189 namespace DomTreeBuilder {
190 // The routines below are provided in a separate header but referenced here.
191 template <typename DomTreeT>
192 void Calculate(DomTreeT &DT);
194 template <typename DomTreeT>
195 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
196 typename DomTreeT::NodePtr To);
198 template <typename DomTreeT>
199 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200 typename DomTreeT::NodePtr To);
202 // UpdateKind and Update are used by the batch update API and it's easiest to
204 enum class UpdateKind : unsigned char { Insert, Delete };
206 template <typename NodePtr>
208 using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
211 NodeKindPair ToAndKind;
213 Update(UpdateKind Kind, NodePtr From, NodePtr To)
214 : From(From), ToAndKind(To, Kind) {}
216 UpdateKind getKind() const { return ToAndKind.getInt(); }
217 NodePtr getFrom() const { return From; }
218 NodePtr getTo() const { return ToAndKind.getPointer(); }
219 bool operator==(const Update &RHS) const {
220 return From == RHS.From && ToAndKind == RHS.ToAndKind;
223 friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
224 OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
225 U.getFrom()->printAsOperand(OS, false);
227 U.getTo()->printAsOperand(OS, false);
232 template <typename DomTreeT>
233 void ApplyUpdates(DomTreeT &DT,
234 ArrayRef<typename DomTreeT::UpdateType> Updates);
236 template <typename DomTreeT>
237 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
238 } // namespace DomTreeBuilder
240 /// Core dominator tree base class.
242 /// This class is a generic template over graph nodes. It is instantiated for
243 /// various graphs in the LLVM IR or in the code generator.
244 template <typename NodeT, bool IsPostDom>
245 class DominatorTreeBase {
247 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
248 "Currently DominatorTreeBase supports only pointer nodes");
249 using NodeType = NodeT;
250 using NodePtr = NodeT *;
251 using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
252 static_assert(std::is_pointer<ParentPtr>::value,
253 "Currently NodeT's parent must be a pointer type");
254 using ParentType = typename std::remove_pointer<ParentPtr>::type;
255 static constexpr bool IsPostDominator = IsPostDom;
257 using UpdateType = DomTreeBuilder::Update<NodePtr>;
258 using UpdateKind = DomTreeBuilder::UpdateKind;
259 static constexpr UpdateKind Insert = UpdateKind::Insert;
260 static constexpr UpdateKind Delete = UpdateKind::Delete;
262 enum class VerificationLevel { Fast, Basic, Full };
265 // Dominators always have a single root, postdominators can have more.
266 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
268 using DomTreeNodeMapType =
269 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
270 DomTreeNodeMapType DomTreeNodes;
271 DomTreeNodeBase<NodeT> *RootNode;
272 ParentPtr Parent = nullptr;
274 mutable bool DFSInfoValid = false;
275 mutable unsigned int SlowQueries = 0;
277 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
280 DominatorTreeBase() {}
282 DominatorTreeBase(DominatorTreeBase &&Arg)
283 : Roots(std::move(Arg.Roots)),
284 DomTreeNodes(std::move(Arg.DomTreeNodes)),
285 RootNode(Arg.RootNode),
287 DFSInfoValid(Arg.DFSInfoValid),
288 SlowQueries(Arg.SlowQueries) {
292 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
293 Roots = std::move(RHS.Roots);
294 DomTreeNodes = std::move(RHS.DomTreeNodes);
295 RootNode = RHS.RootNode;
297 DFSInfoValid = RHS.DFSInfoValid;
298 SlowQueries = RHS.SlowQueries;
303 DominatorTreeBase(const DominatorTreeBase &) = delete;
304 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
306 /// getRoots - Return the root blocks of the current CFG. This may include
307 /// multiple blocks if we are computing post dominators. For forward
308 /// dominators, this will always be a single block (the entry node).
310 const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
312 /// isPostDominator - Returns true if analysis based of postdoms
314 bool isPostDominator() const { return IsPostDominator; }
316 /// compare - Return false if the other dominator tree base matches this
317 /// dominator tree base. Otherwise return true.
318 bool compare(const DominatorTreeBase &Other) const {
319 if (Parent != Other.Parent) return true;
321 if (Roots.size() != Other.Roots.size())
324 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
327 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
328 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
331 for (const auto &DomTreeNode : DomTreeNodes) {
332 NodeT *BB = DomTreeNode.first;
333 typename DomTreeNodeMapType::const_iterator OI =
334 OtherDomTreeNodes.find(BB);
335 if (OI == OtherDomTreeNodes.end())
338 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
339 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
341 if (MyNd.compare(&OtherNd))
348 void releaseMemory() { reset(); }
350 /// getNode - return the (Post)DominatorTree node for the specified basic
351 /// block. This is the same as using operator[] on this class. The result
352 /// may (but is not required to) be null for a forward (backwards)
353 /// statically unreachable block.
354 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
355 auto I = DomTreeNodes.find(BB);
356 if (I != DomTreeNodes.end())
357 return I->second.get();
362 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
366 /// getRootNode - This returns the entry node for the CFG of the function. If
367 /// this tree represents the post-dominance relations for a function, however,
368 /// this root may be a node with the block == NULL. This is the case when
369 /// there are multiple exit nodes from a particular function. Consumers of
370 /// post-dominance information must be capable of dealing with this
373 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
374 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
376 /// Get all nodes dominated by R, including R itself.
377 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
379 const DomTreeNodeBase<NodeT> *RN = getNode(R);
381 return; // If R is unreachable, it will not be present in the DOM tree.
382 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
385 while (!WL.empty()) {
386 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
387 Result.push_back(N->getBlock());
388 WL.append(N->begin(), N->end());
392 /// properlyDominates - Returns true iff A dominates B and A != B.
393 /// Note that this is not a constant time operation!
395 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
396 const DomTreeNodeBase<NodeT> *B) const {
401 return dominates(A, B);
404 bool properlyDominates(const NodeT *A, const NodeT *B) const;
406 /// isReachableFromEntry - Return true if A is dominated by the entry
407 /// block of the function containing it.
408 bool isReachableFromEntry(const NodeT *A) const {
409 assert(!this->isPostDominator() &&
410 "This is not implemented for post dominators");
411 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
414 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
416 /// dominates - Returns true iff A dominates B. Note that this is not a
417 /// constant time operation!
419 bool dominates(const DomTreeNodeBase<NodeT> *A,
420 const DomTreeNodeBase<NodeT> *B) const {
421 // A node trivially dominates itself.
425 // An unreachable node is dominated by anything.
426 if (!isReachableFromEntry(B))
429 // And dominates nothing.
430 if (!isReachableFromEntry(A))
433 if (B->getIDom() == A) return true;
435 if (A->getIDom() == B) return false;
437 // A can only dominate B if it is higher in the tree.
438 if (A->getLevel() >= B->getLevel()) return false;
440 // Compare the result of the tree walk and the dfs numbers, if expensive
441 // checks are enabled.
442 #ifdef EXPENSIVE_CHECKS
443 assert((!DFSInfoValid ||
444 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
445 "Tree walk disagrees with dfs numbers!");
449 return B->DominatedBy(A);
451 // If we end up with too many slow queries, just update the
452 // DFS numbers on the theory that we are going to keep querying.
454 if (SlowQueries > 32) {
456 return B->DominatedBy(A);
459 return dominatedBySlowTreeWalk(A, B);
462 bool dominates(const NodeT *A, const NodeT *B) const;
464 NodeT *getRoot() const {
465 assert(this->Roots.size() == 1 && "Should always have entry node!");
466 return this->Roots[0];
469 /// findNearestCommonDominator - Find nearest common dominator basic block
470 /// for basic block A and B. If there is no such block then return nullptr.
471 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
472 assert(A && B && "Pointers are not valid");
473 assert(A->getParent() == B->getParent() &&
474 "Two blocks are not in same function");
476 // If either A or B is a entry block then it is nearest common dominator
477 // (for forward-dominators).
478 if (!isPostDominator()) {
479 NodeT &Entry = A->getParent()->front();
480 if (A == &Entry || B == &Entry)
484 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
485 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
487 if (!NodeA || !NodeB) return nullptr;
489 // Use level information to go up the tree until the levels match. Then
490 // continue going up til we arrive at the same node.
491 while (NodeA && NodeA != NodeB) {
492 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
497 return NodeA ? NodeA->getBlock() : nullptr;
500 const NodeT *findNearestCommonDominator(const NodeT *A,
501 const NodeT *B) const {
502 // Cast away the const qualifiers here. This is ok since
503 // const is re-introduced on the return type.
504 return findNearestCommonDominator(const_cast<NodeT *>(A),
505 const_cast<NodeT *>(B));
508 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
509 return isPostDominator() && !A->getBlock();
512 //===--------------------------------------------------------------------===//
513 // API to update (Post)DominatorTree information based on modifications to
516 /// Inform the dominator tree about a sequence of CFG edge insertions and
517 /// deletions and perform a batch update on the tree.
519 /// This function should be used when there were multiple CFG updates after
520 /// the last dominator tree update. It takes care of performing the updates
521 /// in sync with the CFG and optimizes away the redundant operations that
522 /// cancel each other.
523 /// The functions expects the sequence of updates to be balanced. Eg.:
524 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
525 /// logically it results in a single insertions.
526 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
527 /// sense to insert the same edge twice.
529 /// What's more, the functions assumes that it's safe to ask every node in the
530 /// CFG about its children and inverse children. This implies that deletions
531 /// of CFG edges must not delete the CFG nodes before calling this function.
533 /// The applyUpdates function can reorder the updates and remove redundant
534 /// ones internally. The batch updater is also able to detect sequences of
535 /// zero and exactly one update -- it's optimized to do less work in these
538 /// Note that for postdominators it automatically takes care of applying
539 /// updates on reverse edges internally (so there's no need to swap the
540 /// From and To pointers when constructing DominatorTree::UpdateType).
541 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
542 /// with the same template parameter T.
544 /// \param Updates An unordered sequence of updates to perform.
546 void applyUpdates(ArrayRef<UpdateType> Updates) {
547 DomTreeBuilder::ApplyUpdates(*this, Updates);
550 /// Inform the dominator tree about a CFG edge insertion and update the tree.
552 /// This function has to be called just before or just after making the update
553 /// on the actual CFG. There cannot be any other updates that the dominator
554 /// tree doesn't know about.
556 /// Note that for postdominators it automatically takes care of inserting
557 /// a reverse edge internally (so there's no need to swap the parameters).
559 void insertEdge(NodeT *From, NodeT *To) {
562 assert(From->getParent() == Parent);
563 assert(To->getParent() == Parent);
564 DomTreeBuilder::InsertEdge(*this, From, To);
567 /// Inform the dominator tree about a CFG edge deletion and update the tree.
569 /// This function has to be called just after making the update on the actual
570 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
571 /// DEBUG mode. There cannot be any other updates that the
572 /// dominator tree doesn't know about.
574 /// Note that for postdominators it automatically takes care of deleting
575 /// a reverse edge internally (so there's no need to swap the parameters).
577 void deleteEdge(NodeT *From, NodeT *To) {
580 assert(From->getParent() == Parent);
581 assert(To->getParent() == Parent);
582 DomTreeBuilder::DeleteEdge(*this, From, To);
585 /// Add a new node to the dominator tree information.
587 /// This creates a new node as a child of DomBB dominator node, linking it
588 /// into the children list of the immediate dominator.
590 /// \param BB New node in CFG.
591 /// \param DomBB CFG node that is dominator for BB.
592 /// \returns New dominator tree node that represents new CFG node.
594 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
595 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
596 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
597 assert(IDomNode && "Not immediate dominator specified for block!");
598 DFSInfoValid = false;
599 return (DomTreeNodes[BB] = IDomNode->addChild(
600 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
603 /// Add a new node to the forward dominator tree and make it a new root.
605 /// \param BB New node in CFG.
606 /// \returns New dominator tree node that represents new CFG node.
608 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
609 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
610 assert(!this->isPostDominator() &&
611 "Cannot change root of post-dominator tree");
612 DFSInfoValid = false;
613 DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
614 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
618 assert(Roots.size() == 1);
619 NodeT *OldRoot = Roots.front();
620 auto &OldNode = DomTreeNodes[OldRoot];
621 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
622 OldNode->IDom = NewNode;
623 OldNode->UpdateLevel();
626 return RootNode = NewNode;
629 /// changeImmediateDominator - This method is used to update the dominator
630 /// tree information when a node's immediate dominator changes.
632 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
633 DomTreeNodeBase<NodeT> *NewIDom) {
634 assert(N && NewIDom && "Cannot change null node pointers!");
635 DFSInfoValid = false;
639 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
640 changeImmediateDominator(getNode(BB), getNode(NewBB));
643 /// eraseNode - Removes a node from the dominator tree. Block must not
644 /// dominate any other blocks. Removes node from its immediate dominator's
645 /// children list. Deletes dominator node associated with basic block BB.
646 void eraseNode(NodeT *BB) {
647 DomTreeNodeBase<NodeT> *Node = getNode(BB);
648 assert(Node && "Removing node that isn't in dominator tree.");
649 assert(Node->getChildren().empty() && "Node is not a leaf node.");
651 DFSInfoValid = false;
653 // Remove node from immediate dominator's children list.
654 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
656 const auto I = find(IDom->Children, Node);
657 assert(I != IDom->Children.end() &&
658 "Not in immediate dominator children set!");
659 // I am no longer your child...
660 IDom->Children.erase(I);
663 DomTreeNodes.erase(BB);
665 if (!IsPostDom) return;
667 // Remember to update PostDominatorTree roots.
668 auto RIt = llvm::find(Roots, BB);
669 if (RIt != Roots.end()) {
670 std::swap(*RIt, Roots.back());
675 /// splitBlock - BB is split and now it has one successor. Update dominator
676 /// tree to reflect this change.
677 void splitBlock(NodeT *NewBB) {
679 Split<Inverse<NodeT *>>(NewBB);
681 Split<NodeT *>(NewBB);
684 /// print - Convert to human readable form
686 void print(raw_ostream &O) const {
687 O << "=============================--------------------------------\n";
689 O << "Inorder PostDominator Tree: ";
691 O << "Inorder Dominator Tree: ";
693 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
696 // The postdom tree can have a null root if there are no returns.
697 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
698 if (IsPostDominator) {
700 for (const NodePtr Block : Roots) {
701 Block->printAsOperand(O, false);
709 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
710 /// dominator tree in dfs order.
711 void updateDFSNumbers() const {
717 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
718 typename DomTreeNodeBase<NodeT>::const_iterator>,
721 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
722 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
726 // Both dominators and postdominators have a single root node. In the case
727 // case of PostDominatorTree, this node is a virtual root.
728 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
731 ThisRoot->DFSNumIn = DFSNum++;
733 while (!WorkStack.empty()) {
734 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
735 const auto ChildIt = WorkStack.back().second;
737 // If we visited all of the children of this node, "recurse" back up the
738 // stack setting the DFOutNum.
739 if (ChildIt == Node->end()) {
740 Node->DFSNumOut = DFSNum++;
741 WorkStack.pop_back();
743 // Otherwise, recursively visit this child.
744 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
745 ++WorkStack.back().second;
747 WorkStack.push_back({Child, Child->begin()});
748 Child->DFSNumIn = DFSNum++;
756 /// recalculate - compute a dominator tree for the given function
757 void recalculate(ParentType &Func) {
759 DomTreeBuilder::Calculate(*this);
762 /// verify - checks if the tree is correct. There are 3 level of verification:
763 /// - Full -- verifies if the tree is correct by making sure all the
764 /// properties (including the parent and the sibling property)
766 /// Takes O(N^3) time.
768 /// - Basic -- checks if the tree is correct, but compares it to a freshly
769 /// constructed tree instead of checking the sibling property.
770 /// Takes O(N^2) time.
772 /// - Fast -- checks basic tree structure and compares it with a freshly
773 /// constructed tree.
774 /// Takes O(N^2) time worst case, but is faster in practise (same
775 /// as tree construction).
776 bool verify(VerificationLevel VL = VerificationLevel::Full) const {
777 return DomTreeBuilder::Verify(*this, VL);
781 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
784 DomTreeNodes.clear();
788 DFSInfoValid = false;
792 // NewBB is split and now it has one successor. Update dominator tree to
793 // reflect this change.
795 void Split(typename GraphTraits<N>::NodeRef NewBB) {
796 using GraphT = GraphTraits<N>;
797 using NodeRef = typename GraphT::NodeRef;
798 assert(std::distance(GraphT::child_begin(NewBB),
799 GraphT::child_end(NewBB)) == 1 &&
800 "NewBB should have a single successor!");
801 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
803 std::vector<NodeRef> PredBlocks;
804 for (const auto &Pred : children<Inverse<N>>(NewBB))
805 PredBlocks.push_back(Pred);
807 assert(!PredBlocks.empty() && "No predblocks?");
809 bool NewBBDominatesNewBBSucc = true;
810 for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
811 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
812 isReachableFromEntry(Pred)) {
813 NewBBDominatesNewBBSucc = false;
818 // Find NewBB's immediate dominator and create new dominator tree node for
820 NodeT *NewBBIDom = nullptr;
822 for (i = 0; i < PredBlocks.size(); ++i)
823 if (isReachableFromEntry(PredBlocks[i])) {
824 NewBBIDom = PredBlocks[i];
828 // It's possible that none of the predecessors of NewBB are reachable;
829 // in that case, NewBB itself is unreachable, so nothing needs to be
831 if (!NewBBIDom) return;
833 for (i = i + 1; i < PredBlocks.size(); ++i) {
834 if (isReachableFromEntry(PredBlocks[i]))
835 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
838 // Create the new dominator tree node... and set the idom of NewBB.
839 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
841 // If NewBB strictly dominates other blocks, then it is now the immediate
842 // dominator of NewBBSucc. Update the dominator tree as appropriate.
843 if (NewBBDominatesNewBBSucc) {
844 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
845 changeImmediateDominator(NewBBSuccNode, NewBBNode);
850 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
851 const DomTreeNodeBase<NodeT> *B) const {
853 assert(isReachableFromEntry(B));
854 assert(isReachableFromEntry(A));
856 const unsigned ALevel = A->getLevel();
857 const DomTreeNodeBase<NodeT> *IDom;
859 // Don't walk nodes above A's subtree. When we reach A's level, we must
860 // either find A or be in some other subtree not dominated by A.
861 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
862 B = IDom; // Walk up the tree
867 /// Wipe this tree's state without releasing any resources.
869 /// This is essentially a post-move helper only. It leaves the object in an
870 /// assignable and destroyable state, but otherwise invalid.
872 DomTreeNodes.clear();
878 template <typename T>
879 using DomTreeBase = DominatorTreeBase<T, false>;
881 template <typename T>
882 using PostDomTreeBase = DominatorTreeBase<T, true>;
884 // These two functions are declared out of line as a workaround for building
885 // with old (< r147295) versions of clang because of pr11642.
886 template <typename NodeT, bool IsPostDom>
887 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
888 const NodeT *B) const {
892 // Cast away the const qualifiers here. This is ok since
893 // this function doesn't actually return the values returned
895 return dominates(getNode(const_cast<NodeT *>(A)),
896 getNode(const_cast<NodeT *>(B)));
898 template <typename NodeT, bool IsPostDom>
899 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
900 const NodeT *A, const NodeT *B) const {
904 // Cast away the const qualifiers here. This is ok since
905 // this function doesn't actually return the values returned
907 return dominates(getNode(const_cast<NodeT *>(A)),
908 getNode(const_cast<NodeT *>(B)));
911 } // end namespace llvm
913 #endif // LLVM_SUPPORT_GENERICDOMTREE_H