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 namespace {
 580 struct LiveRegUnit {
 581   unsigned RegUnit;
 582   unsigned DefOp;
 583   const MachineInstr *DefMI;
 584
 585   unsigned getSparseSetIndex() const { return RegUnit; }
 586
 587   LiveRegUnit(unsigned RU, const MachineInstr *MI = 0, unsigned OpNo = 0)
 588     : RegUnit(RU), DefOp(OpNo), DefMI(MI) {}
 589 };
 590 }
 591
 592 // Identify physreg dependencies for UseMI, and update the live regunit
 593 // tracking set when scanning instructions downwards.
 594 static void updatePhysDepsDownwards(const MachineInstr *UseMI,
 595                                     SmallVectorImpl<DataDep> &Deps,
 596                                     SparseSet<LiveRegUnit> &RegUnits,
 597                                     const TargetRegisterInfo *TRI) {
 598   SmallVector<unsigned, 8> Kills;
 599   SmallVector<unsigned, 8> LiveDefOps;
 600
 601   for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) {
 602     if (!MO->isReg())
 603       continue;
 604     unsigned Reg = MO->getReg();
 605     if (!TargetRegisterInfo::isPhysicalRegister(Reg))
 606       continue;
 607     // Track live defs and kills for updating RegUnits.
 608     if (MO->isDef()) {
 609       if (MO->isDead())
 610         Kills.push_back(Reg);
 611       else
 612         LiveDefOps.push_back(MO.getOperandNo());
 613     } else if (MO->isKill())
 614       Kills.push_back(Reg);
 615     // Identify dependencies.
 616     if (!MO->readsReg())
 617       continue;
 618     for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
 619       SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units);
 620       if (I == RegUnits.end())
 621         continue;
 622       Deps.push_back(DataDep(I->DefMI, I->DefOp, MO.getOperandNo()));
 623       break;
 624     }
 625   }
 626
 627   // Update RegUnits to reflect live registers after UseMI.
 628   // First kills.
 629   for (unsigned i = 0, e = Kills.size(); i != e; ++i)
 630     for (MCRegUnitIterator Units(Kills[i], TRI); Units.isValid(); ++Units)
 631       RegUnits.erase(*Units);
 632
 633   // Second, live defs.
 634   for (unsigned i = 0, e = LiveDefOps.size(); i != e; ++i) {
 635     unsigned DefOp = LiveDefOps[i];
 636     for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg(), TRI);
 637          Units.isValid(); ++Units) {
 638       LiveRegUnit &LRU = RegUnits[*Units];
 639       LRU.DefMI = UseMI;
 640       LRU.DefOp = DefOp;
 641     }
 642   }
 643 }
 644
 645
 646
 647
 648 /// Compute instruction depths for all instructions above or in MBB in its
 649 /// trace. This assumes that the trace through MBB has already been computed.
 650 void MachineTraceMetrics::Ensemble::
 651 computeInstrDepths(const MachineBasicBlock *MBB) {
 652   // The top of the trace may already be computed, and HasValidInstrDepths
 653   // implies Head->HasValidInstrDepths, so we only need to start from the first
 654   // block in the trace that needs to be recomputed.
 655   SmallVector<const MachineBasicBlock*, 8> Stack;
 656   do {
 657     TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
 658     assert(TBI.hasValidDepth() && "Incomplete trace");
 659     if (TBI.HasValidInstrDepths)
 660       break;
 661     Stack.push_back(MBB);
 662     MBB = TBI.Pred;
 663   } while (MBB);
 664
 665   // FIXME: If MBB is non-null at this point, it is the last pre-computed block
 666   // in the trace. We should track any live-out physregs that were defined in
 667   // the trace. This is quite rare in SSA form, typically created by CSE
 668   // hoisting a compare.
 669   SparseSet<LiveRegUnit> RegUnits;
 670   RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
 671
 672   // Go through trace blocks in top-down order, stopping after the center block.
 673   SmallVector<DataDep, 8> Deps;
 674   while (!Stack.empty()) {
 675     MBB = Stack.pop_back_val();
 676     DEBUG(dbgs() << "Depths for BB#" << MBB->getNumber() << ":\n");
 677     TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
 678     TBI.HasValidInstrDepths = true;
 679     for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
 680          I != E; ++I) {
 681       const MachineInstr *UseMI = I;
 682
 683       // Collect all data dependencies.
 684       Deps.clear();
 685       if (UseMI->isPHI())
 686         getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI);
 687       else if (getDataDeps(UseMI, Deps, MTM.MRI))
 688         updatePhysDepsDownwards(UseMI, Deps, RegUnits, MTM.TRI);
 689
 690       // Filter and process dependencies, computing the earliest issue cycle.
 691       unsigned Cycle = 0;
 692       for (unsigned i = 0, e = Deps.size(); i != e; ++i) {
 693         const DataDep &Dep = Deps[i];
 694         const TraceBlockInfo&DepTBI =
 695           BlockInfo[Dep.DefMI->getParent()->getNumber()];
 696         // Ignore dependencies from outside the current trace.
 697         if (!DepTBI.hasValidDepth() || DepTBI.Head != TBI.Head)
 698           continue;
 699         assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency");
 700         unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;
 701         // Add latency if DefMI is a real instruction. Transients get latency 0.
 702         if (!Dep.DefMI->isTransient())
 703           DepCycle += MTM.TII->computeOperandLatency(MTM.ItinData,
 704                                                      Dep.DefMI, Dep.DefOp,
 705                                                      UseMI, Dep.UseOp,
 706                                                      /* FindMin = */ false);
 707         Cycle = std::max(Cycle, DepCycle);
 708       }
 709       // Remember the instruction depth.
 710       Cycles[UseMI].Depth = Cycle;
 711       DEBUG(dbgs() << Cycle << '\t' << *UseMI);
 712     }
 713   }
 714 }
 715
 716 MachineTraceMetrics::Trace
 717 MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) {
 718   // FIXME: Check cache tags, recompute as needed.
 719   computeTrace(MBB);
 720   computeInstrDepths(MBB);
 721   return Trace(*this, BlockInfo[MBB->getNumber()]);
 722 }
 723
 724 void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const {
 725   OS << getName() << " ensemble:\n";
 726   for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
 727     OS << "  BB#" << i << '\t';
 728     BlockInfo[i].print(OS);
 729     OS << '\n';
 730   }
 731 }
 732
 733 void MachineTraceMetrics::TraceBlockInfo::print(raw_ostream &OS) const {
 734   if (hasValidDepth()) {
 735     OS << "depth=" << InstrDepth;
 736     if (Pred)
 737       OS << " pred=BB#" << Pred->getNumber();
 738     else
 739       OS << " pred=null";
 740     OS << " head=BB#" << Head;
 741     if (HasValidInstrDepths)
 742       OS << " +instrs";
 743   } else
 744     OS << "depth invalid";
 745   OS << ", ";
 746   if (hasValidHeight()) {
 747     OS << "height=" << InstrHeight;
 748     if (Succ)
 749       OS << " succ=BB#" << Succ->getNumber();
 750     else
 751       OS << " succ=null";
 752     OS << " tail=BB#" << Tail;
 753     if (HasValidInstrHeights)
 754       OS << " +instrs";
 755   } else
 756     OS << "height invalid";
 757 }
 758
 759 void MachineTraceMetrics::Trace::print(raw_ostream &OS) const {
 760   unsigned MBBNum = &TBI - &TE.BlockInfo[0];
 761
 762   OS << TE.getName() << " trace BB#" << TBI.Head << " --> BB#" << MBBNum
 763      << " --> BB#" << TBI.Tail << ':';
 764   if (TBI.hasValidHeight() && TBI.hasValidDepth())
 765     OS << ' ' << getInstrCount() << " instrs.";
 766
 767   const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
 768   OS << "\nBB#" << MBBNum;
 769   while (Block->hasValidDepth() && Block->Pred) {
 770     unsigned Num = Block->Pred->getNumber();
 771     OS << " <- BB#" << Num;
 772     Block = &TE.BlockInfo[Num];
 773   }
 774
 775   Block = &TBI;
 776   OS << "\n    ";
 777   while (Block->hasValidHeight() && Block->Succ) {
 778     unsigned Num = Block->Succ->getNumber();
 779     OS << " -> BB#" << Num;
 780     Block = &TE.BlockInfo[Num];
 781   }
 782   OS << '\n';
 783 }