LLVM  13.0.0git
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"
28 #include "llvm/ADT/STLExtras.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/Support/CFGDiff.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 
42 namespace llvm {
43 
44 template <typename NodeT, bool IsPostDom>
45 class DominatorTreeBase;
46 
47 namespace DomTreeBuilder {
48 template <typename DomTreeT>
49 struct SemiNCAInfo;
50 } // namespace DomTreeBuilder
51 
52 /// Base class for the actual dominator tree node.
53 template <class NodeT> class DomTreeNodeBase {
54  friend class PostDominatorTree;
55  friend class DominatorTreeBase<NodeT, false>;
56  friend class DominatorTreeBase<NodeT, true>;
59 
60  NodeT *TheBB;
61  DomTreeNodeBase *IDom;
62  unsigned Level;
64  mutable unsigned DFSNumIn = ~0;
65  mutable unsigned DFSNumOut = ~0;
66 
67  public:
69  : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
70 
72  using const_iterator =
74 
75  iterator begin() { return Children.begin(); }
76  iterator end() { return Children.end(); }
77  const_iterator begin() const { return Children.begin(); }
78  const_iterator end() const { return Children.end(); }
79 
80  DomTreeNodeBase *const &back() const { return Children.back(); }
81  DomTreeNodeBase *&back() { return Children.back(); }
82 
85  return make_range(begin(), end());
86  }
87 
88  NodeT *getBlock() const { return TheBB; }
89  DomTreeNodeBase *getIDom() const { return IDom; }
90  unsigned getLevel() const { return Level; }
91 
92  std::unique_ptr<DomTreeNodeBase> addChild(
93  std::unique_ptr<DomTreeNodeBase> C) {
94  Children.push_back(C.get());
95  return C;
96  }
97 
98  bool isLeaf() const { return Children.empty(); }
99  size_t getNumChildren() const { return Children.size(); }
100 
101  void clearAllChildren() { Children.clear(); }
102 
103  bool compare(const DomTreeNodeBase *Other) const {
104  if (getNumChildren() != Other->getNumChildren())
105  return true;
106 
107  if (Level != Other->Level) return true;
108 
109  SmallPtrSet<const NodeT *, 4> OtherChildren;
110  for (const DomTreeNodeBase *I : *Other) {
111  const NodeT *Nd = I->getBlock();
112  OtherChildren.insert(Nd);
113  }
114 
115  for (const DomTreeNodeBase *I : *this) {
116  const NodeT *N = I->getBlock();
117  if (OtherChildren.count(N) == 0)
118  return true;
119  }
120  return false;
121  }
122 
123  void setIDom(DomTreeNodeBase *NewIDom) {
124  assert(IDom && "No immediate dominator?");
125  if (IDom == NewIDom) return;
126 
127  auto I = find(IDom->Children, this);
128  assert(I != IDom->Children.end() &&
129  "Not in immediate dominator children set!");
130  // I am no longer your child...
131  IDom->Children.erase(I);
132 
133  // Switch to new dominator
134  IDom = NewIDom;
135  IDom->Children.push_back(this);
136 
137  UpdateLevel();
138  }
139 
140  /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
141  /// in the dominator tree. They are only guaranteed valid if
142  /// updateDFSNumbers() has been called.
143  unsigned getDFSNumIn() const { return DFSNumIn; }
144  unsigned getDFSNumOut() const { return DFSNumOut; }
145 
146 private:
147  // Return true if this node is dominated by other. Use this only if DFS info
148  // is valid.
149  bool DominatedBy(const DomTreeNodeBase *other) const {
150  return this->DFSNumIn >= other->DFSNumIn &&
151  this->DFSNumOut <= other->DFSNumOut;
152  }
153 
154  void UpdateLevel() {
155  assert(IDom);
156  if (Level == IDom->Level + 1) return;
157 
158  SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
159 
160  while (!WorkStack.empty()) {
161  DomTreeNodeBase *Current = WorkStack.pop_back_val();
162  Current->Level = Current->IDom->Level + 1;
163 
164  for (DomTreeNodeBase *C : *Current) {
165  assert(C->IDom);
166  if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
167  }
168  }
169  }
170 };
171 
172 template <class NodeT>
174  if (Node->getBlock())
175  Node->getBlock()->printAsOperand(O, false);
176  else
177  O << " <<exit node>>";
178 
179  O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
180  << Node->getLevel() << "]\n";
181 
182  return O;
183 }
184 
185 template <class NodeT>
187  unsigned Lev) {
188  O.indent(2 * Lev) << "[" << Lev << "] " << N;
189  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
190  E = N->end();
191  I != E; ++I)
192  PrintDomTree<NodeT>(*I, O, Lev + 1);
193 }
194 
195 namespace DomTreeBuilder {
196 // The routines below are provided in a separate header but referenced here.
197 template <typename DomTreeT>
198 void Calculate(DomTreeT &DT);
199 
200 template <typename DomTreeT>
201 void CalculateWithUpdates(DomTreeT &DT,
202  ArrayRef<typename DomTreeT::UpdateType> Updates);
203 
204 template <typename DomTreeT>
205 void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
206  typename DomTreeT::NodePtr To);
207 
208 template <typename DomTreeT>
209 void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
210  typename DomTreeT::NodePtr To);
211 
212 template <typename DomTreeT>
213 void ApplyUpdates(DomTreeT &DT,
214  GraphDiff<typename DomTreeT::NodePtr,
215  DomTreeT::IsPostDominator> &PreViewCFG,
216  GraphDiff<typename DomTreeT::NodePtr,
217  DomTreeT::IsPostDominator> *PostViewCFG);
218 
219 template <typename DomTreeT>
220 bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
221 } // namespace DomTreeBuilder
222 
223 /// Core dominator tree base class.
224 ///
225 /// This class is a generic template over graph nodes. It is instantiated for
226 /// various graphs in the LLVM IR or in the code generator.
227 template <typename NodeT, bool IsPostDom>
228 class DominatorTreeBase {
229  public:
230  static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
231  "Currently DominatorTreeBase supports only pointer nodes");
232  using NodeType = NodeT;
233  using NodePtr = NodeT *;
234  using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
235  static_assert(std::is_pointer<ParentPtr>::value,
236  "Currently NodeT's parent must be a pointer type");
237  using ParentType = std::remove_pointer_t<ParentPtr>;
238  static constexpr bool IsPostDominator = IsPostDom;
239 
244 
245  enum class VerificationLevel { Fast, Basic, Full };
246 
247 protected:
248  // Dominators always have a single root, postdominators can have more.
250 
251  using DomTreeNodeMapType =
255  ParentPtr Parent = nullptr;
256 
257  mutable bool DFSInfoValid = false;
258  mutable unsigned int SlowQueries = 0;
259 
261 
262  public:
264 
266  : Roots(std::move(Arg.Roots)),
269  Parent(Arg.Parent),
272  Arg.wipe();
273  }
274 
276  Roots = std::move(RHS.Roots);
277  DomTreeNodes = std::move(RHS.DomTreeNodes);
278  RootNode = RHS.RootNode;
279  Parent = RHS.Parent;
280  DFSInfoValid = RHS.DFSInfoValid;
281  SlowQueries = RHS.SlowQueries;
282  RHS.wipe();
283  return *this;
284  }
285 
286  DominatorTreeBase(const DominatorTreeBase &) = delete;
287  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
288 
289  /// Iteration over roots.
290  ///
291  /// This may include multiple blocks if we are computing post dominators.
292  /// For forward dominators, this will always be a single block (the entry
293  /// block).
296 
297  root_iterator root_begin() { return Roots.begin(); }
298  const_root_iterator root_begin() const { return Roots.begin(); }
299  root_iterator root_end() { return Roots.end(); }
300  const_root_iterator root_end() const { return Roots.end(); }
301 
302  size_t root_size() const { return Roots.size(); }
303 
305  return make_range(root_begin(), root_end());
306  }
308  return make_range(root_begin(), root_end());
309  }
310 
311  /// isPostDominator - Returns true if analysis based of postdoms
312  ///
313  bool isPostDominator() const { return IsPostDominator; }
314 
315  /// compare - Return false if the other dominator tree base matches this
316  /// dominator tree base. Otherwise return true.
317  bool compare(const DominatorTreeBase &Other) const {
318  if (Parent != Other.Parent) return true;
319 
320  if (Roots.size() != Other.Roots.size())
321  return true;
322 
323  if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
324  return true;
325 
326  const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
327  if (DomTreeNodes.size() != OtherDomTreeNodes.size())
328  return true;
329 
330  for (const auto &DomTreeNode : DomTreeNodes) {
331  NodeT *BB = DomTreeNode.first;
332  typename DomTreeNodeMapType::const_iterator OI =
333  OtherDomTreeNodes.find(BB);
334  if (OI == OtherDomTreeNodes.end())
335  return true;
336 
337  DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
338  DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
339 
340  if (MyNd.compare(&OtherNd))
341  return true;
342  }
343 
344  return false;
345  }
346 
347  /// getNode - return the (Post)DominatorTree node for the specified basic
348  /// block. This is the same as using operator[] on this class. The result
349  /// may (but is not required to) be null for a forward (backwards)
350  /// statically unreachable block.
351  DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
352  auto I = DomTreeNodes.find(BB);
353  if (I != DomTreeNodes.end())
354  return I->second.get();
355  return nullptr;
356  }
357 
358  /// See getNode.
359  DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
360  return getNode(BB);
361  }
362 
363  /// getRootNode - This returns the entry node for the CFG of the function. If
364  /// this tree represents the post-dominance relations for a function, however,
365  /// this root may be a node with the block == NULL. This is the case when
366  /// there are multiple exit nodes from a particular function. Consumers of
367  /// post-dominance information must be capable of dealing with this
368  /// possibility.
369  ///
371  const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
372 
373  /// Get all nodes dominated by R, including R itself.
374  void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
375  Result.clear();
377  if (!RN)
378  return; // If R is unreachable, it will not be present in the DOM tree.
380  WL.push_back(RN);
381 
382  while (!WL.empty()) {
383  const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
384  Result.push_back(N->getBlock());
385  WL.append(N->begin(), N->end());
386  }
387  }
388 
389  /// properlyDominates - Returns true iff A dominates B and A != B.
390  /// Note that this is not a constant time operation!
391  ///
393  const DomTreeNodeBase<NodeT> *B) const {
394  if (!A || !B)
395  return false;
396  if (A == B)
397  return false;
398  return dominates(A, B);
399  }
400 
401  bool properlyDominates(const NodeT *A, const NodeT *B) const;
402 
403  /// isReachableFromEntry - Return true if A is dominated by the entry
404  /// block of the function containing it.
405  bool isReachableFromEntry(const NodeT *A) const {
406  assert(!this->isPostDominator() &&
407  "This is not implemented for post dominators");
408  return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
409  }
410 
411  bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
412 
413  /// dominates - Returns true iff A dominates B. Note that this is not a
414  /// constant time operation!
415  ///
417  const DomTreeNodeBase<NodeT> *B) const {
418  // A node trivially dominates itself.
419  if (B == A)
420  return true;
421 
422  // An unreachable node is dominated by anything.
423  if (!isReachableFromEntry(B))
424  return true;
425 
426  // And dominates nothing.
427  if (!isReachableFromEntry(A))
428  return false;
429 
430  if (B->getIDom() == A) return true;
431 
432  if (A->getIDom() == B) return false;
433 
434  // A can only dominate B if it is higher in the tree.
435  if (A->getLevel() >= B->getLevel()) return false;
436 
437  // Compare the result of the tree walk and the dfs numbers, if expensive
438  // checks are enabled.
439 #ifdef EXPENSIVE_CHECKS
440  assert((!DFSInfoValid ||
441  (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
442  "Tree walk disagrees with dfs numbers!");
443 #endif
444 
445  if (DFSInfoValid)
446  return B->DominatedBy(A);
447 
448  // If we end up with too many slow queries, just update the
449  // DFS numbers on the theory that we are going to keep querying.
450  SlowQueries++;
451  if (SlowQueries > 32) {
453  return B->DominatedBy(A);
454  }
455 
456  return dominatedBySlowTreeWalk(A, B);
457  }
458 
459  bool dominates(const NodeT *A, const NodeT *B) const;
460 
461  NodeT *getRoot() const {
462  assert(this->Roots.size() == 1 && "Should always have entry node!");
463  return this->Roots[0];
464  }
465 
466  /// Find nearest common dominator basic block for basic block A and B. A and B
467  /// must have tree nodes.
468  NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
469  assert(A && B && "Pointers are not valid");
470  assert(A->getParent() == B->getParent() &&
471  "Two blocks are not in same function");
472 
473  // If either A or B is a entry block then it is nearest common dominator
474  // (for forward-dominators).
475  if (!isPostDominator()) {
476  NodeT &Entry = A->getParent()->front();
477  if (A == &Entry || B == &Entry)
478  return &Entry;
479  }
480 
481  DomTreeNodeBase<NodeT> *NodeA = getNode(A);
482  DomTreeNodeBase<NodeT> *NodeB = getNode(B);
483  assert(NodeA && "A must be in the tree");
484  assert(NodeB && "B must be in the tree");
485 
486  // Use level information to go up the tree until the levels match. Then
487  // continue going up til we arrive at the same node.
488  while (NodeA != NodeB) {
489  if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
490 
491  NodeA = NodeA->IDom;
492  }
493 
494  return NodeA->getBlock();
495  }
496 
497  const NodeT *findNearestCommonDominator(const NodeT *A,
498  const NodeT *B) const {
499  // Cast away the const qualifiers here. This is ok since
500  // const is re-introduced on the return type.
501  return findNearestCommonDominator(const_cast<NodeT *>(A),
502  const_cast<NodeT *>(B));
503  }
504 
506  return isPostDominator() && !A->getBlock();
507  }
508 
509  //===--------------------------------------------------------------------===//
510  // API to update (Post)DominatorTree information based on modifications to
511  // the CFG...
512 
513  /// Inform the dominator tree about a sequence of CFG edge insertions and
514  /// deletions and perform a batch update on the tree.
515  ///
516  /// This function should be used when there were multiple CFG updates after
517  /// the last dominator tree update. It takes care of performing the updates
518  /// in sync with the CFG and optimizes away the redundant operations that
519  /// cancel each other.
520  /// The functions expects the sequence of updates to be balanced. Eg.:
521  /// - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
522  /// logically it results in a single insertions.
523  /// - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
524  /// sense to insert the same edge twice.
525  ///
526  /// What's more, the functions assumes that it's safe to ask every node in the
527  /// CFG about its children and inverse children. This implies that deletions
528  /// of CFG edges must not delete the CFG nodes before calling this function.
529  ///
530  /// The applyUpdates function can reorder the updates and remove redundant
531  /// ones internally. The batch updater is also able to detect sequences of
532  /// zero and exactly one update -- it's optimized to do less work in these
533  /// cases.
534  ///
535  /// Note that for postdominators it automatically takes care of applying
536  /// updates on reverse edges internally (so there's no need to swap the
537  /// From and To pointers when constructing DominatorTree::UpdateType).
538  /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
539  /// with the same template parameter T.
540  ///
541  /// \param Updates An unordered sequence of updates to perform. The current
542  /// CFG and the reverse of these updates provides the pre-view of the CFG.
543  ///
546  Updates, /*ReverseApplyUpdates=*/true);
547  DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, nullptr);
548  }
549 
550  /// \param Updates An unordered sequence of updates to perform. The current
551  /// CFG and the reverse of these updates provides the pre-view of the CFG.
552  /// \param PostViewUpdates An unordered sequence of update to perform in order
553  /// to obtain a post-view of the CFG. The DT will be updated assuming the
554  /// obtained PostViewCFG is the desired end state.
556  ArrayRef<UpdateType> PostViewUpdates) {
557  if (Updates.empty()) {
558  GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
559  DomTreeBuilder::ApplyUpdates(*this, PostViewCFG, &PostViewCFG);
560  } else {
561  // PreViewCFG needs to merge Updates and PostViewCFG. The updates in
562  // Updates need to be reversed, and match the direction in PostViewCFG.
563  // The PostViewCFG is created with updates reversed (equivalent to changes
564  // made to the CFG), so the PreViewCFG needs all the updates reverse
565  // applied.
566  SmallVector<UpdateType> AllUpdates(Updates.begin(), Updates.end());
567  append_range(AllUpdates, PostViewUpdates);
568  GraphDiff<NodePtr, IsPostDom> PreViewCFG(AllUpdates,
569  /*ReverseApplyUpdates=*/true);
570  GraphDiff<NodePtr, IsPostDom> PostViewCFG(PostViewUpdates);
571  DomTreeBuilder::ApplyUpdates(*this, PreViewCFG, &PostViewCFG);
572  }
573  }
574 
575  /// Inform the dominator tree about a CFG edge insertion and update the tree.
576  ///
577  /// This function has to be called just before or just after making the update
578  /// on the actual CFG. There cannot be any other updates that the dominator
579  /// tree doesn't know about.
580  ///
581  /// Note that for postdominators it automatically takes care of inserting
582  /// a reverse edge internally (so there's no need to swap the parameters).
583  ///
584  void insertEdge(NodeT *From, NodeT *To) {
585  assert(From);
586  assert(To);
587  assert(From->getParent() == Parent);
588  assert(To->getParent() == Parent);
589  DomTreeBuilder::InsertEdge(*this, From, To);
590  }
591 
592  /// Inform the dominator tree about a CFG edge deletion and update the tree.
593  ///
594  /// This function has to be called just after making the update on the actual
595  /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
596  /// DEBUG mode. There cannot be any other updates that the
597  /// dominator tree doesn't know about.
598  ///
599  /// Note that for postdominators it automatically takes care of deleting
600  /// a reverse edge internally (so there's no need to swap the parameters).
601  ///
602  void deleteEdge(NodeT *From, NodeT *To) {
603  assert(From);
604  assert(To);
605  assert(From->getParent() == Parent);
606  assert(To->getParent() == Parent);
607  DomTreeBuilder::DeleteEdge(*this, From, To);
608  }
609 
610  /// Add a new node to the dominator tree information.
611  ///
612  /// This creates a new node as a child of DomBB dominator node, linking it
613  /// into the children list of the immediate dominator.
614  ///
615  /// \param BB New node in CFG.
616  /// \param DomBB CFG node that is dominator for BB.
617  /// \returns New dominator tree node that represents new CFG node.
618  ///
619  DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
620  assert(getNode(BB) == nullptr && "Block already in dominator tree!");
621  DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
622  assert(IDomNode && "Not immediate dominator specified for block!");
623  DFSInfoValid = false;
624  return createChild(BB, IDomNode);
625  }
626 
627  /// Add a new node to the forward dominator tree and make it a new root.
628  ///
629  /// \param BB New node in CFG.
630  /// \returns New dominator tree node that represents new CFG node.
631  ///
633  assert(getNode(BB) == nullptr && "Block already in dominator tree!");
634  assert(!this->isPostDominator() &&
635  "Cannot change root of post-dominator tree");
636  DFSInfoValid = false;
638  if (Roots.empty()) {
639  addRoot(BB);
640  } else {
641  assert(Roots.size() == 1);
642  NodeT *OldRoot = Roots.front();
643  auto &OldNode = DomTreeNodes[OldRoot];
644  OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
645  OldNode->IDom = NewNode;
646  OldNode->UpdateLevel();
647  Roots[0] = BB;
648  }
649  return RootNode = NewNode;
650  }
651 
652  /// changeImmediateDominator - This method is used to update the dominator
653  /// tree information when a node's immediate dominator changes.
654  ///
656  DomTreeNodeBase<NodeT> *NewIDom) {
657  assert(N && NewIDom && "Cannot change null node pointers!");
658  DFSInfoValid = false;
659  N->setIDom(NewIDom);
660  }
661 
662  void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
664  }
665 
666  /// eraseNode - Removes a node from the dominator tree. Block must not
667  /// dominate any other blocks. Removes node from its immediate dominator's
668  /// children list. Deletes dominator node associated with basic block BB.
669  void eraseNode(NodeT *BB) {
671  assert(Node && "Removing node that isn't in dominator tree.");
672  assert(Node->isLeaf() && "Node is not a leaf node.");
673 
674  DFSInfoValid = false;
675 
676  // Remove node from immediate dominator's children list.
677  DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
678  if (IDom) {
679  const auto I = find(IDom->Children, Node);
680  assert(I != IDom->Children.end() &&
681  "Not in immediate dominator children set!");
682  // I am no longer your child...
683  IDom->Children.erase(I);
684  }
685 
686  DomTreeNodes.erase(BB);
687 
688  if (!IsPostDom) return;
689 
690  // Remember to update PostDominatorTree roots.
691  auto RIt = llvm::find(Roots, BB);
692  if (RIt != Roots.end()) {
693  std::swap(*RIt, Roots.back());
694  Roots.pop_back();
695  }
696  }
697 
698  /// splitBlock - BB is split and now it has one successor. Update dominator
699  /// tree to reflect this change.
700  void splitBlock(NodeT *NewBB) {
701  if (IsPostDominator)
702  Split<Inverse<NodeT *>>(NewBB);
703  else
704  Split<NodeT *>(NewBB);
705  }
706 
707  /// print - Convert to human readable form
708  ///
709  void print(raw_ostream &O) const {
710  O << "=============================--------------------------------\n";
711  if (IsPostDominator)
712  O << "Inorder PostDominator Tree: ";
713  else
714  O << "Inorder Dominator Tree: ";
715  if (!DFSInfoValid)
716  O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
717  O << "\n";
718 
719  // The postdom tree can have a null root if there are no returns.
720  if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
721  O << "Roots: ";
722  for (const NodePtr Block : Roots) {
723  Block->printAsOperand(O, false);
724  O << " ";
725  }
726  O << "\n";
727  }
728 
729 public:
730  /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
731  /// dominator tree in dfs order.
732  void updateDFSNumbers() const {
733  if (DFSInfoValid) {
734  SlowQueries = 0;
735  return;
736  }
737 
740  32> WorkStack;
741 
742  const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
743  assert((!Parent || ThisRoot) && "Empty constructed DomTree");
744  if (!ThisRoot)
745  return;
746 
747  // Both dominators and postdominators have a single root node. In the case
748  // case of PostDominatorTree, this node is a virtual root.
749  WorkStack.push_back({ThisRoot, ThisRoot->begin()});
750 
751  unsigned DFSNum = 0;
752  ThisRoot->DFSNumIn = DFSNum++;
753 
754  while (!WorkStack.empty()) {
755  const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
756  const auto ChildIt = WorkStack.back().second;
757 
758  // If we visited all of the children of this node, "recurse" back up the
759  // stack setting the DFOutNum.
760  if (ChildIt == Node->end()) {
761  Node->DFSNumOut = DFSNum++;
762  WorkStack.pop_back();
763  } else {
764  // Otherwise, recursively visit this child.
765  const DomTreeNodeBase<NodeT> *Child = *ChildIt;
766  ++WorkStack.back().second;
767 
768  WorkStack.push_back({Child, Child->begin()});
769  Child->DFSNumIn = DFSNum++;
770  }
771  }
772 
773  SlowQueries = 0;
774  DFSInfoValid = true;
775  }
776 
777  /// recalculate - compute a dominator tree for the given function
778  void recalculate(ParentType &Func) {
779  Parent = &Func;
781  }
782 
784  Parent = &Func;
785  DomTreeBuilder::CalculateWithUpdates(*this, Updates);
786  }
787 
788  /// verify - checks if the tree is correct. There are 3 level of verification:
789  /// - Full -- verifies if the tree is correct by making sure all the
790  /// properties (including the parent and the sibling property)
791  /// hold.
792  /// Takes O(N^3) time.
793  ///
794  /// - Basic -- checks if the tree is correct, but compares it to a freshly
795  /// constructed tree instead of checking the sibling property.
796  /// Takes O(N^2) time.
797  ///
798  /// - Fast -- checks basic tree structure and compares it with a freshly
799  /// constructed tree.
800  /// Takes O(N^2) time worst case, but is faster in practise (same
801  /// as tree construction).
803  return DomTreeBuilder::Verify(*this, VL);
804  }
805 
806  void reset() {
807  DomTreeNodes.clear();
808  Roots.clear();
809  RootNode = nullptr;
810  Parent = nullptr;
811  DFSInfoValid = false;
812  SlowQueries = 0;
813  }
814 
815 protected:
816  void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
817 
819  return (DomTreeNodes[BB] = IDom->addChild(
820  std::make_unique<DomTreeNodeBase<NodeT>>(BB, IDom)))
821  .get();
822  }
823 
825  return (DomTreeNodes[BB] =
826  std::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr))
827  .get();
828  }
829 
830  // NewBB is split and now it has one successor. Update dominator tree to
831  // reflect this change.
832  template <class N>
833  void Split(typename GraphTraits<N>::NodeRef NewBB) {
834  using GraphT = GraphTraits<N>;
835  using NodeRef = typename GraphT::NodeRef;
836  assert(std::distance(GraphT::child_begin(NewBB),
837  GraphT::child_end(NewBB)) == 1 &&
838  "NewBB should have a single successor!");
839  NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
840 
841  SmallVector<NodeRef, 4> PredBlocks(children<Inverse<N>>(NewBB));
842 
843  assert(!PredBlocks.empty() && "No predblocks?");
844 
845  bool NewBBDominatesNewBBSucc = true;
846  for (auto Pred : children<Inverse<N>>(NewBBSucc)) {
847  if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
848  isReachableFromEntry(Pred)) {
849  NewBBDominatesNewBBSucc = false;
850  break;
851  }
852  }
853 
854  // Find NewBB's immediate dominator and create new dominator tree node for
855  // NewBB.
856  NodeT *NewBBIDom = nullptr;
857  unsigned i = 0;
858  for (i = 0; i < PredBlocks.size(); ++i)
859  if (isReachableFromEntry(PredBlocks[i])) {
860  NewBBIDom = PredBlocks[i];
861  break;
862  }
863 
864  // It's possible that none of the predecessors of NewBB are reachable;
865  // in that case, NewBB itself is unreachable, so nothing needs to be
866  // changed.
867  if (!NewBBIDom) return;
868 
869  for (i = i + 1; i < PredBlocks.size(); ++i) {
870  if (isReachableFromEntry(PredBlocks[i]))
871  NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
872  }
873 
874  // Create the new dominator tree node... and set the idom of NewBB.
875  DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
876 
877  // If NewBB strictly dominates other blocks, then it is now the immediate
878  // dominator of NewBBSucc. Update the dominator tree as appropriate.
879  if (NewBBDominatesNewBBSucc) {
880  DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
881  changeImmediateDominator(NewBBSuccNode, NewBBNode);
882  }
883  }
884 
885  private:
886  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
887  const DomTreeNodeBase<NodeT> *B) const {
888  assert(A != B);
891 
892  const unsigned ALevel = A->getLevel();
893  const DomTreeNodeBase<NodeT> *IDom;
894 
895  // Don't walk nodes above A's subtree. When we reach A's level, we must
896  // either find A or be in some other subtree not dominated by A.
897  while ((IDom = B->getIDom()) != nullptr && IDom->getLevel() >= ALevel)
898  B = IDom; // Walk up the tree
899 
900  return B == A;
901  }
902 
903  /// Wipe this tree's state without releasing any resources.
904  ///
905  /// This is essentially a post-move helper only. It leaves the object in an
906  /// assignable and destroyable state, but otherwise invalid.
907  void wipe() {
908  DomTreeNodes.clear();
909  RootNode = nullptr;
910  Parent = nullptr;
911  }
912 };
913 
914 template <typename T>
916 
917 template <typename T>
919 
920 // These two functions are declared out of line as a workaround for building
921 // with old (< r147295) versions of clang because of pr11642.
922 template <typename NodeT, bool IsPostDom>
924  const NodeT *B) const {
925  if (A == B)
926  return true;
927 
928  // Cast away the const qualifiers here. This is ok since
929  // this function doesn't actually return the values returned
930  // from getNode.
931  return dominates(getNode(const_cast<NodeT *>(A)),
932  getNode(const_cast<NodeT *>(B)));
933 }
934 template <typename NodeT, bool IsPostDom>
936  const NodeT *A, const NodeT *B) const {
937  if (A == B)
938  return false;
939 
940  // Cast away the const qualifiers here. This is ok since
941  // this function doesn't actually return the values returned
942  // from getNode.
943  return dominates(getNode(const_cast<NodeT *>(A)),
944  getNode(const_cast<NodeT *>(B)));
945 }
946 
947 } // end namespace llvm
948 
949 #endif // LLVM_SUPPORT_GENERICDOMTREE_H
i
i
Definition: README.txt:29
llvm::DominatorTreeBase::createChild
DomTreeNodeBase< NodeT > * createChild(NodeT *BB, DomTreeNodeBase< NodeT > *IDom)
Definition: GenericDomTree.h:818
llvm::DominatorTreeBase::root_begin
root_iterator root_begin()
Definition: GenericDomTree.h:297
llvm::DomTreeBuilder::Verify
bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL)
Definition: GenericDomTreeConstruction.h:1601
CFGUpdate.h
llvm
Definition: AllocatorList.h:23
llvm::DominatorTreeBase::findNearestCommonDominator
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
Definition: GenericDomTree.h:468
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DominatorTreeBase::isReachableFromEntry
bool isReachableFromEntry(const NodeT *A) const
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
Definition: GenericDomTree.h:405
llvm::DominatorTreeBase::RootNode
DomTreeNodeBase< NodeT > * RootNode
Definition: GenericDomTree.h:254
llvm::DominatorTreeBase::print
void print(raw_ostream &O) const
print - Convert to human readable form
Definition: GenericDomTree.h:709
llvm::DominatorTreeBase::eraseNode
void eraseNode(NodeT *BB)
eraseNode - Removes a node from the dominator tree.
Definition: GenericDomTree.h:669
llvm::cfg::UpdateKind::Insert
@ Insert
unique_ptr< DomTreeNodeBase< BasicBlock > >>
llvm::DominatorTreeBase::applyUpdates
void applyUpdates(ArrayRef< UpdateType > Updates, ArrayRef< UpdateType > PostViewUpdates)
Definition: GenericDomTree.h:555
llvm::DominatorTreeBase::isPostDominator
bool isPostDominator() const
isPostDominator - Returns true if analysis based of postdoms
Definition: GenericDomTree.h:313
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::DominatorTreeBase::root_begin
const_root_iterator root_begin() const
Definition: GenericDomTree.h:298
llvm::DominatorTreeBase::setNewRoot
DomTreeNodeBase< NodeT > * setNewRoot(NodeT *BB)
Add a new node to the forward dominator tree and make it a new root.
Definition: GenericDomTree.h:632
llvm::DominatorTreeBase::root_size
size_t root_size() const
Definition: GenericDomTree.h:302
llvm::DominatorTreeBase::VerificationLevel::Fast
@ Fast
DenseMap.h
llvm::DominatorTreeBase::addRoot
void addRoot(NodeT *BB)
Definition: GenericDomTree.h:816
llvm::DominatorTreeBase::Insert
static constexpr UpdateKind Insert
Definition: GenericDomTree.h:242
llvm::DomTreeNodeBase::addChild
std::unique_ptr< DomTreeNodeBase > addChild(std::unique_ptr< DomTreeNodeBase > C)
Definition: GenericDomTree.h:92
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::cfg::UpdateKind::Delete
@ Delete
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::DomTreeNodeBase::getIDom
DomTreeNodeBase * getIDom() const
Definition: GenericDomTree.h:89
llvm::DominatorTreeBase::getDescendants
void getDescendants(NodeT *R, SmallVectorImpl< NodeT * > &Result) const
Get all nodes dominated by R, including R itself.
Definition: GenericDomTree.h:374
llvm::DominatorTreeBase::applyUpdates
void applyUpdates(ArrayRef< UpdateType > Updates)
Inform the dominator tree about a sequence of CFG edge insertions and deletions and perform a batch u...
Definition: GenericDomTree.h:544
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:133
llvm::GraphDiff
Definition: CFGDiff.h:57
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
GraphTraits.h
llvm::DomTreeNodeBase::getDFSNumIn
unsigned getDFSNumIn() const
getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes in the dominator tree.
Definition: GenericDomTree.h:143
llvm::DomTreeBuilder::DeleteEdge
void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
Definition: GenericDomTreeConstruction.h:1585
llvm::DomTreeNodeBase::getDFSNumOut
unsigned getDFSNumOut() const
Definition: GenericDomTree.h:144
CFGDiff.h
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
llvm::DominatorTreeBase::getRootNode
DomTreeNodeBase< NodeT > * getRootNode()
getRootNode - This returns the entry node for the CFG of the function.
Definition: GenericDomTree.h:370
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::DominatorTreeBase::insertEdge
void insertEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge insertion and update the tree.
Definition: GenericDomTree.h:584
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::DomTreeNodeBase::children
iterator_range< iterator > children()
Definition: GenericDomTree.h:83
llvm::DomTreeBuilder::CalculateWithUpdates
void CalculateWithUpdates(DomTreeT &DT, ArrayRef< typename DomTreeT::UpdateType > Updates)
Definition: GenericDomTreeConstruction.h:1567
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
dominates
static bool dominates(MachineBasicBlock &MBB, MachineBasicBlock::const_iterator A, MachineBasicBlock::const_iterator B)
Definition: RegAllocFast.cpp:315
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::DominatorTreeBase::DominatorTreeBase
DominatorTreeBase()
Definition: GenericDomTree.h:263
llvm::DominatorTreeBase::root_end
root_iterator root_end()
Definition: GenericDomTree.h:299
SmallPtrSet.h
llvm::DominatorTreeBase< BasicBlock, IsPostDom >::ParentType
std::remove_pointer_t< ParentPtr > ParentType
Definition: GenericDomTree.h:237
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(NodeT *BB, NodeT *NewBB)
Definition: GenericDomTree.h:662
llvm::DominatorTreeBase::changeImmediateDominator
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: GenericDomTree.h:655
llvm::DominatorTreeBase::updateDFSNumbers
void updateDFSNumbers() const
updateDFSNumbers - Assign In and Out numbers to the nodes while walking dominator tree in dfs order.
Definition: GenericDomTree.h:732
llvm::DominatorTreeBase::roots
iterator_range< root_iterator > roots()
Definition: GenericDomTree.h:304
llvm::DominatorTreeBase::operator=
DominatorTreeBase & operator=(DominatorTreeBase &&RHS)
Definition: GenericDomTree.h:275
llvm::DominatorTreeBase::getRoot
NodeT * getRoot() const
Definition: GenericDomTree.h:461
llvm::DominatorTreeBase::isVirtualRoot
bool isVirtualRoot(const DomTreeNodeBase< NodeT > *A) const
Definition: GenericDomTree.h:505
llvm::cfg::UpdateKind
UpdateKind
Definition: CFGUpdate.h:25
llvm::DominatorTreeBase::DomTreeNodes
DomTreeNodeMapType DomTreeNodes
Definition: GenericDomTree.h:253
llvm::DomTreeNodeBase::back
DomTreeNodeBase *& back()
Definition: GenericDomTree.h:81
llvm::RISCVFenceField::O
@ O
Definition: RISCVBaseInfo.h:132
llvm::DomTreeBuilder::ApplyUpdates
void ApplyUpdates(DomTreeT &DT, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > &PreViewCFG, GraphDiff< typename DomTreeT::NodePtr, DomTreeT::IsPostDominator > *PostViewCFG)
Definition: GenericDomTreeConstruction.h:1592
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::DominatorTreeBase< BasicBlock, IsPostDom >::root_iterator
typename SmallVectorImpl< BasicBlock * >::iterator root_iterator
Iteration over roots.
Definition: GenericDomTree.h:294
llvm::DominatorTreeBase::DFSInfoValid
bool DFSInfoValid
Definition: GenericDomTree.h:257
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1502
llvm::DominatorTreeBase::operator[]
DomTreeNodeBase< NodeT > * operator[](const NodeT *BB) const
See getNode.
Definition: GenericDomTree.h:359
llvm::DominatorTreeBase< BasicBlock, IsPostDom >::const_root_iterator
typename SmallVectorImpl< BasicBlock * >::const_iterator const_root_iterator
Definition: GenericDomTree.h:295
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DomTreeNodeBase::children
iterator_range< const_iterator > children() const
Definition: GenericDomTree.h:84
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::DominatorTreeBase::DominatorTreeBase
DominatorTreeBase(DominatorTreeBase &&Arg)
Definition: GenericDomTree.h:265
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DominatorTreeBase::Roots
SmallVector< NodeT *, IsPostDom ? 4 :1 > Roots
Definition: GenericDomTree.h:249
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1540
llvm::DomTreeNodeBase::clearAllChildren
void clearAllChildren()
Definition: GenericDomTree.h:101
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:121
llvm::DominatorTreeBase::findNearestCommonDominator
const NodeT * findNearestCommonDominator(const NodeT *A, const NodeT *B) const
Definition: GenericDomTree.h:497
llvm::DomTreeNodeBase::DomTreeNodeBase
DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
Definition: GenericDomTree.h:68
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::DominatorTreeBase::Split
void Split(typename GraphTraits< N >::NodeRef NewBB)
Definition: GenericDomTree.h:833
llvm::DomTreeNodeBase::begin
const_iterator begin() const
Definition: GenericDomTree.h:77
llvm::DominatorTreeBase::reset
void reset()
Definition: GenericDomTree.h:806
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
Definition: GenericDomTree.h:778
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::DominatorTreeBase::createNode
DomTreeNodeBase< NodeT > * createNode(NodeT *BB)
Definition: GenericDomTree.h:824
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
A
* A
Definition: README_ALTIVEC.txt:89
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:767
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1667
llvm::DomTreeNodeBase::begin
iterator begin()
Definition: GenericDomTree.h:75
llvm::DominatorTreeBase::Parent
ParentPtr Parent
Definition: GenericDomTree.h:255
llvm::DominatorTreeBase::SlowQueries
unsigned int SlowQueries
Definition: GenericDomTree.h:258
llvm::PICLevel::Level
Level
Definition: CodeGen.h:33
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::DominatorTreeBase::properlyDominates
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Definition: GenericDomTree.h:392
Node
Definition: ItaniumDemangle.h:114
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::DominatorTreeBase::dominates
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
Definition: GenericDomTree.h:416
llvm::DominatorTreeBase::addNewBlock
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
Definition: GenericDomTree.h:619
llvm::DomTreeNodeBase< VPBlockBase >::iterator
typename SmallVector< DomTreeNodeBase *, 4 >::iterator iterator
Definition: GenericDomTree.h:71
llvm::DomTreeBuilder::Calculate
void Calculate(DomTreeT &DT)
Definition: GenericDomTreeConstruction.h:1562
llvm::DominatorTreeBase::root_end
const_root_iterator root_end() const
Definition: GenericDomTree.h:300
llvm::DomTreeNodeBase::getNumChildren
size_t getNumChildren() const
Definition: GenericDomTree.h:99
llvm::DomTreeNodeBase::setIDom
void setIDom(DomTreeNodeBase *NewIDom)
Definition: GenericDomTree.h:123
std
Definition: BitVector.h:838
llvm::DominatorTreeBase::isReachableFromEntry
bool isReachableFromEntry(const DomTreeNodeBase< NodeT > *A) const
Definition: GenericDomTree.h:411
llvm::DomTreeNodeBase::getLevel
unsigned getLevel() const
Definition: GenericDomTree.h:90
llvm::DominatorTreeBase::VerificationLevel::Basic
@ Basic
llvm::ArrayRef::begin
iterator begin() const
Definition: ArrayRef.h:151
llvm::DomTreeNodeBase::end
iterator end()
Definition: GenericDomTree.h:76
llvm::DominatorTreeBase::splitBlock
void splitBlock(NodeT *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: GenericDomTree.h:700
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DomTreeNodeBase::isLeaf
bool isLeaf() const
Definition: GenericDomTree.h:98
llvm::Inverse
Definition: GraphTraits.h:95
llvm::DominatorTreeBase< BasicBlock, IsPostDom >::VerificationLevel
VerificationLevel
Definition: GenericDomTree.h:245
llvm::DomTreeBuilder::InsertEdge
void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From, typename DomTreeT::NodePtr To)
Definition: GenericDomTreeConstruction.h:1578
llvm::DomTreeNodeBase::back
DomTreeNodeBase *const & back() const
Definition: GenericDomTree.h:80
llvm::DomTreeNodeBase< VPBlockBase >::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
llvm::DominatorTreeBase< BasicBlock, IsPostDom >::ParentPtr
decltype(std::declval< BasicBlock * >() ->getParent()) ParentPtr
Definition: GenericDomTree.h:234
SmallVector.h
llvm::DominatorTreeBase::getRootNode
const DomTreeNodeBase< NodeT > * getRootNode() const
Definition: GenericDomTree.h:371
llvm::DomTreeNodeBase::compare
bool compare(const DomTreeNodeBase *Other) const
Definition: GenericDomTree.h:103
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:562
N
#define N
llvm::DominatorTreeBase::VerificationLevel::Full
@ Full
llvm::DominatorTreeBase::verify
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
Definition: GenericDomTree.h:802
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::DominatorTreeBase::IsPostDominator
static constexpr bool IsPostDominator
Definition: GenericDomTree.h:238
llvm::DomTreeNodeBase::end
const_iterator end() const
Definition: GenericDomTree.h:78
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::cfg::Update
Definition: CFGUpdate.h:27
llvm::PrintDomTree
void PrintDomTree(const DomTreeNodeBase< NodeT > *N, raw_ostream &O, unsigned Lev)
Definition: GenericDomTree.h:186
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DominatorTreeBase::recalculate
void recalculate(ParentType &Func, ArrayRef< UpdateType > Updates)
Definition: GenericDomTree.h:783
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::GraphTraits::NodeRef
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
llvm::GraphTraits
Definition: GraphTraits.h:35
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
raw_ostream.h
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1797
llvm::DominatorTreeBase::deleteEdge
void deleteEdge(NodeT *From, NodeT *To)
Inform the dominator tree about a CFG edge deletion and update the tree.
Definition: GenericDomTree.h:602
llvm::ArrayRef::end
iterator end() const
Definition: ArrayRef.h:152
llvm::DomTreeBuilder::SemiNCAInfo
Definition: GenericDomTree.h:49
llvm::DominatorTreeBase::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1167
llvm::DominatorTreeBase::roots
iterator_range< const_root_iterator > roots() const
Definition: GenericDomTree.h:307
llvm::SmallPtrSetImpl::insert
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:364
llvm::DominatorTreeBase::compare
bool compare(const DominatorTreeBase &Other) const
compare - Return false if the other dominator tree base matches this dominator tree base.
Definition: GenericDomTree.h:317