LLVM  8.0.0svn
GenericDomTree.h
Go to the documentation of this file.
1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 ///
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
14 /// graph types.
15 ///
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.
19 ///
20 /// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
21 ///
22 //===----------------------------------------------------------------------===//
23 
24 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
25 #define LLVM_SUPPORT_GENERICDOMTREE_H
26 
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/GraphTraits.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"
35 #include <algorithm>
36 #include <cassert>
37 #include <cstddef>
38 #include <iterator>
39 #include <memory>
40 #include <type_traits>
41 #include <utility>
42 #include <vector>
43 
44 namespace llvm {
45 
46 template <typename NodeT, bool IsPostDom>
47 class DominatorTreeBase;
48 
49 namespace DomTreeBuilder {
50 template <typename DomTreeT>
51 struct SemiNCAInfo;
52 } // namespace DomTreeBuilder
53 
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>;
61 
62  NodeT *TheBB;
63  DomTreeNodeBase *IDom;
64  unsigned Level;
65  std::vector<DomTreeNodeBase *> Children;
66  mutable unsigned DFSNumIn = ~0;
67  mutable unsigned DFSNumOut = ~0;
68 
69  public:
70  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
71  : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
72 
73  using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
74  using const_iterator =
75  typename std::vector<DomTreeNodeBase *>::const_iterator;
76 
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(); }
81 
82  NodeT *getBlock() const { return TheBB; }
83  DomTreeNodeBase *getIDom() const { return IDom; }
84  unsigned getLevel() const { return Level; }
85 
86  const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
87 
88  std::unique_ptr<DomTreeNodeBase> addChild(
89  std::unique_ptr<DomTreeNodeBase> C) {
90  Children.push_back(C.get());
91  return C;
92  }
93 
94  size_t getNumChildren() const { return Children.size(); }
95 
96  void clearAllChildren() { Children.clear(); }
97 
98  bool compare(const DomTreeNodeBase *Other) const {
99  if (getNumChildren() != Other->getNumChildren())
100  return true;
101 
102  if (Level != Other->Level) return true;
103 
104  SmallPtrSet<const NodeT *, 4> OtherChildren;
105  for (const DomTreeNodeBase *I : *Other) {
106  const NodeT *Nd = I->getBlock();
107  OtherChildren.insert(Nd);
108  }
109 
110  for (const DomTreeNodeBase *I : *this) {
111  const NodeT *N = I->getBlock();
112  if (OtherChildren.count(N) == 0)
113  return true;
114  }
115  return false;
116  }
117 
118  void setIDom(DomTreeNodeBase *NewIDom) {
119  assert(IDom && "No immediate dominator?");
120  if (IDom == NewIDom) return;
121 
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);
127 
128  // Switch to new dominator
129  IDom = NewIDom;
130  IDom->Children.push_back(this);
131 
132  UpdateLevel();
133  }
134 
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; }
140 
141 private:
142  // Return true if this node is dominated by other. Use this only if DFS info
143  // is valid.
144  bool DominatedBy(const DomTreeNodeBase *other) const {
145  return this->DFSNumIn >= other->DFSNumIn &&
146  this->DFSNumOut <= other->DFSNumOut;
147  }
148 
149  void UpdateLevel() {
150  assert(IDom);
151  if (Level == IDom->Level + 1) return;
152 
153  SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
154 
155  while (!WorkStack.empty()) {
156  DomTreeNodeBase *Current = WorkStack.pop_back_val();
157  Current->Level = Current->IDom->Level + 1;
158 
159  for (DomTreeNodeBase *C : *Current) {
160  assert(C->IDom);
161  if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
162  }
163  }
164  }
165 };
166 
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);
171  else
172  O << " <<exit node>>";
173 
174  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
175  << Node->getLevel() << "]\n";
176 
177  return O;
178 }
179 
180 template <class NodeT>
182  unsigned Lev) {
183  O.indent(2 * Lev) << "[" << Lev << "] " << N;
184  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
185  E = N->end();
186  I != E; ++I)
187  PrintDomTree<NodeT>(*I, O, Lev + 1);
188 }
189 
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);
194 
195 template <typename DomTreeT>
196 void CalculateWithUpdates(DomTreeT &DT,
198 
199 template <typename DomTreeT>
200 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
201  typename DomTreeT::NodePtr To);
202 
203 template <typename DomTreeT>
204 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
205  typename DomTreeT::NodePtr To);
206 
207 template <typename DomTreeT>
208 void ApplyUpdates(DomTreeT &DT,
210 
211 template <typename DomTreeT>
212 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
213 } // namespace DomTreeBuilder
214 
215 /// Core dominator tree base class.
216 ///
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 {
221  public:
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;
231 
234  static constexpr UpdateKind Insert = UpdateKind::Insert;
235  static constexpr UpdateKind Delete = UpdateKind::Delete;
236 
237  enum class VerificationLevel { Fast, Basic, Full };
238 
239 protected:
240  // Dominators always have a single root, postdominators can have more.
242 
243  using DomTreeNodeMapType =
247  ParentPtr Parent = nullptr;
248 
249  mutable bool DFSInfoValid = false;
250  mutable unsigned int SlowQueries = 0;
251 
253 
254  public:
256 
258  : Roots(std::move(Arg.Roots)),
259  DomTreeNodes(std::move(Arg.DomTreeNodes)),
260  RootNode(Arg.RootNode),
261  Parent(Arg.Parent),
262  DFSInfoValid(Arg.DFSInfoValid),
263  SlowQueries(Arg.SlowQueries) {
264  Arg.wipe();
265  }
266 
268  Roots = std::move(RHS.Roots);
269  DomTreeNodes = std::move(RHS.DomTreeNodes);
270  RootNode = RHS.RootNode;
271  Parent = RHS.Parent;
272  DFSInfoValid = RHS.DFSInfoValid;
273  SlowQueries = RHS.SlowQueries;
274  RHS.wipe();
275  return *this;
276  }
277 
278  DominatorTreeBase(const DominatorTreeBase &) = delete;
279  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
280 
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).
284  ///
285  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
286 
287  /// isPostDominator - Returns true if analysis based of postdoms
288  ///
289  bool isPostDominator() const { return IsPostDominator; }
290 
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;
295 
296  if (Roots.size() != Other.Roots.size())
297  return true;
298 
299  if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
300  return true;
301 
302  const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
303  if (DomTreeNodes.size() != OtherDomTreeNodes.size())
304  return true;
305 
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())
311  return true;
312 
313  DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
314  DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
315 
316  if (MyNd.compare(&OtherNd))
317  return true;
318  }
319 
320  return false;
321  }
322 
323  void releaseMemory() { reset(); }
324 
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();
333  return nullptr;
334  }
335 
336  /// See getNode.
337  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
338  return getNode(BB);
339  }
340 
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
346  /// possibility.
347  ///
348  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
349  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
350 
351  /// Get all nodes dominated by R, including R itself.
352  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
353  Result.clear();
354  const DomTreeNodeBase<NodeT> *RN = getNode(R);
355  if (!RN)
356  return; // If R is unreachable, it will not be present in the DOM tree.
358  WL.push_back(RN);
359 
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());
364  }
365  }
366 
367  /// properlyDominates - Returns true iff A dominates B and A != B.
368  /// Note that this is not a constant time operation!
369  ///
371  const DomTreeNodeBase<NodeT> *B) const {
372  if (!A || !B)
373  return false;
374  if (A == B)
375  return false;
376  return dominates(A, B);
377  }
378 
379  bool properlyDominates(const NodeT *A, const NodeT *B) const;
380 
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)));
387  }
388 
389  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
390 
391  /// dominates - Returns true iff A dominates B. Note that this is not a
392  /// constant time operation!
393  ///
395  const DomTreeNodeBase<NodeT> *B) const {
396  // A node trivially dominates itself.
397  if (B == A)
398  return true;
399 
400  // An unreachable node is dominated by anything.
401  if (!isReachableFromEntry(B))
402  return true;
403 
404  // And dominates nothing.
405  if (!isReachableFromEntry(A))
406  return false;
407 
408  if (B->getIDom() == A) return true;
409 
410  if (A->getIDom() == B) return false;
411 
412  // A can only dominate B if it is higher in the tree.
413  if (A->getLevel() >= B->getLevel()) return false;
414 
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!");
421 #endif
422 
423  if (DFSInfoValid)
424  return B->DominatedBy(A);
425 
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.
428  SlowQueries++;
429  if (SlowQueries > 32) {
430  updateDFSNumbers();
431  return B->DominatedBy(A);
432  }
433 
434  return dominatedBySlowTreeWalk(A, B);
435  }
436 
437  bool dominates(const NodeT *A, const NodeT *B) const;
438 
439  NodeT *getRoot() const {
440  assert(this->Roots.size() == 1 && "Should always have entry node!");
441  return this->Roots[0];
442  }
443 
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");
450 
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)
456  return &Entry;
457  }
458 
459  DomTreeNodeBase<NodeT> *NodeA = getNode(A);
460  DomTreeNodeBase<NodeT> *NodeB = getNode(B);
461 
462  if (!NodeA || !NodeB) return nullptr;
463 
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);
468 
469  NodeA = NodeA->IDom;
470  }
471 
472  return NodeA ? NodeA->getBlock() : nullptr;
473  }
474 
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));
481  }
482 
483  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
484  return isPostDominator() && !A->getBlock();
485  }
486 
487  //===--------------------------------------------------------------------===//
488  // API to update (Post)DominatorTree information based on modifications to
489  // the CFG...
490 
491  /// Inform the dominator tree about a sequence of CFG edge insertions and
492  /// deletions and perform a batch update on the tree.
493  ///
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.
503  ///
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.
507  ///
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
511  /// cases.
512  ///
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.
518  ///
519  /// \param Updates An unordered sequence of updates to perform.
520  ///
522  DomTreeBuilder::ApplyUpdates(*this, Updates);
523  }
524 
525  /// Inform the dominator tree about a CFG edge insertion and update the tree.
526  ///
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.
530  ///
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).
533  ///
534  void insertEdge(NodeT *From, NodeT *To) {
535  assert(From);
536  assert(To);
537  assert(From->getParent() == Parent);
538  assert(To->getParent() == Parent);
539  DomTreeBuilder::InsertEdge(*this, From, To);
540  }
541 
542  /// Inform the dominator tree about a CFG edge deletion and update the tree.
543  ///
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.
548  ///
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).
551  ///
552  void deleteEdge(NodeT *From, NodeT *To) {
553  assert(From);
554  assert(To);
555  assert(From->getParent() == Parent);
556  assert(To->getParent() == Parent);
557  DomTreeBuilder::DeleteEdge(*this, From, To);
558  }
559 
560  /// Add a new node to the dominator tree information.
561  ///
562  /// This creates a new node as a child of DomBB dominator node, linking it
563  /// into the children list of the immediate dominator.
564  ///
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.
568  ///
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();
576  }
577 
578  /// Add a new node to the forward dominator tree and make it a new root.
579  ///
580  /// \param BB New node in CFG.
581  /// \returns New dominator tree node that represents new CFG node.
582  ///
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();
590  if (Roots.empty()) {
591  addRoot(BB);
592  } else {
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();
599  Roots[0] = BB;
600  }
601  return RootNode = NewNode;
602  }
603 
604  /// changeImmediateDominator - This method is used to update the dominator
605  /// tree information when a node's immediate dominator changes.
606  ///
608  DomTreeNodeBase<NodeT> *NewIDom) {
609  assert(N && NewIDom && "Cannot change null node pointers!");
610  DFSInfoValid = false;
611  N->setIDom(NewIDom);
612  }
613 
614  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
615  changeImmediateDominator(getNode(BB), getNode(NewBB));
616  }
617 
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.");
625 
626  DFSInfoValid = false;
627 
628  // Remove node from immediate dominator's children list.
629  DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
630  if (IDom) {
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);
636  }
637 
638  DomTreeNodes.erase(BB);
639 
640  if (!IsPostDom) return;
641 
642  // Remember to update PostDominatorTree roots.
643  auto RIt = llvm::find(Roots, BB);
644  if (RIt != Roots.end()) {
645  std::swap(*RIt, Roots.back());
646  Roots.pop_back();
647  }
648  }
649 
650  /// splitBlock - BB is split and now it has one successor. Update dominator
651  /// tree to reflect this change.
652  void splitBlock(NodeT *NewBB) {
653  if (IsPostDominator)
654  Split<Inverse<NodeT *>>(NewBB);
655  else
656  Split<NodeT *>(NewBB);
657  }
658 
659  /// print - Convert to human readable form
660  ///
661  void print(raw_ostream &O) const {
662  O << "=============================--------------------------------\n";
663  if (IsPostDominator)
664  O << "Inorder PostDominator Tree: ";
665  else
666  O << "Inorder Dominator Tree: ";
667  if (!DFSInfoValid)
668  O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
669  O << "\n";
670 
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) {
674  O << "Roots: ";
675  for (const NodePtr Block : Roots) {
676  Block->printAsOperand(O, false);
677  O << " ";
678  }
679  O << "\n";
680  }
681  }
682 
683 public:
684  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
685  /// dominator tree in dfs order.
686  void updateDFSNumbers() const {
687  if (DFSInfoValid) {
688  SlowQueries = 0;
689  return;
690  }
691 
694  32> WorkStack;
695 
696  const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
697  assert((!Parent || ThisRoot) && "Empty constructed DomTree");
698  if (!ThisRoot)
699  return;
700 
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()});
704 
705  unsigned DFSNum = 0;
706  ThisRoot->DFSNumIn = DFSNum++;
707 
708  while (!WorkStack.empty()) {
709  const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
710  const auto ChildIt = WorkStack.back().second;
711 
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();
717  } else {
718  // Otherwise, recursively visit this child.
719  const DomTreeNodeBase<NodeT> *Child = *ChildIt;
720  ++WorkStack.back().second;
721 
722  WorkStack.push_back({Child, Child->begin()});
723  Child->DFSNumIn = DFSNum++;
724  }
725  }
726 
727  SlowQueries = 0;
728  DFSInfoValid = true;
729  }
730 
731  /// recalculate - compute a dominator tree for the given function
732  void recalculate(ParentType &Func) {
733  Parent = &Func;
735  }
736 
738  Parent = &Func;
739  DomTreeBuilder::CalculateWithUpdates(*this, Updates);
740  }
741 
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)
745  /// hold.
746  /// Takes O(N^3) time.
747  ///
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.
751  ///
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).
757  return DomTreeBuilder::Verify(*this, VL);
758  }
759 
760 protected:
761  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
762 
763  void reset() {
764  DomTreeNodes.clear();
765  Roots.clear();
766  RootNode = nullptr;
767  Parent = nullptr;
768  DFSInfoValid = false;
769  SlowQueries = 0;
770  }
771 
772  // NewBB is split and now it has one successor. Update dominator tree to
773  // reflect this change.
774  template <class N>
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);
782 
783  std::vector<NodeRef> PredBlocks;
784  for (const auto &Pred : children<Inverse<N>>(NewBB))
785  PredBlocks.push_back(Pred);
786 
787  assert(!PredBlocks.empty() && "No predblocks?");
788 
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;
794  break;
795  }
796  }
797 
798  // Find NewBB's immediate dominator and create new dominator tree node for
799  // NewBB.
800  NodeT *NewBBIDom = nullptr;
801  unsigned i = 0;
802  for (i = 0; i < PredBlocks.size(); ++i)
803  if (isReachableFromEntry(PredBlocks[i])) {
804  NewBBIDom = PredBlocks[i];
805  break;
806  }
807 
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
810  // changed.
811  if (!NewBBIDom) return;
812 
813  for (i = i + 1; i < PredBlocks.size(); ++i) {
814  if (isReachableFromEntry(PredBlocks[i]))
815  NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
816  }
817 
818  // Create the new dominator tree node... and set the idom of NewBB.
819  DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
820 
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);
826  }
827  }
828 
829  private:
830  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
831  const DomTreeNodeBase<NodeT> *B) const {
832  assert(A != B);
833  assert(isReachableFromEntry(B));
834  assert(isReachableFromEntry(A));
835 
836  const unsigned ALevel = A->getLevel();
837  const DomTreeNodeBase<NodeT> *IDom;
838 
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
843 
844  return B == A;
845  }
846 
847  /// Wipe this tree's state without releasing any resources.
848  ///
849  /// This is essentially a post-move helper only. It leaves the object in an
850  /// assignable and destroyable state, but otherwise invalid.
851  void wipe() {
852  DomTreeNodes.clear();
853  RootNode = nullptr;
854  Parent = nullptr;
855  }
856 };
857 
858 template <typename T>
860 
861 template <typename T>
863 
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>
868  const NodeT *B) const {
869  if (A == B)
870  return true;
871 
872  // Cast away the const qualifiers here. This is ok since
873  // this function doesn't actually return the values returned
874  // from getNode.
875  return dominates(getNode(const_cast<NodeT *>(A)),
876  getNode(const_cast<NodeT *>(B)));
877 }
878 template <typename NodeT, bool IsPostDom>
880  const NodeT *A, const NodeT *B) const {
881  if (A == B)
882  return false;
883 
884  // Cast away the const qualifiers here. This is ok since
885  // this function doesn't actually return the values returned
886  // from getNode.
887  return dominates(getNode(const_cast<NodeT *>(A)),
888  getNode(const_cast<NodeT *>(B)));
889 }
890 
891 } // end namespace llvm
892 
893 #endif // LLVM_SUPPORT_GENERICDOMTREE_H
uint64_t CallInst * C
typename std::vector< DomTreeNodeBase *>::const_iterator const_iterator
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:122
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
This class represents lattice values for constants.
Definition: AllocatorList.h:24
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
void recalculate(ParentType &Func, ArrayRef< UpdateType > Updates)
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
block Block Frequency true
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:1343
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
SmallVector< NodeT *, IsPostDom ? 4 :1 > Roots
void Split(typename GraphTraits< N >::NodeRef NewBB)
const NodeT * findNearestCommonDominator(const NodeT *A, const NodeT *B) const
Definition: BitVector.h:938
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
DominatorTreeBase & operator=(DominatorTreeBase &&RHS)
void changeImmediateDominator(NodeT *BB, NodeT *NewBB)
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
void addRoot(NodeT *BB)
const SmallVectorImpl< NodeT * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:783
decltype(std::declval< BasicBlock *>() ->getParent()) ParentPtr
bool compare(const DominatorTreeBase &Other) const
compare - Return false if the other dominator tree base matches this dominator tree base...
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:43
void PrintDomTree(const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
const DomTreeNodeBase< NodeT > * getRootNode() const
Base class for the actual dominator tree node.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
const std::vector< DomTreeNodeBase * > & getChildren() const
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
Core dominator tree base class.
Definition: LoopInfo.h:61
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree...
NodeT * getBlock() const
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:79
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
std::shared_ptr< Node > NodePtr
Short-hand for a Node pointer.
Definition: MsgPackTypes.h:33
bool isReachableFromEntry(const DomTreeNodeBase< NodeT > *A) const
void getDescendants(NodeT *R, SmallVectorImpl< NodeT *> &Result) const
Get all nodes dominated by R, including R itself.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
DomTreeNodeBase * getIDom() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
typename std::remove_pointer< ParentPtr >::type ParentType
unsigned getDFSNumOut() const
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
DomTreeNodeBase< NodeT > * operator[](const NodeT *BB) const
See getNode.
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
size_t size() const
Definition: SmallVector.h:53
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1201
void print(raw_ostream &O) const
print - Convert to human readable form
const_iterator begin() const
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
BlockVerifier::State From
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
size_t getNumChildren() const
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
DomTreeNodeBase< NodeT > * RootNode
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:394
std::unique_ptr< DomTreeNodeBase > addChild(std::unique_ptr< DomTreeNodeBase > C)
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
amdgpu Simplify well known AMD library false Value Value * Arg
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
bool compare(const DomTreeNodeBase *Other) const
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
DomTreeNodeMapType DomTreeNodes
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
void ApplyUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
DominatorTreeBase(DominatorTreeBase &&Arg)
bool isVirtualRoot(const DomTreeNodeBase< NodeT > *A) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order...
typename std::vector< DomTreeNodeBase *>::iterator iterator
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
NodeT * getRoot() const
unsigned getLevel() const
const_iterator end() const
void setIDom(DomTreeNodeBase *NewIDom)