LLVM  16.0.0git
MachineCombiner.cpp
Go to the documentation of this file.
1 //===---- MachineCombiner.cpp - Instcombining on SSA form machine code ----===//
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 //
9 // The machine combiner pass uses machine trace metrics to ensure the combined
10 // instructions do not lengthen the critical path or the resource depth.
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ADT/DenseMap.h"
14 #include "llvm/ADT/Statistic.h"
30 #include "llvm/InitializePasses.h"
32 #include "llvm/Support/Debug.h"
34 
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "machine-combiner"
38 
39 STATISTIC(NumInstCombined, "Number of machineinst combined");
40 
41 static cl::opt<unsigned>
42 inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
43  cl::desc("Incremental depth computation will be used for basic "
44  "blocks with more instructions."), cl::init(500));
45 
46 static cl::opt<bool> dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden,
47  cl::desc("Dump all substituted intrs"),
48  cl::init(false));
49 
50 #ifdef EXPENSIVE_CHECKS
52  "machine-combiner-verify-pattern-order", cl::Hidden,
53  cl::desc(
54  "Verify that the generated patterns are ordered by increasing latency"),
55  cl::init(true));
56 #else
58  "machine-combiner-verify-pattern-order", cl::Hidden,
59  cl::desc(
60  "Verify that the generated patterns are ordered by increasing latency"),
61  cl::init(false));
62 #endif
63 
64 namespace {
65 class MachineCombiner : public MachineFunctionPass {
66  const TargetSubtargetInfo *STI;
67  const TargetInstrInfo *TII;
68  const TargetRegisterInfo *TRI;
69  MCSchedModel SchedModel;
71  MachineLoopInfo *MLI; // Current MachineLoopInfo
72  MachineTraceMetrics *Traces;
75  ProfileSummaryInfo *PSI;
76  RegisterClassInfo RegClassInfo;
77 
78  TargetSchedModel TSchedModel;
79 
80  /// True if optimizing for code size.
81  bool OptSize;
82 
83 public:
84  static char ID;
85  MachineCombiner() : MachineFunctionPass(ID) {
87  }
88  void getAnalysisUsage(AnalysisUsage &AU) const override;
89  bool runOnMachineFunction(MachineFunction &MF) override;
90  StringRef getPassName() const override { return "Machine InstCombiner"; }
91 
92 private:
93  bool doSubstitute(unsigned NewSize, unsigned OldSize, bool OptForSize);
94  bool combineInstructions(MachineBasicBlock *);
95  MachineInstr *getOperandDef(const MachineOperand &MO);
96  bool isTransientMI(const MachineInstr *MI);
97  unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
98  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
99  MachineTraceMetrics::Trace BlockTrace);
100  unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
101  MachineTraceMetrics::Trace BlockTrace);
102  bool
103  improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
104  MachineTraceMetrics::Trace BlockTrace,
107  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
108  MachineCombinerPattern Pattern, bool SlackIsAccurate);
109  bool reduceRegisterPressure(MachineInstr &Root, MachineBasicBlock *MBB,
113  bool preservesResourceLen(MachineBasicBlock *MBB,
114  MachineTraceMetrics::Trace BlockTrace,
117  void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
119  std::pair<unsigned, unsigned>
120  getLatenciesForInstrSequences(MachineInstr &MI,
123  MachineTraceMetrics::Trace BlockTrace);
124 
125  void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
127 };
128 }
129 
130 char MachineCombiner::ID = 0;
132 
133 INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
134  "Machine InstCombiner", false, false)
139 
140 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
141  AU.setPreservesCFG();
142  AU.addPreserved<MachineDominatorTree>();
143  AU.addRequired<MachineLoopInfo>();
144  AU.addPreserved<MachineLoopInfo>();
145  AU.addRequired<MachineTraceMetrics>();
146  AU.addPreserved<MachineTraceMetrics>();
147  AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
148  AU.addRequired<ProfileSummaryInfoWrapperPass>();
150 }
151 
152 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
153  MachineInstr *DefInstr = nullptr;
154  // We need a virtual register definition.
155  if (MO.isReg() && Register::isVirtualRegister(MO.getReg()))
156  DefInstr = MRI->getUniqueVRegDef(MO.getReg());
157  // PHI's have no depth etc.
158  if (DefInstr && DefInstr->isPHI())
159  DefInstr = nullptr;
160  return DefInstr;
161 }
162 
163 /// Return true if MI is unlikely to generate an actual target instruction.
164 bool MachineCombiner::isTransientMI(const MachineInstr *MI) {
165  if (!MI->isCopy())
166  return MI->isTransient();
167 
168  // If MI is a COPY, check if its src and dst registers can be coalesced.
169  Register Dst = MI->getOperand(0).getReg();
170  Register Src = MI->getOperand(1).getReg();
171 
172  if (!MI->isFullCopy()) {
173  // If src RC contains super registers of dst RC, it can also be coalesced.
174  if (MI->getOperand(0).getSubReg() || Src.isPhysical() || Dst.isPhysical())
175  return false;
176 
177  auto SrcSub = MI->getOperand(1).getSubReg();
178  auto SrcRC = MRI->getRegClass(Src);
179  auto DstRC = MRI->getRegClass(Dst);
180  return TRI->getMatchingSuperRegClass(SrcRC, DstRC, SrcSub) != nullptr;
181  }
182 
183  if (Src.isPhysical() && Dst.isPhysical())
184  return Src == Dst;
185 
186  if (Src.isVirtual() && Dst.isVirtual()) {
187  auto SrcRC = MRI->getRegClass(Src);
188  auto DstRC = MRI->getRegClass(Dst);
189  return SrcRC->hasSuperClassEq(DstRC) || SrcRC->hasSubClassEq(DstRC);
190  }
191 
192  if (Src.isVirtual())
193  std::swap(Src, Dst);
194 
195  // Now Src is physical register, Dst is virtual register.
196  auto DstRC = MRI->getRegClass(Dst);
197  return DstRC->contains(Src);
198 }
199 
200 /// Computes depth of instructions in vector \InsInstr.
201 ///
202 /// \param InsInstrs is a vector of machine instructions
203 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
204 /// of defining machine instruction in \p InsInstrs
205 /// \param BlockTrace is a trace of machine instructions
206 ///
207 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
208 unsigned
209 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
210  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
211  MachineTraceMetrics::Trace BlockTrace) {
212  SmallVector<unsigned, 16> InstrDepth;
213  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
214  "Missing machine model\n");
215 
216  // For each instruction in the new sequence compute the depth based on the
217  // operands. Use the trace information when possible. For new operands which
218  // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
219  for (auto *InstrPtr : InsInstrs) { // for each Use
220  unsigned IDepth = 0;
221  for (const MachineOperand &MO : InstrPtr->operands()) {
222  // Check for virtual register operand.
223  if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
224  continue;
225  if (!MO.isUse())
226  continue;
227  unsigned DepthOp = 0;
228  unsigned LatencyOp = 0;
230  InstrIdxForVirtReg.find(MO.getReg());
231  if (II != InstrIdxForVirtReg.end()) {
232  // Operand is new virtual register not in trace
233  assert(II->second < InstrDepth.size() && "Bad Index");
234  MachineInstr *DefInstr = InsInstrs[II->second];
235  assert(DefInstr &&
236  "There must be a definition for a new virtual register");
237  DepthOp = InstrDepth[II->second];
238  int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
239  int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
240  LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
241  InstrPtr, UseIdx);
242  } else {
243  MachineInstr *DefInstr = getOperandDef(MO);
244  if (DefInstr) {
245  DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
246  if (!isTransientMI(DefInstr))
247  LatencyOp = TSchedModel.computeOperandLatency(
248  DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
249  InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
250  }
251  }
252  IDepth = std::max(IDepth, DepthOp + LatencyOp);
253  }
254  InstrDepth.push_back(IDepth);
255  }
256  unsigned NewRootIdx = InsInstrs.size() - 1;
257  return InstrDepth[NewRootIdx];
258 }
259 
260 /// Computes instruction latency as max of latency of defined operands.
261 ///
262 /// \param Root is a machine instruction that could be replaced by NewRoot.
263 /// It is used to compute a more accurate latency information for NewRoot in
264 /// case there is a dependent instruction in the same trace (\p BlockTrace)
265 /// \param NewRoot is the instruction for which the latency is computed
266 /// \param BlockTrace is a trace of machine instructions
267 ///
268 /// \returns Latency of \p NewRoot
269 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
270  MachineTraceMetrics::Trace BlockTrace) {
271  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
272  "Missing machine model\n");
273 
274  // Check each definition in NewRoot and compute the latency
275  unsigned NewRootLatency = 0;
276 
277  for (const MachineOperand &MO : NewRoot->operands()) {
278  // Check for virtual register operand.
279  if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
280  continue;
281  if (!MO.isDef())
282  continue;
283  // Get the first instruction that uses MO
285  RI++;
286  if (RI == MRI->reg_end())
287  continue;
288  MachineInstr *UseMO = RI->getParent();
289  unsigned LatencyOp = 0;
290  if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
291  LatencyOp = TSchedModel.computeOperandLatency(
292  NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
293  UseMO->findRegisterUseOperandIdx(MO.getReg()));
294  } else {
295  LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
296  }
297  NewRootLatency = std::max(NewRootLatency, LatencyOp);
298  }
299  return NewRootLatency;
300 }
301 
302 /// The combiner's goal may differ based on which pattern it is attempting
303 /// to optimize.
304 enum class CombinerObjective {
305  MustReduceDepth, // The data dependency chain must be improved.
306  MustReduceRegisterPressure, // The register pressure must be reduced.
307  Default // The critical path must not be lengthened.
308 };
309 
311  // TODO: If C++ ever gets a real enum class, make this part of the
312  // MachineCombinerPattern class.
313  switch (P) {
330  default:
332  }
333 }
334 
335 /// Estimate the latency of the new and original instruction sequence by summing
336 /// up the latencies of the inserted and deleted instructions. This assumes
337 /// that the inserted and deleted instructions are dependent instruction chains,
338 /// which might not hold in all cases.
339 std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
342  MachineTraceMetrics::Trace BlockTrace) {
343  assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
344  unsigned NewRootLatency = 0;
345  // NewRoot is the last instruction in the \p InsInstrs vector.
346  MachineInstr *NewRoot = InsInstrs.back();
347  for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
348  NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
349  NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
350 
351  unsigned RootLatency = 0;
352  for (auto *I : DelInstrs)
353  RootLatency += TSchedModel.computeInstrLatency(I);
354 
355  return {NewRootLatency, RootLatency};
356 }
357 
358 bool MachineCombiner::reduceRegisterPressure(
363  // FIXME: for now, we don't do any check for the register pressure patterns.
364  // We treat them as always profitable. But we can do better if we make
365  // RegPressureTracker class be aware of TIE attribute. Then we can get an
366  // accurate compare of register pressure with DelInstrs or InsInstrs.
367  return true;
368 }
369 
370 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
371 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
372 /// sequence to replace the old sequence is that it cannot lengthen the critical
373 /// path. The definition of "improve" may be restricted by specifying that the
374 /// new path improves the data dependency chain (MustReduceDepth).
375 bool MachineCombiner::improvesCriticalPathLen(
377  MachineTraceMetrics::Trace BlockTrace,
380  DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
382  bool SlackIsAccurate) {
383  assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
384  "Missing machine model\n");
385  // Get depth and latency of NewRoot and Root.
386  unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
387  unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
388 
389  LLVM_DEBUG(dbgs() << " Dependence data for " << *Root << "\tNewRootDepth: "
390  << NewRootDepth << "\tRootDepth: " << RootDepth);
391 
392  // For a transform such as reassociation, the cost equation is
393  // conservatively calculated so that we must improve the depth (data
394  // dependency cycles) in the critical path to proceed with the transform.
395  // Being conservative also protects against inaccuracies in the underlying
396  // machine trace metrics and CPU models.
398  LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
399  LLVM_DEBUG(NewRootDepth < RootDepth
400  ? dbgs() << "\t and it does it\n"
401  : dbgs() << "\t but it does NOT do it\n");
402  return NewRootDepth < RootDepth;
403  }
404 
405  // A more flexible cost calculation for the critical path includes the slack
406  // of the original code sequence. This may allow the transform to proceed
407  // even if the instruction depths (data dependency cycles) become worse.
408 
409  // Account for the latency of the inserted and deleted instructions by
410  unsigned NewRootLatency, RootLatency;
411  std::tie(NewRootLatency, RootLatency) =
412  getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
413 
414  unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
415  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
416  unsigned OldCycleCount =
417  RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
418  LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
419  << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
420  << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
421  << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
422  << "\n\tRootDepth + RootLatency + RootSlack = "
423  << OldCycleCount;);
424  LLVM_DEBUG(NewCycleCount <= OldCycleCount
425  ? dbgs() << "\n\t It IMPROVES PathLen because"
426  : dbgs() << "\n\t It DOES NOT improve PathLen because");
427  LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
428  << ", OldCycleCount = " << OldCycleCount << "\n");
429 
430  return NewCycleCount <= OldCycleCount;
431 }
432 
433 /// helper routine to convert instructions into SC
434 void MachineCombiner::instr2instrSC(
437  for (auto *InstrPtr : Instrs) {
438  unsigned Opc = InstrPtr->getOpcode();
439  unsigned Idx = TII->get(Opc).getSchedClass();
440  const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
441  InstrsSC.push_back(SC);
442  }
443 }
444 
445 /// True when the new instructions do not increase resource length
446 bool MachineCombiner::preservesResourceLen(
449  SmallVectorImpl<MachineInstr *> &DelInstrs) {
450  if (!TSchedModel.hasInstrSchedModel())
451  return true;
452 
453  // Compute current resource length
454 
455  //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
457  MBBarr.push_back(MBB);
458  unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
459 
460  // Deal with SC rather than Instructions.
463 
464  instr2instrSC(InsInstrs, InsInstrsSC);
465  instr2instrSC(DelInstrs, DelInstrsSC);
466 
467  ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
468  ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
469 
470  // Compute new resource length.
471  unsigned ResLenAfterCombine =
472  BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
473 
474  LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
475  << ResLenBeforeCombine
476  << " and after: " << ResLenAfterCombine << "\n";);
477  LLVM_DEBUG(
478  ResLenAfterCombine <=
479  ResLenBeforeCombine + TII->getExtendResourceLenLimit()
480  ? dbgs() << "\t\t As result it IMPROVES/PRESERVES Resource Length\n"
481  : dbgs() << "\t\t As result it DOES NOT improve/preserve Resource "
482  "Length\n");
483 
484  return ResLenAfterCombine <=
485  ResLenBeforeCombine + TII->getExtendResourceLenLimit();
486 }
487 
488 /// \returns true when new instruction sequence should be generated
489 /// independent if it lengthens critical path or not
490 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize,
491  bool OptForSize) {
492  if (OptForSize && (NewSize < OldSize))
493  return true;
494  if (!TSchedModel.hasInstrSchedModelOrItineraries())
495  return true;
496  return false;
497 }
498 
499 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
500 /// depths if requested.
501 ///
502 /// \param MBB basic block to insert instructions in
503 /// \param MI current machine instruction
504 /// \param InsInstrs new instructions to insert in \p MBB
505 /// \param DelInstrs instruction to delete from \p MBB
506 /// \param MinInstr is a pointer to the machine trace information
507 /// \param RegUnits set of live registers, needed to compute instruction depths
508 /// \param TII is target instruction info, used to call target hook
509 /// \param Pattern is used to call target hook finalizeInsInstrs
510 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
511 /// otherwise invalidate the trace
516  SparseSet<LiveRegUnit> &RegUnits,
517  const TargetInstrInfo *TII,
519  bool IncrementalUpdate) {
520  // If we want to fix up some placeholder for some target, do it now.
521  // We need this because in genAlternativeCodeSequence, we have not decided the
522  // better pattern InsInstrs or DelInstrs, so we don't want generate some
523  // sideeffect to the function. For example we need to delay the constant pool
524  // entry creation here after InsInstrs is selected as better pattern.
525  // Otherwise the constant pool entry created for InsInstrs will not be deleted
526  // even if InsInstrs is not the better pattern.
527  TII->finalizeInsInstrs(MI, Pattern, InsInstrs);
528 
529  for (auto *InstrPtr : InsInstrs)
531 
532  for (auto *InstrPtr : DelInstrs) {
533  InstrPtr->eraseFromParent();
534  // Erase all LiveRegs defined by the removed instruction
535  for (auto *I = RegUnits.begin(); I != RegUnits.end();) {
536  if (I->MI == InstrPtr)
537  I = RegUnits.erase(I);
538  else
539  I++;
540  }
541  }
542 
543  if (IncrementalUpdate)
544  for (auto *InstrPtr : InsInstrs)
545  MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
546  else
547  MinInstr->invalidate(MBB);
548 
549  NumInstCombined++;
550 }
551 
552 // Check that the difference between original and new latency is decreasing for
553 // later patterns. This helps to discover sub-optimal pattern orderings.
554 void MachineCombiner::verifyPatternOrder(
557  long PrevLatencyDiff = std::numeric_limits<long>::max();
558  (void)PrevLatencyDiff; // Variable is used in assert only.
559  for (auto P : Patterns) {
562  DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
563  TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
564  InstrIdxForVirtReg);
565  // Found pattern, but did not generate alternative sequence.
566  // This can happen e.g. when an immediate could not be materialized
567  // in a single instruction.
568  if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
569  continue;
570 
571  unsigned NewRootLatency, RootLatency;
572  std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
573  Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
574  long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
575  assert(CurrentLatencyDiff <= PrevLatencyDiff &&
576  "Current pattern is better than previous pattern.");
577  PrevLatencyDiff = CurrentLatencyDiff;
578  }
579 }
580 
581 /// Substitute a slow code sequence with a faster one by
582 /// evaluating instruction combining pattern.
583 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
584 /// combining based on machine trace metrics. Only combine a sequence of
585 /// instructions when this neither lengthens the critical path nor increases
586 /// resource pressure. When optimizing for codesize always combine when the new
587 /// sequence is shorter.
588 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
589  bool Changed = false;
590  LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
591 
592  bool IncrementalUpdate = false;
593  auto BlockIter = MBB->begin();
594  decltype(BlockIter) LastUpdate;
595  // Check if the block is in a loop.
596  const MachineLoop *ML = MLI->getLoopFor(MBB);
597  if (!MinInstr)
598  MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
599 
600  SparseSet<LiveRegUnit> RegUnits;
601  RegUnits.setUniverse(TRI->getNumRegUnits());
602 
603  bool OptForSize = OptSize || llvm::shouldOptimizeForSize(MBB, PSI, MBFI);
604 
605  bool DoRegPressureReduce =
606  TII->shouldReduceRegisterPressure(MBB, &RegClassInfo);
607 
608  while (BlockIter != MBB->end()) {
609  auto &MI = *BlockIter++;
611  // The motivating example is:
612  //
613  // MUL Other MUL_op1 MUL_op2 Other
614  // \ / \ | /
615  // ADD/SUB => MADD/MSUB
616  // (=Root) (=NewRoot)
617 
618  // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
619  // usually beneficial for code size it unfortunately can hurt performance
620  // when the ADD is on the critical path, but the MUL is not. With the
621  // substitution the MUL becomes part of the critical path (in form of the
622  // MADD) and can lengthen it on architectures where the MADD latency is
623  // longer than the ADD latency.
624  //
625  // For each instruction we check if it can be the root of a combiner
626  // pattern. Then for each pattern the new code sequence in form of MI is
627  // generated and evaluated. When the efficiency criteria (don't lengthen
628  // critical path, don't use more resources) is met the new sequence gets
629  // hooked up into the basic block before the old sequence is removed.
630  //
631  // The algorithm does not try to evaluate all patterns and pick the best.
632  // This is only an artificial restriction though. In practice there is
633  // mostly one pattern, and getMachineCombinerPatterns() can order patterns
634  // based on an internal cost heuristic. If
635  // machine-combiner-verify-pattern-order is enabled, all patterns are
636  // checked to ensure later patterns do not provide better latency savings.
637 
638  if (!TII->getMachineCombinerPatterns(MI, Patterns, DoRegPressureReduce))
639  continue;
640 
641  if (VerifyPatternOrder)
642  verifyPatternOrder(MBB, MI, Patterns);
643 
644  for (auto P : Patterns) {
647  DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
648  TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
649  InstrIdxForVirtReg);
650  unsigned NewInstCount = InsInstrs.size();
651  unsigned OldInstCount = DelInstrs.size();
652  // Found pattern, but did not generate alternative sequence.
653  // This can happen e.g. when an immediate could not be materialized
654  // in a single instruction.
655  if (!NewInstCount)
656  continue;
657 
658  LLVM_DEBUG(if (dump_intrs) {
659  dbgs() << "\tFor the Pattern (" << (int)P
660  << ") these instructions could be removed\n";
661  for (auto const *InstrPtr : DelInstrs)
662  InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
663  /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
664  dbgs() << "\tThese instructions could replace the removed ones\n";
665  for (auto const *InstrPtr : InsInstrs)
666  InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
667  /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
668  });
669 
670  bool SubstituteAlways = false;
671  if (ML && TII->isThroughputPattern(P))
672  SubstituteAlways = true;
673 
674  if (IncrementalUpdate && LastUpdate != BlockIter) {
675  // Update depths since the last incremental update.
676  MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
677  LastUpdate = BlockIter;
678  }
679 
680  if (DoRegPressureReduce &&
683  if (MBB->size() > inc_threshold) {
684  // Use incremental depth updates for basic blocks above threshold
685  IncrementalUpdate = true;
686  LastUpdate = BlockIter;
687  }
688  if (reduceRegisterPressure(MI, MBB, InsInstrs, DelInstrs, P)) {
689  // Replace DelInstrs with InsInstrs.
690  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
691  RegUnits, TII, P, IncrementalUpdate);
692  Changed |= true;
693 
694  // Go back to previous instruction as it may have ILP reassociation
695  // opportunity.
696  BlockIter--;
697  break;
698  }
699  }
700 
701  // Substitute when we optimize for codesize and the new sequence has
702  // fewer instructions OR
703  // the new sequence neither lengthens the critical path nor increases
704  // resource pressure.
705  if (SubstituteAlways ||
706  doSubstitute(NewInstCount, OldInstCount, OptForSize)) {
707  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
708  RegUnits, TII, P, IncrementalUpdate);
709  // Eagerly stop after the first pattern fires.
710  Changed = true;
711  break;
712  } else {
713  // For big basic blocks, we only compute the full trace the first time
714  // we hit this. We do not invalidate the trace, but instead update the
715  // instruction depths incrementally.
716  // NOTE: Only the instruction depths up to MI are accurate. All other
717  // trace information is not updated.
718  MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
719  Traces->verifyAnalysis();
720  if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
721  InstrIdxForVirtReg, P,
722  !IncrementalUpdate) &&
723  preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
724  if (MBB->size() > inc_threshold) {
725  // Use incremental depth updates for basic blocks above treshold
726  IncrementalUpdate = true;
727  LastUpdate = BlockIter;
728  }
729 
730  insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
731  RegUnits, TII, P, IncrementalUpdate);
732 
733  // Eagerly stop after the first pattern fires.
734  Changed = true;
735  break;
736  }
737  // Cleanup instructions of the alternative code sequence. There is no
738  // use for them.
739  MachineFunction *MF = MBB->getParent();
740  for (auto *InstrPtr : InsInstrs)
741  MF->deleteMachineInstr(InstrPtr);
742  }
743  InstrIdxForVirtReg.clear();
744  }
745  }
746 
747  if (Changed && IncrementalUpdate)
748  Traces->invalidate(MBB);
749  return Changed;
750 }
751 
752 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
753  STI = &MF.getSubtarget();
754  TII = STI->getInstrInfo();
755  TRI = STI->getRegisterInfo();
756  SchedModel = STI->getSchedModel();
757  TSchedModel.init(STI);
758  MRI = &MF.getRegInfo();
759  MLI = &getAnalysis<MachineLoopInfo>();
760  Traces = &getAnalysis<MachineTraceMetrics>();
761  PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
762  MBFI = (PSI && PSI->hasProfileSummary()) ?
763  &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :
764  nullptr;
765  MinInstr = nullptr;
766  OptSize = MF.getFunction().hasOptSize();
767  RegClassInfo.runOnMachineFunction(MF);
768 
769  LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
770  if (!TII->useMachineCombiner()) {
771  LLVM_DEBUG(
772  dbgs()
773  << " Skipping pass: Target does not support machine combiner\n");
774  return false;
775  }
776 
777  bool Changed = false;
778 
779  // Try to combine instructions.
780  for (auto &MBB : MF)
781  Changed |= combineInstructions(&MBB);
782 
783  return Changed;
784 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MachineTraceMetrics::InstrCycles::Depth
unsigned Depth
Earliest issue cycle as determined by data dependencies and instruction latencies from the beginning ...
Definition: MachineTraceMetrics.h:245
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::MachineTraceMetrics::Ensemble::invalidate
void invalidate(const MachineBasicBlock *MBB)
Invalidate traces through BadMBB.
Definition: MachineTraceMetrics.cpp:523
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
llvm::MachineRegisterInfo::getUniqueVRegDef
MachineInstr * getUniqueVRegDef(Register Reg) const
getUniqueVRegDef - Return the unique machine instr that defines the specified virtual register or nul...
Definition: MachineRegisterInfo.cpp:407
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineSizeOpts.h
RegisterClassInfo.h
llvm::MachineCombinerPattern::FNMSUB
@ FNMSUB
llvm::SparseSet::begin
const_iterator begin() const
Definition: SparseSet.h:174
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::MachineTraceMetrics::TS_MinInstrCount
@ TS_MinInstrCount
Select the trace through a block that has the fewest instructions.
Definition: MachineTraceMetrics.h:379
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
insertDeleteInstructions
static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI, SmallVector< MachineInstr *, 16 > InsInstrs, SmallVector< MachineInstr *, 16 > DelInstrs, MachineTraceMetrics::Ensemble *MinInstr, SparseSet< LiveRegUnit > &RegUnits, const TargetInstrInfo *TII, MachineCombinerPattern Pattern, bool IncrementalUpdate)
Inserts InsInstrs and deletes DelInstrs.
Definition: MachineCombiner.cpp:512
DenseMap.h
TargetInstrInfo.h
llvm::MachineCombinerPattern::REASSOC_XY_BAC
@ REASSOC_XY_BAC
CombinerObjective::MustReduceRegisterPressure
@ MustReduceRegisterPressure
llvm::MachineRegisterInfo::reg_end
static reg_iterator reg_end()
Definition: MachineRegisterInfo.h:292
llvm::MachineCombinerPattern::SUBADD_OP2
@ SUBADD_OP2
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MCRegisterInfo::getNumRegUnits
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Definition: MCRegisterInfo.h:505
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
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::MachineCombinerPattern::REASSOC_AX_YB
@ REASSOC_AX_YB
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineTraceMetrics::Trace::getInstrCycles
InstrCycles getInstrCycles(const MachineInstr &MI) const
Return the depth and height of MI.
Definition: MachineTraceMetrics.h:298
CommandLine.h
llvm::TargetRegisterClass::contains
bool contains(Register Reg) const
Return true if the specified register is included in this register class.
Definition: TargetRegisterInfo.h:97
llvm::MachineCombinerPattern::FMADD_AX
@ FMADD_AX
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:667
llvm::shouldOptimizeForSize
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Definition: MachineSizeOpts.cpp:183
llvm::MachineTraceMetrics::Ensemble::updateDepth
void updateDepth(TraceBlockInfo &TBI, const MachineInstr &, SparseSet< LiveRegUnit > &RegUnits)
Updates the depth of an machine instruction, given RegUnits.
Definition: MachineTraceMetrics.cpp:782
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
MachineLoopInfo.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
llvm::PPCISD::SC
@ SC
CHAIN = SC CHAIN, Imm128 - System call.
Definition: PPCISelLowering.h:419
llvm::MachineBlockFrequencyInfo
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Definition: MachineBlockFrequencyInfo.h:33
VerifyPatternOrder
static cl::opt< bool > VerifyPatternOrder("machine-combiner-verify-pattern-order", cl::Hidden, cl::desc("Verify that the generated patterns are ordered by increasing latency"), cl::init(false))
llvm::SparseSet::end
const_iterator end() const
Definition: SparseSet.h:175
llvm::MachineCombinerPattern::REASSOC_XMM_AMM_BMM
@ REASSOC_XMM_AMM_BMM
llvm::MachineOperand::isUse
bool isUse() const
Definition: MachineOperand.h:369
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:109
getLatency
static int getLatency(LLVMDisasmContext *DC, const MCInst &Inst)
Gets latency information for Inst, based on DC information.
Definition: Disassembler.cpp:194
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineFunction::deleteMachineInstr
void deleteMachineInstr(MachineInstr *MI)
DeleteMachineInstr - Delete the given MachineInstr.
Definition: MachineFunction.cpp:418
false
Definition: StackSlotColoring.cpp:141
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
MachineCombinerPattern.h
llvm::TargetRegisterClass::hasSuperClassEq
bool hasSuperClassEq(const TargetRegisterClass *RC) const
Returns true if RC is a super-class of or equal to this class.
Definition: TargetRegisterInfo.h:142
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::TargetRegisterInfo::getMatchingSuperRegClass
virtual const TargetRegisterClass * getMatchingSuperRegClass(const TargetRegisterClass *A, const TargetRegisterClass *B, unsigned Idx) const
Return a subclass of the specified register class A so that each register in it has a sub-register of...
Definition: TargetRegisterInfo.cpp:303
llvm::MachineTraceMetrics::Trace
A trace represents a plausible sequence of executed basic blocks that passes through the current basi...
Definition: MachineTraceMetrics.h:255
CombinerObjective::Default
@ Default
llvm::MachineOperand::getParent
MachineInstr * getParent()
getParent - Return the instruction that this operand belongs to.
Definition: MachineOperand.h:237
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:40
llvm::MachineTraceMetrics::Trace::isDepInTrace
bool isDepInTrace(const MachineInstr &DefMI, const MachineInstr &UseMI) const
A dependence is useful if the basic block of the defining instruction is part of the trace of the use...
Definition: MachineTraceMetrics.cpp:1277
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::cl::opt
Definition: CommandLine.h:1412
CombinerObjective
CombinerObjective
The combiner's goal may differ based on which pattern it is attempting to optimize.
Definition: MachineCombiner.cpp:304
LazyMachineBlockFrequencyInfo.h
===- LazyMachineBlockFrequencyInfo.h - Lazy Block Frequency -*- C++ -*–===//
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
TargetSchedule.h
inc_threshold
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))
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:110
llvm::TargetSchedModel
Provide an instruction scheduling machine model to CodeGen passes.
Definition: TargetSchedule.h:30
llvm::MachineOperand::isReg
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Definition: MachineOperand.h:320
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
ProfileSummaryInfo.h
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::DenseMap< unsigned, unsigned >
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:194
MachineFunctionPass.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::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:567
llvm::initializeMachineCombinerPass
void initializeMachineCombinerPass(PassRegistry &)
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::size
unsigned size() const
Definition: MachineBasicBlock.h:275
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:29
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
llvm::MachineTraceMetrics::Trace::getResourceLength
unsigned getResourceLength(ArrayRef< const MachineBasicBlock * > Extrablocks=None, ArrayRef< const MCSchedClassDesc * > ExtraInstrs=None, ArrayRef< const MCSchedClassDesc * > RemoveInstrs=None) const
Return the resource length of the trace.
Definition: MachineTraceMetrics.cpp:1223
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1300
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineCombinerPattern::REASSOC_AX_BY
@ REASSOC_AX_BY
llvm::LazyMachineBlockFrequencyInfoPass
This is an alternative analysis pass to MachineBlockFrequencyInfo.
Definition: LazyMachineBlockFrequencyInfo.h:37
llvm::MachineCombinerPattern::REASSOC_XY_BCA
@ REASSOC_XY_BCA
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::MachineCombinerPattern::SUBADD_OP1
@ SUBADD_OP1
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
TargetSubtargetInfo.h
llvm::MachineOperand::isDef
bool isDef() const
Definition: MachineOperand.h:374
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::Function::hasOptSize
bool hasOptSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:645
getCombinerObjective
static CombinerObjective getCombinerObjective(MachineCombinerPattern P)
Definition: MachineCombiner.cpp:310
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner", false, false) INITIALIZE_PASS_END(MachineCombiner
llvm::MachineRegisterInfo::reg_begin
reg_iterator reg_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:289
llvm::MachineTraceMetrics::Ensemble
A trace ensemble is a collection of traces selected using the same strategy, for example 'minimum res...
Definition: MachineTraceMetrics.h:321
llvm::MachineCombinerPattern::REASSOC_XY_AMM_BMM
@ REASSOC_XY_AMM_BMM
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:84
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1327
DEBUG_TYPE
#define DEBUG_TYPE
Definition: MachineCombiner.cpp:37
llvm::SparseSet::erase
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:288
llvm::MCSchedModel
Machine model for scheduling, bundling, and heuristics.
Definition: MCSchedule.h:244
llvm::InstCombiner
The core instruction combiner logic.
Definition: InstCombiner.h:45
llvm::makeArrayRef
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:475
dump_intrs
static cl::opt< bool > dump_intrs("machine-combiner-dump-subst-intrs", cl::Hidden, cl::desc("Dump all substituted intrs"), cl::init(false))
llvm::Pattern
Definition: FileCheckImpl.h:614
llvm::MachineInstr::findRegisterDefOperandIdx
int findRegisterDefOperandIdx(Register 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.
Definition: MachineInstr.cpp:1036
Machine
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:370
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::MachineTraceMetrics::Trace::getInstrSlack
unsigned getInstrSlack(const MachineInstr &MI) const
Return the slack of MI.
Definition: MachineTraceMetrics.cpp:1173
llvm::MachineCombinerPattern::REASSOC_XA_BY
@ REASSOC_XA_BY
llvm::MachineCombinerID
char & MachineCombinerID
This pass performs instruction combining using trace metrics to estimate critical-path and resource d...
Definition: MachineCombiner.cpp:131
llvm::MachineRegisterInfo::defusechain_iterator
reg_begin/reg_end - Provide iteration support to walk over all definitions and uses of a register wit...
Definition: MachineRegisterInfo.h:274
CombinerObjective::MustReduceDepth
@ MustReduceDepth
llvm::SmallVectorImpl< MachineInstr * >
llvm::SparseSet
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
Definition: SparseSet.h:124
llvm::MachineCombinerPattern::REASSOC_XA_YB
@ REASSOC_XA_YB
llvm::cl::desc
Definition: CommandLine.h:413
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
MachineFunction.h
llvm::MachineCombinerPattern::FMSUB
@ FMSUB
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::MachineTraceMetrics
Definition: MachineTraceMetrics.h:87
InitializePasses.h
llvm::MachineInstr::operands
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:641
llvm::MachineInstr::findRegisterUseOperandIdx
int findRegisterUseOperandIdx(Register 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.
Definition: MachineInstr.cpp:987
TargetRegisterInfo.h
llvm::MachineBasicBlock::getName
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Definition: MachineBasicBlock.cpp:311
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
MachineDominators.h
llvm::MachineCombinerPattern
MachineCombinerPattern
These are instruction patterns matched by the machine combiner pass.
Definition: MachineCombinerPattern.h:20
llvm::MachineCombinerPattern::FMADD_XA
@ FMADD_XA