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
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/GraphTraits.h"
29 #include "llvm/ADT/PointerIntPair.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/Support/CFGUpdate.h"
34 #include "llvm/Support/raw_ostream.h"
40 #include <type_traits>
46 template <typename NodeT, bool IsPostDom>
47 class DominatorTreeBase;
49 namespace DomTreeBuilder {
50 template <typename DomTreeT>
52 } // namespace DomTreeBuilder
54 /// Base class for the actual dominator tree node.
55 template <class NodeT> class DomTreeNodeBase {
56 friend class PostDominatorTree;
57 friend class DominatorTreeBase<NodeT, false>;
58 friend class DominatorTreeBase<NodeT, true>;
59 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
60 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
63 DomTreeNodeBase *IDom;
65 std::vector<DomTreeNodeBase *> Children;
66 mutable unsigned DFSNumIn = ~0;
67 mutable unsigned DFSNumOut = ~0;
70 DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
71 : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
73 using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
74 using const_iterator =
75 typename std::vector<DomTreeNodeBase *>::const_iterator;
77 iterator begin() { return Children.begin(); }
78 iterator end() { return Children.end(); }
79 const_iterator begin() const { return Children.begin(); }
80 const_iterator end() const { return Children.end(); }
82 NodeT *getBlock() const { return TheBB; }
83 DomTreeNodeBase *getIDom() const { return IDom; }
84 unsigned getLevel() const { return Level; }
86 const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
88 std::unique_ptr<DomTreeNodeBase> addChild(
89 std::unique_ptr<DomTreeNodeBase> C) {
90 Children.push_back(C.get());
94 size_t getNumChildren() const { return Children.size(); }
96 void clearAllChildren() { Children.clear(); }
98 bool compare(const DomTreeNodeBase *Other) const {
99 if (getNumChildren() != Other->getNumChildren())
102 if (Level != Other->Level) return true;
104 SmallPtrSet<const NodeT *, 4> OtherChildren;
105 for (const DomTreeNodeBase *I : *Other) {
106 const NodeT *Nd = I->getBlock();
107 OtherChildren.insert(Nd);
110 for (const DomTreeNodeBase *I : *this) {
111 const NodeT *N = I->getBlock();
112 if (OtherChildren.count(N) == 0)
118 void setIDom(DomTreeNodeBase *NewIDom) {
119 assert(IDom && "No immediate dominator?");
120 if (IDom == NewIDom) return;
122 auto I = find(IDom->Children, this);
123 assert(I != IDom->Children.end() &&
124 "Not in immediate dominator children set!");
125 // I am no longer your child...
126 IDom->Children.erase(I);
128 // Switch to new dominator
130 IDom->Children.push_back(this);
135 /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
136 /// in the dominator tree. They are only guaranteed valid if
137 /// updateDFSNumbers() has been called.
138 unsigned getDFSNumIn() const { return DFSNumIn; }
139 unsigned getDFSNumOut() const { return DFSNumOut; }
142 // Return true if this node is dominated by other. Use this only if DFS info
144 bool DominatedBy(const DomTreeNodeBase *other) const {
145 return this->DFSNumIn >= other->DFSNumIn &&
146 this->DFSNumOut <= other->DFSNumOut;
151 if (Level == IDom->Level + 1) return;
153 SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
155 while (!WorkStack.empty()) {
156 DomTreeNodeBase *Current = WorkStack.pop_back_val();
157 Current->Level = Current->IDom->Level + 1;
159 for (DomTreeNodeBase *C : *Current) {
161 if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
167 template <class NodeT>
168 raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
169 if (Node->getBlock())
170 Node->getBlock()->printAsOperand(O, false);
172 O << " <<exit node>>";
174 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
175 << Node->getLevel() << "]\n";
180 template <class NodeT>
181 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
183 O.indent(2 * Lev) << "[" << Lev << "] " << N;
184 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
187 PrintDomTree<NodeT>(*I, O, Lev + 1);
190 namespace DomTreeBuilder {
191 // The routines below are provided in a separate header but referenced here.
192 template <typename DomTreeT>
193 void Calculate(DomTreeT &DT);
195 template <typename DomTreeT>
196 void CalculateWithUpdates(DomTreeT &DT,
197 ArrayRef<typename DomTreeT::UpdateType> Updates);
199 template <typename DomTreeT>
200 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
201 typename DomTreeT::NodePtr To);
203 template <typename DomTreeT>
204 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
205 typename DomTreeT::NodePtr To);
207 template <typename DomTreeT>
208 void ApplyUpdates(DomTreeT &DT,
209 ArrayRef<typename DomTreeT::UpdateType> Updates);
211 template <typename DomTreeT>
212 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
213 } // namespace DomTreeBuilder
215 /// Core dominator tree base class.
217 /// This class is a generic template over graph nodes. It is instantiated for
218 /// various graphs in the LLVM IR or in the code generator.
219 template <typename NodeT, bool IsPostDom>
220 class DominatorTreeBase {
222 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
223 "Currently DominatorTreeBase supports only pointer nodes");
224 using NodeType = NodeT;
225 using NodePtr = NodeT *;
226 using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
227 static_assert(std::is_pointer<ParentPtr>::value,
228 "Currently NodeT's parent must be a pointer type");
229 using ParentType = typename std::remove_pointer<ParentPtr>::type;
230 static constexpr bool IsPostDominator = IsPostDom;
232 using UpdateType = cfg::Update<NodePtr>;
233 using UpdateKind = cfg::UpdateKind;
234 static constexpr UpdateKind Insert = UpdateKind::Insert;
235 static constexpr UpdateKind Delete = UpdateKind::Delete;
237 enum class VerificationLevel { Fast, Basic, Full };
240 // Dominators always have a single root, postdominators can have more.
241 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
243 using DomTreeNodeMapType =
244 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
245 DomTreeNodeMapType DomTreeNodes;
246 DomTreeNodeBase<NodeT> *RootNode;
247 ParentPtr Parent = nullptr;
249 mutable bool DFSInfoValid = false;
250 mutable unsigned int SlowQueries = 0;
252 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
255 DominatorTreeBase() {}
257 DominatorTreeBase(DominatorTreeBase &&Arg)
258 : Roots(std::move(Arg.Roots)),
259 DomTreeNodes(std::move(Arg.DomTreeNodes)),
260 RootNode(Arg.RootNode),
262 DFSInfoValid(Arg.DFSInfoValid),
263 SlowQueries(Arg.SlowQueries) {
267 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
268 Roots = std::move(RHS.Roots);
269 DomTreeNodes = std::move(RHS.DomTreeNodes);
270 RootNode = RHS.RootNode;
272 DFSInfoValid = RHS.DFSInfoValid;
273 SlowQueries = RHS.SlowQueries;
278 DominatorTreeBase(const DominatorTreeBase &) = delete;
279 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
281 /// getRoots - Return the root blocks of the current CFG. This may include
282 /// multiple blocks if we are computing post dominators. For forward
283 /// dominators, this will always be a single block (the entry node).
285 const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
287 /// isPostDominator - Returns true if analysis based of postdoms
289 bool isPostDominator() const { return IsPostDominator; }
291 /// compare - Return false if the other dominator tree base matches this
292 /// dominator tree base. Otherwise return true.
293 bool compare(const DominatorTreeBase &Other) const {
294 if (Parent != Other.Parent) return true;
296 if (Roots.size() != Other.Roots.size())
299 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
302 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
303 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
306 for (const auto &DomTreeNode : DomTreeNodes) {
307 NodeT *BB = DomTreeNode.first;
308 typename DomTreeNodeMapType::const_iterator OI =
309 OtherDomTreeNodes.find(BB);
310 if (OI == OtherDomTreeNodes.end())
313 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
314 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
316 if (MyNd.compare(&OtherNd))
323 void releaseMemory() { reset(); }
325 /// getNode - return the (Post)DominatorTree node for the specified basic
326 /// block. This is the same as using operator[] on this class. The result
327 /// may (but is not required to) be null for a forward (backwards)
328 /// statically unreachable block.
329 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
330 auto I = DomTreeNodes.find(BB);
331 if (I != DomTreeNodes.end())
332 return I->second.get();
337 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
341 /// getRootNode - This returns the entry node for the CFG of the function. If
342 /// this tree represents the post-dominance relations for a function, however,
343 /// this root may be a node with the block == NULL. This is the case when
344 /// there are multiple exit nodes from a particular function. Consumers of
345 /// post-dominance information must be capable of dealing with this
348 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
349 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
351 /// Get all nodes dominated by R, including R itself.
352 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
354 const DomTreeNodeBase<NodeT> *RN = getNode(R);
356 return; // If R is unreachable, it will not be present in the DOM tree.
357 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
360 while (!WL.empty()) {
361 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
362 Result.push_back(N->getBlock());
363 WL.append(N->begin(), N->end());
367 /// properlyDominates - Returns true iff A dominates B and A != B.
368 /// Note that this is not a constant time operation!
370 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
371 const DomTreeNodeBase<NodeT> *B) const {
376 return dominates(A, B);
379 bool properlyDominates(const NodeT *A, const NodeT *B) const;
381 /// isReachableFromEntry - Return true if A is dominated by the entry
382 /// block of the function containing it.
383 bool isReachableFromEntry(const NodeT *A) const {
384 assert(!this->isPostDominator() &&
385 "This is not implemented for post dominators");
386 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
389 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
391 /// dominates - Returns true iff A dominates B. Note that this is not a
392 /// constant time operation!
394 bool dominates(const DomTreeNodeBase<NodeT> *A,
395 const DomTreeNodeBase<NodeT> *B) const {
396 // A node trivially dominates itself.
400 // An unreachable node is dominated by anything.
401 if (!isReachableFromEntry(B))
404 // And dominates nothing.
405 if (!isReachableFromEntry(A))
408 if (B->getIDom() == A) return true;
410 if (A->getIDom() == B) return false;
412 // A can only dominate B if it is higher in the tree.
413 if (A->getLevel() >= B->getLevel()) return false;
415 // Compare the result of the tree walk and the dfs numbers, if expensive
416 // checks are enabled.
417 #ifdef EXPENSIVE_CHECKS
418 assert((!DFSInfoValid ||
419 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
420 "Tree walk disagrees with dfs numbers!");
424 return B->DominatedBy(A);
426 // If we end up with too many slow queries, just update the
427 // DFS numbers on the theory that we are going to keep querying.
429 if (SlowQueries > 32) {
431 return B->DominatedBy(A);
434 return dominatedBySlowTreeWalk(A, B);
437 bool dominates(const NodeT *A, const NodeT *B) const;
439 NodeT *getRoot() const {
440 assert(this->Roots.size() == 1 && "Should always have entry node!");
441 return this->Roots[0];
444 /// findNearestCommonDominator - Find nearest common dominator basic block
445 /// for basic block A and B. If there is no such block then return nullptr.
446 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
447 assert(A && B && "Pointers are not valid");
448 assert(A->getParent() == B->getParent() &&
449 "Two blocks are not in same function");
451 // If either A or B is a entry block then it is nearest common dominator
452 // (for forward-dominators).
453 if (!isPostDominator()) {
454 NodeT &Entry = A->getParent()->front();
455 if (A == &Entry || B == &Entry)
459 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
460 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
462 if (!NodeA || !NodeB) return nullptr;
464 // Use level information to go up the tree until the levels match. Then
465 // continue going up til we arrive at the same node.
466 while (NodeA && NodeA != NodeB) {
467 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
472 return NodeA ? NodeA->getBlock() : nullptr;
475 const NodeT *findNearestCommonDominator(const NodeT *A,
476 const NodeT *B) const {
477 // Cast away the const qualifiers here. This is ok since
478 // const is re-introduced on the return type.
479 return findNearestCommonDominator(const_cast<NodeT *>(A),
480 const_cast<NodeT *>(B));
483 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
484 return isPostDominator() && !A->getBlock();
487 //===--------------------------------------------------------------------===//
488 // API to update (Post)DominatorTree information based on modifications to
491 /// Inform the dominator tree about a sequence of CFG edge insertions and
492 /// deletions and perform a batch update on the tree.
494 /// This function should be used when there were multiple CFG updates after
495 /// the last dominator tree update. It takes care of performing the updates
496 /// in sync with the CFG and optimizes away the redundant operations that
497 /// cancel each other.
498 /// The functions expects the sequence of updates to be balanced. Eg.:
499 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
500 /// logically it results in a single insertions.
501 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
502 /// sense to insert the same edge twice.
504 /// What's more, the functions assumes that it's safe to ask every node in the
505 /// CFG about its children and inverse children. This implies that deletions
506 /// of CFG edges must not delete the CFG nodes before calling this function.
508 /// The applyUpdates function can reorder the updates and remove redundant
509 /// ones internally. The batch updater is also able to detect sequences of
510 /// zero and exactly one update -- it's optimized to do less work in these
513 /// Note that for postdominators it automatically takes care of applying
514 /// updates on reverse edges internally (so there's no need to swap the
515 /// From and To pointers when constructing DominatorTree::UpdateType).
516 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
517 /// with the same template parameter T.
519 /// \param Updates An unordered sequence of updates to perform.
521 void applyUpdates(ArrayRef<UpdateType> Updates) {
522 DomTreeBuilder::ApplyUpdates(*this, Updates);
525 /// Inform the dominator tree about a CFG edge insertion and update the tree.
527 /// This function has to be called just before or just after making the update
528 /// on the actual CFG. There cannot be any other updates that the dominator
529 /// tree doesn't know about.
531 /// Note that for postdominators it automatically takes care of inserting
532 /// a reverse edge internally (so there's no need to swap the parameters).
534 void insertEdge(NodeT *From, NodeT *To) {
537 assert(From->getParent() == Parent);
538 assert(To->getParent() == Parent);
539 DomTreeBuilder::InsertEdge(*this, From, To);
542 /// Inform the dominator tree about a CFG edge deletion and update the tree.
544 /// This function has to be called just after making the update on the actual
545 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
546 /// DEBUG mode. There cannot be any other updates that the
547 /// dominator tree doesn't know about.
549 /// Note that for postdominators it automatically takes care of deleting
550 /// a reverse edge internally (so there's no need to swap the parameters).
552 void deleteEdge(NodeT *From, NodeT *To) {
555 assert(From->getParent() == Parent);
556 assert(To->getParent() == Parent);
557 DomTreeBuilder::DeleteEdge(*this, From, To);
560 /// Add a new node to the dominator tree information.
562 /// This creates a new node as a child of DomBB dominator node, linking it
563 /// into the children list of the immediate dominator.
565 /// \param BB New node in CFG.
566 /// \param DomBB CFG node that is dominator for BB.
567 /// \returns New dominator tree node that represents new CFG node.
569 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
570 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
571 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
572 assert(IDomNode && "Not immediate dominator specified for block!");
573 DFSInfoValid = false;
574 return (DomTreeNodes[BB] = IDomNode->addChild(
575 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
578 /// Add a new node to the forward dominator tree and make it a new root.
580 /// \param BB New node in CFG.
581 /// \returns New dominator tree node that represents new CFG node.
583 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
584 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
585 assert(!this->isPostDominator() &&
586 "Cannot change root of post-dominator tree");
587 DFSInfoValid = false;
588 DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
589 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
593 assert(Roots.size() == 1);
594 NodeT *OldRoot = Roots.front();
595 auto &OldNode = DomTreeNodes[OldRoot];
596 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
597 OldNode->IDom = NewNode;
598 OldNode->UpdateLevel();
601 return RootNode = NewNode;
604 /// changeImmediateDominator - This method is used to update the dominator
605 /// tree information when a node's immediate dominator changes.
607 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
608 DomTreeNodeBase<NodeT> *NewIDom) {
609 assert(N && NewIDom && "Cannot change null node pointers!");
610 DFSInfoValid = false;
614 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
615 changeImmediateDominator(getNode(BB), getNode(NewBB));
618 /// eraseNode - Removes a node from the dominator tree. Block must not
619 /// dominate any other blocks. Removes node from its immediate dominator's
620 /// children list. Deletes dominator node associated with basic block BB.
621 void eraseNode(NodeT *BB) {
622 DomTreeNodeBase<NodeT> *Node = getNode(BB);
623 assert(Node && "Removing node that isn't in dominator tree.");
624 assert(Node->getChildren().empty() && "Node is not a leaf node.");
626 DFSInfoValid = false;
628 // Remove node from immediate dominator's children list.
629 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
631 const auto I = find(IDom->Children, Node);
632 assert(I != IDom->Children.end() &&
633 "Not in immediate dominator children set!");
634 // I am no longer your child...
635 IDom->Children.erase(I);
638 DomTreeNodes.erase(BB);
640 if (!IsPostDom) return;
642 // Remember to update PostDominatorTree roots.
643 auto RIt = llvm::find(Roots, BB);
644 if (RIt != Roots.end()) {
645 std::swap(*RIt, Roots.back());
650 /// splitBlock - BB is split and now it has one successor. Update dominator
651 /// tree to reflect this change.
652 void splitBlock(NodeT *NewBB) {
654 Split<Inverse<NodeT *>>(NewBB);
656 Split<NodeT *>(NewBB);
659 /// print - Convert to human readable form
661 void print(raw_ostream &O) const {
662 O << "=============================--------------------------------\n";
664 O << "Inorder PostDominator Tree: ";
666 O << "Inorder Dominator Tree: ";
668 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
671 // The postdom tree can have a null root if there are no returns.
672 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
673 if (IsPostDominator) {
675 for (const NodePtr Block : Roots) {
676 Block->printAsOperand(O, false);
684 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
685 /// dominator tree in dfs order.
686 void updateDFSNumbers() const {
692 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
693 typename DomTreeNodeBase<NodeT>::const_iterator>,
696 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
697 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
701 // Both dominators and postdominators have a single root node. In the case
702 // case of PostDominatorTree, this node is a virtual root.
703 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
706 ThisRoot->DFSNumIn = DFSNum++;
708 while (!WorkStack.empty()) {
709 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
710 const auto ChildIt = WorkStack.back().second;
712 // If we visited all of the children of this node, "recurse" back up the
713 // stack setting the DFOutNum.
714 if (ChildIt == Node->end()) {
715 Node->DFSNumOut = DFSNum++;
716 WorkStack.pop_back();
718 // Otherwise, recursively visit this child.
719 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
720 ++WorkStack.back().second;
722 WorkStack.push_back({Child, Child->begin()});
723 Child->DFSNumIn = DFSNum++;
731 /// recalculate - compute a dominator tree for the given function
732 void recalculate(ParentType &Func) {
734 DomTreeBuilder::Calculate(*this);
737 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
739 DomTreeBuilder::CalculateWithUpdates(*this, Updates);
742 /// verify - checks if the tree is correct. There are 3 level of verification:
743 /// - Full -- verifies if the tree is correct by making sure all the
744 /// properties (including the parent and the sibling property)
746 /// Takes O(N^3) time.
748 /// - Basic -- checks if the tree is correct, but compares it to a freshly
749 /// constructed tree instead of checking the sibling property.
750 /// Takes O(N^2) time.
752 /// - Fast -- checks basic tree structure and compares it with a freshly
753 /// constructed tree.
754 /// Takes O(N^2) time worst case, but is faster in practise (same
755 /// as tree construction).
756 bool verify(VerificationLevel VL = VerificationLevel::Full) const {
757 return DomTreeBuilder::Verify(*this, VL);
761 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
764 DomTreeNodes.clear();
768 DFSInfoValid = false;
772 // NewBB is split and now it has one successor. Update dominator tree to
773 // reflect this change.
775 void Split(typename GraphTraits<N>::NodeRef NewBB) {
776 using GraphT = GraphTraits<N>;
777 using NodeRef = typename GraphT::NodeRef;
778 assert(std::distance(GraphT::child_begin(NewBB),
779 GraphT::child_end(NewBB)) == 1 &&
780 "NewBB should have a single successor!");
781 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
783 std::vector<NodeRef> PredBlocks;
784 for (const auto &Pred : children<Inverse<N>>(NewBB))
785 PredBlocks.push_back(Pred);
787 assert(!PredBlocks.empty() && "No predblocks?");
789 bool NewBBDominatesNewBBSucc = true;
790 for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
791 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
792 isReachableFromEntry(Pred)) {
793 NewBBDominatesNewBBSucc = false;
798 // Find NewBB's immediate dominator and create new dominator tree node for
800 NodeT *NewBBIDom = nullptr;
802 for (i = 0; i < PredBlocks.size(); ++i)
803 if (isReachableFromEntry(PredBlocks[i])) {
804 NewBBIDom = PredBlocks[i];
808 // It's possible that none of the predecessors of NewBB are reachable;
809 // in that case, NewBB itself is unreachable, so nothing needs to be
811 if (!NewBBIDom) return;
813 for (i = i + 1; i < PredBlocks.size(); ++i) {
814 if (isReachableFromEntry(PredBlocks[i]))
815 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
818 // Create the new dominator tree node... and set the idom of NewBB.
819 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
821 // If NewBB strictly dominates other blocks, then it is now the immediate
822 // dominator of NewBBSucc. Update the dominator tree as appropriate.
823 if (NewBBDominatesNewBBSucc) {
824 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
825 changeImmediateDominator(NewBBSuccNode, NewBBNode);
830 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
831 const DomTreeNodeBase<NodeT> *B) const {
833 assert(isReachableFromEntry(B));
834 assert(isReachableFromEntry(A));
836 const unsigned ALevel = A->getLevel();
837 const DomTreeNodeBase<NodeT> *IDom;
839 // Don't walk nodes above A's subtree. When we reach A's level, we must
840 // either find A or be in some other subtree not dominated by A.
841 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
842 B = IDom; // Walk up the tree
847 /// Wipe this tree's state without releasing any resources.
849 /// This is essentially a post-move helper only. It leaves the object in an
850 /// assignable and destroyable state, but otherwise invalid.
852 DomTreeNodes.clear();
858 template <typename T>
859 using DomTreeBase = DominatorTreeBase<T, false>;
861 template <typename T>
862 using PostDomTreeBase = DominatorTreeBase<T, true>;
864 // These two functions are declared out of line as a workaround for building
865 // with old (< r147295) versions of clang because of pr11642.
866 template <typename NodeT, bool IsPostDom>
867 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
868 const NodeT *B) const {
872 // Cast away the const qualifiers here. This is ok since
873 // this function doesn't actually return the values returned
875 return dominates(getNode(const_cast<NodeT *>(A)),
876 getNode(const_cast<NodeT *>(B)));
878 template <typename NodeT, bool IsPostDom>
879 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
880 const NodeT *A, const NodeT *B) const {
884 // Cast away the const qualifiers here. This is ok since
885 // this function doesn't actually return the values returned
887 return dominates(getNode(const_cast<NodeT *>(A)),
888 getNode(const_cast<NodeT *>(B)));
891 } // end namespace llvm
893 #endif // LLVM_SUPPORT_GENERICDOMTREE_H