/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineTraceMetrics.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- lib/CodeGen/MachineTraceMetrics.cpp --------------------------------===// |
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 | | #include "llvm/CodeGen/MachineTraceMetrics.h" |
11 | | #include "llvm/ADT/ArrayRef.h" |
12 | | #include "llvm/ADT/DenseMap.h" |
13 | | #include "llvm/ADT/Optional.h" |
14 | | #include "llvm/ADT/PostOrderIterator.h" |
15 | | #include "llvm/ADT/SmallPtrSet.h" |
16 | | #include "llvm/ADT/SmallVector.h" |
17 | | #include "llvm/ADT/SparseSet.h" |
18 | | #include "llvm/CodeGen/MachineBasicBlock.h" |
19 | | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
20 | | #include "llvm/CodeGen/MachineFunction.h" |
21 | | #include "llvm/CodeGen/MachineInstr.h" |
22 | | #include "llvm/CodeGen/MachineLoopInfo.h" |
23 | | #include "llvm/CodeGen/MachineOperand.h" |
24 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
25 | | #include "llvm/CodeGen/TargetSchedule.h" |
26 | | #include "llvm/MC/MCRegisterInfo.h" |
27 | | #include "llvm/Pass.h" |
28 | | #include "llvm/Support/Debug.h" |
29 | | #include "llvm/Support/ErrorHandling.h" |
30 | | #include "llvm/Support/Format.h" |
31 | | #include "llvm/Support/raw_ostream.h" |
32 | | #include "llvm/Target/TargetRegisterInfo.h" |
33 | | #include "llvm/Target/TargetSubtargetInfo.h" |
34 | | #include <algorithm> |
35 | | #include <cassert> |
36 | | #include <iterator> |
37 | | #include <tuple> |
38 | | #include <utility> |
39 | | |
40 | | using namespace llvm; |
41 | | |
42 | | #define DEBUG_TYPE "machine-trace-metrics" |
43 | | |
44 | | char MachineTraceMetrics::ID = 0; |
45 | | |
46 | | char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; |
47 | | |
48 | 90.2k | INITIALIZE_PASS_BEGIN90.2k (MachineTraceMetrics, DEBUG_TYPE,
|
49 | 90.2k | "Machine Trace Metrics", false, true) |
50 | 90.2k | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) |
51 | 90.2k | INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) |
52 | 90.2k | INITIALIZE_PASS_END(MachineTraceMetrics, DEBUG_TYPE, |
53 | | "Machine Trace Metrics", false, true) |
54 | | |
55 | 37.4k | MachineTraceMetrics::MachineTraceMetrics() : MachineFunctionPass(ID) { |
56 | 37.4k | std::fill(std::begin(Ensembles), std::end(Ensembles), nullptr); |
57 | 37.4k | } |
58 | | |
59 | 37.4k | void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { |
60 | 37.4k | AU.setPreservesAll(); |
61 | 37.4k | AU.addRequired<MachineBranchProbabilityInfo>(); |
62 | 37.4k | AU.addRequired<MachineLoopInfo>(); |
63 | 37.4k | MachineFunctionPass::getAnalysisUsage(AU); |
64 | 37.4k | } |
65 | | |
66 | 996k | bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { |
67 | 996k | MF = &Func; |
68 | 996k | const TargetSubtargetInfo &ST = MF->getSubtarget(); |
69 | 996k | TII = ST.getInstrInfo(); |
70 | 996k | TRI = ST.getRegisterInfo(); |
71 | 996k | MRI = &MF->getRegInfo(); |
72 | 996k | Loops = &getAnalysis<MachineLoopInfo>(); |
73 | 996k | SchedModel.init(ST.getSchedModel(), &ST, TII); |
74 | 996k | BlockInfo.resize(MF->getNumBlockIDs()); |
75 | 996k | ProcResourceCycles.resize(MF->getNumBlockIDs() * |
76 | 996k | SchedModel.getNumProcResourceKinds()); |
77 | 996k | return false; |
78 | 996k | } |
79 | | |
80 | 996k | void MachineTraceMetrics::releaseMemory() { |
81 | 996k | MF = nullptr; |
82 | 996k | BlockInfo.clear(); |
83 | 1.99M | for (unsigned i = 0; i != TS_NumStrategies1.99M ; ++i996k ) { |
84 | 996k | delete Ensembles[i]; |
85 | 996k | Ensembles[i] = nullptr; |
86 | 996k | } |
87 | 996k | } |
88 | | |
89 | | //===----------------------------------------------------------------------===// |
90 | | // Fixed block information |
91 | | //===----------------------------------------------------------------------===// |
92 | | // |
93 | | // The number of instructions in a basic block and the CPU resources used by |
94 | | // those instructions don't depend on any given trace strategy. |
95 | | |
96 | | /// Compute the resource usage in basic block MBB. |
97 | | const MachineTraceMetrics::FixedBlockInfo* |
98 | 3.73M | MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { |
99 | 3.73M | assert(MBB && "No basic block"); |
100 | 3.73M | FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; |
101 | 3.73M | if (FBI->hasResources()) |
102 | 1.82M | return FBI; |
103 | 1.90M | |
104 | 1.90M | // Compute resource usage in the block. |
105 | 1.90M | FBI->HasCalls = false; |
106 | 1.90M | unsigned InstrCount = 0; |
107 | 1.90M | |
108 | 1.90M | // Add up per-processor resource cycles as well. |
109 | 1.90M | unsigned PRKinds = SchedModel.getNumProcResourceKinds(); |
110 | 1.90M | SmallVector<unsigned, 32> PRCycles(PRKinds); |
111 | 1.90M | |
112 | 17.8M | for (const auto &MI : *MBB) { |
113 | 17.8M | if (MI.isTransient()) |
114 | 6.18M | continue; |
115 | 11.6M | ++InstrCount; |
116 | 11.6M | if (MI.isCall()) |
117 | 587k | FBI->HasCalls = true; |
118 | 11.6M | |
119 | 11.6M | // Count processor resources used. |
120 | 11.6M | if (!SchedModel.hasInstrSchedModel()) |
121 | 926 | continue; |
122 | 11.6M | const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(&MI); |
123 | 11.6M | if (!SC->isValid()) |
124 | 961k | continue; |
125 | 10.6M | |
126 | 10.6M | for (TargetSchedModel::ProcResIter |
127 | 10.6M | PI = SchedModel.getWriteProcResBegin(SC), |
128 | 26.7M | PE = SchedModel.getWriteProcResEnd(SC); PI != PE26.7M ; ++PI16.0M ) { |
129 | 16.0M | assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind"); |
130 | 16.0M | PRCycles[PI->ProcResourceIdx] += PI->Cycles; |
131 | 16.0M | } |
132 | 17.8M | } |
133 | 1.90M | FBI->InstrCount = InstrCount; |
134 | 1.90M | |
135 | 1.90M | // Scale the resource cycles so they are comparable. |
136 | 1.90M | unsigned PROffset = MBB->getNumber() * PRKinds; |
137 | 28.6M | for (unsigned K = 0; K != PRKinds28.6M ; ++K26.7M ) |
138 | 26.7M | ProcResourceCycles[PROffset + K] = |
139 | 26.7M | PRCycles[K] * SchedModel.getResourceFactor(K); |
140 | 3.73M | |
141 | 3.73M | return FBI; |
142 | 3.73M | } |
143 | | |
144 | | ArrayRef<unsigned> |
145 | 5.26M | MachineTraceMetrics::getProcResourceCycles(unsigned MBBNum) const { |
146 | 5.26M | assert(BlockInfo[MBBNum].hasResources() && |
147 | 5.26M | "getResources() must be called before getProcResourceCycles()"); |
148 | 5.26M | unsigned PRKinds = SchedModel.getNumProcResourceKinds(); |
149 | 5.26M | assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size()); |
150 | 5.26M | return makeArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, PRKinds); |
151 | 5.26M | } |
152 | | |
153 | | //===----------------------------------------------------------------------===// |
154 | | // Ensemble utility functions |
155 | | //===----------------------------------------------------------------------===// |
156 | | |
157 | | MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) |
158 | 554k | : MTM(*ct) { |
159 | 554k | BlockInfo.resize(MTM.BlockInfo.size()); |
160 | 554k | unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); |
161 | 554k | ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds); |
162 | 554k | ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds); |
163 | 554k | } |
164 | | |
165 | | // Virtual destructor serves as an anchor. |
166 | 554k | MachineTraceMetrics::Ensemble::~Ensemble() = default; |
167 | | |
168 | | const MachineLoop* |
169 | 4.47M | MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { |
170 | 4.47M | return MTM.Loops->getLoopFor(MBB); |
171 | 4.47M | } |
172 | | |
173 | | // Update resource-related information in the TraceBlockInfo for MBB. |
174 | | // Only update resources related to the trace above MBB. |
175 | | void MachineTraceMetrics::Ensemble:: |
176 | 1.28M | computeDepthResources(const MachineBasicBlock *MBB) { |
177 | 1.28M | TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; |
178 | 1.28M | unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); |
179 | 1.28M | unsigned PROffset = MBB->getNumber() * PRKinds; |
180 | 1.28M | |
181 | 1.28M | // Compute resources from trace above. The top block is simple. |
182 | 1.28M | if (!TBI->Pred1.28M ) { |
183 | 192k | TBI->InstrDepth = 0; |
184 | 192k | TBI->Head = MBB->getNumber(); |
185 | 192k | std::fill(ProcResourceDepths.begin() + PROffset, |
186 | 192k | ProcResourceDepths.begin() + PROffset + PRKinds, 0); |
187 | 192k | return; |
188 | 192k | } |
189 | 1.09M | |
190 | 1.09M | // Compute from the block above. A post-order traversal ensures the |
191 | 1.09M | // predecessor is always computed first. |
192 | 1.09M | unsigned PredNum = TBI->Pred->getNumber(); |
193 | 1.09M | TraceBlockInfo *PredTBI = &BlockInfo[PredNum]; |
194 | 1.09M | assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); |
195 | 1.09M | const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred); |
196 | 1.09M | TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; |
197 | 1.09M | TBI->Head = PredTBI->Head; |
198 | 1.09M | |
199 | 1.09M | // Compute per-resource depths. |
200 | 1.09M | ArrayRef<unsigned> PredPRDepths = getProcResourceDepths(PredNum); |
201 | 1.09M | ArrayRef<unsigned> PredPRCycles = MTM.getProcResourceCycles(PredNum); |
202 | 16.3M | for (unsigned K = 0; K != PRKinds16.3M ; ++K15.2M ) |
203 | 15.2M | ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K]; |
204 | 1.28M | } |
205 | | |
206 | | // Update resource-related information in the TraceBlockInfo for MBB. |
207 | | // Only update resources related to the trace below MBB. |
208 | | void MachineTraceMetrics::Ensemble:: |
209 | 1.34M | computeHeightResources(const MachineBasicBlock *MBB) { |
210 | 1.34M | TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; |
211 | 1.34M | unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); |
212 | 1.34M | unsigned PROffset = MBB->getNumber() * PRKinds; |
213 | 1.34M | |
214 | 1.34M | // Compute resources for the current block. |
215 | 1.34M | TBI->InstrHeight = MTM.getResources(MBB)->InstrCount; |
216 | 1.34M | ArrayRef<unsigned> PRCycles = MTM.getProcResourceCycles(MBB->getNumber()); |
217 | 1.34M | |
218 | 1.34M | // The trace tail is done. |
219 | 1.34M | if (!TBI->Succ1.34M ) { |
220 | 316k | TBI->Tail = MBB->getNumber(); |
221 | 316k | std::copy(PRCycles.begin(), PRCycles.end(), |
222 | 316k | ProcResourceHeights.begin() + PROffset); |
223 | 316k | return; |
224 | 316k | } |
225 | 1.02M | |
226 | 1.02M | // Compute from the block below. A post-order traversal ensures the |
227 | 1.02M | // predecessor is always computed first. |
228 | 1.02M | unsigned SuccNum = TBI->Succ->getNumber(); |
229 | 1.02M | TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum]; |
230 | 1.02M | assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); |
231 | 1.02M | TBI->InstrHeight += SuccTBI->InstrHeight; |
232 | 1.02M | TBI->Tail = SuccTBI->Tail; |
233 | 1.02M | |
234 | 1.02M | // Compute per-resource heights. |
235 | 1.02M | ArrayRef<unsigned> SuccPRHeights = getProcResourceHeights(SuccNum); |
236 | 15.4M | for (unsigned K = 0; K != PRKinds15.4M ; ++K14.4M ) |
237 | 14.4M | ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K]; |
238 | 1.34M | } |
239 | | |
240 | | // Check if depth resources for MBB are valid and return the TBI. |
241 | | // Return NULL if the resources have been invalidated. |
242 | | const MachineTraceMetrics::TraceBlockInfo* |
243 | | MachineTraceMetrics::Ensemble:: |
244 | 1.51M | getDepthResources(const MachineBasicBlock *MBB) const { |
245 | 1.51M | const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; |
246 | 1.51M | return TBI->hasValidDepth() ? TBI1.47M : nullptr39.6k ; |
247 | 1.51M | } |
248 | | |
249 | | // Check if height resources for MBB are valid and return the TBI. |
250 | | // Return NULL if the resources have been invalidated. |
251 | | const MachineTraceMetrics::TraceBlockInfo* |
252 | | MachineTraceMetrics::Ensemble:: |
253 | 1.61M | getHeightResources(const MachineBasicBlock *MBB) const { |
254 | 1.61M | const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; |
255 | 1.61M | return TBI->hasValidHeight() ? TBI1.55M : nullptr55.7k ; |
256 | 1.61M | } |
257 | | |
258 | | /// Get an array of processor resource depths for MBB. Indexed by processor |
259 | | /// resource kind, this array contains the scaled processor resources consumed |
260 | | /// by all blocks preceding MBB in its trace. It does not include instructions |
261 | | /// in MBB. |
262 | | /// |
263 | | /// Compare TraceBlockInfo::InstrDepth. |
264 | | ArrayRef<unsigned> |
265 | | MachineTraceMetrics::Ensemble:: |
266 | 1.45M | getProcResourceDepths(unsigned MBBNum) const { |
267 | 1.45M | unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); |
268 | 1.45M | assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size()); |
269 | 1.45M | return makeArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds); |
270 | 1.45M | } |
271 | | |
272 | | /// Get an array of processor resource heights for MBB. Indexed by processor |
273 | | /// resource kind, this array contains the scaled processor resources consumed |
274 | | /// by this block and all blocks following it in its trace. |
275 | | /// |
276 | | /// Compare TraceBlockInfo::InstrHeight. |
277 | | ArrayRef<unsigned> |
278 | | MachineTraceMetrics::Ensemble:: |
279 | 1.31M | getProcResourceHeights(unsigned MBBNum) const { |
280 | 1.31M | unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); |
281 | 1.31M | assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size()); |
282 | 1.31M | return makeArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds); |
283 | 1.31M | } |
284 | | |
285 | | //===----------------------------------------------------------------------===// |
286 | | // Trace Selection Strategies |
287 | | //===----------------------------------------------------------------------===// |
288 | | // |
289 | | // A trace selection strategy is implemented as a sub-class of Ensemble. The |
290 | | // trace through a block B is computed by two DFS traversals of the CFG |
291 | | // starting from B. One upwards, and one downwards. During the upwards DFS, |
292 | | // pickTracePred() is called on the post-ordered blocks. During the downwards |
293 | | // DFS, pickTraceSucc() is called in a post-order. |
294 | | // |
295 | | |
296 | | // We never allow traces that leave loops, but we do allow traces to enter |
297 | | // nested loops. We also never allow traces to contain back-edges. |
298 | | // |
299 | | // This means that a loop header can never appear above the center block of a |
300 | | // trace, except as the trace head. Below the center block, loop exiting edges |
301 | | // are banned. |
302 | | // |
303 | | // Return true if an edge from the From loop to the To loop is leaving a loop. |
304 | | // Either of To and From can be null. |
305 | 2.51M | static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { |
306 | 1.33M | return From && !From->contains(To); |
307 | 2.51M | } |
308 | | |
309 | | // MinInstrCountEnsemble - Pick the trace that executes the least number of |
310 | | // instructions. |
311 | | namespace { |
312 | | |
313 | | class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { |
314 | 0 | const char *getName() const override { return "MinInstr"; } |
315 | | const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) override; |
316 | | const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) override; |
317 | | |
318 | | public: |
319 | | MinInstrCountEnsemble(MachineTraceMetrics *mtm) |
320 | 554k | : MachineTraceMetrics::Ensemble(mtm) {} |
321 | | }; |
322 | | |
323 | | } // end anonymous namespace |
324 | | |
325 | | // Select the preferred predecessor for MBB. |
326 | | const MachineBasicBlock* |
327 | 1.28M | MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { |
328 | 1.28M | if (MBB->pred_empty()) |
329 | 66.6k | return nullptr; |
330 | 1.21M | const MachineLoop *CurLoop = getLoopFor(MBB); |
331 | 1.21M | // Don't leave loops, and never follow back-edges. |
332 | 1.21M | if (CurLoop && 1.21M MBB == CurLoop->getHeader()394k ) |
333 | 117k | return nullptr; |
334 | 1.10M | unsigned CurCount = MTM.getResources(MBB)->InstrCount; |
335 | 1.10M | const MachineBasicBlock *Best = nullptr; |
336 | 1.10M | unsigned BestDepth = 0; |
337 | 1.51M | for (const MachineBasicBlock *Pred : MBB->predecessors()) { |
338 | 1.51M | const MachineTraceMetrics::TraceBlockInfo *PredTBI = |
339 | 1.51M | getDepthResources(Pred); |
340 | 1.51M | // Ignore cycles that aren't natural loops. |
341 | 1.51M | if (!PredTBI) |
342 | 39.6k | continue; |
343 | 1.47M | // Pick the predecessor that would give this block the smallest InstrDepth. |
344 | 1.47M | unsigned Depth = PredTBI->InstrDepth + CurCount; |
345 | 1.47M | if (!Best || 1.47M Depth < BestDepth386k ) { |
346 | 1.16M | Best = Pred; |
347 | 1.16M | BestDepth = Depth; |
348 | 1.16M | } |
349 | 1.51M | } |
350 | 1.28M | return Best; |
351 | 1.28M | } |
352 | | |
353 | | // Select the preferred successor for MBB. |
354 | | const MachineBasicBlock* |
355 | 1.34M | MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { |
356 | 1.34M | if (MBB->pred_empty()) |
357 | 18.2k | return nullptr; |
358 | 1.32M | const MachineLoop *CurLoop = getLoopFor(MBB); |
359 | 1.32M | const MachineBasicBlock *Best = nullptr; |
360 | 1.32M | unsigned BestHeight = 0; |
361 | 1.91M | for (const MachineBasicBlock *Succ : MBB->successors()) { |
362 | 1.91M | // Don't consider back-edges. |
363 | 1.91M | if (CurLoop && 1.91M Succ == CurLoop->getHeader()727k ) |
364 | 138k | continue; |
365 | 1.77M | // Don't consider successors exiting CurLoop. |
366 | 1.77M | if (1.77M isExitingLoop(CurLoop, getLoopFor(Succ))1.77M ) |
367 | 163k | continue; |
368 | 1.61M | const MachineTraceMetrics::TraceBlockInfo *SuccTBI = |
369 | 1.61M | getHeightResources(Succ); |
370 | 1.61M | // Ignore cycles that aren't natural loops. |
371 | 1.61M | if (!SuccTBI) |
372 | 55.7k | continue; |
373 | 1.55M | // Pick the successor that would give this block the smallest InstrHeight. |
374 | 1.55M | unsigned Height = SuccTBI->InstrHeight; |
375 | 1.55M | if (!Best || 1.55M Height < BestHeight527k ) { |
376 | 1.31M | Best = Succ; |
377 | 1.31M | BestHeight = Height; |
378 | 1.31M | } |
379 | 1.91M | } |
380 | 1.34M | return Best; |
381 | 1.34M | } |
382 | | |
383 | | // Get an Ensemble sub-class for the requested trace strategy. |
384 | | MachineTraceMetrics::Ensemble * |
385 | 593k | MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { |
386 | 593k | assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); |
387 | 593k | Ensemble *&E = Ensembles[strategy]; |
388 | 593k | if (E) |
389 | 38.7k | return E; |
390 | 554k | |
391 | 554k | // Allocate new Ensemble on demand. |
392 | 554k | switch (strategy) { |
393 | 554k | case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); |
394 | 0 | default: 0 llvm_unreachable0 ("Invalid trace strategy enum"); |
395 | 0 | } |
396 | 0 | } |
397 | | |
398 | 91.9k | void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { |
399 | 91.9k | DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n'); |
400 | 91.9k | BlockInfo[MBB->getNumber()].invalidate(); |
401 | 183k | for (unsigned i = 0; i != TS_NumStrategies183k ; ++i91.9k ) |
402 | 91.9k | if (91.9k Ensembles[i]91.9k ) |
403 | 91.8k | Ensembles[i]->invalidate(MBB); |
404 | 91.9k | } |
405 | | |
406 | 121k | void MachineTraceMetrics::verifyAnalysis() const { |
407 | 121k | if (!MF) |
408 | 0 | return; |
409 | | #ifndef NDEBUG |
410 | | assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); |
411 | | for (unsigned i = 0; i != TS_NumStrategies; ++i) |
412 | | if (Ensembles[i]) |
413 | | Ensembles[i]->verify(); |
414 | | #endif |
415 | | } |
416 | | |
417 | | //===----------------------------------------------------------------------===// |
418 | | // Trace building |
419 | | //===----------------------------------------------------------------------===// |
420 | | // |
421 | | // Traces are built by two CFG traversals. To avoid recomputing too much, use a |
422 | | // set abstraction that confines the search to the current loop, and doesn't |
423 | | // revisit blocks. |
424 | | |
425 | | namespace { |
426 | | |
427 | | struct LoopBounds { |
428 | | MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; |
429 | | SmallPtrSet<const MachineBasicBlock*, 8> Visited; |
430 | | const MachineLoopInfo *Loops; |
431 | | bool Downward = false; |
432 | | |
433 | | LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, |
434 | 248k | const MachineLoopInfo *loops) : Blocks(blocks), Loops(loops) {} |
435 | | }; |
436 | | |
437 | | } // end anonymous namespace |
438 | | |
439 | | // Specialize po_iterator_storage in order to prune the post-order traversal so |
440 | | // it is limited to the current loop and doesn't traverse the loop back edges. |
441 | | namespace llvm { |
442 | | |
443 | | template<> |
444 | | class po_iterator_storage<LoopBounds, true> { |
445 | | LoopBounds &LB; |
446 | | |
447 | | public: |
448 | 995k | po_iterator_storage(LoopBounds &lb) : LB(lb) {} |
449 | | |
450 | 2.63M | void finishPostorder(const MachineBasicBlock*) {} |
451 | | |
452 | | bool insertEdge(Optional<const MachineBasicBlock *> From, |
453 | 4.17M | const MachineBasicBlock *To) { |
454 | 4.17M | // Skip already visited To blocks. |
455 | 4.17M | MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; |
456 | 4.17M | if (LB.Downward ? 4.17M TBI.hasValidHeight()2.16M : TBI.hasValidDepth()2.01M ) |
457 | 927k | return false; |
458 | 3.24M | // From is null once when To is the trace center block. |
459 | 3.24M | if (3.24M From3.24M ) { |
460 | 2.86M | if (const MachineLoop *FromLoop2.86M = LB.Loops->getLoopFor(*From)) { |
461 | 1.12M | // Don't follow backedges, don't leave FromLoop when going upwards. |
462 | 1.12M | if ((LB.Downward ? 1.12M To610k : *From515k ) == FromLoop->getHeader()) |
463 | 382k | return false; |
464 | 743k | // Don't leave FromLoop. |
465 | 743k | if (743k isExitingLoop(FromLoop, LB.Loops->getLoopFor(To))743k ) |
466 | 141k | return false; |
467 | 2.72M | } |
468 | 2.86M | } |
469 | 2.72M | // To is a new block. Mark the block as visited in case the CFG has cycles |
470 | 2.72M | // that MachineLoopInfo didn't recognize as a natural loop. |
471 | 2.72M | return LB.Visited.insert(To).second; |
472 | 2.72M | } |
473 | | }; |
474 | | |
475 | | } // end namespace llvm |
476 | | |
477 | | /// Compute the trace through MBB. |
478 | 248k | void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { |
479 | 248k | DEBUG(dbgs() << "Computing " << getName() << " trace through BB#" |
480 | 248k | << MBB->getNumber() << '\n'); |
481 | 248k | // Set up loop bounds for the backwards post-order traversal. |
482 | 248k | LoopBounds Bounds(BlockInfo, MTM.Loops); |
483 | 248k | |
484 | 248k | // Run an upwards post-order search for the trace start. |
485 | 248k | Bounds.Downward = false; |
486 | 248k | Bounds.Visited.clear(); |
487 | 1.28M | for (auto I : inverse_post_order_ext(MBB, Bounds)) { |
488 | 1.28M | DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); |
489 | 1.28M | TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; |
490 | 1.28M | // All the predecessors have been visited, pick the preferred one. |
491 | 1.28M | TBI.Pred = pickTracePred(I); |
492 | 1.28M | DEBUG({ |
493 | 1.28M | if (TBI.Pred) |
494 | 1.28M | dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; |
495 | 1.28M | else |
496 | 1.28M | dbgs() << "null\n"; |
497 | 1.28M | }); |
498 | 1.28M | // The trace leading to I is now known, compute the depth resources. |
499 | 1.28M | computeDepthResources(I); |
500 | 1.28M | } |
501 | 248k | |
502 | 248k | // Run a downwards post-order search for the trace end. |
503 | 248k | Bounds.Downward = true; |
504 | 248k | Bounds.Visited.clear(); |
505 | 1.34M | for (auto I : post_order_ext(MBB, Bounds)) { |
506 | 1.34M | DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); |
507 | 1.34M | TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; |
508 | 1.34M | // All the successors have been visited, pick the preferred one. |
509 | 1.34M | TBI.Succ = pickTraceSucc(I); |
510 | 1.34M | DEBUG({ |
511 | 1.34M | if (TBI.Succ) |
512 | 1.34M | dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; |
513 | 1.34M | else |
514 | 1.34M | dbgs() << "null\n"; |
515 | 1.34M | }); |
516 | 1.34M | // The trace leaving I is now known, compute the height resources. |
517 | 1.34M | computeHeightResources(I); |
518 | 1.34M | } |
519 | 248k | } |
520 | | |
521 | | /// Invalidate traces through BadMBB. |
522 | | void |
523 | 188k | MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { |
524 | 188k | SmallVector<const MachineBasicBlock*, 16> WorkList; |
525 | 188k | TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; |
526 | 188k | |
527 | 188k | // Invalidate height resources of blocks above MBB. |
528 | 188k | if (BadTBI.hasValidHeight()188k ) { |
529 | 146k | BadTBI.invalidateHeight(); |
530 | 146k | WorkList.push_back(BadMBB); |
531 | 222k | do { |
532 | 222k | const MachineBasicBlock *MBB = WorkList.pop_back_val(); |
533 | 222k | DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() |
534 | 222k | << " height.\n"); |
535 | 222k | // Find any MBB predecessors that have MBB as their preferred successor. |
536 | 222k | // They are the only ones that need to be invalidated. |
537 | 321k | for (const MachineBasicBlock *Pred : MBB->predecessors()) { |
538 | 321k | TraceBlockInfo &TBI = BlockInfo[Pred->getNumber()]; |
539 | 321k | if (!TBI.hasValidHeight()) |
540 | 180k | continue; |
541 | 140k | if (140k TBI.Succ == MBB140k ) { |
542 | 75.8k | TBI.invalidateHeight(); |
543 | 75.8k | WorkList.push_back(Pred); |
544 | 75.8k | continue; |
545 | 75.8k | } |
546 | 64.8k | // Verify that TBI.Succ is actually a *I successor. |
547 | 140k | assert((!TBI.Succ || Pred->isSuccessor(TBI.Succ)) && "CFG changed"); |
548 | 64.8k | } |
549 | 222k | } while (!WorkList.empty()); |
550 | 146k | } |
551 | 188k | |
552 | 188k | // Invalidate depth resources of blocks below MBB. |
553 | 188k | if (BadTBI.hasValidDepth()188k ) { |
554 | 135k | BadTBI.invalidateDepth(); |
555 | 135k | WorkList.push_back(BadMBB); |
556 | 197k | do { |
557 | 197k | const MachineBasicBlock *MBB = WorkList.pop_back_val(); |
558 | 197k | DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() |
559 | 197k | << " depth.\n"); |
560 | 197k | // Find any MBB successors that have MBB as their preferred predecessor. |
561 | 197k | // They are the only ones that need to be invalidated. |
562 | 293k | for (const MachineBasicBlock *Succ : MBB->successors()) { |
563 | 293k | TraceBlockInfo &TBI = BlockInfo[Succ->getNumber()]; |
564 | 293k | if (!TBI.hasValidDepth()) |
565 | 207k | continue; |
566 | 85.5k | if (85.5k TBI.Pred == MBB85.5k ) { |
567 | 62.0k | TBI.invalidateDepth(); |
568 | 62.0k | WorkList.push_back(Succ); |
569 | 62.0k | continue; |
570 | 62.0k | } |
571 | 23.4k | // Verify that TBI.Pred is actually a *I predecessor. |
572 | 85.5k | assert((!TBI.Pred || Succ->isPredecessor(TBI.Pred)) && "CFG changed"); |
573 | 23.4k | } |
574 | 197k | } while (!WorkList.empty()); |
575 | 135k | } |
576 | 188k | |
577 | 188k | // Clear any per-instruction data. We only have to do this for BadMBB itself |
578 | 188k | // because the instructions in that block may change. Other blocks may be |
579 | 188k | // invalidated, but their instructions will stay the same, so there is no |
580 | 188k | // need to erase the Cycle entries. They will be overwritten when we |
581 | 188k | // recompute. |
582 | 188k | for (const auto &I : *BadMBB) |
583 | 3.18M | Cycles.erase(&I); |
584 | 188k | } |
585 | | |
586 | 0 | void MachineTraceMetrics::Ensemble::verify() const { |
587 | | #ifndef NDEBUG |
588 | | assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() && |
589 | | "Outdated BlockInfo size"); |
590 | | for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { |
591 | | const TraceBlockInfo &TBI = BlockInfo[Num]; |
592 | | if (TBI.hasValidDepth() && TBI.Pred) { |
593 | | const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); |
594 | | assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); |
595 | | assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && |
596 | | "Trace is broken, depth should have been invalidated."); |
597 | | const MachineLoop *Loop = getLoopFor(MBB); |
598 | | assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); |
599 | | } |
600 | | if (TBI.hasValidHeight() && TBI.Succ) { |
601 | | const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); |
602 | | assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); |
603 | | assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && |
604 | | "Trace is broken, height should have been invalidated."); |
605 | | const MachineLoop *Loop = getLoopFor(MBB); |
606 | | const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); |
607 | | assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && |
608 | | "Trace contains backedge"); |
609 | | } |
610 | | } |
611 | | #endif |
612 | | } |
613 | | |
614 | | //===----------------------------------------------------------------------===// |
615 | | // Data Dependencies |
616 | | //===----------------------------------------------------------------------===// |
617 | | // |
618 | | // Compute the depth and height of each instruction based on data dependencies |
619 | | // and instruction latencies. These cycle numbers assume that the CPU can issue |
620 | | // an infinite number of instructions per cycle as long as their dependencies |
621 | | // are ready. |
622 | | |
623 | | // A data dependency is represented as a defining MI and operand numbers on the |
624 | | // defining and using MI. |
625 | | namespace { |
626 | | |
627 | | struct DataDep { |
628 | | const MachineInstr *DefMI; |
629 | | unsigned DefOp; |
630 | | unsigned UseOp; |
631 | | |
632 | | DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp) |
633 | 1.20M | : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {} |
634 | | |
635 | | /// Create a DataDep from an SSA form virtual register. |
636 | | DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp) |
637 | 15.0M | : UseOp(UseOp) { |
638 | 15.0M | assert(TargetRegisterInfo::isVirtualRegister(VirtReg)); |
639 | 15.0M | MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg); |
640 | 15.0M | assert(!DefI.atEnd() && "Register has no defs"); |
641 | 15.0M | DefMI = DefI->getParent(); |
642 | 15.0M | DefOp = DefI.getOperandNo(); |
643 | 15.0M | assert((++DefI).atEnd() && "Register has multiple defs"); |
644 | 15.0M | } |
645 | | }; |
646 | | |
647 | | } // end anonymous namespace |
648 | | |
649 | | // Get the input data dependencies that must be ready before UseMI can issue. |
650 | | // Return true if UseMI has any physreg operands. |
651 | | static bool getDataDeps(const MachineInstr &UseMI, |
652 | | SmallVectorImpl<DataDep> &Deps, |
653 | 14.8M | const MachineRegisterInfo *MRI) { |
654 | 14.8M | // Debug values should not be included in any calculations. |
655 | 14.8M | if (UseMI.isDebugValue()) |
656 | 12 | return false; |
657 | 14.8M | |
658 | 14.8M | bool HasPhysRegs = false; |
659 | 14.8M | for (MachineInstr::const_mop_iterator I = UseMI.operands_begin(), |
660 | 58.4M | E = UseMI.operands_end(); I != E58.4M ; ++I43.5M ) { |
661 | 43.5M | const MachineOperand &MO = *I; |
662 | 43.5M | if (!MO.isReg()) |
663 | 12.2M | continue; |
664 | 31.3M | unsigned Reg = MO.getReg(); |
665 | 31.3M | if (!Reg) |
666 | 2.60k | continue; |
667 | 31.3M | if (31.3M TargetRegisterInfo::isPhysicalRegister(Reg)31.3M ) { |
668 | 6.98M | HasPhysRegs = true; |
669 | 6.98M | continue; |
670 | 6.98M | } |
671 | 24.3M | // Collect virtual register reads. |
672 | 24.3M | if (24.3M MO.readsReg()24.3M ) |
673 | 14.4M | Deps.push_back(DataDep(MRI, Reg, UseMI.getOperandNo(I))); |
674 | 43.5M | } |
675 | 14.8M | return HasPhysRegs; |
676 | 14.8M | } |
677 | | |
678 | | // Get the input data dependencies of a PHI instruction, using Pred as the |
679 | | // preferred predecessor. |
680 | | // This will add at most one dependency to Deps. |
681 | | static void getPHIDeps(const MachineInstr &UseMI, |
682 | | SmallVectorImpl<DataDep> &Deps, |
683 | | const MachineBasicBlock *Pred, |
684 | 762k | const MachineRegisterInfo *MRI) { |
685 | 762k | // No predecessor at the beginning of a trace. Ignore dependencies. |
686 | 762k | if (!Pred) |
687 | 131k | return; |
688 | 762k | assert(UseMI.isPHI() && UseMI.getNumOperands() % 2 && "Bad PHI"); |
689 | 1.68M | for (unsigned i = 1; i != UseMI.getNumOperands()1.68M ; i += 21.05M ) { |
690 | 1.68M | if (UseMI.getOperand(i + 1).getMBB() == Pred1.68M ) { |
691 | 630k | unsigned Reg = UseMI.getOperand(i).getReg(); |
692 | 630k | Deps.push_back(DataDep(MRI, Reg, i)); |
693 | 630k | return; |
694 | 630k | } |
695 | 1.68M | } |
696 | 762k | } |
697 | | |
698 | | // Identify physreg dependencies for UseMI, and update the live regunit |
699 | | // tracking set when scanning instructions downwards. |
700 | | static void updatePhysDepsDownwards(const MachineInstr *UseMI, |
701 | | SmallVectorImpl<DataDep> &Deps, |
702 | | SparseSet<LiveRegUnit> &RegUnits, |
703 | 2.55M | const TargetRegisterInfo *TRI) { |
704 | 2.55M | SmallVector<unsigned, 8> Kills; |
705 | 2.55M | SmallVector<unsigned, 8> LiveDefOps; |
706 | 2.55M | |
707 | 2.55M | for (MachineInstr::const_mop_iterator MI = UseMI->operands_begin(), |
708 | 11.7M | ME = UseMI->operands_end(); MI != ME11.7M ; ++MI9.23M ) { |
709 | 9.23M | const MachineOperand &MO = *MI; |
710 | 9.23M | if (!MO.isReg()) |
711 | 2.18M | continue; |
712 | 7.05M | unsigned Reg = MO.getReg(); |
713 | 7.05M | if (!TargetRegisterInfo::isPhysicalRegister(Reg)) |
714 | 3.19M | continue; |
715 | 3.85M | // Track live defs and kills for updating RegUnits. |
716 | 3.85M | if (3.85M MO.isDef()3.85M ) { |
717 | 1.71M | if (MO.isDead()) |
718 | 523k | Kills.push_back(Reg); |
719 | 1.71M | else |
720 | 1.19M | LiveDefOps.push_back(UseMI->getOperandNo(MI)); |
721 | 3.85M | } else if (2.14M MO.isKill()2.14M ) |
722 | 16 | Kills.push_back(Reg); |
723 | 3.85M | // Identify dependencies. |
724 | 3.85M | if (!MO.readsReg()) |
725 | 1.71M | continue; |
726 | 3.08M | for (MCRegUnitIterator Units(Reg, TRI); 2.14M Units.isValid()3.08M ; ++Units938k ) { |
727 | 2.14M | SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); |
728 | 2.14M | if (I == RegUnits.end()) |
729 | 938k | continue; |
730 | 1.20M | Deps.push_back(DataDep(I->MI, I->Op, UseMI->getOperandNo(MI))); |
731 | 1.20M | break; |
732 | 1.20M | } |
733 | 9.23M | } |
734 | 2.55M | |
735 | 2.55M | // Update RegUnits to reflect live registers after UseMI. |
736 | 2.55M | // First kills. |
737 | 2.55M | for (unsigned Kill : Kills) |
738 | 1.04M | for (MCRegUnitIterator Units(Kill, TRI); 523k Units.isValid()1.04M ; ++Units523k ) |
739 | 523k | RegUnits.erase(*Units); |
740 | 2.55M | |
741 | 2.55M | // Second, live defs. |
742 | 1.19M | for (unsigned DefOp : LiveDefOps) { |
743 | 1.19M | for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI); |
744 | 2.38M | Units.isValid()2.38M ; ++Units1.19M ) { |
745 | 1.19M | LiveRegUnit &LRU = RegUnits[*Units]; |
746 | 1.19M | LRU.MI = UseMI; |
747 | 1.19M | LRU.Op = DefOp; |
748 | 1.19M | } |
749 | 1.19M | } |
750 | 2.55M | } |
751 | | |
752 | | /// The length of the critical path through a trace is the maximum of two path |
753 | | /// lengths: |
754 | | /// |
755 | | /// 1. The maximum height+depth over all instructions in the trace center block. |
756 | | /// |
757 | | /// 2. The longest cross-block dependency chain. For small blocks, it is |
758 | | /// possible that the critical path through the trace doesn't include any |
759 | | /// instructions in the block. |
760 | | /// |
761 | | /// This function computes the second number from the live-in list of the |
762 | | /// center block. |
763 | | unsigned MachineTraceMetrics::Ensemble:: |
764 | 317k | computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { |
765 | 317k | assert(TBI.HasValidInstrDepths && "Missing depth info"); |
766 | 317k | assert(TBI.HasValidInstrHeights && "Missing height info"); |
767 | 317k | unsigned MaxLen = 0; |
768 | 1.38M | for (const LiveInReg &LIR : TBI.LiveIns) { |
769 | 1.38M | if (!TargetRegisterInfo::isVirtualRegister(LIR.Reg)) |
770 | 400k | continue; |
771 | 983k | const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); |
772 | 983k | // Ignore dependencies outside the current trace. |
773 | 983k | const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()]; |
774 | 983k | if (!DefTBI.isUsefulDominator(TBI)) |
775 | 378k | continue; |
776 | 604k | unsigned Len = LIR.Height + Cycles[DefMI].Depth; |
777 | 604k | MaxLen = std::max(MaxLen, Len); |
778 | 604k | } |
779 | 317k | return MaxLen; |
780 | 317k | } |
781 | | |
782 | | void MachineTraceMetrics::Ensemble:: |
783 | | updateDepth(MachineTraceMetrics::TraceBlockInfo &TBI, const MachineInstr &UseMI, |
784 | 8.96M | SparseSet<LiveRegUnit> &RegUnits) { |
785 | 8.96M | SmallVector<DataDep, 8> Deps; |
786 | 8.96M | // Collect all data dependencies. |
787 | 8.96M | if (UseMI.isPHI()) |
788 | 326k | getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI); |
789 | 8.63M | else if (8.63M getDataDeps(UseMI, Deps, MTM.MRI)8.63M ) |
790 | 2.55M | updatePhysDepsDownwards(&UseMI, Deps, RegUnits, MTM.TRI); |
791 | 8.96M | |
792 | 8.96M | // Filter and process dependencies, computing the earliest issue cycle. |
793 | 8.96M | unsigned Cycle = 0; |
794 | 9.49M | for (const DataDep &Dep : Deps) { |
795 | 9.49M | const TraceBlockInfo&DepTBI = |
796 | 9.49M | BlockInfo[Dep.DefMI->getParent()->getNumber()]; |
797 | 9.49M | // Ignore dependencies from outside the current trace. |
798 | 9.49M | if (!DepTBI.isUsefulDominator(TBI)) |
799 | 553k | continue; |
800 | 9.49M | assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency"); |
801 | 8.94M | unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth; |
802 | 8.94M | // Add latency if DefMI is a real instruction. Transients get latency 0. |
803 | 8.94M | if (!Dep.DefMI->isTransient()) |
804 | 5.45M | DepCycle += MTM.SchedModel |
805 | 5.45M | .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp); |
806 | 9.49M | Cycle = std::max(Cycle, DepCycle); |
807 | 9.49M | } |
808 | 8.96M | // Remember the instruction depth. |
809 | 8.96M | InstrCycles &MICycles = Cycles[&UseMI]; |
810 | 8.96M | MICycles.Depth = Cycle; |
811 | 8.96M | |
812 | 8.96M | if (TBI.HasValidInstrHeights8.96M ) { |
813 | 912k | // Update critical path length. |
814 | 912k | TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height); |
815 | 912k | DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI); |
816 | 8.96M | } else { |
817 | 8.05M | DEBUG(dbgs() << Cycle << '\t' << UseMI); |
818 | 8.05M | } |
819 | 8.96M | } |
820 | | |
821 | | void MachineTraceMetrics::Ensemble:: |
822 | | updateDepth(const MachineBasicBlock *MBB, const MachineInstr &UseMI, |
823 | 11.5k | SparseSet<LiveRegUnit> &RegUnits) { |
824 | 11.5k | updateDepth(BlockInfo[MBB->getNumber()], UseMI, RegUnits); |
825 | 11.5k | } |
826 | | |
827 | | void MachineTraceMetrics::Ensemble:: |
828 | | updateDepths(MachineBasicBlock::iterator Start, |
829 | | MachineBasicBlock::iterator End, |
830 | 1.12k | SparseSet<LiveRegUnit> &RegUnits) { |
831 | 11.3k | for (; Start != End11.3k ; Start++10.2k ) |
832 | 10.2k | updateDepth(Start->getParent(), *Start, RegUnits); |
833 | 1.12k | } |
834 | | |
835 | | /// Compute instruction depths for all instructions above or in MBB in its |
836 | | /// trace. This assumes that the trace through MBB has already been computed. |
837 | | void MachineTraceMetrics::Ensemble:: |
838 | 247k | computeInstrDepths(const MachineBasicBlock *MBB) { |
839 | 247k | // The top of the trace may already be computed, and HasValidInstrDepths |
840 | 247k | // implies Head->HasValidInstrDepths, so we only need to start from the first |
841 | 247k | // block in the trace that needs to be recomputed. |
842 | 247k | SmallVector<const MachineBasicBlock*, 8> Stack; |
843 | 838k | do { |
844 | 838k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
845 | 838k | assert(TBI.hasValidDepth() && "Incomplete trace"); |
846 | 838k | if (TBI.HasValidInstrDepths) |
847 | 93.7k | break; |
848 | 744k | Stack.push_back(MBB); |
849 | 744k | MBB = TBI.Pred; |
850 | 744k | } while (MBB); |
851 | 247k | |
852 | 247k | // FIXME: If MBB is non-null at this point, it is the last pre-computed block |
853 | 247k | // in the trace. We should track any live-out physregs that were defined in |
854 | 247k | // the trace. This is quite rare in SSA form, typically created by CSE |
855 | 247k | // hoisting a compare. |
856 | 247k | SparseSet<LiveRegUnit> RegUnits; |
857 | 247k | RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); |
858 | 247k | |
859 | 247k | // Go through trace blocks in top-down order, stopping after the center block. |
860 | 991k | while (!Stack.empty()991k ) { |
861 | 744k | MBB = Stack.pop_back_val(); |
862 | 744k | DEBUG(dbgs() << "\nDepths for BB#" << MBB->getNumber() << ":\n"); |
863 | 744k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
864 | 744k | TBI.HasValidInstrDepths = true; |
865 | 744k | TBI.CriticalPath = 0; |
866 | 744k | |
867 | 744k | // Print out resource depths here as well. |
868 | 744k | DEBUG({ |
869 | 744k | dbgs() << format("%7u Instructions\n", TBI.InstrDepth); |
870 | 744k | ArrayRef<unsigned> PRDepths = getProcResourceDepths(MBB->getNumber()); |
871 | 744k | for (unsigned K = 0; K != PRDepths.size(); ++K) |
872 | 744k | if (PRDepths[K]) { |
873 | 744k | unsigned Factor = MTM.SchedModel.getResourceFactor(K); |
874 | 744k | dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K])) |
875 | 744k | << MTM.SchedModel.getProcResource(K)->Name << " (" |
876 | 744k | << PRDepths[K]/Factor << " ops x" << Factor << ")\n"; |
877 | 744k | } |
878 | 744k | }); |
879 | 744k | |
880 | 744k | // Also compute the critical path length through MBB when possible. |
881 | 744k | if (TBI.HasValidInstrHeights) |
882 | 81.9k | TBI.CriticalPath = computeCrossBlockCriticalPath(TBI); |
883 | 744k | |
884 | 8.95M | for (const auto &UseMI : *MBB) { |
885 | 8.95M | updateDepth(TBI, UseMI, RegUnits); |
886 | 8.95M | } |
887 | 744k | } |
888 | 247k | } |
889 | | |
890 | | // Identify physreg dependencies for MI when scanning instructions upwards. |
891 | | // Return the issue height of MI after considering any live regunits. |
892 | | // Height is the issue height computed from virtual register dependencies alone. |
893 | | static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height, |
894 | | SparseSet<LiveRegUnit> &RegUnits, |
895 | | const TargetSchedModel &SchedModel, |
896 | | const TargetInstrInfo *TII, |
897 | 2.02M | const TargetRegisterInfo *TRI) { |
898 | 2.02M | SmallVector<unsigned, 8> ReadOps; |
899 | 2.02M | |
900 | 2.02M | for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), |
901 | 2.02M | MOE = MI.operands_end(); |
902 | 9.23M | MOI != MOE9.23M ; ++MOI7.20M ) { |
903 | 7.20M | const MachineOperand &MO = *MOI; |
904 | 7.20M | if (!MO.isReg()) |
905 | 1.54M | continue; |
906 | 5.66M | unsigned Reg = MO.getReg(); |
907 | 5.66M | if (!TargetRegisterInfo::isPhysicalRegister(Reg)) |
908 | 2.53M | continue; |
909 | 3.12M | if (3.12M MO.readsReg()3.12M ) |
910 | 1.67M | ReadOps.push_back(MI.getOperandNo(MOI)); |
911 | 3.12M | if (!MO.isDef()) |
912 | 1.67M | continue; |
913 | 1.45M | // This is a def of Reg. Remove corresponding entries from RegUnits, and |
914 | 1.45M | // update MI Height to consider the physreg dependencies. |
915 | 2.90M | for (MCRegUnitIterator Units(Reg, TRI); 1.45M Units.isValid()2.90M ; ++Units1.45M ) { |
916 | 1.45M | SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); |
917 | 1.45M | if (I == RegUnits.end()) |
918 | 321k | continue; |
919 | 1.13M | unsigned DepHeight = I->Cycle; |
920 | 1.13M | if (!MI.isTransient()1.13M ) { |
921 | 664k | // We may not know the UseMI of this dependency, if it came from the |
922 | 664k | // live-in list. SchedModel can handle a NULL UseMI. |
923 | 664k | DepHeight += SchedModel.computeOperandLatency(&MI, MI.getOperandNo(MOI), |
924 | 664k | I->MI, I->Op); |
925 | 664k | } |
926 | 1.45M | Height = std::max(Height, DepHeight); |
927 | 1.45M | // This regunit is dead above MI. |
928 | 1.45M | RegUnits.erase(I); |
929 | 1.45M | } |
930 | 7.20M | } |
931 | 2.02M | |
932 | 2.02M | // Now we know the height of MI. Update any regunits read. |
933 | 3.69M | for (unsigned i = 0, e = ReadOps.size(); i != e3.69M ; ++i1.67M ) { |
934 | 1.67M | unsigned Reg = MI.getOperand(ReadOps[i]).getReg(); |
935 | 3.34M | for (MCRegUnitIterator Units(Reg, TRI); Units.isValid()3.34M ; ++Units1.67M ) { |
936 | 1.67M | LiveRegUnit &LRU = RegUnits[*Units]; |
937 | 1.67M | // Set the height to the highest reader of the unit. |
938 | 1.67M | if (LRU.Cycle <= Height && 1.67M LRU.MI != &MI1.57M ) { |
939 | 1.55M | LRU.Cycle = Height; |
940 | 1.55M | LRU.MI = &MI; |
941 | 1.55M | LRU.Op = ReadOps[i]; |
942 | 1.55M | } |
943 | 1.67M | } |
944 | 1.67M | } |
945 | 2.02M | |
946 | 2.02M | return Height; |
947 | 2.02M | } |
948 | | |
949 | | using MIHeightMap = DenseMap<const MachineInstr *, unsigned>; |
950 | | |
951 | | // Push the height of DefMI upwards if required to match UseMI. |
952 | | // Return true if this is the first time DefMI was seen. |
953 | | static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI, |
954 | | unsigned UseHeight, MIHeightMap &Heights, |
955 | | const TargetSchedModel &SchedModel, |
956 | 6.71M | const TargetInstrInfo *TII) { |
957 | 6.71M | // Adjust height by Dep.DefMI latency. |
958 | 6.71M | if (!Dep.DefMI->isTransient()) |
959 | 3.76M | UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, |
960 | 3.76M | Dep.UseOp); |
961 | 6.71M | |
962 | 6.71M | // Update Heights[DefMI] to be the maximum height seen. |
963 | 6.71M | MIHeightMap::iterator I; |
964 | 6.71M | bool New; |
965 | 6.71M | std::tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight)); |
966 | 6.71M | if (New) |
967 | 4.68M | return true; |
968 | 2.02M | |
969 | 2.02M | // DefMI has been pushed before. Give it the max height. |
970 | 2.02M | if (2.02M I->second < UseHeight2.02M ) |
971 | 556k | I->second = UseHeight; |
972 | 6.71M | return false; |
973 | 6.71M | } |
974 | | |
975 | | /// Assuming that the virtual register defined by DefMI:DefOp was used by |
976 | | /// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop |
977 | | /// when reaching the block that contains DefMI. |
978 | | void MachineTraceMetrics::Ensemble:: |
979 | | addLiveIns(const MachineInstr *DefMI, unsigned DefOp, |
980 | 4.68M | ArrayRef<const MachineBasicBlock*> Trace) { |
981 | 4.68M | assert(!Trace.empty() && "Trace should contain at least one block"); |
982 | 4.68M | unsigned Reg = DefMI->getOperand(DefOp).getReg(); |
983 | 4.68M | assert(TargetRegisterInfo::isVirtualRegister(Reg)); |
984 | 4.68M | const MachineBasicBlock *DefMBB = DefMI->getParent(); |
985 | 4.68M | |
986 | 4.68M | // Reg is live-in to all blocks in Trace that follow DefMBB. |
987 | 6.05M | for (unsigned i = Trace.size(); i6.05M ; --i1.37M ) { |
988 | 5.32M | const MachineBasicBlock *MBB = Trace[i-1]; |
989 | 5.32M | if (MBB == DefMBB) |
990 | 3.95M | return; |
991 | 1.37M | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
992 | 1.37M | // Just add the register. The height will be updated later. |
993 | 1.37M | TBI.LiveIns.push_back(Reg); |
994 | 1.37M | } |
995 | 4.68M | } |
996 | | |
997 | | /// Compute instruction heights in the trace through MBB. This updates MBB and |
998 | | /// the blocks below it in the trace. It is assumed that the trace has already |
999 | | /// been computed. |
1000 | | void MachineTraceMetrics::Ensemble:: |
1001 | 223k | computeInstrHeights(const MachineBasicBlock *MBB) { |
1002 | 223k | // The bottom of the trace may already be computed. |
1003 | 223k | // Find the blocks that need updating. |
1004 | 223k | SmallVector<const MachineBasicBlock*, 8> Stack; |
1005 | 594k | do { |
1006 | 594k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
1007 | 594k | assert(TBI.hasValidHeight() && "Incomplete trace"); |
1008 | 594k | if (TBI.HasValidInstrHeights) |
1009 | 72.6k | break; |
1010 | 522k | Stack.push_back(MBB); |
1011 | 522k | TBI.LiveIns.clear(); |
1012 | 522k | MBB = TBI.Succ; |
1013 | 522k | } while (MBB); |
1014 | 223k | |
1015 | 223k | // As we move upwards in the trace, keep track of instructions that are |
1016 | 223k | // required by deeper trace instructions. Map MI -> height required so far. |
1017 | 223k | MIHeightMap Heights; |
1018 | 223k | |
1019 | 223k | // For physregs, the def isn't known when we see the use. |
1020 | 223k | // Instead, keep track of the highest use of each regunit. |
1021 | 223k | SparseSet<LiveRegUnit> RegUnits; |
1022 | 223k | RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); |
1023 | 223k | |
1024 | 223k | // If the bottom of the trace was already precomputed, initialize heights |
1025 | 223k | // from its live-in list. |
1026 | 223k | // MBB is the highest precomputed block in the trace. |
1027 | 223k | if (MBB223k ) { |
1028 | 72.6k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
1029 | 226k | for (LiveInReg &LI : TBI.LiveIns) { |
1030 | 226k | if (TargetRegisterInfo::isVirtualRegister(LI.Reg)226k ) { |
1031 | 174k | // For virtual registers, the def latency is included. |
1032 | 174k | unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; |
1033 | 174k | if (Height < LI.Height) |
1034 | 143k | Height = LI.Height; |
1035 | 226k | } else { |
1036 | 51.3k | // For register units, the def latency is not included because we don't |
1037 | 51.3k | // know the def yet. |
1038 | 51.3k | RegUnits[LI.Reg].Cycle = LI.Height; |
1039 | 51.3k | } |
1040 | 226k | } |
1041 | 72.6k | } |
1042 | 223k | |
1043 | 223k | // Go through the trace blocks in bottom-up order. |
1044 | 223k | SmallVector<DataDep, 8> Deps; |
1045 | 746k | for (;!Stack.empty()746k ; Stack.pop_back()522k ) { |
1046 | 522k | MBB = Stack.back(); |
1047 | 522k | DEBUG(dbgs() << "Heights for BB#" << MBB->getNumber() << ":\n"); |
1048 | 522k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
1049 | 522k | TBI.HasValidInstrHeights = true; |
1050 | 522k | TBI.CriticalPath = 0; |
1051 | 522k | |
1052 | 522k | DEBUG({ |
1053 | 522k | dbgs() << format("%7u Instructions\n", TBI.InstrHeight); |
1054 | 522k | ArrayRef<unsigned> PRHeights = getProcResourceHeights(MBB->getNumber()); |
1055 | 522k | for (unsigned K = 0; K != PRHeights.size(); ++K) |
1056 | 522k | if (PRHeights[K]) { |
1057 | 522k | unsigned Factor = MTM.SchedModel.getResourceFactor(K); |
1058 | 522k | dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K])) |
1059 | 522k | << MTM.SchedModel.getProcResource(K)->Name << " (" |
1060 | 522k | << PRHeights[K]/Factor << " ops x" << Factor << ")\n"; |
1061 | 522k | } |
1062 | 522k | }); |
1063 | 522k | |
1064 | 522k | // Get dependencies from PHIs in the trace successor. |
1065 | 522k | const MachineBasicBlock *Succ = TBI.Succ; |
1066 | 522k | // If MBB is the last block in the trace, and it has a back-edge to the |
1067 | 522k | // loop header, get loop-carried dependencies from PHIs in the header. For |
1068 | 522k | // that purpose, pretend that all the loop header PHIs have height 0. |
1069 | 522k | if (!Succ) |
1070 | 151k | if (const MachineLoop *151k Loop151k = getLoopFor(MBB)) |
1071 | 75.8k | if (75.8k MBB->isSuccessor(Loop->getHeader())75.8k ) |
1072 | 75.8k | Succ = Loop->getHeader(); |
1073 | 522k | |
1074 | 522k | if (Succ522k ) { |
1075 | 814k | for (const auto &PHI : *Succ) { |
1076 | 814k | if (!PHI.isPHI()) |
1077 | 427k | break; |
1078 | 387k | Deps.clear(); |
1079 | 387k | getPHIDeps(PHI, Deps, MBB, MTM.MRI); |
1080 | 387k | if (!Deps.empty()387k ) { |
1081 | 387k | // Loop header PHI heights are all 0. |
1082 | 387k | unsigned Height = TBI.Succ ? Cycles.lookup(&PHI).Height267k : 0119k ; |
1083 | 387k | DEBUG(dbgs() << "pred\t" << Height << '\t' << PHI); |
1084 | 387k | if (pushDepHeight(Deps.front(), PHI, Height, Heights, MTM.SchedModel, |
1085 | 387k | MTM.TII)) |
1086 | 383k | addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack); |
1087 | 387k | } |
1088 | 814k | } |
1089 | 446k | } |
1090 | 522k | |
1091 | 522k | // Go through the block backwards. |
1092 | 522k | for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin(); |
1093 | 7.06M | BI != BB7.06M ;) { |
1094 | 6.54M | const MachineInstr &MI = *--BI; |
1095 | 6.54M | |
1096 | 6.54M | // Find the MI height as determined by virtual register uses in the |
1097 | 6.54M | // trace below. |
1098 | 6.54M | unsigned Cycle = 0; |
1099 | 6.54M | MIHeightMap::iterator HeightI = Heights.find(&MI); |
1100 | 6.54M | if (HeightI != Heights.end()6.54M ) { |
1101 | 3.97M | Cycle = HeightI->second; |
1102 | 3.97M | // We won't be seeing any more MI uses. |
1103 | 3.97M | Heights.erase(HeightI); |
1104 | 3.97M | } |
1105 | 6.54M | |
1106 | 6.54M | // Don't process PHI deps. They depend on the specific predecessor, and |
1107 | 6.54M | // we'll get them when visiting the predecessor. |
1108 | 6.54M | Deps.clear(); |
1109 | 6.25M | bool HasPhysRegs = !MI.isPHI() && getDataDeps(MI, Deps, MTM.MRI); |
1110 | 6.54M | |
1111 | 6.54M | // There may also be regunit dependencies to include in the height. |
1112 | 6.54M | if (HasPhysRegs) |
1113 | 2.02M | Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, MTM.SchedModel, |
1114 | 2.02M | MTM.TII, MTM.TRI); |
1115 | 6.54M | |
1116 | 6.54M | // Update the required height of any virtual registers read by MI. |
1117 | 6.54M | for (const DataDep &Dep : Deps) |
1118 | 6.32M | if (6.32M pushDepHeight(Dep, MI, Cycle, Heights, MTM.SchedModel, MTM.TII)6.32M ) |
1119 | 4.30M | addLiveIns(Dep.DefMI, Dep.DefOp, Stack); |
1120 | 6.54M | |
1121 | 6.54M | InstrCycles &MICycles = Cycles[&MI]; |
1122 | 6.54M | MICycles.Height = Cycle; |
1123 | 6.54M | if (!TBI.HasValidInstrDepths6.54M ) { |
1124 | 2.37M | DEBUG(dbgs() << Cycle << '\t' << MI); |
1125 | 2.37M | continue; |
1126 | 2.37M | } |
1127 | 4.16M | // Update critical path length. |
1128 | 4.16M | TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth); |
1129 | 4.16M | DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << MI); |
1130 | 6.54M | } |
1131 | 522k | |
1132 | 522k | // Update virtual live-in heights. They were added by addLiveIns() with a 0 |
1133 | 522k | // height because the final height isn't known until now. |
1134 | 522k | DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:"); |
1135 | 1.37M | for (LiveInReg &LIR : TBI.LiveIns) { |
1136 | 1.37M | const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); |
1137 | 1.37M | LIR.Height = Heights.lookup(DefMI); |
1138 | 1.37M | DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height); |
1139 | 1.37M | } |
1140 | 522k | |
1141 | 522k | // Transfer the live regunits to the live-in list. |
1142 | 522k | for (SparseSet<LiveRegUnit>::const_iterator |
1143 | 1.05M | RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE1.05M ; ++RI529k ) { |
1144 | 529k | TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle)); |
1145 | 529k | DEBUG(dbgs() << ' ' << PrintRegUnit(RI->RegUnit, MTM.TRI) |
1146 | 529k | << '@' << RI->Cycle); |
1147 | 529k | } |
1148 | 522k | DEBUG(dbgs() << '\n'); |
1149 | 522k | |
1150 | 522k | if (!TBI.HasValidInstrDepths) |
1151 | 287k | continue; |
1152 | 235k | // Add live-ins to the critical path length. |
1153 | 235k | TBI.CriticalPath = std::max(TBI.CriticalPath, |
1154 | 235k | computeCrossBlockCriticalPath(TBI)); |
1155 | 235k | DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n'); |
1156 | 522k | } |
1157 | 223k | } |
1158 | | |
1159 | | MachineTraceMetrics::Trace |
1160 | 272k | MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { |
1161 | 272k | TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; |
1162 | 272k | |
1163 | 272k | if (!TBI.hasValidDepth() || 272k !TBI.hasValidHeight()32.1k ) |
1164 | 248k | computeTrace(MBB); |
1165 | 272k | if (!TBI.HasValidInstrDepths) |
1166 | 247k | computeInstrDepths(MBB); |
1167 | 272k | if (!TBI.HasValidInstrHeights) |
1168 | 223k | computeInstrHeights(MBB); |
1169 | 272k | |
1170 | 272k | return Trace(*this, TBI); |
1171 | 272k | } |
1172 | | |
1173 | | unsigned |
1174 | 122k | MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr &MI) const { |
1175 | 122k | assert(getBlockNum() == unsigned(MI.getParent()->getNumber()) && |
1176 | 122k | "MI must be in the trace center block"); |
1177 | 122k | InstrCycles Cyc = getInstrCycles(MI); |
1178 | 122k | return getCriticalPath() - (Cyc.Depth + Cyc.Height); |
1179 | 122k | } |
1180 | | |
1181 | | unsigned |
1182 | 49.0k | MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr &PHI) const { |
1183 | 49.0k | const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum()); |
1184 | 49.0k | SmallVector<DataDep, 1> Deps; |
1185 | 49.0k | getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI); |
1186 | 49.0k | assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor"); |
1187 | 49.0k | DataDep &Dep = Deps.front(); |
1188 | 49.0k | unsigned DepCycle = getInstrCycles(*Dep.DefMI).Depth; |
1189 | 49.0k | // Add latency if DefMI is a real instruction. Transients get latency 0. |
1190 | 49.0k | if (!Dep.DefMI->isTransient()) |
1191 | 4.77k | DepCycle += TE.MTM.SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, |
1192 | 4.77k | &PHI, Dep.UseOp); |
1193 | 49.0k | return DepCycle; |
1194 | 49.0k | } |
1195 | | |
1196 | | /// When bottom is set include instructions in current block in estimate. |
1197 | 74.2k | unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { |
1198 | 74.2k | // Find the limiting processor resource. |
1199 | 74.2k | // Numbers have been pre-scaled to be comparable. |
1200 | 74.2k | unsigned PRMax = 0; |
1201 | 74.2k | ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); |
1202 | 74.2k | if (Bottom74.2k ) { |
1203 | 74.2k | ArrayRef<unsigned> PRCycles = TE.MTM.getProcResourceCycles(getBlockNum()); |
1204 | 1.11M | for (unsigned K = 0; K != PRDepths.size()1.11M ; ++K1.03M ) |
1205 | 1.03M | PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]); |
1206 | 0 | } else { |
1207 | 0 | for (unsigned K = 0; K != PRDepths.size()0 ; ++K0 ) |
1208 | 0 | PRMax = std::max(PRMax, PRDepths[K]); |
1209 | 0 | } |
1210 | 74.2k | // Convert to cycle count. |
1211 | 74.2k | PRMax = TE.MTM.getCycles(PRMax); |
1212 | 74.2k | |
1213 | 74.2k | /// All instructions before current block |
1214 | 74.2k | unsigned Instrs = TBI.InstrDepth; |
1215 | 74.2k | // plus instructions in current block |
1216 | 74.2k | if (Bottom) |
1217 | 74.2k | Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; |
1218 | 74.2k | if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) |
1219 | 74.2k | Instrs /= IW; |
1220 | 74.2k | // Assume issue width 1 without a schedule model. |
1221 | 74.2k | return std::max(Instrs, PRMax); |
1222 | 74.2k | } |
1223 | | |
1224 | | unsigned MachineTraceMetrics::Trace::getResourceLength( |
1225 | | ArrayRef<const MachineBasicBlock *> Extrablocks, |
1226 | | ArrayRef<const MCSchedClassDesc *> ExtraInstrs, |
1227 | 285k | ArrayRef<const MCSchedClassDesc *> RemoveInstrs) const { |
1228 | 285k | // Add up resources above and below the center block. |
1229 | 285k | ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); |
1230 | 285k | ArrayRef<unsigned> PRHeights = TE.getProcResourceHeights(getBlockNum()); |
1231 | 285k | unsigned PRMax = 0; |
1232 | 285k | |
1233 | 285k | // Capture computing cycles from extra instructions |
1234 | 285k | auto extraCycles = [this](ArrayRef<const MCSchedClassDesc *> Instrs, |
1235 | 285k | unsigned ResourceIdx) |
1236 | 7.98M | ->unsigned { |
1237 | 7.98M | unsigned Cycles = 0; |
1238 | 4.63M | for (const MCSchedClassDesc *SC : Instrs) { |
1239 | 4.63M | if (!SC->isValid()) |
1240 | 320 | continue; |
1241 | 4.63M | for (TargetSchedModel::ProcResIter |
1242 | 4.63M | PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), |
1243 | 4.63M | PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); |
1244 | 16.9M | PI != PE16.9M ; ++PI12.3M ) { |
1245 | 12.3M | if (PI->ProcResourceIdx != ResourceIdx) |
1246 | 11.4M | continue; |
1247 | 880k | Cycles += |
1248 | 880k | (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(ResourceIdx)); |
1249 | 880k | } |
1250 | 4.63M | } |
1251 | 7.98M | return Cycles; |
1252 | 7.98M | }; |
1253 | 285k | |
1254 | 4.27M | for (unsigned K = 0; K != PRDepths.size()4.27M ; ++K3.99M ) { |
1255 | 3.99M | unsigned PRCycles = PRDepths[K] + PRHeights[K]; |
1256 | 3.99M | for (const MachineBasicBlock *MBB : Extrablocks) |
1257 | 2.75M | PRCycles += TE.MTM.getProcResourceCycles(MBB->getNumber())[K]; |
1258 | 3.99M | PRCycles += extraCycles(ExtraInstrs, K); |
1259 | 3.99M | PRCycles -= extraCycles(RemoveInstrs, K); |
1260 | 3.99M | PRMax = std::max(PRMax, PRCycles); |
1261 | 3.99M | } |
1262 | 285k | // Convert to cycle count. |
1263 | 285k | PRMax = TE.MTM.getCycles(PRMax); |
1264 | 285k | |
1265 | 285k | // Instrs: #instructions in current trace outside current block. |
1266 | 285k | unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; |
1267 | 285k | // Add instruction count from the extra blocks. |
1268 | 285k | for (const MachineBasicBlock *MBB : Extrablocks) |
1269 | 196k | Instrs += TE.MTM.getResources(MBB)->InstrCount; |
1270 | 285k | Instrs += ExtraInstrs.size(); |
1271 | 285k | Instrs -= RemoveInstrs.size(); |
1272 | 285k | if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) |
1273 | 285k | Instrs /= IW; |
1274 | 285k | // Assume issue width 1 without a schedule model. |
1275 | 285k | return std::max(Instrs, PRMax); |
1276 | 285k | } |
1277 | | |
1278 | | bool MachineTraceMetrics::Trace::isDepInTrace(const MachineInstr &DefMI, |
1279 | 97.5k | const MachineInstr &UseMI) const { |
1280 | 97.5k | if (DefMI.getParent() == UseMI.getParent()) |
1281 | 97.4k | return true; |
1282 | 100 | |
1283 | 100 | const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI.getParent()->getNumber()]; |
1284 | 100 | const TraceBlockInfo &TBI = TE.BlockInfo[UseMI.getParent()->getNumber()]; |
1285 | 100 | |
1286 | 100 | return DepTBI.isUsefulDominator(TBI); |
1287 | 100 | } |
1288 | | |
1289 | 0 | void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { |
1290 | 0 | OS << getName() << " ensemble:\n"; |
1291 | 0 | for (unsigned i = 0, e = BlockInfo.size(); i != e0 ; ++i0 ) { |
1292 | 0 | OS << " BB#" << i << '\t'; |
1293 | 0 | BlockInfo[i].print(OS); |
1294 | 0 | OS << '\n'; |
1295 | 0 | } |
1296 | 0 | } |
1297 | | |
1298 | 0 | void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { |
1299 | 0 | if (hasValidDepth()0 ) { |
1300 | 0 | OS << "depth=" << InstrDepth; |
1301 | 0 | if (Pred) |
1302 | 0 | OS << " pred=BB#" << Pred->getNumber(); |
1303 | 0 | else |
1304 | 0 | OS << " pred=null"; |
1305 | 0 | OS << " head=BB#" << Head; |
1306 | 0 | if (HasValidInstrDepths) |
1307 | 0 | OS << " +instrs"; |
1308 | 0 | } else |
1309 | 0 | OS << "depth invalid"; |
1310 | 0 | OS << ", "; |
1311 | 0 | if (hasValidHeight()0 ) { |
1312 | 0 | OS << "height=" << InstrHeight; |
1313 | 0 | if (Succ) |
1314 | 0 | OS << " succ=BB#" << Succ->getNumber(); |
1315 | 0 | else |
1316 | 0 | OS << " succ=null"; |
1317 | 0 | OS << " tail=BB#" << Tail; |
1318 | 0 | if (HasValidInstrHeights) |
1319 | 0 | OS << " +instrs"; |
1320 | 0 | } else |
1321 | 0 | OS << "height invalid"; |
1322 | 0 | if (HasValidInstrDepths && 0 HasValidInstrHeights0 ) |
1323 | 0 | OS << ", crit=" << CriticalPath; |
1324 | 0 | } |
1325 | | |
1326 | 0 | void MachineTraceMetrics::Trace::print(raw_ostream &OS) const { |
1327 | 0 | unsigned MBBNum = &TBI - &TE.BlockInfo[0]; |
1328 | 0 |
|
1329 | 0 | OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum |
1330 | 0 | << " --> BB#" << TBI.Tail << ':'; |
1331 | 0 | if (TBI.hasValidHeight() && 0 TBI.hasValidDepth()0 ) |
1332 | 0 | OS << ' ' << getInstrCount() << " instrs."; |
1333 | 0 | if (TBI.HasValidInstrDepths && 0 TBI.HasValidInstrHeights0 ) |
1334 | 0 | OS << ' ' << TBI.CriticalPath << " cycles."; |
1335 | 0 |
|
1336 | 0 | const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; |
1337 | 0 | OS << "\nBB#" << MBBNum; |
1338 | 0 | while (Block->hasValidDepth() && 0 Block->Pred0 ) { |
1339 | 0 | unsigned Num = Block->Pred->getNumber(); |
1340 | 0 | OS << " <- BB#" << Num; |
1341 | 0 | Block = &TE.BlockInfo[Num]; |
1342 | 0 | } |
1343 | 0 |
|
1344 | 0 | Block = &TBI; |
1345 | 0 | OS << "\n "; |
1346 | 0 | while (Block->hasValidHeight() && 0 Block->Succ0 ) { |
1347 | 0 | unsigned Num = Block->Succ->getNumber(); |
1348 | 0 | OS << " -> BB#" << Num; |
1349 | 0 | Block = &TE.BlockInfo[Num]; |
1350 | 0 | } |
1351 | 0 | OS << '\n'; |
1352 | 0 | } |