lib/CodeGen/MachineTraceMetrics.cpp

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