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
  23 using namespace llvm;
  24
  25 char MachineTraceMetrics::ID = 0;
  26 char &llvm::MachineTraceMetricsID = MachineTraceMetrics::ID;
  27
  28 INITIALIZE_PASS_BEGIN(MachineTraceMetrics,
  29                   "machine-trace-metrics", "Machine Trace Metrics", false, true)
  30 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
  31 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  32 INITIALIZE_PASS_END(MachineTraceMetrics,
  33                   "machine-trace-metrics", "Machine Trace Metrics", false, true)
  34
  35 MachineTraceMetrics::MachineTraceMetrics()
  36   : MachineFunctionPass(ID), TII(0), TRI(0), MRI(0), Loops(0) {
  37   std::fill(Ensembles, array_endof(Ensembles), (Ensemble*)0);
  38 }
  39
  40 void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const {
  41   AU.setPreservesAll();
  42   AU.addRequired<MachineBranchProbabilityInfo>();
  43   AU.addRequired<MachineLoopInfo>();
  44   MachineFunctionPass::getAnalysisUsage(AU);
  45 }
  46
  47 bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) {
  48   MF = &Func;
  49   TII = MF->getTarget().getInstrInfo();
  50   TRI = MF->getTarget().getRegisterInfo();
  51   MRI = &MF->getRegInfo();
  52   Loops = &getAnalysis<MachineLoopInfo>();
  53   BlockInfo.resize(MF->getNumBlockIDs());
  54   return false;
  55 }
  56
  57 void MachineTraceMetrics::releaseMemory() {
  58   BlockInfo.clear();
  59   for (unsigned i = 0; i != TS_NumStrategies; ++i) {
  60     delete Ensembles[i];
  61     Ensembles[i] = 0;
  62   }
  63 }
  64
  65 //===----------------------------------------------------------------------===//
  66 //                          Fixed block information
  67 //===----------------------------------------------------------------------===//
  68 //
  69 // The number of instructions in a basic block and the CPU resources used by
  70 // those instructions don't depend on any given trace strategy.
  71
  72 /// Compute the resource usage in basic block MBB.
  73 const MachineTraceMetrics::FixedBlockInfo*
  74 MachineTraceMetrics::getResources(const MachineBasicBlock *MBB) {
  75   assert(MBB && "No basic block");
  76   FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()];
  77   if (FBI->hasResources())
  78     return FBI;
  79
  80   // Compute resource usage in the block.
  81   // FIXME: Compute per-functional unit counts.
  82   FBI->HasCalls = false;
  83   unsigned InstrCount = 0;
  84   for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
  85        I != E; ++I) {
  86     const MachineInstr *MI = I;
  87     if (MI->isTransient())
  88       continue;
  89     ++InstrCount;
  90     if (MI->isCall())
  91       FBI->HasCalls = true;
  92   }
  93   FBI->InstrCount = InstrCount;
  94   return FBI;
  95 }
  96
  97 //===----------------------------------------------------------------------===//
  98 //                         Ensemble utility functions
  99 //===----------------------------------------------------------------------===//
 100
 101 MachineTraceMetrics::Ensemble::Ensemble(MachineTraceMetrics *ct)
 102   : CT(*ct) {
 103   BlockInfo.resize(CT.BlockInfo.size());
 104 }
 105
 106 // Virtual destructor serves as an anchor.
 107 MachineTraceMetrics::Ensemble::~Ensemble() {}
 108
 109 const MachineLoop*
 110 MachineTraceMetrics::Ensemble::getLoopFor(const MachineBasicBlock *MBB) const {
 111   return CT.Loops->getLoopFor(MBB);
 112 }
 113
 114 // Update resource-related information in the TraceBlockInfo for MBB.
 115 // Only update resources related to the trace above MBB.
 116 void MachineTraceMetrics::Ensemble::
 117 computeDepthResources(const MachineBasicBlock *MBB) {
 118   TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
 119
 120   // Compute resources from trace above. The top block is simple.
 121   if (!TBI->Pred) {
 122     TBI->InstrDepth = 0;
 123     TBI->Head = MBB->getNumber();
 124     return;
 125   }
 126
 127   // Compute from the block above. A post-order traversal ensures the
 128   // predecessor is always computed first.
 129   TraceBlockInfo *PredTBI = &BlockInfo[TBI->Pred->getNumber()];
 130   assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet");
 131   const FixedBlockInfo *PredFBI = CT.getResources(TBI->Pred);
 132   TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount;
 133   TBI->Head = PredTBI->Head;
 134 }
 135
 136 // Update resource-related information in the TraceBlockInfo for MBB.
 137 // Only update resources related to the trace below MBB.
 138 void MachineTraceMetrics::Ensemble::
 139 computeHeightResources(const MachineBasicBlock *MBB) {
 140   TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
 141
 142   // Compute resources for the current block.
 143   TBI->InstrHeight = CT.getResources(MBB)->InstrCount;
 144
 145   // The trace tail is done.
 146   if (!TBI->Succ) {
 147     TBI->Tail = MBB->getNumber();
 148     return;
 149   }
 150
 151   // Compute from the block below. A post-order traversal ensures the
 152   // predecessor is always computed first.
 153   TraceBlockInfo *SuccTBI = &BlockInfo[TBI->Succ->getNumber()];
 154   assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet");
 155   TBI->InstrHeight += SuccTBI->InstrHeight;
 156   TBI->Tail = SuccTBI->Tail;
 157 }
 158
 159 // Check if depth resources for MBB are valid and return the TBI.
 160 // Return NULL if the resources have been invalidated.
 161 const MachineTraceMetrics::TraceBlockInfo*
 162 MachineTraceMetrics::Ensemble::
 163 getDepthResources(const MachineBasicBlock *MBB) const {
 164   const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
 165   return TBI->hasValidDepth() ? TBI : 0;
 166 }
 167
 168 // Check if height resources for MBB are valid and return the TBI.
 169 // Return NULL if the resources have been invalidated.
 170 const MachineTraceMetrics::TraceBlockInfo*
 171 MachineTraceMetrics::Ensemble::
 172 getHeightResources(const MachineBasicBlock *MBB) const {
 173   const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
 174   return TBI->hasValidHeight() ? TBI : 0;
 175 }
 176
 177 //===----------------------------------------------------------------------===//
 178 //                         Trace Selection Strategies
 179 //===----------------------------------------------------------------------===//
 180 //
 181 // A trace selection strategy is implemented as a sub-class of Ensemble. The
 182 // trace through a block B is computed by two DFS traversals of the CFG
 183 // starting from B. One upwards, and one downwards. During the upwards DFS,
 184 // pickTracePred() is called on the post-ordered blocks. During the downwards
 185 // DFS, pickTraceSucc() is called in a post-order.
 186 //
 187
 188 // We never allow traces that leave loops, but we do allow traces to enter
 189 // nested loops. We also never allow traces to contain back-edges.
 190 //
 191 // This means that a loop header can never appear above the center block of a
 192 // trace, except as the trace head. Below the center block, loop exiting edges
 193 // are banned.
 194 //
 195 // Return true if an edge from the From loop to the To loop is leaving a loop.
 196 // Either of To and From can be null.
 197 static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) {
 198   return From && !From->contains(To);
 199 }
 200
 201 // MinInstrCountEnsemble - Pick the trace that executes the least number of
 202 // instructions.
 203 namespace {
 204 class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble {
 205   const char *getName() const { return "MinInstr"; }
 206   const MachineBasicBlock *pickTracePred(const MachineBasicBlock*);
 207   const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*);
 208
 209 public:
 210   MinInstrCountEnsemble(MachineTraceMetrics *ct)
 211     : MachineTraceMetrics::Ensemble(ct) {}
 212 };
 213 }
 214
 215 // Select the preferred predecessor for MBB.
 216 const MachineBasicBlock*
 217 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
 218   if (MBB->pred_empty())
 219     return 0;
 220   const MachineLoop *CurLoop = getLoopFor(MBB);
 221   // Don't leave loops, and never follow back-edges.
 222   if (CurLoop && MBB == CurLoop->getHeader())
 223     return 0;
 224   unsigned CurCount = CT.getResources(MBB)->InstrCount;
 225   const MachineBasicBlock *Best = 0;
 226   unsigned BestDepth = 0;
 227   for (MachineBasicBlock::const_pred_iterator
 228        I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
 229     const MachineBasicBlock *Pred = *I;
 230     const MachineTraceMetrics::TraceBlockInfo *PredTBI =
 231       getDepthResources(Pred);
 232     assert(PredTBI && "Predecessor must be visited first");
 233     // Pick the predecessor that would give this block the smallest InstrDepth.
 234     unsigned Depth = PredTBI->InstrDepth + CurCount;
 235     if (!Best || Depth < BestDepth)
 236       Best = Pred, BestDepth = Depth;
 237   }
 238   return Best;
 239 }
 240
 241 // Select the preferred successor for MBB.
 242 const MachineBasicBlock*
 243 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
 244   if (MBB->pred_empty())
 245     return 0;
 246   const MachineLoop *CurLoop = getLoopFor(MBB);
 247   const MachineBasicBlock *Best = 0;
 248   unsigned BestHeight = 0;
 249   for (MachineBasicBlock::const_succ_iterator
 250        I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
 251     const MachineBasicBlock *Succ = *I;
 252     // Don't consider back-edges.
 253     if (CurLoop && Succ == CurLoop->getHeader())
 254       continue;
 255     // Don't consider successors exiting CurLoop.
 256     if (isExitingLoop(CurLoop, getLoopFor(Succ)))
 257       continue;
 258     const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
 259       getHeightResources(Succ);
 260     assert(SuccTBI && "Successor must be visited first");
 261     // Pick the successor that would give this block the smallest InstrHeight.
 262     unsigned Height = SuccTBI->InstrHeight;
 263     if (!Best || Height < BestHeight)
 264       Best = Succ, BestHeight = Height;
 265   }
 266   return Best;
 267 }
 268
 269 // Get an Ensemble sub-class for the requested trace strategy.
 270 MachineTraceMetrics::Ensemble *
 271 MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) {
 272   assert(strategy < TS_NumStrategies && "Invalid trace strategy enum");
 273   Ensemble *&E = Ensembles[strategy];
 274   if (E)
 275     return E;
 276
 277   // Allocate new Ensemble on demand.
 278   switch (strategy) {
 279   case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this));
 280   default: llvm_unreachable("Invalid trace strategy enum");
 281   }
 282 }
 283
 284 void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) {
 285   DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n');
 286   BlockInfo[MBB->getNumber()].invalidate();
 287   for (unsigned i = 0; i != TS_NumStrategies; ++i)
 288     if (Ensembles[i])
 289       Ensembles[i]->invalidate(MBB);
 290 }
 291
 292 void MachineTraceMetrics::verifyAnalysis() const {
 293 #ifndef NDEBUG
 294   assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");
 295   for (unsigned i = 0; i != TS_NumStrategies; ++i)
 296     if (Ensembles[i])
 297       Ensembles[i]->verify();
 298 #endif
 299 }
 300
 301 //===----------------------------------------------------------------------===//
 302 //                               Trace building
 303 //===----------------------------------------------------------------------===//
 304 //
 305 // Traces are built by two CFG traversals. To avoid recomputing too much, use a
 306 // set abstraction that confines the search to the current loop, and doesn't
 307 // revisit blocks.
 308
 309 namespace {
 310 struct LoopBounds {
 311   MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks;
 312   const MachineLoopInfo *Loops;
 313   bool Downward;
 314   LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks,
 315              const MachineLoopInfo *loops)
 316     : Blocks(blocks), Loops(loops), Downward(false) {}
 317 };
 318 }
 319
 320 // Specialize po_iterator_storage in order to prune the post-order traversal so
 321 // it is limited to the current loop and doesn't traverse the loop back edges.
 322 namespace llvm {
 323 template<>
 324 class po_iterator_storage<LoopBounds, true> {
 325   LoopBounds &LB;
 326 public:
 327   po_iterator_storage(LoopBounds &lb) : LB(lb) {}
 328   void finishPostorder(const MachineBasicBlock*) {}
 329
 330   bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) {
 331     // Skip already visited To blocks.
 332     MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
 333     if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
 334       return false;
 335     // From is null once when To is the trace center block.
 336     if (!From)
 337       return true;
 338     const MachineLoop *FromLoop = LB.Loops->getLoopFor(From);
 339     if (!FromLoop)
 340       return true;
 341     // Don't follow backedges, don't leave FromLoop when going upwards.
 342     if ((LB.Downward ? To : From) == FromLoop->getHeader())
 343       return false;
 344     // Don't leave FromLoop.
 345     if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
 346       return false;
 347     // This is a new block. The PO traversal will compute height/depth
 348     // resources, causing us to reject new edges to To. This only works because
 349     // we reject back-edges, so the CFG is cycle-free.
 350     return true;
 351   }
 352 };
 353 }
 354
 355 /// Compute the trace through MBB.
 356 void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {
 357   DEBUG(dbgs() << "Computing " << getName() << " trace through BB#"
 358                << MBB->getNumber() << '\n');
 359   // Set up loop bounds for the backwards post-order traversal.
 360   LoopBounds Bounds(BlockInfo, CT.Loops);
 361
 362   // Run an upwards post-order search for the trace start.
 363   Bounds.Downward = false;
 364   typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO;
 365   for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds);
 366        I != E; ++I) {
 367     DEBUG(dbgs() << "  pred for BB#" << I->getNumber() << ": ");
 368     TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
 369     // All the predecessors have been visited, pick the preferred one.
 370     TBI.Pred = pickTracePred(*I);
 371     DEBUG({
 372       if (TBI.Pred)
 373         dbgs() << "BB#" << TBI.Pred->getNumber() << '\n';
 374       else
 375         dbgs() << "null\n";
 376     });
 377     // The trace leading to I is now known, compute the depth resources.
 378     computeDepthResources(*I);
 379   }
 380
 381   // Run a downwards post-order search for the trace end.
 382   Bounds.Downward = true;
 383   typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO;
 384   for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds);
 385        I != E; ++I) {
 386     DEBUG(dbgs() << "  succ for BB#" << I->getNumber() << ": ");
 387     TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
 388     // All the successors have been visited, pick the preferred one.
 389     TBI.Succ = pickTraceSucc(*I);
 390     DEBUG({
 391       if (TBI.Succ)
 392         dbgs() << "BB#" << TBI.Succ->getNumber() << '\n';
 393       else
 394         dbgs() << "null\n";
 395     });
 396     // The trace leaving I is now known, compute the height resources.
 397     computeHeightResources(*I);
 398   }
 399 }
 400
 401 /// Invalidate traces through BadMBB.
 402 void
 403 MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) {
 404   SmallVector<const MachineBasicBlock*, 16> WorkList;
 405   TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()];
 406
 407   // Invalidate height resources of blocks above MBB.
 408   if (BadTBI.hasValidHeight()) {
 409     BadTBI.invalidateHeight();
 410     WorkList.push_back(BadMBB);
 411     do {
 412       const MachineBasicBlock *MBB = WorkList.pop_back_val();
 413       DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
 414             << " height.\n");
 415       // Find any MBB predecessors that have MBB as their preferred successor.
 416       // They are the only ones that need to be invalidated.
 417       for (MachineBasicBlock::const_pred_iterator
 418            I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
 419         TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
 420         if (!TBI.hasValidHeight())
 421           continue;
 422         if (TBI.Succ == MBB) {
 423           TBI.invalidateHeight();
 424           WorkList.push_back(*I);
 425           continue;
 426         }
 427         // Verify that TBI.Succ is actually a *I successor.
 428         assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed");
 429       }
 430     } while (!WorkList.empty());
 431   }
 432
 433   // Invalidate depth resources of blocks below MBB.
 434   if (BadTBI.hasValidDepth()) {
 435     BadTBI.invalidateDepth();
 436     WorkList.push_back(BadMBB);
 437     do {
 438       const MachineBasicBlock *MBB = WorkList.pop_back_val();
 439       DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
 440             << " depth.\n");
 441       // Find any MBB successors that have MBB as their preferred predecessor.
 442       // They are the only ones that need to be invalidated.
 443       for (MachineBasicBlock::const_succ_iterator
 444            I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
 445         TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
 446         if (!TBI.hasValidDepth())
 447           continue;
 448         if (TBI.Pred == MBB) {
 449           TBI.invalidateDepth();
 450           WorkList.push_back(*I);
 451           continue;
 452         }
 453         // Verify that TBI.Pred is actually a *I predecessor.
 454         assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed");
 455       }
 456     } while (!WorkList.empty());
 457   }
 458 }
 459
 460 void MachineTraceMetrics::Ensemble::verify() const {
 461 #ifndef NDEBUG
 462   assert(BlockInfo.size() == CT.MF->getNumBlockIDs() &&
 463          "Outdated BlockInfo size");
 464   for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {
 465     const TraceBlockInfo &TBI = BlockInfo[Num];
 466     if (TBI.hasValidDepth() && TBI.Pred) {
 467       const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
 468       assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");
 469       assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() &&
 470              "Trace is broken, depth should have been invalidated.");
 471       const MachineLoop *Loop = getLoopFor(MBB);
 472       assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge");
 473     }
 474     if (TBI.hasValidHeight() && TBI.Succ) {
 475       const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
 476       assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");
 477       assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() &&
 478              "Trace is broken, height should have been invalidated.");
 479       const MachineLoop *Loop = getLoopFor(MBB);
 480       const MachineLoop *SuccLoop = getLoopFor(TBI.Succ);
 481       assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) &&
 482              "Trace contains backedge");
 483     }
 484   }
 485 #endif
 486 }
 487
 488 MachineTraceMetrics::Trace
 489 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
 490   // FIXME: Check cache tags, recompute as needed.
 491   computeTrace(MBB);
 492   return Trace(*this, BlockInfo[MBB->getNumber()]);
 493 }
 494
 495 void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const {
 496   OS << getName() << " ensemble:\n";
 497   for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
 498     OS << "  BB#" << i << '\t';
 499     BlockInfo[i].print(OS);
 500     OS << '\n';
 501   }
 502 }
 503
 504 void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const {
 505   if (hasValidDepth()) {
 506     OS << "depth=" << InstrDepth;
 507     if (Pred)
 508       OS << " pred=BB#" << Pred->getNumber();
 509     else
 510       OS << " pred=null";
 511     OS << " head=BB#" << Head;
 512   } else
 513     OS << "depth invalid";
 514   OS << ", ";
 515   if (hasValidHeight()) {
 516     OS << "height=" << InstrHeight;
 517     if (Succ)
 518       OS << " succ=BB#" << Succ->getNumber();
 519     else
 520       OS << " succ=null";
 521     OS << " tail=BB#" << Tail;
 522   } else
 523     OS << "height invalid";
 524 }
 525
 526 void MachineTraceMetrics::Trace::print(raw_ostream &OS) const {
 527   unsigned MBBNum = &TBI - &TE.BlockInfo[0];
 528
 529   OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum
 530      << " --> BB#" << TBI.Tail << ':';
 531   if (TBI.hasValidHeight() && TBI.hasValidDepth())
 532     OS << ' ' << getInstrCount() << " instrs.";
 533
 534   const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
 535   OS << "\nBB#" << MBBNum;
 536   while (Block->hasValidDepth() && Block->Pred) {
 537     unsigned Num = Block->Pred->getNumber();
 538     OS << " <- BB#" << Num;
 539     Block = &TE.BlockInfo[Num];
 540   }
 541
 542   Block = &TBI;
 543   OS << "\n    ";
 544   while (Block->hasValidHeight() && Block->Succ) {
 545     unsigned Num = Block->Succ->getNumber();
 546     OS << " -> BB#" << Num;
 547     Block = &TE.BlockInfo[Num];
 548   }
 549   OS << '\n';
 550 }