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