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