1 //===- lib/CodeGen/MachineTraceMetrics.cpp ----------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "early-ifcvt"
11 #include "MachineTraceMetrics.h"
12 #include "llvm/CodeGen/MachineBasicBlock.h"
13 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
14 #include "llvm/CodeGen/MachineLoopInfo.h"
15 #include "llvm/CodeGen/MachineRegisterInfo.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/MC/MCInstrItineraries.h"
18 #include "llvm/Target/TargetInstrInfo.h"
19 #include "llvm/Target/TargetRegisterInfo.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include "llvm/ADT/PostOrderIterator.h"
23 #include "llvm/ADT/SparseSet.h"
27 char MachineTraceMetrics::ID = 0;
28 char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID;
30 INITIALIZE_PASS_BEGIN(MachineTraceMetrics,
31 "machine-trace-metrics", "Machine Trace Metrics", false, true)
32 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
33 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
34 INITIALIZE_PASS_END(MachineTraceMetrics,
35 "machine-trace-metrics", "Machine Trace Metrics", false, true)
37 MachineTraceMetrics::MachineTraceMetrics()
38 : MachineFunctionPass(ID), MF(0), TII(0), TRI(0), MRI(0), Loops(0) {
39 std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0);
42 void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const {
44 AU.addRequired<MachineBranchProbabilityInfo>();
45 AU.addRequired<MachineLoopInfo>();
46 MachineFunctionPass::getAnalysisUsage(AU);
49 bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) {
51 TII = MF->getTarget().getInstrInfo();
52 TRI = MF->getTarget().getRegisterInfo();
53 ItinData = MF->getTarget().getInstrItineraryData();
54 MRI = &MF->getRegInfo();
55 Loops = &getAnalysis<MachineLoopInfo>();
56 BlockInfo.resize(MF->getNumBlockIDs());
60 void MachineTraceMetrics::releaseMemory() {
63 for (unsigned i = 0; i != TS_NumStrategies; ++i) {
69 //===----------------------------------------------------------------------===//
70 // Fixed block information
71 //===----------------------------------------------------------------------===//
73 // The number of instructions in a basic block and the CPU resources used by
74 // those instructions don't depend on any given trace strategy.
76 /// Compute the resource usage in basic block MBB.
77 const MachineTraceMetrics::FixedBlockInfo*
78 MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) {
79 assert(MBB && "No basic block");
80 FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()];
81 if (FBI->hasResources())
84 // Compute resource usage in the block.
85 // FIXME: Compute per-functional unit counts.
86 FBI->HasCalls = false;
87 unsigned InstrCount = 0;
88 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
90 const MachineInstr *MI = I;
91 if (MI->isTransient())
97 FBI->InstrCount = InstrCount;
101 //===----------------------------------------------------------------------===//
102 // Ensemble utility functions
103 //===----------------------------------------------------------------------===//
105 MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct)
107 BlockInfo.resize(MTM.BlockInfo.size());
110 // Virtual destructor serves as an anchor.
111 MachineTraceMetrics::Ensemble::~Ensemble() {}
114 MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const {
115 return MTM.Loops->getLoopFor(MBB);
118 // Update resource-related information in the TraceBlockInfo for MBB.
119 // Only update resources related to the trace above MBB.
120 void MachineTraceMetrics::Ensemble::
121 computeDepthResources(const MachineBasicBlock *MBB) {
122 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
124 // Compute resources from trace above. The top block is simple.
127 TBI->Head = MBB->getNumber();
131 // Compute from the block above. A post-order traversal ensures the
132 // predecessor is always computed first.
133 TraceBlockInfo *PredTBI = &BlockInfo[TBI->Pred->getNumber()];
134 assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet");
135 const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred);
136 TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount;
137 TBI->Head = PredTBI->Head;
140 // Update resource-related information in the TraceBlockInfo for MBB.
141 // Only update resources related to the trace below MBB.
142 void MachineTraceMetrics::Ensemble::
143 computeHeightResources(const MachineBasicBlock *MBB) {
144 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
146 // Compute resources for the current block.
147 TBI->InstrHeight = MTM.getResources(MBB)->InstrCount;
149 // The trace tail is done.
151 TBI->Tail = MBB->getNumber();
155 // Compute from the block below. A post-order traversal ensures the
156 // predecessor is always computed first.
157 TraceBlockInfo *SuccTBI = &BlockInfo[TBI->Succ->getNumber()];
158 assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet");
159 TBI->InstrHeight += SuccTBI->InstrHeight;
160 TBI->Tail = SuccTBI->Tail;
163 // Check if depth resources for MBB are valid and return the TBI.
164 // Return NULL if the resources have been invalidated.
165 const MachineTraceMetrics::TraceBlockInfo*
166 MachineTraceMetrics::Ensemble::
167 getDepthResources(const MachineBasicBlock *MBB) const {
168 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
169 return TBI->hasValidDepth() ? TBI : 0;
172 // Check if height resources for MBB are valid and return the TBI.
173 // Return NULL if the resources have been invalidated.
174 const MachineTraceMetrics::TraceBlockInfo*
175 MachineTraceMetrics::Ensemble::
176 getHeightResources(const MachineBasicBlock *MBB) const {
177 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
178 return TBI->hasValidHeight() ? TBI : 0;
181 //===----------------------------------------------------------------------===//
182 // Trace Selection Strategies
183 //===----------------------------------------------------------------------===//
185 // A trace selection strategy is implemented as a sub-class of Ensemble. The
186 // trace through a block B is computed by two DFS traversals of the CFG
187 // starting from B. One upwards, and one downwards. During the upwards DFS,
188 // pickTracePred() is called on the post-ordered blocks. During the downwards
189 // DFS, pickTraceSucc() is called in a post-order.
192 // We never allow traces that leave loops, but we do allow traces to enter
193 // nested loops. We also never allow traces to contain back-edges.
195 // This means that a loop header can never appear above the center block of a
196 // trace, except as the trace head. Below the center block, loop exiting edges
199 // Return true if an edge from the From loop to the To loop is leaving a loop.
200 // Either of To and From can be null.
201 static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) {
202 return From && !From->contains(To);
205 // MinInstrCountEnsemble - Pick the trace that executes the least number of
208 class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble {
209 const char *getName() const { return "MinInstr"; }
210 const MachineBasicBlock *pickTracePred(const MachineBasicBlock*);
211 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*);
214 MinInstrCountEnsemble(MachineTraceMetrics *mtm)
215 : MachineTraceMetrics::Ensemble(mtm) {}
219 // Select the preferred predecessor for MBB.
220 const MachineBasicBlock*
221 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
222 if (MBB->pred_empty())
224 const MachineLoop *CurLoop = getLoopFor(MBB);
225 // Don't leave loops, and never follow back-edges.
226 if (CurLoop && MBB == CurLoop->getHeader())
228 unsigned CurCount = MTM.getResources(MBB)->InstrCount;
229 const MachineBasicBlock *Best = 0;
230 unsigned BestDepth = 0;
231 for (MachineBasicBlock::const_pred_iterator
232 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
233 const MachineBasicBlock *Pred = *I;
234 const MachineTraceMetrics::TraceBlockInfo *PredTBI =
235 getDepthResources(Pred);
236 assert(PredTBI && "Predecessor must be visited first");
237 // Pick the predecessor that would give this block the smallest InstrDepth.
238 unsigned Depth = PredTBI->InstrDepth + CurCount;
239 if (!Best || Depth < BestDepth)
240 Best = Pred, BestDepth = Depth;
245 // Select the preferred successor for MBB.
246 const MachineBasicBlock*
247 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
248 if (MBB->pred_empty())
250 const MachineLoop *CurLoop = getLoopFor(MBB);
251 const MachineBasicBlock *Best = 0;
252 unsigned BestHeight = 0;
253 for (MachineBasicBlock::const_succ_iterator
254 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
255 const MachineBasicBlock *Succ = *I;
256 // Don't consider back-edges.
257 if (CurLoop && Succ == CurLoop->getHeader())
259 // Don't consider successors exiting CurLoop.
260 if (isExitingLoop(CurLoop, getLoopFor(Succ)))
262 const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
263 getHeightResources(Succ);
264 assert(SuccTBI && "Successor must be visited first");
265 // Pick the successor that would give this block the smallest InstrHeight.
266 unsigned Height = SuccTBI->InstrHeight;
267 if (!Best || Height < BestHeight)
268 Best = Succ, BestHeight = Height;
273 // Get an Ensemble sub-class for the requested trace strategy.
274 MachineTraceMetrics::Ensemble *
275 MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) {
276 assert(strategy < TS_NumStrategies && "Invalid trace strategy enum");
277 Ensemble *&E = Ensembles[strategy];
281 // Allocate new Ensemble on demand.
283 case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this));
284 default: llvm_unreachable("Invalid trace strategy enum");
288 void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) {
289 DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n');
290 BlockInfo[MBB->getNumber()].invalidate();
291 for (unsigned i = 0; i != TS_NumStrategies; ++i)
293 Ensembles[i]->invalidate(MBB);
296 void MachineTraceMetrics::verifyAnalysis() const {
300 assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");
301 for (unsigned i = 0; i != TS_NumStrategies; ++i)
303 Ensembles[i]->verify();
307 //===----------------------------------------------------------------------===//
309 //===----------------------------------------------------------------------===//
311 // Traces are built by two CFG traversals. To avoid recomputing too much, use a
312 // set abstraction that confines the search to the current loop, and doesn't
317 MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks;
318 const MachineLoopInfo *Loops;
320 LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks,
321 const MachineLoopInfo *loops)
322 : Blocks(blocks), Loops(loops), Downward(false) {}
326 // Specialize po_iterator_storage in order to prune the post-order traversal so
327 // it is limited to the current loop and doesn't traverse the loop back edges.
330 class po_iterator_storage<LoopBounds, true> {
333 po_iterator_storage(LoopBounds &lb) : LB(lb) {}
334 void finishPostorder(const MachineBasicBlock*) {}
336 bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) {
337 // Skip already visited To blocks.
338 MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
339 if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
341 // From is null once when To is the trace center block.
344 const MachineLoop *FromLoop = LB.Loops->getLoopFor(From);
347 // Don't follow backedges, don't leave FromLoop when going upwards.
348 if ((LB.Downward ? To : From) == FromLoop->getHeader())
350 // Don't leave FromLoop.
351 if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
353 // This is a new block. The PO traversal will compute height/depth
354 // resources, causing us to reject new edges to To. This only works because
355 // we reject back-edges, so the CFG is cycle-free.
361 /// Compute the trace through MBB.
362 void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {
363 DEBUG(dbgs() << "Computing " << getName() << " trace through BB#"
364 << MBB->getNumber() << '\n');
365 // Set up loop bounds for the backwards post-order traversal.
366 LoopBounds Bounds(BlockInfo, MTM.Loops);
368 // Run an upwards post-order search for the trace start.
369 Bounds.Downward = false;
370 typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO;
371 for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds);
373 DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": ");
374 TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
375 // All the predecessors have been visited, pick the preferred one.
376 TBI.Pred = pickTracePred(*I);
379 dbgs() << "BB#" << TBI.Pred->getNumber() << '\n';
383 // The trace leading to I is now known, compute the depth resources.
384 computeDepthResources(*I);
387 // Run a downwards post-order search for the trace end.
388 Bounds.Downward = true;
389 typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO;
390 for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds);
392 DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": ");
393 TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
394 // All the successors have been visited, pick the preferred one.
395 TBI.Succ = pickTraceSucc(*I);
398 dbgs() << "BB#" << TBI.Succ->getNumber() << '\n';
402 // The trace leaving I is now known, compute the height resources.
403 computeHeightResources(*I);
407 /// Invalidate traces through BadMBB.
409 MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) {
410 SmallVector<const MachineBasicBlock*, 16> WorkList;
411 TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()];
413 // Invalidate height resources of blocks above MBB.
414 if (BadTBI.hasValidHeight()) {
415 BadTBI.invalidateHeight();
416 WorkList.push_back(BadMBB);
418 const MachineBasicBlock *MBB = WorkList.pop_back_val();
419 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
421 // Find any MBB predecessors that have MBB as their preferred successor.
422 // They are the only ones that need to be invalidated.
423 for (MachineBasicBlock::const_pred_iterator
424 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
425 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
426 if (!TBI.hasValidHeight())
428 if (TBI.Succ == MBB) {
429 TBI.invalidateHeight();
430 WorkList.push_back(*I);
433 // Verify that TBI.Succ is actually a *I successor.
434 assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed");
436 } while (!WorkList.empty());
439 // Invalidate depth resources of blocks below MBB.
440 if (BadTBI.hasValidDepth()) {
441 BadTBI.invalidateDepth();
442 WorkList.push_back(BadMBB);
444 const MachineBasicBlock *MBB = WorkList.pop_back_val();
445 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
447 // Find any MBB successors that have MBB as their preferred predecessor.
448 // They are the only ones that need to be invalidated.
449 for (MachineBasicBlock::const_succ_iterator
450 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
451 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
452 if (!TBI.hasValidDepth())
454 if (TBI.Pred == MBB) {
455 TBI.invalidateDepth();
456 WorkList.push_back(*I);
459 // Verify that TBI.Pred is actually a *I predecessor.
460 assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed");
462 } while (!WorkList.empty());
465 // Clear any per-instruction data. We only have to do this for BadMBB itself
466 // because the instructions in that block may change. Other blocks may be
467 // invalidated, but their instructions will stay the same, so there is no
468 // need to erase the Cycle entries. They will be overwritten when we
470 for (MachineBasicBlock::const_iterator I = BadMBB->begin(), E = BadMBB->end();
475 void MachineTraceMetrics::Ensemble::verify() const {
477 assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() &&
478 "Outdated BlockInfo size");
479 for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {
480 const TraceBlockInfo &TBI = BlockInfo[Num];
481 if (TBI.hasValidDepth() && TBI.Pred) {
482 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num);
483 assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");
484 assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() &&
485 "Trace is broken, depth should have been invalidated.");
486 const MachineLoop *Loop = getLoopFor(MBB);
487 assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge");
489 if (TBI.hasValidHeight() && TBI.Succ) {
490 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num);
491 assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");
492 assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() &&
493 "Trace is broken, height should have been invalidated.");
494 const MachineLoop *Loop = getLoopFor(MBB);
495 const MachineLoop *SuccLoop = getLoopFor(TBI.Succ);
496 assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) &&
497 "Trace contains backedge");
503 //===----------------------------------------------------------------------===//
505 //===----------------------------------------------------------------------===//
507 // Compute the depth and height of each instruction based on data dependencies
508 // and instruction latencies. These cycle numbers assume that the CPU can issue
509 // an infinite number of instructions per cycle as long as their dependencies
512 // A data dependency is represented as a defining MI and operand numbers on the
513 // defining and using MI.
516 const MachineInstr *DefMI;
520 DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp)
521 : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {}
523 /// Create a DataDep from an SSA form virtual register.
524 DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp)
526 assert(TargetRegisterInfo::isVirtualRegister(VirtReg));
527 MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg);
528 assert(!DefI.atEnd() && "Register has no defs");
530 DefOp = DefI.getOperandNo();
531 assert((++DefI).atEnd() && "Register has multiple defs");
536 // Get the input data dependencies that must be ready before UseMI can issue.
537 // Return true if UseMI has any physreg operands.
538 static bool getDataDeps(const MachineInstr *UseMI,
539 SmallVectorImpl<DataDep> &Deps,
540 const MachineRegisterInfo *MRI) {
541 bool HasPhysRegs = false;
542 for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) {
545 unsigned Reg = MO->getReg();
548 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
552 // Collect virtual register reads.
554 Deps.push_back(DataDep(MRI, Reg, MO.getOperandNo()));
559 // Get the input data dependencies of a PHI instruction, using Pred as the
560 // preferred predecessor.
561 // This will add at most one dependency to Deps.
562 static void getPHIDeps(const MachineInstr *UseMI,
563 SmallVectorImpl<DataDep> &Deps,
564 const MachineBasicBlock *Pred,
565 const MachineRegisterInfo *MRI) {
566 // No predecessor at the beginning of a trace. Ignore dependencies.
569 assert(UseMI->isPHI() && UseMI->getNumOperands() % 2 && "Bad PHI");
570 for (unsigned i = 1; i != UseMI->getNumOperands(); i += 2) {
571 if (UseMI->getOperand(i + 1).getMBB() == Pred) {
572 unsigned Reg = UseMI->getOperand(i).getReg();
573 Deps.push_back(DataDep(MRI, Reg, i));
579 // Keep track of physreg data dependencies by recording each live register unit.
580 // Associate each regunit with an instruction operand. Depending on the
581 // direction instructions are scanned, it could be the operand that defined the
582 // regunit, or the highest operand to read the regunit.
587 const MachineInstr *MI;
590 unsigned getSparseSetIndex() const { return RegUnit; }
592 LiveRegUnit(unsigned RU) : RegUnit(RU), Cycle(0), MI(0), Op(0) {}
596 // Identify physreg dependencies for UseMI, and update the live regunit
597 // tracking set when scanning instructions downwards.
598 static void updatePhysDepsDownwards(const MachineInstr *UseMI,
599 SmallVectorImpl<DataDep> &Deps,
600 SparseSet<LiveRegUnit> &RegUnits,
601 const TargetRegisterInfo *TRI) {
602 SmallVector<unsigned, 8> Kills;
603 SmallVector<unsigned, 8> LiveDefOps;
605 for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) {
608 unsigned Reg = MO->getReg();
609 if (!TargetRegisterInfo::isPhysicalRegister(Reg))
611 // Track live defs and kills for updating RegUnits.
614 Kills.push_back(Reg);
616 LiveDefOps.push_back(MO.getOperandNo());
617 } else if (MO->isKill())
618 Kills.push_back(Reg);
619 // Identify dependencies.
622 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
623 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units);
624 if (I == RegUnits.end())
626 Deps.push_back(DataDep(I->MI, I->Op, MO.getOperandNo()));
631 // Update RegUnits to reflect live registers after UseMI.
633 for (unsigned i = 0, e = Kills.size(); i != e; ++i)
634 for (MCRegUnitIterator Units(Kills[i], TRI); Units.isValid(); ++Units)
635 RegUnits.erase(*Units);
637 // Second, live defs.
638 for (unsigned i = 0, e = LiveDefOps.size(); i != e; ++i) {
639 unsigned DefOp = LiveDefOps[i];
640 for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI);
641 Units.isValid(); ++Units) {
642 LiveRegUnit &LRU = RegUnits[*Units];
649 /// The length of the critical path through a trace is the maximum of two path
652 /// 1. The maximum height+depth over all instructions in the trace center block.
654 /// 2. The longest cross-block dependency chain. For small blocks, it is
655 /// possible that the critical path through the trace doesn't include any
656 /// instructions in the block.
658 /// This function computes the second number from the live-in list of the
660 unsigned MachineTraceMetrics::Ensemble::
661 computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) {
662 assert(TBI.HasValidInstrDepths && "Missing depth info");
663 assert(TBI.HasValidInstrHeights && "Missing height info");
665 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) {
666 const LiveInReg &LIR = TBI.LiveIns[i];
667 if (!TargetRegisterInfo::isVirtualRegister(LIR.Reg))
669 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg);
670 // Ignore dependencies outside the current trace.
671 const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()];
672 if (!DefTBI.hasValidDepth() || DefTBI.Head != TBI.Head)
674 unsigned Len = LIR.Height + Cycles[DefMI].Depth;
675 MaxLen = std::max(MaxLen, Len);
680 /// Compute instruction depths for all instructions above or in MBB in its
681 /// trace. This assumes that the trace through MBB has already been computed.
682 void MachineTraceMetrics::Ensemble::
683 computeInstrDepths(const MachineBasicBlock *MBB) {
684 // The top of the trace may already be computed, and HasValidInstrDepths
685 // implies Head->HasValidInstrDepths, so we only need to start from the first
686 // block in the trace that needs to be recomputed.
687 SmallVector<const MachineBasicBlock*, 8> Stack;
689 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
690 assert(TBI.hasValidDepth() && "Incomplete trace");
691 if (TBI.HasValidInstrDepths)
693 Stack.push_back(MBB);
697 // FIXME: If MBB is non-null at this point, it is the last pre-computed block
698 // in the trace. We should track any live-out physregs that were defined in
699 // the trace. This is quite rare in SSA form, typically created by CSE
700 // hoisting a compare.
701 SparseSet<LiveRegUnit> RegUnits;
702 RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
704 // Go through trace blocks in top-down order, stopping after the center block.
705 SmallVector<DataDep, 8> Deps;
706 while (!Stack.empty()) {
707 MBB = Stack.pop_back_val();
708 DEBUG(dbgs() << "Depths for BB#" << MBB->getNumber() << ":\n");
709 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
710 TBI.HasValidInstrDepths = true;
711 TBI.CriticalPath = 0;
713 // Also compute the critical path length through MBB when possible.
714 if (TBI.HasValidInstrHeights)
715 TBI.CriticalPath = computeCrossBlockCriticalPath(TBI);
717 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
719 const MachineInstr *UseMI = I;
721 // Collect all data dependencies.
724 getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI);
725 else if (getDataDeps(UseMI, Deps, MTM.MRI))
726 updatePhysDepsDownwards(UseMI, Deps, RegUnits, MTM.TRI);
728 // Filter and process dependencies, computing the earliest issue cycle.
730 for (unsigned i = 0, e = Deps.size(); i != e; ++i) {
731 const DataDep &Dep = Deps[i];
732 const TraceBlockInfo&DepTBI =
733 BlockInfo[Dep.DefMI->getParent()->getNumber()];
734 // Ignore dependencies from outside the current trace.
735 if (!DepTBI.hasValidDepth() || DepTBI.Head != TBI.Head)
737 assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency");
738 unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;
739 // Add latency if DefMI is a real instruction. Transients get latency 0.
740 if (!Dep.DefMI->isTransient())
741 DepCycle += MTM.TII->computeOperandLatency(MTM.ItinData,
742 Dep.DefMI, Dep.DefOp,
744 /* FindMin = */ false);
745 Cycle = std::max(Cycle, DepCycle);
747 // Remember the instruction depth.
748 InstrCycles &MICycles = Cycles[UseMI];
749 MICycles.Depth = Cycle;
751 if (!TBI.HasValidInstrHeights) {
752 DEBUG(dbgs() << Cycle << '\t' << *UseMI);
755 // Update critical path length.
756 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height);
757 DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *UseMI);
762 // Identify physreg dependencies for MI when scanning instructions upwards.
763 // Return the issue height of MI after considering any live regunits.
764 // Height is the issue height computed from virtual register dependencies alone.
765 static unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height,
766 SparseSet<LiveRegUnit> &RegUnits,
767 const InstrItineraryData *ItinData,
768 const TargetInstrInfo *TII,
769 const TargetRegisterInfo *TRI) {
770 SmallVector<unsigned, 8> ReadOps;
771 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) {
774 unsigned Reg = MO->getReg();
775 if (!TargetRegisterInfo::isPhysicalRegister(Reg))
778 ReadOps.push_back(MO.getOperandNo());
781 // This is a def of Reg. Remove corresponding entries from RegUnits, and
782 // update MI Height to consider the physreg dependencies.
783 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
784 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units);
785 if (I == RegUnits.end())
787 unsigned DepHeight = I->Cycle;
788 if (!MI->isTransient()) {
789 // We may not know the UseMI of this dependency, if it came from the
792 DepHeight += TII->computeOperandLatency(ItinData,
793 MI, MO.getOperandNo(),
796 // No UseMI. Just use the MI latency instead.
797 DepHeight += TII->getInstrLatency(ItinData, MI);
799 Height = std::max(Height, DepHeight);
800 // This regunit is dead above MI.
805 // Now we know the height of MI. Update any regunits read.
806 for (unsigned i = 0, e = ReadOps.size(); i != e; ++i) {
807 unsigned Reg = MI->getOperand(ReadOps[i]).getReg();
808 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
809 LiveRegUnit &LRU = RegUnits[*Units];
810 // Set the height to the highest reader of the unit.
811 if (LRU.Cycle <= Height && LRU.MI != MI) {
823 typedef DenseMap<const MachineInstr *, unsigned> MIHeightMap;
825 // Push the height of DefMI upwards if required to match UseMI.
826 // Return true if this is the first time DefMI was seen.
827 static bool pushDepHeight(const DataDep &Dep,
828 const MachineInstr *UseMI, unsigned UseHeight,
829 MIHeightMap &Heights,
830 const InstrItineraryData *ItinData,
831 const TargetInstrInfo *TII) {
832 // Adjust height by Dep.DefMI latency.
833 if (!Dep.DefMI->isTransient())
834 UseHeight += TII->computeOperandLatency(ItinData, Dep.DefMI, Dep.DefOp,
837 // Update Heights[DefMI] to be the maximum height seen.
838 MIHeightMap::iterator I;
840 tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight));
844 // DefMI has been pushed before. Give it the max height.
845 if (I->second < UseHeight)
846 I->second = UseHeight;
850 /// Assuming that DefMI was used by Trace.back(), add it to the live-in lists
851 /// of all the blocks in Trace. Stop when reaching the block that contains
853 void MachineTraceMetrics::Ensemble::
854 addLiveIns(const MachineInstr *DefMI,
855 ArrayRef<const MachineBasicBlock*> Trace) {
856 assert(!Trace.empty() && "Trace should contain at least one block");
857 unsigned Reg = DefMI->getOperand(0).getReg();
858 assert(TargetRegisterInfo::isVirtualRegister(Reg));
859 const MachineBasicBlock *DefMBB = DefMI->getParent();
861 // Reg is live-in to all blocks in Trace that follow DefMBB.
862 for (unsigned i = Trace.size(); i; --i) {
863 const MachineBasicBlock *MBB = Trace[i-1];
866 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
867 // Just add the register. The height will be updated later.
868 TBI.LiveIns.push_back(Reg);
872 /// Compute instruction heights in the trace through MBB. This updates MBB and
873 /// the blocks below it in the trace. It is assumed that the trace has already
875 void MachineTraceMetrics::Ensemble::
876 computeInstrHeights(const MachineBasicBlock *MBB) {
877 // The bottom of the trace may already be computed.
878 // Find the blocks that need updating.
879 SmallVector<const MachineBasicBlock*, 8> Stack;
881 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
882 assert(TBI.hasValidHeight() && "Incomplete trace");
883 if (TBI.HasValidInstrHeights)
885 Stack.push_back(MBB);
890 // As we move upwards in the trace, keep track of instructions that are
891 // required by deeper trace instructions. Map MI -> height required so far.
894 // For physregs, the def isn't known when we see the use.
895 // Instead, keep track of the highest use of each regunit.
896 SparseSet<LiveRegUnit> RegUnits;
897 RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
899 // If the bottom of the trace was already precomputed, initialize heights
900 // from its live-in list.
901 // MBB is the highest precomputed block in the trace.
903 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
904 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) {
905 LiveInReg LI = TBI.LiveIns[i];
906 if (TargetRegisterInfo::isVirtualRegister(LI.Reg)) {
907 // For virtual registers, the def latency is included.
908 unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)];
909 if (Height < LI.Height)
912 // For register units, the def latency is not included because we don't
914 RegUnits[LI.Reg].Cycle = LI.Height;
919 // Go through the trace blocks in bottom-up order.
920 SmallVector<DataDep, 8> Deps;
921 for (;!Stack.empty(); Stack.pop_back()) {
923 DEBUG(dbgs() << "Heights for BB#" << MBB->getNumber() << ":\n");
924 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
925 TBI.HasValidInstrHeights = true;
926 TBI.CriticalPath = 0;
928 // Get dependencies from PHIs in the trace successor.
930 for (MachineBasicBlock::const_iterator
931 I = TBI.Succ->begin(), E = TBI.Succ->end();
932 I != E && !I->isPHI(); ++I) {
933 const MachineInstr *PHI = I;
935 getPHIDeps(PHI, Deps, MBB, MTM.MRI);
937 if (pushDepHeight(Deps.front(), PHI, Cycles.lookup(PHI).Height,
938 Heights, MTM.ItinData, MTM.TII))
939 addLiveIns(Deps.front().DefMI, Stack);
943 // Go through the block backwards.
944 for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin();
946 const MachineInstr *MI = --BI;
948 // Find the MI height as determined by virtual register uses in the
951 MIHeightMap::iterator HeightI = Heights.find(MI);
952 if (HeightI != Heights.end()) {
953 Cycle = HeightI->second;
954 // We won't be seeing any more MI uses.
955 Heights.erase(HeightI);
958 // Don't process PHI deps. They depend on the specific predecessor, and
959 // we'll get them when visiting the predecessor.
961 bool HasPhysRegs = !MI->isPHI() && getDataDeps(MI, Deps, MTM.MRI);
963 // There may also be regunit dependencies to include in the height.
965 Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits,
966 MTM.ItinData, MTM.TII, MTM.TRI);
968 // Update the required height of any virtual registers read by MI.
969 for (unsigned i = 0, e = Deps.size(); i != e; ++i)
970 if (pushDepHeight(Deps[i], MI, Cycle, Heights, MTM.ItinData, MTM.TII))
971 addLiveIns(Deps[i].DefMI, Stack);
973 InstrCycles &MICycles = Cycles[MI];
974 MICycles.Height = Cycle;
975 if (!TBI.HasValidInstrDepths) {
976 DEBUG(dbgs() << Cycle << '\t' << *MI);
979 // Update critical path length.
980 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth);
981 DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *MI);
984 // Update virtual live-in heights. They were added by addLiveIns() with a 0
985 // height because the final height isn't known until now.
986 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:");
987 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) {
988 LiveInReg &LIR = TBI.LiveIns[i];
989 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg);
990 LIR.Height = Heights.lookup(DefMI);
991 DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height);
994 // Transfer the live regunits to the live-in list.
995 for (SparseSet<LiveRegUnit>::const_iterator
996 RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) {
997 TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle));
998 DEBUG(dbgs() << ' ' << PrintRegUnit(RI->RegUnit, MTM.TRI)
999 << '@' << RI->Cycle);
1001 DEBUG(dbgs() << '\n');
1003 if (!TBI.HasValidInstrDepths)
1005 // Add live-ins to the critical path length.
1006 TBI.CriticalPath = std::max(TBI.CriticalPath,
1007 computeCrossBlockCriticalPath(TBI));
1008 DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n');
1012 MachineTraceMetrics::Trace
1013 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
1014 // FIXME: Check cache tags, recompute as needed.
1016 computeInstrDepths(MBB);
1017 computeInstrHeights(MBB);
1018 return Trace(*this, BlockInfo[MBB->getNumber()]);
1022 MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr *MI) const {
1023 assert(MI && "Not an instruction.");
1024 assert(getBlockNum() == unsigned(MI->getParent()->getNumber()) &&
1025 "MI must be in the trace center block");
1026 InstrCycles Cyc = getInstrCycles(MI);
1027 return getCriticalPath() - (Cyc.Depth + Cyc.Height);
1030 unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const {
1031 // For now, we compute the resource depth from instruction count / issue
1032 // width. Eventually, we should compute resource depth per functional unit
1033 // and return the max.
1034 unsigned Instrs = TBI.InstrDepth;
1036 Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount;
1037 if (const MCSchedModel *Model = TE.MTM.ItinData->SchedModel)
1038 if (Model->IssueWidth != 0)
1039 return Instrs / Model->IssueWidth;
1040 // Assume issue width 1 without a schedule model.
1044 void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const {
1045 OS << getName() << " ensemble:\n";
1046 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
1047 OS << " BB#" << i << '\t';
1048 BlockInfo[i].print(OS);
1053 void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const {
1054 if (hasValidDepth()) {
1055 OS << "depth=" << InstrDepth;
1057 OS << " pred=BB#" << Pred->getNumber();
1060 OS << " head=BB#" << Head;
1061 if (HasValidInstrDepths)
1064 OS << "depth invalid";
1066 if (hasValidHeight()) {
1067 OS << "height=" << InstrHeight;
1069 OS << " succ=BB#" << Succ->getNumber();
1072 OS << " tail=BB#" << Tail;
1073 if (HasValidInstrHeights)
1076 OS << "height invalid";
1077 if (HasValidInstrDepths && HasValidInstrHeights)
1078 OS << ", crit=" << CriticalPath;
1081 void MachineTraceMetrics::Trace::print(raw_ostream &OS) const {
1082 unsigned MBBNum = &TBI - &TE.BlockInfo[0];
1084 OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum
1085 << " --> BB#" << TBI.Tail << ':';
1086 if (TBI.hasValidHeight() && TBI.hasValidDepth())
1087 OS << ' ' << getInstrCount() << " instrs.";
1088 if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights)
1089 OS << ' ' << TBI.CriticalPath << " cycles.";
1091 const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
1092 OS << "\nBB#" << MBBNum;
1093 while (Block->hasValidDepth() && Block->Pred) {
1094 unsigned Num = Block->Pred->getNumber();
1095 OS << " <- BB#" << Num;
1096 Block = &TE.BlockInfo[Num];
1101 while (Block->hasValidHeight() && Block->Succ) {
1102 unsigned Num = Block->Succ->getNumber();
1103 OS << " -> BB#" << Num;
1104 Block = &TE.BlockInfo[Num];