LLVM  16.0.0git
MachineTraceMetrics.cpp
Go to the documentation of this file.
1 //===- lib/CodeGen/MachineTraceMetrics.cpp --------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/DenseMap.h"
12 #include "llvm/ADT/Optional.h"
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/SparseSet.h"
27 #include "llvm/InitializePasses.h"
28 #include "llvm/MC/MCRegisterInfo.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/Format.h"
34 #include <algorithm>
35 #include <cassert>
36 #include <iterator>
37 #include <tuple>
38 #include <utility>
39 
40 using namespace llvm;
41 
42 #define DEBUG_TYPE "machine-trace-metrics"
43 
45 
47 
49  "Machine Trace Metrics", false, true)
54 
56  std::fill(std::begin(Ensembles), std::end(Ensembles), nullptr);
57 }
58 
60  AU.setPreservesAll();
64 }
65 
67  MF = &Func;
68  const TargetSubtargetInfo &ST = MF->getSubtarget();
69  TII = ST.getInstrInfo();
70  TRI = ST.getRegisterInfo();
71  MRI = &MF->getRegInfo();
72  Loops = &getAnalysis<MachineLoopInfo>();
73  SchedModel.init(&ST);
74  BlockInfo.resize(MF->getNumBlockIDs());
75  ProcResourceCycles.resize(MF->getNumBlockIDs() *
76  SchedModel.getNumProcResourceKinds());
77  return false;
78 }
79 
81  MF = nullptr;
82  BlockInfo.clear();
83  for (Ensemble *&E : Ensembles) {
84  delete E;
85  E = nullptr;
86  }
87 }
88 
89 //===----------------------------------------------------------------------===//
90 // Fixed block information
91 //===----------------------------------------------------------------------===//
92 //
93 // The number of instructions in a basic block and the CPU resources used by
94 // those instructions don't depend on any given trace strategy.
95 
96 /// Compute the resource usage in basic block MBB.
99  assert(MBB && "No basic block");
100  FixedBlockInfo *FBI = &BlockInfo[MBB->getNumber()];
101  if (FBI->hasResources())
102  return FBI;
103 
104  // Compute resource usage in the block.
105  FBI->HasCalls = false;
106  unsigned InstrCount = 0;
107 
108  // Add up per-processor resource cycles as well.
109  unsigned PRKinds = SchedModel.getNumProcResourceKinds();
110  SmallVector<unsigned, 32> PRCycles(PRKinds);
111 
112  for (const auto &MI : *MBB) {
113  if (MI.isTransient())
114  continue;
115  ++InstrCount;
116  if (MI.isCall())
117  FBI->HasCalls = true;
118 
119  // Count processor resources used.
120  if (!SchedModel.hasInstrSchedModel())
121  continue;
122  const MCSchedClassDesc *SC = SchedModel.resolveSchedClass(&MI);
123  if (!SC->isValid())
124  continue;
125 
127  PI = SchedModel.getWriteProcResBegin(SC),
128  PE = SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) {
129  assert(PI->ProcResourceIdx < PRKinds && "Bad processor resource kind");
130  PRCycles[PI->ProcResourceIdx] += PI->Cycles;
131  }
132  }
133  FBI->InstrCount = InstrCount;
134 
135  // Scale the resource cycles so they are comparable.
136  unsigned PROffset = MBB->getNumber() * PRKinds;
137  for (unsigned K = 0; K != PRKinds; ++K)
138  ProcResourceCycles[PROffset + K] =
139  PRCycles[K] * SchedModel.getResourceFactor(K);
140 
141  return FBI;
142 }
143 
146  assert(BlockInfo[MBBNum].hasResources() &&
147  "getResources() must be called before getProcResourceCycles()");
148  unsigned PRKinds = SchedModel.getNumProcResourceKinds();
149  assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size());
150  return makeArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, PRKinds);
151 }
152 
153 //===----------------------------------------------------------------------===//
154 // Ensemble utility functions
155 //===----------------------------------------------------------------------===//
156 
158  : MTM(*ct) {
159  BlockInfo.resize(MTM.BlockInfo.size());
160  unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();
161  ProcResourceDepths.resize(MTM.BlockInfo.size() * PRKinds);
162  ProcResourceHeights.resize(MTM.BlockInfo.size() * PRKinds);
163 }
164 
165 // Virtual destructor serves as an anchor.
167 
168 const MachineLoop*
170  return MTM.Loops->getLoopFor(MBB);
171 }
172 
173 // Update resource-related information in the TraceBlockInfo for MBB.
174 // Only update resources related to the trace above MBB.
175 void MachineTraceMetrics::Ensemble::
176 computeDepthResources(const MachineBasicBlock *MBB) {
177  TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
178  unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();
179  unsigned PROffset = MBB->getNumber() * PRKinds;
180 
181  // Compute resources from trace above. The top block is simple.
182  if (!TBI->Pred) {
183  TBI->InstrDepth = 0;
184  TBI->Head = MBB->getNumber();
185  std::fill(ProcResourceDepths.begin() + PROffset,
186  ProcResourceDepths.begin() + PROffset + PRKinds, 0);
187  return;
188  }
189 
190  // Compute from the block above. A post-order traversal ensures the
191  // predecessor is always computed first.
192  unsigned PredNum = TBI->Pred->getNumber();
193  TraceBlockInfo *PredTBI = &BlockInfo[PredNum];
194  assert(PredTBI->hasValidDepth() && "Trace above has not been computed yet");
195  const FixedBlockInfo *PredFBI = MTM.getResources(TBI->Pred);
196  TBI->InstrDepth = PredTBI->InstrDepth + PredFBI->InstrCount;
197  TBI->Head = PredTBI->Head;
198 
199  // Compute per-resource depths.
200  ArrayRef<unsigned> PredPRDepths = getProcResourceDepths(PredNum);
201  ArrayRef<unsigned> PredPRCycles = MTM.getProcResourceCycles(PredNum);
202  for (unsigned K = 0; K != PRKinds; ++K)
203  ProcResourceDepths[PROffset + K] = PredPRDepths[K] + PredPRCycles[K];
204 }
205 
206 // Update resource-related information in the TraceBlockInfo for MBB.
207 // Only update resources related to the trace below MBB.
208 void MachineTraceMetrics::Ensemble::
209 computeHeightResources(const MachineBasicBlock *MBB) {
210  TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
211  unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();
212  unsigned PROffset = MBB->getNumber() * PRKinds;
213 
214  // Compute resources for the current block.
215  TBI->InstrHeight = MTM.getResources(MBB)->InstrCount;
216  ArrayRef<unsigned> PRCycles = MTM.getProcResourceCycles(MBB->getNumber());
217 
218  // The trace tail is done.
219  if (!TBI->Succ) {
220  TBI->Tail = MBB->getNumber();
221  llvm::copy(PRCycles, ProcResourceHeights.begin() + PROffset);
222  return;
223  }
224 
225  // Compute from the block below. A post-order traversal ensures the
226  // predecessor is always computed first.
227  unsigned SuccNum = TBI->Succ->getNumber();
228  TraceBlockInfo *SuccTBI = &BlockInfo[SuccNum];
229  assert(SuccTBI->hasValidHeight() && "Trace below has not been computed yet");
230  TBI->InstrHeight += SuccTBI->InstrHeight;
231  TBI->Tail = SuccTBI->Tail;
232 
233  // Compute per-resource heights.
234  ArrayRef<unsigned> SuccPRHeights = getProcResourceHeights(SuccNum);
235  for (unsigned K = 0; K != PRKinds; ++K)
236  ProcResourceHeights[PROffset + K] = SuccPRHeights[K] + PRCycles[K];
237 }
238 
239 // Check if depth resources for MBB are valid and return the TBI.
240 // Return NULL if the resources have been invalidated.
244  const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
245  return TBI->hasValidDepth() ? TBI : nullptr;
246 }
247 
248 // Check if height resources for MBB are valid and return the TBI.
249 // Return NULL if the resources have been invalidated.
253  const TraceBlockInfo *TBI = &BlockInfo[MBB->getNumber()];
254  return TBI->hasValidHeight() ? TBI : nullptr;
255 }
256 
257 /// Get an array of processor resource depths for MBB. Indexed by processor
258 /// resource kind, this array contains the scaled processor resources consumed
259 /// by all blocks preceding MBB in its trace. It does not include instructions
260 /// in MBB.
261 ///
262 /// Compare TraceBlockInfo::InstrDepth.
265 getProcResourceDepths(unsigned MBBNum) const {
266  unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();
267  assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size());
268  return makeArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds);
269 }
270 
271 /// Get an array of processor resource heights for MBB. Indexed by processor
272 /// resource kind, this array contains the scaled processor resources consumed
273 /// by this block and all blocks following it in its trace.
274 ///
275 /// Compare TraceBlockInfo::InstrHeight.
278 getProcResourceHeights(unsigned MBBNum) const {
279  unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds();
280  assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size());
281  return makeArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds);
282 }
283 
284 //===----------------------------------------------------------------------===//
285 // Trace Selection Strategies
286 //===----------------------------------------------------------------------===//
287 //
288 // A trace selection strategy is implemented as a sub-class of Ensemble. The
289 // trace through a block B is computed by two DFS traversals of the CFG
290 // starting from B. One upwards, and one downwards. During the upwards DFS,
291 // pickTracePred() is called on the post-ordered blocks. During the downwards
292 // DFS, pickTraceSucc() is called in a post-order.
293 //
294 
295 // We never allow traces that leave loops, but we do allow traces to enter
296 // nested loops. We also never allow traces to contain back-edges.
297 //
298 // This means that a loop header can never appear above the center block of a
299 // trace, except as the trace head. Below the center block, loop exiting edges
300 // are banned.
301 //
302 // Return true if an edge from the From loop to the To loop is leaving a loop.
303 // Either of To and From can be null.
304 static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To) {
305  return From && !From->contains(To);
306 }
307 
308 // MinInstrCountEnsemble - Pick the trace that executes the least number of
309 // instructions.
310 namespace {
311 
312 class MinInstrCountEnsemble : public MachineTraceMetrics::Ensemble {
313  const char *getName() const override { return "MinInstr"; }
314  const MachineBasicBlock *pickTracePred(const MachineBasicBlock*) override;
315  const MachineBasicBlock *pickTraceSucc(const MachineBasicBlock*) override;
316 
317 public:
318  MinInstrCountEnsemble(MachineTraceMetrics *mtm)
319  : MachineTraceMetrics::Ensemble(mtm) {}
320 };
321 
322 } // end anonymous namespace
323 
324 // Select the preferred predecessor for MBB.
325 const MachineBasicBlock*
326 MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) {
327  if (MBB->pred_empty())
328  return nullptr;
329  const MachineLoop *CurLoop = getLoopFor(MBB);
330  // Don't leave loops, and never follow back-edges.
331  if (CurLoop && MBB == CurLoop->getHeader())
332  return nullptr;
333  unsigned CurCount = MTM.getResources(MBB)->InstrCount;
334  const MachineBasicBlock *Best = nullptr;
335  unsigned BestDepth = 0;
336  for (const MachineBasicBlock *Pred : MBB->predecessors()) {
337  const MachineTraceMetrics::TraceBlockInfo *PredTBI =
338  getDepthResources(Pred);
339  // Ignore cycles that aren't natural loops.
340  if (!PredTBI)
341  continue;
342  // Pick the predecessor that would give this block the smallest InstrDepth.
343  unsigned Depth = PredTBI->InstrDepth + CurCount;
344  if (!Best || Depth < BestDepth) {
345  Best = Pred;
346  BestDepth = Depth;
347  }
348  }
349  return Best;
350 }
351 
352 // Select the preferred successor for MBB.
353 const MachineBasicBlock*
354 MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) {
355  if (MBB->succ_empty())
356  return nullptr;
357  const MachineLoop *CurLoop = getLoopFor(MBB);
358  const MachineBasicBlock *Best = nullptr;
359  unsigned BestHeight = 0;
360  for (const MachineBasicBlock *Succ : MBB->successors()) {
361  // Don't consider back-edges.
362  if (CurLoop && Succ == CurLoop->getHeader())
363  continue;
364  // Don't consider successors exiting CurLoop.
365  if (isExitingLoop(CurLoop, getLoopFor(Succ)))
366  continue;
367  const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
368  getHeightResources(Succ);
369  // Ignore cycles that aren't natural loops.
370  if (!SuccTBI)
371  continue;
372  // Pick the successor that would give this block the smallest InstrHeight.
373  unsigned Height = SuccTBI->InstrHeight;
374  if (!Best || Height < BestHeight) {
375  Best = Succ;
376  BestHeight = Height;
377  }
378  }
379  return Best;
380 }
381 
382 // Get an Ensemble sub-class for the requested trace strategy.
385  assert(strategy < TS_NumStrategies && "Invalid trace strategy enum");
386  Ensemble *&E = Ensembles[strategy];
387  if (E)
388  return E;
389 
390  // Allocate new Ensemble on demand.
391  switch (strategy) {
392  case TS_MinInstrCount: return (E = new MinInstrCountEnsemble(this));
393  default: llvm_unreachable("Invalid trace strategy enum");
394  }
395 }
396 
398  LLVM_DEBUG(dbgs() << "Invalidate traces through " << printMBBReference(*MBB)
399  << '\n');
400  BlockInfo[MBB->getNumber()].invalidate();
401  for (Ensemble *E : Ensembles)
402  if (E)
403  E->invalidate(MBB);
404 }
405 
407  if (!MF)
408  return;
409 #ifndef NDEBUG
410  assert(BlockInfo.size() == MF->getNumBlockIDs() && "Outdated BlockInfo size");
411  for (Ensemble *E : Ensembles)
412  if (E)
413  E->verify();
414 #endif
415 }
416 
417 //===----------------------------------------------------------------------===//
418 // Trace building
419 //===----------------------------------------------------------------------===//
420 //
421 // Traces are built by two CFG traversals. To avoid recomputing too much, use a
422 // set abstraction that confines the search to the current loop, and doesn't
423 // revisit blocks.
424 
425 namespace {
426 
427 struct LoopBounds {
430  const MachineLoopInfo *Loops;
431  bool Downward = false;
432 
434  const MachineLoopInfo *loops) : Blocks(blocks), Loops(loops) {}
435 };
436 
437 } // end anonymous namespace
438 
439 // Specialize po_iterator_storage in order to prune the post-order traversal so
440 // it is limited to the current loop and doesn't traverse the loop back edges.
441 namespace llvm {
442 
443 template<>
444 class po_iterator_storage<LoopBounds, true> {
445  LoopBounds &LB;
446 
447 public:
448  po_iterator_storage(LoopBounds &lb) : LB(lb) {}
449 
451 
453  const MachineBasicBlock *To) {
454  // Skip already visited To blocks.
455  MachineTraceMetrics::TraceBlockInfo &TBI = LB.Blocks[To->getNumber()];
456  if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
457  return false;
458  // From is null once when To is the trace center block.
459  if (From) {
460  if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(*From)) {
461  // Don't follow backedges, don't leave FromLoop when going upwards.
462  if ((LB.Downward ? To : *From) == FromLoop->getHeader())
463  return false;
464  // Don't leave FromLoop.
465  if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
466  return false;
467  }
468  }
469  // To is a new block. Mark the block as visited in case the CFG has cycles
470  // that MachineLoopInfo didn't recognize as a natural loop.
471  return LB.Visited.insert(To).second;
472  }
473 };
474 
475 } // end namespace llvm
476 
477 /// Compute the trace through MBB.
478 void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) {
479  LLVM_DEBUG(dbgs() << "Computing " << getName() << " trace through "
480  << printMBBReference(*MBB) << '\n');
481  // Set up loop bounds for the backwards post-order traversal.
482  LoopBounds Bounds(BlockInfo, MTM.Loops);
483 
484  // Run an upwards post-order search for the trace start.
485  Bounds.Downward = false;
486  Bounds.Visited.clear();
487  for (const auto *I : inverse_post_order_ext(MBB, Bounds)) {
488  LLVM_DEBUG(dbgs() << " pred for " << printMBBReference(*I) << ": ");
489  TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
490  // All the predecessors have been visited, pick the preferred one.
491  TBI.Pred = pickTracePred(I);
492  LLVM_DEBUG({
493  if (TBI.Pred)
494  dbgs() << printMBBReference(*TBI.Pred) << '\n';
495  else
496  dbgs() << "null\n";
497  });
498  // The trace leading to I is now known, compute the depth resources.
499  computeDepthResources(I);
500  }
501 
502  // Run a downwards post-order search for the trace end.
503  Bounds.Downward = true;
504  Bounds.Visited.clear();
505  for (const auto *I : post_order_ext(MBB, Bounds)) {
506  LLVM_DEBUG(dbgs() << " succ for " << printMBBReference(*I) << ": ");
507  TraceBlockInfo &TBI = BlockInfo[I->getNumber()];
508  // All the successors have been visited, pick the preferred one.
509  TBI.Succ = pickTraceSucc(I);
510  LLVM_DEBUG({
511  if (TBI.Succ)
512  dbgs() << printMBBReference(*TBI.Succ) << '\n';
513  else
514  dbgs() << "null\n";
515  });
516  // The trace leaving I is now known, compute the height resources.
517  computeHeightResources(I);
518  }
519 }
520 
521 /// Invalidate traces through BadMBB.
522 void
525  TraceBlockInfo &BadTBI = BlockInfo[BadMBB->getNumber()];
526 
527  // Invalidate height resources of blocks above MBB.
528  if (BadTBI.hasValidHeight()) {
529  BadTBI.invalidateHeight();
530  WorkList.push_back(BadMBB);
531  do {
532  const MachineBasicBlock *MBB = WorkList.pop_back_val();
533  LLVM_DEBUG(dbgs() << "Invalidate " << printMBBReference(*MBB) << ' '
534  << getName() << " height.\n");
535  // Find any MBB predecessors that have MBB as their preferred successor.
536  // They are the only ones that need to be invalidated.
537  for (const MachineBasicBlock *Pred : MBB->predecessors()) {
538  TraceBlockInfo &TBI = BlockInfo[Pred->getNumber()];
539  if (!TBI.hasValidHeight())
540  continue;
541  if (TBI.Succ == MBB) {
542  TBI.invalidateHeight();
543  WorkList.push_back(Pred);
544  continue;
545  }
546  // Verify that TBI.Succ is actually a *I successor.
547  assert((!TBI.Succ || Pred->isSuccessor(TBI.Succ)) && "CFG changed");
548  }
549  } while (!WorkList.empty());
550  }
551 
552  // Invalidate depth resources of blocks below MBB.
553  if (BadTBI.hasValidDepth()) {
554  BadTBI.invalidateDepth();
555  WorkList.push_back(BadMBB);
556  do {
557  const MachineBasicBlock *MBB = WorkList.pop_back_val();
558  LLVM_DEBUG(dbgs() << "Invalidate " << printMBBReference(*MBB) << ' '
559  << getName() << " depth.\n");
560  // Find any MBB successors that have MBB as their preferred predecessor.
561  // They are the only ones that need to be invalidated.
562  for (const MachineBasicBlock *Succ : MBB->successors()) {
563  TraceBlockInfo &TBI = BlockInfo[Succ->getNumber()];
564  if (!TBI.hasValidDepth())
565  continue;
566  if (TBI.Pred == MBB) {
567  TBI.invalidateDepth();
568  WorkList.push_back(Succ);
569  continue;
570  }
571  // Verify that TBI.Pred is actually a *I predecessor.
572  assert((!TBI.Pred || Succ->isPredecessor(TBI.Pred)) && "CFG changed");
573  }
574  } while (!WorkList.empty());
575  }
576 
577  // Clear any per-instruction data. We only have to do this for BadMBB itself
578  // because the instructions in that block may change. Other blocks may be
579  // invalidated, but their instructions will stay the same, so there is no
580  // need to erase the Cycle entries. They will be overwritten when we
581  // recompute.
582  for (const auto &I : *BadMBB)
583  Cycles.erase(&I);
584 }
585 
587 #ifndef NDEBUG
588  assert(BlockInfo.size() == MTM.MF->getNumBlockIDs() &&
589  "Outdated BlockInfo size");
590  for (unsigned Num = 0, e = BlockInfo.size(); Num != e; ++Num) {
591  const TraceBlockInfo &TBI = BlockInfo[Num];
592  if (TBI.hasValidDepth() && TBI.Pred) {
593  const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num);
594  assert(MBB->isPredecessor(TBI.Pred) && "CFG doesn't match trace");
595  assert(BlockInfo[TBI.Pred->getNumber()].hasValidDepth() &&
596  "Trace is broken, depth should have been invalidated.");
597  const MachineLoop *Loop = getLoopFor(MBB);
598  assert(!(Loop && MBB == Loop->getHeader()) && "Trace contains backedge");
599  }
600  if (TBI.hasValidHeight() && TBI.Succ) {
601  const MachineBasicBlock *MBB = MTM.MF->getBlockNumbered(Num);
602  assert(MBB->isSuccessor(TBI.Succ) && "CFG doesn't match trace");
603  assert(BlockInfo[TBI.Succ->getNumber()].hasValidHeight() &&
604  "Trace is broken, height should have been invalidated.");
605  const MachineLoop *Loop = getLoopFor(MBB);
606  const MachineLoop *SuccLoop = getLoopFor(TBI.Succ);
607  assert(!(Loop && Loop == SuccLoop && TBI.Succ == Loop->getHeader()) &&
608  "Trace contains backedge");
609  }
610  }
611 #endif
612 }
613 
614 //===----------------------------------------------------------------------===//
615 // Data Dependencies
616 //===----------------------------------------------------------------------===//
617 //
618 // Compute the depth and height of each instruction based on data dependencies
619 // and instruction latencies. These cycle numbers assume that the CPU can issue
620 // an infinite number of instructions per cycle as long as their dependencies
621 // are ready.
622 
623 // A data dependency is represented as a defining MI and operand numbers on the
624 // defining and using MI.
625 namespace {
626 
627 struct DataDep {
628  const MachineInstr *DefMI;
629  unsigned DefOp;
630  unsigned UseOp;
631 
632  DataDep(const MachineInstr *DefMI, unsigned DefOp, unsigned UseOp)
633  : DefMI(DefMI), DefOp(DefOp), UseOp(UseOp) {}
634 
635  /// Create a DataDep from an SSA form virtual register.
636  DataDep(const MachineRegisterInfo *MRI, unsigned VirtReg, unsigned UseOp)
637  : UseOp(UseOp) {
640  assert(!DefI.atEnd() && "Register has no defs");
641  DefMI = DefI->getParent();
642  DefOp = DefI.getOperandNo();
643  assert((++DefI).atEnd() && "Register has multiple defs");
644  }
645 };
646 
647 } // end anonymous namespace
648 
649 // Get the input data dependencies that must be ready before UseMI can issue.
650 // Return true if UseMI has any physreg operands.
651 static bool getDataDeps(const MachineInstr &UseMI,
653  const MachineRegisterInfo *MRI) {
654  // Debug values should not be included in any calculations.
655  if (UseMI.isDebugInstr())
656  return false;
657 
658  bool HasPhysRegs = false;
659  for (MachineInstr::const_mop_iterator I = UseMI.operands_begin(),
660  E = UseMI.operands_end(); I != E; ++I) {
661  const MachineOperand &MO = *I;
662  if (!MO.isReg())
663  continue;
664  Register Reg = MO.getReg();
665  if (!Reg)
666  continue;
668  HasPhysRegs = true;
669  continue;
670  }
671  // Collect virtual register reads.
672  if (MO.readsReg())
673  Deps.push_back(DataDep(MRI, Reg, UseMI.getOperandNo(I)));
674  }
675  return HasPhysRegs;
676 }
677 
678 // Get the input data dependencies of a PHI instruction, using Pred as the
679 // preferred predecessor.
680 // This will add at most one dependency to Deps.
681 static void getPHIDeps(const MachineInstr &UseMI,
683  const MachineBasicBlock *Pred,
684  const MachineRegisterInfo *MRI) {
685  // No predecessor at the beginning of a trace. Ignore dependencies.
686  if (!Pred)
687  return;
688  assert(UseMI.isPHI() && UseMI.getNumOperands() % 2 && "Bad PHI");
689  for (unsigned i = 1; i != UseMI.getNumOperands(); i += 2) {
690  if (UseMI.getOperand(i + 1).getMBB() == Pred) {
691  Register Reg = UseMI.getOperand(i).getReg();
692  Deps.push_back(DataDep(MRI, Reg, i));
693  return;
694  }
695  }
696 }
697 
698 // Identify physreg dependencies for UseMI, and update the live regunit
699 // tracking set when scanning instructions downwards.
702  SparseSet<LiveRegUnit> &RegUnits,
703  const TargetRegisterInfo *TRI) {
705  SmallVector<unsigned, 8> LiveDefOps;
706 
708  ME = UseMI->operands_end(); MI != ME; ++MI) {
709  const MachineOperand &MO = *MI;
710  if (!MO.isReg() || !MO.getReg().isPhysical())
711  continue;
712  MCRegister Reg = MO.getReg().asMCReg();
713  // Track live defs and kills for updating RegUnits.
714  if (MO.isDef()) {
715  if (MO.isDead())
716  Kills.push_back(Reg);
717  else
718  LiveDefOps.push_back(UseMI->getOperandNo(MI));
719  } else if (MO.isKill())
720  Kills.push_back(Reg);
721  // Identify dependencies.
722  if (!MO.readsReg())
723  continue;
724  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
725  SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units);
726  if (I == RegUnits.end())
727  continue;
728  Deps.push_back(DataDep(I->MI, I->Op, UseMI->getOperandNo(MI)));
729  break;
730  }
731  }
732 
733  // Update RegUnits to reflect live registers after UseMI.
734  // First kills.
735  for (MCRegister Kill : Kills)
736  for (MCRegUnitIterator Units(Kill, TRI); Units.isValid(); ++Units)
737  RegUnits.erase(*Units);
738 
739  // Second, live defs.
740  for (unsigned DefOp : LiveDefOps) {
741  for (MCRegUnitIterator Units(UseMI->getOperand(DefOp).getReg().asMCReg(),
742  TRI);
743  Units.isValid(); ++Units) {
744  LiveRegUnit &LRU = RegUnits[*Units];
745  LRU.MI = UseMI;
746  LRU.Op = DefOp;
747  }
748  }
749 }
750 
751 /// The length of the critical path through a trace is the maximum of two path
752 /// lengths:
753 ///
754 /// 1. The maximum height+depth over all instructions in the trace center block.
755 ///
756 /// 2. The longest cross-block dependency chain. For small blocks, it is
757 /// possible that the critical path through the trace doesn't include any
758 /// instructions in the block.
759 ///
760 /// This function computes the second number from the live-in list of the
761 /// center block.
762 unsigned MachineTraceMetrics::Ensemble::
763 computeCrossBlockCriticalPath(const TraceBlockInfo &TBI) {
764  assert(TBI.HasValidInstrDepths && "Missing depth info");
765  assert(TBI.HasValidInstrHeights && "Missing height info");
766  unsigned MaxLen = 0;
767  for (const LiveInReg &LIR : TBI.LiveIns) {
768  if (!LIR.Reg.isVirtual())
769  continue;
770  const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg);
771  // Ignore dependencies outside the current trace.
772  const TraceBlockInfo &DefTBI = BlockInfo[DefMI->getParent()->getNumber()];
773  if (!DefTBI.isUsefulDominator(TBI))
774  continue;
775  unsigned Len = LIR.Height + Cycles[DefMI].Depth;
776  MaxLen = std::max(MaxLen, Len);
777  }
778  return MaxLen;
779 }
780 
783  SparseSet<LiveRegUnit> &RegUnits) {
785  // Collect all data dependencies.
786  if (UseMI.isPHI())
787  getPHIDeps(UseMI, Deps, TBI.Pred, MTM.MRI);
788  else if (getDataDeps(UseMI, Deps, MTM.MRI))
789  updatePhysDepsDownwards(&UseMI, Deps, RegUnits, MTM.TRI);
790 
791  // Filter and process dependencies, computing the earliest issue cycle.
792  unsigned Cycle = 0;
793  for (const DataDep &Dep : Deps) {
794  const TraceBlockInfo&DepTBI =
795  BlockInfo[Dep.DefMI->getParent()->getNumber()];
796  // Ignore dependencies from outside the current trace.
797  if (!DepTBI.isUsefulDominator(TBI))
798  continue;
799  assert(DepTBI.HasValidInstrDepths && "Inconsistent dependency");
800  unsigned DepCycle = Cycles.lookup(Dep.DefMI).Depth;
801  // Add latency if DefMI is a real instruction. Transients get latency 0.
802  if (!Dep.DefMI->isTransient())
803  DepCycle += MTM.SchedModel
804  .computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI, Dep.UseOp);
805  Cycle = std::max(Cycle, DepCycle);
806  }
807  // Remember the instruction depth.
808  InstrCycles &MICycles = Cycles[&UseMI];
809  MICycles.Depth = Cycle;
810 
811  if (TBI.HasValidInstrHeights) {
812  // Update critical path length.
813  TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height);
814  LLVM_DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI);
815  } else {
816  LLVM_DEBUG(dbgs() << Cycle << '\t' << UseMI);
817  }
818 }
819 
822  SparseSet<LiveRegUnit> &RegUnits) {
823  updateDepth(BlockInfo[MBB->getNumber()], UseMI, RegUnits);
824 }
825 
829  SparseSet<LiveRegUnit> &RegUnits) {
830  for (; Start != End; Start++)
831  updateDepth(Start->getParent(), *Start, RegUnits);
832 }
833 
834 /// Compute instruction depths for all instructions above or in MBB in its
835 /// trace. This assumes that the trace through MBB has already been computed.
836 void MachineTraceMetrics::Ensemble::
837 computeInstrDepths(const MachineBasicBlock *MBB) {
838  // The top of the trace may already be computed, and HasValidInstrDepths
839  // implies Head->HasValidInstrDepths, so we only need to start from the first
840  // block in the trace that needs to be recomputed.
842  do {
843  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
844  assert(TBI.hasValidDepth() && "Incomplete trace");
845  if (TBI.HasValidInstrDepths)
846  break;
847  Stack.push_back(MBB);
848  MBB = TBI.Pred;
849  } while (MBB);
850 
851  // FIXME: If MBB is non-null at this point, it is the last pre-computed block
852  // in the trace. We should track any live-out physregs that were defined in
853  // the trace. This is quite rare in SSA form, typically created by CSE
854  // hoisting a compare.
855  SparseSet<LiveRegUnit> RegUnits;
856  RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
857 
858  // Go through trace blocks in top-down order, stopping after the center block.
859  while (!Stack.empty()) {
860  MBB = Stack.pop_back_val();
861  LLVM_DEBUG(dbgs() << "\nDepths for " << printMBBReference(*MBB) << ":\n");
862  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
863  TBI.HasValidInstrDepths = true;
864  TBI.CriticalPath = 0;
865 
866  // Print out resource depths here as well.
867  LLVM_DEBUG({
868  dbgs() << format("%7u Instructions\n", TBI.InstrDepth);
869  ArrayRef<unsigned> PRDepths = getProcResourceDepths(MBB->getNumber());
870  for (unsigned K = 0; K != PRDepths.size(); ++K)
871  if (PRDepths[K]) {
872  unsigned Factor = MTM.SchedModel.getResourceFactor(K);
873  dbgs() << format("%6uc @ ", MTM.getCycles(PRDepths[K]))
874  << MTM.SchedModel.getProcResource(K)->Name << " ("
875  << PRDepths[K]/Factor << " ops x" << Factor << ")\n";
876  }
877  });
878 
879  // Also compute the critical path length through MBB when possible.
880  if (TBI.HasValidInstrHeights)
881  TBI.CriticalPath = computeCrossBlockCriticalPath(TBI);
882 
883  for (const auto &UseMI : *MBB) {
884  updateDepth(TBI, UseMI, RegUnits);
885  }
886  }
887 }
888 
889 // Identify physreg dependencies for MI when scanning instructions upwards.
890 // Return the issue height of MI after considering any live regunits.
891 // Height is the issue height computed from virtual register dependencies alone.
892 static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height,
893  SparseSet<LiveRegUnit> &RegUnits,
894  const TargetSchedModel &SchedModel,
895  const TargetInstrInfo *TII,
896  const TargetRegisterInfo *TRI) {
897  SmallVector<unsigned, 8> ReadOps;
898 
899  for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
900  MOE = MI.operands_end();
901  MOI != MOE; ++MOI) {
902  const MachineOperand &MO = *MOI;
903  if (!MO.isReg())
904  continue;
905  Register Reg = MO.getReg();
907  continue;
908  if (MO.readsReg())
909  ReadOps.push_back(MI.getOperandNo(MOI));
910  if (!MO.isDef())
911  continue;
912  // This is a def of Reg. Remove corresponding entries from RegUnits, and
913  // update MI Height to consider the physreg dependencies.
914  for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
915  ++Units) {
916  SparseSet<LiveRegUnit>::iterator I = RegUnits.find(*Units);
917  if (I == RegUnits.end())
918  continue;
919  unsigned DepHeight = I->Cycle;
920  if (!MI.isTransient()) {
921  // We may not know the UseMI of this dependency, if it came from the
922  // live-in list. SchedModel can handle a NULL UseMI.
923  DepHeight += SchedModel.computeOperandLatency(&MI, MI.getOperandNo(MOI),
924  I->MI, I->Op);
925  }
926  Height = std::max(Height, DepHeight);
927  // This regunit is dead above MI.
928  RegUnits.erase(I);
929  }
930  }
931 
932  // Now we know the height of MI. Update any regunits read.
933  for (size_t I = 0, E = ReadOps.size(); I != E; ++I) {
934  MCRegister Reg = MI.getOperand(ReadOps[I]).getReg().asMCReg();
935  for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) {
936  LiveRegUnit &LRU = RegUnits[*Units];
937  // Set the height to the highest reader of the unit.
938  if (LRU.Cycle <= Height && LRU.MI != &MI) {
939  LRU.Cycle = Height;
940  LRU.MI = &MI;
941  LRU.Op = ReadOps[I];
942  }
943  }
944  }
945 
946  return Height;
947 }
948 
950 
951 // Push the height of DefMI upwards if required to match UseMI.
952 // Return true if this is the first time DefMI was seen.
953 static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI,
954  unsigned UseHeight, MIHeightMap &Heights,
955  const TargetSchedModel &SchedModel,
956  const TargetInstrInfo *TII) {
957  // Adjust height by Dep.DefMI latency.
958  if (!Dep.DefMI->isTransient())
959  UseHeight += SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp, &UseMI,
960  Dep.UseOp);
961 
962  // Update Heights[DefMI] to be the maximum height seen.
964  bool New;
965  std::tie(I, New) = Heights.insert(std::make_pair(Dep.DefMI, UseHeight));
966  if (New)
967  return true;
968 
969  // DefMI has been pushed before. Give it the max height.
970  if (I->second < UseHeight)
971  I->second = UseHeight;
972  return false;
973 }
974 
975 /// Assuming that the virtual register defined by DefMI:DefOp was used by
976 /// Trace.back(), add it to the live-in lists of all the blocks in Trace. Stop
977 /// when reaching the block that contains DefMI.
978 void MachineTraceMetrics::Ensemble::
979 addLiveIns(const MachineInstr *DefMI, unsigned DefOp,
981  assert(!Trace.empty() && "Trace should contain at least one block");
982  Register Reg = DefMI->getOperand(DefOp).getReg();
984  const MachineBasicBlock *DefMBB = DefMI->getParent();
985 
986  // Reg is live-in to all blocks in Trace that follow DefMBB.
987  for (const MachineBasicBlock *MBB : llvm::reverse(Trace)) {
988  if (MBB == DefMBB)
989  return;
990  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
991  // Just add the register. The height will be updated later.
992  TBI.LiveIns.push_back(Reg);
993  }
994 }
995 
996 /// Compute instruction heights in the trace through MBB. This updates MBB and
997 /// the blocks below it in the trace. It is assumed that the trace has already
998 /// been computed.
999 void MachineTraceMetrics::Ensemble::
1000 computeInstrHeights(const MachineBasicBlock *MBB) {
1001  // The bottom of the trace may already be computed.
1002  // Find the blocks that need updating.
1004  do {
1005  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
1006  assert(TBI.hasValidHeight() && "Incomplete trace");
1007  if (TBI.HasValidInstrHeights)
1008  break;
1009  Stack.push_back(MBB);
1010  TBI.LiveIns.clear();
1011  MBB = TBI.Succ;
1012  } while (MBB);
1013 
1014  // As we move upwards in the trace, keep track of instructions that are
1015  // required by deeper trace instructions. Map MI -> height required so far.
1016  MIHeightMap Heights;
1017 
1018  // For physregs, the def isn't known when we see the use.
1019  // Instead, keep track of the highest use of each regunit.
1020  SparseSet<LiveRegUnit> RegUnits;
1021  RegUnits.setUniverse(MTM.TRI->getNumRegUnits());
1022 
1023  // If the bottom of the trace was already precomputed, initialize heights
1024  // from its live-in list.
1025  // MBB is the highest precomputed block in the trace.
1026  if (MBB) {
1027  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
1028  for (LiveInReg &LI : TBI.LiveIns) {
1029  if (LI.Reg.isVirtual()) {
1030  // For virtual registers, the def latency is included.
1031  unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)];
1032  if (Height < LI.Height)
1033  Height = LI.Height;
1034  } else {
1035  // For register units, the def latency is not included because we don't
1036  // know the def yet.
1037  RegUnits[LI.Reg].Cycle = LI.Height;
1038  }
1039  }
1040  }
1041 
1042  // Go through the trace blocks in bottom-up order.
1044  for (;!Stack.empty(); Stack.pop_back()) {
1045  MBB = Stack.back();
1046  LLVM_DEBUG(dbgs() << "Heights for " << printMBBReference(*MBB) << ":\n");
1047  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
1048  TBI.HasValidInstrHeights = true;
1049  TBI.CriticalPath = 0;
1050 
1051  LLVM_DEBUG({
1052  dbgs() << format("%7u Instructions\n", TBI.InstrHeight);
1053  ArrayRef<unsigned> PRHeights = getProcResourceHeights(MBB->getNumber());
1054  for (unsigned K = 0; K != PRHeights.size(); ++K)
1055  if (PRHeights[K]) {
1056  unsigned Factor = MTM.SchedModel.getResourceFactor(K);
1057  dbgs() << format("%6uc @ ", MTM.getCycles(PRHeights[K]))
1058  << MTM.SchedModel.getProcResource(K)->Name << " ("
1059  << PRHeights[K]/Factor << " ops x" << Factor << ")\n";
1060  }
1061  });
1062 
1063  // Get dependencies from PHIs in the trace successor.
1064  const MachineBasicBlock *Succ = TBI.Succ;
1065  // If MBB is the last block in the trace, and it has a back-edge to the
1066  // loop header, get loop-carried dependencies from PHIs in the header. For
1067  // that purpose, pretend that all the loop header PHIs have height 0.
1068  if (!Succ)
1069  if (const MachineLoop *Loop = getLoopFor(MBB))
1070  if (MBB->isSuccessor(Loop->getHeader()))
1071  Succ = Loop->getHeader();
1072 
1073  if (Succ) {
1074  for (const auto &PHI : *Succ) {
1075  if (!PHI.isPHI())
1076  break;
1077  Deps.clear();
1078  getPHIDeps(PHI, Deps, MBB, MTM.MRI);
1079  if (!Deps.empty()) {
1080  // Loop header PHI heights are all 0.
1081  unsigned Height = TBI.Succ ? Cycles.lookup(&PHI).Height : 0;
1082  LLVM_DEBUG(dbgs() << "pred\t" << Height << '\t' << PHI);
1083  if (pushDepHeight(Deps.front(), PHI, Height, Heights, MTM.SchedModel,
1084  MTM.TII))
1085  addLiveIns(Deps.front().DefMI, Deps.front().DefOp, Stack);
1086  }
1087  }
1088  }
1089 
1090  // Go through the block backwards.
1091  for (MachineBasicBlock::const_iterator BI = MBB->end(), BB = MBB->begin();
1092  BI != BB;) {
1093  const MachineInstr &MI = *--BI;
1094 
1095  // Find the MI height as determined by virtual register uses in the
1096  // trace below.
1097  unsigned Cycle = 0;
1098  MIHeightMap::iterator HeightI = Heights.find(&MI);
1099  if (HeightI != Heights.end()) {
1100  Cycle = HeightI->second;
1101  // We won't be seeing any more MI uses.
1102  Heights.erase(HeightI);
1103  }
1104 
1105  // Don't process PHI deps. They depend on the specific predecessor, and
1106  // we'll get them when visiting the predecessor.
1107  Deps.clear();
1108  bool HasPhysRegs = !MI.isPHI() && getDataDeps(MI, Deps, MTM.MRI);
1109 
1110  // There may also be regunit dependencies to include in the height.
1111  if (HasPhysRegs)
1112  Cycle = updatePhysDepsUpwards(MI, Cycle, RegUnits, MTM.SchedModel,
1113  MTM.TII, MTM.TRI);
1114 
1115  // Update the required height of any virtual registers read by MI.
1116  for (const DataDep &Dep : Deps)
1117  if (pushDepHeight(Dep, MI, Cycle, Heights, MTM.SchedModel, MTM.TII))
1118  addLiveIns(Dep.DefMI, Dep.DefOp, Stack);
1119 
1120  InstrCycles &MICycles = Cycles[&MI];
1121  MICycles.Height = Cycle;
1122  if (!TBI.HasValidInstrDepths) {
1123  LLVM_DEBUG(dbgs() << Cycle << '\t' << MI);
1124  continue;
1125  }
1126  // Update critical path length.
1127  TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Depth);
1128  LLVM_DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << MI);
1129  }
1130 
1131  // Update virtual live-in heights. They were added by addLiveIns() with a 0
1132  // height because the final height isn't known until now.
1133  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " Live-ins:");
1134  for (LiveInReg &LIR : TBI.LiveIns) {
1135  const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg);
1136  LIR.Height = Heights.lookup(DefMI);
1137  LLVM_DEBUG(dbgs() << ' ' << printReg(LIR.Reg) << '@' << LIR.Height);
1138  }
1139 
1140  // Transfer the live regunits to the live-in list.
1142  RI = RegUnits.begin(), RE = RegUnits.end(); RI != RE; ++RI) {
1143  TBI.LiveIns.push_back(LiveInReg(RI->RegUnit, RI->Cycle));
1144  LLVM_DEBUG(dbgs() << ' ' << printRegUnit(RI->RegUnit, MTM.TRI) << '@'
1145  << RI->Cycle);
1146  }
1147  LLVM_DEBUG(dbgs() << '\n');
1148 
1149  if (!TBI.HasValidInstrDepths)
1150  continue;
1151  // Add live-ins to the critical path length.
1152  TBI.CriticalPath = std::max(TBI.CriticalPath,
1153  computeCrossBlockCriticalPath(TBI));
1154  LLVM_DEBUG(dbgs() << "Critical path: " << TBI.CriticalPath << '\n');
1155  }
1156 }
1157 
1160  TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()];
1161 
1162  if (!TBI.hasValidDepth() || !TBI.hasValidHeight())
1163  computeTrace(MBB);
1164  if (!TBI.HasValidInstrDepths)
1165  computeInstrDepths(MBB);
1166  if (!TBI.HasValidInstrHeights)
1167  computeInstrHeights(MBB);
1168 
1169  return Trace(*this, TBI);
1170 }
1171 
1172 unsigned
1174  assert(getBlockNum() == unsigned(MI.getParent()->getNumber()) &&
1175  "MI must be in the trace center block");
1176  InstrCycles Cyc = getInstrCycles(MI);
1177  return getCriticalPath() - (Cyc.Depth + Cyc.Height);
1178 }
1179 
1180 unsigned
1182  const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum());
1184  getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI);
1185  assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor");
1186  DataDep &Dep = Deps.front();
1187  unsigned DepCycle = getInstrCycles(*Dep.DefMI).Depth;
1188  // Add latency if DefMI is a real instruction. Transients get latency 0.
1189  if (!Dep.DefMI->isTransient())
1190  DepCycle += TE.MTM.SchedModel.computeOperandLatency(Dep.DefMI, Dep.DefOp,
1191  &PHI, Dep.UseOp);
1192  return DepCycle;
1193 }
1194 
1195 /// When bottom is set include instructions in current block in estimate.
1197  // Find the limiting processor resource.
1198  // Numbers have been pre-scaled to be comparable.
1199  unsigned PRMax = 0;
1200  ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum());
1201  if (Bottom) {
1202  ArrayRef<unsigned> PRCycles = TE.MTM.getProcResourceCycles(getBlockNum());
1203  for (unsigned K = 0; K != PRDepths.size(); ++K)
1204  PRMax = std::max(PRMax, PRDepths[K] + PRCycles[K]);
1205  } else {
1206  for (unsigned PRD : PRDepths)
1207  PRMax = std::max(PRMax, PRD);
1208  }
1209  // Convert to cycle count.
1210  PRMax = TE.MTM.getCycles(PRMax);
1211 
1212  /// All instructions before current block
1213  unsigned Instrs = TBI.InstrDepth;
1214  // plus instructions in current block
1215  if (Bottom)
1216  Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount;
1217  if (unsigned IW = TE.MTM.SchedModel.getIssueWidth())
1218  Instrs /= IW;
1219  // Assume issue width 1 without a schedule model.
1220  return std::max(Instrs, PRMax);
1221 }
1222 
1226  ArrayRef<const MCSchedClassDesc *> RemoveInstrs) const {
1227  // Add up resources above and below the center block.
1228  ArrayRef<unsigned> PRDepths = TE.getProcResourceDepths(getBlockNum());
1229  ArrayRef<unsigned> PRHeights = TE.getProcResourceHeights(getBlockNum());
1230  unsigned PRMax = 0;
1231 
1232  // Capture computing cycles from extra instructions
1233  auto extraCycles = [this](ArrayRef<const MCSchedClassDesc *> Instrs,
1234  unsigned ResourceIdx)
1235  ->unsigned {
1236  unsigned Cycles = 0;
1237  for (const MCSchedClassDesc *SC : Instrs) {
1238  if (!SC->isValid())
1239  continue;
1241  PI = TE.MTM.SchedModel.getWriteProcResBegin(SC),
1242  PE = TE.MTM.SchedModel.getWriteProcResEnd(SC);
1243  PI != PE; ++PI) {
1244  if (PI->ProcResourceIdx != ResourceIdx)
1245  continue;
1246  Cycles +=
1247  (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(ResourceIdx));
1248  }
1249  }
1250  return Cycles;
1251  };
1252 
1253  for (unsigned K = 0; K != PRDepths.size(); ++K) {
1254  unsigned PRCycles = PRDepths[K] + PRHeights[K];
1255  for (const MachineBasicBlock *MBB : Extrablocks)
1256  PRCycles += TE.MTM.getProcResourceCycles(MBB->getNumber())[K];
1257  PRCycles += extraCycles(ExtraInstrs, K);
1258  PRCycles -= extraCycles(RemoveInstrs, K);
1259  PRMax = std::max(PRMax, PRCycles);
1260  }
1261  // Convert to cycle count.
1262  PRMax = TE.MTM.getCycles(PRMax);
1263 
1264  // Instrs: #instructions in current trace outside current block.
1265  unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight;
1266  // Add instruction count from the extra blocks.
1267  for (const MachineBasicBlock *MBB : Extrablocks)
1268  Instrs += TE.MTM.getResources(MBB)->InstrCount;
1269  Instrs += ExtraInstrs.size();
1270  Instrs -= RemoveInstrs.size();
1271  if (unsigned IW = TE.MTM.SchedModel.getIssueWidth())
1272  Instrs /= IW;
1273  // Assume issue width 1 without a schedule model.
1274  return std::max(Instrs, PRMax);
1275 }
1276 
1278  const MachineInstr &UseMI) const {
1279  if (DefMI.getParent() == UseMI.getParent())
1280  return true;
1281 
1282  const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI.getParent()->getNumber()];
1283  const TraceBlockInfo &TBI = TE.BlockInfo[UseMI.getParent()->getNumber()];
1284 
1285  return DepTBI.isUsefulDominator(TBI);
1286 }
1287 
1289  OS << getName() << " ensemble:\n";
1290  for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
1291  OS << " %bb." << i << '\t';
1292  BlockInfo[i].print(OS);
1293  OS << '\n';
1294  }
1295 }
1296 
1298  if (hasValidDepth()) {
1299  OS << "depth=" << InstrDepth;
1300  if (Pred)
1301  OS << " pred=" << printMBBReference(*Pred);
1302  else
1303  OS << " pred=null";
1304  OS << " head=%bb." << Head;
1305  if (HasValidInstrDepths)
1306  OS << " +instrs";
1307  } else
1308  OS << "depth invalid";
1309  OS << ", ";
1310  if (hasValidHeight()) {
1311  OS << "height=" << InstrHeight;
1312  if (Succ)
1313  OS << " succ=" << printMBBReference(*Succ);
1314  else
1315  OS << " succ=null";
1316  OS << " tail=%bb." << Tail;
1317  if (HasValidInstrHeights)
1318  OS << " +instrs";
1319  } else
1320  OS << "height invalid";
1321  if (HasValidInstrDepths && HasValidInstrHeights)
1322  OS << ", crit=" << CriticalPath;
1323 }
1324 
1326  unsigned MBBNum = &TBI - &TE.BlockInfo[0];
1327 
1328  OS << TE.getName() << " trace %bb." << TBI.Head << " --> %bb." << MBBNum
1329  << " --> %bb." << TBI.Tail << ':';
1330  if (TBI.hasValidHeight() && TBI.hasValidDepth())
1331  OS << ' ' << getInstrCount() << " instrs.";
1332  if (TBI.HasValidInstrDepths && TBI.HasValidInstrHeights)
1333  OS << ' ' << TBI.CriticalPath << " cycles.";
1334 
1335  const MachineTraceMetrics::TraceBlockInfo *Block = &TBI;
1336  OS << "\n%bb." << MBBNum;
1337  while (Block->hasValidDepth() && Block->Pred) {
1338  unsigned Num = Block->Pred->getNumber();
1339  OS << " <- " << printMBBReference(*Block->Pred);
1340  Block = &TE.BlockInfo[Num];
1341  }
1342 
1343  Block = &TBI;
1344  OS << "\n ";
1345  while (Block->hasValidHeight() && Block->Succ) {
1346  unsigned Num = Block->Succ->getNumber();
1347  OS << " -> " << printMBBReference(*Block->Succ);
1348  Block = &TE.BlockInfo[Num];
1349  }
1350  OS << '\n';
1351 }
i
i
Definition: README.txt:29
llvm::MachineTraceMetrics::Ensemble
friend class Ensemble
Definition: MachineTraceMetrics.h:96
llvm::post_order_ext
iterator_range< po_ext_iterator< T, SetType > > post_order_ext(const T &G, SetType &S)
Definition: PostOrderIterator.h:211
llvm::MachineTraceMetrics::FixedBlockInfo::hasResources
bool hasResources() const
Returns true when resource information for this block has been computed.
Definition: MachineTraceMetrics.h:123
llvm::TargetSchedModel::getWriteProcResBegin
ProcResIter getWriteProcResBegin(const MCSchedClassDesc *SC) const
Definition: TargetSchedule.h:133
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:20
llvm::SparseSet::iterator
typename DenseT::iterator iterator
Definition: SparseSet.h:171
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm::MachineInstr::getOperandNo
unsigned getOperandNo(const_mop_iterator I) const
Returns the number of the operand iterator I points to.
Definition: MachineInstr.h:706
MachineInstr.h
llvm::SparseSet::const_iterator
typename DenseT::const_iterator const_iterator
Definition: SparseSet.h:172
llvm::MachineRegisterInfo::def_begin
def_iterator def_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:392
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
UseMI
MachineInstrBuilder & UseMI
Definition: AArch64ExpandPseudoInsts.cpp:107
Optional.h
llvm::MachineTraceMetrics::InstrCycles::Depth
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
Definition: MachineTraceMetrics.h:245
llvm::SparseSet::find
iterator find(const KeyT &Key)
find - Find an element by its key.
Definition: SparseSet.h:224
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
llvm::MachineTraceMetrics::TraceBlockInfo
Per-basic block information that relates to a specific trace through the block.
Definition: MachineTraceMetrics.h:155
llvm::MachineTraceMetrics::FixedBlockInfo::InstrCount
unsigned InstrCount
The number of non-trivial instructions in the block.
Definition: MachineTraceMetrics.h:115
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::po_iterator_storage< LoopBounds, true >::insertEdge
bool insertEdge(Optional< const MachineBasicBlock * > From, const MachineBasicBlock *To)
Definition: MachineTraceMetrics.cpp:452
llvm::DenseMapBase::lookup
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:197
Pass.h
llvm::TargetSchedModel::getResourceFactor
unsigned getResourceFactor(unsigned ResIdx) const
Multiply the number of units consumed for a resource by this factor to normalize it relative to other...
Definition: TargetSchedule.h:143
llvm::MachineTraceMetrics::Ensemble::invalidate
void invalidate(const MachineBasicBlock *MBB)
Invalidate traces through BadMBB.
Definition: MachineTraceMetrics.cpp:523
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:374
llvm::MachineTraceMetrics::getResources
const FixedBlockInfo * getResources(const MachineBasicBlock *)
Get the fixed resource information about MBB. Compute it on demand.
Definition: MachineTraceMetrics.cpp:98
llvm::SmallVector< unsigned, 32 >
llvm::Trace::empty
bool empty() const
Definition: Trace.h:96
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
llvm::parallel::strategy
ThreadPoolStrategy strategy
Definition: Parallel.cpp:20
ErrorHandling.h
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::MachineTraceMetrics::Strategy
Strategy
Strategies for selecting traces.
Definition: MachineTraceMetrics.h:377
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::SparseSet::begin
const_iterator begin() const
Definition: SparseSet.h:174
llvm::MachineTraceMetrics::TraceBlockInfo::hasValidHeight
bool hasValidHeight() const
Returns true if the height resources have been computed from the trace below this block.
Definition: MachineTraceMetrics.h:186
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::MachineTraceMetrics::TS_MinInstrCount
@ TS_MinInstrCount
Select the trace through a block that has the fewest instructions.
Definition: MachineTraceMetrics.h:379
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:799
llvm::MachineTraceMetrics::TraceBlockInfo::hasValidDepth
bool hasValidDepth() const
Returns true if the depth resources have been computed from the trace above this block.
Definition: MachineTraceMetrics.h:182
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
InstrCount
static unsigned InstrCount
Definition: DFAPacketizer.cpp:53
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1793
llvm::DenseMapIterator
Definition: DenseMap.h:57
DenseMap.h
llvm::MachineTraceMetrics::FixedBlockInfo
Per-basic block information that doesn't depend on the trace through the block.
Definition: MachineTraceMetrics.h:112
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::MachineTraceMetrics::TraceBlockInfo::Head
unsigned Head
The block number of the head of the trace. (When hasValidDepth()).
Definition: MachineTraceMetrics.h:165
llvm::copy
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1836
llvm::Optional
Definition: APInt.h:33
llvm::SmallPtrSet< const MachineBasicBlock *, 8 >
llvm::MachineInstr::operands_end
mop_iterator operands_end()
Definition: MachineInstr.h:636
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MCWriteProcResEntry
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Definition: MCSchedule.h:63
llvm::addLiveIns
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
Definition: LivePhysRegs.cpp:259
llvm::LiveRegUnit::Op
unsigned Op
Definition: MachineTraceMetrics.h:79
llvm::MachineTraceMetrics::invalidate
void invalidate(const MachineBasicBlock *MBB)
Invalidate cached information about MBB.
Definition: MachineTraceMetrics.cpp:397
Format.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::po_iterator_storage
Default po_iterator_storage implementation with an internal set object.
Definition: PostOrderIterator.h:59
loops
loops
Definition: LoopInfo.cpp:1177
llvm::MachineRegisterInfo::defusechain_iterator::getOperandNo
unsigned getOperandNo() const
getOperandNo - Return the operand # of this MachineOperand in its MachineInstr.
Definition: MachineRegisterInfo.h:1086
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
MachineTraceMetrics.h
llvm::MachineTraceMetrics::Ensemble::getTrace
Trace getTrace(const MachineBasicBlock *MBB)
Get the trace that passes through MBB.
Definition: MachineTraceMetrics.cpp:1159
llvm::TargetSchedModel::init
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
Definition: TargetSchedule.cpp:47
getDataDeps
static bool getDataDeps(const MachineInstr &UseMI, SmallVectorImpl< DataDep > &Deps, const MachineRegisterInfo *MRI)
Definition: MachineTraceMetrics.cpp:651
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineTraceMetrics::Ensemble::Ensemble
Ensemble(MachineTraceMetrics *)
Definition: MachineTraceMetrics.cpp:157
llvm::MachineTraceMetrics::Trace
friend class Trace
Definition: MachineTraceMetrics.h:97
llvm::MachineOperand::isKill
bool isKill() const
Definition: MachineOperand.h:389
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::MachineTraceMetrics::TraceBlockInfo::HasValidInstrHeights
bool HasValidInstrHeights
Instruction heights have been computed. This implies hasValidHeight().
Definition: MachineTraceMetrics.h:223
llvm::MachineTraceMetrics::Ensemble::updateDepths
void updateDepths(MachineBasicBlock::iterator Start, MachineBasicBlock::iterator End, SparseSet< LiveRegUnit > &RegUnits)
Updates the depth of the instructions from Start to End.
Definition: MachineTraceMetrics.cpp:827
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::MachineTraceMetrics::Ensemble::updateDepth
void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, SparseSet< LiveRegUnit > &RegUnits)
Updates the depth of an machine instruction, given RegUnits.
Definition: MachineTraceMetrics.cpp:782
llvm::MachineTraceMetrics::TraceBlockInfo::InstrHeight
unsigned InstrHeight
Accumulated number of instructions in the trace below this block.
Definition: MachineTraceMetrics.h:176
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
MachineLoopInfo.h
llvm::po_iterator_storage< LoopBounds, true >::finishPostorder
void finishPostorder(const MachineBasicBlock *)
Definition: MachineTraceMetrics.cpp:450
llvm::MutableArrayRef
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:28
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:420
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:22
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::MachineTraceMetrics::TraceBlockInfo::isUsefulDominator
bool isUsefulDominator(const TraceBlockInfo &TBI) const
Assuming that this is a dominator of TBI, determine if it contains useful instruction depths.
Definition: MachineTraceMetrics.h:200
llvm::SparseSet::end
const_iterator end() const
Definition: SparseSet.h:175
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineTraceMetrics.cpp:42
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::MachineBasicBlock::isSuccessor
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
Definition: MachineBasicBlock.cpp:924
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:109
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineTraceMetrics::Ensemble::verify
void verify() const
Definition: MachineTraceMetrics.cpp:586
llvm::MachineTraceMetricsID
char & MachineTraceMetricsID
MachineTraceMetrics - This pass computes critical path and CPU resource usage in an ensemble of trace...
Definition: MachineTraceMetrics.cpp:46
false
Definition: StackSlotColoring.cpp:141
llvm::MachineRegisterInfo::defusechain_iterator::atEnd
bool atEnd() const
atEnd - return true if this iterator is equal to reg_end() on the value.
Definition: MachineRegisterInfo.h:1058
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::MachineTraceMetrics::TS_NumStrategies
@ TS_NumStrategies
Definition: MachineTraceMetrics.h:381
llvm::MachineTraceMetrics::getProcResourceCycles
ArrayRef< unsigned > getProcResourceCycles(unsigned MBBNum) const
Get the scaled number of cycles used per processor resource in MBB.
Definition: MachineTraceMetrics.cpp:145
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::MachineTraceMetrics::InstrCycles
InstrCycles represents the cycle height and depth of an instruction in a trace.
Definition: MachineTraceMetrics.h:241
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::SmallVectorImpl::resize
void resize(size_type N)
Definition: SmallVector.h:642
llvm::MachineTraceMetrics::Ensemble::print
void print(raw_ostream &) const
Definition: MachineTraceMetrics.cpp:1288
SmallPtrSet.h
llvm::MachineTraceMetrics::Trace::getResourceDepth
unsigned getResourceDepth(bool Bottom) const
Return the resource depth of the top/bottom of the trace center block.
Definition: MachineTraceMetrics.cpp:1196
llvm::TargetSchedModel::getWriteProcResEnd
ProcResIter getWriteProcResEnd(const MCSchedClassDesc *SC) const
Definition: TargetSchedule.h:137
llvm::MachineTraceMetrics::Trace
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
Definition: MachineTraceMetrics.h:255
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::MachineTraceMetrics::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineTraceMetrics.cpp:59
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineInstrBuilder::getReg
Register getReg(unsigned Idx) const
Get the register for the operand index.
Definition: MachineInstrBuilder.h:94
llvm::omp::RTLDependInfoFields::Len
@ Len
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::MachineTraceMetrics::Ensemble::~Ensemble
virtual ~Ensemble()
llvm::printRegUnit
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
Definition: TargetRegisterInfo.cpp:142
llvm::MachineTraceMetrics::Trace::isDepInTrace
bool isDepInTrace(const MachineInstr &DefMI, const MachineInstr &UseMI) const
A dependence is useful if the basic block of the defining instruction is part of the trace of the use...
Definition: MachineTraceMetrics.cpp:1277
llvm::TargetSchedModel::resolveSchedClass
const MCSchedClassDesc * resolveSchedClass(const MachineInstr *MI) const
Return the MCSchedClassDesc for this instruction.
Definition: TargetSchedule.cpp:117
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::MachineTraceMetrics::getEnsemble
Ensemble * getEnsemble(Strategy)
Get the trace ensemble representing the given trace selection strategy.
Definition: MachineTraceMetrics.cpp:384
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
TargetSchedule.h
llvm::TargetSchedModel
Provide an instruction scheduling machine model to CodeGen passes.
Definition: TargetSchedule.h:30
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::MachineTraceMetrics::TraceBlockInfo::InstrDepth
unsigned InstrDepth
Accumulated number of instructions in the trace above this block.
Definition: MachineTraceMetrics.h:172
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::DenseMap
Definition: DenseMap.h:714
isExitingLoop
static bool isExitingLoop(const MachineLoop *From, const MachineLoop *To)
Definition: MachineTraceMetrics.cpp:304
llvm::MachineOperand::isDead
bool isDead() const
Definition: MachineOperand.h:384
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MachineInstr::operands_begin
mop_iterator operands_begin()
Definition: MachineInstr.h:635
MCRegisterInfo.h
Metrics
Machine Trace Metrics
Definition: MachineTraceMetrics.cpp:53
ArrayRef.h
llvm::SparseSet::setUniverse
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::pdb::PDB_MemoryType::Stack
@ Stack
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::MachineTraceMetrics::Ensemble::MTM
MachineTraceMetrics & MTM
Definition: MachineTraceMetrics.h:339
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBranchProbabilityInfo.h
llvm::MachineTraceMetrics::Trace::getResourceLength
unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks=None, ArrayRef< const MCSchedClassDesc * > ExtraInstrs=None, ArrayRef< const MCSchedClassDesc * > RemoveInstrs=None) const
Return the resource length of the trace.
Definition: MachineTraceMetrics.cpp:1223
llvm::LiveRegUnit::Cycle
unsigned Cycle
Definition: MachineTraceMetrics.h:77
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::inverse_post_order_ext
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
Definition: PostOrderIterator.h:259
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:386
llvm::TargetSchedModel::computeOperandLatency
unsigned computeOperandLatency(const MachineInstr *DefMI, unsigned DefOperIdx, const MachineInstr *UseMI, unsigned UseOperIdx) const
Compute operand latency based on the available machine model.
Definition: TargetSchedule.cpp:168
llvm::Register::asMCReg
MCRegister asMCReg() const
Utility to check-convert this value to a MCRegister.
Definition: Register.h:120
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:368
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::MachineBasicBlock::succ_empty
bool succ_empty() const
Definition: MachineBasicBlock.h:384
llvm::MachineTraceMetrics::TraceBlockInfo::print
void print(raw_ostream &) const
Definition: MachineTraceMetrics.cpp:1297
llvm::ArrayRef< unsigned >
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:1115
llvm::MachineTraceMetrics::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: MachineTraceMetrics.cpp:406
llvm::MachineBasicBlock::successors
iterator_range< succ_iterator > successors()
Definition: MachineBasicBlock.h:392
llvm::MachineTraceMetrics::Ensemble::getHeightResources
const TraceBlockInfo * getHeightResources(const MachineBasicBlock *) const
Definition: MachineTraceMetrics.cpp:252
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MachineTraceMetrics, DEBUG_TYPE, "Machine Trace Metrics", false, true) INITIALIZE_PASS_END(MachineTraceMetrics
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::MachineTraceMetrics::TraceBlockInfo::HasValidInstrDepths
bool HasValidInstrDepths
Instruction depths have been computed. This implies hasValidDepth().
Definition: MachineTraceMetrics.h:220
llvm::LiveRegUnit::MI
const MachineInstr * MI
Definition: MachineTraceMetrics.h:78
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
updatePhysDepsUpwards
static unsigned updatePhysDepsUpwards(const MachineInstr &MI, unsigned Height, SparseSet< LiveRegUnit > &RegUnits, const TargetSchedModel &SchedModel, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
Definition: MachineTraceMetrics.cpp:892
llvm::po_iterator_storage< LoopBounds, true >::po_iterator_storage
po_iterator_storage(LoopBounds &lb)
Definition: MachineTraceMetrics.cpp:448
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
llvm::MachineInstr::getParent
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:313
llvm::MachineTraceMetrics::InstrCycles::Height
unsigned Height
Minimum number of cycles from this instruction is issued to the of the trace, as determined by data d...
Definition: MachineTraceMetrics.h:249
llvm::MachineTraceMetrics::TraceBlockInfo::invalidateHeight
void invalidateHeight()
Invalidate height resources when a block below this one has changed.
Definition: MachineTraceMetrics.h:192
SparseSet.h
getPHIDeps
static void getPHIDeps(const MachineInstr &UseMI, SmallVectorImpl< DataDep > &Deps, const MachineBasicBlock *Pred, const MachineRegisterInfo *MRI)
Definition: MachineTraceMetrics.cpp:681
pushDepHeight
static bool pushDepHeight(const DataDep &Dep, const MachineInstr &UseMI, unsigned UseHeight, MIHeightMap &Heights, const TargetSchedModel &SchedModel, const TargetInstrInfo *TII)
Definition: MachineTraceMetrics.cpp:953
llvm::TargetSchedModel::getNumProcResourceKinds
unsigned getNumProcResourceKinds() const
Get the number of kinds of resources for this target.
Definition: TargetSchedule.h:112
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::Trace
Definition: Trace.h:30
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineBasicBlock::isPredecessor
bool isPredecessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a predecessor of this block.
Definition: MachineBasicBlock.cpp:920
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineTraceMetrics::TraceBlockInfo::Pred
const MachineBasicBlock * Pred
Trace predecessor, or NULL for the first block in the trace.
Definition: MachineTraceMetrics.h:158
llvm::MachineTraceMetrics::Ensemble
A trace ensemble is a collection of traces selected using the same strategy, for example 'minimum res...
Definition: MachineTraceMetrics.h:321
llvm::MachineOperand::readsReg
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
Definition: MachineOperand.h:457
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::MachineTraceMetrics::Trace::print
void print(raw_ostream &) const
Definition: MachineTraceMetrics.cpp:1325
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::MachineTraceMetrics::Ensemble::getLoopFor
const MachineLoop * getLoopFor(const MachineBasicBlock *) const
Definition: MachineTraceMetrics.cpp:169
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:48
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:105
llvm::SparseSet::erase
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:288
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::MachineTraceMetrics::Ensemble::getProcResourceDepths
ArrayRef< unsigned > getProcResourceDepths(unsigned MBBNum) const
Get an array of processor resource depths for MBB.
Definition: MachineTraceMetrics.cpp:265
llvm::MachineTraceMetrics::Ensemble::getProcResourceHeights
ArrayRef< unsigned > getProcResourceHeights(unsigned MBBNum) const
Get an array of processor resource heights for MBB.
Definition: MachineTraceMetrics.cpp:278
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
llvm::MachineTraceMetrics::Ensemble::getDepthResources
const TraceBlockInfo * getDepthResources(const MachineBasicBlock *) const
Definition: MachineTraceMetrics.cpp:243
llvm::MachineTraceMetrics::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MachineTraceMetrics.cpp:80
llvm::Cycle
CycleInfo::CycleT Cycle
Definition: CycleAnalysis.h:28
llvm::MCRegUnitIterator
Definition: MCRegisterInfo.h:680
PostOrderIterator.h
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:370
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::MachineTraceMetrics::ID
static char ID
Definition: MachineTraceMetrics.h:99
llvm::MachineTraceMetrics::Trace::getInstrSlack
unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
Definition: MachineTraceMetrics.cpp:1173
llvm::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
DefMI
MachineInstrBuilder MachineInstrBuilder & DefMI
Definition: AArch64ExpandPseudoInsts.cpp:108
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:677
llvm::CallingConv::Tail
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::MachineTraceMetrics::TraceBlockInfo::invalidateDepth
void invalidateDepth()
Invalidate depth resources when some block above this one has changed.
Definition: MachineTraceMetrics.h:189
llvm::MachineRegisterInfo::defusechain_iterator
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
Definition: MachineRegisterInfo.h:274
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::LiveRegUnit
Definition: MachineTraceMetrics.h:75
MachineOperand.h
llvm::SparseSet
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:124
llvm::MachineTraceMetrics::FixedBlockInfo::HasCalls
bool HasCalls
True when the block contains calls.
Definition: MachineTraceMetrics.h:118
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::MachineTraceMetrics::Trace::getPHIDepth
unsigned getPHIDepth(const MachineInstr &PHI) const
Return the Depth of a PHI instruction in a trace center block successor.
Definition: MachineTraceMetrics.cpp:1181
raw_ostream.h
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:111
llvm::MachineTraceMetrics::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: MachineTraceMetrics.cpp:66
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::MachineTraceMetrics
Definition: MachineTraceMetrics.h:87
InitializePasses.h
llvm::MachineTraceMetrics::TraceBlockInfo::Succ
const MachineBasicBlock * Succ
Trace successor, or NULL for the last block in the trace.
Definition: MachineTraceMetrics.h:162
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::TargetSchedModel::hasInstrSchedModel
bool hasInstrSchedModel() const
Return true if this machine model includes an instruction-level scheduling model.
Definition: TargetSchedule.cpp:39
updatePhysDepsDownwards
static void updatePhysDepsDownwards(const MachineInstr *UseMI, SmallVectorImpl< DataDep > &Deps, SparseSet< LiveRegUnit > &RegUnits, const TargetRegisterInfo *TRI)
Definition: MachineTraceMetrics.cpp:700
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
llvm::MachineTraceMetrics::TraceBlockInfo::CriticalPath
unsigned CriticalPath
Critical path length.
Definition: MachineTraceMetrics.h:228