1 | //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- 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 | // |
9 | // This file defines classes mirroring those in llvm/Analysis/Dominators.h, |
10 | // but for target-specific code rather than target-independent IR. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H |
15 | #define LLVM_CODEGEN_MACHINEDOMINATORS_H |
16 | |
17 | #include "llvm/ADT/SmallSet.h" |
18 | #include "llvm/ADT/SmallVector.h" |
19 | #include "llvm/CodeGen/MachineBasicBlock.h" |
20 | #include "llvm/CodeGen/MachineFunctionPass.h" |
21 | #include "llvm/CodeGen/MachineInstr.h" |
22 | #include "llvm/CodeGen/MachineInstrBundleIterator.h" |
23 | #include "llvm/Support/GenericDomTree.h" |
24 | #include "llvm/Support/GenericDomTreeConstruction.h" |
25 | #include <cassert> |
26 | #include <memory> |
27 | |
28 | namespace llvm { |
29 | class AnalysisUsage; |
30 | class MachineFunction; |
31 | class Module; |
32 | class raw_ostream; |
33 | |
34 | template <> |
35 | inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot( |
36 | MachineBasicBlock *MBB) { |
37 | this->Roots.push_back(Elt: MBB); |
38 | } |
39 | |
40 | extern template class DomTreeNodeBase<MachineBasicBlock>; |
41 | extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree |
42 | extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree |
43 | |
44 | using MachineDomTree = DomTreeBase<MachineBasicBlock>; |
45 | using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; |
46 | |
47 | //===------------------------------------- |
48 | /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to |
49 | /// compute a normal dominator tree. |
50 | /// |
51 | class MachineDominatorTree : public MachineFunctionPass { |
52 | /// Helper structure used to hold all the basic blocks |
53 | /// involved in the split of a critical edge. |
54 | struct CriticalEdge { |
55 | MachineBasicBlock *FromBB; |
56 | MachineBasicBlock *ToBB; |
57 | MachineBasicBlock *NewBB; |
58 | }; |
59 | |
60 | /// Pile up all the critical edges to be split. |
61 | /// The splitting of a critical edge is local and thus, it is possible |
62 | /// to apply several of those changes at the same time. |
63 | mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit; |
64 | |
65 | /// Remember all the basic blocks that are inserted during |
66 | /// edge splitting. |
67 | /// Invariant: NewBBs == all the basic blocks contained in the NewBB |
68 | /// field of all the elements of CriticalEdgesToSplit. |
69 | /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs |
70 | /// such as BB == elt.NewBB. |
71 | mutable SmallSet<MachineBasicBlock *, 32> NewBBs; |
72 | |
73 | /// The DominatorTreeBase that is used to compute a normal dominator tree. |
74 | std::unique_ptr<MachineDomTree> DT; |
75 | |
76 | /// Apply all the recorded critical edges to the DT. |
77 | /// This updates the underlying DT information in a way that uses |
78 | /// the fast query path of DT as much as possible. |
79 | /// |
80 | /// \post CriticalEdgesToSplit.empty(). |
81 | void applySplitCriticalEdges() const; |
82 | |
83 | public: |
84 | static char ID; // Pass ID, replacement for typeid |
85 | |
86 | MachineDominatorTree(); |
87 | explicit MachineDominatorTree(MachineFunction &MF) : MachineFunctionPass(ID) { |
88 | calculate(F&: MF); |
89 | } |
90 | |
91 | MachineDomTree &getBase() { |
92 | if (!DT) |
93 | DT.reset(p: new MachineDomTree()); |
94 | applySplitCriticalEdges(); |
95 | return *DT; |
96 | } |
97 | |
98 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
99 | |
100 | MachineBasicBlock *getRoot() const { |
101 | applySplitCriticalEdges(); |
102 | return DT->getRoot(); |
103 | } |
104 | |
105 | MachineDomTreeNode *getRootNode() const { |
106 | applySplitCriticalEdges(); |
107 | return DT->getRootNode(); |
108 | } |
109 | |
110 | bool runOnMachineFunction(MachineFunction &F) override; |
111 | |
112 | void calculate(MachineFunction &F); |
113 | |
114 | bool dominates(const MachineDomTreeNode *A, |
115 | const MachineDomTreeNode *B) const { |
116 | applySplitCriticalEdges(); |
117 | return DT->dominates(A, B); |
118 | } |
119 | |
120 | void getDescendants(MachineBasicBlock *A, |
121 | SmallVectorImpl<MachineBasicBlock *> &Result) { |
122 | applySplitCriticalEdges(); |
123 | DT->getDescendants(R: A, Result); |
124 | } |
125 | |
126 | bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const { |
127 | applySplitCriticalEdges(); |
128 | return DT->dominates(A, B); |
129 | } |
130 | |
131 | // dominates - Return true if A dominates B. This performs the |
132 | // special checks necessary if A and B are in the same basic block. |
133 | bool dominates(const MachineInstr *A, const MachineInstr *B) const { |
134 | applySplitCriticalEdges(); |
135 | const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); |
136 | if (BBA != BBB) return DT->dominates(A: BBA, B: BBB); |
137 | |
138 | // Loop through the basic block until we find A or B. |
139 | MachineBasicBlock::const_iterator I = BBA->begin(); |
140 | for (; &*I != A && &*I != B; ++I) |
141 | /*empty*/ ; |
142 | |
143 | return &*I == A; |
144 | } |
145 | |
146 | bool properlyDominates(const MachineDomTreeNode *A, |
147 | const MachineDomTreeNode *B) const { |
148 | applySplitCriticalEdges(); |
149 | return DT->properlyDominates(A, B); |
150 | } |
151 | |
152 | 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. |
160 | MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A, |
161 | MachineBasicBlock *B) { |
162 | applySplitCriticalEdges(); |
163 | return DT->findNearestCommonDominator(A, B); |
164 | } |
165 | |
166 | MachineDomTreeNode *operator[](MachineBasicBlock *BB) const { |
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 | /// |
174 | MachineDomTreeNode *getNode(MachineBasicBlock *BB) const { |
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. |
182 | MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB, |
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 | /// |
191 | void changeImmediateDominator(MachineBasicBlock *N, |
192 | MachineBasicBlock *NewIDom) { |
193 | applySplitCriticalEdges(); |
194 | DT->changeImmediateDominator(BB: N, NewBB: NewIDom); |
195 | } |
196 | |
197 | void changeImmediateDominator(MachineDomTreeNode *N, |
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 | 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 | 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. |
220 | bool isReachableFromEntry(const MachineBasicBlock *A) { |
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 | /// 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. |
243 | void recordSplitCriticalEdge(MachineBasicBlock *FromBB, |
244 | MachineBasicBlock *ToBB, |
245 | MachineBasicBlock *NewBB) { |
246 | bool Inserted = NewBBs.insert(Ptr: NewBB).second; |
247 | (void)Inserted; |
248 | assert(Inserted && |
249 | "A basic block inserted via edge splitting cannot appear twice" ); |
250 | CriticalEdgesToSplit.push_back(Elt: {.FromBB: FromBB, .ToBB: ToBB, .NewBB: NewBB}); |
251 | } |
252 | }; |
253 | |
254 | //===------------------------------------- |
255 | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
256 | /// iterable by generic graph iterators. |
257 | /// |
258 | |
259 | template <class Node, class ChildIterator> |
260 | struct MachineDomTreeGraphTraitsBase { |
261 | using NodeRef = Node *; |
262 | using ChildIteratorType = ChildIterator; |
263 | |
264 | static NodeRef getEntryNode(NodeRef N) { return N; } |
265 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
266 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
267 | }; |
268 | |
269 | template <class T> struct GraphTraits; |
270 | |
271 | template <> |
272 | struct GraphTraits<MachineDomTreeNode *> |
273 | : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, |
274 | MachineDomTreeNode::const_iterator> { |
275 | }; |
276 | |
277 | template <> |
278 | struct GraphTraits<const MachineDomTreeNode *> |
279 | : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, |
280 | MachineDomTreeNode::const_iterator> { |
281 | }; |
282 | |
283 | template <> struct GraphTraits<MachineDominatorTree*> |
284 | : public GraphTraits<MachineDomTreeNode *> { |
285 | static NodeRef getEntryNode(MachineDominatorTree *DT) { |
286 | return DT->getRootNode(); |
287 | } |
288 | }; |
289 | |
290 | } // end namespace llvm |
291 | |
292 | #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H |
293 | |