[Alignment][NFC] Convert StoreInst to MaybeAlign
[llvm-complete.git] / include / llvm / Support / GenericDomTree.h
blob9169379f746d0f0b0e5489e0d14cfa7697e4821f
1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 /// \file
9 ///
10 /// This file defines a set of templates that efficiently compute a dominator
11 /// tree over a generic graph. This is used typically in LLVM for fast
12 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
13 /// graph types.
14 ///
15 /// Unlike ADT/* graph algorithms, generic dominator tree has more requirements
16 /// on the graph's NodeRef. The NodeRef should be a pointer and,
17 /// NodeRef->getParent() must return the parent node that is also a pointer.
18 ///
19 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
20 ///
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/PointerIntPair.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/ADT/SmallPtrSet.h"
31 #include "llvm/ADT/SmallVector.h"
32 #include "llvm/Support/CFGUpdate.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include <algorithm>
35 #include <cassert>
36 #include <cstddef>
37 #include <iterator>
38 #include <memory>
39 #include <type_traits>
40 #include <utility>
41 #include <vector>
43 namespace llvm {
45 template <typename NodeT, bool IsPostDom>
46 class DominatorTreeBase;
48 namespace DomTreeBuilder {
49 template <typename DomTreeT>
50 struct SemiNCAInfo;
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>>;
61 NodeT *TheBB;
62 DomTreeNodeBase *IDom;
63 unsigned Level;
64 std::vector<DomTreeNodeBase *> Children;
65 mutable unsigned DFSNumIn = ~0;
66 mutable unsigned DFSNumOut = ~0;
68 public:
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());
90 return C;
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())
99 return true;
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)
112 return true;
114 return false;
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
128 IDom = NewIDom;
129 IDom->Children.push_back(this);
131 UpdateLevel();
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; }
140 private:
141 // Return true if this node is dominated by other. Use this only if DFS info
142 // is valid.
143 bool DominatedBy(const DomTreeNodeBase *other) const {
144 return this->DFSNumIn >= other->DFSNumIn &&
145 this->DFSNumOut <= other->DFSNumOut;
148 void UpdateLevel() {
149 assert(IDom);
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) {
159 assert(C->IDom);
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);
170 else
171 O << " <<exit node>>";
173 O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174 << Node->getLevel() << "]\n";
176 return O;
179 template <class NodeT>
180 void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
181 unsigned Lev) {
182 O.indent(2 * Lev) << "[" << Lev << "] " << N;
183 for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
184 E = N->end();
185 I != E; ++I)
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 CalculateWithUpdates(DomTreeT &DT,
196 ArrayRef<typename DomTreeT::UpdateType> Updates);
198 template <typename DomTreeT>
199 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200 typename DomTreeT::NodePtr To);
202 template <typename DomTreeT>
203 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
204 typename DomTreeT::NodePtr To);
206 template <typename DomTreeT>
207 void ApplyUpdates(DomTreeT &DT,
208 ArrayRef<typename DomTreeT::UpdateType> Updates);
210 template <typename DomTreeT>
211 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
212 } // namespace DomTreeBuilder
214 /// Core dominator tree base class.
216 /// This class is a generic template over graph nodes. It is instantiated for
217 /// various graphs in the LLVM IR or in the code generator.
218 template <typename NodeT, bool IsPostDom>
219 class DominatorTreeBase {
220 public:
221 static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
222 "Currently DominatorTreeBase supports only pointer nodes");
223 using NodeType = NodeT;
224 using NodePtr = NodeT *;
225 using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
226 static_assert(std::is_pointer<ParentPtr>::value,
227 "Currently NodeT's parent must be a pointer type");
228 using ParentType = typename std::remove_pointer<ParentPtr>::type;
229 static constexpr bool IsPostDominator = IsPostDom;
231 using UpdateType = cfg::Update<NodePtr>;
232 using UpdateKind = cfg::UpdateKind;
233 static constexpr UpdateKind Insert = UpdateKind::Insert;
234 static constexpr UpdateKind Delete = UpdateKind::Delete;
236 enum class VerificationLevel { Fast, Basic, Full };
238 protected:
239 // Dominators always have a single root, postdominators can have more.
240 SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
242 using DomTreeNodeMapType =
243 DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
244 DomTreeNodeMapType DomTreeNodes;
245 DomTreeNodeBase<NodeT> *RootNode = nullptr;
246 ParentPtr Parent = nullptr;
248 mutable bool DFSInfoValid = false;
249 mutable unsigned int SlowQueries = 0;
251 friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
253 public:
254 DominatorTreeBase() {}
256 DominatorTreeBase(DominatorTreeBase &&Arg)
257 : Roots(std::move(Arg.Roots)),
258 DomTreeNodes(std::move(Arg.DomTreeNodes)),
259 RootNode(Arg.RootNode),
260 Parent(Arg.Parent),
261 DFSInfoValid(Arg.DFSInfoValid),
262 SlowQueries(Arg.SlowQueries) {
263 Arg.wipe();
266 DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
267 Roots = std::move(RHS.Roots);
268 DomTreeNodes = std::move(RHS.DomTreeNodes);
269 RootNode = RHS.RootNode;
270 Parent = RHS.Parent;
271 DFSInfoValid = RHS.DFSInfoValid;
272 SlowQueries = RHS.SlowQueries;
273 RHS.wipe();
274 return *this;
277 DominatorTreeBase(const DominatorTreeBase &) = delete;
278 DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
280 /// getRoots - Return the root blocks of the current CFG. This may include
281 /// multiple blocks if we are computing post dominators. For forward
282 /// dominators, this will always be a single block (the entry node).
284 const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
286 /// isPostDominator - Returns true if analysis based of postdoms
288 bool isPostDominator() const { return IsPostDominator; }
290 /// compare - Return false if the other dominator tree base matches this
291 /// dominator tree base. Otherwise return true.
292 bool compare(const DominatorTreeBase &Other) const {
293 if (Parent != Other.Parent) return true;
295 if (Roots.size() != Other.Roots.size())
296 return true;
298 if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299 return true;
301 const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302 if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303 return true;
305 for (const auto &DomTreeNode : DomTreeNodes) {
306 NodeT *BB = DomTreeNode.first;
307 typename DomTreeNodeMapType::const_iterator OI =
308 OtherDomTreeNodes.find(BB);
309 if (OI == OtherDomTreeNodes.end())
310 return true;
312 DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313 DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
315 if (MyNd.compare(&OtherNd))
316 return true;
319 return false;
322 void releaseMemory() { reset(); }
324 /// getNode - return the (Post)DominatorTree node for the specified basic
325 /// block. This is the same as using operator[] on this class. The result
326 /// may (but is not required to) be null for a forward (backwards)
327 /// statically unreachable block.
328 DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
329 auto I = DomTreeNodes.find(BB);
330 if (I != DomTreeNodes.end())
331 return I->second.get();
332 return nullptr;
335 /// See getNode.
336 DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337 return getNode(BB);
340 /// getRootNode - This returns the entry node for the CFG of the function. If
341 /// this tree represents the post-dominance relations for a function, however,
342 /// this root may be a node with the block == NULL. This is the case when
343 /// there are multiple exit nodes from a particular function. Consumers of
344 /// post-dominance information must be capable of dealing with this
345 /// possibility.
347 DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
348 const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
350 /// Get all nodes dominated by R, including R itself.
351 void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
352 Result.clear();
353 const DomTreeNodeBase<NodeT> *RN = getNode(R);
354 if (!RN)
355 return; // If R is unreachable, it will not be present in the DOM tree.
356 SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
357 WL.push_back(RN);
359 while (!WL.empty()) {
360 const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
361 Result.push_back(N->getBlock());
362 WL.append(N->begin(), N->end());
366 /// properlyDominates - Returns true iff A dominates B and A != B.
367 /// Note that this is not a constant time operation!
369 bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
370 const DomTreeNodeBase<NodeT> *B) const {
371 if (!A || !B)
372 return false;
373 if (A == B)
374 return false;
375 return dominates(A, B);
378 bool properlyDominates(const NodeT *A, const NodeT *B) const;
380 /// isReachableFromEntry - Return true if A is dominated by the entry
381 /// block of the function containing it.
382 bool isReachableFromEntry(const NodeT *A) const {
383 assert(!this->isPostDominator() &&
384 "This is not implemented for post dominators");
385 return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
388 bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
390 /// dominates - Returns true iff A dominates B. Note that this is not a
391 /// constant time operation!
393 bool dominates(const DomTreeNodeBase<NodeT> *A,
394 const DomTreeNodeBase<NodeT> *B) const {
395 // A node trivially dominates itself.
396 if (B == A)
397 return true;
399 // An unreachable node is dominated by anything.
400 if (!isReachableFromEntry(B))
401 return true;
403 // And dominates nothing.
404 if (!isReachableFromEntry(A))
405 return false;
407 if (B->getIDom() == A) return true;
409 if (A->getIDom() == B) return false;
411 // A can only dominate B if it is higher in the tree.
412 if (A->getLevel() >= B->getLevel()) return false;
414 // Compare the result of the tree walk and the dfs numbers, if expensive
415 // checks are enabled.
416 #ifdef EXPENSIVE_CHECKS
417 assert((!DFSInfoValid ||
418 (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
419 "Tree walk disagrees with dfs numbers!");
420 #endif
422 if (DFSInfoValid)
423 return B->DominatedBy(A);
425 // If we end up with too many slow queries, just update the
426 // DFS numbers on the theory that we are going to keep querying.
427 SlowQueries++;
428 if (SlowQueries > 32) {
429 updateDFSNumbers();
430 return B->DominatedBy(A);
433 return dominatedBySlowTreeWalk(A, B);
436 bool dominates(const NodeT *A, const NodeT *B) const;
438 NodeT *getRoot() const {
439 assert(this->Roots.size() == 1 && "Should always have entry node!");
440 return this->Roots[0];
443 /// findNearestCommonDominator - Find nearest common dominator basic block
444 /// for basic block A and B. If there is no such block then return nullptr.
445 NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
446 assert(A && B && "Pointers are not valid");
447 assert(A->getParent() == B->getParent() &&
448 "Two blocks are not in same function");
450 // If either A or B is a entry block then it is nearest common dominator
451 // (for forward-dominators).
452 if (!isPostDominator()) {
453 NodeT &Entry = A->getParent()->front();
454 if (A == &Entry || B == &Entry)
455 return &Entry;
458 DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459 DomTreeNodeBase<NodeT> *NodeB = getNode(B);
461 if (!NodeA || !NodeB) return nullptr;
463 // Use level information to go up the tree until the levels match. Then
464 // continue going up til we arrive at the same node.
465 while (NodeA && NodeA != NodeB) {
466 if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
468 NodeA = NodeA->IDom;
471 return NodeA ? NodeA->getBlock() : nullptr;
474 const NodeT *findNearestCommonDominator(const NodeT *A,
475 const NodeT *B) const {
476 // Cast away the const qualifiers here. This is ok since
477 // const is re-introduced on the return type.
478 return findNearestCommonDominator(const_cast<NodeT *>(A),
479 const_cast<NodeT *>(B));
482 bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483 return isPostDominator() && !A->getBlock();
486 //===--------------------------------------------------------------------===//
487 // API to update (Post)DominatorTree information based on modifications to
488 // the CFG...
490 /// Inform the dominator tree about a sequence of CFG edge insertions and
491 /// deletions and perform a batch update on the tree.
493 /// This function should be used when there were multiple CFG updates after
494 /// the last dominator tree update. It takes care of performing the updates
495 /// in sync with the CFG and optimizes away the redundant operations that
496 /// cancel each other.
497 /// The functions expects the sequence of updates to be balanced. Eg.:
498 /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
499 /// logically it results in a single insertions.
500 /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
501 /// sense to insert the same edge twice.
503 /// What's more, the functions assumes that it's safe to ask every node in the
504 /// CFG about its children and inverse children. This implies that deletions
505 /// of CFG edges must not delete the CFG nodes before calling this function.
507 /// The applyUpdates function can reorder the updates and remove redundant
508 /// ones internally. The batch updater is also able to detect sequences of
509 /// zero and exactly one update -- it's optimized to do less work in these
510 /// cases.
512 /// Note that for postdominators it automatically takes care of applying
513 /// updates on reverse edges internally (so there's no need to swap the
514 /// From and To pointers when constructing DominatorTree::UpdateType).
515 /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
516 /// with the same template parameter T.
518 /// \param Updates An unordered sequence of updates to perform.
520 void applyUpdates(ArrayRef<UpdateType> Updates) {
521 DomTreeBuilder::ApplyUpdates(*this, Updates);
524 /// Inform the dominator tree about a CFG edge insertion and update the tree.
526 /// This function has to be called just before or just after making the update
527 /// on the actual CFG. There cannot be any other updates that the dominator
528 /// tree doesn't know about.
530 /// Note that for postdominators it automatically takes care of inserting
531 /// a reverse edge internally (so there's no need to swap the parameters).
533 void insertEdge(NodeT *From, NodeT *To) {
534 assert(From);
535 assert(To);
536 assert(From->getParent() == Parent);
537 assert(To->getParent() == Parent);
538 DomTreeBuilder::InsertEdge(*this, From, To);
541 /// Inform the dominator tree about a CFG edge deletion and update the tree.
543 /// This function has to be called just after making the update on the actual
544 /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
545 /// DEBUG mode. There cannot be any other updates that the
546 /// dominator tree doesn't know about.
548 /// Note that for postdominators it automatically takes care of deleting
549 /// a reverse edge internally (so there's no need to swap the parameters).
551 void deleteEdge(NodeT *From, NodeT *To) {
552 assert(From);
553 assert(To);
554 assert(From->getParent() == Parent);
555 assert(To->getParent() == Parent);
556 DomTreeBuilder::DeleteEdge(*this, From, To);
559 /// Add a new node to the dominator tree information.
561 /// This creates a new node as a child of DomBB dominator node, linking it
562 /// into the children list of the immediate dominator.
564 /// \param BB New node in CFG.
565 /// \param DomBB CFG node that is dominator for BB.
566 /// \returns New dominator tree node that represents new CFG node.
568 DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
569 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
570 DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
571 assert(IDomNode && "Not immediate dominator specified for block!");
572 DFSInfoValid = false;
573 return (DomTreeNodes[BB] = IDomNode->addChild(
574 std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
577 /// Add a new node to the forward dominator tree and make it a new root.
579 /// \param BB New node in CFG.
580 /// \returns New dominator tree node that represents new CFG node.
582 DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
583 assert(getNode(BB) == nullptr && "Block already in dominator tree!");
584 assert(!this->isPostDominator() &&
585 "Cannot change root of post-dominator tree");
586 DFSInfoValid = false;
587 DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
588 std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
589 if (Roots.empty()) {
590 addRoot(BB);
591 } else {
592 assert(Roots.size() == 1);
593 NodeT *OldRoot = Roots.front();
594 auto &OldNode = DomTreeNodes[OldRoot];
595 OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
596 OldNode->IDom = NewNode;
597 OldNode->UpdateLevel();
598 Roots[0] = BB;
600 return RootNode = NewNode;
603 /// changeImmediateDominator - This method is used to update the dominator
604 /// tree information when a node's immediate dominator changes.
606 void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
607 DomTreeNodeBase<NodeT> *NewIDom) {
608 assert(N && NewIDom && "Cannot change null node pointers!");
609 DFSInfoValid = false;
610 N->setIDom(NewIDom);
613 void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614 changeImmediateDominator(getNode(BB), getNode(NewBB));
617 /// eraseNode - Removes a node from the dominator tree. Block must not
618 /// dominate any other blocks. Removes node from its immediate dominator's
619 /// children list. Deletes dominator node associated with basic block BB.
620 void eraseNode(NodeT *BB) {
621 DomTreeNodeBase<NodeT> *Node = getNode(BB);
622 assert(Node && "Removing node that isn't in dominator tree.");
623 assert(Node->getChildren().empty() && "Node is not a leaf node.");
625 DFSInfoValid = false;
627 // Remove node from immediate dominator's children list.
628 DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
629 if (IDom) {
630 const auto I = find(IDom->Children, Node);
631 assert(I != IDom->Children.end() &&
632 "Not in immediate dominator children set!");
633 // I am no longer your child...
634 IDom->Children.erase(I);
637 DomTreeNodes.erase(BB);
639 if (!IsPostDom) return;
641 // Remember to update PostDominatorTree roots.
642 auto RIt = llvm::find(Roots, BB);
643 if (RIt != Roots.end()) {
644 std::swap(*RIt, Roots.back());
645 Roots.pop_back();
649 /// splitBlock - BB is split and now it has one successor. Update dominator
650 /// tree to reflect this change.
651 void splitBlock(NodeT *NewBB) {
652 if (IsPostDominator)
653 Split<Inverse<NodeT *>>(NewBB);
654 else
655 Split<NodeT *>(NewBB);
658 /// print - Convert to human readable form
660 void print(raw_ostream &O) const {
661 O << "=============================--------------------------------\n";
662 if (IsPostDominator)
663 O << "Inorder PostDominator Tree: ";
664 else
665 O << "Inorder Dominator Tree: ";
666 if (!DFSInfoValid)
667 O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
668 O << "\n";
670 // The postdom tree can have a null root if there are no returns.
671 if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
672 O << "Roots: ";
673 for (const NodePtr Block : Roots) {
674 Block->printAsOperand(O, false);
675 O << " ";
677 O << "\n";
680 public:
681 /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
682 /// dominator tree in dfs order.
683 void updateDFSNumbers() const {
684 if (DFSInfoValid) {
685 SlowQueries = 0;
686 return;
689 SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
690 typename DomTreeNodeBase<NodeT>::const_iterator>,
691 32> WorkStack;
693 const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694 assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695 if (!ThisRoot)
696 return;
698 // Both dominators and postdominators have a single root node. In the case
699 // case of PostDominatorTree, this node is a virtual root.
700 WorkStack.push_back({ThisRoot, ThisRoot->begin()});
702 unsigned DFSNum = 0;
703 ThisRoot->DFSNumIn = DFSNum++;
705 while (!WorkStack.empty()) {
706 const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707 const auto ChildIt = WorkStack.back().second;
709 // If we visited all of the children of this node, "recurse" back up the
710 // stack setting the DFOutNum.
711 if (ChildIt == Node->end()) {
712 Node->DFSNumOut = DFSNum++;
713 WorkStack.pop_back();
714 } else {
715 // Otherwise, recursively visit this child.
716 const DomTreeNodeBase<NodeT> *Child = *ChildIt;
717 ++WorkStack.back().second;
719 WorkStack.push_back({Child, Child->begin()});
720 Child->DFSNumIn = DFSNum++;
724 SlowQueries = 0;
725 DFSInfoValid = true;
728 /// recalculate - compute a dominator tree for the given function
729 void recalculate(ParentType &Func) {
730 Parent = &Func;
731 DomTreeBuilder::Calculate(*this);
734 void recalculate(ParentType &Func, ArrayRef<UpdateType> Updates) {
735 Parent = &Func;
736 DomTreeBuilder::CalculateWithUpdates(*this, Updates);
739 /// verify - checks if the tree is correct. There are 3 level of verification:
740 /// - Full -- verifies if the tree is correct by making sure all the
741 /// properties (including the parent and the sibling property)
742 /// hold.
743 /// Takes O(N^3) time.
745 /// - Basic -- checks if the tree is correct, but compares it to a freshly
746 /// constructed tree instead of checking the sibling property.
747 /// Takes O(N^2) time.
749 /// - Fast -- checks basic tree structure and compares it with a freshly
750 /// constructed tree.
751 /// Takes O(N^2) time worst case, but is faster in practise (same
752 /// as tree construction).
753 bool verify(VerificationLevel VL = VerificationLevel::Full) const {
754 return DomTreeBuilder::Verify(*this, VL);
757 protected:
758 void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
760 void reset() {
761 DomTreeNodes.clear();
762 Roots.clear();
763 RootNode = nullptr;
764 Parent = nullptr;
765 DFSInfoValid = false;
766 SlowQueries = 0;
769 // NewBB is split and now it has one successor. Update dominator tree to
770 // reflect this change.
771 template <class N>
772 void Split(typename GraphTraits<N>::NodeRef NewBB) {
773 using GraphT = GraphTraits<N>;
774 using NodeRef = typename GraphT::NodeRef;
775 assert(std::distance(GraphT::child_begin(NewBB),
776 GraphT::child_end(NewBB)) == 1 &&
777 "NewBB should have a single successor!");
778 NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
780 std::vector<NodeRef> PredBlocks;
781 for (const auto &Pred : children<Inverse<N>>(NewBB))
782 PredBlocks.push_back(Pred);
784 assert(!PredBlocks.empty() && "No predblocks?");
786 bool NewBBDominatesNewBBSucc = true;
787 for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
788 if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
789 isReachableFromEntry(Pred)) {
790 NewBBDominatesNewBBSucc = false;
791 break;
795 // Find NewBB's immediate dominator and create new dominator tree node for
796 // NewBB.
797 NodeT *NewBBIDom = nullptr;
798 unsigned i = 0;
799 for (i = 0; i < PredBlocks.size(); ++i)
800 if (isReachableFromEntry(PredBlocks[i])) {
801 NewBBIDom = PredBlocks[i];
802 break;
805 // It's possible that none of the predecessors of NewBB are reachable;
806 // in that case, NewBB itself is unreachable, so nothing needs to be
807 // changed.
808 if (!NewBBIDom) return;
810 for (i = i + 1; i < PredBlocks.size(); ++i) {
811 if (isReachableFromEntry(PredBlocks[i]))
812 NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
815 // Create the new dominator tree node... and set the idom of NewBB.
816 DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
818 // If NewBB strictly dominates other blocks, then it is now the immediate
819 // dominator of NewBBSucc. Update the dominator tree as appropriate.
820 if (NewBBDominatesNewBBSucc) {
821 DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
822 changeImmediateDominator(NewBBSuccNode, NewBBNode);
826 private:
827 bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
828 const DomTreeNodeBase<NodeT> *B) const {
829 assert(A != B);
830 assert(isReachableFromEntry(B));
831 assert(isReachableFromEntry(A));
833 const unsigned ALevel = A->getLevel();
834 const DomTreeNodeBase<NodeT> *IDom;
836 // Don't walk nodes above A's subtree. When we reach A's level, we must
837 // either find A or be in some other subtree not dominated by A.
838 while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
839 B = IDom; // Walk up the tree
841 return B == A;
844 /// Wipe this tree's state without releasing any resources.
846 /// This is essentially a post-move helper only. It leaves the object in an
847 /// assignable and destroyable state, but otherwise invalid.
848 void wipe() {
849 DomTreeNodes.clear();
850 RootNode = nullptr;
851 Parent = nullptr;
855 template <typename T>
856 using DomTreeBase = DominatorTreeBase<T, false>;
858 template <typename T>
859 using PostDomTreeBase = DominatorTreeBase<T, true>;
861 // These two functions are declared out of line as a workaround for building
862 // with old (< r147295) versions of clang because of pr11642.
863 template <typename NodeT, bool IsPostDom>
864 bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
865 const NodeT *B) const {
866 if (A == B)
867 return true;
869 // Cast away the const qualifiers here. This is ok since
870 // this function doesn't actually return the values returned
871 // from getNode.
872 return dominates(getNode(const_cast<NodeT *>(A)),
873 getNode(const_cast<NodeT *>(B)));
875 template <typename NodeT, bool IsPostDom>
876 bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
877 const NodeT *A, const NodeT *B) const {
878 if (A == B)
879 return false;
881 // Cast away the const qualifiers here. This is ok since
882 // this function doesn't actually return the values returned
883 // from getNode.
884 return dominates(getNode(const_cast<NodeT *>(A)),
885 getNode(const_cast<NodeT *>(B)));
888 } // end namespace llvm
890 #endif // LLVM_SUPPORT_GENERICDOMTREE_H