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/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFunction.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/Support/GenericDomTree.h"
23 #include "llvm/Support/GenericDomTreeConstruction.h"
24
25 namespace llvm {
26
27 template<>
addRoot(MachineBasicBlock * MBB)28 inline void DominatorTreeBase<MachineBasicBlock>::addRoot(MachineBasicBlock* MBB) {
29 this->Roots.push_back(MBB);
30 }
31
32 EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
33 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>);
34
35 typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
36
37 //===-------------------------------------
38 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
39 /// compute a normal dominator tree.
40 ///
41 class MachineDominatorTree : public MachineFunctionPass {
42 /// \brief Helper structure used to hold all the basic blocks
43 /// involved in the split of a critical edge.
44 struct CriticalEdge {
45 MachineBasicBlock *FromBB;
46 MachineBasicBlock *ToBB;
47 MachineBasicBlock *NewBB;
48 };
49
50 /// \brief Pile up all the critical edges to be split.
51 /// The splitting of a critical edge is local and thus, it is possible
52 /// to apply several of those changes at the same time.
53 mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
54 /// \brief Remember all the basic blocks that are inserted during
55 /// edge splitting.
56 /// Invariant: NewBBs == all the basic blocks contained in the NewBB
57 /// field of all the elements of CriticalEdgesToSplit.
58 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
59 /// such as BB == elt.NewBB.
60 mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
61
62 /// \brief Apply all the recorded critical edges to the DT.
63 /// This updates the underlying DT information in a way that uses
64 /// the fast query path of DT as much as possible.
65 ///
66 /// \post CriticalEdgesToSplit.empty().
67 void applySplitCriticalEdges() const;
68
69 public:
70 static char ID; // Pass ID, replacement for typeid
71 DominatorTreeBase<MachineBasicBlock>* DT;
72
73 MachineDominatorTree();
74
75 ~MachineDominatorTree() override;
76
getBase()77 DominatorTreeBase<MachineBasicBlock> &getBase() {
78 applySplitCriticalEdges();
79 return *DT;
80 }
81
82 void getAnalysisUsage(AnalysisUsage &AU) const override;
83
84 /// getRoots - Return the root blocks of the current CFG. This may include
85 /// multiple blocks if we are computing post dominators. For forward
86 /// dominators, this will always be a single block (the entry node).
87 ///
getRoots()88 inline const std::vector<MachineBasicBlock*> &getRoots() const {
89 applySplitCriticalEdges();
90 return DT->getRoots();
91 }
92
getRoot()93 inline MachineBasicBlock *getRoot() const {
94 applySplitCriticalEdges();
95 return DT->getRoot();
96 }
97
getRootNode()98 inline MachineDomTreeNode *getRootNode() const {
99 applySplitCriticalEdges();
100 return DT->getRootNode();
101 }
102
103 bool runOnMachineFunction(MachineFunction &F) override;
104
dominates(const MachineDomTreeNode * A,const MachineDomTreeNode * B)105 inline bool dominates(const MachineDomTreeNode* A,
106 const MachineDomTreeNode* B) const {
107 applySplitCriticalEdges();
108 return DT->dominates(A, B);
109 }
110
dominates(const MachineBasicBlock * A,const MachineBasicBlock * B)111 inline bool dominates(const MachineBasicBlock* A,
112 const MachineBasicBlock* B) const {
113 applySplitCriticalEdges();
114 return DT->dominates(A, B);
115 }
116
117 // dominates - Return true if A dominates B. This performs the
118 // special checks necessary if A and B are in the same basic block.
dominates(const MachineInstr * A,const MachineInstr * B)119 bool dominates(const MachineInstr *A, const MachineInstr *B) const {
120 applySplitCriticalEdges();
121 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
122 if (BBA != BBB) return DT->dominates(BBA, BBB);
123
124 // Loop through the basic block until we find A or B.
125 MachineBasicBlock::const_iterator I = BBA->begin();
126 for (; &*I != A && &*I != B; ++I)
127 /*empty*/ ;
128
129 //if(!DT.IsPostDominators) {
130 // A dominates B if it is found first in the basic block.
131 return &*I == A;
132 //} else {
133 // // A post-dominates B if B is found first in the basic block.
134 // return &*I == B;
135 //}
136 }
137
properlyDominates(const MachineDomTreeNode * A,const MachineDomTreeNode * B)138 inline bool properlyDominates(const MachineDomTreeNode* A,
139 const MachineDomTreeNode* B) const {
140 applySplitCriticalEdges();
141 return DT->properlyDominates(A, B);
142 }
143
properlyDominates(const MachineBasicBlock * A,const MachineBasicBlock * B)144 inline bool properlyDominates(const MachineBasicBlock* A,
145 const MachineBasicBlock* B) const {
146 applySplitCriticalEdges();
147 return DT->properlyDominates(A, B);
148 }
149
150 /// findNearestCommonDominator - Find nearest common dominator basic block
151 /// for basic block A and B. If there is no such block then return NULL.
findNearestCommonDominator(MachineBasicBlock * A,MachineBasicBlock * B)152 inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
153 MachineBasicBlock *B) {
154 applySplitCriticalEdges();
155 return DT->findNearestCommonDominator(A, B);
156 }
157
158 inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
159 applySplitCriticalEdges();
160 return DT->getNode(BB);
161 }
162
163 /// getNode - return the (Post)DominatorTree node for the specified basic
164 /// block. This is the same as using operator[] on this class.
165 ///
getNode(MachineBasicBlock * BB)166 inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
167 applySplitCriticalEdges();
168 return DT->getNode(BB);
169 }
170
171 /// addNewBlock - Add a new node to the dominator tree information. This
172 /// creates a new node as a child of DomBB dominator node,linking it into
173 /// the children list of the immediate dominator.
addNewBlock(MachineBasicBlock * BB,MachineBasicBlock * DomBB)174 inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
175 MachineBasicBlock *DomBB) {
176 applySplitCriticalEdges();
177 return DT->addNewBlock(BB, DomBB);
178 }
179
180 /// changeImmediateDominator - This method is used to update the dominator
181 /// tree information when a node's immediate dominator changes.
182 ///
changeImmediateDominator(MachineBasicBlock * N,MachineBasicBlock * NewIDom)183 inline void changeImmediateDominator(MachineBasicBlock *N,
184 MachineBasicBlock* NewIDom) {
185 applySplitCriticalEdges();
186 DT->changeImmediateDominator(N, NewIDom);
187 }
188
changeImmediateDominator(MachineDomTreeNode * N,MachineDomTreeNode * NewIDom)189 inline void changeImmediateDominator(MachineDomTreeNode *N,
190 MachineDomTreeNode* NewIDom) {
191 applySplitCriticalEdges();
192 DT->changeImmediateDominator(N, NewIDom);
193 }
194
195 /// eraseNode - Removes a node from the dominator tree. Block must not
196 /// dominate any other blocks. Removes node from its immediate dominator's
197 /// children list. Deletes dominator node associated with basic block BB.
eraseNode(MachineBasicBlock * BB)198 inline void eraseNode(MachineBasicBlock *BB) {
199 applySplitCriticalEdges();
200 DT->eraseNode(BB);
201 }
202
203 /// splitBlock - BB is split and now it has one successor. Update dominator
204 /// tree to reflect this change.
splitBlock(MachineBasicBlock * NewBB)205 inline void splitBlock(MachineBasicBlock* NewBB) {
206 applySplitCriticalEdges();
207 DT->splitBlock(NewBB);
208 }
209
210 /// isReachableFromEntry - Return true if A is dominated by the entry
211 /// block of the function containing it.
isReachableFromEntry(const MachineBasicBlock * A)212 bool isReachableFromEntry(const MachineBasicBlock *A) {
213 applySplitCriticalEdges();
214 return DT->isReachableFromEntry(A);
215 }
216
217 void releaseMemory() override;
218
219 void print(raw_ostream &OS, const Module*) const override;
220
221 /// \brief Record that the critical edge (FromBB, ToBB) has been
222 /// split with NewBB.
223 /// This is best to use this method instead of directly update the
224 /// underlying information, because this helps mitigating the
225 /// number of time the DT information is invalidated.
226 ///
227 /// \note Do not use this method with regular edges.
228 ///
229 /// \note To benefit from the compile time improvement incurred by this
230 /// method, the users of this method have to limit the queries to the DT
231 /// interface between two edges splitting. In other words, they have to
232 /// pack the splitting of critical edges as much as possible.
recordSplitCriticalEdge(MachineBasicBlock * FromBB,MachineBasicBlock * ToBB,MachineBasicBlock * NewBB)233 void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
234 MachineBasicBlock *ToBB,
235 MachineBasicBlock *NewBB) {
236 bool Inserted = NewBBs.insert(NewBB).second;
237 (void)Inserted;
238 assert(Inserted &&
239 "A basic block inserted via edge splitting cannot appear twice");
240 CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
241 }
242 };
243
244 //===-------------------------------------
245 /// DominatorTree GraphTraits specialization so the DominatorTree can be
246 /// iterable by generic graph iterators.
247 ///
248
249 template<class T> struct GraphTraits;
250
251 template <> struct GraphTraits<MachineDomTreeNode *> {
252 typedef MachineDomTreeNode NodeType;
253 typedef NodeType::iterator ChildIteratorType;
254
255 static NodeType *getEntryNode(NodeType *N) {
256 return N;
257 }
258 static inline ChildIteratorType child_begin(NodeType* N) {
259 return N->begin();
260 }
261 static inline ChildIteratorType child_end(NodeType* N) {
262 return N->end();
263 }
264 };
265
266 template <> struct GraphTraits<MachineDominatorTree*>
267 : public GraphTraits<MachineDomTreeNode *> {
268 static NodeType *getEntryNode(MachineDominatorTree *DT) {
269 return DT->getRootNode();
270 }
271 };
272
273 }
274
275 #endif
276