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 // MinInstrCountEnsemble - Pick the trace that executes the least number of
 189 // instructions.
 190 namespace {
 191 class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble {
 192   const char *getName() const { return "MinInstr"; }
 193   const MachineBasicBlock *pickTracePred(const MachineBasicBlock*);
 194   const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*);
 195
 196 public:
 197   MinInstrCountEnsemble(MachineTraceMetrics *ct)
 198     : MachineTraceMetrics::Ensemble(ct) {}
 199 };
 200 }
 201
 202 // Select the preferred predecessor for MBB.
 203 const MachineBasicBlock*
 204 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
 205   if (MBB->pred_empty())
 206     return 0;
 207   const MachineLoop *CurLoop = getLoopFor(MBB);
 208   // Don't leave loops, and never follow back-edges.
 209   if (CurLoop && MBB == CurLoop->getHeader())
 210     return 0;
 211   unsigned CurCount = CT.getResources(MBB)->InstrCount;
 212   const MachineBasicBlock *Best = 0;
 213   unsigned BestDepth = 0;
 214   for (MachineBasicBlock::const_pred_iterator
 215        I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
 216     const MachineBasicBlock *Pred = *I;
 217     const MachineTraceMetrics::TraceBlockInfo *PredTBI =
 218       getDepthResources(Pred);
 219     // Ignore invalidated predecessors. This never happens on the first scan,
 220     // but if we rejected this predecessor earlier, it won't be revalidated.
 221     if (!PredTBI)
 222       continue;
 223     // Don't consider predecessors in other loops.
 224     if (getLoopFor(Pred) != CurLoop)
 225       continue;
 226     // Pick the predecessor that would give this block the smallest InstrDepth.
 227     unsigned Depth = PredTBI->InstrDepth + CurCount;
 228     if (!Best || Depth < BestDepth)
 229       Best = Pred, BestDepth = Depth;
 230   }
 231   return Best;
 232 }
 233
 234 // Select the preferred successor for MBB.
 235 const MachineBasicBlock*
 236 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
 237   if (MBB->pred_empty())
 238     return 0;
 239   const MachineLoop *CurLoop = getLoopFor(MBB);
 240   const MachineBasicBlock *Best = 0;
 241   unsigned BestHeight = 0;
 242   for (MachineBasicBlock::const_succ_iterator
 243        I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
 244     const MachineBasicBlock *Succ = *I;
 245     const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
 246       getHeightResources(Succ);
 247     // Ignore invalidated successors.
 248     if (!SuccTBI)
 249       continue;
 250     // Don't consider back-edges.
 251     if (CurLoop && Succ == CurLoop->getHeader())
 252       continue;
 253     // Don't consider successors in other loops.
 254     if (getLoopFor(Succ) != CurLoop)
 255       continue;
 256     // Pick the successor that would give this block the smallest InstrHeight.
 257     unsigned Height = SuccTBI->InstrHeight;
 258     if (!Best || Height < BestHeight)
 259       Best = Succ, BestHeight = Height;
 260   }
 261   return Best;
 262 }
 263
 264 // Get an Ensemble sub-class for the requested trace strategy.
 265 MachineTraceMetrics::Ensemble *
 266 MachineTraceMetrics::getEnsemble(MachineTraceMetrics::Strategy strategy) {
 267   assert(strategy < TS_NumStrategies && "Invalid trace strategy enum");
 268   Ensemble *&E = Ensembles[strategy];
 269   if (E)
 270     return E;
 271
 272   // Allocate new Ensemble on demand.
 273   switch (strategy) {
 274   case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this));
 275   default: llvm_unreachable("Invalid trace strategy enum");
 276   }
 277 }
 278
 279 void MachineTraceMetrics::invalidate(const MachineBasicBlock *MBB) {
 280   DEBUG(dbgs() << "Invalidate traces through BB#" << MBB->getNumber() << '\n');
 281   BlockInfo[MBB->getNumber()].invalidate();
 282   for (unsigned i = 0; i != TS_NumStrategies; ++i)
 283     if (Ensembles[i])
 284       Ensembles[i]->invalidate(MBB);
 285 }
 286
 287 void MachineTraceMetrics::verify() const {
 288 #ifndef NDEBUG
 289   assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");
 290   for (unsigned i = 0; i != TS_NumStrategies; ++i)
 291     if (Ensembles[i])
 292       Ensembles[i]->verify();
 293 #endif
 294 }
 295
 296 //===----------------------------------------------------------------------===//
 297 //                               Trace building
 298 //===----------------------------------------------------------------------===//
 299 //
 300 // Traces are built by two CFG traversals. To avoid recomputing too much, use a
 301 // set abstraction that confines the search to the current loop, and doesn't
 302 // revisit blocks.
 303
 304 namespace {
 305 struct LoopBounds {
 306   MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks;
 307   const MachineLoopInfo *Loops;
 308   const MachineLoop *CurLoop;
 309   bool Downward;
 310   LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks,
 311              const MachineLoopInfo *loops, const MachineLoop *curloop)
 312     : Blocks(blocks), Loops(loops), CurLoop(curloop), Downward(false) {}
 313 };
 314 }
 315
 316 // Specialize po_iterator_storage in order to prune the post-order traversal so
 317 // it is limited to the current loop and doesn't traverse the loop back edges.
 318 namespace llvm {
 319 template<>
 320 class po_iterator_storage<LoopBounds, true> {
 321   LoopBounds &LB;
 322 public:
 323   po_iterator_storage(LoopBounds &lb) : LB(lb) {}
 324   void finishPostorder(const MachineBasicBlock*) {}
 325
 326   bool insertEdge(const MachineBasicBlock *From, const MachineBasicBlock *To) {
 327     // Skip already visited To blocks.
 328     MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
 329     if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
 330       return false;
 331     // Don't follow CurLoop backedges.
 332     if (LB.CurLoop && (LB.Downward ? To : From) == LB.CurLoop->getHeader())
 333       return false;
 334     // Don't leave CurLoop.
 335     if (LB.Loops->getLoopFor(To) != LB.CurLoop)
 336       return false;
 337     // This is a new block. The PO traversal will compute height/depth
 338     // resources, causing us to reject new edges to To. This only works because
 339     // we reject back-edges, so the CFG is cycle-free.
 340     return true;
 341   }
 342 };
 343 }
 344
 345 /// Compute the trace through MBB.
 346 void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {
 347   DEBUG(dbgs() << "Computing " << getName() << " trace through BB#"
 348                << MBB->getNumber() << '\n');
 349   // Set up loop bounds for the backwards post-order traversal.
 350   LoopBounds Bounds(BlockInfo, CT.Loops, getLoopFor(MBB));
 351
 352   // Run an upwards post-order search for the trace start.
 353   Bounds.Downward = false;
 354   typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO;
 355   for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds);
 356        I != E; ++I) {
 357     DEBUG(dbgs() << "  pred for BB#" << I->getNumber() << ": ");
 358     TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
 359     // All the predecessors have been visited, pick the preferred one.
 360     TBI.Pred = pickTracePred(*I);
 361     DEBUG({
 362       if (TBI.Pred)
 363         dbgs() << "BB#" << TBI.Pred->getNumber() << '\n';
 364       else
 365         dbgs() << "null\n";
 366     });
 367     // The trace leading to I is now known, compute the depth resources.
 368     computeDepthResources(*I);
 369   }
 370
 371   // Run a downwards post-order search for the trace end.
 372   Bounds.Downward = true;
 373   typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO;
 374   for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds);
 375        I != E; ++I) {
 376     DEBUG(dbgs() << "  succ for BB#" << I->getNumber() << ": ");
 377     TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
 378     // All the successors have been visited, pick the preferred one.
 379     TBI.Succ = pickTraceSucc(*I);
 380     DEBUG({
 381       if (TBI.Pred)
 382         dbgs() << "BB#" << TBI.Succ->getNumber() << '\n';
 383       else
 384         dbgs() << "null\n";
 385     });
 386     // The trace leaving I is now known, compute the height resources.
 387     computeHeightResources(*I);
 388   }
 389 }
 390
 391 /// Invalidate traces through BadMBB.
 392 void
 393 MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) {
 394   SmallVector<const MachineBasicBlock*, 16> WorkList;
 395   TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()];
 396
 397   // Invalidate height resources of blocks above MBB.
 398   if (BadTBI.hasValidHeight()) {
 399     BadTBI.invalidateHeight();
 400     WorkList.push_back(BadMBB);
 401     do {
 402       const MachineBasicBlock *MBB = WorkList.pop_back_val();
 403       DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
 404             << " height.\n");
 405       // Find any MBB predecessors that have MBB as their preferred successor.
 406       // They are the only ones that need to be invalidated.
 407       for (MachineBasicBlock::const_pred_iterator
 408            I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) {
 409         TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
 410         if (!TBI.hasValidHeight())
 411           continue;
 412         if (TBI.Succ == MBB) {
 413           TBI.invalidateHeight();
 414           WorkList.push_back(*I);
 415           continue;
 416         }
 417         // Verify that TBI.Succ is actually a *I successor.
 418         assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed");
 419       }
 420     } while (!WorkList.empty());
 421   }
 422
 423   // Invalidate depth resources of blocks below MBB.
 424   if (BadTBI.hasValidDepth()) {
 425     BadTBI.invalidateDepth();
 426     WorkList.push_back(BadMBB);
 427     do {
 428       const MachineBasicBlock *MBB = WorkList.pop_back_val();
 429       DEBUG(dbgs() << "Invalidate BB#" << MBB->getNumber() << ' ' << getName()
 430             << " depth.\n");
 431       // Find any MBB successors that have MBB as their preferred predecessor.
 432       // They are the only ones that need to be invalidated.
 433       for (MachineBasicBlock::const_succ_iterator
 434            I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) {
 435         TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()];
 436         if (!TBI.hasValidDepth())
 437           continue;
 438         if (TBI.Pred == MBB) {
 439           TBI.invalidateDepth();
 440           WorkList.push_back(*I);
 441           continue;
 442         }
 443         // Verify that TBI.Pred is actually a *I predecessor.
 444         assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed");
 445       }
 446     } while (!WorkList.empty());
 447   }
 448 }
 449
 450 void MachineTraceMetrics::Ensemble::verify() const {
 451 #ifndef NDEBUG
 452   assert(BlockInfo.size() == CT.MF->getNumBlockIDs() &&
 453          "Outdated BlockInfo size");
 454   for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {
 455     const TraceBlockInfo &TBI = BlockInfo[Num];
 456     if (TBI.hasValidDepth() && TBI.Pred) {
 457       const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
 458       assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");
 459       assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() &&
 460              "Trace is broken, depth should have been invalidated.");
 461       const MachineLoop *Loop = getLoopFor(MBB);
 462       assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge");
 463     }
 464     if (TBI.hasValidHeight() && TBI.Succ) {
 465       const MachineBasicBlock *MBB = CT.MF->getBlockNumbered(Num);
 466       assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");
 467       assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() &&
 468              "Trace is broken, height should have been invalidated.");
 469       const MachineLoop *Loop = getLoopFor(MBB);
 470       const MachineLoop *SuccLoop = getLoopFor(TBI.Succ);
 471       assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) &&
 472              "Trace contains backedge");
 473     }
 474   }
 475 #endif
 476 }
 477
 478 MachineTraceMetrics::Trace
 479 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
 480   // FIXME: Check cache tags, recompute as needed.
 481   computeTrace(MBB);
 482   return Trace(*this, BlockInfo[MBB->getNumber()]);
 483 }
 484
 485 void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const {
 486   OS << getName() << " ensemble:\n";
 487   for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
 488     OS << "  BB#" << i << '\t';
 489     BlockInfo[i].print(OS);
 490     OS << '\n';
 491   }
 492 }
 493
 494 void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const {
 495   if (hasValidDepth()) {
 496     OS << "depth=" << InstrDepth;
 497     if (Pred)
 498       OS << " pred=BB#" << Pred->getNumber();
 499     else
 500       OS << " pred=null";
 501     OS << " head=BB#" << Head;
 502   } else
 503     OS << "depth invalid";
 504   OS << ", ";
 505   if (hasValidHeight()) {
 506     OS << "height=" << InstrHeight;
 507     if (Succ)
 508       OS << " succ=BB#" << Succ->getNumber();
 509     else
 510       OS << " succ=null";
 511     OS << " tail=BB#" << Tail;
 512   } else
 513     OS << "height invalid";
 514 }
 515
 516 void MachineTraceMetrics::Trace::print(raw_ostream &OS) const {
 517   unsigned MBBNum = &TBI - &TE.BlockInfo[0];
 518
 519   OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum
 520      << " --> BB#" << TBI.Tail << ':';
 521   if (TBI.hasValidHeight() && TBI.hasValidDepth())
 522     OS << ' ' << getInstrCount() << " instrs.";
 523
 524   const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
 525   OS << "\nBB#" << MBBNum;
 526   while (Block->hasValidDepth() && Block->Pred) {
 527     unsigned Num = Block->Pred->getNumber();
 528     OS << " <- BB#" << Num;
 529     Block = &TE.BlockInfo[Num];
 530   }
 531
 532   Block = &TBI;
 533   OS << "\n    ";
 534   while (Block->hasValidHeight() && Block->Succ) {
 535     unsigned Num = Block->Succ->getNumber();
 536     OS << " -> BB#" << Num;
 537     Block = &TE.BlockInfo[Num];
 538   }
 539   OS << '\n';
 540 }