LLVM  6.0.0svn
MachineCombiner.cpp
Go to the documentation of this file.
1 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // The machine combiner pass uses machine trace metrics to ensure the combined
11 // instructions do not lengthen the critical path or the resource depth.
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/Statistic.h"
23 #include "llvm/CodeGen/Passes.h"
29 #include "llvm/Support/Debug.h"
31 
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "machine-combiner"
35 
36 STATISTIC(NumInstCombined, "Number of machineinst combined");
37 
38 static cl::opt<unsigned>
39 inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
40  cl::desc("Incremental depth computation will be used for basic "
41  "blocks with more instructions."), cl::init(500));
42 
43 namespace {
44 class MachineCombiner : public MachineFunctionPass {
45  const TargetInstrInfo *TII;
46  const TargetRegisterInfo *TRI;
47  MCSchedModel SchedModel;
49  MachineLoopInfo *MLI; // Current MachineLoopInfo
50  MachineTraceMetrics *Traces;
52 
53  TargetSchedModel TSchedModel;
54 
55  /// True if optimizing for code size.
56  bool OptSize;
57 
58 public:
59  static char ID;
60  MachineCombiner() : MachineFunctionPass(ID) {
62  }
63  void getAnalysisUsage(AnalysisUsage &AU) const override;
64  bool runOnMachineFunction(MachineFunction &MF) override;
65  StringRef getPassName() const override { return "Machine InstCombiner"; }
66 
67 private:
68  bool doSubstitute(unsigned NewSize, unsigned OldSize);
69  bool combineInstructions(MachineBasicBlock *);
70  MachineInstr *getOperandDef(const MachineOperand &MO);
71  unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
72  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
73  MachineTraceMetrics::Trace BlockTrace);
74  unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
75  MachineTraceMetrics::Trace BlockTrace);
76  bool
77  improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
78  MachineTraceMetrics::Trace BlockTrace,
81  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
82  MachineCombinerPattern Pattern, bool SlackIsAccurate);
83  bool preservesResourceLen(MachineBasicBlock *MBB,
84  MachineTraceMetrics::Trace BlockTrace,
87  void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
89 };
90 }
91 
92 char MachineCombiner::ID = 0;
94 
95 INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
96  "Machine InstCombiner", false, false)
100  false, false)
101 
102 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
103  AU.setPreservesCFG();
104  AU.addPreserved<MachineDominatorTree>();
105  AU.addRequired<MachineLoopInfo>();
106  AU.addPreserved<MachineLoopInfo>();
107  AU.addRequired<MachineTraceMetrics>();
108  AU.addPreserved<MachineTraceMetrics>();
110 }
111 
112 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
113  MachineInstr *DefInstr = nullptr;
114  // We need a virtual register definition.
116  DefInstr = MRI->getUniqueVRegDef(MO.getReg());
117  // PHI's have no depth etc.
118  if (DefInstr && DefInstr->isPHI())
119  DefInstr = nullptr;
120  return DefInstr;
121 }
122 
123 /// Computes depth of instructions in vector \InsInstr.
124 ///
125 /// \param InsInstrs is a vector of machine instructions
126 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
127 /// of defining machine instruction in \p InsInstrs
128 /// \param BlockTrace is a trace of machine instructions
129 ///
130 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
131 unsigned
132 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
133  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
134  MachineTraceMetrics::Trace BlockTrace) {
135  SmallVector<unsigned, 16> InstrDepth;
136  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
137  "Missing machine model\n");
138 
139  // For each instruction in the new sequence compute the depth based on the
140  // operands. Use the trace information when possible. For new operands which
141  // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
142  for (auto *InstrPtr : InsInstrs) { // for each Use
143  unsigned IDepth = 0;
144  DEBUG(dbgs() << "NEW INSTR ";
145  InstrPtr->print(dbgs(), TII);
146  dbgs() << "\n";);
147  for (const MachineOperand &MO : InstrPtr->operands()) {
148  // Check for virtual register operand.
150  continue;
151  if (!MO.isUse())
152  continue;
153  unsigned DepthOp = 0;
154  unsigned LatencyOp = 0;
156  InstrIdxForVirtReg.find(MO.getReg());
157  if (II != InstrIdxForVirtReg.end()) {
158  // Operand is new virtual register not in trace
159  assert(II->second < InstrDepth.size() && "Bad Index");
160  MachineInstr *DefInstr = InsInstrs[II->second];
161  assert(DefInstr &&
162  "There must be a definition for a new virtual register");
163  DepthOp = InstrDepth[II->second];
164  int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
165  int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
166  LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
167  InstrPtr, UseIdx);
168  } else {
169  MachineInstr *DefInstr = getOperandDef(MO);
170  if (DefInstr) {
171  DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
172  LatencyOp = TSchedModel.computeOperandLatency(
173  DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
174  InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
175  }
176  }
177  IDepth = std::max(IDepth, DepthOp + LatencyOp);
178  }
179  InstrDepth.push_back(IDepth);
180  }
181  unsigned NewRootIdx = InsInstrs.size() - 1;
182  return InstrDepth[NewRootIdx];
183 }
184 
185 /// Computes instruction latency as max of latency of defined operands.
186 ///
187 /// \param Root is a machine instruction that could be replaced by NewRoot.
188 /// It is used to compute a more accurate latency information for NewRoot in
189 /// case there is a dependent instruction in the same trace (\p BlockTrace)
190 /// \param NewRoot is the instruction for which the latency is computed
191 /// \param BlockTrace is a trace of machine instructions
192 ///
193 /// \returns Latency of \p NewRoot
194 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
195  MachineTraceMetrics::Trace BlockTrace) {
196  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
197  "Missing machine model\n");
198 
199  // Check each definition in NewRoot and compute the latency
200  unsigned NewRootLatency = 0;
201 
202  for (const MachineOperand &MO : NewRoot->operands()) {
203  // Check for virtual register operand.
205  continue;
206  if (!MO.isDef())
207  continue;
208  // Get the first instruction that uses MO
209  MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
210  RI++;
211  MachineInstr *UseMO = RI->getParent();
212  unsigned LatencyOp = 0;
213  if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
214  LatencyOp = TSchedModel.computeOperandLatency(
215  NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
216  UseMO->findRegisterUseOperandIdx(MO.getReg()));
217  } else {
218  LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
219  }
220  NewRootLatency = std::max(NewRootLatency, LatencyOp);
221  }
222  return NewRootLatency;
223 }
224 
225 /// The combiner's goal may differ based on which pattern it is attempting
226 /// to optimize.
227 enum class CombinerObjective {
228  MustReduceDepth, // The data dependency chain must be improved.
229  Default // The critical path must not be lengthened.
230 };
231 
233  // TODO: If C++ ever gets a real enum class, make this part of the
234  // MachineCombinerPattern class.
235  switch (P) {
241  default:
243  }
244 }
245 
246 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
247 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
248 /// sequence to replace the old sequence is that it cannot lengthen the critical
249 /// path. The definition of "improve" may be restricted by specifying that the
250 /// new path improves the data dependency chain (MustReduceDepth).
251 bool MachineCombiner::improvesCriticalPathLen(
252  MachineBasicBlock *MBB, MachineInstr *Root,
253  MachineTraceMetrics::Trace BlockTrace,
256  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
257  MachineCombinerPattern Pattern,
258  bool SlackIsAccurate) {
259  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
260  "Missing machine model\n");
261  // NewRoot is the last instruction in the \p InsInstrs vector.
262  unsigned NewRootIdx = InsInstrs.size() - 1;
263  MachineInstr *NewRoot = InsInstrs[NewRootIdx];
264 
265  // Get depth and latency of NewRoot and Root.
266  unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
267  unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
268 
269  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << *Root << "\n";
270  dbgs() << " NewRootDepth: " << NewRootDepth << "\n";
271  dbgs() << " RootDepth: " << RootDepth << "\n");
272 
273  // For a transform such as reassociation, the cost equation is
274  // conservatively calculated so that we must improve the depth (data
275  // dependency cycles) in the critical path to proceed with the transform.
276  // Being conservative also protects against inaccuracies in the underlying
277  // machine trace metrics and CPU models.
279  return NewRootDepth < RootDepth;
280 
281  // A more flexible cost calculation for the critical path includes the slack
282  // of the original code sequence. This may allow the transform to proceed
283  // even if the instruction depths (data dependency cycles) become worse.
284 
285  unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
286  unsigned RootLatency = 0;
287 
288  for (auto I : DelInstrs)
289  RootLatency += TSchedModel.computeInstrLatency(I);
290 
291  unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
292  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
293  unsigned OldCycleCount = RootDepth + RootLatency +
294  (SlackIsAccurate ? RootSlack : 0);
295  DEBUG(dbgs() << " NewRootLatency: " << NewRootLatency << "\n";
296  dbgs() << " RootLatency: " << RootLatency << "\n";
297  dbgs() << " RootSlack: " << RootSlack << " SlackIsAccurate="
298  << SlackIsAccurate << "\n";
299  dbgs() << " NewRootDepth + NewRootLatency = "
300  << NewCycleCount << "\n";
301  dbgs() << " RootDepth + RootLatency + RootSlack = "
302  << OldCycleCount << "\n";
303  );
304 
305  return NewCycleCount <= OldCycleCount;
306 }
307 
308 /// helper routine to convert instructions into SC
309 void MachineCombiner::instr2instrSC(
312  for (auto *InstrPtr : Instrs) {
313  unsigned Opc = InstrPtr->getOpcode();
314  unsigned Idx = TII->get(Opc).getSchedClass();
315  const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
316  InstrsSC.push_back(SC);
317  }
318 }
319 
320 /// True when the new instructions do not increase resource length
321 bool MachineCombiner::preservesResourceLen(
324  SmallVectorImpl<MachineInstr *> &DelInstrs) {
325  if (!TSchedModel.hasInstrSchedModel())
326  return true;
327 
328  // Compute current resource length
329 
330  //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
332  MBBarr.push_back(MBB);
333  unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
334 
335  // Deal with SC rather than Instructions.
338 
339  instr2instrSC(InsInstrs, InsInstrsSC);
340  instr2instrSC(DelInstrs, DelInstrsSC);
341 
342  ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
343  ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
344 
345  // Compute new resource length.
346  unsigned ResLenAfterCombine =
347  BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
348 
349  DEBUG(dbgs() << "RESOURCE DATA: \n";
350  dbgs() << " resource len before: " << ResLenBeforeCombine
351  << " after: " << ResLenAfterCombine << "\n";);
352 
353  return ResLenAfterCombine <= ResLenBeforeCombine;
354 }
355 
356 /// \returns true when new instruction sequence should be generated
357 /// independent if it lengthens critical path or not
358 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
359  if (OptSize && (NewSize < OldSize))
360  return true;
361  if (!TSchedModel.hasInstrSchedModelOrItineraries())
362  return true;
363  return false;
364 }
365 
366 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
367 /// depths if requested.
368 ///
369 /// \param MBB basic block to insert instructions in
370 /// \param MI current machine instruction
371 /// \param InsInstrs new instructions to insert in \p MBB
372 /// \param DelInstrs instruction to delete from \p MBB
373 /// \param MinInstr is a pointer to the machine trace information
374 /// \param RegUnits set of live registers, needed to compute instruction depths
375 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
376 /// otherwise invalidate the trace
381  SparseSet<LiveRegUnit> &RegUnits,
382  bool IncrementalUpdate) {
383  for (auto *InstrPtr : InsInstrs)
384  MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
385 
386  for (auto *InstrPtr : DelInstrs) {
387  InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
388  // Erase all LiveRegs defined by the removed instruction
389  for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
390  if (I->MI == InstrPtr)
391  I = RegUnits.erase(I);
392  else
393  I++;
394  }
395  }
396 
397  if (IncrementalUpdate)
398  for (auto *InstrPtr : InsInstrs)
399  MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
400  else
401  MinInstr->invalidate(MBB);
402 
403  NumInstCombined++;
404 }
405 
406 /// Substitute a slow code sequence with a faster one by
407 /// evaluating instruction combining pattern.
408 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
409 /// combining based on machine trace metrics. Only combine a sequence of
410 /// instructions when this neither lengthens the critical path nor increases
411 /// resource pressure. When optimizing for codesize always combine when the new
412 /// sequence is shorter.
413 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
414  bool Changed = false;
415  DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
416 
417  bool IncrementalUpdate = false;
418  auto BlockIter = MBB->begin();
419  decltype(BlockIter) LastUpdate;
420  // Check if the block is in a loop.
421  const MachineLoop *ML = MLI->getLoopFor(MBB);
422  if (!MinInstr)
423  MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
424 
425  SparseSet<LiveRegUnit> RegUnits;
426  RegUnits.setUniverse(TRI->getNumRegUnits());
427 
428  while (BlockIter != MBB->end()) {
429  auto &MI = *BlockIter++;
430 
431  DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
433  // The motivating example is:
434  //
435  // MUL Other MUL_op1 MUL_op2 Other
436  // \ / \ | /
437  // ADD/SUB => MADD/MSUB
438  // (=Root) (=NewRoot)
439 
440  // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
441  // usually beneficial for code size it unfortunately can hurt performance
442  // when the ADD is on the critical path, but the MUL is not. With the
443  // substitution the MUL becomes part of the critical path (in form of the
444  // MADD) and can lengthen it on architectures where the MADD latency is
445  // longer than the ADD latency.
446  //
447  // For each instruction we check if it can be the root of a combiner
448  // pattern. Then for each pattern the new code sequence in form of MI is
449  // generated and evaluated. When the efficiency criteria (don't lengthen
450  // critical path, don't use more resources) is met the new sequence gets
451  // hooked up into the basic block before the old sequence is removed.
452  //
453  // The algorithm does not try to evaluate all patterns and pick the best.
454  // This is only an artificial restriction though. In practice there is
455  // mostly one pattern, and getMachineCombinerPatterns() can order patterns
456  // based on an internal cost heuristic.
457 
458  if (!TII->getMachineCombinerPatterns(MI, Patterns))
459  continue;
460 
461  for (auto P : Patterns) {
464  DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
465  TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
466  InstrIdxForVirtReg);
467  unsigned NewInstCount = InsInstrs.size();
468  unsigned OldInstCount = DelInstrs.size();
469  // Found pattern, but did not generate alternative sequence.
470  // This can happen e.g. when an immediate could not be materialized
471  // in a single instruction.
472  if (!NewInstCount)
473  continue;
474 
475  bool SubstituteAlways = false;
476  if (ML && TII->isThroughputPattern(P))
477  SubstituteAlways = true;
478 
479  if (IncrementalUpdate) {
480  // Update depths since the last incremental update.
481  MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
482  LastUpdate = BlockIter;
483  }
484 
485  // Substitute when we optimize for codesize and the new sequence has
486  // fewer instructions OR
487  // the new sequence neither lengthens the critical path nor increases
488  // resource pressure.
489  if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
490  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
491  RegUnits, IncrementalUpdate);
492  // Eagerly stop after the first pattern fires.
493  Changed = true;
494  break;
495  } else {
496  // For big basic blocks, we only compute the full trace the first time
497  // we hit this. We do not invalidate the trace, but instead update the
498  // instruction depths incrementally.
499  // NOTE: Only the instruction depths up to MI are accurate. All other
500  // trace information is not updated.
501  MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
502  Traces->verifyAnalysis();
503  if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
504  InstrIdxForVirtReg, P,
505  !IncrementalUpdate) &&
506  preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
507  if (MBB->size() > inc_threshold) {
508  // Use incremental depth updates for basic blocks above treshold
509  IncrementalUpdate = true;
510  LastUpdate = BlockIter;
511  }
512 
513  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
514  RegUnits, IncrementalUpdate);
515 
516  // Eagerly stop after the first pattern fires.
517  Changed = true;
518  break;
519  }
520  // Cleanup instructions of the alternative code sequence. There is no
521  // use for them.
522  MachineFunction *MF = MBB->getParent();
523  for (auto *InstrPtr : InsInstrs)
524  MF->DeleteMachineInstr(InstrPtr);
525  }
526  InstrIdxForVirtReg.clear();
527  }
528  }
529 
530  if (Changed && IncrementalUpdate)
531  Traces->invalidate(MBB);
532  return Changed;
533 }
534 
535 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
536  const TargetSubtargetInfo &STI = MF.getSubtarget();
537  TII = STI.getInstrInfo();
538  TRI = STI.getRegisterInfo();
539  SchedModel = STI.getSchedModel();
540  TSchedModel.init(SchedModel, &STI, TII);
541  MRI = &MF.getRegInfo();
542  MLI = &getAnalysis<MachineLoopInfo>();
543  Traces = &getAnalysis<MachineTraceMetrics>();
544  MinInstr = nullptr;
545  OptSize = MF.getFunction()->optForSize();
546 
547  DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
548  if (!TII->useMachineCombiner()) {
549  DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
550  return false;
551  }
552 
553  bool Changed = false;
554 
555  // Try to combine instructions.
556  for (auto &MBB : MF)
557  Changed |= combineInstructions(&MBB);
558 
559  return Changed;
560 }
void push_back(const T &Elt)
Definition: SmallVector.h:212
char & MachineCombinerID
This pass performs instruction combining using trace metrics to estimate critical-path and resource d...
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
STATISTIC(NumFunctions, "Total number of functions")
A trace ensemble is a collection of traces selected using the same strategy, for example &#39;minimum res...
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
bool isPHI() const
Definition: MachineInstr.h:826
void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, SparseSet< LiveRegUnit > &RegUnits)
Updates the depth of an machine instruction, given RegUnits.
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
The core instruction combiner logic.
Select the trace through a block that has the fewest instructions.
void dump() const
Definition: Pass.cpp:129
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:363
virtual const TargetInstrInfo * getInstrInfo() const
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
static int getLatency(LLVMDisasmContext *DC, const MCInst &Inst)
Gets latency information for Inst, based on DC information.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:285
TargetInstrInfo - Interface to description of machine instruction set.
static CombinerObjective getCombinerObjective(MachineCombinerPattern P)
static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI, SmallVector< MachineInstr *, 16 > InsInstrs, SmallVector< MachineInstr *, 16 > DelInstrs, MachineTraceMetrics::Ensemble *MinInstr, SparseSet< LiveRegUnit > &RegUnits, bool IncrementalUpdate)
Inserts InsInstrs and deletes DelInstrs.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
void invalidate(const MachineBasicBlock *MBB)
Invalidate traces through BadMBB.
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
unsigned const MachineRegisterInfo * MRI
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Summarize the scheduling resources required for an instruction of a particular scheduling class...
Definition: MCSchedule.h:101
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
Represent the analysis usage information of a pass.
bool optForSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:530
CombinerObjective
The combiner&#39;s goal may differ based on which pattern it is attempting to optimize.
void setUniverse(unsigned U)
setUniverse - Set the universe size which determines the largest key the set can hold.
Definition: SparseSet.h:155
MachineCombinerPattern
These are instruction patterns matched by the machine combiner pass.
void DeleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
const_iterator end() const
Definition: SparseSet.h:175
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
MachineOperand class - Representation of each machine instruction operand.
const_iterator begin() const
Definition: SparseSet.h:174
CHAIN = SC CHAIN, Imm128 - System call.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static cl::opt< unsigned > inc_threshold("machine-combiner-inc-threshold", cl::Hidden, cl::desc("Incremental depth computation will be used for basic " "blocks with more instructions."), cl::init(500))
int findRegisterDefOperandIdx(unsigned Reg, bool isDead=false, bool Overlap=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a def of the specified register or -1 if it is not found...
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
TargetSubtargetInfo - Generic base class for all target subtargets.
Representation of each machine instruction.
Definition: MachineInstr.h:59
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:123
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
#define DEBUG_TYPE
iterator end()
Definition: DenseMap.h:79
INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner", false, false) INITIALIZE_PASS_END(MachineCombiner
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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.
#define DEBUG(X)
Definition: Debug.h:118
void initializeMachineCombinerPass(PassRegistry &)
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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...
unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:136
int findRegisterUseOperandIdx(unsigned Reg, bool isKill=false, const TargetRegisterInfo *TRI=nullptr) const
Returns the operand index that is a use of the specific register or -1 if it is not found...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
const MCSchedModel & getSchedModel() const
Get the machine model for this subtarget&#39;s CPU.