1//===- lib/CodeGen/MachineTraceMetrics.cpp ----------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#define DEBUG_TYPE "machine-trace-metrics" 11#include "MachineTraceMetrics.h" 12#include "llvm/CodeGen/MachineBasicBlock.h" 13#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 14#include "llvm/CodeGen/MachineLoopInfo.h" 15#include "llvm/CodeGen/MachineRegisterInfo.h" 16#include "llvm/CodeGen/Passes.h" 17#include "llvm/MC/MCSubtargetInfo.h" 18#include "llvm/Target/TargetInstrInfo.h" 19#include "llvm/Target/TargetRegisterInfo.h" 20#include "llvm/Target/TargetSubtargetInfo.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/raw_ostream.h" 23#include "llvm/ADT/PostOrderIterator.h" 24#include "llvm/ADT/SparseSet.h" 25 26using namespace llvm; 27 28char MachineTraceMetrics::ID = 0; 29char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID; 30 31INITIALIZE_PASS_BEGIN(MachineTraceMetrics, 32 "machine-trace-metrics", "Machine Trace Metrics", false, true) 33INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) 34INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 35INITIALIZE_PASS_END(MachineTraceMetrics, 36 "machine-trace-metrics", "Machine Trace Metrics", false, true) 37 38MachineTraceMetrics::MachineTraceMetrics() 39 : MachineFunctionPass(ID), MF(0), TII(0), TRI(0), MRI(0), Loops(0) { 40 std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0); 41} 42 43void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { 44 AU.setPreservesAll(); 45 AU.addRequired<MachineBranchProbabilityInfo>(); 46 AU.addRequired<MachineLoopInfo>(); 47 MachineFunctionPass::getAnalysisUsage(AU); 48} 49 50bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { 51 MF = &Func; 52 TII = MF->getTarget().getInstrInfo(); 53 TRI = MF->getTarget().getRegisterInfo(); 54 MRI = &MF->getRegInfo(); 55 Loops = &getAnalysis<MachineLoopInfo>(); 56 const TargetSubtargetInfo &ST = 57 MF->getTarget().getSubtarget<TargetSubtargetInfo>(); 58 SchedModel.init(*ST.getSchedModel(), &ST, TII); 59 BlockInfo.resize(MF->getNumBlockIDs()); 60 return false; 61} 62 63void MachineTraceMetrics::releaseMemory() { 64 MF = 0; 65 BlockInfo.clear(); 66 for (unsigned i = 0; i != TS_NumStrategies; ++i) { 67 delete Ensembles[i]; 68 Ensembles[i] = 0; 69 } 70} 71 72//===----------------------------------------------------------------------===// 73// Fixed block information 74//===----------------------------------------------------------------------===// 75// 76// The number of instructions in a basic block and the CPU resources used by 77// those instructions don't depend on any given trace strategy. 78 79/// Compute the resource usage in basic block MBB. 80const MachineTraceMetrics::FixedBlockInfo* 81MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) { 82 assert(MBB && "No basic block"); 83 FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()]; 84 if (FBI->hasResources()) 85 return FBI; 86 87 // Compute resource usage in the block. 88 // FIXME: Compute per-functional unit counts. 89 FBI->HasCalls = false; 90 unsigned InstrCount = 0; 91 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 92 I != E; ++I) { 93 const MachineInstr *MI = I; 94 if (MI->isTransient()) 95 continue; 96 ++InstrCount; 97 if (MI->isCall()) 98 FBI->HasCalls = true; 99 } 100 FBI->InstrCount = InstrCount; 101 return FBI; 102} 103 104//===----------------------------------------------------------------------===// 105// Ensemble utility functions 106//===----------------------------------------------------------------------===// 107 108MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct) 109 : MTM(*ct) { 110 BlockInfo.resize(MTM.BlockInfo.size()); 111} 112 113// Virtual destructor serves as an anchor. 114MachineTraceMetrics::Ensemble::~Ensemble() {} 115 116const MachineLoop* 117MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const { 118 return MTM.Loops->getLoopFor(MBB); 119} 120 121// Update resource-related information in the TraceBlockInfo for MBB. 122// Only update resources related to the trace above MBB. 123void MachineTraceMetrics::Ensemble:: 124computeDepthResources(const MachineBasicBlock *MBB) { 125 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 126 127 // Compute resources from trace above. The top block is simple. 128 if (!TBI->Pred) { 129 TBI->InstrDepth = 0; 130 TBI->Head = MBB->getNumber(); 131 return; 132 } 133 134 // Compute from the block above. A post-order traversal ensures the 135 // predecessor is always computed first. 136 TraceBlockInfo *PredTBI = &BlockInfo[TBI->Pred->getNumber()]; 137 assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet"); 138 const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred); 139 TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount; 140 TBI->Head = PredTBI->Head; 141} 142 143// Update resource-related information in the TraceBlockInfo for MBB. 144// Only update resources related to the trace below MBB. 145void MachineTraceMetrics::Ensemble:: 146computeHeightResources(const MachineBasicBlock *MBB) { 147 TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 148 149 // Compute resources for the current block. 150 TBI->InstrHeight = MTM.getResources(MBB)->InstrCount; 151 152 // The trace tail is done. 153 if (!TBI->Succ) { 154 TBI->Tail = MBB->getNumber(); 155 return; 156 } 157 158 // Compute from the block below. A post-order traversal ensures the 159 // predecessor is always computed first. 160 TraceBlockInfo *SuccTBI = &BlockInfo[TBI->Succ->getNumber()]; 161 assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet"); 162 TBI->InstrHeight += SuccTBI->InstrHeight; 163 TBI->Tail = SuccTBI->Tail; 164} 165 166// Check if depth resources for MBB are valid and return the TBI. 167// Return NULL if the resources have been invalidated. 168const MachineTraceMetrics::TraceBlockInfo* 169MachineTraceMetrics::Ensemble:: 170getDepthResources(const MachineBasicBlock *MBB) const { 171 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 172 return TBI->hasValidDepth() ? TBI : 0; 173} 174 175// Check if height resources for MBB are valid and return the TBI. 176// Return NULL if the resources have been invalidated. 177const MachineTraceMetrics::TraceBlockInfo* 178MachineTraceMetrics::Ensemble:: 179getHeightResources(const MachineBasicBlock *MBB) const { 180 const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()]; 181 return TBI->hasValidHeight() ? TBI : 0; 182} 183 184//===----------------------------------------------------------------------===// 185// Trace Selection Strategies 186//===----------------------------------------------------------------------===// 187// 188// A trace selection strategy is implemented as a sub-class of Ensemble. The 189// trace through a block B is computed by two DFS traversals of the CFG 190// starting from B. One upwards, and one downwards. During the upwards DFS, 191// pickTracePred() is called on the post-ordered blocks. During the downwards 192// DFS, pickTraceSucc() is called in a post-order. 193// 194 195// We never allow traces that leave loops, but we do allow traces to enter 196// nested loops. We also never allow traces to contain back-edges. 197// 198// This means that a loop header can never appear above the center block of a 199// trace, except as the trace head. Below the center block, loop exiting edges 200// are banned. 201// 202// Return true if an edge from the From loop to the To loop is leaving a loop. 203// Either of To and From can be null. 204static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) { 205 return From && !From->contains(To); 206} 207 208// MinInstrCountEnsemble - Pick the trace that executes the least number of 209// instructions. 210namespace { 211class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble { 212 const char *getName() const { return "MinInstr"; } 213 const MachineBasicBlock *pickTracePred(const MachineBasicBlock*); 214 const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*); 215 216public: 217 MinInstrCountEnsemble(MachineTraceMetrics *mtm) 218 : MachineTraceMetrics::Ensemble(mtm) {} 219}; 220} 221 222// Select the preferred predecessor for MBB. 223const MachineBasicBlock* 224MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { 225 if (MBB->pred_empty()) 226 return 0; 227 const MachineLoop *CurLoop = getLoopFor(MBB); 228 // Don't leave loops, and never follow back-edges. 229 if (CurLoop && MBB == CurLoop->getHeader()) 230 return 0; 231 unsigned CurCount = MTM.getResources(MBB)->InstrCount; 232 const MachineBasicBlock *Best = 0; 233 unsigned BestDepth = 0; 234 for (MachineBasicBlock::const_pred_iterator 235 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 236 const MachineBasicBlock *Pred = *I; 237 const MachineTraceMetrics::TraceBlockInfo *PredTBI = 238 getDepthResources(Pred); 239 // Ignore cycles that aren't natural loops. 240 if (!PredTBI) 241 continue; 242 // Pick the predecessor that would give this block the smallest InstrDepth. 243 unsigned Depth = PredTBI->InstrDepth + CurCount; 244 if (!Best || Depth < BestDepth) 245 Best = Pred, BestDepth = Depth; 246 } 247 return Best; 248} 249 250// Select the preferred successor for MBB. 251const MachineBasicBlock* 252MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { 253 if (MBB->pred_empty()) 254 return 0; 255 const MachineLoop *CurLoop = getLoopFor(MBB); 256 const MachineBasicBlock *Best = 0; 257 unsigned BestHeight = 0; 258 for (MachineBasicBlock::const_succ_iterator 259 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 260 const MachineBasicBlock *Succ = *I; 261 // Don't consider back-edges. 262 if (CurLoop && Succ == CurLoop->getHeader()) 263 continue; 264 // Don't consider successors exiting CurLoop. 265 if (isExitingLoop(CurLoop, getLoopFor(Succ))) 266 continue; 267 const MachineTraceMetrics::TraceBlockInfo *SuccTBI = 268 getHeightResources(Succ); 269 // Ignore cycles that aren't natural loops. 270 if (!SuccTBI) 271 continue; 272 // Pick the successor that would give this block the smallest InstrHeight. 273 unsigned Height = SuccTBI->InstrHeight; 274 if (!Best || Height < BestHeight) 275 Best = Succ, BestHeight = Height; 276 } 277 return Best; 278} 279 280// Get an Ensemble sub-class for the requested trace strategy. 281MachineTraceMetrics::Ensemble * 282MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) { 283 assert(strategy < TS_NumStrategies && "Invalid trace strategy enum"); 284 Ensemble *&E = Ensembles[strategy]; 285 if (E) 286 return E; 287 288 // Allocate new Ensemble on demand. 289 switch (strategy) { 290 case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this)); 291 default: llvm_unreachable("Invalid trace strategy enum"); 292 } 293} 294 295void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) { 296 DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n'); 297 BlockInfo[MBB->getNumber()].invalidate(); 298 for (unsigned i = 0; i != TS_NumStrategies; ++i) 299 if (Ensembles[i]) 300 Ensembles[i]->invalidate(MBB); 301} 302 303void MachineTraceMetrics::verifyAnalysis() const { 304 if (!MF) 305 return; 306#ifndef NDEBUG 307 assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size"); 308 for (unsigned i = 0; i != TS_NumStrategies; ++i) 309 if (Ensembles[i]) 310 Ensembles[i]->verify(); 311#endif 312} 313 314//===----------------------------------------------------------------------===// 315// Trace building 316//===----------------------------------------------------------------------===// 317// 318// Traces are built by two CFG traversals. To avoid recomputing too much, use a 319// set abstraction that confines the search to the current loop, and doesn't 320// revisit blocks. 321 322namespace { 323struct LoopBounds { 324 MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks; 325 SmallPtrSet<const MachineBasicBlock*, 8> Visited; 326 const MachineLoopInfo *Loops; 327 bool Downward; 328 LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks, 329 const MachineLoopInfo *loops) 330 : Blocks(blocks), Loops(loops), Downward(false) {} 331}; 332} 333 334// Specialize po_iterator_storage in order to prune the post-order traversal so 335// it is limited to the current loop and doesn't traverse the loop back edges. 336namespace llvm { 337template<> 338class po_iterator_storage<LoopBounds, true> { 339 LoopBounds &LB; 340public: 341 po_iterator_storage(LoopBounds &lb) : LB(lb) {} 342 void finishPostorder(const MachineBasicBlock*) {} 343 344 bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) { 345 // Skip already visited To blocks. 346 MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()]; 347 if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth()) 348 return false; 349 // From is null once when To is the trace center block. 350 if (From) { 351 if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(From)) { 352 // Don't follow backedges, don't leave FromLoop when going upwards. 353 if ((LB.Downward ? To : From) == FromLoop->getHeader()) 354 return false; 355 // Don't leave FromLoop. 356 if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To))) 357 return false; 358 } 359 } 360 // To is a new block. Mark the block as visited in case the CFG has cycles 361 // that MachineLoopInfo didn't recognize as a natural loop. 362 return LB.Visited.insert(To); 363 } 364}; 365} 366 367/// Compute the trace through MBB. 368void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { 369 DEBUG(dbgs() << "Computing " << getName() << " trace through BB#" 370 << MBB->getNumber() << '\n'); 371 // Set up loop bounds for the backwards post-order traversal. 372 LoopBounds Bounds(BlockInfo, MTM.Loops); 373 374 // Run an upwards post-order search for the trace start. 375 Bounds.Downward = false; 376 Bounds.Visited.clear(); 377 typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO; 378 for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds); 379 I != E; ++I) { 380 DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); 381 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 382 // All the predecessors have been visited, pick the preferred one. 383 TBI.Pred = pickTracePred(*I); 384 DEBUG({ 385 if (TBI.Pred) 386 dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; 387 else 388 dbgs() << "null\n"; 389 }); 390 // The trace leading to I is now known, compute the depth resources. 391 computeDepthResources(*I); 392 } 393 394 // Run a downwards post-order search for the trace end. 395 Bounds.Downward = true; 396 Bounds.Visited.clear(); 397 typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO; 398 for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds); 399 I != E; ++I) { 400 DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); 401 TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; 402 // All the successors have been visited, pick the preferred one. 403 TBI.Succ = pickTraceSucc(*I); 404 DEBUG({ 405 if (TBI.Succ) 406 dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; 407 else 408 dbgs() << "null\n"; 409 }); 410 // The trace leaving I is now known, compute the height resources. 411 computeHeightResources(*I); 412 } 413} 414 415/// Invalidate traces through BadMBB. 416void 417MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { 418 SmallVector<const MachineBasicBlock*, 16> WorkList; 419 TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()]; 420 421 // Invalidate height resources of blocks above MBB. 422 if (BadTBI.hasValidHeight()) { 423 BadTBI.invalidateHeight(); 424 WorkList.push_back(BadMBB); 425 do { 426 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 427 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 428 << " height.\n"); 429 // Find any MBB predecessors that have MBB as their preferred successor. 430 // They are the only ones that need to be invalidated. 431 for (MachineBasicBlock::const_pred_iterator 432 I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { 433 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 434 if (!TBI.hasValidHeight()) 435 continue; 436 if (TBI.Succ == MBB) { 437 TBI.invalidateHeight(); 438 WorkList.push_back(*I); 439 continue; 440 } 441 // Verify that TBI.Succ is actually a *I successor. 442 assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed"); 443 } 444 } while (!WorkList.empty()); 445 } 446 447 // Invalidate depth resources of blocks below MBB. 448 if (BadTBI.hasValidDepth()) { 449 BadTBI.invalidateDepth(); 450 WorkList.push_back(BadMBB); 451 do { 452 const MachineBasicBlock *MBB = WorkList.pop_back_val(); 453 DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName() 454 << " depth.\n"); 455 // Find any MBB successors that have MBB as their preferred predecessor. 456 // They are the only ones that need to be invalidated. 457 for (MachineBasicBlock::const_succ_iterator 458 I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { 459 TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; 460 if (!TBI.hasValidDepth()) 461 continue; 462 if (TBI.Pred == MBB) { 463 TBI.invalidateDepth(); 464 WorkList.push_back(*I); 465 continue; 466 } 467 // Verify that TBI.Pred is actually a *I predecessor. 468 assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed"); 469 } 470 } while (!WorkList.empty()); 471 } 472 473 // Clear any per-instruction data. We only have to do this for BadMBB itself 474 // because the instructions in that block may change. Other blocks may be 475 // invalidated, but their instructions will stay the same, so there is no 476 // need to erase the Cycle entries. They will be overwritten when we 477 // recompute. 478 for (MachineBasicBlock::const_iterator I = BadMBB->begin(), E = BadMBB->end(); 479 I != E; ++I) 480 Cycles.erase(I); 481} 482 483void MachineTraceMetrics::Ensemble::verify() const { 484#ifndef NDEBUG 485 assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() && 486 "Outdated BlockInfo size"); 487 for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) { 488 const TraceBlockInfo &TBI = BlockInfo[Num]; 489 if (TBI.hasValidDepth() && TBI.Pred) { 490 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 491 assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace"); 492 assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() && 493 "Trace is broken, depth should have been invalidated."); 494 const MachineLoop *Loop = getLoopFor(MBB); 495 assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge"); 496 } 497 if (TBI.hasValidHeight() && TBI.Succ) { 498 const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num); 499 assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace"); 500 assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() && 501 "Trace is broken, height should have been invalidated."); 502 const MachineLoop *Loop = getLoopFor(MBB); 503 const MachineLoop *SuccLoop = getLoopFor(TBI.Succ); 504 assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) && 505 "Trace contains backedge"); 506 } 507 } 508#endif 509} 510 511//===----------------------------------------------------------------------===// 512// Data Dependencies 513//===----------------------------------------------------------------------===// 514// 515// Compute the depth and height of each instruction based on data dependencies 516// and instruction latencies. These cycle numbers assume that the CPU can issue 517// an infinite number of instructions per cycle as long as their dependencies 518// are ready. 519 520// A data dependency is represented as a defining MI and operand numbers on the 521// defining and using MI. 522namespace { 523struct DataDep { 524 const MachineInstr *DefMI; 525 unsigned DefOp; 526 unsigned UseOp; 527 528 DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp) 529 : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {} 530 531 /// Create a DataDep from an SSA form virtual register. 532 DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp) 533 : UseOp(UseOp) { 534 assert(TargetRegisterInfo::isVirtualRegister(VirtReg)); 535 MachineRegisterInfo::def_iterator DefI = MRI->def_begin(VirtReg); 536 assert(!DefI.atEnd() && "Register has no defs"); 537 DefMI = &*DefI; 538 DefOp = DefI.getOperandNo(); 539 assert((++DefI).atEnd() && "Register has multiple defs"); 540 } 541}; 542} 543 544// Get the input data dependencies that must be ready before UseMI can issue. 545// Return true if UseMI has any physreg operands. 546static bool getDataDeps(const MachineInstr *UseMI, 547 SmallVectorImpl<DataDep> &Deps, 548 const MachineRegisterInfo *MRI) { 549 bool HasPhysRegs = false; 550 for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { 551 if (!MO->isReg()) 552 continue; 553 unsigned Reg = MO->getReg(); 554 if (!Reg) 555 continue; 556 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 557 HasPhysRegs = true; 558 continue; 559 } 560 // Collect virtual register reads. 561 if (MO->readsReg()) 562 Deps.push_back(DataDep(MRI, Reg, MO.getOperandNo())); 563 } 564 return HasPhysRegs; 565} 566 567// Get the input data dependencies of a PHI instruction, using Pred as the 568// preferred predecessor. 569// This will add at most one dependency to Deps. 570static void getPHIDeps(const MachineInstr *UseMI, 571 SmallVectorImpl<DataDep> &Deps, 572 const MachineBasicBlock *Pred, 573 const MachineRegisterInfo *MRI) { 574 // No predecessor at the beginning of a trace. Ignore dependencies. 575 if (!Pred) 576 return; 577 assert(UseMI->isPHI() && UseMI->getNumOperands() % 2 && "Bad PHI"); 578 for (unsigned i = 1; i != UseMI->getNumOperands(); i += 2) { 579 if (UseMI->getOperand(i + 1).getMBB() == Pred) { 580 unsigned Reg = UseMI->getOperand(i).getReg(); 581 Deps.push_back(DataDep(MRI, Reg, i)); 582 return; 583 } 584 } 585} 586 587// Keep track of physreg data dependencies by recording each live register unit. 588// Associate each regunit with an instruction operand. Depending on the 589// direction instructions are scanned, it could be the operand that defined the 590// regunit, or the highest operand to read the regunit. 591namespace { 592struct LiveRegUnit { 593 unsigned RegUnit; 594 unsigned Cycle; 595 const MachineInstr *MI; 596 unsigned Op; 597 598 unsigned getSparseSetIndex() const { return RegUnit; } 599 600 LiveRegUnit(unsigned RU) : RegUnit(RU), Cycle(0), MI(0), Op(0) {} 601}; 602} 603 604// Identify physreg dependencies for UseMI, and update the live regunit 605// tracking set when scanning instructions downwards. 606static void updatePhysDepsDownwards(const MachineInstr *UseMI, 607 SmallVectorImpl<DataDep> &Deps, 608 SparseSet<LiveRegUnit> &RegUnits, 609 const TargetRegisterInfo *TRI) { 610 SmallVector<unsigned, 8> Kills; 611 SmallVector<unsigned, 8> LiveDefOps; 612 613 for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { 614 if (!MO->isReg()) 615 continue; 616 unsigned Reg = MO->getReg(); 617 if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 618 continue; 619 // Track live defs and kills for updating RegUnits. 620 if (MO->isDef()) { 621 if (MO->isDead()) 622 Kills.push_back(Reg); 623 else 624 LiveDefOps.push_back(MO.getOperandNo()); 625 } else if (MO->isKill()) 626 Kills.push_back(Reg); 627 // Identify dependencies. 628 if (!MO->readsReg()) 629 continue; 630 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 631 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 632 if (I == RegUnits.end()) 633 continue; 634 Deps.push_back(DataDep(I->MI, I->Op, MO.getOperandNo())); 635 break; 636 } 637 } 638 639 // Update RegUnits to reflect live registers after UseMI. 640 // First kills. 641 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 642 for (MCRegUnitIterator Units(Kills[i], TRI); Units.isValid(); ++Units) 643 RegUnits.erase(*Units); 644 645 // Second, live defs. 646 for (unsigned i = 0, e = LiveDefOps.size(); i != e; ++i) { 647 unsigned DefOp = LiveDefOps[i]; 648 for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI); 649 Units.isValid(); ++Units) { 650 LiveRegUnit &LRU = RegUnits[*Units]; 651 LRU.MI = UseMI; 652 LRU.Op = DefOp; 653 } 654 } 655} 656 657/// The length of the critical path through a trace is the maximum of two path 658/// lengths: 659/// 660/// 1. The maximum height+depth over all instructions in the trace center block. 661/// 662/// 2. The longest cross-block dependency chain. For small blocks, it is 663/// possible that the critical path through the trace doesn't include any 664/// instructions in the block. 665/// 666/// This function computes the second number from the live-in list of the 667/// center block. 668unsigned MachineTraceMetrics::Ensemble:: 669computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) { 670 assert(TBI.HasValidInstrDepths && "Missing depth info"); 671 assert(TBI.HasValidInstrHeights && "Missing height info"); 672 unsigned MaxLen = 0; 673 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 674 const LiveInReg &LIR = TBI.LiveIns[i]; 675 if (!TargetRegisterInfo::isVirtualRegister(LIR.Reg)) 676 continue; 677 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 678 // Ignore dependencies outside the current trace. 679 const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()]; 680 if (!DefTBI.isEarlierInSameTrace(TBI)) 681 continue; 682 unsigned Len = LIR.Height + Cycles[DefMI].Depth; 683 MaxLen = std::max(MaxLen, Len); 684 } 685 return MaxLen; 686} 687 688/// Compute instruction depths for all instructions above or in MBB in its 689/// trace. This assumes that the trace through MBB has already been computed. 690void MachineTraceMetrics::Ensemble:: 691computeInstrDepths(const MachineBasicBlock *MBB) { 692 // The top of the trace may already be computed, and HasValidInstrDepths 693 // implies Head->HasValidInstrDepths, so we only need to start from the first 694 // block in the trace that needs to be recomputed. 695 SmallVector<const MachineBasicBlock*, 8> Stack; 696 do { 697 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 698 assert(TBI.hasValidDepth() && "Incomplete trace"); 699 if (TBI.HasValidInstrDepths) 700 break; 701 Stack.push_back(MBB); 702 MBB = TBI.Pred; 703 } while (MBB); 704 705 // FIXME: If MBB is non-null at this point, it is the last pre-computed block 706 // in the trace. We should track any live-out physregs that were defined in 707 // the trace. This is quite rare in SSA form, typically created by CSE 708 // hoisting a compare. 709 SparseSet<LiveRegUnit> RegUnits; 710 RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 711 712 // Go through trace blocks in top-down order, stopping after the center block. 713 SmallVector<DataDep, 8> Deps; 714 while (!Stack.empty()) { 715 MBB = Stack.pop_back_val(); 716 DEBUG(dbgs() << "Depths for BB#" << MBB->getNumber() << ":\n"); 717 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 718 TBI.HasValidInstrDepths = true; 719 TBI.CriticalPath = 0; 720 721 // Also compute the critical path length through MBB when possible. 722 if (TBI.HasValidInstrHeights) 723 TBI.CriticalPath = computeCrossBlockCriticalPath(TBI); 724 725 for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end(); 726 I != E; ++I) { 727 const MachineInstr *UseMI = I; 728 729 // Collect all data dependencies. 730 Deps.clear(); 731 if (UseMI->isPHI()) 732 getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI); 733 else if (getDataDeps(UseMI, Deps, MTM.MRI)) 734 updatePhysDepsDownwards(UseMI, Deps, RegUnits, MTM.TRI); 735 736 // Filter and process dependencies, computing the earliest issue cycle. 737 unsigned Cycle = 0; 738 for (unsigned i = 0, e = Deps.size(); i != e; ++i) { 739 const DataDep &Dep = Deps[i]; 740 const TraceBlockInfo&DepTBI = 741 BlockInfo[Dep.DefMI->getParent()->getNumber()]; 742 // Ignore dependencies from outside the current trace. 743 if (!DepTBI.isEarlierInSameTrace(TBI)) 744 continue; 745 assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency"); 746 unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth; 747 // Add latency if DefMI is a real instruction. Transients get latency 0. 748 if (!Dep.DefMI->isTransient()) 749 DepCycle += MTM.SchedModel 750 .computeOperandLatency(Dep.DefMI, Dep.DefOp, UseMI, Dep.UseOp, 751 /* FindMin = */ false); 752 Cycle = std::max(Cycle, DepCycle); 753 } 754 // Remember the instruction depth. 755 InstrCycles &MICycles = Cycles[UseMI]; 756 MICycles.Depth = Cycle; 757 758 if (!TBI.HasValidInstrHeights) { 759 DEBUG(dbgs() << Cycle << '\t' << *UseMI); 760 continue; 761 } 762 // Update critical path length. 763 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height); 764 DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *UseMI); 765 } 766 } 767} 768 769// Identify physreg dependencies for MI when scanning instructions upwards. 770// Return the issue height of MI after considering any live regunits. 771// Height is the issue height computed from virtual register dependencies alone. 772static unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height, 773 SparseSet<LiveRegUnit> &RegUnits, 774 const TargetSchedModel &SchedModel, 775 const TargetInstrInfo *TII, 776 const TargetRegisterInfo *TRI) { 777 SmallVector<unsigned, 8> ReadOps; 778 for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 779 if (!MO->isReg()) 780 continue; 781 unsigned Reg = MO->getReg(); 782 if (!TargetRegisterInfo::isPhysicalRegister(Reg)) 783 continue; 784 if (MO->readsReg()) 785 ReadOps.push_back(MO.getOperandNo()); 786 if (!MO->isDef()) 787 continue; 788 // This is a def of Reg. Remove corresponding entries from RegUnits, and 789 // update MI Height to consider the physreg dependencies. 790 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 791 SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units); 792 if (I == RegUnits.end()) 793 continue; 794 unsigned DepHeight = I->Cycle; 795 if (!MI->isTransient()) { 796 // We may not know the UseMI of this dependency, if it came from the 797 // live-in list. SchedModel can handle a NULL UseMI. 798 DepHeight += SchedModel 799 .computeOperandLatency(MI, MO.getOperandNo(), I->MI, I->Op, 800 /* FindMin = */ false); 801 } 802 Height = std::max(Height, DepHeight); 803 // This regunit is dead above MI. 804 RegUnits.erase(I); 805 } 806 } 807 808 // Now we know the height of MI. Update any regunits read. 809 for (unsigned i = 0, e = ReadOps.size(); i != e; ++i) { 810 unsigned Reg = MI->getOperand(ReadOps[i]).getReg(); 811 for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { 812 LiveRegUnit &LRU = RegUnits[*Units]; 813 // Set the height to the highest reader of the unit. 814 if (LRU.Cycle <= Height && LRU.MI != MI) { 815 LRU.Cycle = Height; 816 LRU.MI = MI; 817 LRU.Op = ReadOps[i]; 818 } 819 } 820 } 821 822 return Height; 823} 824 825 826typedef DenseMap<const MachineInstr *, unsigned> MIHeightMap; 827 828// Push the height of DefMI upwards if required to match UseMI. 829// Return true if this is the first time DefMI was seen. 830static bool pushDepHeight(const DataDep &Dep, 831 const MachineInstr *UseMI, unsigned UseHeight, 832 MIHeightMap &Heights, 833 const TargetSchedModel &SchedModel, 834 const TargetInstrInfo *TII) { 835 // Adjust height by Dep.DefMI latency. 836 if (!Dep.DefMI->isTransient()) 837 UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, 838 UseMI, Dep.UseOp, false); 839 840 // Update Heights[DefMI] to be the maximum height seen. 841 MIHeightMap::iterator I; 842 bool New; 843 tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight)); 844 if (New) 845 return true; 846 847 // DefMI has been pushed before. Give it the max height. 848 if (I->second < UseHeight) 849 I->second = UseHeight; 850 return false; 851} 852 853/// Assuming that the virtual register defined by DefMI:DefOp was used by 854/// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop 855/// when reaching the block that contains DefMI. 856void MachineTraceMetrics::Ensemble:: 857addLiveIns(const MachineInstr *DefMI, unsigned DefOp, 858 ArrayRef<const MachineBasicBlock*> Trace) { 859 assert(!Trace.empty() && "Trace should contain at least one block"); 860 unsigned Reg = DefMI->getOperand(DefOp).getReg(); 861 assert(TargetRegisterInfo::isVirtualRegister(Reg)); 862 const MachineBasicBlock *DefMBB = DefMI->getParent(); 863 864 // Reg is live-in to all blocks in Trace that follow DefMBB. 865 for (unsigned i = Trace.size(); i; --i) { 866 const MachineBasicBlock *MBB = Trace[i-1]; 867 if (MBB == DefMBB) 868 return; 869 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 870 // Just add the register. The height will be updated later. 871 TBI.LiveIns.push_back(Reg); 872 } 873} 874 875/// Compute instruction heights in the trace through MBB. This updates MBB and 876/// the blocks below it in the trace. It is assumed that the trace has already 877/// been computed. 878void MachineTraceMetrics::Ensemble:: 879computeInstrHeights(const MachineBasicBlock *MBB) { 880 // The bottom of the trace may already be computed. 881 // Find the blocks that need updating. 882 SmallVector<const MachineBasicBlock*, 8> Stack; 883 do { 884 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 885 assert(TBI.hasValidHeight() && "Incomplete trace"); 886 if (TBI.HasValidInstrHeights) 887 break; 888 Stack.push_back(MBB); 889 TBI.LiveIns.clear(); 890 MBB = TBI.Succ; 891 } while (MBB); 892 893 // As we move upwards in the trace, keep track of instructions that are 894 // required by deeper trace instructions. Map MI -> height required so far. 895 MIHeightMap Heights; 896 897 // For physregs, the def isn't known when we see the use. 898 // Instead, keep track of the highest use of each regunit. 899 SparseSet<LiveRegUnit> RegUnits; 900 RegUnits.setUniverse(MTM.TRI->getNumRegUnits()); 901 902 // If the bottom of the trace was already precomputed, initialize heights 903 // from its live-in list. 904 // MBB is the highest precomputed block in the trace. 905 if (MBB) { 906 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 907 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 908 LiveInReg LI = TBI.LiveIns[i]; 909 if (TargetRegisterInfo::isVirtualRegister(LI.Reg)) { 910 // For virtual registers, the def latency is included. 911 unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; 912 if (Height < LI.Height) 913 Height = LI.Height; 914 } else { 915 // For register units, the def latency is not included because we don't 916 // know the def yet. 917 RegUnits[LI.Reg].Cycle = LI.Height; 918 } 919 } 920 } 921 922 // Go through the trace blocks in bottom-up order. 923 SmallVector<DataDep, 8> Deps; 924 for (;!Stack.empty(); Stack.pop_back()) { 925 MBB = Stack.back(); 926 DEBUG(dbgs() << "Heights for BB#" << MBB->getNumber() << ":\n"); 927 TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; 928 TBI.HasValidInstrHeights = true; 929 TBI.CriticalPath = 0; 930 931 // Get dependencies from PHIs in the trace successor. 932 const MachineBasicBlock *Succ = TBI.Succ; 933 // If MBB is the last block in the trace, and it has a back-edge to the 934 // loop header, get loop-carried dependencies from PHIs in the header. For 935 // that purpose, pretend that all the loop header PHIs have height 0. 936 if (!Succ) 937 if (const MachineLoop *Loop = getLoopFor(MBB)) 938 if (MBB->isSuccessor(Loop->getHeader())) 939 Succ = Loop->getHeader(); 940 941 if (Succ) { 942 for (MachineBasicBlock::const_iterator I = Succ->begin(), E = Succ->end(); 943 I != E && I->isPHI(); ++I) { 944 const MachineInstr *PHI = I; 945 Deps.clear(); 946 getPHIDeps(PHI, Deps, MBB, MTM.MRI); 947 if (!Deps.empty()) { 948 // Loop header PHI heights are all 0. 949 unsigned Height = TBI.Succ ? Cycles.lookup(PHI).Height : 0; 950 DEBUG(dbgs() << "pred\t" << Height << '\t' << *PHI); 951 if (pushDepHeight(Deps.front(), PHI, Height, 952 Heights, MTM.SchedModel, MTM.TII)) 953 addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack); 954 } 955 } 956 } 957 958 // Go through the block backwards. 959 for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin(); 960 BI != BB;) { 961 const MachineInstr *MI = --BI; 962 963 // Find the MI height as determined by virtual register uses in the 964 // trace below. 965 unsigned Cycle = 0; 966 MIHeightMap::iterator HeightI = Heights.find(MI); 967 if (HeightI != Heights.end()) { 968 Cycle = HeightI->second; 969 // We won't be seeing any more MI uses. 970 Heights.erase(HeightI); 971 } 972 973 // Don't process PHI deps. They depend on the specific predecessor, and 974 // we'll get them when visiting the predecessor. 975 Deps.clear(); 976 bool HasPhysRegs = !MI->isPHI() && getDataDeps(MI, Deps, MTM.MRI); 977 978 // There may also be regunit dependencies to include in the height. 979 if (HasPhysRegs) 980 Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, 981 MTM.SchedModel, MTM.TII, MTM.TRI); 982 983 // Update the required height of any virtual registers read by MI. 984 for (unsigned i = 0, e = Deps.size(); i != e; ++i) 985 if (pushDepHeight(Deps[i], MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) 986 addLiveIns(Deps[i].DefMI, Deps[i].DefOp, Stack); 987 988 InstrCycles &MICycles = Cycles[MI]; 989 MICycles.Height = Cycle; 990 if (!TBI.HasValidInstrDepths) { 991 DEBUG(dbgs() << Cycle << '\t' << *MI); 992 continue; 993 } 994 // Update critical path length. 995 TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth); 996 DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << *MI); 997 } 998 999 // Update virtual live-in heights. They were added by addLiveIns() with a 0 1000 // height because the final height isn't known until now. 1001 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:"); 1002 for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { 1003 LiveInReg &LIR = TBI.LiveIns[i]; 1004 const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); 1005 LIR.Height = Heights.lookup(DefMI); 1006 DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height); 1007 } 1008 1009 // Transfer the live regunits to the live-in list. 1010 for (SparseSet<LiveRegUnit>::const_iterator 1011 RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) { 1012 TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle)); 1013 DEBUG(dbgs() << ' ' << PrintRegUnit(RI->RegUnit, MTM.TRI) 1014 << '@' << RI->Cycle); 1015 } 1016 DEBUG(dbgs() << '\n'); 1017 1018 if (!TBI.HasValidInstrDepths) 1019 continue; 1020 // Add live-ins to the critical path length. 1021 TBI.CriticalPath = std::max(TBI.CriticalPath, 1022 computeCrossBlockCriticalPath(TBI)); 1023 DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n'); 1024 } 1025} 1026 1027MachineTraceMetrics::Trace 1028MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { 1029 // FIXME: Check cache tags, recompute as needed. 1030 computeTrace(MBB); 1031 computeInstrDepths(MBB); 1032 computeInstrHeights(MBB); 1033 return Trace(*this, BlockInfo[MBB->getNumber()]); 1034} 1035 1036unsigned 1037MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr *MI) const { 1038 assert(MI && "Not an instruction."); 1039 assert(getBlockNum() == unsigned(MI->getParent()->getNumber()) && 1040 "MI must be in the trace center block"); 1041 InstrCycles Cyc = getInstrCycles(MI); 1042 return getCriticalPath() - (Cyc.Depth + Cyc.Height); 1043} 1044 1045unsigned 1046MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr *PHI) const { 1047 const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum()); 1048 SmallVector<DataDep, 1> Deps; 1049 getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI); 1050 assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor"); 1051 DataDep &Dep = Deps.front(); 1052 unsigned DepCycle = getInstrCycles(Dep.DefMI).Depth; 1053 // Add latency if DefMI is a real instruction. Transients get latency 0. 1054 if (!Dep.DefMI->isTransient()) 1055 DepCycle += TE.MTM.SchedModel 1056 .computeOperandLatency(Dep.DefMI, Dep.DefOp, PHI, Dep.UseOp, false); 1057 return DepCycle; 1058} 1059 1060unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { 1061 // For now, we compute the resource depth from instruction count / issue 1062 // width. Eventually, we should compute resource depth per functional unit 1063 // and return the max. 1064 unsigned Instrs = TBI.InstrDepth; 1065 if (Bottom) 1066 Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; 1067 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1068 Instrs /= IW; 1069 // Assume issue width 1 without a schedule model. 1070 return Instrs; 1071} 1072 1073unsigned MachineTraceMetrics::Trace:: 1074getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks) const { 1075 unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; 1076 for (unsigned i = 0, e = Extrablocks.size(); i != e; ++i) 1077 Instrs += TE.MTM.getResources(Extrablocks[i])->InstrCount; 1078 if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) 1079 Instrs /= IW; 1080 // Assume issue width 1 without a schedule model. 1081 return Instrs; 1082} 1083 1084void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { 1085 OS << getName() << " ensemble:\n"; 1086 for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { 1087 OS << " BB#" << i << '\t'; 1088 BlockInfo[i].print(OS); 1089 OS << '\n'; 1090 } 1091} 1092 1093void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const { 1094 if (hasValidDepth()) { 1095 OS << "depth=" << InstrDepth; 1096 if (Pred) 1097 OS << " pred=BB#" << Pred->getNumber(); 1098 else 1099 OS << " pred=null"; 1100 OS << " head=BB#" << Head; 1101 if (HasValidInstrDepths) 1102 OS << " +instrs"; 1103 } else 1104 OS << "depth invalid"; 1105 OS << ", "; 1106 if (hasValidHeight()) { 1107 OS << "height=" << InstrHeight; 1108 if (Succ) 1109 OS << " succ=BB#" << Succ->getNumber(); 1110 else 1111 OS << " succ=null"; 1112 OS << " tail=BB#" << Tail; 1113 if (HasValidInstrHeights) 1114 OS << " +instrs"; 1115 } else 1116 OS << "height invalid"; 1117 if (HasValidInstrDepths && HasValidInstrHeights) 1118 OS << ", crit=" << CriticalPath; 1119} 1120 1121void MachineTraceMetrics::Trace::print(raw_ostream &OS) const { 1122 unsigned MBBNum = &TBI - &TE.BlockInfo[0]; 1123 1124 OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum 1125 << " --> BB#" << TBI.Tail << ':'; 1126 if (TBI.hasValidHeight() && TBI.hasValidDepth()) 1127 OS << ' ' << getInstrCount() << " instrs."; 1128 if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights) 1129 OS << ' ' << TBI.CriticalPath << " cycles."; 1130 1131 const MachineTraceMetrics::TraceBlockInfo *Block = &TBI; 1132 OS << "\nBB#" << MBBNum; 1133 while (Block->hasValidDepth() && Block->Pred) { 1134 unsigned Num = Block->Pred->getNumber(); 1135 OS << " <- BB#" << Num; 1136 Block = &TE.BlockInfo[Num]; 1137 } 1138 1139 Block = &TBI; 1140 OS << "\n "; 1141 while (Block->hasValidHeight() && Block->Succ) { 1142 unsigned Num = Block->Succ->getNumber(); 1143 OS << " -> BB#" << Num; 1144 Block = &TE.BlockInfo[Num]; 1145 } 1146 OS << '\n'; 1147} 1148