1239310Sdim//===- lib/CodeGen/MachineTraceMetrics.cpp ----------------------*- C++ -*-===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim 10239310Sdim#define DEBUG_TYPE "machine-trace-metrics" 11249423Sdim#include "llvm/CodeGen/MachineTraceMetrics.h" 12249423Sdim#include "llvm/ADT/PostOrderIterator.h" 13249423Sdim#include "llvm/ADT/SparseSet.h" 14239310Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 15239310Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 16239310Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 17239310Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 18239310Sdim#include "llvm/CodeGen/Passes.h" 19243830Sdim#include "llvm/MC/MCSubtargetInfo.h" 20249423Sdim#include "llvm/Support/Debug.h" 21249423Sdim#include "llvm/Support/Format.h" 22249423Sdim#include "llvm/Support/raw_ostream.h" 23239310Sdim#include "llvm/Target/TargetInstrInfo.h" 24239310Sdim#include "llvm/Target/TargetRegisterInfo.h" 25243830Sdim#include "llvm/Target/TargetSubtargetInfo.h" 26239310Sdim 27239310Sdimusing namespace llvm; 28239310Sdim 29239310Sdimchar MachineTraceMetrics::ID = 0; 30239310Sdimchar &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; 31239310Sdim 32239310SdimINITIALIZE_PASS_BEGIN(MachineTraceMetrics, 33239310Sdim "machine-trace-metrics", "Machine Trace Metrics", false, true) 34239310SdimINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 35239310SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 36239310SdimINITIALIZE_PASS_END(MachineTraceMetrics, 37239310Sdim "machine-trace-metrics", "Machine Trace Metrics", false, true) 38239310Sdim 39239310SdimMachineTraceMetrics::MachineTraceMetrics() 40239310Sdim : MachineFunctionPass(ID), MF(0), TII(0), TRI(0), MRI(0), Loops(0) { 41239310Sdim std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0); 42239310Sdim} 43239310Sdim 44239310Sdimvoid MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { 45239310Sdim AU.setPreservesAll(); 46239310Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 47239310Sdim AU.addRequired<MachineLoopInfo>(); 48239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 49239310Sdim} 50239310Sdim 51239310Sdimbool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { 52239310Sdim MF = &Func; 53239310Sdim TII = MF->getTarget().getInstrInfo(); 54239310Sdim TRI = MF->getTarget().getRegisterInfo(); 55239310Sdim MRI = &MF->getRegInfo(); 56239310Sdim Loops = &getAnalysis<MachineLoopInfo>(); 57243830Sdim const TargetSubtargetInfo &ST = 58243830Sdim MF->getTarget().getSubtarget<TargetSubtargetInfo>(); 59243830Sdim SchedModel.init(*ST.getSchedModel(), &ST, TII); 60239310Sdim BlockInfo.resize(MF->getNumBlockIDs()); 61249423Sdim ProcResourceCycles.resize(MF->getNumBlockIDs() * 62249423Sdim SchedModel.getNumProcResourceKinds()); 63239310Sdim return false; 64239310Sdim} 65239310Sdim 66239310Sdimvoid MachineTraceMetrics::releaseMemory() { 67239310Sdim MF = 0; 68239310Sdim BlockInfo.clear(); 69239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) { 70239310Sdim delete Ensembles[i]; 71239310Sdim Ensembles[i] = 0; 72239310Sdim } 73239310Sdim} 74239310Sdim 75239310Sdim//===----------------------------------------------------------------------===// 76239310Sdim// Fixed block information 77239310Sdim//===----------------------------------------------------------------------===// 78239310Sdim// 79239310Sdim// The number of instructions in a basic block and the CPU resources used by 80239310Sdim// those instructions don't depend on any given trace strategy. 81239310Sdim 82239310Sdim/// Compute the resource usage in basic block MBB. 83239310Sdimconst MachineTraceMetrics::FixedBlockInfo* 84239310SdimMachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { 85239310Sdim assert(MBB && "No basic block"); 86239310Sdim FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; 87239310Sdim if (FBI->hasResources()) 88239310Sdim return FBI; 89239310Sdim 90239310Sdim // Compute resource usage in the block. 91239310Sdim FBI->HasCalls = false; 92239310Sdim unsigned InstrCount = 0; 93249423Sdim 94249423Sdim // Add up per-processor resource cycles as well. 95249423Sdim unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 96249423Sdim SmallVector<unsigned, 32> PRCycles(PRKinds); 97249423Sdim 98239310Sdim for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 99239310Sdim I != E; ++I) { 100239310Sdim const MachineInstr *MI = I; 101239310Sdim if (MI->isTransient()) 102239310Sdim continue; 103239310Sdim ++InstrCount; 104239310Sdim if (MI->isCall()) 105239310Sdim FBI->HasCalls = true; 106249423Sdim 107249423Sdim // Count processor resources used. 108249423Sdim if (!SchedModel.hasInstrSchedModel()) 109249423Sdim continue; 110249423Sdim const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(MI); 111249423Sdim if (!SC->isValid()) 112249423Sdim continue; 113249423Sdim 114249423Sdim for (TargetSchedModel::ProcResIter 115249423Sdim PI = SchedModel.getWriteProcResBegin(SC), 116249423Sdim PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 117249423Sdim assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind"); 118249423Sdim PRCycles[PI->ProcResourceIdx] += PI->Cycles; 119249423Sdim } 120239310Sdim } 121239310Sdim FBI->InstrCount = InstrCount; 122249423Sdim 123249423Sdim // Scale the resource cycles so they are comparable. 124249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 125249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 126249423Sdim ProcResourceCycles[PROffset + K] = 127249423Sdim PRCycles[K] * SchedModel.getResourceFactor(K); 128249423Sdim 129239310Sdim return FBI; 130239310Sdim} 131239310Sdim 132249423SdimArrayRef<unsigned> 133249423SdimMachineTraceMetrics::getProcResourceCycles(unsigned MBBNum) const { 134249423Sdim assert(BlockInfo[MBBNum].hasResources() && 135249423Sdim "getResources() must be called before getProcResourceCycles()"); 136249423Sdim unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 137249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size()); 138249423Sdim return ArrayRef<unsigned>(ProcResourceCycles.data() + MBBNum * PRKinds, 139249423Sdim PRKinds); 140249423Sdim} 141249423Sdim 142249423Sdim 143239310Sdim//===----------------------------------------------------------------------===// 144239310Sdim// Ensemble utility functions 145239310Sdim//===----------------------------------------------------------------------===// 146239310Sdim 147239310SdimMachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) 148239310Sdim : MTM(*ct) { 149239310Sdim BlockInfo.resize(MTM.BlockInfo.size()); 150249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 151249423Sdim ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds); 152249423Sdim ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds); 153239310Sdim} 154239310Sdim 155239310Sdim// Virtual destructor serves as an anchor. 156239310SdimMachineTraceMetrics::Ensemble::~Ensemble() {} 157239310Sdim 158239310Sdimconst MachineLoop* 159239310SdimMachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { 160239310Sdim return MTM.Loops->getLoopFor(MBB); 161239310Sdim} 162239310Sdim 163239310Sdim// Update resource-related information in the TraceBlockInfo for MBB. 164239310Sdim// Only update resources related to the trace above MBB. 165239310Sdimvoid MachineTraceMetrics::Ensemble:: 166239310SdimcomputeDepthResources(const MachineBasicBlock *MBB) { 167239310Sdim TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 168249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 169249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 170239310Sdim 171239310Sdim // Compute resources from trace above. The top block is simple. 172239310Sdim if (!TBI->Pred) { 173239310Sdim TBI->InstrDepth = 0; 174239310Sdim TBI->Head = MBB->getNumber(); 175249423Sdim std::fill(ProcResourceDepths.begin() + PROffset, 176249423Sdim ProcResourceDepths.begin() + PROffset + PRKinds, 0); 177239310Sdim return; 178239310Sdim } 179239310Sdim 180239310Sdim // Compute from the block above. A post-order traversal ensures the 181239310Sdim // predecessor is always computed first. 182249423Sdim unsigned PredNum = TBI->Pred->getNumber(); 183249423Sdim TraceBlockInfo *PredTBI = &BlockInfo[PredNum]; 184239310Sdim assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); 185239310Sdim const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred); 186239310Sdim TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; 187239310Sdim TBI->Head = PredTBI->Head; 188249423Sdim 189249423Sdim // Compute per-resource depths. 190249423Sdim ArrayRef<unsigned> PredPRDepths = getProcResourceDepths(PredNum); 191249423Sdim ArrayRef<unsigned> PredPRCycles = MTM.getProcResourceCycles(PredNum); 192249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 193249423Sdim ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K]; 194239310Sdim} 195239310Sdim 196239310Sdim// Update resource-related information in the TraceBlockInfo for MBB. 197239310Sdim// Only update resources related to the trace below MBB. 198239310Sdimvoid MachineTraceMetrics::Ensemble:: 199239310SdimcomputeHeightResources(const MachineBasicBlock *MBB) { 200239310Sdim TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 201249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 202249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 203239310Sdim 204239310Sdim // Compute resources for the current block. 205239310Sdim TBI->InstrHeight = MTM.getResources(MBB)->InstrCount; 206249423Sdim ArrayRef<unsigned> PRCycles = MTM.getProcResourceCycles(MBB->getNumber()); 207239310Sdim 208239310Sdim // The trace tail is done. 209239310Sdim if (!TBI->Succ) { 210239310Sdim TBI->Tail = MBB->getNumber(); 211249423Sdim std::copy(PRCycles.begin(), PRCycles.end(), 212249423Sdim ProcResourceHeights.begin() + PROffset); 213239310Sdim return; 214239310Sdim } 215239310Sdim 216239310Sdim // Compute from the block below. A post-order traversal ensures the 217239310Sdim // predecessor is always computed first. 218249423Sdim unsigned SuccNum = TBI->Succ->getNumber(); 219249423Sdim TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum]; 220239310Sdim assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); 221239310Sdim TBI->InstrHeight += SuccTBI->InstrHeight; 222239310Sdim TBI->Tail = SuccTBI->Tail; 223249423Sdim 224249423Sdim // Compute per-resource heights. 225249423Sdim ArrayRef<unsigned> SuccPRHeights = getProcResourceHeights(SuccNum); 226249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 227249423Sdim ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K]; 228239310Sdim} 229239310Sdim 230239310Sdim// Check if depth resources for MBB are valid and return the TBI. 231239310Sdim// Return NULL if the resources have been invalidated. 232239310Sdimconst MachineTraceMetrics::TraceBlockInfo* 233239310SdimMachineTraceMetrics::Ensemble:: 234239310SdimgetDepthResources(const MachineBasicBlock *MBB) const { 235239310Sdim const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 236239310Sdim return TBI->hasValidDepth() ? TBI : 0; 237239310Sdim} 238239310Sdim 239239310Sdim// Check if height resources for MBB are valid and return the TBI. 240239310Sdim// Return NULL if the resources have been invalidated. 241239310Sdimconst MachineTraceMetrics::TraceBlockInfo* 242239310SdimMachineTraceMetrics::Ensemble:: 243239310SdimgetHeightResources(const MachineBasicBlock *MBB) const { 244239310Sdim const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 245239310Sdim return TBI->hasValidHeight() ? TBI : 0; 246239310Sdim} 247239310Sdim 248249423Sdim/// Get an array of processor resource depths for MBB. Indexed by processor 249249423Sdim/// resource kind, this array contains the scaled processor resources consumed 250249423Sdim/// by all blocks preceding MBB in its trace. It does not include instructions 251249423Sdim/// in MBB. 252249423Sdim/// 253249423Sdim/// Compare TraceBlockInfo::InstrDepth. 254249423SdimArrayRef<unsigned> 255249423SdimMachineTraceMetrics::Ensemble:: 256249423SdimgetProcResourceDepths(unsigned MBBNum) const { 257249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 258249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size()); 259249423Sdim return ArrayRef<unsigned>(ProcResourceDepths.data() + MBBNum * PRKinds, 260249423Sdim PRKinds); 261249423Sdim} 262249423Sdim 263249423Sdim/// Get an array of processor resource heights for MBB. Indexed by processor 264249423Sdim/// resource kind, this array contains the scaled processor resources consumed 265249423Sdim/// by this block and all blocks following it in its trace. 266249423Sdim/// 267249423Sdim/// Compare TraceBlockInfo::InstrHeight. 268249423SdimArrayRef<unsigned> 269249423SdimMachineTraceMetrics::Ensemble:: 270249423SdimgetProcResourceHeights(unsigned MBBNum) const { 271249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 272249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size()); 273249423Sdim return ArrayRef<unsigned>(ProcResourceHeights.data() + MBBNum * PRKinds, 274249423Sdim PRKinds); 275249423Sdim} 276249423Sdim 277239310Sdim//===----------------------------------------------------------------------===// 278239310Sdim// Trace Selection Strategies 279239310Sdim//===----------------------------------------------------------------------===// 280239310Sdim// 281239310Sdim// A trace selection strategy is implemented as a sub-class of Ensemble. The 282239310Sdim// trace through a block B is computed by two DFS traversals of the CFG 283239310Sdim// starting from B. One upwards, and one downwards. During the upwards DFS, 284239310Sdim// pickTracePred() is called on the post-ordered blocks. During the downwards 285239310Sdim// DFS, pickTraceSucc() is called in a post-order. 286239310Sdim// 287239310Sdim 288239310Sdim// We never allow traces that leave loops, but we do allow traces to enter 289239310Sdim// nested loops. We also never allow traces to contain back-edges. 290239310Sdim// 291239310Sdim// This means that a loop header can never appear above the center block of a 292239310Sdim// trace, except as the trace head. Below the center block, loop exiting edges 293239310Sdim// are banned. 294239310Sdim// 295239310Sdim// Return true if an edge from the From loop to the To loop is leaving a loop. 296239310Sdim// Either of To and From can be null. 297239310Sdimstatic bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { 298239310Sdim return From && !From->contains(To); 299239310Sdim} 300239310Sdim 301239310Sdim// MinInstrCountEnsemble - Pick the trace that executes the least number of 302239310Sdim// instructions. 303239310Sdimnamespace { 304239310Sdimclass MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { 305239310Sdim const char *getName() const { return "MinInstr"; } 306239310Sdim const MachineBasicBlock *pickTracePred(const MachineBasicBlock*); 307239310Sdim const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*); 308239310Sdim 309239310Sdimpublic: 310239310Sdim MinInstrCountEnsemble(MachineTraceMetrics *mtm) 311239310Sdim : MachineTraceMetrics::Ensemble(mtm) {} 312239310Sdim}; 313239310Sdim} 314239310Sdim 315239310Sdim// Select the preferred predecessor for MBB. 316239310Sdimconst MachineBasicBlock* 317239310SdimMinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { 318239310Sdim if (MBB->pred_empty()) 319239310Sdim return 0; 320239310Sdim const MachineLoop *CurLoop = getLoopFor(MBB); 321239310Sdim // Don't leave loops, and never follow back-edges. 322239310Sdim if (CurLoop && MBB == CurLoop->getHeader()) 323239310Sdim return 0; 324239310Sdim unsigned CurCount = MTM.getResources(MBB)->InstrCount; 325239310Sdim const MachineBasicBlock *Best = 0; 326239310Sdim unsigned BestDepth = 0; 327239310Sdim for (MachineBasicBlock::const_pred_iterator 328239310Sdim I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 329239310Sdim const MachineBasicBlock *Pred = *I; 330239310Sdim const MachineTraceMetrics::TraceBlockInfo *PredTBI = 331239310Sdim getDepthResources(Pred); 332239310Sdim // Ignore cycles that aren't natural loops. 333239310Sdim if (!PredTBI) 334239310Sdim continue; 335239310Sdim // Pick the predecessor that would give this block the smallest InstrDepth. 336239310Sdim unsigned Depth = PredTBI->InstrDepth + CurCount; 337239310Sdim if (!Best || Depth < BestDepth) 338239310Sdim Best = Pred, BestDepth = Depth; 339239310Sdim } 340239310Sdim return Best; 341239310Sdim} 342239310Sdim 343239310Sdim// Select the preferred successor for MBB. 344239310Sdimconst MachineBasicBlock* 345239310SdimMinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { 346239310Sdim if (MBB->pred_empty()) 347239310Sdim return 0; 348239310Sdim const MachineLoop *CurLoop = getLoopFor(MBB); 349239310Sdim const MachineBasicBlock *Best = 0; 350239310Sdim unsigned BestHeight = 0; 351239310Sdim for (MachineBasicBlock::const_succ_iterator 352239310Sdim I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 353239310Sdim const MachineBasicBlock *Succ = *I; 354239310Sdim // Don't consider back-edges. 355239310Sdim if (CurLoop && Succ == CurLoop->getHeader()) 356239310Sdim continue; 357239310Sdim // Don't consider successors exiting CurLoop. 358239310Sdim if (isExitingLoop(CurLoop, getLoopFor(Succ))) 359239310Sdim continue; 360239310Sdim const MachineTraceMetrics::TraceBlockInfo *SuccTBI = 361239310Sdim getHeightResources(Succ); 362239310Sdim // Ignore cycles that aren't natural loops. 363239310Sdim if (!SuccTBI) 364239310Sdim continue; 365239310Sdim // Pick the successor that would give this block the smallest InstrHeight. 366239310Sdim unsigned Height = SuccTBI->InstrHeight; 367239310Sdim if (!Best || Height < BestHeight) 368239310Sdim Best = Succ, BestHeight = Height; 369239310Sdim } 370239310Sdim return Best; 371239310Sdim} 372239310Sdim 373239310Sdim// Get an Ensemble sub-class for the requested trace strategy. 374239310SdimMachineTraceMetrics::Ensemble * 375239310SdimMachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { 376239310Sdim assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); 377239310Sdim Ensemble *&E = Ensembles[strategy]; 378239310Sdim if (E) 379239310Sdim return E; 380239310Sdim 381239310Sdim // Allocate new Ensemble on demand. 382239310Sdim switch (strategy) { 383239310Sdim case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); 384239310Sdim default: llvm_unreachable("Invalid trace strategy enum"); 385239310Sdim } 386239310Sdim} 387239310Sdim 388239310Sdimvoid MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { 389239310Sdim DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n'); 390239310Sdim BlockInfo[MBB->getNumber()].invalidate(); 391239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) 392239310Sdim if (Ensembles[i]) 393239310Sdim Ensembles[i]->invalidate(MBB); 394239310Sdim} 395239310Sdim 396239310Sdimvoid MachineTraceMetrics::verifyAnalysis() const { 397239310Sdim if (!MF) 398239310Sdim return; 399239310Sdim#ifndef NDEBUG 400239310Sdim assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); 401239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) 402239310Sdim if (Ensembles[i]) 403239310Sdim Ensembles[i]->verify(); 404239310Sdim#endif 405239310Sdim} 406239310Sdim 407239310Sdim//===----------------------------------------------------------------------===// 408239310Sdim// Trace building 409239310Sdim//===----------------------------------------------------------------------===// 410239310Sdim// 411239310Sdim// Traces are built by two CFG traversals. To avoid recomputing too much, use a 412239310Sdim// set abstraction that confines the search to the current loop, and doesn't 413239310Sdim// revisit blocks. 414239310Sdim 415239310Sdimnamespace { 416239310Sdimstruct LoopBounds { 417239310Sdim MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; 418239310Sdim SmallPtrSet<const MachineBasicBlock*, 8> Visited; 419239310Sdim const MachineLoopInfo *Loops; 420239310Sdim bool Downward; 421239310Sdim LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, 422239310Sdim const MachineLoopInfo *loops) 423239310Sdim : Blocks(blocks), Loops(loops), Downward(false) {} 424239310Sdim}; 425239310Sdim} 426239310Sdim 427239310Sdim// Specialize po_iterator_storage in order to prune the post-order traversal so 428239310Sdim// it is limited to the current loop and doesn't traverse the loop back edges. 429239310Sdimnamespace llvm { 430239310Sdimtemplate<> 431239310Sdimclass po_iterator_storage<LoopBounds, true> { 432239310Sdim LoopBounds &LB; 433239310Sdimpublic: 434239310Sdim po_iterator_storage(LoopBounds &lb) : LB(lb) {} 435239310Sdim void finishPostorder(const MachineBasicBlock*) {} 436239310Sdim 437239310Sdim bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) { 438239310Sdim // Skip already visited To blocks. 439239310Sdim MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; 440239310Sdim if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth()) 441239310Sdim return false; 442239310Sdim // From is null once when To is the trace center block. 443239310Sdim if (From) { 444239310Sdim if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(From)) { 445239310Sdim // Don't follow backedges, don't leave FromLoop when going upwards. 446239310Sdim if ((LB.Downward ? To : From) == FromLoop->getHeader()) 447239310Sdim return false; 448239310Sdim // Don't leave FromLoop. 449239310Sdim if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To))) 450239310Sdim return false; 451239310Sdim } 452239310Sdim } 453239310Sdim // To is a new block. Mark the block as visited in case the CFG has cycles 454239310Sdim // that MachineLoopInfo didn't recognize as a natural loop. 455239310Sdim return LB.Visited.insert(To); 456239310Sdim } 457239310Sdim}; 458239310Sdim} 459239310Sdim 460239310Sdim/// Compute the trace through MBB. 461239310Sdimvoid MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { 462239310Sdim DEBUG(dbgs() << "Computing " << getName() << " trace through BB#" 463239310Sdim << MBB->getNumber() << '\n'); 464239310Sdim // Set up loop bounds for the backwards post-order traversal. 465239310Sdim LoopBounds Bounds(BlockInfo, MTM.Loops); 466239310Sdim 467239310Sdim // Run an upwards post-order search for the trace start. 468239310Sdim Bounds.Downward = false; 469239310Sdim Bounds.Visited.clear(); 470239310Sdim typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO; 471239310Sdim for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds); 472239310Sdim I != E; ++I) { 473239310Sdim DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); 474239310Sdim TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 475239310Sdim // All the predecessors have been visited, pick the preferred one. 476239310Sdim TBI.Pred = pickTracePred(*I); 477239310Sdim DEBUG({ 478239310Sdim if (TBI.Pred) 479239310Sdim dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; 480239310Sdim else 481239310Sdim dbgs() << "null\n"; 482239310Sdim }); 483239310Sdim // The trace leading to I is now known, compute the depth resources. 484239310Sdim computeDepthResources(*I); 485239310Sdim } 486239310Sdim 487239310Sdim // Run a downwards post-order search for the trace end. 488239310Sdim Bounds.Downward = true; 489239310Sdim Bounds.Visited.clear(); 490239310Sdim typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO; 491239310Sdim for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds); 492239310Sdim I != E; ++I) { 493239310Sdim DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); 494239310Sdim TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 495239310Sdim // All the successors have been visited, pick the preferred one. 496239310Sdim TBI.Succ = pickTraceSucc(*I); 497239310Sdim DEBUG({ 498239310Sdim if (TBI.Succ) 499239310Sdim dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; 500239310Sdim else 501239310Sdim dbgs() << "null\n"; 502239310Sdim }); 503239310Sdim // The trace leaving I is now known, compute the height resources. 504239310Sdim computeHeightResources(*I); 505239310Sdim } 506239310Sdim} 507239310Sdim 508239310Sdim/// Invalidate traces through BadMBB. 509239310Sdimvoid 510239310SdimMachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { 511239310Sdim SmallVector<const MachineBasicBlock*, 16> WorkList; 512239310Sdim TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; 513239310Sdim 514239310Sdim // Invalidate height resources of blocks above MBB. 515239310Sdim if (BadTBI.hasValidHeight()) { 516239310Sdim BadTBI.invalidateHeight(); 517239310Sdim WorkList.push_back(BadMBB); 518239310Sdim do { 519239310Sdim const MachineBasicBlock *MBB = WorkList.pop_back_val(); 520239310Sdim DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 521239310Sdim << " height.\n"); 522239310Sdim // Find any MBB predecessors that have MBB as their preferred successor. 523239310Sdim // They are the only ones that need to be invalidated. 524239310Sdim for (MachineBasicBlock::const_pred_iterator 525239310Sdim I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 526239310Sdim TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 527239310Sdim if (!TBI.hasValidHeight()) 528239310Sdim continue; 529239310Sdim if (TBI.Succ == MBB) { 530239310Sdim TBI.invalidateHeight(); 531239310Sdim WorkList.push_back(*I); 532239310Sdim continue; 533239310Sdim } 534239310Sdim // Verify that TBI.Succ is actually a *I successor. 535239310Sdim assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed"); 536239310Sdim } 537239310Sdim } while (!WorkList.empty()); 538239310Sdim } 539239310Sdim 540239310Sdim // Invalidate depth resources of blocks below MBB. 541239310Sdim if (BadTBI.hasValidDepth()) { 542239310Sdim BadTBI.invalidateDepth(); 543239310Sdim WorkList.push_back(BadMBB); 544239310Sdim do { 545239310Sdim const MachineBasicBlock *MBB = WorkList.pop_back_val(); 546239310Sdim DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 547239310Sdim << " depth.\n"); 548239310Sdim // Find any MBB successors that have MBB as their preferred predecessor. 549239310Sdim // They are the only ones that need to be invalidated. 550239310Sdim for (MachineBasicBlock::const_succ_iterator 551239310Sdim I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 552239310Sdim TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 553239310Sdim if (!TBI.hasValidDepth()) 554239310Sdim continue; 555239310Sdim if (TBI.Pred == MBB) { 556239310Sdim TBI.invalidateDepth(); 557239310Sdim WorkList.push_back(*I); 558239310Sdim continue; 559239310Sdim } 560239310Sdim // Verify that TBI.Pred is actually a *I predecessor. 561239310Sdim assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed"); 562239310Sdim } 563239310Sdim } while (!WorkList.empty()); 564239310Sdim } 565239310Sdim 566239310Sdim // Clear any per-instruction data. We only have to do this for BadMBB itself 567239310Sdim // because the instructions in that block may change. Other blocks may be 568239310Sdim // invalidated, but their instructions will stay the same, so there is no 569239310Sdim // need to erase the Cycle entries. They will be overwritten when we 570239310Sdim // recompute. 571239310Sdim for (MachineBasicBlock::const_iterator I = BadMBB->begin(), E = BadMBB->end(); 572239310Sdim I != E; ++I) 573239310Sdim Cycles.erase(I); 574239310Sdim} 575239310Sdim 576239310Sdimvoid MachineTraceMetrics::Ensemble::verify() const { 577239310Sdim#ifndef NDEBUG 578239310Sdim assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() && 579239310Sdim "Outdated BlockInfo size"); 580239310Sdim for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { 581239310Sdim const TraceBlockInfo &TBI = BlockInfo[Num]; 582239310Sdim if (TBI.hasValidDepth() && TBI.Pred) { 583239310Sdim const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 584239310Sdim assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); 585239310Sdim assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && 586239310Sdim "Trace is broken, depth should have been invalidated."); 587239310Sdim const MachineLoop *Loop = getLoopFor(MBB); 588239310Sdim assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); 589239310Sdim } 590239310Sdim if (TBI.hasValidHeight() && TBI.Succ) { 591239310Sdim const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 592239310Sdim assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); 593239310Sdim assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && 594239310Sdim "Trace is broken, height should have been invalidated."); 595239310Sdim const MachineLoop *Loop = getLoopFor(MBB); 596239310Sdim const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); 597239310Sdim assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && 598239310Sdim "Trace contains backedge"); 599239310Sdim } 600239310Sdim } 601239310Sdim#endif 602239310Sdim} 603239310Sdim 604239310Sdim//===----------------------------------------------------------------------===// 605239310Sdim// Data Dependencies 606239310Sdim//===----------------------------------------------------------------------===// 607239310Sdim// 608239310Sdim// Compute the depth and height of each instruction based on data dependencies 609239310Sdim// and instruction latencies. These cycle numbers assume that the CPU can issue 610239310Sdim// an infinite number of instructions per cycle as long as their dependencies 611239310Sdim// are ready. 612239310Sdim 613239310Sdim// A data dependency is represented as a defining MI and operand numbers on the 614239310Sdim// defining and using MI. 615239310Sdimnamespace { 616239310Sdimstruct DataDep { 617239310Sdim const MachineInstr *DefMI; 618239310Sdim unsigned DefOp; 619239310Sdim unsigned UseOp; 620239310Sdim 621239310Sdim DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp) 622239310Sdim : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {} 623239310Sdim 624239310Sdim /// Create a DataDep from an SSA form virtual register. 625239310Sdim DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp) 626239310Sdim : UseOp(UseOp) { 627239310Sdim assert(TargetRegisterInfo::isVirtualRegister(VirtReg)); 628239310Sdim MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg); 629239310Sdim assert(!DefI.atEnd() && "Register has no defs"); 630239310Sdim DefMI = &*DefI; 631239310Sdim DefOp = DefI.getOperandNo(); 632239310Sdim assert((++DefI).atEnd() && "Register has multiple defs"); 633239310Sdim } 634239310Sdim}; 635239310Sdim} 636239310Sdim 637239310Sdim// Get the input data dependencies that must be ready before UseMI can issue. 638239310Sdim// Return true if UseMI has any physreg operands. 639239310Sdimstatic bool getDataDeps(const MachineInstr *UseMI, 640239310Sdim SmallVectorImpl<DataDep> &Deps, 641239310Sdim const MachineRegisterInfo *MRI) { 642239310Sdim bool HasPhysRegs = false; 643239310Sdim for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { 644239310Sdim if (!MO->isReg()) 645239310Sdim continue; 646239310Sdim unsigned Reg = MO->getReg(); 647239310Sdim if (!Reg) 648239310Sdim continue; 649239310Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 650239310Sdim HasPhysRegs = true; 651239310Sdim continue; 652239310Sdim } 653239310Sdim // Collect virtual register reads. 654239310Sdim if (MO->readsReg()) 655239310Sdim Deps.push_back(DataDep(MRI, Reg, MO.getOperandNo())); 656239310Sdim } 657239310Sdim return HasPhysRegs; 658239310Sdim} 659239310Sdim 660239310Sdim// Get the input data dependencies of a PHI instruction, using Pred as the 661239310Sdim// preferred predecessor. 662239310Sdim// This will add at most one dependency to Deps. 663239310Sdimstatic void getPHIDeps(const MachineInstr *UseMI, 664239310Sdim SmallVectorImpl<DataDep> &Deps, 665239310Sdim const MachineBasicBlock *Pred, 666239310Sdim const MachineRegisterInfo *MRI) { 667239310Sdim // No predecessor at the beginning of a trace. Ignore dependencies. 668239310Sdim if (!Pred) 669239310Sdim return; 670239310Sdim assert(UseMI->isPHI() && UseMI->getNumOperands() % 2 && "Bad PHI"); 671239310Sdim for (unsigned i = 1; i != UseMI->getNumOperands(); i += 2) { 672239310Sdim if (UseMI->getOperand(i + 1).getMBB() == Pred) { 673239310Sdim unsigned Reg = UseMI->getOperand(i).getReg(); 674239310Sdim Deps.push_back(DataDep(MRI, Reg, i)); 675239310Sdim return; 676239310Sdim } 677239310Sdim } 678239310Sdim} 679239310Sdim 680239310Sdim// Keep track of physreg data dependencies by recording each live register unit. 681239310Sdim// Associate each regunit with an instruction operand. Depending on the 682239310Sdim// direction instructions are scanned, it could be the operand that defined the 683239310Sdim// regunit, or the highest operand to read the regunit. 684239310Sdimnamespace { 685239310Sdimstruct LiveRegUnit { 686239310Sdim unsigned RegUnit; 687239310Sdim unsigned Cycle; 688239310Sdim const MachineInstr *MI; 689239310Sdim unsigned Op; 690239310Sdim 691239310Sdim unsigned getSparseSetIndex() const { return RegUnit; } 692239310Sdim 693239310Sdim LiveRegUnit(unsigned RU) : RegUnit(RU), Cycle(0), MI(0), Op(0) {} 694239310Sdim}; 695239310Sdim} 696239310Sdim 697239310Sdim// Identify physreg dependencies for UseMI, and update the live regunit 698239310Sdim// tracking set when scanning instructions downwards. 699239310Sdimstatic void updatePhysDepsDownwards(const MachineInstr *UseMI, 700239310Sdim SmallVectorImpl<DataDep> &Deps, 701239310Sdim SparseSet<LiveRegUnit> &RegUnits, 702239310Sdim const TargetRegisterInfo *TRI) { 703239310Sdim SmallVector<unsigned, 8> Kills; 704239310Sdim SmallVector<unsigned, 8> LiveDefOps; 705239310Sdim 706239310Sdim for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { 707239310Sdim if (!MO->isReg()) 708239310Sdim continue; 709239310Sdim unsigned Reg = MO->getReg(); 710239310Sdim if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 711239310Sdim continue; 712239310Sdim // Track live defs and kills for updating RegUnits. 713239310Sdim if (MO->isDef()) { 714239310Sdim if (MO->isDead()) 715239310Sdim Kills.push_back(Reg); 716239310Sdim else 717239310Sdim LiveDefOps.push_back(MO.getOperandNo()); 718239310Sdim } else if (MO->isKill()) 719239310Sdim Kills.push_back(Reg); 720239310Sdim // Identify dependencies. 721239310Sdim if (!MO->readsReg()) 722239310Sdim continue; 723239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 724239310Sdim SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 725239310Sdim if (I == RegUnits.end()) 726239310Sdim continue; 727239310Sdim Deps.push_back(DataDep(I->MI, I->Op, MO.getOperandNo())); 728239310Sdim break; 729239310Sdim } 730239310Sdim } 731239310Sdim 732239310Sdim // Update RegUnits to reflect live registers after UseMI. 733239310Sdim // First kills. 734239310Sdim for (unsigned i = 0, e = Kills.size(); i != e; ++i) 735239310Sdim for (MCRegUnitIterator Units(Kills[i], TRI); Units.isValid(); ++Units) 736239310Sdim RegUnits.erase(*Units); 737239310Sdim 738239310Sdim // Second, live defs. 739239310Sdim for (unsigned i = 0, e = LiveDefOps.size(); i != e; ++i) { 740239310Sdim unsigned DefOp = LiveDefOps[i]; 741239310Sdim for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI); 742239310Sdim Units.isValid(); ++Units) { 743239310Sdim LiveRegUnit &LRU = RegUnits[*Units]; 744239310Sdim LRU.MI = UseMI; 745239310Sdim LRU.Op = DefOp; 746239310Sdim } 747239310Sdim } 748239310Sdim} 749239310Sdim 750239310Sdim/// The length of the critical path through a trace is the maximum of two path 751239310Sdim/// lengths: 752239310Sdim/// 753239310Sdim/// 1. The maximum height+depth over all instructions in the trace center block. 754239310Sdim/// 755239310Sdim/// 2. The longest cross-block dependency chain. For small blocks, it is 756239310Sdim/// possible that the critical path through the trace doesn't include any 757239310Sdim/// instructions in the block. 758239310Sdim/// 759239310Sdim/// This function computes the second number from the live-in list of the 760239310Sdim/// center block. 761239310Sdimunsigned MachineTraceMetrics::Ensemble:: 762239310SdimcomputeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { 763239310Sdim assert(TBI.HasValidInstrDepths && "Missing depth info"); 764239310Sdim assert(TBI.HasValidInstrHeights && "Missing height info"); 765239310Sdim unsigned MaxLen = 0; 766239310Sdim for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 767239310Sdim const LiveInReg &LIR = TBI.LiveIns[i]; 768239310Sdim if (!TargetRegisterInfo::isVirtualRegister(LIR.Reg)) 769239310Sdim continue; 770239310Sdim const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 771239310Sdim // Ignore dependencies outside the current trace. 772239310Sdim const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()]; 773249423Sdim if (!DefTBI.isUsefulDominator(TBI)) 774239310Sdim continue; 775239310Sdim unsigned Len = LIR.Height + Cycles[DefMI].Depth; 776239310Sdim MaxLen = std::max(MaxLen, Len); 777239310Sdim } 778239310Sdim return MaxLen; 779239310Sdim} 780239310Sdim 781239310Sdim/// Compute instruction depths for all instructions above or in MBB in its 782239310Sdim/// trace. This assumes that the trace through MBB has already been computed. 783239310Sdimvoid MachineTraceMetrics::Ensemble:: 784239310SdimcomputeInstrDepths(const MachineBasicBlock *MBB) { 785239310Sdim // The top of the trace may already be computed, and HasValidInstrDepths 786239310Sdim // implies Head->HasValidInstrDepths, so we only need to start from the first 787239310Sdim // block in the trace that needs to be recomputed. 788239310Sdim SmallVector<const MachineBasicBlock*, 8> Stack; 789239310Sdim do { 790239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 791239310Sdim assert(TBI.hasValidDepth() && "Incomplete trace"); 792239310Sdim if (TBI.HasValidInstrDepths) 793239310Sdim break; 794239310Sdim Stack.push_back(MBB); 795239310Sdim MBB = TBI.Pred; 796239310Sdim } while (MBB); 797239310Sdim 798239310Sdim // FIXME: If MBB is non-null at this point, it is the last pre-computed block 799239310Sdim // in the trace. We should track any live-out physregs that were defined in 800239310Sdim // the trace. This is quite rare in SSA form, typically created by CSE 801239310Sdim // hoisting a compare. 802239310Sdim SparseSet<LiveRegUnit> RegUnits; 803239310Sdim RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 804239310Sdim 805239310Sdim // Go through trace blocks in top-down order, stopping after the center block. 806239310Sdim SmallVector<DataDep, 8> Deps; 807239310Sdim while (!Stack.empty()) { 808239310Sdim MBB = Stack.pop_back_val(); 809249423Sdim DEBUG(dbgs() << "\nDepths for BB#" << MBB->getNumber() << ":\n"); 810239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 811239310Sdim TBI.HasValidInstrDepths = true; 812239310Sdim TBI.CriticalPath = 0; 813239310Sdim 814249423Sdim // Print out resource depths here as well. 815249423Sdim DEBUG({ 816249423Sdim dbgs() << format("%7u Instructions\n", TBI.InstrDepth); 817249423Sdim ArrayRef<unsigned> PRDepths = getProcResourceDepths(MBB->getNumber()); 818249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 819249423Sdim if (PRDepths[K]) { 820249423Sdim unsigned Factor = MTM.SchedModel.getResourceFactor(K); 821249423Sdim dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K])) 822249423Sdim << MTM.SchedModel.getProcResource(K)->Name << " (" 823249423Sdim << PRDepths[K]/Factor << " ops x" << Factor << ")\n"; 824249423Sdim } 825249423Sdim }); 826249423Sdim 827239310Sdim // Also compute the critical path length through MBB when possible. 828239310Sdim if (TBI.HasValidInstrHeights) 829239310Sdim TBI.CriticalPath = computeCrossBlockCriticalPath(TBI); 830239310Sdim 831239310Sdim for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 832239310Sdim I != E; ++I) { 833239310Sdim const MachineInstr *UseMI = I; 834239310Sdim 835239310Sdim // Collect all data dependencies. 836239310Sdim Deps.clear(); 837239310Sdim if (UseMI->isPHI()) 838239310Sdim getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI); 839239310Sdim else if (getDataDeps(UseMI, Deps, MTM.MRI)) 840239310Sdim updatePhysDepsDownwards(UseMI, Deps, RegUnits, MTM.TRI); 841239310Sdim 842239310Sdim // Filter and process dependencies, computing the earliest issue cycle. 843239310Sdim unsigned Cycle = 0; 844239310Sdim for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 845239310Sdim const DataDep &Dep = Deps[i]; 846239310Sdim const TraceBlockInfo&DepTBI = 847239310Sdim BlockInfo[Dep.DefMI->getParent()->getNumber()]; 848239310Sdim // Ignore dependencies from outside the current trace. 849249423Sdim if (!DepTBI.isUsefulDominator(TBI)) 850239310Sdim continue; 851239310Sdim assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency"); 852239310Sdim unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth; 853239310Sdim // Add latency if DefMI is a real instruction. Transients get latency 0. 854239310Sdim if (!Dep.DefMI->isTransient()) 855243830Sdim DepCycle += MTM.SchedModel 856263508Sdim .computeOperandLatency(Dep.DefMI, Dep.DefOp, UseMI, Dep.UseOp); 857239310Sdim Cycle = std::max(Cycle, DepCycle); 858239310Sdim } 859239310Sdim // Remember the instruction depth. 860239310Sdim InstrCycles &MICycles = Cycles[UseMI]; 861239310Sdim MICycles.Depth = Cycle; 862239310Sdim 863239310Sdim if (!TBI.HasValidInstrHeights) { 864239310Sdim DEBUG(dbgs() << Cycle << '\t' << *UseMI); 865239310Sdim continue; 866239310Sdim } 867239310Sdim // Update critical path length. 868239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height); 869239310Sdim DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *UseMI); 870239310Sdim } 871239310Sdim } 872239310Sdim} 873239310Sdim 874239310Sdim// Identify physreg dependencies for MI when scanning instructions upwards. 875239310Sdim// Return the issue height of MI after considering any live regunits. 876239310Sdim// Height is the issue height computed from virtual register dependencies alone. 877239310Sdimstatic unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height, 878239310Sdim SparseSet<LiveRegUnit> &RegUnits, 879243830Sdim const TargetSchedModel &SchedModel, 880239310Sdim const TargetInstrInfo *TII, 881239310Sdim const TargetRegisterInfo *TRI) { 882239310Sdim SmallVector<unsigned, 8> ReadOps; 883239310Sdim for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 884239310Sdim if (!MO->isReg()) 885239310Sdim continue; 886239310Sdim unsigned Reg = MO->getReg(); 887239310Sdim if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 888239310Sdim continue; 889239310Sdim if (MO->readsReg()) 890239310Sdim ReadOps.push_back(MO.getOperandNo()); 891239310Sdim if (!MO->isDef()) 892239310Sdim continue; 893239310Sdim // This is a def of Reg. Remove corresponding entries from RegUnits, and 894239310Sdim // update MI Height to consider the physreg dependencies. 895239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 896239310Sdim SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 897239310Sdim if (I == RegUnits.end()) 898239310Sdim continue; 899239310Sdim unsigned DepHeight = I->Cycle; 900239310Sdim if (!MI->isTransient()) { 901239310Sdim // We may not know the UseMI of this dependency, if it came from the 902243830Sdim // live-in list. SchedModel can handle a NULL UseMI. 903243830Sdim DepHeight += SchedModel 904263508Sdim .computeOperandLatency(MI, MO.getOperandNo(), I->MI, I->Op); 905239310Sdim } 906239310Sdim Height = std::max(Height, DepHeight); 907239310Sdim // This regunit is dead above MI. 908239310Sdim RegUnits.erase(I); 909239310Sdim } 910239310Sdim } 911239310Sdim 912239310Sdim // Now we know the height of MI. Update any regunits read. 913239310Sdim for (unsigned i = 0, e = ReadOps.size(); i != e; ++i) { 914239310Sdim unsigned Reg = MI->getOperand(ReadOps[i]).getReg(); 915239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 916239310Sdim LiveRegUnit &LRU = RegUnits[*Units]; 917239310Sdim // Set the height to the highest reader of the unit. 918239310Sdim if (LRU.Cycle <= Height && LRU.MI != MI) { 919239310Sdim LRU.Cycle = Height; 920239310Sdim LRU.MI = MI; 921239310Sdim LRU.Op = ReadOps[i]; 922239310Sdim } 923239310Sdim } 924239310Sdim } 925239310Sdim 926239310Sdim return Height; 927239310Sdim} 928239310Sdim 929239310Sdim 930239310Sdimtypedef DenseMap<const MachineInstr *, unsigned> MIHeightMap; 931239310Sdim 932239310Sdim// Push the height of DefMI upwards if required to match UseMI. 933239310Sdim// Return true if this is the first time DefMI was seen. 934239310Sdimstatic bool pushDepHeight(const DataDep &Dep, 935239310Sdim const MachineInstr *UseMI, unsigned UseHeight, 936239310Sdim MIHeightMap &Heights, 937243830Sdim const TargetSchedModel &SchedModel, 938239310Sdim const TargetInstrInfo *TII) { 939239310Sdim // Adjust height by Dep.DefMI latency. 940239310Sdim if (!Dep.DefMI->isTransient()) 941243830Sdim UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, 942263508Sdim UseMI, Dep.UseOp); 943239310Sdim 944239310Sdim // Update Heights[DefMI] to be the maximum height seen. 945239310Sdim MIHeightMap::iterator I; 946239310Sdim bool New; 947239310Sdim tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight)); 948239310Sdim if (New) 949239310Sdim return true; 950239310Sdim 951239310Sdim // DefMI has been pushed before. Give it the max height. 952239310Sdim if (I->second < UseHeight) 953239310Sdim I->second = UseHeight; 954239310Sdim return false; 955239310Sdim} 956239310Sdim 957243830Sdim/// Assuming that the virtual register defined by DefMI:DefOp was used by 958243830Sdim/// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop 959243830Sdim/// when reaching the block that contains DefMI. 960239310Sdimvoid MachineTraceMetrics::Ensemble:: 961243830SdimaddLiveIns(const MachineInstr *DefMI, unsigned DefOp, 962239310Sdim ArrayRef<const MachineBasicBlock*> Trace) { 963239310Sdim assert(!Trace.empty() && "Trace should contain at least one block"); 964243830Sdim unsigned Reg = DefMI->getOperand(DefOp).getReg(); 965239310Sdim assert(TargetRegisterInfo::isVirtualRegister(Reg)); 966239310Sdim const MachineBasicBlock *DefMBB = DefMI->getParent(); 967239310Sdim 968239310Sdim // Reg is live-in to all blocks in Trace that follow DefMBB. 969239310Sdim for (unsigned i = Trace.size(); i; --i) { 970239310Sdim const MachineBasicBlock *MBB = Trace[i-1]; 971239310Sdim if (MBB == DefMBB) 972239310Sdim return; 973239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 974239310Sdim // Just add the register. The height will be updated later. 975239310Sdim TBI.LiveIns.push_back(Reg); 976239310Sdim } 977239310Sdim} 978239310Sdim 979239310Sdim/// Compute instruction heights in the trace through MBB. This updates MBB and 980239310Sdim/// the blocks below it in the trace. It is assumed that the trace has already 981239310Sdim/// been computed. 982239310Sdimvoid MachineTraceMetrics::Ensemble:: 983239310SdimcomputeInstrHeights(const MachineBasicBlock *MBB) { 984239310Sdim // The bottom of the trace may already be computed. 985239310Sdim // Find the blocks that need updating. 986239310Sdim SmallVector<const MachineBasicBlock*, 8> Stack; 987239310Sdim do { 988239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 989239310Sdim assert(TBI.hasValidHeight() && "Incomplete trace"); 990239310Sdim if (TBI.HasValidInstrHeights) 991239310Sdim break; 992239310Sdim Stack.push_back(MBB); 993239310Sdim TBI.LiveIns.clear(); 994239310Sdim MBB = TBI.Succ; 995239310Sdim } while (MBB); 996239310Sdim 997239310Sdim // As we move upwards in the trace, keep track of instructions that are 998239310Sdim // required by deeper trace instructions. Map MI -> height required so far. 999239310Sdim MIHeightMap Heights; 1000239310Sdim 1001239310Sdim // For physregs, the def isn't known when we see the use. 1002239310Sdim // Instead, keep track of the highest use of each regunit. 1003239310Sdim SparseSet<LiveRegUnit> RegUnits; 1004239310Sdim RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 1005239310Sdim 1006239310Sdim // If the bottom of the trace was already precomputed, initialize heights 1007239310Sdim // from its live-in list. 1008239310Sdim // MBB is the highest precomputed block in the trace. 1009239310Sdim if (MBB) { 1010239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1011239310Sdim for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 1012239310Sdim LiveInReg LI = TBI.LiveIns[i]; 1013239310Sdim if (TargetRegisterInfo::isVirtualRegister(LI.Reg)) { 1014239310Sdim // For virtual registers, the def latency is included. 1015239310Sdim unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; 1016239310Sdim if (Height < LI.Height) 1017239310Sdim Height = LI.Height; 1018239310Sdim } else { 1019239310Sdim // For register units, the def latency is not included because we don't 1020239310Sdim // know the def yet. 1021239310Sdim RegUnits[LI.Reg].Cycle = LI.Height; 1022239310Sdim } 1023239310Sdim } 1024239310Sdim } 1025239310Sdim 1026239310Sdim // Go through the trace blocks in bottom-up order. 1027239310Sdim SmallVector<DataDep, 8> Deps; 1028239310Sdim for (;!Stack.empty(); Stack.pop_back()) { 1029239310Sdim MBB = Stack.back(); 1030239310Sdim DEBUG(dbgs() << "Heights for BB#" << MBB->getNumber() << ":\n"); 1031239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1032239310Sdim TBI.HasValidInstrHeights = true; 1033239310Sdim TBI.CriticalPath = 0; 1034239310Sdim 1035249423Sdim DEBUG({ 1036249423Sdim dbgs() << format("%7u Instructions\n", TBI.InstrHeight); 1037249423Sdim ArrayRef<unsigned> PRHeights = getProcResourceHeights(MBB->getNumber()); 1038249423Sdim for (unsigned K = 0; K != PRHeights.size(); ++K) 1039249423Sdim if (PRHeights[K]) { 1040249423Sdim unsigned Factor = MTM.SchedModel.getResourceFactor(K); 1041249423Sdim dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K])) 1042249423Sdim << MTM.SchedModel.getProcResource(K)->Name << " (" 1043249423Sdim << PRHeights[K]/Factor << " ops x" << Factor << ")\n"; 1044249423Sdim } 1045249423Sdim }); 1046249423Sdim 1047239310Sdim // Get dependencies from PHIs in the trace successor. 1048239310Sdim const MachineBasicBlock *Succ = TBI.Succ; 1049239310Sdim // If MBB is the last block in the trace, and it has a back-edge to the 1050239310Sdim // loop header, get loop-carried dependencies from PHIs in the header. For 1051239310Sdim // that purpose, pretend that all the loop header PHIs have height 0. 1052239310Sdim if (!Succ) 1053239310Sdim if (const MachineLoop *Loop = getLoopFor(MBB)) 1054239310Sdim if (MBB->isSuccessor(Loop->getHeader())) 1055239310Sdim Succ = Loop->getHeader(); 1056239310Sdim 1057239310Sdim if (Succ) { 1058239310Sdim for (MachineBasicBlock::const_iterator I = Succ->begin(), E = Succ->end(); 1059239310Sdim I != E && I->isPHI(); ++I) { 1060239310Sdim const MachineInstr *PHI = I; 1061239310Sdim Deps.clear(); 1062239310Sdim getPHIDeps(PHI, Deps, MBB, MTM.MRI); 1063239310Sdim if (!Deps.empty()) { 1064239310Sdim // Loop header PHI heights are all 0. 1065239310Sdim unsigned Height = TBI.Succ ? Cycles.lookup(PHI).Height : 0; 1066239310Sdim DEBUG(dbgs() << "pred\t" << Height << '\t' << *PHI); 1067239310Sdim if (pushDepHeight(Deps.front(), PHI, Height, 1068243830Sdim Heights, MTM.SchedModel, MTM.TII)) 1069243830Sdim addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack); 1070239310Sdim } 1071239310Sdim } 1072239310Sdim } 1073239310Sdim 1074239310Sdim // Go through the block backwards. 1075239310Sdim for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin(); 1076239310Sdim BI != BB;) { 1077239310Sdim const MachineInstr *MI = --BI; 1078239310Sdim 1079239310Sdim // Find the MI height as determined by virtual register uses in the 1080239310Sdim // trace below. 1081239310Sdim unsigned Cycle = 0; 1082239310Sdim MIHeightMap::iterator HeightI = Heights.find(MI); 1083239310Sdim if (HeightI != Heights.end()) { 1084239310Sdim Cycle = HeightI->second; 1085239310Sdim // We won't be seeing any more MI uses. 1086239310Sdim Heights.erase(HeightI); 1087239310Sdim } 1088239310Sdim 1089239310Sdim // Don't process PHI deps. They depend on the specific predecessor, and 1090239310Sdim // we'll get them when visiting the predecessor. 1091239310Sdim Deps.clear(); 1092239310Sdim bool HasPhysRegs = !MI->isPHI() && getDataDeps(MI, Deps, MTM.MRI); 1093239310Sdim 1094239310Sdim // There may also be regunit dependencies to include in the height. 1095239310Sdim if (HasPhysRegs) 1096239310Sdim Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, 1097243830Sdim MTM.SchedModel, MTM.TII, MTM.TRI); 1098239310Sdim 1099239310Sdim // Update the required height of any virtual registers read by MI. 1100239310Sdim for (unsigned i = 0, e = Deps.size(); i != e; ++i) 1101243830Sdim if (pushDepHeight(Deps[i], MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) 1102243830Sdim addLiveIns(Deps[i].DefMI, Deps[i].DefOp, Stack); 1103239310Sdim 1104239310Sdim InstrCycles &MICycles = Cycles[MI]; 1105239310Sdim MICycles.Height = Cycle; 1106239310Sdim if (!TBI.HasValidInstrDepths) { 1107239310Sdim DEBUG(dbgs() << Cycle << '\t' << *MI); 1108239310Sdim continue; 1109239310Sdim } 1110239310Sdim // Update critical path length. 1111239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth); 1112239310Sdim DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *MI); 1113239310Sdim } 1114239310Sdim 1115239310Sdim // Update virtual live-in heights. They were added by addLiveIns() with a 0 1116239310Sdim // height because the final height isn't known until now. 1117239310Sdim DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:"); 1118239310Sdim for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 1119239310Sdim LiveInReg &LIR = TBI.LiveIns[i]; 1120239310Sdim const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 1121239310Sdim LIR.Height = Heights.lookup(DefMI); 1122239310Sdim DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height); 1123239310Sdim } 1124239310Sdim 1125239310Sdim // Transfer the live regunits to the live-in list. 1126239310Sdim for (SparseSet<LiveRegUnit>::const_iterator 1127239310Sdim RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) { 1128239310Sdim TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle)); 1129239310Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(RI->RegUnit, MTM.TRI) 1130239310Sdim << '@' << RI->Cycle); 1131239310Sdim } 1132239310Sdim DEBUG(dbgs() << '\n'); 1133239310Sdim 1134239310Sdim if (!TBI.HasValidInstrDepths) 1135239310Sdim continue; 1136239310Sdim // Add live-ins to the critical path length. 1137239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, 1138239310Sdim computeCrossBlockCriticalPath(TBI)); 1139239310Sdim DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n'); 1140239310Sdim } 1141239310Sdim} 1142239310Sdim 1143239310SdimMachineTraceMetrics::Trace 1144239310SdimMachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { 1145239310Sdim // FIXME: Check cache tags, recompute as needed. 1146239310Sdim computeTrace(MBB); 1147239310Sdim computeInstrDepths(MBB); 1148239310Sdim computeInstrHeights(MBB); 1149239310Sdim return Trace(*this, BlockInfo[MBB->getNumber()]); 1150239310Sdim} 1151239310Sdim 1152239310Sdimunsigned 1153239310SdimMachineTraceMetrics::Trace::getInstrSlack(const MachineInstr *MI) const { 1154239310Sdim assert(MI && "Not an instruction."); 1155239310Sdim assert(getBlockNum() == unsigned(MI->getParent()->getNumber()) && 1156239310Sdim "MI must be in the trace center block"); 1157239310Sdim InstrCycles Cyc = getInstrCycles(MI); 1158239310Sdim return getCriticalPath() - (Cyc.Depth + Cyc.Height); 1159239310Sdim} 1160239310Sdim 1161239310Sdimunsigned 1162239310SdimMachineTraceMetrics::Trace::getPHIDepth(const MachineInstr *PHI) const { 1163239310Sdim const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum()); 1164239310Sdim SmallVector<DataDep, 1> Deps; 1165239310Sdim getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI); 1166239310Sdim assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor"); 1167239310Sdim DataDep &Dep = Deps.front(); 1168239310Sdim unsigned DepCycle = getInstrCycles(Dep.DefMI).Depth; 1169239310Sdim // Add latency if DefMI is a real instruction. Transients get latency 0. 1170239310Sdim if (!Dep.DefMI->isTransient()) 1171243830Sdim DepCycle += TE.MTM.SchedModel 1172263508Sdim .computeOperandLatency(Dep.DefMI, Dep.DefOp, PHI, Dep.UseOp); 1173239310Sdim return DepCycle; 1174239310Sdim} 1175239310Sdim 1176239310Sdimunsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { 1177249423Sdim // Find the limiting processor resource. 1178249423Sdim // Numbers have been pre-scaled to be comparable. 1179249423Sdim unsigned PRMax = 0; 1180249423Sdim ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1181249423Sdim if (Bottom) { 1182249423Sdim ArrayRef<unsigned> PRCycles = TE.MTM.getProcResourceCycles(getBlockNum()); 1183249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 1184249423Sdim PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]); 1185249423Sdim } else { 1186249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 1187249423Sdim PRMax = std::max(PRMax, PRDepths[K]); 1188249423Sdim } 1189249423Sdim // Convert to cycle count. 1190249423Sdim PRMax = TE.MTM.getCycles(PRMax); 1191249423Sdim 1192239310Sdim unsigned Instrs = TBI.InstrDepth; 1193239310Sdim if (Bottom) 1194239310Sdim Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; 1195243830Sdim if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1196243830Sdim Instrs /= IW; 1197239310Sdim // Assume issue width 1 without a schedule model. 1198249423Sdim return std::max(Instrs, PRMax); 1199239310Sdim} 1200239310Sdim 1201251662Sdim 1202239310Sdimunsigned MachineTraceMetrics::Trace:: 1203251662SdimgetResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks, 1204251662Sdim ArrayRef<const MCSchedClassDesc*> ExtraInstrs) const { 1205249423Sdim // Add up resources above and below the center block. 1206249423Sdim ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1207249423Sdim ArrayRef<unsigned> PRHeights = TE.getProcResourceHeights(getBlockNum()); 1208249423Sdim unsigned PRMax = 0; 1209249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) { 1210249423Sdim unsigned PRCycles = PRDepths[K] + PRHeights[K]; 1211249423Sdim for (unsigned I = 0; I != Extrablocks.size(); ++I) 1212249423Sdim PRCycles += TE.MTM.getProcResourceCycles(Extrablocks[I]->getNumber())[K]; 1213251662Sdim for (unsigned I = 0; I != ExtraInstrs.size(); ++I) { 1214251662Sdim const MCSchedClassDesc* SC = ExtraInstrs[I]; 1215251662Sdim if (!SC->isValid()) 1216251662Sdim continue; 1217251662Sdim for (TargetSchedModel::ProcResIter 1218251662Sdim PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), 1219251662Sdim PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 1220251662Sdim if (PI->ProcResourceIdx != K) 1221251662Sdim continue; 1222251662Sdim PRCycles += (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(K)); 1223251662Sdim } 1224251662Sdim } 1225249423Sdim PRMax = std::max(PRMax, PRCycles); 1226249423Sdim } 1227249423Sdim // Convert to cycle count. 1228249423Sdim PRMax = TE.MTM.getCycles(PRMax); 1229249423Sdim 1230239310Sdim unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; 1231239310Sdim for (unsigned i = 0, e = Extrablocks.size(); i != e; ++i) 1232239310Sdim Instrs += TE.MTM.getResources(Extrablocks[i])->InstrCount; 1233243830Sdim if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1234243830Sdim Instrs /= IW; 1235239310Sdim // Assume issue width 1 without a schedule model. 1236249423Sdim return std::max(Instrs, PRMax); 1237239310Sdim} 1238239310Sdim 1239239310Sdimvoid MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { 1240239310Sdim OS << getName() << " ensemble:\n"; 1241239310Sdim for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 1242239310Sdim OS << " BB#" << i << '\t'; 1243239310Sdim BlockInfo[i].print(OS); 1244239310Sdim OS << '\n'; 1245239310Sdim } 1246239310Sdim} 1247239310Sdim 1248239310Sdimvoid MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { 1249239310Sdim if (hasValidDepth()) { 1250239310Sdim OS << "depth=" << InstrDepth; 1251239310Sdim if (Pred) 1252239310Sdim OS << " pred=BB#" << Pred->getNumber(); 1253239310Sdim else 1254239310Sdim OS << " pred=null"; 1255239310Sdim OS << " head=BB#" << Head; 1256239310Sdim if (HasValidInstrDepths) 1257239310Sdim OS << " +instrs"; 1258239310Sdim } else 1259239310Sdim OS << "depth invalid"; 1260239310Sdim OS << ", "; 1261239310Sdim if (hasValidHeight()) { 1262239310Sdim OS << "height=" << InstrHeight; 1263239310Sdim if (Succ) 1264239310Sdim OS << " succ=BB#" << Succ->getNumber(); 1265239310Sdim else 1266239310Sdim OS << " succ=null"; 1267239310Sdim OS << " tail=BB#" << Tail; 1268239310Sdim if (HasValidInstrHeights) 1269239310Sdim OS << " +instrs"; 1270239310Sdim } else 1271239310Sdim OS << "height invalid"; 1272239310Sdim if (HasValidInstrDepths && HasValidInstrHeights) 1273239310Sdim OS << ", crit=" << CriticalPath; 1274239310Sdim} 1275239310Sdim 1276239310Sdimvoid MachineTraceMetrics::Trace::print(raw_ostream &OS) const { 1277239310Sdim unsigned MBBNum = &TBI - &TE.BlockInfo[0]; 1278239310Sdim 1279239310Sdim OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum 1280239310Sdim << " --> BB#" << TBI.Tail << ':'; 1281239310Sdim if (TBI.hasValidHeight() && TBI.hasValidDepth()) 1282239310Sdim OS << ' ' << getInstrCount() << " instrs."; 1283239310Sdim if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights) 1284239310Sdim OS << ' ' << TBI.CriticalPath << " cycles."; 1285239310Sdim 1286239310Sdim const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; 1287239310Sdim OS << "\nBB#" << MBBNum; 1288239310Sdim while (Block->hasValidDepth() && Block->Pred) { 1289239310Sdim unsigned Num = Block->Pred->getNumber(); 1290239310Sdim OS << " <- BB#" << Num; 1291239310Sdim Block = &TE.BlockInfo[Num]; 1292239310Sdim } 1293239310Sdim 1294239310Sdim Block = &TBI; 1295239310Sdim OS << "\n "; 1296239310Sdim while (Block->hasValidHeight() && Block->Succ) { 1297239310Sdim unsigned Num = Block->Succ->getNumber(); 1298239310Sdim OS << " -> BB#" << Num; 1299239310Sdim Block = &TE.BlockInfo[Num]; 1300239310Sdim } 1301239310Sdim OS << '\n'; 1302239310Sdim} 1303