LLVM  7.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"
22 #include "llvm/CodeGen/Passes.h"
28 #include "llvm/Support/Debug.h"
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "machine-combiner"
34 
35 STATISTIC(NumInstCombined, "Number of machineinst combined");
36 
37 static cl::opt<unsigned>
38 inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
39  cl::desc("Incremental depth computation will be used for basic "
40  "blocks with more instructions."), cl::init(500));
41 
42 namespace {
43 class MachineCombiner : public MachineFunctionPass {
44  const TargetInstrInfo *TII;
45  const TargetRegisterInfo *TRI;
46  MCSchedModel SchedModel;
48  MachineLoopInfo *MLI; // Current MachineLoopInfo
49  MachineTraceMetrics *Traces;
51 
52  TargetSchedModel TSchedModel;
53 
54  /// True if optimizing for code size.
55  bool OptSize;
56 
57 public:
58  static char ID;
59  MachineCombiner() : MachineFunctionPass(ID) {
61  }
62  void getAnalysisUsage(AnalysisUsage &AU) const override;
63  bool runOnMachineFunction(MachineFunction &MF) override;
64  StringRef getPassName() const override { return "Machine InstCombiner"; }
65 
66 private:
67  bool doSubstitute(unsigned NewSize, unsigned OldSize);
68  bool combineInstructions(MachineBasicBlock *);
69  MachineInstr *getOperandDef(const MachineOperand &MO);
70  unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
71  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
72  MachineTraceMetrics::Trace BlockTrace);
73  unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
74  MachineTraceMetrics::Trace BlockTrace);
75  bool
76  improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
77  MachineTraceMetrics::Trace BlockTrace,
80  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
81  MachineCombinerPattern Pattern, bool SlackIsAccurate);
82  bool preservesResourceLen(MachineBasicBlock *MBB,
83  MachineTraceMetrics::Trace BlockTrace,
86  void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
88 };
89 }
90 
91 char MachineCombiner::ID = 0;
93 
94 INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
95  "Machine InstCombiner", false, false)
99  false, false)
100 
101 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
102  AU.setPreservesCFG();
103  AU.addPreserved<MachineDominatorTree>();
104  AU.addRequired<MachineLoopInfo>();
105  AU.addPreserved<MachineLoopInfo>();
106  AU.addRequired<MachineTraceMetrics>();
107  AU.addPreserved<MachineTraceMetrics>();
109 }
110 
111 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
112  MachineInstr *DefInstr = nullptr;
113  // We need a virtual register definition.
115  DefInstr = MRI->getUniqueVRegDef(MO.getReg());
116  // PHI's have no depth etc.
117  if (DefInstr && DefInstr->isPHI())
118  DefInstr = nullptr;
119  return DefInstr;
120 }
121 
122 /// Computes depth of instructions in vector \InsInstr.
123 ///
124 /// \param InsInstrs is a vector of machine instructions
125 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
126 /// of defining machine instruction in \p InsInstrs
127 /// \param BlockTrace is a trace of machine instructions
128 ///
129 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
130 unsigned
131 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
132  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
133  MachineTraceMetrics::Trace BlockTrace) {
134  SmallVector<unsigned, 16> InstrDepth;
135  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
136  "Missing machine model\n");
137 
138  // For each instruction in the new sequence compute the depth based on the
139  // operands. Use the trace information when possible. For new operands which
140  // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
141  for (auto *InstrPtr : InsInstrs) { // for each Use
142  unsigned IDepth = 0;
143  DEBUG(dbgs() << "NEW INSTR ";
144  InstrPtr->print(dbgs(), TII);
145  dbgs() << "\n";);
146  for (const MachineOperand &MO : InstrPtr->operands()) {
147  // Check for virtual register operand.
149  continue;
150  if (!MO.isUse())
151  continue;
152  unsigned DepthOp = 0;
153  unsigned LatencyOp = 0;
155  InstrIdxForVirtReg.find(MO.getReg());
156  if (II != InstrIdxForVirtReg.end()) {
157  // Operand is new virtual register not in trace
158  assert(II->second < InstrDepth.size() && "Bad Index");
159  MachineInstr *DefInstr = InsInstrs[II->second];
160  assert(DefInstr &&
161  "There must be a definition for a new virtual register");
162  DepthOp = InstrDepth[II->second];
163  int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
164  int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
165  LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
166  InstrPtr, UseIdx);
167  } else {
168  MachineInstr *DefInstr = getOperandDef(MO);
169  if (DefInstr) {
170  DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
171  LatencyOp = TSchedModel.computeOperandLatency(
172  DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
173  InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
174  }
175  }
176  IDepth = std::max(IDepth, DepthOp + LatencyOp);
177  }
178  InstrDepth.push_back(IDepth);
179  }
180  unsigned NewRootIdx = InsInstrs.size() - 1;
181  return InstrDepth[NewRootIdx];
182 }
183 
184 /// Computes instruction latency as max of latency of defined operands.
185 ///
186 /// \param Root is a machine instruction that could be replaced by NewRoot.
187 /// It is used to compute a more accurate latency information for NewRoot in
188 /// case there is a dependent instruction in the same trace (\p BlockTrace)
189 /// \param NewRoot is the instruction for which the latency is computed
190 /// \param BlockTrace is a trace of machine instructions
191 ///
192 /// \returns Latency of \p NewRoot
193 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
194  MachineTraceMetrics::Trace BlockTrace) {
195  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
196  "Missing machine model\n");
197 
198  // Check each definition in NewRoot and compute the latency
199  unsigned NewRootLatency = 0;
200 
201  for (const MachineOperand &MO : NewRoot->operands()) {
202  // Check for virtual register operand.
204  continue;
205  if (!MO.isDef())
206  continue;
207  // Get the first instruction that uses MO
208  MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
209  RI++;
210  MachineInstr *UseMO = RI->getParent();
211  unsigned LatencyOp = 0;
212  if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
213  LatencyOp = TSchedModel.computeOperandLatency(
214  NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
215  UseMO->findRegisterUseOperandIdx(MO.getReg()));
216  } else {
217  LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
218  }
219  NewRootLatency = std::max(NewRootLatency, LatencyOp);
220  }
221  return NewRootLatency;
222 }
223 
224 /// The combiner's goal may differ based on which pattern it is attempting
225 /// to optimize.
226 enum class CombinerObjective {
227  MustReduceDepth, // The data dependency chain must be improved.
228  Default // The critical path must not be lengthened.
229 };
230 
232  // TODO: If C++ ever gets a real enum class, make this part of the
233  // MachineCombinerPattern class.
234  switch (P) {
240  default:
242  }
243 }
244 
245 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
246 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
247 /// sequence to replace the old sequence is that it cannot lengthen the critical
248 /// path. The definition of "improve" may be restricted by specifying that the
249 /// new path improves the data dependency chain (MustReduceDepth).
250 bool MachineCombiner::improvesCriticalPathLen(
251  MachineBasicBlock *MBB, MachineInstr *Root,
252  MachineTraceMetrics::Trace BlockTrace,
255  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
256  MachineCombinerPattern Pattern,
257  bool SlackIsAccurate) {
258  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
259  "Missing machine model\n");
260  // NewRoot is the last instruction in the \p InsInstrs vector.
261  unsigned NewRootIdx = InsInstrs.size() - 1;
262  MachineInstr *NewRoot = InsInstrs[NewRootIdx];
263 
264  // Get depth and latency of NewRoot and Root.
265  unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
266  unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
267 
268  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << *Root << "\n";
269  dbgs() << " NewRootDepth: " << NewRootDepth << "\n";
270  dbgs() << " RootDepth: " << RootDepth << "\n");
271 
272  // For a transform such as reassociation, the cost equation is
273  // conservatively calculated so that we must improve the depth (data
274  // dependency cycles) in the critical path to proceed with the transform.
275  // Being conservative also protects against inaccuracies in the underlying
276  // machine trace metrics and CPU models.
278  return NewRootDepth < RootDepth;
279 
280  // A more flexible cost calculation for the critical path includes the slack
281  // of the original code sequence. This may allow the transform to proceed
282  // even if the instruction depths (data dependency cycles) become worse.
283 
284  // Account for the latency of the inserted and deleted instructions by
285  // adding up their latencies. This assumes that the inserted and deleted
286  // instructions are dependent instruction chains, which might not hold
287  // in all cases.
288  unsigned NewRootLatency = 0;
289  for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
290  NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
291  NewRootLatency += getLatency(Root, NewRoot, BlockTrace);
292 
293  unsigned RootLatency = 0;
294  for (auto I : DelInstrs)
295  RootLatency += TSchedModel.computeInstrLatency(I);
296 
297  unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
298  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
299  unsigned OldCycleCount = RootDepth + RootLatency +
300  (SlackIsAccurate ? RootSlack : 0);
301  DEBUG(dbgs() << " NewRootLatency: " << NewRootLatency << "\n";
302  dbgs() << " RootLatency: " << RootLatency << "\n";
303  dbgs() << " RootSlack: " << RootSlack << " SlackIsAccurate="
304  << SlackIsAccurate << "\n";
305  dbgs() << " NewRootDepth + NewRootLatency = "
306  << NewCycleCount << "\n";
307  dbgs() << " RootDepth + RootLatency + RootSlack = "
308  << OldCycleCount << "\n";
309  );
310 
311  return NewCycleCount <= OldCycleCount;
312 }
313 
314 /// helper routine to convert instructions into SC
315 void MachineCombiner::instr2instrSC(
318  for (auto *InstrPtr : Instrs) {
319  unsigned Opc = InstrPtr->getOpcode();
320  unsigned Idx = TII->get(Opc).getSchedClass();
321  const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
322  InstrsSC.push_back(SC);
323  }
324 }
325 
326 /// True when the new instructions do not increase resource length
327 bool MachineCombiner::preservesResourceLen(
330  SmallVectorImpl<MachineInstr *> &DelInstrs) {
331  if (!TSchedModel.hasInstrSchedModel())
332  return true;
333 
334  // Compute current resource length
335 
336  //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
338  MBBarr.push_back(MBB);
339  unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
340 
341  // Deal with SC rather than Instructions.
344 
345  instr2instrSC(InsInstrs, InsInstrsSC);
346  instr2instrSC(DelInstrs, DelInstrsSC);
347 
348  ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
349  ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
350 
351  // Compute new resource length.
352  unsigned ResLenAfterCombine =
353  BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
354 
355  DEBUG(dbgs() << "RESOURCE DATA: \n";
356  dbgs() << " resource len before: " << ResLenBeforeCombine
357  << " after: " << ResLenAfterCombine << "\n";);
358 
359  return ResLenAfterCombine <= ResLenBeforeCombine;
360 }
361 
362 /// \returns true when new instruction sequence should be generated
363 /// independent if it lengthens critical path or not
364 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
365  if (OptSize && (NewSize < OldSize))
366  return true;
367  if (!TSchedModel.hasInstrSchedModelOrItineraries())
368  return true;
369  return false;
370 }
371 
372 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
373 /// depths if requested.
374 ///
375 /// \param MBB basic block to insert instructions in
376 /// \param MI current machine instruction
377 /// \param InsInstrs new instructions to insert in \p MBB
378 /// \param DelInstrs instruction to delete from \p MBB
379 /// \param MinInstr is a pointer to the machine trace information
380 /// \param RegUnits set of live registers, needed to compute instruction depths
381 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
382 /// otherwise invalidate the trace
387  SparseSet<LiveRegUnit> &RegUnits,
388  bool IncrementalUpdate) {
389  for (auto *InstrPtr : InsInstrs)
390  MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
391 
392  for (auto *InstrPtr : DelInstrs) {
393  InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
394  // Erase all LiveRegs defined by the removed instruction
395  for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
396  if (I->MI == InstrPtr)
397  I = RegUnits.erase(I);
398  else
399  I++;
400  }
401  }
402 
403  if (IncrementalUpdate)
404  for (auto *InstrPtr : InsInstrs)
405  MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
406  else
407  MinInstr->invalidate(MBB);
408 
409  NumInstCombined++;
410 }
411 
412 /// Substitute a slow code sequence with a faster one by
413 /// evaluating instruction combining pattern.
414 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
415 /// combining based on machine trace metrics. Only combine a sequence of
416 /// instructions when this neither lengthens the critical path nor increases
417 /// resource pressure. When optimizing for codesize always combine when the new
418 /// sequence is shorter.
419 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
420  bool Changed = false;
421  DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
422 
423  bool IncrementalUpdate = false;
424  auto BlockIter = MBB->begin();
425  decltype(BlockIter) LastUpdate;
426  // Check if the block is in a loop.
427  const MachineLoop *ML = MLI->getLoopFor(MBB);
428  if (!MinInstr)
429  MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
430 
431  SparseSet<LiveRegUnit> RegUnits;
432  RegUnits.setUniverse(TRI->getNumRegUnits());
433 
434  while (BlockIter != MBB->end()) {
435  auto &MI = *BlockIter++;
436 
437  DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
439  // The motivating example is:
440  //
441  // MUL Other MUL_op1 MUL_op2 Other
442  // \ / \ | /
443  // ADD/SUB => MADD/MSUB
444  // (=Root) (=NewRoot)
445 
446  // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
447  // usually beneficial for code size it unfortunately can hurt performance
448  // when the ADD is on the critical path, but the MUL is not. With the
449  // substitution the MUL becomes part of the critical path (in form of the
450  // MADD) and can lengthen it on architectures where the MADD latency is
451  // longer than the ADD latency.
452  //
453  // For each instruction we check if it can be the root of a combiner
454  // pattern. Then for each pattern the new code sequence in form of MI is
455  // generated and evaluated. When the efficiency criteria (don't lengthen
456  // critical path, don't use more resources) is met the new sequence gets
457  // hooked up into the basic block before the old sequence is removed.
458  //
459  // The algorithm does not try to evaluate all patterns and pick the best.
460  // This is only an artificial restriction though. In practice there is
461  // mostly one pattern, and getMachineCombinerPatterns() can order patterns
462  // based on an internal cost heuristic.
463 
464  if (!TII->getMachineCombinerPatterns(MI, Patterns))
465  continue;
466 
467  for (auto P : Patterns) {
470  DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
471  TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
472  InstrIdxForVirtReg);
473  unsigned NewInstCount = InsInstrs.size();
474  unsigned OldInstCount = DelInstrs.size();
475  // Found pattern, but did not generate alternative sequence.
476  // This can happen e.g. when an immediate could not be materialized
477  // in a single instruction.
478  if (!NewInstCount)
479  continue;
480 
481  bool SubstituteAlways = false;
482  if (ML && TII->isThroughputPattern(P))
483  SubstituteAlways = true;
484 
485  if (IncrementalUpdate) {
486  // Update depths since the last incremental update.
487  MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
488  LastUpdate = BlockIter;
489  }
490 
491  // Substitute when we optimize for codesize and the new sequence has
492  // fewer instructions OR
493  // the new sequence neither lengthens the critical path nor increases
494  // resource pressure.
495  if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
496  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
497  RegUnits, IncrementalUpdate);
498  // Eagerly stop after the first pattern fires.
499  Changed = true;
500  break;
501  } else {
502  // For big basic blocks, we only compute the full trace the first time
503  // we hit this. We do not invalidate the trace, but instead update the
504  // instruction depths incrementally.
505  // NOTE: Only the instruction depths up to MI are accurate. All other
506  // trace information is not updated.
507  MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
508  Traces->verifyAnalysis();
509  if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
510  InstrIdxForVirtReg, P,
511  !IncrementalUpdate) &&
512  preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
513  if (MBB->size() > inc_threshold) {
514  // Use incremental depth updates for basic blocks above treshold
515  IncrementalUpdate = true;
516  LastUpdate = BlockIter;
517  }
518 
519  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
520  RegUnits, IncrementalUpdate);
521 
522  // Eagerly stop after the first pattern fires.
523  Changed = true;
524  break;
525  }
526  // Cleanup instructions of the alternative code sequence. There is no
527  // use for them.
528  MachineFunction *MF = MBB->getParent();
529  for (auto *InstrPtr : InsInstrs)
530  MF->DeleteMachineInstr(InstrPtr);
531  }
532  InstrIdxForVirtReg.clear();
533  }
534  }
535 
536  if (Changed && IncrementalUpdate)
537  Traces->invalidate(MBB);
538  return Changed;
539 }
540 
541 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
542  const TargetSubtargetInfo &STI = MF.getSubtarget();
543  TII = STI.getInstrInfo();
544  TRI = STI.getRegisterInfo();
545  SchedModel = STI.getSchedModel();
546  TSchedModel.init(SchedModel, &STI, TII);
547  MRI = &MF.getRegInfo();
548  MLI = &getAnalysis<MachineLoopInfo>();
549  Traces = &getAnalysis<MachineTraceMetrics>();
550  MinInstr = nullptr;
551  OptSize = MF.getFunction().optForSize();
552 
553  DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
554  if (!TII->useMachineCombiner()) {
555  DEBUG(dbgs() << " Skipping pass: Target does not support machine combiner\n");
556  return false;
557  }
558 
559  bool Changed = false;
560 
561  // Try to combine instructions.
562  for (auto &MBB : MF)
563  Changed |= combineInstructions(&MBB);
564 
565  return Changed;
566 }
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:335
bool isPHI() const
Definition: MachineInstr.h:829
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:576
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.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
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:60
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.
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.