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