LLVM  10.0.0svn
GenericDomTree.h
Go to the documentation of this file.
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 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
24 #define LLVM_SUPPORT_GENERICDOMTREE_H
25 
26 #include "llvm/ADT/DenseMap.h"
27 #include "llvm/ADT/GraphTraits.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"
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>
42 
43 namespace llvm {
44 
45 template <typename NodeT, bool IsPostDom>
46 class DominatorTreeBase;
47 
48 namespace DomTreeBuilder {
49 template <typename DomTreeT>
50 struct SemiNCAInfo;
51 } // namespace DomTreeBuilder
52 
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>;
60 
61  NodeT *TheBB;
62  DomTreeNodeBase *IDom;
63  unsigned Level;
64  std::vector<DomTreeNodeBase *> Children;
65  mutable unsigned DFSNumIn = ~0;
66  mutable unsigned DFSNumOut = ~0;
67 
68  public:
69  DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
70  : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
71 
72  using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
73  using const_iterator =
74  typename std::vector<DomTreeNodeBase *>::const_iterator;
75 
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(); }
80 
81  NodeT *getBlock() const { return TheBB; }
82  DomTreeNodeBase *getIDom() const { return IDom; }
83  unsigned getLevel() const { return Level; }
84 
85  const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
86 
87  std::unique_ptr<DomTreeNodeBase> addChild(
88  std::unique_ptr<DomTreeNodeBase> C) {
89  Children.push_back(C.get());
90  return C;
91  }
92 
93  size_t getNumChildren() const { return Children.size(); }
94 
95  void clearAllChildren() { Children.clear(); }
96 
97  bool compare(const DomTreeNodeBase *Other) const {
98  if (getNumChildren() != Other->getNumChildren())
99  return true;
100 
101  if (Level != Other->Level) return true;
102 
103  SmallPtrSet<const NodeT *, 4> OtherChildren;
104  for (const DomTreeNodeBase *I : *Other) {
105  const NodeT *Nd = I->getBlock();
106  OtherChildren.insert(Nd);
107  }
108 
109  for (const DomTreeNodeBase *I : *this) {
110  const NodeT *N = I->getBlock();
111  if (OtherChildren.count(N) == 0)
112  return true;
113  }
114  return false;
115  }
116 
117  void setIDom(DomTreeNodeBase *NewIDom) {
118  assert(IDom && "No immediate dominator?");
119  if (IDom == NewIDom) return;
120 
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);
126 
127  // Switch to new dominator
128  IDom = NewIDom;
129  IDom->Children.push_back(this);
130 
131  UpdateLevel();
132  }
133 
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; }
139 
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;
146  }
147 
148  void UpdateLevel() {
149  assert(IDom);
150  if (Level == IDom->Level + 1) return;
151 
152  SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
153 
154  while (!WorkStack.empty()) {
155  DomTreeNodeBase *Current = WorkStack.pop_back_val();
156  Current->Level = Current->IDom->Level + 1;
157 
158  for (DomTreeNodeBase *C : *Current) {
159  assert(C->IDom);
160  if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
161  }
162  }
163  }
164 };
165 
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>>";
172 
173  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
174  << Node->getLevel() << "]\n";
175 
176  return O;
177 }
178 
179 template <class NodeT>
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);
187 }
188 
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);
193 
194 template <typename DomTreeT>
195 void CalculateWithUpdates(DomTreeT &DT,
197 
198 template <typename DomTreeT>
199 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200  typename DomTreeT::NodePtr To);
201 
202 template <typename DomTreeT>
203 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
204  typename DomTreeT::NodePtr To);
205 
206 template <typename DomTreeT>
207 void ApplyUpdates(DomTreeT &DT,
209 
210 template <typename DomTreeT>
211 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
212 } // namespace DomTreeBuilder
213 
214 /// Core dominator tree base class.
215 ///
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;
230 
233  static constexpr UpdateKind Insert = UpdateKind::Insert;
234  static constexpr UpdateKind Delete = UpdateKind::Delete;
235 
236  enum class VerificationLevel { Fast, Basic, Full };
237 
238 protected:
239  // Dominators always have a single root, postdominators can have more.
241 
242  using DomTreeNodeMapType =
246  ParentPtr Parent = nullptr;
247 
248  mutable bool DFSInfoValid = false;
249  mutable unsigned int SlowQueries = 0;
250 
252 
253  public:
255 
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();
264  }
265 
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;
275  }
276 
277  DominatorTreeBase(const DominatorTreeBase &) = delete;
278  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
279 
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).
283  ///
284  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
285 
286  /// isPostDominator - Returns true if analysis based of postdoms
287  ///
288  bool isPostDominator() const { return IsPostDominator; }
289 
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;
294 
295  if (Roots.size() != Other.Roots.size())
296  return true;
297 
298  if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
299  return true;
300 
301  const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
302  if (DomTreeNodes.size() != OtherDomTreeNodes.size())
303  return true;
304 
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;
311 
312  DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
313  DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
314 
315  if (MyNd.compare(&OtherNd))
316  return true;
317  }
318 
319  return false;
320  }
321 
322  void releaseMemory() { reset(); }
323 
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;
333  }
334 
335  /// See getNode.
336  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
337  return getNode(BB);
338  }
339 
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.
346  ///
347  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
348  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
349 
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.
357  WL.push_back(RN);
358 
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());
363  }
364  }
365 
366  /// properlyDominates - Returns true iff A dominates B and A != B.
367  /// Note that this is not a constant time operation!
368  ///
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);
376  }
377 
378  bool properlyDominates(const NodeT *A, const NodeT *B) const;
379 
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)));
386  }
387 
388  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
389 
390  /// dominates - Returns true iff A dominates B. Note that this is not a
391  /// constant time operation!
392  ///
394  const DomTreeNodeBase<NodeT> *B) const {
395  // A node trivially dominates itself.
396  if (B == A)
397  return true;
398 
399  // An unreachable node is dominated by anything.
400  if (!isReachableFromEntry(B))
401  return true;
402 
403  // And dominates nothing.
404  if (!isReachableFromEntry(A))
405  return false;
406 
407  if (B->getIDom() == A) return true;
408 
409  if (A->getIDom() == B) return false;
410 
411  // A can only dominate B if it is higher in the tree.
412  if (A->getLevel() >= B->getLevel()) return false;
413 
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
421 
422  if (DFSInfoValid)
423  return B->DominatedBy(A);
424 
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);
431  }
432 
433  return dominatedBySlowTreeWalk(A, B);
434  }
435 
436  bool dominates(const NodeT *A, const NodeT *B) const;
437 
438  NodeT *getRoot() const {
439  assert(this->Roots.size() == 1 && "Should always have entry node!");
440  return this->Roots[0];
441  }
442 
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");
449 
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;
456  }
457 
458  DomTreeNodeBase<NodeT> *NodeA = getNode(A);
459  DomTreeNodeBase<NodeT> *NodeB = getNode(B);
460 
461  if (!NodeA || !NodeB) return nullptr;
462 
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);
467 
468  NodeA = NodeA->IDom;
469  }
470 
471  return NodeA ? NodeA->getBlock() : nullptr;
472  }
473 
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));
480  }
481 
482  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
483  return isPostDominator() && !A->getBlock();
484  }
485 
486  //===--------------------------------------------------------------------===//
487  // API to update (Post)DominatorTree information based on modifications to
488  // the CFG...
489 
490  /// Inform the dominator tree about a sequence of CFG edge insertions and
491  /// deletions and perform a batch update on the tree.
492  ///
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.
502  ///
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.
506  ///
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.
511  ///
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.
517  ///
518  /// \param Updates An unordered sequence of updates to perform.
519  ///
521  DomTreeBuilder::ApplyUpdates(*this, Updates);
522  }
523 
524  /// Inform the dominator tree about a CFG edge insertion and update the tree.
525  ///
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.
529  ///
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).
532  ///
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);
539  }
540 
541  /// Inform the dominator tree about a CFG edge deletion and update the tree.
542  ///
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.
547  ///
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).
550  ///
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);
557  }
558 
559  /// Add a new node to the dominator tree information.
560  ///
561  /// This creates a new node as a child of DomBB dominator node, linking it
562  /// into the children list of the immediate dominator.
563  ///
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.
567  ///
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  llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
575  }
576 
577  /// Add a new node to the forward dominator tree and make it a new root.
578  ///
579  /// \param BB New node in CFG.
580  /// \returns New dominator tree node that represents new CFG node.
581  ///
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  llvm::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;
599  }
600  return RootNode = NewNode;
601  }
602 
603  /// changeImmediateDominator - This method is used to update the dominator
604  /// tree information when a node's immediate dominator changes.
605  ///
607  DomTreeNodeBase<NodeT> *NewIDom) {
608  assert(N && NewIDom && "Cannot change null node pointers!");
609  DFSInfoValid = false;
610  N->setIDom(NewIDom);
611  }
612 
613  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
614  changeImmediateDominator(getNode(BB), getNode(NewBB));
615  }
616 
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.");
624 
625  DFSInfoValid = false;
626 
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);
635  }
636 
637  DomTreeNodes.erase(BB);
638 
639  if (!IsPostDom) return;
640 
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();
646  }
647  }
648 
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);
656  }
657 
658  /// print - Convert to human readable form
659  ///
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";
669 
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 << " ";
676  }
677  O << "\n";
678  }
679 
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;
687  }
688 
691  32> WorkStack;
692 
693  const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
694  assert((!Parent || ThisRoot) && "Empty constructed DomTree");
695  if (!ThisRoot)
696  return;
697 
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()});
701 
702  unsigned DFSNum = 0;
703  ThisRoot->DFSNumIn = DFSNum++;
704 
705  while (!WorkStack.empty()) {
706  const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
707  const auto ChildIt = WorkStack.back().second;
708 
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;
718 
719  WorkStack.push_back({Child, Child->begin()});
720  Child->DFSNumIn = DFSNum++;
721  }
722  }
723 
724  SlowQueries = 0;
725  DFSInfoValid = true;
726  }
727 
728  /// recalculate - compute a dominator tree for the given function
729  void recalculate(ParentType &Func) {
730  Parent = &Func;
732  }
733 
735  Parent = &Func;
736  DomTreeBuilder::CalculateWithUpdates(*this, Updates);
737  }
738 
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.
744  ///
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.
748  ///
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).
754  return DomTreeBuilder::Verify(*this, VL);
755  }
756 
757 protected:
758  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
759 
760  void reset() {
761  DomTreeNodes.clear();
762  Roots.clear();
763  RootNode = nullptr;
764  Parent = nullptr;
765  DFSInfoValid = false;
766  SlowQueries = 0;
767  }
768 
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);
779 
780  std::vector<NodeRef> PredBlocks;
781  for (const auto &Pred : children<Inverse<N>>(NewBB))
782  PredBlocks.push_back(Pred);
783 
784  assert(!PredBlocks.empty() && "No predblocks?");
785 
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;
792  }
793  }
794 
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;
803  }
804 
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;
809 
810  for (i = i + 1; i < PredBlocks.size(); ++i) {
811  if (isReachableFromEntry(PredBlocks[i]))
812  NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
813  }
814 
815  // Create the new dominator tree node... and set the idom of NewBB.
816  DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
817 
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);
823  }
824  }
825 
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));
832 
833  const unsigned ALevel = A->getLevel();
834  const DomTreeNodeBase<NodeT> *IDom;
835 
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
840 
841  return B == A;
842  }
843 
844  /// Wipe this tree's state without releasing any resources.
845  ///
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;
852  }
853 };
854 
855 template <typename T>
857 
858 template <typename T>
860 
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>
865  const NodeT *B) const {
866  if (A == B)
867  return true;
868 
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)));
874 }
875 template <typename NodeT, bool IsPostDom>
877  const NodeT *A, const NodeT *B) const {
878  if (A == B)
879  return false;
880 
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)));
886 }
887 
888 } // end namespace llvm
889 
890 #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:121
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:1405
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:937
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:877
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...
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:32
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:63
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:78
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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")
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:370
typename std::remove_pointer< ParentPtr >::type ParentType
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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:381
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:52
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:1213
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:417
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:837
size_t getNumChildren() const
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
DomTreeNodeBase< NodeT > * RootNode
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
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:387
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.
bool compare(const DomTreeNodeBase *Other) const
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#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...
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:42
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:45
NodeT * getRoot() const
unsigned getLevel() const
const_iterator end() const
void setIDom(DomTreeNodeBase *NewIDom)