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 10249423Sdim#include "llvm/CodeGen/MachineTraceMetrics.h" 11249423Sdim#include "llvm/ADT/PostOrderIterator.h" 12249423Sdim#include "llvm/ADT/SparseSet.h" 13239310Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 14239310Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 15239310Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 16239310Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 17239310Sdim#include "llvm/CodeGen/Passes.h" 18243830Sdim#include "llvm/MC/MCSubtargetInfo.h" 19249423Sdim#include "llvm/Support/Debug.h" 20249423Sdim#include "llvm/Support/Format.h" 21249423Sdim#include "llvm/Support/raw_ostream.h" 22239310Sdim#include "llvm/Target/TargetInstrInfo.h" 23239310Sdim#include "llvm/Target/TargetRegisterInfo.h" 24243830Sdim#include "llvm/Target/TargetSubtargetInfo.h" 25239310Sdim 26239310Sdimusing namespace llvm; 27239310Sdim 28276479Sdim#define DEBUG_TYPE "machine-trace-metrics" 29276479Sdim 30239310Sdimchar MachineTraceMetrics::ID = 0; 31239310Sdimchar &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; 32239310Sdim 33239310SdimINITIALIZE_PASS_BEGIN(MachineTraceMetrics, 34239310Sdim "machine-trace-metrics", "Machine Trace Metrics", false, true) 35239310SdimINITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 36239310SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 37239310SdimINITIALIZE_PASS_END(MachineTraceMetrics, 38239310Sdim "machine-trace-metrics", "Machine Trace Metrics", false, true) 39239310Sdim 40239310SdimMachineTraceMetrics::MachineTraceMetrics() 41276479Sdim : MachineFunctionPass(ID), MF(nullptr), TII(nullptr), TRI(nullptr), 42276479Sdim MRI(nullptr), Loops(nullptr) { 43276479Sdim std::fill(std::begin(Ensembles), std::end(Ensembles), nullptr); 44239310Sdim} 45239310Sdim 46239310Sdimvoid MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { 47239310Sdim AU.setPreservesAll(); 48239310Sdim AU.addRequired<MachineBranchProbabilityInfo>(); 49239310Sdim AU.addRequired<MachineLoopInfo>(); 50239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 51239310Sdim} 52239310Sdim 53239310Sdimbool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { 54239310Sdim MF = &Func; 55288943Sdim const TargetSubtargetInfo &ST = MF->getSubtarget(); 56288943Sdim TII = ST.getInstrInfo(); 57288943Sdim TRI = ST.getRegisterInfo(); 58239310Sdim MRI = &MF->getRegInfo(); 59239310Sdim Loops = &getAnalysis<MachineLoopInfo>(); 60280031Sdim SchedModel.init(ST.getSchedModel(), &ST, TII); 61239310Sdim BlockInfo.resize(MF->getNumBlockIDs()); 62249423Sdim ProcResourceCycles.resize(MF->getNumBlockIDs() * 63249423Sdim SchedModel.getNumProcResourceKinds()); 64239310Sdim return false; 65239310Sdim} 66239310Sdim 67239310Sdimvoid MachineTraceMetrics::releaseMemory() { 68276479Sdim MF = nullptr; 69239310Sdim BlockInfo.clear(); 70239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) { 71239310Sdim delete Ensembles[i]; 72276479Sdim Ensembles[i] = nullptr; 73239310Sdim } 74239310Sdim} 75239310Sdim 76239310Sdim//===----------------------------------------------------------------------===// 77239310Sdim// Fixed block information 78239310Sdim//===----------------------------------------------------------------------===// 79239310Sdim// 80239310Sdim// The number of instructions in a basic block and the CPU resources used by 81239310Sdim// those instructions don't depend on any given trace strategy. 82239310Sdim 83239310Sdim/// Compute the resource usage in basic block MBB. 84239310Sdimconst MachineTraceMetrics::FixedBlockInfo* 85239310SdimMachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { 86239310Sdim assert(MBB && "No basic block"); 87239310Sdim FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; 88239310Sdim if (FBI->hasResources()) 89239310Sdim return FBI; 90239310Sdim 91239310Sdim // Compute resource usage in the block. 92239310Sdim FBI->HasCalls = false; 93239310Sdim unsigned InstrCount = 0; 94249423Sdim 95249423Sdim // Add up per-processor resource cycles as well. 96249423Sdim unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 97249423Sdim SmallVector<unsigned, 32> PRCycles(PRKinds); 98249423Sdim 99276479Sdim for (const auto &MI : *MBB) { 100276479Sdim if (MI.isTransient()) 101239310Sdim continue; 102239310Sdim ++InstrCount; 103276479Sdim if (MI.isCall()) 104239310Sdim FBI->HasCalls = true; 105249423Sdim 106249423Sdim // Count processor resources used. 107249423Sdim if (!SchedModel.hasInstrSchedModel()) 108249423Sdim continue; 109276479Sdim const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(&MI); 110249423Sdim if (!SC->isValid()) 111249423Sdim continue; 112249423Sdim 113249423Sdim for (TargetSchedModel::ProcResIter 114249423Sdim PI = SchedModel.getWriteProcResBegin(SC), 115249423Sdim PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { 116249423Sdim assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind"); 117249423Sdim PRCycles[PI->ProcResourceIdx] += PI->Cycles; 118249423Sdim } 119239310Sdim } 120239310Sdim FBI->InstrCount = InstrCount; 121249423Sdim 122249423Sdim // Scale the resource cycles so they are comparable. 123249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 124249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 125249423Sdim ProcResourceCycles[PROffset + K] = 126249423Sdim PRCycles[K] * SchedModel.getResourceFactor(K); 127249423Sdim 128239310Sdim return FBI; 129239310Sdim} 130239310Sdim 131249423SdimArrayRef<unsigned> 132249423SdimMachineTraceMetrics::getProcResourceCycles(unsigned MBBNum) const { 133249423Sdim assert(BlockInfo[MBBNum].hasResources() && 134249423Sdim "getResources() must be called before getProcResourceCycles()"); 135249423Sdim unsigned PRKinds = SchedModel.getNumProcResourceKinds(); 136249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size()); 137280031Sdim return makeArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, PRKinds); 138249423Sdim} 139249423Sdim 140249423Sdim 141239310Sdim//===----------------------------------------------------------------------===// 142239310Sdim// Ensemble utility functions 143239310Sdim//===----------------------------------------------------------------------===// 144239310Sdim 145239310SdimMachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) 146239310Sdim : MTM(*ct) { 147239310Sdim BlockInfo.resize(MTM.BlockInfo.size()); 148249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 149249423Sdim ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds); 150249423Sdim ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds); 151239310Sdim} 152239310Sdim 153239310Sdim// Virtual destructor serves as an anchor. 154239310SdimMachineTraceMetrics::Ensemble::~Ensemble() {} 155239310Sdim 156239310Sdimconst MachineLoop* 157239310SdimMachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { 158239310Sdim return MTM.Loops->getLoopFor(MBB); 159239310Sdim} 160239310Sdim 161239310Sdim// Update resource-related information in the TraceBlockInfo for MBB. 162239310Sdim// Only update resources related to the trace above MBB. 163239310Sdimvoid MachineTraceMetrics::Ensemble:: 164239310SdimcomputeDepthResources(const MachineBasicBlock *MBB) { 165239310Sdim TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 166249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 167249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 168239310Sdim 169239310Sdim // Compute resources from trace above. The top block is simple. 170239310Sdim if (!TBI->Pred) { 171239310Sdim TBI->InstrDepth = 0; 172239310Sdim TBI->Head = MBB->getNumber(); 173249423Sdim std::fill(ProcResourceDepths.begin() + PROffset, 174249423Sdim ProcResourceDepths.begin() + PROffset + PRKinds, 0); 175239310Sdim return; 176239310Sdim } 177239310Sdim 178239310Sdim // Compute from the block above. A post-order traversal ensures the 179239310Sdim // predecessor is always computed first. 180249423Sdim unsigned PredNum = TBI->Pred->getNumber(); 181249423Sdim TraceBlockInfo *PredTBI = &BlockInfo[PredNum]; 182239310Sdim assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); 183239310Sdim const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred); 184239310Sdim TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; 185239310Sdim TBI->Head = PredTBI->Head; 186249423Sdim 187249423Sdim // Compute per-resource depths. 188249423Sdim ArrayRef<unsigned> PredPRDepths = getProcResourceDepths(PredNum); 189249423Sdim ArrayRef<unsigned> PredPRCycles = MTM.getProcResourceCycles(PredNum); 190249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 191249423Sdim ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K]; 192239310Sdim} 193239310Sdim 194239310Sdim// Update resource-related information in the TraceBlockInfo for MBB. 195239310Sdim// Only update resources related to the trace below MBB. 196239310Sdimvoid MachineTraceMetrics::Ensemble:: 197239310SdimcomputeHeightResources(const MachineBasicBlock *MBB) { 198239310Sdim TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 199249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 200249423Sdim unsigned PROffset = MBB->getNumber() * PRKinds; 201239310Sdim 202239310Sdim // Compute resources for the current block. 203239310Sdim TBI->InstrHeight = MTM.getResources(MBB)->InstrCount; 204249423Sdim ArrayRef<unsigned> PRCycles = MTM.getProcResourceCycles(MBB->getNumber()); 205239310Sdim 206239310Sdim // The trace tail is done. 207239310Sdim if (!TBI->Succ) { 208239310Sdim TBI->Tail = MBB->getNumber(); 209249423Sdim std::copy(PRCycles.begin(), PRCycles.end(), 210249423Sdim ProcResourceHeights.begin() + PROffset); 211239310Sdim return; 212239310Sdim } 213239310Sdim 214239310Sdim // Compute from the block below. A post-order traversal ensures the 215239310Sdim // predecessor is always computed first. 216249423Sdim unsigned SuccNum = TBI->Succ->getNumber(); 217249423Sdim TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum]; 218239310Sdim assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); 219239310Sdim TBI->InstrHeight += SuccTBI->InstrHeight; 220239310Sdim TBI->Tail = SuccTBI->Tail; 221249423Sdim 222249423Sdim // Compute per-resource heights. 223249423Sdim ArrayRef<unsigned> SuccPRHeights = getProcResourceHeights(SuccNum); 224249423Sdim for (unsigned K = 0; K != PRKinds; ++K) 225249423Sdim ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K]; 226239310Sdim} 227239310Sdim 228239310Sdim// Check if depth resources for MBB are valid and return the TBI. 229239310Sdim// Return NULL if the resources have been invalidated. 230239310Sdimconst MachineTraceMetrics::TraceBlockInfo* 231239310SdimMachineTraceMetrics::Ensemble:: 232239310SdimgetDepthResources(const MachineBasicBlock *MBB) const { 233239310Sdim const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 234276479Sdim return TBI->hasValidDepth() ? TBI : nullptr; 235239310Sdim} 236239310Sdim 237239310Sdim// Check if height resources for MBB are valid and return the TBI. 238239310Sdim// Return NULL if the resources have been invalidated. 239239310Sdimconst MachineTraceMetrics::TraceBlockInfo* 240239310SdimMachineTraceMetrics::Ensemble:: 241239310SdimgetHeightResources(const MachineBasicBlock *MBB) const { 242239310Sdim const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 243276479Sdim return TBI->hasValidHeight() ? TBI : nullptr; 244239310Sdim} 245239310Sdim 246249423Sdim/// Get an array of processor resource depths for MBB. Indexed by processor 247249423Sdim/// resource kind, this array contains the scaled processor resources consumed 248249423Sdim/// by all blocks preceding MBB in its trace. It does not include instructions 249249423Sdim/// in MBB. 250249423Sdim/// 251249423Sdim/// Compare TraceBlockInfo::InstrDepth. 252249423SdimArrayRef<unsigned> 253249423SdimMachineTraceMetrics::Ensemble:: 254249423SdimgetProcResourceDepths(unsigned MBBNum) const { 255249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 256249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size()); 257280031Sdim return makeArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds); 258249423Sdim} 259249423Sdim 260249423Sdim/// Get an array of processor resource heights for MBB. Indexed by processor 261249423Sdim/// resource kind, this array contains the scaled processor resources consumed 262249423Sdim/// by this block and all blocks following it in its trace. 263249423Sdim/// 264249423Sdim/// Compare TraceBlockInfo::InstrHeight. 265249423SdimArrayRef<unsigned> 266249423SdimMachineTraceMetrics::Ensemble:: 267249423SdimgetProcResourceHeights(unsigned MBBNum) const { 268249423Sdim unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); 269249423Sdim assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size()); 270280031Sdim return makeArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds); 271249423Sdim} 272249423Sdim 273239310Sdim//===----------------------------------------------------------------------===// 274239310Sdim// Trace Selection Strategies 275239310Sdim//===----------------------------------------------------------------------===// 276239310Sdim// 277239310Sdim// A trace selection strategy is implemented as a sub-class of Ensemble. The 278239310Sdim// trace through a block B is computed by two DFS traversals of the CFG 279239310Sdim// starting from B. One upwards, and one downwards. During the upwards DFS, 280239310Sdim// pickTracePred() is called on the post-ordered blocks. During the downwards 281239310Sdim// DFS, pickTraceSucc() is called in a post-order. 282239310Sdim// 283239310Sdim 284239310Sdim// We never allow traces that leave loops, but we do allow traces to enter 285239310Sdim// nested loops. We also never allow traces to contain back-edges. 286239310Sdim// 287239310Sdim// This means that a loop header can never appear above the center block of a 288239310Sdim// trace, except as the trace head. Below the center block, loop exiting edges 289239310Sdim// are banned. 290239310Sdim// 291239310Sdim// Return true if an edge from the From loop to the To loop is leaving a loop. 292239310Sdim// Either of To and From can be null. 293239310Sdimstatic bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { 294239310Sdim return From && !From->contains(To); 295239310Sdim} 296239310Sdim 297239310Sdim// MinInstrCountEnsemble - Pick the trace that executes the least number of 298239310Sdim// instructions. 299239310Sdimnamespace { 300239310Sdimclass MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { 301276479Sdim const char *getName() const override { return "MinInstr"; } 302276479Sdim const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) override; 303276479Sdim const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) override; 304239310Sdim 305239310Sdimpublic: 306239310Sdim MinInstrCountEnsemble(MachineTraceMetrics *mtm) 307239310Sdim : MachineTraceMetrics::Ensemble(mtm) {} 308239310Sdim}; 309239310Sdim} 310239310Sdim 311239310Sdim// Select the preferred predecessor for MBB. 312239310Sdimconst MachineBasicBlock* 313239310SdimMinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { 314239310Sdim if (MBB->pred_empty()) 315276479Sdim return nullptr; 316239310Sdim const MachineLoop *CurLoop = getLoopFor(MBB); 317239310Sdim // Don't leave loops, and never follow back-edges. 318239310Sdim if (CurLoop && MBB == CurLoop->getHeader()) 319276479Sdim return nullptr; 320239310Sdim unsigned CurCount = MTM.getResources(MBB)->InstrCount; 321276479Sdim const MachineBasicBlock *Best = nullptr; 322239310Sdim unsigned BestDepth = 0; 323288943Sdim for (const MachineBasicBlock *Pred : MBB->predecessors()) { 324239310Sdim const MachineTraceMetrics::TraceBlockInfo *PredTBI = 325239310Sdim getDepthResources(Pred); 326239310Sdim // Ignore cycles that aren't natural loops. 327239310Sdim if (!PredTBI) 328239310Sdim continue; 329239310Sdim // Pick the predecessor that would give this block the smallest InstrDepth. 330239310Sdim unsigned Depth = PredTBI->InstrDepth + CurCount; 331239310Sdim if (!Best || Depth < BestDepth) 332239310Sdim Best = Pred, BestDepth = Depth; 333239310Sdim } 334239310Sdim return Best; 335239310Sdim} 336239310Sdim 337239310Sdim// Select the preferred successor for MBB. 338239310Sdimconst MachineBasicBlock* 339239310SdimMinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { 340239310Sdim if (MBB->pred_empty()) 341276479Sdim return nullptr; 342239310Sdim const MachineLoop *CurLoop = getLoopFor(MBB); 343276479Sdim const MachineBasicBlock *Best = nullptr; 344239310Sdim unsigned BestHeight = 0; 345288943Sdim for (const MachineBasicBlock *Succ : MBB->successors()) { 346239310Sdim // Don't consider back-edges. 347239310Sdim if (CurLoop && Succ == CurLoop->getHeader()) 348239310Sdim continue; 349239310Sdim // Don't consider successors exiting CurLoop. 350239310Sdim if (isExitingLoop(CurLoop, getLoopFor(Succ))) 351239310Sdim continue; 352239310Sdim const MachineTraceMetrics::TraceBlockInfo *SuccTBI = 353239310Sdim getHeightResources(Succ); 354239310Sdim // Ignore cycles that aren't natural loops. 355239310Sdim if (!SuccTBI) 356239310Sdim continue; 357239310Sdim // Pick the successor that would give this block the smallest InstrHeight. 358239310Sdim unsigned Height = SuccTBI->InstrHeight; 359239310Sdim if (!Best || Height < BestHeight) 360239310Sdim Best = Succ, BestHeight = Height; 361239310Sdim } 362239310Sdim return Best; 363239310Sdim} 364239310Sdim 365239310Sdim// Get an Ensemble sub-class for the requested trace strategy. 366239310SdimMachineTraceMetrics::Ensemble * 367239310SdimMachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { 368239310Sdim assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); 369239310Sdim Ensemble *&E = Ensembles[strategy]; 370239310Sdim if (E) 371239310Sdim return E; 372239310Sdim 373239310Sdim // Allocate new Ensemble on demand. 374239310Sdim switch (strategy) { 375239310Sdim case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); 376239310Sdim default: llvm_unreachable("Invalid trace strategy enum"); 377239310Sdim } 378239310Sdim} 379239310Sdim 380239310Sdimvoid MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { 381239310Sdim DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n'); 382239310Sdim BlockInfo[MBB->getNumber()].invalidate(); 383239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) 384239310Sdim if (Ensembles[i]) 385239310Sdim Ensembles[i]->invalidate(MBB); 386239310Sdim} 387239310Sdim 388239310Sdimvoid MachineTraceMetrics::verifyAnalysis() const { 389239310Sdim if (!MF) 390239310Sdim return; 391239310Sdim#ifndef NDEBUG 392239310Sdim assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); 393239310Sdim for (unsigned i = 0; i != TS_NumStrategies; ++i) 394239310Sdim if (Ensembles[i]) 395239310Sdim Ensembles[i]->verify(); 396239310Sdim#endif 397239310Sdim} 398239310Sdim 399239310Sdim//===----------------------------------------------------------------------===// 400239310Sdim// Trace building 401239310Sdim//===----------------------------------------------------------------------===// 402239310Sdim// 403239310Sdim// Traces are built by two CFG traversals. To avoid recomputing too much, use a 404239310Sdim// set abstraction that confines the search to the current loop, and doesn't 405239310Sdim// revisit blocks. 406239310Sdim 407239310Sdimnamespace { 408239310Sdimstruct LoopBounds { 409239310Sdim MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; 410239310Sdim SmallPtrSet<const MachineBasicBlock*, 8> Visited; 411239310Sdim const MachineLoopInfo *Loops; 412239310Sdim bool Downward; 413239310Sdim LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, 414239310Sdim const MachineLoopInfo *loops) 415239310Sdim : Blocks(blocks), Loops(loops), Downward(false) {} 416239310Sdim}; 417239310Sdim} 418239310Sdim 419239310Sdim// Specialize po_iterator_storage in order to prune the post-order traversal so 420239310Sdim// it is limited to the current loop and doesn't traverse the loop back edges. 421239310Sdimnamespace llvm { 422239310Sdimtemplate<> 423239310Sdimclass po_iterator_storage<LoopBounds, true> { 424239310Sdim LoopBounds &LB; 425239310Sdimpublic: 426239310Sdim po_iterator_storage(LoopBounds &lb) : LB(lb) {} 427239310Sdim void finishPostorder(const MachineBasicBlock*) {} 428239310Sdim 429239310Sdim bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) { 430239310Sdim // Skip already visited To blocks. 431239310Sdim MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; 432239310Sdim if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth()) 433239310Sdim return false; 434239310Sdim // From is null once when To is the trace center block. 435239310Sdim if (From) { 436239310Sdim if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(From)) { 437239310Sdim // Don't follow backedges, don't leave FromLoop when going upwards. 438239310Sdim if ((LB.Downward ? To : From) == FromLoop->getHeader()) 439239310Sdim return false; 440239310Sdim // Don't leave FromLoop. 441239310Sdim if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To))) 442239310Sdim return false; 443239310Sdim } 444239310Sdim } 445239310Sdim // To is a new block. Mark the block as visited in case the CFG has cycles 446239310Sdim // that MachineLoopInfo didn't recognize as a natural loop. 447280031Sdim return LB.Visited.insert(To).second; 448239310Sdim } 449239310Sdim}; 450239310Sdim} 451239310Sdim 452239310Sdim/// Compute the trace through MBB. 453239310Sdimvoid MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { 454239310Sdim DEBUG(dbgs() << "Computing " << getName() << " trace through BB#" 455239310Sdim << MBB->getNumber() << '\n'); 456239310Sdim // Set up loop bounds for the backwards post-order traversal. 457239310Sdim LoopBounds Bounds(BlockInfo, MTM.Loops); 458239310Sdim 459239310Sdim // Run an upwards post-order search for the trace start. 460239310Sdim Bounds.Downward = false; 461239310Sdim Bounds.Visited.clear(); 462288943Sdim for (auto I : inverse_post_order_ext(MBB, Bounds)) { 463239310Sdim DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); 464239310Sdim TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 465239310Sdim // All the predecessors have been visited, pick the preferred one. 466288943Sdim TBI.Pred = pickTracePred(I); 467239310Sdim DEBUG({ 468239310Sdim if (TBI.Pred) 469239310Sdim dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; 470239310Sdim else 471239310Sdim dbgs() << "null\n"; 472239310Sdim }); 473239310Sdim // The trace leading to I is now known, compute the depth resources. 474288943Sdim computeDepthResources(I); 475239310Sdim } 476239310Sdim 477239310Sdim // Run a downwards post-order search for the trace end. 478239310Sdim Bounds.Downward = true; 479239310Sdim Bounds.Visited.clear(); 480288943Sdim for (auto I : post_order_ext(MBB, Bounds)) { 481239310Sdim DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); 482239310Sdim TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 483239310Sdim // All the successors have been visited, pick the preferred one. 484288943Sdim TBI.Succ = pickTraceSucc(I); 485239310Sdim DEBUG({ 486239310Sdim if (TBI.Succ) 487239310Sdim dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; 488239310Sdim else 489239310Sdim dbgs() << "null\n"; 490239310Sdim }); 491239310Sdim // The trace leaving I is now known, compute the height resources. 492288943Sdim computeHeightResources(I); 493239310Sdim } 494239310Sdim} 495239310Sdim 496239310Sdim/// Invalidate traces through BadMBB. 497239310Sdimvoid 498239310SdimMachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { 499239310Sdim SmallVector<const MachineBasicBlock*, 16> WorkList; 500239310Sdim TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; 501239310Sdim 502239310Sdim // Invalidate height resources of blocks above MBB. 503239310Sdim if (BadTBI.hasValidHeight()) { 504239310Sdim BadTBI.invalidateHeight(); 505239310Sdim WorkList.push_back(BadMBB); 506239310Sdim do { 507239310Sdim const MachineBasicBlock *MBB = WorkList.pop_back_val(); 508239310Sdim DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 509239310Sdim << " height.\n"); 510239310Sdim // Find any MBB predecessors that have MBB as their preferred successor. 511239310Sdim // They are the only ones that need to be invalidated. 512288943Sdim for (const MachineBasicBlock *Pred : MBB->predecessors()) { 513288943Sdim TraceBlockInfo &TBI = BlockInfo[Pred->getNumber()]; 514239310Sdim if (!TBI.hasValidHeight()) 515239310Sdim continue; 516239310Sdim if (TBI.Succ == MBB) { 517239310Sdim TBI.invalidateHeight(); 518288943Sdim WorkList.push_back(Pred); 519239310Sdim continue; 520239310Sdim } 521239310Sdim // Verify that TBI.Succ is actually a *I successor. 522288943Sdim assert((!TBI.Succ || Pred->isSuccessor(TBI.Succ)) && "CFG changed"); 523239310Sdim } 524239310Sdim } while (!WorkList.empty()); 525239310Sdim } 526239310Sdim 527239310Sdim // Invalidate depth resources of blocks below MBB. 528239310Sdim if (BadTBI.hasValidDepth()) { 529239310Sdim BadTBI.invalidateDepth(); 530239310Sdim WorkList.push_back(BadMBB); 531239310Sdim do { 532239310Sdim const MachineBasicBlock *MBB = WorkList.pop_back_val(); 533239310Sdim DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 534239310Sdim << " depth.\n"); 535239310Sdim // Find any MBB successors that have MBB as their preferred predecessor. 536239310Sdim // They are the only ones that need to be invalidated. 537288943Sdim for (const MachineBasicBlock *Succ : MBB->successors()) { 538288943Sdim TraceBlockInfo &TBI = BlockInfo[Succ->getNumber()]; 539239310Sdim if (!TBI.hasValidDepth()) 540239310Sdim continue; 541239310Sdim if (TBI.Pred == MBB) { 542239310Sdim TBI.invalidateDepth(); 543288943Sdim WorkList.push_back(Succ); 544239310Sdim continue; 545239310Sdim } 546239310Sdim // Verify that TBI.Pred is actually a *I predecessor. 547288943Sdim assert((!TBI.Pred || Succ->isPredecessor(TBI.Pred)) && "CFG changed"); 548239310Sdim } 549239310Sdim } while (!WorkList.empty()); 550239310Sdim } 551239310Sdim 552239310Sdim // Clear any per-instruction data. We only have to do this for BadMBB itself 553239310Sdim // because the instructions in that block may change. Other blocks may be 554239310Sdim // invalidated, but their instructions will stay the same, so there is no 555239310Sdim // need to erase the Cycle entries. They will be overwritten when we 556239310Sdim // recompute. 557276479Sdim for (const auto &I : *BadMBB) 558276479Sdim Cycles.erase(&I); 559239310Sdim} 560239310Sdim 561239310Sdimvoid MachineTraceMetrics::Ensemble::verify() const { 562239310Sdim#ifndef NDEBUG 563239310Sdim assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() && 564239310Sdim "Outdated BlockInfo size"); 565239310Sdim for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { 566239310Sdim const TraceBlockInfo &TBI = BlockInfo[Num]; 567239310Sdim if (TBI.hasValidDepth() && TBI.Pred) { 568239310Sdim const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 569239310Sdim assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); 570239310Sdim assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && 571239310Sdim "Trace is broken, depth should have been invalidated."); 572239310Sdim const MachineLoop *Loop = getLoopFor(MBB); 573239310Sdim assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); 574239310Sdim } 575239310Sdim if (TBI.hasValidHeight() && TBI.Succ) { 576239310Sdim const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 577239310Sdim assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); 578239310Sdim assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && 579239310Sdim "Trace is broken, height should have been invalidated."); 580239310Sdim const MachineLoop *Loop = getLoopFor(MBB); 581239310Sdim const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); 582239310Sdim assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && 583239310Sdim "Trace contains backedge"); 584239310Sdim } 585239310Sdim } 586239310Sdim#endif 587239310Sdim} 588239310Sdim 589239310Sdim//===----------------------------------------------------------------------===// 590239310Sdim// Data Dependencies 591239310Sdim//===----------------------------------------------------------------------===// 592239310Sdim// 593239310Sdim// Compute the depth and height of each instruction based on data dependencies 594239310Sdim// and instruction latencies. These cycle numbers assume that the CPU can issue 595239310Sdim// an infinite number of instructions per cycle as long as their dependencies 596239310Sdim// are ready. 597239310Sdim 598239310Sdim// A data dependency is represented as a defining MI and operand numbers on the 599239310Sdim// defining and using MI. 600239310Sdimnamespace { 601239310Sdimstruct DataDep { 602239310Sdim const MachineInstr *DefMI; 603239310Sdim unsigned DefOp; 604239310Sdim unsigned UseOp; 605239310Sdim 606239310Sdim DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp) 607239310Sdim : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {} 608239310Sdim 609239310Sdim /// Create a DataDep from an SSA form virtual register. 610239310Sdim DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp) 611239310Sdim : UseOp(UseOp) { 612239310Sdim assert(TargetRegisterInfo::isVirtualRegister(VirtReg)); 613239310Sdim MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg); 614239310Sdim assert(!DefI.atEnd() && "Register has no defs"); 615276479Sdim DefMI = DefI->getParent(); 616239310Sdim DefOp = DefI.getOperandNo(); 617239310Sdim assert((++DefI).atEnd() && "Register has multiple defs"); 618239310Sdim } 619239310Sdim}; 620239310Sdim} 621239310Sdim 622239310Sdim// Get the input data dependencies that must be ready before UseMI can issue. 623239310Sdim// Return true if UseMI has any physreg operands. 624239310Sdimstatic bool getDataDeps(const MachineInstr *UseMI, 625239310Sdim SmallVectorImpl<DataDep> &Deps, 626239310Sdim const MachineRegisterInfo *MRI) { 627288943Sdim // Debug values should not be included in any calculations. 628288943Sdim if (UseMI->isDebugValue()) 629288943Sdim return false; 630288943Sdim 631239310Sdim bool HasPhysRegs = false; 632288943Sdim for (MachineInstr::const_mop_iterator I = UseMI->operands_begin(), 633288943Sdim E = UseMI->operands_end(); I != E; ++I) { 634288943Sdim const MachineOperand &MO = *I; 635288943Sdim if (!MO.isReg()) 636239310Sdim continue; 637288943Sdim unsigned Reg = MO.getReg(); 638239310Sdim if (!Reg) 639239310Sdim continue; 640239310Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 641239310Sdim HasPhysRegs = true; 642239310Sdim continue; 643239310Sdim } 644239310Sdim // Collect virtual register reads. 645288943Sdim if (MO.readsReg()) 646288943Sdim Deps.push_back(DataDep(MRI, Reg, UseMI->getOperandNo(I))); 647239310Sdim } 648239310Sdim return HasPhysRegs; 649239310Sdim} 650239310Sdim 651239310Sdim// Get the input data dependencies of a PHI instruction, using Pred as the 652239310Sdim// preferred predecessor. 653239310Sdim// This will add at most one dependency to Deps. 654239310Sdimstatic void getPHIDeps(const MachineInstr *UseMI, 655239310Sdim SmallVectorImpl<DataDep> &Deps, 656239310Sdim const MachineBasicBlock *Pred, 657239310Sdim const MachineRegisterInfo *MRI) { 658239310Sdim // No predecessor at the beginning of a trace. Ignore dependencies. 659239310Sdim if (!Pred) 660239310Sdim return; 661239310Sdim assert(UseMI->isPHI() && UseMI->getNumOperands() % 2 && "Bad PHI"); 662239310Sdim for (unsigned i = 1; i != UseMI->getNumOperands(); i += 2) { 663239310Sdim if (UseMI->getOperand(i + 1).getMBB() == Pred) { 664239310Sdim unsigned Reg = UseMI->getOperand(i).getReg(); 665239310Sdim Deps.push_back(DataDep(MRI, Reg, i)); 666239310Sdim return; 667239310Sdim } 668239310Sdim } 669239310Sdim} 670239310Sdim 671239310Sdim// Keep track of physreg data dependencies by recording each live register unit. 672239310Sdim// Associate each regunit with an instruction operand. Depending on the 673239310Sdim// direction instructions are scanned, it could be the operand that defined the 674239310Sdim// regunit, or the highest operand to read the regunit. 675239310Sdimnamespace { 676239310Sdimstruct LiveRegUnit { 677239310Sdim unsigned RegUnit; 678239310Sdim unsigned Cycle; 679239310Sdim const MachineInstr *MI; 680239310Sdim unsigned Op; 681239310Sdim 682239310Sdim unsigned getSparseSetIndex() const { return RegUnit; } 683239310Sdim 684276479Sdim LiveRegUnit(unsigned RU) : RegUnit(RU), Cycle(0), MI(nullptr), Op(0) {} 685239310Sdim}; 686239310Sdim} 687239310Sdim 688239310Sdim// Identify physreg dependencies for UseMI, and update the live regunit 689239310Sdim// tracking set when scanning instructions downwards. 690239310Sdimstatic void updatePhysDepsDownwards(const MachineInstr *UseMI, 691239310Sdim SmallVectorImpl<DataDep> &Deps, 692239310Sdim SparseSet<LiveRegUnit> &RegUnits, 693239310Sdim const TargetRegisterInfo *TRI) { 694239310Sdim SmallVector<unsigned, 8> Kills; 695239310Sdim SmallVector<unsigned, 8> LiveDefOps; 696239310Sdim 697288943Sdim for (MachineInstr::const_mop_iterator MI = UseMI->operands_begin(), 698288943Sdim ME = UseMI->operands_end(); MI != ME; ++MI) { 699288943Sdim const MachineOperand &MO = *MI; 700288943Sdim if (!MO.isReg()) 701239310Sdim continue; 702288943Sdim unsigned Reg = MO.getReg(); 703239310Sdim if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 704239310Sdim continue; 705239310Sdim // Track live defs and kills for updating RegUnits. 706288943Sdim if (MO.isDef()) { 707288943Sdim if (MO.isDead()) 708239310Sdim Kills.push_back(Reg); 709239310Sdim else 710288943Sdim LiveDefOps.push_back(UseMI->getOperandNo(MI)); 711288943Sdim } else if (MO.isKill()) 712239310Sdim Kills.push_back(Reg); 713239310Sdim // Identify dependencies. 714288943Sdim if (!MO.readsReg()) 715239310Sdim continue; 716239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 717239310Sdim SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 718239310Sdim if (I == RegUnits.end()) 719239310Sdim continue; 720288943Sdim Deps.push_back(DataDep(I->MI, I->Op, UseMI->getOperandNo(MI))); 721239310Sdim break; 722239310Sdim } 723239310Sdim } 724239310Sdim 725239310Sdim // Update RegUnits to reflect live registers after UseMI. 726239310Sdim // First kills. 727296417Sdim for (unsigned Kill : Kills) 728296417Sdim for (MCRegUnitIterator Units(Kill, TRI); Units.isValid(); ++Units) 729239310Sdim RegUnits.erase(*Units); 730239310Sdim 731239310Sdim // Second, live defs. 732296417Sdim for (unsigned DefOp : LiveDefOps) { 733239310Sdim for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI); 734239310Sdim Units.isValid(); ++Units) { 735239310Sdim LiveRegUnit &LRU = RegUnits[*Units]; 736239310Sdim LRU.MI = UseMI; 737239310Sdim LRU.Op = DefOp; 738239310Sdim } 739239310Sdim } 740239310Sdim} 741239310Sdim 742239310Sdim/// The length of the critical path through a trace is the maximum of two path 743239310Sdim/// lengths: 744239310Sdim/// 745239310Sdim/// 1. The maximum height+depth over all instructions in the trace center block. 746239310Sdim/// 747239310Sdim/// 2. The longest cross-block dependency chain. For small blocks, it is 748239310Sdim/// possible that the critical path through the trace doesn't include any 749239310Sdim/// instructions in the block. 750239310Sdim/// 751239310Sdim/// This function computes the second number from the live-in list of the 752239310Sdim/// center block. 753239310Sdimunsigned MachineTraceMetrics::Ensemble:: 754239310SdimcomputeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { 755239310Sdim assert(TBI.HasValidInstrDepths && "Missing depth info"); 756239310Sdim assert(TBI.HasValidInstrHeights && "Missing height info"); 757239310Sdim unsigned MaxLen = 0; 758296417Sdim for (const LiveInReg &LIR : TBI.LiveIns) { 759239310Sdim if (!TargetRegisterInfo::isVirtualRegister(LIR.Reg)) 760239310Sdim continue; 761239310Sdim const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 762239310Sdim // Ignore dependencies outside the current trace. 763239310Sdim const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()]; 764249423Sdim if (!DefTBI.isUsefulDominator(TBI)) 765239310Sdim continue; 766239310Sdim unsigned Len = LIR.Height + Cycles[DefMI].Depth; 767239310Sdim MaxLen = std::max(MaxLen, Len); 768239310Sdim } 769239310Sdim return MaxLen; 770239310Sdim} 771239310Sdim 772239310Sdim/// Compute instruction depths for all instructions above or in MBB in its 773239310Sdim/// trace. This assumes that the trace through MBB has already been computed. 774239310Sdimvoid MachineTraceMetrics::Ensemble:: 775239310SdimcomputeInstrDepths(const MachineBasicBlock *MBB) { 776239310Sdim // The top of the trace may already be computed, and HasValidInstrDepths 777239310Sdim // implies Head->HasValidInstrDepths, so we only need to start from the first 778239310Sdim // block in the trace that needs to be recomputed. 779239310Sdim SmallVector<const MachineBasicBlock*, 8> Stack; 780239310Sdim do { 781239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 782239310Sdim assert(TBI.hasValidDepth() && "Incomplete trace"); 783239310Sdim if (TBI.HasValidInstrDepths) 784239310Sdim break; 785239310Sdim Stack.push_back(MBB); 786239310Sdim MBB = TBI.Pred; 787239310Sdim } while (MBB); 788239310Sdim 789239310Sdim // FIXME: If MBB is non-null at this point, it is the last pre-computed block 790239310Sdim // in the trace. We should track any live-out physregs that were defined in 791239310Sdim // the trace. This is quite rare in SSA form, typically created by CSE 792239310Sdim // hoisting a compare. 793239310Sdim SparseSet<LiveRegUnit> RegUnits; 794239310Sdim RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 795239310Sdim 796239310Sdim // Go through trace blocks in top-down order, stopping after the center block. 797239310Sdim SmallVector<DataDep, 8> Deps; 798239310Sdim while (!Stack.empty()) { 799239310Sdim MBB = Stack.pop_back_val(); 800249423Sdim DEBUG(dbgs() << "\nDepths for BB#" << MBB->getNumber() << ":\n"); 801239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 802239310Sdim TBI.HasValidInstrDepths = true; 803239310Sdim TBI.CriticalPath = 0; 804239310Sdim 805249423Sdim // Print out resource depths here as well. 806249423Sdim DEBUG({ 807249423Sdim dbgs() << format("%7u Instructions\n", TBI.InstrDepth); 808249423Sdim ArrayRef<unsigned> PRDepths = getProcResourceDepths(MBB->getNumber()); 809249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 810249423Sdim if (PRDepths[K]) { 811249423Sdim unsigned Factor = MTM.SchedModel.getResourceFactor(K); 812249423Sdim dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K])) 813249423Sdim << MTM.SchedModel.getProcResource(K)->Name << " (" 814249423Sdim << PRDepths[K]/Factor << " ops x" << Factor << ")\n"; 815249423Sdim } 816249423Sdim }); 817249423Sdim 818239310Sdim // Also compute the critical path length through MBB when possible. 819239310Sdim if (TBI.HasValidInstrHeights) 820239310Sdim TBI.CriticalPath = computeCrossBlockCriticalPath(TBI); 821239310Sdim 822276479Sdim for (const auto &UseMI : *MBB) { 823239310Sdim // Collect all data dependencies. 824239310Sdim Deps.clear(); 825276479Sdim if (UseMI.isPHI()) 826276479Sdim getPHIDeps(&UseMI, Deps, TBI.Pred, MTM.MRI); 827276479Sdim else if (getDataDeps(&UseMI, Deps, MTM.MRI)) 828276479Sdim updatePhysDepsDownwards(&UseMI, Deps, RegUnits, MTM.TRI); 829239310Sdim 830239310Sdim // Filter and process dependencies, computing the earliest issue cycle. 831239310Sdim unsigned Cycle = 0; 832288943Sdim for (const DataDep &Dep : Deps) { 833239310Sdim const TraceBlockInfo&DepTBI = 834239310Sdim BlockInfo[Dep.DefMI->getParent()->getNumber()]; 835239310Sdim // Ignore dependencies from outside the current trace. 836249423Sdim if (!DepTBI.isUsefulDominator(TBI)) 837239310Sdim continue; 838239310Sdim assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency"); 839239310Sdim unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth; 840239310Sdim // Add latency if DefMI is a real instruction. Transients get latency 0. 841239310Sdim if (!Dep.DefMI->isTransient()) 842243830Sdim DepCycle += MTM.SchedModel 843276479Sdim .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp); 844239310Sdim Cycle = std::max(Cycle, DepCycle); 845239310Sdim } 846239310Sdim // Remember the instruction depth. 847276479Sdim InstrCycles &MICycles = Cycles[&UseMI]; 848239310Sdim MICycles.Depth = Cycle; 849239310Sdim 850239310Sdim if (!TBI.HasValidInstrHeights) { 851276479Sdim DEBUG(dbgs() << Cycle << '\t' << UseMI); 852239310Sdim continue; 853239310Sdim } 854239310Sdim // Update critical path length. 855239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height); 856276479Sdim DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI); 857239310Sdim } 858239310Sdim } 859239310Sdim} 860239310Sdim 861239310Sdim// Identify physreg dependencies for MI when scanning instructions upwards. 862239310Sdim// Return the issue height of MI after considering any live regunits. 863239310Sdim// Height is the issue height computed from virtual register dependencies alone. 864239310Sdimstatic unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height, 865239310Sdim SparseSet<LiveRegUnit> &RegUnits, 866243830Sdim const TargetSchedModel &SchedModel, 867239310Sdim const TargetInstrInfo *TII, 868239310Sdim const TargetRegisterInfo *TRI) { 869239310Sdim SmallVector<unsigned, 8> ReadOps; 870288943Sdim 871288943Sdim for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), 872288943Sdim MOE = MI->operands_end(); MOI != MOE; ++MOI) { 873288943Sdim const MachineOperand &MO = *MOI; 874288943Sdim if (!MO.isReg()) 875239310Sdim continue; 876288943Sdim unsigned Reg = MO.getReg(); 877239310Sdim if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 878239310Sdim continue; 879288943Sdim if (MO.readsReg()) 880288943Sdim ReadOps.push_back(MI->getOperandNo(MOI)); 881288943Sdim if (!MO.isDef()) 882239310Sdim continue; 883239310Sdim // This is a def of Reg. Remove corresponding entries from RegUnits, and 884239310Sdim // update MI Height to consider the physreg dependencies. 885239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 886239310Sdim SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 887239310Sdim if (I == RegUnits.end()) 888239310Sdim continue; 889239310Sdim unsigned DepHeight = I->Cycle; 890239310Sdim if (!MI->isTransient()) { 891239310Sdim // We may not know the UseMI of this dependency, if it came from the 892243830Sdim // live-in list. SchedModel can handle a NULL UseMI. 893243830Sdim DepHeight += SchedModel 894288943Sdim .computeOperandLatency(MI, MI->getOperandNo(MOI), I->MI, I->Op); 895239310Sdim } 896239310Sdim Height = std::max(Height, DepHeight); 897239310Sdim // This regunit is dead above MI. 898239310Sdim RegUnits.erase(I); 899239310Sdim } 900239310Sdim } 901239310Sdim 902239310Sdim // Now we know the height of MI. Update any regunits read. 903239310Sdim for (unsigned i = 0, e = ReadOps.size(); i != e; ++i) { 904239310Sdim unsigned Reg = MI->getOperand(ReadOps[i]).getReg(); 905239310Sdim for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 906239310Sdim LiveRegUnit &LRU = RegUnits[*Units]; 907239310Sdim // Set the height to the highest reader of the unit. 908239310Sdim if (LRU.Cycle <= Height && LRU.MI != MI) { 909239310Sdim LRU.Cycle = Height; 910239310Sdim LRU.MI = MI; 911239310Sdim LRU.Op = ReadOps[i]; 912239310Sdim } 913239310Sdim } 914239310Sdim } 915239310Sdim 916239310Sdim return Height; 917239310Sdim} 918239310Sdim 919239310Sdim 920239310Sdimtypedef DenseMap<const MachineInstr *, unsigned> MIHeightMap; 921239310Sdim 922239310Sdim// Push the height of DefMI upwards if required to match UseMI. 923239310Sdim// Return true if this is the first time DefMI was seen. 924239310Sdimstatic bool pushDepHeight(const DataDep &Dep, 925239310Sdim const MachineInstr *UseMI, unsigned UseHeight, 926239310Sdim MIHeightMap &Heights, 927243830Sdim const TargetSchedModel &SchedModel, 928239310Sdim const TargetInstrInfo *TII) { 929239310Sdim // Adjust height by Dep.DefMI latency. 930239310Sdim if (!Dep.DefMI->isTransient()) 931243830Sdim UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, 932261991Sdim UseMI, Dep.UseOp); 933239310Sdim 934239310Sdim // Update Heights[DefMI] to be the maximum height seen. 935239310Sdim MIHeightMap::iterator I; 936239310Sdim bool New; 937276479Sdim std::tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight)); 938239310Sdim if (New) 939239310Sdim return true; 940239310Sdim 941239310Sdim // DefMI has been pushed before. Give it the max height. 942239310Sdim if (I->second < UseHeight) 943239310Sdim I->second = UseHeight; 944239310Sdim return false; 945239310Sdim} 946239310Sdim 947243830Sdim/// Assuming that the virtual register defined by DefMI:DefOp was used by 948243830Sdim/// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop 949243830Sdim/// when reaching the block that contains DefMI. 950239310Sdimvoid MachineTraceMetrics::Ensemble:: 951243830SdimaddLiveIns(const MachineInstr *DefMI, unsigned DefOp, 952239310Sdim ArrayRef<const MachineBasicBlock*> Trace) { 953239310Sdim assert(!Trace.empty() && "Trace should contain at least one block"); 954243830Sdim unsigned Reg = DefMI->getOperand(DefOp).getReg(); 955239310Sdim assert(TargetRegisterInfo::isVirtualRegister(Reg)); 956239310Sdim const MachineBasicBlock *DefMBB = DefMI->getParent(); 957239310Sdim 958239310Sdim // Reg is live-in to all blocks in Trace that follow DefMBB. 959239310Sdim for (unsigned i = Trace.size(); i; --i) { 960239310Sdim const MachineBasicBlock *MBB = Trace[i-1]; 961239310Sdim if (MBB == DefMBB) 962239310Sdim return; 963239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 964239310Sdim // Just add the register. The height will be updated later. 965239310Sdim TBI.LiveIns.push_back(Reg); 966239310Sdim } 967239310Sdim} 968239310Sdim 969239310Sdim/// Compute instruction heights in the trace through MBB. This updates MBB and 970239310Sdim/// the blocks below it in the trace. It is assumed that the trace has already 971239310Sdim/// been computed. 972239310Sdimvoid MachineTraceMetrics::Ensemble:: 973239310SdimcomputeInstrHeights(const MachineBasicBlock *MBB) { 974239310Sdim // The bottom of the trace may already be computed. 975239310Sdim // Find the blocks that need updating. 976239310Sdim SmallVector<const MachineBasicBlock*, 8> Stack; 977239310Sdim do { 978239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 979239310Sdim assert(TBI.hasValidHeight() && "Incomplete trace"); 980239310Sdim if (TBI.HasValidInstrHeights) 981239310Sdim break; 982239310Sdim Stack.push_back(MBB); 983239310Sdim TBI.LiveIns.clear(); 984239310Sdim MBB = TBI.Succ; 985239310Sdim } while (MBB); 986239310Sdim 987239310Sdim // As we move upwards in the trace, keep track of instructions that are 988239310Sdim // required by deeper trace instructions. Map MI -> height required so far. 989239310Sdim MIHeightMap Heights; 990239310Sdim 991239310Sdim // For physregs, the def isn't known when we see the use. 992239310Sdim // Instead, keep track of the highest use of each regunit. 993239310Sdim SparseSet<LiveRegUnit> RegUnits; 994239310Sdim RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 995239310Sdim 996239310Sdim // If the bottom of the trace was already precomputed, initialize heights 997239310Sdim // from its live-in list. 998239310Sdim // MBB is the highest precomputed block in the trace. 999239310Sdim if (MBB) { 1000239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1001288943Sdim for (LiveInReg &LI : TBI.LiveIns) { 1002239310Sdim if (TargetRegisterInfo::isVirtualRegister(LI.Reg)) { 1003239310Sdim // For virtual registers, the def latency is included. 1004239310Sdim unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; 1005239310Sdim if (Height < LI.Height) 1006239310Sdim Height = LI.Height; 1007239310Sdim } else { 1008239310Sdim // For register units, the def latency is not included because we don't 1009239310Sdim // know the def yet. 1010239310Sdim RegUnits[LI.Reg].Cycle = LI.Height; 1011239310Sdim } 1012239310Sdim } 1013239310Sdim } 1014239310Sdim 1015239310Sdim // Go through the trace blocks in bottom-up order. 1016239310Sdim SmallVector<DataDep, 8> Deps; 1017239310Sdim for (;!Stack.empty(); Stack.pop_back()) { 1018239310Sdim MBB = Stack.back(); 1019239310Sdim DEBUG(dbgs() << "Heights for BB#" << MBB->getNumber() << ":\n"); 1020239310Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1021239310Sdim TBI.HasValidInstrHeights = true; 1022239310Sdim TBI.CriticalPath = 0; 1023239310Sdim 1024249423Sdim DEBUG({ 1025249423Sdim dbgs() << format("%7u Instructions\n", TBI.InstrHeight); 1026249423Sdim ArrayRef<unsigned> PRHeights = getProcResourceHeights(MBB->getNumber()); 1027249423Sdim for (unsigned K = 0; K != PRHeights.size(); ++K) 1028249423Sdim if (PRHeights[K]) { 1029249423Sdim unsigned Factor = MTM.SchedModel.getResourceFactor(K); 1030249423Sdim dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K])) 1031249423Sdim << MTM.SchedModel.getProcResource(K)->Name << " (" 1032249423Sdim << PRHeights[K]/Factor << " ops x" << Factor << ")\n"; 1033249423Sdim } 1034249423Sdim }); 1035249423Sdim 1036239310Sdim // Get dependencies from PHIs in the trace successor. 1037239310Sdim const MachineBasicBlock *Succ = TBI.Succ; 1038239310Sdim // If MBB is the last block in the trace, and it has a back-edge to the 1039239310Sdim // loop header, get loop-carried dependencies from PHIs in the header. For 1040239310Sdim // that purpose, pretend that all the loop header PHIs have height 0. 1041239310Sdim if (!Succ) 1042239310Sdim if (const MachineLoop *Loop = getLoopFor(MBB)) 1043239310Sdim if (MBB->isSuccessor(Loop->getHeader())) 1044239310Sdim Succ = Loop->getHeader(); 1045239310Sdim 1046239310Sdim if (Succ) { 1047276479Sdim for (const auto &PHI : *Succ) { 1048276479Sdim if (!PHI.isPHI()) 1049276479Sdim break; 1050239310Sdim Deps.clear(); 1051276479Sdim getPHIDeps(&PHI, Deps, MBB, MTM.MRI); 1052239310Sdim if (!Deps.empty()) { 1053239310Sdim // Loop header PHI heights are all 0. 1054276479Sdim unsigned Height = TBI.Succ ? Cycles.lookup(&PHI).Height : 0; 1055276479Sdim DEBUG(dbgs() << "pred\t" << Height << '\t' << PHI); 1056276479Sdim if (pushDepHeight(Deps.front(), &PHI, Height, 1057243830Sdim Heights, MTM.SchedModel, MTM.TII)) 1058243830Sdim addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack); 1059239310Sdim } 1060239310Sdim } 1061239310Sdim } 1062239310Sdim 1063239310Sdim // Go through the block backwards. 1064239310Sdim for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin(); 1065239310Sdim BI != BB;) { 1066239310Sdim const MachineInstr *MI = --BI; 1067239310Sdim 1068239310Sdim // Find the MI height as determined by virtual register uses in the 1069239310Sdim // trace below. 1070239310Sdim unsigned Cycle = 0; 1071239310Sdim MIHeightMap::iterator HeightI = Heights.find(MI); 1072239310Sdim if (HeightI != Heights.end()) { 1073239310Sdim Cycle = HeightI->second; 1074239310Sdim // We won't be seeing any more MI uses. 1075239310Sdim Heights.erase(HeightI); 1076239310Sdim } 1077239310Sdim 1078239310Sdim // Don't process PHI deps. They depend on the specific predecessor, and 1079239310Sdim // we'll get them when visiting the predecessor. 1080239310Sdim Deps.clear(); 1081239310Sdim bool HasPhysRegs = !MI->isPHI() && getDataDeps(MI, Deps, MTM.MRI); 1082239310Sdim 1083239310Sdim // There may also be regunit dependencies to include in the height. 1084239310Sdim if (HasPhysRegs) 1085239310Sdim Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, 1086243830Sdim MTM.SchedModel, MTM.TII, MTM.TRI); 1087239310Sdim 1088239310Sdim // Update the required height of any virtual registers read by MI. 1089288943Sdim for (const DataDep &Dep : Deps) 1090288943Sdim if (pushDepHeight(Dep, MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) 1091288943Sdim addLiveIns(Dep.DefMI, Dep.DefOp, Stack); 1092239310Sdim 1093239310Sdim InstrCycles &MICycles = Cycles[MI]; 1094239310Sdim MICycles.Height = Cycle; 1095239310Sdim if (!TBI.HasValidInstrDepths) { 1096239310Sdim DEBUG(dbgs() << Cycle << '\t' << *MI); 1097239310Sdim continue; 1098239310Sdim } 1099239310Sdim // Update critical path length. 1100239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth); 1101239310Sdim DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *MI); 1102239310Sdim } 1103239310Sdim 1104239310Sdim // Update virtual live-in heights. They were added by addLiveIns() with a 0 1105239310Sdim // height because the final height isn't known until now. 1106239310Sdim DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:"); 1107288943Sdim for (LiveInReg &LIR : TBI.LiveIns) { 1108239310Sdim const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 1109239310Sdim LIR.Height = Heights.lookup(DefMI); 1110239310Sdim DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height); 1111239310Sdim } 1112239310Sdim 1113239310Sdim // Transfer the live regunits to the live-in list. 1114239310Sdim for (SparseSet<LiveRegUnit>::const_iterator 1115239310Sdim RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) { 1116239310Sdim TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle)); 1117239310Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(RI->RegUnit, MTM.TRI) 1118239310Sdim << '@' << RI->Cycle); 1119239310Sdim } 1120239310Sdim DEBUG(dbgs() << '\n'); 1121239310Sdim 1122239310Sdim if (!TBI.HasValidInstrDepths) 1123239310Sdim continue; 1124239310Sdim // Add live-ins to the critical path length. 1125239310Sdim TBI.CriticalPath = std::max(TBI.CriticalPath, 1126239310Sdim computeCrossBlockCriticalPath(TBI)); 1127239310Sdim DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n'); 1128239310Sdim } 1129239310Sdim} 1130239310Sdim 1131239310SdimMachineTraceMetrics::Trace 1132239310SdimMachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { 1133288943Sdim TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 1134288943Sdim 1135288943Sdim if (!TBI.hasValidDepth() || !TBI.hasValidHeight()) 1136288943Sdim computeTrace(MBB); 1137288943Sdim if (!TBI.HasValidInstrDepths) 1138288943Sdim computeInstrDepths(MBB); 1139288943Sdim if (!TBI.HasValidInstrHeights) 1140288943Sdim computeInstrHeights(MBB); 1141288943Sdim 1142288943Sdim return Trace(*this, TBI); 1143239310Sdim} 1144239310Sdim 1145239310Sdimunsigned 1146239310SdimMachineTraceMetrics::Trace::getInstrSlack(const MachineInstr *MI) const { 1147239310Sdim assert(MI && "Not an instruction."); 1148239310Sdim assert(getBlockNum() == unsigned(MI->getParent()->getNumber()) && 1149239310Sdim "MI must be in the trace center block"); 1150239310Sdim InstrCycles Cyc = getInstrCycles(MI); 1151239310Sdim return getCriticalPath() - (Cyc.Depth + Cyc.Height); 1152239310Sdim} 1153239310Sdim 1154239310Sdimunsigned 1155239310SdimMachineTraceMetrics::Trace::getPHIDepth(const MachineInstr *PHI) const { 1156239310Sdim const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum()); 1157239310Sdim SmallVector<DataDep, 1> Deps; 1158239310Sdim getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI); 1159239310Sdim assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor"); 1160239310Sdim DataDep &Dep = Deps.front(); 1161239310Sdim unsigned DepCycle = getInstrCycles(Dep.DefMI).Depth; 1162239310Sdim // Add latency if DefMI is a real instruction. Transients get latency 0. 1163239310Sdim if (!Dep.DefMI->isTransient()) 1164243830Sdim DepCycle += TE.MTM.SchedModel 1165261991Sdim .computeOperandLatency(Dep.DefMI, Dep.DefOp, PHI, Dep.UseOp); 1166239310Sdim return DepCycle; 1167239310Sdim} 1168239310Sdim 1169280031Sdim/// When bottom is set include instructions in current block in estimate. 1170239310Sdimunsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { 1171249423Sdim // Find the limiting processor resource. 1172249423Sdim // Numbers have been pre-scaled to be comparable. 1173249423Sdim unsigned PRMax = 0; 1174249423Sdim ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1175249423Sdim if (Bottom) { 1176249423Sdim ArrayRef<unsigned> PRCycles = TE.MTM.getProcResourceCycles(getBlockNum()); 1177249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 1178249423Sdim PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]); 1179249423Sdim } else { 1180249423Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) 1181249423Sdim PRMax = std::max(PRMax, PRDepths[K]); 1182249423Sdim } 1183249423Sdim // Convert to cycle count. 1184249423Sdim PRMax = TE.MTM.getCycles(PRMax); 1185249423Sdim 1186280031Sdim /// All instructions before current block 1187239310Sdim unsigned Instrs = TBI.InstrDepth; 1188280031Sdim // plus instructions in current block 1189239310Sdim if (Bottom) 1190239310Sdim Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; 1191243830Sdim if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1192243830Sdim Instrs /= IW; 1193239310Sdim // Assume issue width 1 without a schedule model. 1194249423Sdim return std::max(Instrs, PRMax); 1195239310Sdim} 1196239310Sdim 1197280031Sdimunsigned MachineTraceMetrics::Trace::getResourceLength( 1198280031Sdim ArrayRef<const MachineBasicBlock *> Extrablocks, 1199280031Sdim ArrayRef<const MCSchedClassDesc *> ExtraInstrs, 1200280031Sdim ArrayRef<const MCSchedClassDesc *> RemoveInstrs) const { 1201249423Sdim // Add up resources above and below the center block. 1202249423Sdim ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum()); 1203249423Sdim ArrayRef<unsigned> PRHeights = TE.getProcResourceHeights(getBlockNum()); 1204249423Sdim unsigned PRMax = 0; 1205280031Sdim 1206280031Sdim // Capture computing cycles from extra instructions 1207280031Sdim auto extraCycles = [this](ArrayRef<const MCSchedClassDesc *> Instrs, 1208280031Sdim unsigned ResourceIdx) 1209280031Sdim ->unsigned { 1210280031Sdim unsigned Cycles = 0; 1211288943Sdim for (const MCSchedClassDesc *SC : Instrs) { 1212251662Sdim if (!SC->isValid()) 1213251662Sdim continue; 1214251662Sdim for (TargetSchedModel::ProcResIter 1215280031Sdim PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), 1216280031Sdim PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); 1217280031Sdim PI != PE; ++PI) { 1218280031Sdim if (PI->ProcResourceIdx != ResourceIdx) 1219251662Sdim continue; 1220280031Sdim Cycles += 1221280031Sdim (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(ResourceIdx)); 1222251662Sdim } 1223251662Sdim } 1224280031Sdim return Cycles; 1225280031Sdim }; 1226280031Sdim 1227280031Sdim for (unsigned K = 0; K != PRDepths.size(); ++K) { 1228280031Sdim unsigned PRCycles = PRDepths[K] + PRHeights[K]; 1229288943Sdim for (const MachineBasicBlock *MBB : Extrablocks) 1230288943Sdim PRCycles += TE.MTM.getProcResourceCycles(MBB->getNumber())[K]; 1231280031Sdim PRCycles += extraCycles(ExtraInstrs, K); 1232280031Sdim PRCycles -= extraCycles(RemoveInstrs, K); 1233249423Sdim PRMax = std::max(PRMax, PRCycles); 1234249423Sdim } 1235249423Sdim // Convert to cycle count. 1236249423Sdim PRMax = TE.MTM.getCycles(PRMax); 1237249423Sdim 1238280031Sdim // Instrs: #instructions in current trace outside current block. 1239239310Sdim unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; 1240280031Sdim // Add instruction count from the extra blocks. 1241288943Sdim for (const MachineBasicBlock *MBB : Extrablocks) 1242288943Sdim Instrs += TE.MTM.getResources(MBB)->InstrCount; 1243280031Sdim Instrs += ExtraInstrs.size(); 1244280031Sdim Instrs -= RemoveInstrs.size(); 1245243830Sdim if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1246243830Sdim Instrs /= IW; 1247239310Sdim // Assume issue width 1 without a schedule model. 1248249423Sdim return std::max(Instrs, PRMax); 1249239310Sdim} 1250239310Sdim 1251280031Sdimbool MachineTraceMetrics::Trace::isDepInTrace(const MachineInstr *DefMI, 1252280031Sdim const MachineInstr *UseMI) const { 1253280031Sdim if (DefMI->getParent() == UseMI->getParent()) 1254280031Sdim return true; 1255280031Sdim 1256280031Sdim const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI->getParent()->getNumber()]; 1257280031Sdim const TraceBlockInfo &TBI = TE.BlockInfo[UseMI->getParent()->getNumber()]; 1258280031Sdim 1259280031Sdim return DepTBI.isUsefulDominator(TBI); 1260280031Sdim} 1261280031Sdim 1262239310Sdimvoid MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { 1263239310Sdim OS << getName() << " ensemble:\n"; 1264239310Sdim for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 1265239310Sdim OS << " BB#" << i << '\t'; 1266239310Sdim BlockInfo[i].print(OS); 1267239310Sdim OS << '\n'; 1268239310Sdim } 1269239310Sdim} 1270239310Sdim 1271239310Sdimvoid MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { 1272239310Sdim if (hasValidDepth()) { 1273239310Sdim OS << "depth=" << InstrDepth; 1274239310Sdim if (Pred) 1275239310Sdim OS << " pred=BB#" << Pred->getNumber(); 1276239310Sdim else 1277239310Sdim OS << " pred=null"; 1278239310Sdim OS << " head=BB#" << Head; 1279239310Sdim if (HasValidInstrDepths) 1280239310Sdim OS << " +instrs"; 1281239310Sdim } else 1282239310Sdim OS << "depth invalid"; 1283239310Sdim OS << ", "; 1284239310Sdim if (hasValidHeight()) { 1285239310Sdim OS << "height=" << InstrHeight; 1286239310Sdim if (Succ) 1287239310Sdim OS << " succ=BB#" << Succ->getNumber(); 1288239310Sdim else 1289239310Sdim OS << " succ=null"; 1290239310Sdim OS << " tail=BB#" << Tail; 1291239310Sdim if (HasValidInstrHeights) 1292239310Sdim OS << " +instrs"; 1293239310Sdim } else 1294239310Sdim OS << "height invalid"; 1295239310Sdim if (HasValidInstrDepths && HasValidInstrHeights) 1296239310Sdim OS << ", crit=" << CriticalPath; 1297239310Sdim} 1298239310Sdim 1299239310Sdimvoid MachineTraceMetrics::Trace::print(raw_ostream &OS) const { 1300239310Sdim unsigned MBBNum = &TBI - &TE.BlockInfo[0]; 1301239310Sdim 1302239310Sdim OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum 1303239310Sdim << " --> BB#" << TBI.Tail << ':'; 1304239310Sdim if (TBI.hasValidHeight() && TBI.hasValidDepth()) 1305239310Sdim OS << ' ' << getInstrCount() << " instrs."; 1306239310Sdim if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights) 1307239310Sdim OS << ' ' << TBI.CriticalPath << " cycles."; 1308239310Sdim 1309239310Sdim const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; 1310239310Sdim OS << "\nBB#" << MBBNum; 1311239310Sdim while (Block->hasValidDepth() && Block->Pred) { 1312239310Sdim unsigned Num = Block->Pred->getNumber(); 1313239310Sdim OS << " <- BB#" << Num; 1314239310Sdim Block = &TE.BlockInfo[Num]; 1315239310Sdim } 1316239310Sdim 1317239310Sdim Block = &TBI; 1318239310Sdim OS << "\n "; 1319239310Sdim while (Block->hasValidHeight() && Block->Succ) { 1320239310Sdim unsigned Num = Block->Succ->getNumber(); 1321239310Sdim OS << " -> BB#" << Num; 1322239310Sdim Block = &TE.BlockInfo[Num]; 1323239310Sdim } 1324239310Sdim OS << '\n'; 1325239310Sdim} 1326