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 /// \brief Base class for the actual dominator tree node.
54 template <class NodeT> class DomTreeNodeBase {
55 friend struct 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);
238 } // namespace DomTreeBuilder
240 /// \brief 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;
263 // Dominators always have a single root, postdominators can have more.
264 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
266 using DomTreeNodeMapType =
267 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
268 DomTreeNodeMapType DomTreeNodes;
269 DomTreeNodeBase<NodeT> *RootNode;
270 ParentPtr Parent = nullptr;
272 mutable bool DFSInfoValid = false;
273 mutable unsigned int SlowQueries = 0;
275 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
278 DominatorTreeBase() {}
280 DominatorTreeBase(DominatorTreeBase &&Arg)
281 : Roots(std::move(Arg.Roots)),
282 DomTreeNodes(std::move(Arg.DomTreeNodes)),
283 RootNode(Arg.RootNode),
285 DFSInfoValid(Arg.DFSInfoValid),
286 SlowQueries(Arg.SlowQueries) {
290 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
291 Roots = std::move(RHS.Roots);
292 DomTreeNodes = std::move(RHS.DomTreeNodes);
293 RootNode = RHS.RootNode;
295 DFSInfoValid = RHS.DFSInfoValid;
296 SlowQueries = RHS.SlowQueries;
301 DominatorTreeBase(const DominatorTreeBase &) = delete;
302 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
304 /// getRoots - Return the root blocks of the current CFG. This may include
305 /// multiple blocks if we are computing post dominators. For forward
306 /// dominators, this will always be a single block (the entry node).
308 const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
310 /// isPostDominator - Returns true if analysis based of postdoms
312 bool isPostDominator() const { return IsPostDominator; }
314 /// compare - Return false if the other dominator tree base matches this
315 /// dominator tree base. Otherwise return true.
316 bool compare(const DominatorTreeBase &Other) const {
317 if (Parent != Other.Parent) return true;
319 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
320 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
323 for (const auto &DomTreeNode : DomTreeNodes) {
324 NodeT *BB = DomTreeNode.first;
325 typename DomTreeNodeMapType::const_iterator OI =
326 OtherDomTreeNodes.find(BB);
327 if (OI == OtherDomTreeNodes.end())
330 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
331 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
333 if (MyNd.compare(&OtherNd))
340 void releaseMemory() { reset(); }
342 /// getNode - return the (Post)DominatorTree node for the specified basic
343 /// block. This is the same as using operator[] on this class. The result
344 /// may (but is not required to) be null for a forward (backwards)
345 /// statically unreachable block.
346 DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
347 auto I = DomTreeNodes.find(BB);
348 if (I != DomTreeNodes.end())
349 return I->second.get();
354 DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); }
356 /// getRootNode - This returns the entry node for the CFG of the function. If
357 /// this tree represents the post-dominance relations for a function, however,
358 /// this root may be a node with the block == NULL. This is the case when
359 /// there are multiple exit nodes from a particular function. Consumers of
360 /// post-dominance information must be capable of dealing with this
363 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
364 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
366 /// Get all nodes dominated by R, including R itself.
367 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
369 const DomTreeNodeBase<NodeT> *RN = getNode(R);
371 return; // If R is unreachable, it will not be present in the DOM tree.
372 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
375 while (!WL.empty()) {
376 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
377 Result.push_back(N->getBlock());
378 WL.append(N->begin(), N->end());
382 /// properlyDominates - Returns true iff A dominates B and A != B.
383 /// Note that this is not a constant time operation!
385 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
386 const DomTreeNodeBase<NodeT> *B) const {
391 return dominates(A, B);
394 bool properlyDominates(const NodeT *A, const NodeT *B) const;
396 /// isReachableFromEntry - Return true if A is dominated by the entry
397 /// block of the function containing it.
398 bool isReachableFromEntry(const NodeT *A) const {
399 assert(!this->isPostDominator() &&
400 "This is not implemented for post dominators");
401 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
404 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
406 /// dominates - Returns true iff A dominates B. Note that this is not a
407 /// constant time operation!
409 bool dominates(const DomTreeNodeBase<NodeT> *A,
410 const DomTreeNodeBase<NodeT> *B) const {
411 // A node trivially dominates itself.
415 // An unreachable node is dominated by anything.
416 if (!isReachableFromEntry(B))
419 // And dominates nothing.
420 if (!isReachableFromEntry(A))
423 if (B->getIDom() == A) return true;
425 if (A->getIDom() == B) return false;
427 // A can only dominate B if it is higher in the tree.
428 if (A->getLevel() >= B->getLevel()) return false;
430 // Compare the result of the tree walk and the dfs numbers, if expensive
431 // checks are enabled.
432 #ifdef EXPENSIVE_CHECKS
433 assert((!DFSInfoValid ||
434 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
435 "Tree walk disagrees with dfs numbers!");
439 return B->DominatedBy(A);
441 // If we end up with too many slow queries, just update the
442 // DFS numbers on the theory that we are going to keep querying.
444 if (SlowQueries > 32) {
446 return B->DominatedBy(A);
449 return dominatedBySlowTreeWalk(A, B);
452 bool dominates(const NodeT *A, const NodeT *B) const;
454 NodeT *getRoot() const {
455 assert(this->Roots.size() == 1 && "Should always have entry node!");
456 return this->Roots[0];
459 /// findNearestCommonDominator - Find nearest common dominator basic block
460 /// for basic block A and B. If there is no such block then return nullptr.
461 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
462 assert(A && B && "Pointers are not valid");
463 assert(A->getParent() == B->getParent() &&
464 "Two blocks are not in same function");
466 // If either A or B is a entry block then it is nearest common dominator
467 // (for forward-dominators).
468 if (!isPostDominator()) {
469 NodeT &Entry = A->getParent()->front();
470 if (A == &Entry || B == &Entry)
474 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
475 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
477 if (!NodeA || !NodeB) return nullptr;
479 // Use level information to go up the tree until the levels match. Then
480 // continue going up til we arrive at the same node.
481 while (NodeA && NodeA != NodeB) {
482 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
487 return NodeA ? NodeA->getBlock() : nullptr;
490 const NodeT *findNearestCommonDominator(const NodeT *A,
491 const NodeT *B) const {
492 // Cast away the const qualifiers here. This is ok since
493 // const is re-introduced on the return type.
494 return findNearestCommonDominator(const_cast<NodeT *>(A),
495 const_cast<NodeT *>(B));
498 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
499 return isPostDominator() && !A->getBlock();
502 //===--------------------------------------------------------------------===//
503 // API to update (Post)DominatorTree information based on modifications to
506 /// Inform the dominator tree about a sequence of CFG edge insertions and
507 /// deletions and perform a batch update on the tree.
509 /// This function should be used when there were multiple CFG updates after
510 /// the last dominator tree update. It takes care of performing the updates
511 /// in sync with the CFG and optimizes away the redundant operations that
512 /// cancel each other.
513 /// The functions expects the sequence of updates to be balanced. Eg.:
514 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
515 /// logically it results in a single insertions.
516 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
517 /// sense to insert the same edge twice.
519 /// What's more, the functions assumes that it's safe to ask every node in the
520 /// CFG about its children and inverse children. This implies that deletions
521 /// of CFG edges must not delete the CFG nodes before calling this function.
523 /// Batch updates should be generally faster when performing longer sequences
524 /// of updates than calling insertEdge/deleteEdge manually multiple times, as
525 /// it can reorder the updates and remove redundant ones internally.
526 /// The batch updater is also able to detect sequences of zero and exactly one
527 /// update -- it's optimized to do less work in these cases.
529 /// Note that for postdominators it automatically takes care of applying
530 /// updates on reverse edges internally (so there's no need to swap the
531 /// From and To pointers when constructing DominatorTree::UpdateType).
532 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
533 /// with the same template parameter T.
535 /// \param Updates An unordered sequence of updates to perform.
537 void applyUpdates(ArrayRef<UpdateType> Updates) {
538 DomTreeBuilder::ApplyUpdates(*this, Updates);
541 /// Inform the dominator tree about a CFG edge insertion and update the tree.
543 /// This function has to be called just before or just after making the update
544 /// on the actual CFG. There cannot be any other updates that the dominator
545 /// tree doesn't know about.
547 /// Note that for postdominators it automatically takes care of inserting
548 /// a reverse edge internally (so there's no need to swap the parameters).
550 void insertEdge(NodeT *From, NodeT *To) {
553 assert(From->getParent() == Parent);
554 assert(To->getParent() == Parent);
555 DomTreeBuilder::InsertEdge(*this, From, To);
558 /// Inform the dominator tree about a CFG edge deletion and update the tree.
560 /// This function has to be called just after making the update on the actual
561 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
562 /// DEBUG mode. There cannot be any other updates that the
563 /// dominator tree doesn't know about.
565 /// Note that for postdominators it automatically takes care of deleting
566 /// a reverse edge internally (so there's no need to swap the parameters).
568 void deleteEdge(NodeT *From, NodeT *To) {
571 assert(From->getParent() == Parent);
572 assert(To->getParent() == Parent);
573 DomTreeBuilder::DeleteEdge(*this, From, To);
576 /// Add a new node to the dominator tree information.
578 /// This creates a new node as a child of DomBB dominator node, linking it
579 /// into the children list of the immediate dominator.
581 /// \param BB New node in CFG.
582 /// \param DomBB CFG node that is dominator for BB.
583 /// \returns New dominator tree node that represents new CFG node.
585 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
586 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
587 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
588 assert(IDomNode && "Not immediate dominator specified for block!");
589 DFSInfoValid = false;
590 return (DomTreeNodes[BB] = IDomNode->addChild(
591 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
594 /// Add a new node to the forward dominator tree and make it a new root.
596 /// \param BB New node in CFG.
597 /// \returns New dominator tree node that represents new CFG node.
599 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
600 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
601 assert(!this->isPostDominator() &&
602 "Cannot change root of post-dominator tree");
603 DFSInfoValid = false;
604 DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
605 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
609 assert(Roots.size() == 1);
610 NodeT *OldRoot = Roots.front();
611 auto &OldNode = DomTreeNodes[OldRoot];
612 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
613 OldNode->IDom = NewNode;
614 OldNode->UpdateLevel();
617 return RootNode = NewNode;
620 /// changeImmediateDominator - This method is used to update the dominator
621 /// tree information when a node's immediate dominator changes.
623 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
624 DomTreeNodeBase<NodeT> *NewIDom) {
625 assert(N && NewIDom && "Cannot change null node pointers!");
626 DFSInfoValid = false;
630 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
631 changeImmediateDominator(getNode(BB), getNode(NewBB));
634 /// eraseNode - Removes a node from the dominator tree. Block must not
635 /// dominate any other blocks. Removes node from its immediate dominator's
636 /// children list. Deletes dominator node associated with basic block BB.
637 void eraseNode(NodeT *BB) {
638 DomTreeNodeBase<NodeT> *Node = getNode(BB);
639 assert(Node && "Removing node that isn't in dominator tree.");
640 assert(Node->getChildren().empty() && "Node is not a leaf node.");
642 DFSInfoValid = false;
644 // Remove node from immediate dominator's children list.
645 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
647 const auto I = find(IDom->Children, Node);
648 assert(I != IDom->Children.end() &&
649 "Not in immediate dominator children set!");
650 // I am no longer your child...
651 IDom->Children.erase(I);
654 DomTreeNodes.erase(BB);
656 if (!IsPostDom) return;
658 // Remember to update PostDominatorTree roots.
659 auto RIt = llvm::find(Roots, BB);
660 if (RIt != Roots.end()) {
661 std::swap(*RIt, Roots.back());
666 /// splitBlock - BB is split and now it has one successor. Update dominator
667 /// tree to reflect this change.
668 void splitBlock(NodeT *NewBB) {
670 Split<Inverse<NodeT *>>(NewBB);
672 Split<NodeT *>(NewBB);
675 /// print - Convert to human readable form
677 void print(raw_ostream &O) const {
678 O << "=============================--------------------------------\n";
680 O << "Inorder PostDominator Tree: ";
682 O << "Inorder Dominator Tree: ";
684 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
687 // The postdom tree can have a null root if there are no returns.
688 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
689 if (IsPostDominator) {
691 for (const NodePtr Block : Roots) {
692 Block->printAsOperand(O, false);
700 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
701 /// dominator tree in dfs order.
702 void updateDFSNumbers() const {
708 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
709 typename DomTreeNodeBase<NodeT>::const_iterator>,
712 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
713 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
717 // Both dominators and postdominators have a single root node. In the case
718 // case of PostDominatorTree, this node is a virtual root.
719 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
722 ThisRoot->DFSNumIn = DFSNum++;
724 while (!WorkStack.empty()) {
725 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
726 const auto ChildIt = WorkStack.back().second;
728 // If we visited all of the children of this node, "recurse" back up the
729 // stack setting the DFOutNum.
730 if (ChildIt == Node->end()) {
731 Node->DFSNumOut = DFSNum++;
732 WorkStack.pop_back();
734 // Otherwise, recursively visit this child.
735 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
736 ++WorkStack.back().second;
738 WorkStack.push_back({Child, Child->begin()});
739 Child->DFSNumIn = DFSNum++;
747 /// recalculate - compute a dominator tree for the given function
748 void recalculate(ParentType &Func) {
750 DomTreeBuilder::Calculate(*this);
753 /// verify - check parent and sibling property
754 bool verify() const { return DomTreeBuilder::Verify(*this); }
757 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
760 DomTreeNodes.clear();
764 DFSInfoValid = false;
768 // NewBB is split and now it has one successor. Update dominator tree to
769 // reflect this change.
771 void Split(typename GraphTraits<N>::NodeRef NewBB) {
772 using GraphT = GraphTraits<N>;
773 using NodeRef = typename GraphT::NodeRef;
774 assert(std::distance(GraphT::child_begin(NewBB),
775 GraphT::child_end(NewBB)) == 1 &&
776 "NewBB should have a single successor!");
777 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
779 std::vector<NodeRef> PredBlocks;
780 for (const auto &Pred : children<Inverse<N>>(NewBB))
781 PredBlocks.push_back(Pred);
783 assert(!PredBlocks.empty() && "No predblocks?");
785 bool NewBBDominatesNewBBSucc = true;
786 for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
787 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
788 isReachableFromEntry(Pred)) {
789 NewBBDominatesNewBBSucc = false;
794 // Find NewBB's immediate dominator and create new dominator tree node for
796 NodeT *NewBBIDom = nullptr;
798 for (i = 0; i < PredBlocks.size(); ++i)
799 if (isReachableFromEntry(PredBlocks[i])) {
800 NewBBIDom = PredBlocks[i];
804 // It's possible that none of the predecessors of NewBB are reachable;
805 // in that case, NewBB itself is unreachable, so nothing needs to be
807 if (!NewBBIDom) return;
809 for (i = i + 1; i < PredBlocks.size(); ++i) {
810 if (isReachableFromEntry(PredBlocks[i]))
811 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
814 // Create the new dominator tree node... and set the idom of NewBB.
815 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
817 // If NewBB strictly dominates other blocks, then it is now the immediate
818 // dominator of NewBBSucc. Update the dominator tree as appropriate.
819 if (NewBBDominatesNewBBSucc) {
820 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
821 changeImmediateDominator(NewBBSuccNode, NewBBNode);
826 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
827 const DomTreeNodeBase<NodeT> *B) const {
829 assert(isReachableFromEntry(B));
830 assert(isReachableFromEntry(A));
832 const DomTreeNodeBase<NodeT> *IDom;
833 while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
834 B = IDom; // Walk up the tree
835 return IDom != nullptr;
838 /// \brief Wipe this tree's state without releasing any resources.
840 /// This is essentially a post-move helper only. It leaves the object in an
841 /// assignable and destroyable state, but otherwise invalid.
843 DomTreeNodes.clear();
849 template <typename T>
850 using DomTreeBase = DominatorTreeBase<T, false>;
852 template <typename T>
853 using PostDomTreeBase = DominatorTreeBase<T, true>;
855 // These two functions are declared out of line as a workaround for building
856 // with old (< r147295) versions of clang because of pr11642.
857 template <typename NodeT, bool IsPostDom>
858 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
859 const NodeT *B) const {
863 // Cast away the const qualifiers here. This is ok since
864 // this function doesn't actually return the values returned
866 return dominates(getNode(const_cast<NodeT *>(A)),
867 getNode(const_cast<NodeT *>(B)));
869 template <typename NodeT, bool IsPostDom>
870 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
871 const NodeT *A, const NodeT *B) const {
875 // Cast away the const qualifiers here. This is ok since
876 // this function doesn't actually return the values returned
878 return dominates(getNode(const_cast<NodeT *>(A)),
879 getNode(const_cast<NodeT *>(B)));
882 } // end namespace llvm
884 #endif // LLVM_SUPPORT_GENERICDOMTREE_H