LLVM  6.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 <algorithm>
28 #include <cassert>
29 #include <cstddef>
30 #include <iterator>
31 #include <memory>
32 #include <type_traits>
33 #include <utility>
34 #include <vector>
35 #include "llvm/ADT/DenseMap.h"
36 #include "llvm/ADT/GraphTraits.h"
38 #include "llvm/ADT/STLExtras.h"
39 #include "llvm/ADT/SmallPtrSet.h"
40 #include "llvm/ADT/SmallVector.h"
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 /// \brief Base class for the actual dominator tree node.
54 template <class NodeT> class DomTreeNodeBase {
55  friend struct PostDominatorTree;
56  friend class DominatorTreeBase<NodeT, false>;
57  friend class DominatorTreeBase<NodeT, true>;
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 InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
196  typename DomTreeT::NodePtr To);
197 
198 template <typename DomTreeT>
199 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
200  typename DomTreeT::NodePtr To);
201 
202 // UpdateKind and Update are used by the batch update API and it's easiest to
203 // define them here.
205 
206 template <typename NodePtr>
207 struct Update {
209 
210  NodePtr From;
212 
213  Update(UpdateKind Kind, NodePtr From, NodePtr To)
214  : From(From), ToAndKind(To, Kind) {}
215 
216  UpdateKind getKind() const { return ToAndKind.getInt(); }
217  NodePtr getFrom() const { return From; }
218  NodePtr getTo() const { return ToAndKind.getPointer(); }
219  bool operator==(const Update &RHS) const {
220  return From == RHS.From && ToAndKind == RHS.ToAndKind;
221  }
222 
223  friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
224  OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
225  U.getFrom()->printAsOperand(OS, false);
226  OS << " -> ";
227  U.getTo()->printAsOperand(OS, false);
228  return OS;
229  }
230 };
231 
232 template <typename DomTreeT>
233 void ApplyUpdates(DomTreeT &DT,
235 
236 template <typename DomTreeT>
237 bool Verify(const DomTreeT &DT);
238 } // namespace DomTreeBuilder
239 
240 /// \brief Core dominator tree base class.
241 ///
242 /// This class is a generic template over graph nodes. It is instantiated for
243 /// various graphs in the LLVM IR or in the code generator.
244 template <typename NodeT, bool IsPostDom>
245 class DominatorTreeBase {
246  public:
247  static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
248  "Currently DominatorTreeBase supports only pointer nodes");
249  using NodeType = NodeT;
250  using NodePtr = NodeT *;
251  using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
252  static_assert(std::is_pointer<ParentPtr>::value,
253  "Currently NodeT's parent must be a pointer type");
254  using ParentType = typename std::remove_pointer<ParentPtr>::type;
255  static constexpr bool IsPostDominator = IsPostDom;
256 
261 
262  protected:
263  // Dominators always have a single root, postdominators can have more.
265 
266  using DomTreeNodeMapType =
270  ParentPtr Parent = nullptr;
271 
272  mutable bool DFSInfoValid = false;
273  mutable unsigned int SlowQueries = 0;
274 
276 
277  public:
279 
281  : Roots(std::move(Arg.Roots)),
282  DomTreeNodes(std::move(Arg.DomTreeNodes)),
283  RootNode(Arg.RootNode),
284  Parent(Arg.Parent),
285  DFSInfoValid(Arg.DFSInfoValid),
286  SlowQueries(Arg.SlowQueries) {
287  Arg.wipe();
288  }
289 
291  Roots = std::move(RHS.Roots);
292  DomTreeNodes = std::move(RHS.DomTreeNodes);
293  RootNode = RHS.RootNode;
294  Parent = RHS.Parent;
295  DFSInfoValid = RHS.DFSInfoValid;
296  SlowQueries = RHS.SlowQueries;
297  RHS.wipe();
298  return *this;
299  }
300 
301  DominatorTreeBase(const DominatorTreeBase &) = delete;
302  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
303 
304  /// getRoots - Return the root blocks of the current CFG. This may include
305  /// multiple blocks if we are computing post dominators. For forward
306  /// dominators, this will always be a single block (the entry node).
307  ///
308  const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
309 
310  /// isPostDominator - Returns true if analysis based of postdoms
311  ///
312  bool isPostDominator() const { return IsPostDominator; }
313 
314  /// compare - Return false if the other dominator tree base matches this
315  /// dominator tree base. Otherwise return true.
316  bool compare(const DominatorTreeBase &Other) const {
317  if (Parent != Other.Parent) return true;
318 
319  const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
320  if (DomTreeNodes.size() != OtherDomTreeNodes.size())
321  return true;
322 
323  for (const auto &DomTreeNode : DomTreeNodes) {
324  NodeT *BB = DomTreeNode.first;
325  typename DomTreeNodeMapType::const_iterator OI =
326  OtherDomTreeNodes.find(BB);
327  if (OI == OtherDomTreeNodes.end())
328  return true;
329 
330  DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
331  DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
332 
333  if (MyNd.compare(&OtherNd))
334  return true;
335  }
336 
337  return false;
338  }
339 
340  void releaseMemory() { reset(); }
341 
342  /// getNode - return the (Post)DominatorTree node for the specified basic
343  /// block. This is the same as using operator[] on this class. The result
344  /// may (but is not required to) be null for a forward (backwards)
345  /// statically unreachable block.
346  DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
347  auto I = DomTreeNodes.find(BB);
348  if (I != DomTreeNodes.end())
349  return I->second.get();
350  return nullptr;
351  }
352 
353  /// See getNode.
354  DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); }
355 
356  /// getRootNode - This returns the entry node for the CFG of the function. If
357  /// this tree represents the post-dominance relations for a function, however,
358  /// this root may be a node with the block == NULL. This is the case when
359  /// there are multiple exit nodes from a particular function. Consumers of
360  /// post-dominance information must be capable of dealing with this
361  /// possibility.
362  ///
363  DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
364  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
365 
366  /// Get all nodes dominated by R, including R itself.
367  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
368  Result.clear();
369  const DomTreeNodeBase<NodeT> *RN = getNode(R);
370  if (!RN)
371  return; // If R is unreachable, it will not be present in the DOM tree.
373  WL.push_back(RN);
374 
375  while (!WL.empty()) {
376  const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
377  Result.push_back(N->getBlock());
378  WL.append(N->begin(), N->end());
379  }
380  }
381 
382  /// properlyDominates - Returns true iff A dominates B and A != B.
383  /// Note that this is not a constant time operation!
384  ///
386  const DomTreeNodeBase<NodeT> *B) const {
387  if (!A || !B)
388  return false;
389  if (A == B)
390  return false;
391  return dominates(A, B);
392  }
393 
394  bool properlyDominates(const NodeT *A, const NodeT *B) const;
395 
396  /// isReachableFromEntry - Return true if A is dominated by the entry
397  /// block of the function containing it.
398  bool isReachableFromEntry(const NodeT *A) const {
399  assert(!this->isPostDominator() &&
400  "This is not implemented for post dominators");
401  return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
402  }
403 
404  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
405 
406  /// dominates - Returns true iff A dominates B. Note that this is not a
407  /// constant time operation!
408  ///
410  const DomTreeNodeBase<NodeT> *B) const {
411  // A node trivially dominates itself.
412  if (B == A)
413  return true;
414 
415  // An unreachable node is dominated by anything.
416  if (!isReachableFromEntry(B))
417  return true;
418 
419  // And dominates nothing.
420  if (!isReachableFromEntry(A))
421  return false;
422 
423  if (B->getIDom() == A) return true;
424 
425  if (A->getIDom() == B) return false;
426 
427  // A can only dominate B if it is higher in the tree.
428  if (A->getLevel() >= B->getLevel()) return false;
429 
430  // Compare the result of the tree walk and the dfs numbers, if expensive
431  // checks are enabled.
432 #ifdef EXPENSIVE_CHECKS
433  assert((!DFSInfoValid ||
434  (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
435  "Tree walk disagrees with dfs numbers!");
436 #endif
437 
438  if (DFSInfoValid)
439  return B->DominatedBy(A);
440 
441  // If we end up with too many slow queries, just update the
442  // DFS numbers on the theory that we are going to keep querying.
443  SlowQueries++;
444  if (SlowQueries > 32) {
445  updateDFSNumbers();
446  return B->DominatedBy(A);
447  }
448 
449  return dominatedBySlowTreeWalk(A, B);
450  }
451 
452  bool dominates(const NodeT *A, const NodeT *B) const;
453 
454  NodeT *getRoot() const {
455  assert(this->Roots.size() == 1 && "Should always have entry node!");
456  return this->Roots[0];
457  }
458 
459  /// findNearestCommonDominator - Find nearest common dominator basic block
460  /// for basic block A and B. If there is no such block then return nullptr.
461  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
462  assert(A && B && "Pointers are not valid");
463  assert(A->getParent() == B->getParent() &&
464  "Two blocks are not in same function");
465 
466  // If either A or B is a entry block then it is nearest common dominator
467  // (for forward-dominators).
468  if (!isPostDominator()) {
469  NodeT &Entry = A->getParent()->front();
470  if (A == &Entry || B == &Entry)
471  return &Entry;
472  }
473 
474  DomTreeNodeBase<NodeT> *NodeA = getNode(A);
475  DomTreeNodeBase<NodeT> *NodeB = getNode(B);
476 
477  if (!NodeA || !NodeB) return nullptr;
478 
479  // Use level information to go up the tree until the levels match. Then
480  // continue going up til we arrive at the same node.
481  while (NodeA && NodeA != NodeB) {
482  if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
483 
484  NodeA = NodeA->IDom;
485  }
486 
487  return NodeA ? NodeA->getBlock() : nullptr;
488  }
489 
490  const NodeT *findNearestCommonDominator(const NodeT *A,
491  const NodeT *B) const {
492  // Cast away the const qualifiers here. This is ok since
493  // const is re-introduced on the return type.
494  return findNearestCommonDominator(const_cast<NodeT *>(A),
495  const_cast<NodeT *>(B));
496  }
497 
498  bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
499  return isPostDominator() && !A->getBlock();
500  }
501 
502  //===--------------------------------------------------------------------===//
503  // API to update (Post)DominatorTree information based on modifications to
504  // the CFG...
505 
506  /// Inform the dominator tree about a sequence of CFG edge insertions and
507  /// deletions and perform a batch update on the tree.
508  ///
509  /// This function should be used when there were multiple CFG updates after
510  /// the last dominator tree update. It takes care of performing the updates
511  /// in sync with the CFG and optimizes away the redundant operations that
512  /// cancel each other.
513  /// The functions expects the sequence of updates to be balanced. Eg.:
514  /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
515  /// logically it results in a single insertions.
516  /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
517  /// sense to insert the same edge twice.
518  ///
519  /// What's more, the functions assumes that it's safe to ask every node in the
520  /// CFG about its children and inverse children. This implies that deletions
521  /// of CFG edges must not delete the CFG nodes before calling this function.
522  ///
523  /// Batch updates should be generally faster when performing longer sequences
524  /// of updates than calling insertEdge/deleteEdge manually multiple times, as
525  /// it can reorder the updates and remove redundant ones internally.
526  /// The batch updater is also able to detect sequences of zero and exactly one
527  /// update -- it's optimized to do less work in these cases.
528  ///
529  /// Note that for postdominators it automatically takes care of applying
530  /// updates on reverse edges internally (so there's no need to swap the
531  /// From and To pointers when constructing DominatorTree::UpdateType).
532  /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
533  /// with the same template parameter T.
534  ///
535  /// \param Updates An unordered sequence of updates to perform.
536  ///
538  DomTreeBuilder::ApplyUpdates(*this, Updates);
539  }
540 
541  /// Inform the dominator tree about a CFG edge insertion and update the tree.
542  ///
543  /// This function has to be called just before or just after making the update
544  /// on the actual CFG. There cannot be any other updates that the dominator
545  /// tree doesn't know about.
546  ///
547  /// Note that for postdominators it automatically takes care of inserting
548  /// a reverse edge internally (so there's no need to swap the parameters).
549  ///
550  void insertEdge(NodeT *From, NodeT *To) {
551  assert(From);
552  assert(To);
553  assert(From->getParent() == Parent);
554  assert(To->getParent() == Parent);
555  DomTreeBuilder::InsertEdge(*this, From, To);
556  }
557 
558  /// Inform the dominator tree about a CFG edge deletion and update the tree.
559  ///
560  /// This function has to be called just after making the update on the actual
561  /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
562  /// DEBUG mode. There cannot be any other updates that the
563  /// dominator tree doesn't know about.
564  ///
565  /// Note that for postdominators it automatically takes care of deleting
566  /// a reverse edge internally (so there's no need to swap the parameters).
567  ///
568  void deleteEdge(NodeT *From, NodeT *To) {
569  assert(From);
570  assert(To);
571  assert(From->getParent() == Parent);
572  assert(To->getParent() == Parent);
573  DomTreeBuilder::DeleteEdge(*this, From, To);
574  }
575 
576  /// Add a new node to the dominator tree information.
577  ///
578  /// This creates a new node as a child of DomBB dominator node, linking it
579  /// into the children list of the immediate dominator.
580  ///
581  /// \param BB New node in CFG.
582  /// \param DomBB CFG node that is dominator for BB.
583  /// \returns New dominator tree node that represents new CFG node.
584  ///
585  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
586  assert(getNode(BB) == nullptr && "Block already in dominator tree!");
587  DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
588  assert(IDomNode && "Not immediate dominator specified for block!");
589  DFSInfoValid = false;
590  return (DomTreeNodes[BB] = IDomNode->addChild(
591  llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
592  }
593 
594  /// Add a new node to the forward dominator tree and make it a new root.
595  ///
596  /// \param BB New node in CFG.
597  /// \returns New dominator tree node that represents new CFG node.
598  ///
600  assert(getNode(BB) == nullptr && "Block already in dominator tree!");
601  assert(!this->isPostDominator() &&
602  "Cannot change root of post-dominator tree");
603  DFSInfoValid = false;
604  DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
605  llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
606  if (Roots.empty()) {
607  addRoot(BB);
608  } else {
609  assert(Roots.size() == 1);
610  NodeT *OldRoot = Roots.front();
611  auto &OldNode = DomTreeNodes[OldRoot];
612  OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
613  OldNode->IDom = NewNode;
614  OldNode->UpdateLevel();
615  Roots[0] = BB;
616  }
617  return RootNode = NewNode;
618  }
619 
620  /// changeImmediateDominator - This method is used to update the dominator
621  /// tree information when a node's immediate dominator changes.
622  ///
624  DomTreeNodeBase<NodeT> *NewIDom) {
625  assert(N && NewIDom && "Cannot change null node pointers!");
626  DFSInfoValid = false;
627  N->setIDom(NewIDom);
628  }
629 
630  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
631  changeImmediateDominator(getNode(BB), getNode(NewBB));
632  }
633 
634  /// eraseNode - Removes a node from the dominator tree. Block must not
635  /// dominate any other blocks. Removes node from its immediate dominator's
636  /// children list. Deletes dominator node associated with basic block BB.
637  void eraseNode(NodeT *BB) {
638  DomTreeNodeBase<NodeT> *Node = getNode(BB);
639  assert(Node && "Removing node that isn't in dominator tree.");
640  assert(Node->getChildren().empty() && "Node is not a leaf node.");
641 
642  DFSInfoValid = false;
643 
644  // Remove node from immediate dominator's children list.
645  DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
646  if (IDom) {
647  const auto I = find(IDom->Children, Node);
648  assert(I != IDom->Children.end() &&
649  "Not in immediate dominator children set!");
650  // I am no longer your child...
651  IDom->Children.erase(I);
652  }
653 
654  DomTreeNodes.erase(BB);
655 
656  if (!IsPostDom) return;
657 
658  // Remember to update PostDominatorTree roots.
659  auto RIt = llvm::find(Roots, BB);
660  if (RIt != Roots.end()) {
661  std::swap(*RIt, Roots.back());
662  Roots.pop_back();
663  }
664  }
665 
666  /// splitBlock - BB is split and now it has one successor. Update dominator
667  /// tree to reflect this change.
668  void splitBlock(NodeT *NewBB) {
669  if (IsPostDominator)
670  Split<Inverse<NodeT *>>(NewBB);
671  else
672  Split<NodeT *>(NewBB);
673  }
674 
675  /// print - Convert to human readable form
676  ///
677  void print(raw_ostream &O) const {
678  O << "=============================--------------------------------\n";
679  if (IsPostDominator)
680  O << "Inorder PostDominator Tree: ";
681  else
682  O << "Inorder Dominator Tree: ";
683  if (!DFSInfoValid)
684  O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
685  O << "\n";
686 
687  // The postdom tree can have a null root if there are no returns.
688  if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
689  if (IsPostDominator) {
690  O << "Roots: ";
691  for (const NodePtr Block : Roots) {
692  Block->printAsOperand(O, false);
693  O << " ";
694  }
695  O << "\n";
696  }
697  }
698 
699 public:
700  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
701  /// dominator tree in dfs order.
702  void updateDFSNumbers() const {
703  if (DFSInfoValid) {
704  SlowQueries = 0;
705  return;
706  }
707 
710  32> WorkStack;
711 
712  const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
713  assert((!Parent || ThisRoot) && "Empty constructed DomTree");
714  if (!ThisRoot)
715  return;
716 
717  // Both dominators and postdominators have a single root node. In the case
718  // case of PostDominatorTree, this node is a virtual root.
719  WorkStack.push_back({ThisRoot, ThisRoot->begin()});
720 
721  unsigned DFSNum = 0;
722  ThisRoot->DFSNumIn = DFSNum++;
723 
724  while (!WorkStack.empty()) {
725  const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
726  const auto ChildIt = WorkStack.back().second;
727 
728  // If we visited all of the children of this node, "recurse" back up the
729  // stack setting the DFOutNum.
730  if (ChildIt == Node->end()) {
731  Node->DFSNumOut = DFSNum++;
732  WorkStack.pop_back();
733  } else {
734  // Otherwise, recursively visit this child.
735  const DomTreeNodeBase<NodeT> *Child = *ChildIt;
736  ++WorkStack.back().second;
737 
738  WorkStack.push_back({Child, Child->begin()});
739  Child->DFSNumIn = DFSNum++;
740  }
741  }
742 
743  SlowQueries = 0;
744  DFSInfoValid = true;
745  }
746 
747  /// recalculate - compute a dominator tree for the given function
748  void recalculate(ParentType &Func) {
749  Parent = &Func;
751  }
752 
753  /// verify - check parent and sibling property
754  bool verify() const { return DomTreeBuilder::Verify(*this); }
755 
756  protected:
757  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
758 
759  void reset() {
760  DomTreeNodes.clear();
761  Roots.clear();
762  RootNode = nullptr;
763  Parent = nullptr;
764  DFSInfoValid = false;
765  SlowQueries = 0;
766  }
767 
768  // NewBB is split and now it has one successor. Update dominator tree to
769  // reflect this change.
770  template <class N>
771  void Split(typename GraphTraits<N>::NodeRef NewBB) {
772  using GraphT = GraphTraits<N>;
773  using NodeRef = typename GraphT::NodeRef;
774  assert(std::distance(GraphT::child_begin(NewBB),
775  GraphT::child_end(NewBB)) == 1 &&
776  "NewBB should have a single successor!");
777  NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
778 
779  std::vector<NodeRef> PredBlocks;
780  for (const auto &Pred : children<Inverse<N>>(NewBB))
781  PredBlocks.push_back(Pred);
782 
783  assert(!PredBlocks.empty() && "No predblocks?");
784 
785  bool NewBBDominatesNewBBSucc = true;
786  for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
787  if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
788  isReachableFromEntry(Pred)) {
789  NewBBDominatesNewBBSucc = false;
790  break;
791  }
792  }
793 
794  // Find NewBB's immediate dominator and create new dominator tree node for
795  // NewBB.
796  NodeT *NewBBIDom = nullptr;
797  unsigned i = 0;
798  for (i = 0; i < PredBlocks.size(); ++i)
799  if (isReachableFromEntry(PredBlocks[i])) {
800  NewBBIDom = PredBlocks[i];
801  break;
802  }
803 
804  // It's possible that none of the predecessors of NewBB are reachable;
805  // in that case, NewBB itself is unreachable, so nothing needs to be
806  // changed.
807  if (!NewBBIDom) return;
808 
809  for (i = i + 1; i < PredBlocks.size(); ++i) {
810  if (isReachableFromEntry(PredBlocks[i]))
811  NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
812  }
813 
814  // Create the new dominator tree node... and set the idom of NewBB.
815  DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
816 
817  // If NewBB strictly dominates other blocks, then it is now the immediate
818  // dominator of NewBBSucc. Update the dominator tree as appropriate.
819  if (NewBBDominatesNewBBSucc) {
820  DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
821  changeImmediateDominator(NewBBSuccNode, NewBBNode);
822  }
823  }
824 
825  private:
826  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
827  const DomTreeNodeBase<NodeT> *B) const {
828  assert(A != B);
829  assert(isReachableFromEntry(B));
830  assert(isReachableFromEntry(A));
831 
832  const DomTreeNodeBase<NodeT> *IDom;
833  while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
834  B = IDom; // Walk up the tree
835  return IDom != nullptr;
836  }
837 
838  /// \brief Wipe this tree's state without releasing any resources.
839  ///
840  /// This is essentially a post-move helper only. It leaves the object in an
841  /// assignable and destroyable state, but otherwise invalid.
842  void wipe() {
843  DomTreeNodes.clear();
844  RootNode = nullptr;
845  Parent = nullptr;
846  }
847 };
848 
849 template <typename T>
851 
852 template <typename T>
854 
855 // These two functions are declared out of line as a workaround for building
856 // with old (< r147295) versions of clang because of pr11642.
857 template <typename NodeT, bool IsPostDom>
859  const NodeT *B) const {
860  if (A == B)
861  return true;
862 
863  // Cast away the const qualifiers here. This is ok since
864  // this function doesn't actually return the values returned
865  // from getNode.
866  return dominates(getNode(const_cast<NodeT *>(A)),
867  getNode(const_cast<NodeT *>(B)));
868 }
869 template <typename NodeT, bool IsPostDom>
871  const NodeT *A, const NodeT *B) const {
872  if (A == B)
873  return false;
874 
875  // Cast away the const qualifiers here. This is ok since
876  // this function doesn't actually return the values returned
877  // from getNode.
878  return dominates(getNode(const_cast<NodeT *>(A)),
879  getNode(const_cast<NodeT *>(B)));
880 }
881 
882 } // end namespace llvm
883 
884 #endif // LLVM_SUPPORT_GENERICDOMTREE_H
uint64_t CallInst * C
DomTreeNodeBase< NodeT > * getNode(NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
UpdateKind getKind() const
typename std::vector< DomTreeNodeBase *>::const_iterator const_iterator
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:102
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
PointerTy getPointer() const
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
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.
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:944
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:920
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
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:736
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
IntType getInt() 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.
Update(UpdateKind Kind, NodePtr From, NodePtr To)
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
bool Verify(const DomTreeT &DT)
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:59
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:371
bool verify() const
verify - check parent and sibling property
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 > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
bool operator==(const Update &RHS) const
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:834
void print(raw_ostream &O) const
print - Convert to human readable form
const_iterator begin() const
friend raw_ostream & operator<<(raw_ostream &OS, const Update &U)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
size_t getNumChildren() const
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
DomTreeNodeBase< NodeT > * RootNode
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
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:398
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
Basic Alias true
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
bool compare(const DomTreeNodeBase *Other) const
DomTreeNodeBase< NodeT > * operator[](NodeT *BB) const
See getNode.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#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
const unsigned Kind
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:44
NodeT * getRoot() const
unsigned getLevel() const
const_iterator end() const
void setIDom(DomTreeNodeBase *NewIDom)