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