LLVM  6.0.0svn
MachineDominators.h
Go to the documentation of this file.
1 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- 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 //
10 // This file defines classes mirroring those in llvm/Analysis/Dominators.h,
11 // but for target-specific code rather than target-independent IR.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
16 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
17 
18 #include "llvm/ADT/SmallSet.h"
19 #include "llvm/ADT/SmallVector.h"
25 #include <cassert>
26 #include <memory>
27 #include <vector>
28 
29 namespace llvm {
30 
31 template <>
33  MachineBasicBlock *MBB) {
34  this->Roots.push_back(MBB);
35 }
36 
37 extern template class DomTreeNodeBase<MachineBasicBlock>;
38 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
39 extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
40 
42 
43 //===-------------------------------------
44 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
45 /// compute a normal dominator tree.
46 ///
48  /// \brief Helper structure used to hold all the basic blocks
49  /// involved in the split of a critical edge.
50  struct CriticalEdge {
51  MachineBasicBlock *FromBB;
52  MachineBasicBlock *ToBB;
53  MachineBasicBlock *NewBB;
54  };
55 
56  /// \brief Pile up all the critical edges to be split.
57  /// The splitting of a critical edge is local and thus, it is possible
58  /// to apply several of those changes at the same time.
59  mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
60 
61  /// \brief Remember all the basic blocks that are inserted during
62  /// edge splitting.
63  /// Invariant: NewBBs == all the basic blocks contained in the NewBB
64  /// field of all the elements of CriticalEdgesToSplit.
65  /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
66  /// such as BB == elt.NewBB.
67  mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
68 
69  /// The DominatorTreeBase that is used to compute a normal dominator tree
70  std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT;
71 
72  /// \brief Apply all the recorded critical edges to the DT.
73  /// This updates the underlying DT information in a way that uses
74  /// the fast query path of DT as much as possible.
75  ///
76  /// \post CriticalEdgesToSplit.empty().
77  void applySplitCriticalEdges() const;
78 
79 public:
80  static char ID; // Pass ID, replacement for typeid
81 
83 
85  if (!DT) DT.reset(new DomTreeBase<MachineBasicBlock>());
86  applySplitCriticalEdges();
87  return *DT;
88  }
89 
90  void getAnalysisUsage(AnalysisUsage &AU) const override;
91 
92  /// getRoots - Return the root blocks of the current CFG. This may include
93  /// multiple blocks if we are computing post dominators. For forward
94  /// dominators, this will always be a single block (the entry node).
95  ///
97  applySplitCriticalEdges();
98  return DT->getRoots();
99  }
100 
101  inline MachineBasicBlock *getRoot() const {
102  applySplitCriticalEdges();
103  return DT->getRoot();
104  }
105 
106  inline MachineDomTreeNode *getRootNode() const {
107  applySplitCriticalEdges();
108  return DT->getRootNode();
109  }
110 
111  bool runOnMachineFunction(MachineFunction &F) override;
112 
113  inline bool dominates(const MachineDomTreeNode* A,
114  const MachineDomTreeNode* B) const {
115  applySplitCriticalEdges();
116  return DT->dominates(A, B);
117  }
118 
119  inline bool dominates(const MachineBasicBlock* A,
120  const MachineBasicBlock* B) const {
121  applySplitCriticalEdges();
122  return DT->dominates(A, B);
123  }
124 
125  // dominates - Return true if A dominates B. This performs the
126  // special checks necessary if A and B are in the same basic block.
127  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
128  applySplitCriticalEdges();
129  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
130  if (BBA != BBB) return DT->dominates(BBA, BBB);
131 
132  // Loop through the basic block until we find A or B.
134  for (; &*I != A && &*I != B; ++I)
135  /*empty*/ ;
136 
137  //if(!DT.IsPostDominators) {
138  // A dominates B if it is found first in the basic block.
139  return &*I == A;
140  //} else {
141  // // A post-dominates B if B is found first in the basic block.
142  // return &*I == B;
143  //}
144  }
145 
146  inline bool properlyDominates(const MachineDomTreeNode* A,
147  const MachineDomTreeNode* B) const {
148  applySplitCriticalEdges();
149  return DT->properlyDominates(A, B);
150  }
151 
152  inline bool properlyDominates(const MachineBasicBlock* A,
153  const MachineBasicBlock* B) const {
154  applySplitCriticalEdges();
155  return DT->properlyDominates(A, B);
156  }
157 
158  /// findNearestCommonDominator - Find nearest common dominator basic block
159  /// for basic block A and B. If there is no such block then return NULL.
161  MachineBasicBlock *B) {
162  applySplitCriticalEdges();
163  return DT->findNearestCommonDominator(A, B);
164  }
165 
167  applySplitCriticalEdges();
168  return DT->getNode(BB);
169  }
170 
171  /// getNode - return the (Post)DominatorTree node for the specified basic
172  /// block. This is the same as using operator[] on this class.
173  ///
175  applySplitCriticalEdges();
176  return DT->getNode(BB);
177  }
178 
179  /// addNewBlock - Add a new node to the dominator tree information. This
180  /// creates a new node as a child of DomBB dominator node,linking it into
181  /// the children list of the immediate dominator.
183  MachineBasicBlock *DomBB) {
184  applySplitCriticalEdges();
185  return DT->addNewBlock(BB, DomBB);
186  }
187 
188  /// changeImmediateDominator - This method is used to update the dominator
189  /// tree information when a node's immediate dominator changes.
190  ///
192  MachineBasicBlock* NewIDom) {
193  applySplitCriticalEdges();
194  DT->changeImmediateDominator(N, NewIDom);
195  }
196 
198  MachineDomTreeNode* NewIDom) {
199  applySplitCriticalEdges();
200  DT->changeImmediateDominator(N, NewIDom);
201  }
202 
203  /// eraseNode - Removes a node from the dominator tree. Block must not
204  /// dominate any other blocks. Removes node from its immediate dominator's
205  /// children list. Deletes dominator node associated with basic block BB.
206  inline void eraseNode(MachineBasicBlock *BB) {
207  applySplitCriticalEdges();
208  DT->eraseNode(BB);
209  }
210 
211  /// splitBlock - BB is split and now it has one successor. Update dominator
212  /// tree to reflect this change.
213  inline void splitBlock(MachineBasicBlock* NewBB) {
214  applySplitCriticalEdges();
215  DT->splitBlock(NewBB);
216  }
217 
218  /// isReachableFromEntry - Return true if A is dominated by the entry
219  /// block of the function containing it.
221  applySplitCriticalEdges();
222  return DT->isReachableFromEntry(A);
223  }
224 
225  void releaseMemory() override;
226 
227  void verifyAnalysis() const override;
228 
229  void print(raw_ostream &OS, const Module*) const override;
230 
231  /// \brief Record that the critical edge (FromBB, ToBB) has been
232  /// split with NewBB.
233  /// This is best to use this method instead of directly update the
234  /// underlying information, because this helps mitigating the
235  /// number of time the DT information is invalidated.
236  ///
237  /// \note Do not use this method with regular edges.
238  ///
239  /// \note To benefit from the compile time improvement incurred by this
240  /// method, the users of this method have to limit the queries to the DT
241  /// interface between two edges splitting. In other words, they have to
242  /// pack the splitting of critical edges as much as possible.
244  MachineBasicBlock *ToBB,
245  MachineBasicBlock *NewBB) {
246  bool Inserted = NewBBs.insert(NewBB).second;
247  (void)Inserted;
248  assert(Inserted &&
249  "A basic block inserted via edge splitting cannot appear twice");
250  CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
251  }
252 
253  /// \brief Verify the correctness of the domtree by re-computing it.
254  ///
255  /// This should only be used for debugging as it aborts the program if the
256  /// verification fails.
257  void verifyDomTree() const;
258 };
259 
260 //===-------------------------------------
261 /// DominatorTree GraphTraits specialization so the DominatorTree can be
262 /// iterable by generic graph iterators.
263 ///
264 
265 template <class Node, class ChildIterator>
267  using NodeRef = Node *;
268  using ChildIteratorType = ChildIterator;
269 
270  static NodeRef getEntryNode(NodeRef N) { return N; }
271  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
272  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
273 };
274 
275 template <class T> struct GraphTraits;
276 
277 template <>
281 
282 template <>
283 struct GraphTraits<const MachineDomTreeNode *>
286 };
287 
288 template <> struct GraphTraits<MachineDominatorTree*>
291  return DT->getRootNode();
292  }
293 };
294 
295 } // end namespace llvm
296 
297 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H
void push_back(const T &Elt)
Definition: SmallVector.h:212
MachineBasicBlock * getRoot() const
typename std::vector< DomTreeNodeBase * >::const_iterator const_iterator
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
F(f)
void eraseNode(MachineBasicBlock *BB)
eraseNode - Removes a node from the dominator tree.
void splitBlock(MachineBasicBlock *NewBB)
splitBlock - BB is split and now it has one successor.
const SmallVectorImpl< MachineBasicBlock * > & getRoots() const
getRoots - Return the root blocks of the current CFG.
bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
static NodeRef getEntryNode(NodeRef N)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
MachineDomTreeNode * operator[](MachineBasicBlock *BB) const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void addRoot(NodeT *BB)
static ChildIteratorType child_end(NodeRef N)
Base class for the actual dominator tree node.
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B...
Core dominator tree base class.
Definition: LoopInfo.h:61
void recordSplitCriticalEdge(MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, MachineBasicBlock *NewBB)
Record that the critical edge (FromBB, ToBB) has been split with NewBB.
typename MachineDomTreeNode *::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:59
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
Represent the analysis usage information of a pass.
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode *NewIDom)
bool properlyDominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
bool dominates(const MachineInstr *A, const MachineInstr *B) const
Generic dominator tree construction - This file provides routines to construct immediate dominator in...
static NodeRef getEntryNode(MachineDominatorTree *DT)
MachineDomTreeNode * getRootNode() const
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
static ChildIteratorType child_begin(NodeRef N)
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:139
Representation of each machine instruction.
Definition: MachineInstr.h:59
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
void changeImmediateDominator(MachineBasicBlock *N, MachineBasicBlock *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node&#39;s...
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
aarch64 promote const
typename std::vector< DomTreeNodeBase * >::iterator iterator
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
MachineDomTreeNode * addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB)
addNewBlock - Add a new node to the dominator tree information.
DomTreeBase< MachineBasicBlock > & getBase()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...