]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
1a4d82fc | 18 | #include "llvm/ADT/SmallSet.h" |
223e47cc LB |
19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | #include "llvm/CodeGen/MachineFunction.h" | |
21 | #include "llvm/CodeGen/MachineFunctionPass.h" | |
1a4d82fc JJ |
22 | #include "llvm/Support/GenericDomTree.h" |
23 | #include "llvm/Support/GenericDomTreeConstruction.h" | |
223e47cc LB |
24 | |
25 | namespace llvm { | |
26 | ||
27 | template<> | |
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 { | |
1a4d82fc JJ |
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 | CriticalEdge(MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, | |
49 | MachineBasicBlock *NewBB) | |
50 | : FromBB(FromBB), ToBB(ToBB), NewBB(NewBB) {} | |
51 | }; | |
52 | ||
53 | /// \brief Pile up all the critical edges to be split. | |
54 | /// The splitting of a critical edge is local and thus, it is possible | |
55 | /// to apply several of those changes at the same time. | |
56 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; | |
57 | /// \brief Remember all the basic blocks that are inserted during | |
58 | /// edge splitting. | |
59 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB | |
60 | /// field of all the elements of CriticalEdgesToSplit. | |
61 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs | |
62 | /// such as BB == elt.NewBB. | |
63 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; | |
64 | ||
65 | /// \brief Apply all the recorded critical edges to the DT. | |
66 | /// This updates the underlying DT information in a way that uses | |
67 | /// the fast query path of DT as much as possible. | |
68 | /// | |
69 | /// \post CriticalEdgesToSplit.empty(). | |
70 | void applySplitCriticalEdges() const { | |
71 | // Bail out early if there is nothing to do. | |
72 | if (CriticalEdgesToSplit.empty()) | |
73 | return; | |
74 | ||
75 | // For each element in CriticalEdgesToSplit, remember whether or | |
76 | // not element is the new immediate domminator of its successor. | |
77 | // The mapping is done by index, i.e., the information for the ith | |
78 | // element of CriticalEdgesToSplit is the ith element of IsNewIDom. | |
79 | SmallVector<bool, 32> IsNewIDom; | |
80 | IsNewIDom.resize(CriticalEdgesToSplit.size()); | |
81 | size_t Idx = 0; | |
82 | ||
83 | // Collect all the dominance properties info, before invalidating | |
84 | // the underlying DT. | |
85 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { | |
86 | // Update dominator information. | |
87 | MachineBasicBlock *Succ = Edge.ToBB; | |
88 | MachineDomTreeNode *SucccDTNode = DT->getNode(Succ); | |
89 | ||
90 | IsNewIDom[Idx] = true; | |
91 | for (MachineBasicBlock *PredBB : Succ->predecessors()) { | |
92 | if (PredBB == Edge.NewBB) | |
93 | continue; | |
94 | // If we are in this situation: | |
95 | // FromBB1 FromBB2 | |
96 | // + + | |
97 | // + + + + | |
98 | // + + + + | |
99 | // ... Split1 Split2 ... | |
100 | // + + | |
101 | // + + | |
102 | // + | |
103 | // Succ | |
104 | // Instead of checking the domiance property with Split2, we | |
105 | // check it with FromBB2 since Split2 is still unknown of the | |
106 | // underlying DT structure. | |
107 | if (NewBBs.count(PredBB)) { | |
108 | assert(PredBB->pred_size() == 1 && "A basic block resulting from a " | |
109 | "critical edge split has more " | |
110 | "than one predecessor!"); | |
111 | PredBB = *PredBB->pred_begin(); | |
112 | } | |
113 | if (!DT->dominates(SucccDTNode, DT->getNode(PredBB))) { | |
114 | IsNewIDom[Idx] = false; | |
115 | break; | |
116 | } | |
117 | } | |
118 | ++Idx; | |
119 | } | |
120 | ||
121 | // Now, update DT with the collected dominance properties info. | |
122 | Idx = 0; | |
123 | for (CriticalEdge &Edge : CriticalEdgesToSplit) { | |
124 | // We know FromBB dominates NewBB. | |
125 | MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB); | |
126 | MachineDomTreeNode *SucccDTNode = DT->getNode(Edge.ToBB); | |
127 | ||
128 | // If all the other predecessors of "Succ" are dominated by "Succ" itself | |
129 | // then the new block is the new immediate dominator of "Succ". Otherwise, | |
130 | // the new block doesn't dominate anything. | |
131 | if (IsNewIDom[Idx]) | |
132 | DT->changeImmediateDominator(SucccDTNode, NewDTNode); | |
133 | ++Idx; | |
134 | } | |
135 | NewBBs.clear(); | |
136 | CriticalEdgesToSplit.clear(); | |
137 | } | |
138 | ||
223e47cc LB |
139 | public: |
140 | static char ID; // Pass ID, replacement for typeid | |
141 | DominatorTreeBase<MachineBasicBlock>* DT; | |
970d7e83 | 142 | |
223e47cc | 143 | MachineDominatorTree(); |
970d7e83 | 144 | |
223e47cc | 145 | ~MachineDominatorTree(); |
970d7e83 | 146 | |
1a4d82fc JJ |
147 | DominatorTreeBase<MachineBasicBlock> &getBase() { |
148 | applySplitCriticalEdges(); | |
149 | return *DT; | |
150 | } | |
970d7e83 | 151 | |
1a4d82fc | 152 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
970d7e83 | 153 | |
223e47cc LB |
154 | /// getRoots - Return the root blocks of the current CFG. This may include |
155 | /// multiple blocks if we are computing post dominators. For forward | |
156 | /// dominators, this will always be a single block (the entry node). | |
157 | /// | |
158 | inline const std::vector<MachineBasicBlock*> &getRoots() const { | |
1a4d82fc | 159 | applySplitCriticalEdges(); |
223e47cc LB |
160 | return DT->getRoots(); |
161 | } | |
970d7e83 | 162 | |
223e47cc | 163 | inline MachineBasicBlock *getRoot() const { |
1a4d82fc | 164 | applySplitCriticalEdges(); |
223e47cc LB |
165 | return DT->getRoot(); |
166 | } | |
970d7e83 | 167 | |
223e47cc | 168 | inline MachineDomTreeNode *getRootNode() const { |
1a4d82fc | 169 | applySplitCriticalEdges(); |
223e47cc LB |
170 | return DT->getRootNode(); |
171 | } | |
970d7e83 | 172 | |
1a4d82fc | 173 | bool runOnMachineFunction(MachineFunction &F) override; |
970d7e83 LB |
174 | |
175 | inline bool dominates(const MachineDomTreeNode* A, | |
176 | const MachineDomTreeNode* B) const { | |
1a4d82fc | 177 | applySplitCriticalEdges(); |
223e47cc LB |
178 | return DT->dominates(A, B); |
179 | } | |
970d7e83 LB |
180 | |
181 | inline bool dominates(const MachineBasicBlock* A, | |
182 | const MachineBasicBlock* B) const { | |
1a4d82fc | 183 | applySplitCriticalEdges(); |
223e47cc LB |
184 | return DT->dominates(A, B); |
185 | } | |
970d7e83 | 186 | |
223e47cc LB |
187 | // dominates - Return true if A dominates B. This performs the |
188 | // special checks necessary if A and B are in the same basic block. | |
970d7e83 | 189 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
1a4d82fc | 190 | applySplitCriticalEdges(); |
970d7e83 | 191 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
223e47cc LB |
192 | if (BBA != BBB) return DT->dominates(BBA, BBB); |
193 | ||
194 | // Loop through the basic block until we find A or B. | |
970d7e83 | 195 | MachineBasicBlock::const_iterator I = BBA->begin(); |
223e47cc LB |
196 | for (; &*I != A && &*I != B; ++I) |
197 | /*empty*/ ; | |
198 | ||
199 | //if(!DT.IsPostDominators) { | |
200 | // A dominates B if it is found first in the basic block. | |
201 | return &*I == A; | |
202 | //} else { | |
203 | // // A post-dominates B if B is found first in the basic block. | |
204 | // return &*I == B; | |
205 | //} | |
206 | } | |
970d7e83 | 207 | |
223e47cc | 208 | inline bool properlyDominates(const MachineDomTreeNode* A, |
970d7e83 | 209 | const MachineDomTreeNode* B) const { |
1a4d82fc | 210 | applySplitCriticalEdges(); |
223e47cc LB |
211 | return DT->properlyDominates(A, B); |
212 | } | |
970d7e83 LB |
213 | |
214 | inline bool properlyDominates(const MachineBasicBlock* A, | |
215 | const MachineBasicBlock* B) const { | |
1a4d82fc | 216 | applySplitCriticalEdges(); |
223e47cc LB |
217 | return DT->properlyDominates(A, B); |
218 | } | |
970d7e83 | 219 | |
223e47cc LB |
220 | /// findNearestCommonDominator - Find nearest common dominator basic block |
221 | /// for basic block A and B. If there is no such block then return NULL. | |
222 | inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, | |
223 | MachineBasicBlock *B) { | |
1a4d82fc | 224 | applySplitCriticalEdges(); |
223e47cc LB |
225 | return DT->findNearestCommonDominator(A, B); |
226 | } | |
970d7e83 | 227 | |
223e47cc | 228 | inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
1a4d82fc | 229 | applySplitCriticalEdges(); |
223e47cc LB |
230 | return DT->getNode(BB); |
231 | } | |
970d7e83 | 232 | |
223e47cc LB |
233 | /// getNode - return the (Post)DominatorTree node for the specified basic |
234 | /// block. This is the same as using operator[] on this class. | |
235 | /// | |
236 | inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { | |
1a4d82fc | 237 | applySplitCriticalEdges(); |
223e47cc LB |
238 | return DT->getNode(BB); |
239 | } | |
970d7e83 | 240 | |
223e47cc | 241 | /// addNewBlock - Add a new node to the dominator tree information. This |
970d7e83 | 242 | /// creates a new node as a child of DomBB dominator node,linking it into |
223e47cc LB |
243 | /// the children list of the immediate dominator. |
244 | inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, | |
245 | MachineBasicBlock *DomBB) { | |
1a4d82fc | 246 | applySplitCriticalEdges(); |
223e47cc LB |
247 | return DT->addNewBlock(BB, DomBB); |
248 | } | |
970d7e83 | 249 | |
223e47cc LB |
250 | /// changeImmediateDominator - This method is used to update the dominator |
251 | /// tree information when a node's immediate dominator changes. | |
252 | /// | |
253 | inline void changeImmediateDominator(MachineBasicBlock *N, | |
254 | MachineBasicBlock* NewIDom) { | |
1a4d82fc | 255 | applySplitCriticalEdges(); |
223e47cc LB |
256 | DT->changeImmediateDominator(N, NewIDom); |
257 | } | |
970d7e83 | 258 | |
223e47cc LB |
259 | inline void changeImmediateDominator(MachineDomTreeNode *N, |
260 | MachineDomTreeNode* NewIDom) { | |
1a4d82fc | 261 | applySplitCriticalEdges(); |
223e47cc LB |
262 | DT->changeImmediateDominator(N, NewIDom); |
263 | } | |
970d7e83 | 264 | |
223e47cc LB |
265 | /// eraseNode - Removes a node from the dominator tree. Block must not |
266 | /// dominate any other blocks. Removes node from its immediate dominator's | |
267 | /// children list. Deletes dominator node associated with basic block BB. | |
268 | inline void eraseNode(MachineBasicBlock *BB) { | |
1a4d82fc | 269 | applySplitCriticalEdges(); |
223e47cc LB |
270 | DT->eraseNode(BB); |
271 | } | |
970d7e83 | 272 | |
223e47cc LB |
273 | /// splitBlock - BB is split and now it has one successor. Update dominator |
274 | /// tree to reflect this change. | |
275 | inline void splitBlock(MachineBasicBlock* NewBB) { | |
1a4d82fc | 276 | applySplitCriticalEdges(); |
223e47cc LB |
277 | DT->splitBlock(NewBB); |
278 | } | |
279 | ||
280 | /// isReachableFromEntry - Return true if A is dominated by the entry | |
281 | /// block of the function containing it. | |
970d7e83 | 282 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
1a4d82fc | 283 | applySplitCriticalEdges(); |
223e47cc LB |
284 | return DT->isReachableFromEntry(A); |
285 | } | |
286 | ||
1a4d82fc | 287 | void releaseMemory() override; |
970d7e83 | 288 | |
1a4d82fc JJ |
289 | void print(raw_ostream &OS, const Module*) const override; |
290 | ||
291 | /// \brief Record that the critical edge (FromBB, ToBB) has been | |
292 | /// split with NewBB. | |
293 | /// This is best to use this method instead of directly update the | |
294 | /// underlying information, because this helps mitigating the | |
295 | /// number of time the DT information is invalidated. | |
296 | /// | |
297 | /// \note Do not use this method with regular edges. | |
298 | /// | |
299 | /// \note To benefit from the compile time improvement incurred by this | |
300 | /// method, the users of this method have to limit the queries to the DT | |
301 | /// interface between two edges splitting. In other words, they have to | |
302 | /// pack the splitting of critical edges as much as possible. | |
303 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, | |
304 | MachineBasicBlock *ToBB, | |
305 | MachineBasicBlock *NewBB) { | |
85aaf69f | 306 | bool Inserted = NewBBs.insert(NewBB).second; |
1a4d82fc JJ |
307 | (void)Inserted; |
308 | assert(Inserted && | |
309 | "A basic block inserted via edge splitting cannot appear twice"); | |
310 | CriticalEdgesToSplit.push_back(CriticalEdge(FromBB, ToBB, NewBB)); | |
311 | } | |
223e47cc LB |
312 | }; |
313 | ||
314 | //===------------------------------------- | |
315 | /// DominatorTree GraphTraits specialization so the DominatorTree can be | |
316 | /// iterable by generic graph iterators. | |
317 | /// | |
318 | ||
319 | template<class T> struct GraphTraits; | |
320 | ||
321 | template <> struct GraphTraits<MachineDomTreeNode *> { | |
322 | typedef MachineDomTreeNode NodeType; | |
323 | typedef NodeType::iterator ChildIteratorType; | |
970d7e83 | 324 | |
223e47cc LB |
325 | static NodeType *getEntryNode(NodeType *N) { |
326 | return N; | |
327 | } | |
328 | static inline ChildIteratorType child_begin(NodeType* N) { | |
329 | return N->begin(); | |
330 | } | |
331 | static inline ChildIteratorType child_end(NodeType* N) { | |
332 | return N->end(); | |
333 | } | |
334 | }; | |
335 | ||
336 | template <> struct GraphTraits<MachineDominatorTree*> | |
337 | : public GraphTraits<MachineDomTreeNode *> { | |
338 | static NodeType *getEntryNode(MachineDominatorTree *DT) { | |
339 | return DT->getRootNode(); | |
340 | } | |
341 | }; | |
342 | ||
343 | } | |
344 | ||
345 | #endif |