llvm/lib/CodeGen/MachineCombiner.cpp

   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"
  15 #include "llvm/Analysis/ProfileSummaryInfo.h"
  16 #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h"
  17 #include "llvm/CodeGen/MachineDominators.h"
  18 #include "llvm/CodeGen/MachineFunction.h"
  19 #include "llvm/CodeGen/MachineFunctionPass.h"
  20 #include "llvm/CodeGen/MachineLoopInfo.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/MachineSizeOpts.h"
  23 #include "llvm/CodeGen/MachineTraceMetrics.h"
  24 #include "llvm/CodeGen/Passes.h"
  25 #include "llvm/CodeGen/RegisterClassInfo.h"
  26 #include "llvm/CodeGen/TargetInstrInfo.h"
  27 #include "llvm/CodeGen/TargetRegisterInfo.h"
  28 #include "llvm/CodeGen/TargetSchedule.h"
  29 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  30 #include "llvm/InitializePasses.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/raw_ostream.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
  51 static cl::opt<bool> VerifyPatternOrder(
  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
  57 static cl::opt<bool> VerifyPatternOrder(
  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;
  70   MachineRegisterInfo *MRI;
  71   MachineLoopInfo *MLI; // Current MachineLoopInfo
  72   MachineTraceMetrics *Traces;
  73   MachineTraceMetrics::Ensemble *MinInstr;
  74   MachineBlockFrequencyInfo *MBFI;
  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) {
  86     initializeMachineCombinerPass(*PassRegistry::getPassRegistry());
  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   unsigned getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
  97                     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
  98                     MachineTraceMetrics::Trace BlockTrace);
  99   unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
 100                       MachineTraceMetrics::Trace BlockTrace);
 101   bool
 102   improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
 103                           MachineTraceMetrics::Trace BlockTrace,
 104                           SmallVectorImpl<MachineInstr *> &InsInstrs,
 105                           SmallVectorImpl<MachineInstr *> &DelInstrs,
 106                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
 107                           MachineCombinerPattern Pattern, bool SlackIsAccurate);
 108   bool reduceRegisterPressure(MachineInstr &Root, MachineBasicBlock *MBB,
 109                               SmallVectorImpl<MachineInstr *> &InsInstrs,
 110                               SmallVectorImpl<MachineInstr *> &DelInstrs,
 111                               MachineCombinerPattern Pattern);
 112   bool preservesResourceLen(MachineBasicBlock *MBB,
 113                             MachineTraceMetrics::Trace BlockTrace,
 114                             SmallVectorImpl<MachineInstr *> &InsInstrs,
 115                             SmallVectorImpl<MachineInstr *> &DelInstrs);
 116   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
 117                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
 118   std::pair<unsigned, unsigned>
 119   getLatenciesForInstrSequences(MachineInstr &MI,
 120                                 SmallVectorImpl<MachineInstr *> &InsInstrs,
 121                                 SmallVectorImpl<MachineInstr *> &DelInstrs,
 122                                 MachineTraceMetrics::Trace BlockTrace);
 123
 124   void verifyPatternOrder(MachineBasicBlock *MBB, MachineInstr &Root,
 125                           SmallVector<MachineCombinerPattern, 16> &Patterns);
 126 };
 127 }
 128
 129 char MachineCombiner::ID = 0;
 130 char &llvm::MachineCombinerID = MachineCombiner::ID;
 131
 132 INITIALIZE_PASS_BEGIN(MachineCombiner, DEBUG_TYPE,
 133                       "Machine InstCombiner", false, false)
 134 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 135 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
 136 INITIALIZE_PASS_END(MachineCombiner, DEBUG_TYPE, "Machine InstCombiner",
 137                     false, false)
 138
 139 void MachineCombiner::getAnalysisUsage(AnalysisUsage &AU) const {
 140   AU.setPreservesCFG();
 141   AU.addPreserved<MachineDominatorTree>();
 142   AU.addRequired<MachineLoopInfo>();
 143   AU.addPreserved<MachineLoopInfo>();
 144   AU.addRequired<MachineTraceMetrics>();
 145   AU.addPreserved<MachineTraceMetrics>();
 146   AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
 147   AU.addRequired<ProfileSummaryInfoWrapperPass>();
 148   MachineFunctionPass::getAnalysisUsage(AU);
 149 }
 150
 151 MachineInstr *MachineCombiner::getOperandDef(const MachineOperand &MO) {
 152   MachineInstr *DefInstr = nullptr;
 153   // We need a virtual register definition.
 154   if (MO.isReg() && Register::isVirtualRegister(MO.getReg()))
 155     DefInstr = MRI->getUniqueVRegDef(MO.getReg());
 156   // PHI's have no depth etc.
 157   if (DefInstr && DefInstr->isPHI())
 158     DefInstr = nullptr;
 159   return DefInstr;
 160 }
 161
 162 /// Computes depth of instructions in vector \InsInstr.
 163 ///
 164 /// \param InsInstrs is a vector of machine instructions
 165 /// \param InstrIdxForVirtReg is a dense map of virtual register to index
 166 /// of defining machine instruction in \p InsInstrs
 167 /// \param BlockTrace is a trace of machine instructions
 168 ///
 169 /// \returns Depth of last instruction in \InsInstrs ("NewRoot")
 170 unsigned
 171 MachineCombiner::getDepth(SmallVectorImpl<MachineInstr *> &InsInstrs,
 172                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
 173                           MachineTraceMetrics::Trace BlockTrace) {
 174   SmallVector<unsigned, 16> InstrDepth;
 175   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
 176          "Missing machine model\n");
 177
 178   // For each instruction in the new sequence compute the depth based on the
 179   // operands. Use the trace information when possible. For new operands which
 180   // are tracked in the InstrIdxForVirtReg map depth is looked up in InstrDepth
 181   for (auto *InstrPtr : InsInstrs) { // for each Use
 182     unsigned IDepth = 0;
 183     for (const MachineOperand &MO : InstrPtr->operands()) {
 184       // Check for virtual register operand.
 185       if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
 186         continue;
 187       if (!MO.isUse())
 188         continue;
 189       unsigned DepthOp = 0;
 190       unsigned LatencyOp = 0;
 191       DenseMap<unsigned, unsigned>::iterator II =
 192           InstrIdxForVirtReg.find(MO.getReg());
 193       if (II != InstrIdxForVirtReg.end()) {
 194         // Operand is new virtual register not in trace
 195         assert(II->second < InstrDepth.size() && "Bad Index");
 196         MachineInstr *DefInstr = InsInstrs[II->second];
 197         assert(DefInstr &&
 198                "There must be a definition for a new virtual register");
 199         DepthOp = InstrDepth[II->second];
 200         int DefIdx = DefInstr->findRegisterDefOperandIdx(MO.getReg());
 201         int UseIdx = InstrPtr->findRegisterUseOperandIdx(MO.getReg());
 202         LatencyOp = TSchedModel.computeOperandLatency(DefInstr, DefIdx,
 203                                                       InstrPtr, UseIdx);
 204       } else {
 205         MachineInstr *DefInstr = getOperandDef(MO);
 206         if (DefInstr) {
 207           DepthOp = BlockTrace.getInstrCycles(*DefInstr).Depth;
 208           LatencyOp = TSchedModel.computeOperandLatency(
 209               DefInstr, DefInstr->findRegisterDefOperandIdx(MO.getReg()),
 210               InstrPtr, InstrPtr->findRegisterUseOperandIdx(MO.getReg()));
 211         }
 212       }
 213       IDepth = std::max(IDepth, DepthOp + LatencyOp);
 214     }
 215     InstrDepth.push_back(IDepth);
 216   }
 217   unsigned NewRootIdx = InsInstrs.size() - 1;
 218   return InstrDepth[NewRootIdx];
 219 }
 220
 221 /// Computes instruction latency as max of latency of defined operands.
 222 ///
 223 /// \param Root is a machine instruction that could be replaced by NewRoot.
 224 /// It is used to compute a more accurate latency information for NewRoot in
 225 /// case there is a dependent instruction in the same trace (\p BlockTrace)
 226 /// \param NewRoot is the instruction for which the latency is computed
 227 /// \param BlockTrace is a trace of machine instructions
 228 ///
 229 /// \returns Latency of \p NewRoot
 230 unsigned MachineCombiner::getLatency(MachineInstr *Root, MachineInstr *NewRoot,
 231                                      MachineTraceMetrics::Trace BlockTrace) {
 232   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
 233          "Missing machine model\n");
 234
 235   // Check each definition in NewRoot and compute the latency
 236   unsigned NewRootLatency = 0;
 237
 238   for (const MachineOperand &MO : NewRoot->operands()) {
 239     // Check for virtual register operand.
 240     if (!(MO.isReg() && Register::isVirtualRegister(MO.getReg())))
 241       continue;
 242     if (!MO.isDef())
 243       continue;
 244     // Get the first instruction that uses MO
 245     MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(MO.getReg());
 246     RI++;
 247     if (RI == MRI->reg_end())
 248       continue;
 249     MachineInstr *UseMO = RI->getParent();
 250     unsigned LatencyOp = 0;
 251     if (UseMO && BlockTrace.isDepInTrace(*Root, *UseMO)) {
 252       LatencyOp = TSchedModel.computeOperandLatency(
 253           NewRoot, NewRoot->findRegisterDefOperandIdx(MO.getReg()), UseMO,
 254           UseMO->findRegisterUseOperandIdx(MO.getReg()));
 255     } else {
 256       LatencyOp = TSchedModel.computeInstrLatency(NewRoot);
 257     }
 258     NewRootLatency = std::max(NewRootLatency, LatencyOp);
 259   }
 260   return NewRootLatency;
 261 }
 262
 263 /// The combiner's goal may differ based on which pattern it is attempting
 264 /// to optimize.
 265 enum class CombinerObjective {
 266   MustReduceDepth,            // The data dependency chain must be improved.
 267   MustReduceRegisterPressure, // The register pressure must be reduced.
 268   Default                     // The critical path must not be lengthened.
 269 };
 270
 271 static CombinerObjective getCombinerObjective(MachineCombinerPattern P) {
 272   // TODO: If C++ ever gets a real enum class, make this part of the
 273   // MachineCombinerPattern class.
 274   switch (P) {
 275   case MachineCombinerPattern::REASSOC_AX_BY:
 276   case MachineCombinerPattern::REASSOC_AX_YB:
 277   case MachineCombinerPattern::REASSOC_XA_BY:
 278   case MachineCombinerPattern::REASSOC_XA_YB:
 279   case MachineCombinerPattern::REASSOC_XY_AMM_BMM:
 280   case MachineCombinerPattern::REASSOC_XMM_AMM_BMM:
 281     return CombinerObjective::MustReduceDepth;
 282   case MachineCombinerPattern::REASSOC_XY_BCA:
 283   case MachineCombinerPattern::REASSOC_XY_BAC:
 284     return CombinerObjective::MustReduceRegisterPressure;
 285   default:
 286     return CombinerObjective::Default;
 287   }
 288 }
 289
 290 /// Estimate the latency of the new and original instruction sequence by summing
 291 /// up the latencies of the inserted and deleted instructions. This assumes
 292 /// that the inserted and deleted instructions are dependent instruction chains,
 293 /// which might not hold in all cases.
 294 std::pair<unsigned, unsigned> MachineCombiner::getLatenciesForInstrSequences(
 295     MachineInstr &MI, SmallVectorImpl<MachineInstr *> &InsInstrs,
 296     SmallVectorImpl<MachineInstr *> &DelInstrs,
 297     MachineTraceMetrics::Trace BlockTrace) {
 298   assert(!InsInstrs.empty() && "Only support sequences that insert instrs.");
 299   unsigned NewRootLatency = 0;
 300   // NewRoot is the last instruction in the \p InsInstrs vector.
 301   MachineInstr *NewRoot = InsInstrs.back();
 302   for (unsigned i = 0; i < InsInstrs.size() - 1; i++)
 303     NewRootLatency += TSchedModel.computeInstrLatency(InsInstrs[i]);
 304   NewRootLatency += getLatency(&MI, NewRoot, BlockTrace);
 305
 306   unsigned RootLatency = 0;
 307   for (auto I : DelInstrs)
 308     RootLatency += TSchedModel.computeInstrLatency(I);
 309
 310   return {NewRootLatency, RootLatency};
 311 }
 312
 313 bool MachineCombiner::reduceRegisterPressure(
 314     MachineInstr &Root, MachineBasicBlock *MBB,
 315     SmallVectorImpl<MachineInstr *> &InsInstrs,
 316     SmallVectorImpl<MachineInstr *> &DelInstrs,
 317     MachineCombinerPattern Pattern) {
 318   // FIXME: for now, we don't do any check for the register pressure patterns.
 319   // We treat them as always profitable. But we can do better if we make
 320   // RegPressureTracker class be aware of TIE attribute. Then we can get an
 321   // accurate compare of register pressure with DelInstrs or InsInstrs.
 322   return true;
 323 }
 324
 325 /// The DAGCombine code sequence ends in MI (Machine Instruction) Root.
 326 /// The new code sequence ends in MI NewRoot. A necessary condition for the new
 327 /// sequence to replace the old sequence is that it cannot lengthen the critical
 328 /// path. The definition of "improve" may be restricted by specifying that the
 329 /// new path improves the data dependency chain (MustReduceDepth).
 330 bool MachineCombiner::improvesCriticalPathLen(
 331     MachineBasicBlock *MBB, MachineInstr *Root,
 332     MachineTraceMetrics::Trace BlockTrace,
 333     SmallVectorImpl<MachineInstr *> &InsInstrs,
 334     SmallVectorImpl<MachineInstr *> &DelInstrs,
 335     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
 336     MachineCombinerPattern Pattern,
 337     bool SlackIsAccurate) {
 338   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
 339          "Missing machine model\n");
 340   // Get depth and latency of NewRoot and Root.
 341   unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
 342   unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
 343
 344   LLVM_DEBUG(dbgs() << "  Dependence data for " << *Root << "\tNewRootDepth: "
 345                     << NewRootDepth << "\tRootDepth: " << RootDepth);
 346
 347   // For a transform such as reassociation, the cost equation is
 348   // conservatively calculated so that we must improve the depth (data
 349   // dependency cycles) in the critical path to proceed with the transform.
 350   // Being conservative also protects against inaccuracies in the underlying
 351   // machine trace metrics and CPU models.
 352   if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth) {
 353     LLVM_DEBUG(dbgs() << "\tIt MustReduceDepth ");
 354     LLVM_DEBUG(NewRootDepth < RootDepth
 355                    ? dbgs() << "\t  and it does it\n"
 356                    : dbgs() << "\t  but it does NOT do it\n");
 357     return NewRootDepth < RootDepth;
 358   }
 359
 360   // A more flexible cost calculation for the critical path includes the slack
 361   // of the original code sequence. This may allow the transform to proceed
 362   // even if the instruction depths (data dependency cycles) become worse.
 363
 364   // Account for the latency of the inserted and deleted instructions by
 365   unsigned NewRootLatency, RootLatency;
 366   std::tie(NewRootLatency, RootLatency) =
 367       getLatenciesForInstrSequences(*Root, InsInstrs, DelInstrs, BlockTrace);
 368
 369   unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
 370   unsigned NewCycleCount = NewRootDepth + NewRootLatency;
 371   unsigned OldCycleCount =
 372       RootDepth + RootLatency + (SlackIsAccurate ? RootSlack : 0);
 373   LLVM_DEBUG(dbgs() << "\n\tNewRootLatency: " << NewRootLatency
 374                     << "\tRootLatency: " << RootLatency << "\n\tRootSlack: "
 375                     << RootSlack << " SlackIsAccurate=" << SlackIsAccurate
 376                     << "\n\tNewRootDepth + NewRootLatency = " << NewCycleCount
 377                     << "\n\tRootDepth + RootLatency + RootSlack = "
 378                     << OldCycleCount;);
 379   LLVM_DEBUG(NewCycleCount <= OldCycleCount
 380                  ? dbgs() << "\n\t  It IMPROVES PathLen because"
 381                  : dbgs() << "\n\t  It DOES NOT improve PathLen because");
 382   LLVM_DEBUG(dbgs() << "\n\t\tNewCycleCount = " << NewCycleCount
 383                     << ", OldCycleCount = " << OldCycleCount << "\n");
 384
 385   return NewCycleCount <= OldCycleCount;
 386 }
 387
 388 /// helper routine to convert instructions into SC
 389 void MachineCombiner::instr2instrSC(
 390     SmallVectorImpl<MachineInstr *> &Instrs,
 391     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {
 392   for (auto *InstrPtr : Instrs) {
 393     unsigned Opc = InstrPtr->getOpcode();
 394     unsigned Idx = TII->get(Opc).getSchedClass();
 395     const MCSchedClassDesc *SC = SchedModel.getSchedClassDesc(Idx);
 396     InstrsSC.push_back(SC);
 397   }
 398 }
 399
 400 /// True when the new instructions do not increase resource length
 401 bool MachineCombiner::preservesResourceLen(
 402     MachineBasicBlock *MBB, MachineTraceMetrics::Trace BlockTrace,
 403     SmallVectorImpl<MachineInstr *> &InsInstrs,
 404     SmallVectorImpl<MachineInstr *> &DelInstrs) {
 405   if (!TSchedModel.hasInstrSchedModel())
 406     return true;
 407
 408   // Compute current resource length
 409
 410   //ArrayRef<const MachineBasicBlock *> MBBarr(MBB);
 411   SmallVector <const MachineBasicBlock *, 1> MBBarr;
 412   MBBarr.push_back(MBB);
 413   unsigned ResLenBeforeCombine = BlockTrace.getResourceLength(MBBarr);
 414
 415   // Deal with SC rather than Instructions.
 416   SmallVector<const MCSchedClassDesc *, 16> InsInstrsSC;
 417   SmallVector<const MCSchedClassDesc *, 16> DelInstrsSC;
 418
 419   instr2instrSC(InsInstrs, InsInstrsSC);
 420   instr2instrSC(DelInstrs, DelInstrsSC);
 421
 422   ArrayRef<const MCSchedClassDesc *> MSCInsArr = makeArrayRef(InsInstrsSC);
 423   ArrayRef<const MCSchedClassDesc *> MSCDelArr = makeArrayRef(DelInstrsSC);
 424
 425   // Compute new resource length.
 426   unsigned ResLenAfterCombine =
 427       BlockTrace.getResourceLength(MBBarr, MSCInsArr, MSCDelArr);
 428
 429   LLVM_DEBUG(dbgs() << "\t\tResource length before replacement: "
 430                     << ResLenBeforeCombine
 431                     << " and after: " << ResLenAfterCombine << "\n";);
 432   LLVM_DEBUG(
 433       ResLenAfterCombine <=
 434       ResLenBeforeCombine + TII->getExtendResourceLenLimit()
 435           ? dbgs() << "\t\t  As result it IMPROVES/PRESERVES Resource Length\n"
 436           : dbgs() << "\t\t  As result it DOES NOT improve/preserve Resource "
 437                       "Length\n");
 438
 439   return ResLenAfterCombine <=
 440          ResLenBeforeCombine + TII->getExtendResourceLenLimit();
 441 }
 442
 443 /// \returns true when new instruction sequence should be generated
 444 /// independent if it lengthens critical path or not
 445 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize,
 446                                    bool OptForSize) {
 447   if (OptForSize && (NewSize < OldSize))
 448     return true;
 449   if (!TSchedModel.hasInstrSchedModelOrItineraries())
 450     return true;
 451   return false;
 452 }
 453
 454 /// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
 455 /// depths if requested.
 456 ///
 457 /// \param MBB basic block to insert instructions in
 458 /// \param MI current machine instruction
 459 /// \param InsInstrs new instructions to insert in \p MBB
 460 /// \param DelInstrs instruction to delete from \p MBB
 461 /// \param MinInstr is a pointer to the machine trace information
 462 /// \param RegUnits set of live registers, needed to compute instruction depths
 463 /// \param TII is target instruction info, used to call target hook
 464 /// \param Pattern is used to call target hook finalizeInsInstrs
 465 /// \param IncrementalUpdate if true, compute instruction depths incrementally,
 466 ///                          otherwise invalidate the trace
 467 static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
 468                                      SmallVector<MachineInstr *, 16> InsInstrs,
 469                                      SmallVector<MachineInstr *, 16> DelInstrs,
 470                                      MachineTraceMetrics::Ensemble *MinInstr,
 471                                      SparseSet<LiveRegUnit> &RegUnits,
 472                                      const TargetInstrInfo *TII,
 473                                      MachineCombinerPattern Pattern,
 474                                      bool IncrementalUpdate) {
 475   // If we want to fix up some placeholder for some target, do it now.
 476   // We need this because in genAlternativeCodeSequence, we have not decided the
 477   // better pattern InsInstrs or DelInstrs, so we don't want generate some
 478   // sideeffect to the function. For example we need to delay the constant pool
 479   // entry creation here after InsInstrs is selected as better pattern.
 480   // Otherwise the constant pool entry created for InsInstrs will not be deleted
 481   // even if InsInstrs is not the better pattern.
 482   TII->finalizeInsInstrs(MI, Pattern, InsInstrs);
 483
 484   for (auto *InstrPtr : InsInstrs)
 485     MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
 486
 487   for (auto *InstrPtr : DelInstrs) {
 488     InstrPtr->eraseFromParent();
 489     // Erase all LiveRegs defined by the removed instruction
 490     for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
 491       if (I->MI == InstrPtr)
 492         I = RegUnits.erase(I);
 493       else
 494         I++;
 495     }
 496   }
 497
 498   if (IncrementalUpdate)
 499     for (auto *InstrPtr : InsInstrs)
 500       MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
 501   else
 502     MinInstr->invalidate(MBB);
 503
 504   NumInstCombined++;
 505 }
 506
 507 // Check that the difference between original and new latency is decreasing for
 508 // later patterns. This helps to discover sub-optimal pattern orderings.
 509 void MachineCombiner::verifyPatternOrder(
 510     MachineBasicBlock *MBB, MachineInstr &Root,
 511     SmallVector<MachineCombinerPattern, 16> &Patterns) {
 512   long PrevLatencyDiff = std::numeric_limits<long>::max();
 513   (void)PrevLatencyDiff; // Variable is used in assert only.
 514   for (auto P : Patterns) {
 515     SmallVector<MachineInstr *, 16> InsInstrs;
 516     SmallVector<MachineInstr *, 16> DelInstrs;
 517     DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
 518     TII->genAlternativeCodeSequence(Root, P, InsInstrs, DelInstrs,
 519                                     InstrIdxForVirtReg);
 520     // Found pattern, but did not generate alternative sequence.
 521     // This can happen e.g. when an immediate could not be materialized
 522     // in a single instruction.
 523     if (InsInstrs.empty() || !TSchedModel.hasInstrSchedModelOrItineraries())
 524       continue;
 525
 526     unsigned NewRootLatency, RootLatency;
 527     std::tie(NewRootLatency, RootLatency) = getLatenciesForInstrSequences(
 528         Root, InsInstrs, DelInstrs, MinInstr->getTrace(MBB));
 529     long CurrentLatencyDiff = ((long)RootLatency) - ((long)NewRootLatency);
 530     assert(CurrentLatencyDiff <= PrevLatencyDiff &&
 531            "Current pattern is better than previous pattern.");
 532     PrevLatencyDiff = CurrentLatencyDiff;
 533   }
 534 }
 535
 536 /// Substitute a slow code sequence with a faster one by
 537 /// evaluating instruction combining pattern.
 538 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
 539 /// combining based on machine trace metrics. Only combine a sequence of
 540 /// instructions  when this neither lengthens the critical path nor increases
 541 /// resource pressure. When optimizing for codesize always combine when the new
 542 /// sequence is shorter.
 543 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
 544   bool Changed = false;
 545   LLVM_DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
 546
 547   bool IncrementalUpdate = false;
 548   auto BlockIter = MBB->begin();
 549   decltype(BlockIter) LastUpdate;
 550   // Check if the block is in a loop.
 551   const MachineLoop *ML = MLI->getLoopFor(MBB);
 552   if (!MinInstr)
 553     MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
 554
 555   SparseSet<LiveRegUnit> RegUnits;
 556   RegUnits.setUniverse(TRI->getNumRegUnits());
 557
 558   bool OptForSize = OptSize || llvm::shouldOptimizeForSize(MBB, PSI, MBFI);
 559
 560   bool DoRegPressureReduce =
 561       TII->shouldReduceRegisterPressure(MBB, &RegClassInfo);
 562
 563   while (BlockIter != MBB->end()) {
 564     auto &MI = *BlockIter++;
 565     SmallVector<MachineCombinerPattern, 16> Patterns;
 566     // The motivating example is:
 567     //
 568     //     MUL  Other        MUL_op1 MUL_op2  Other
 569     //      \    /               \      |    /
 570     //      ADD/SUB      =>        MADD/MSUB
 571     //      (=Root)                (=NewRoot)
 572
 573     // The DAGCombine code always replaced MUL + ADD/SUB by MADD. While this is
 574     // usually beneficial for code size it unfortunately can hurt performance
 575     // when the ADD is on the critical path, but the MUL is not. With the
 576     // substitution the MUL becomes part of the critical path (in form of the
 577     // MADD) and can lengthen it on architectures where the MADD latency is
 578     // longer than the ADD latency.
 579     //
 580     // For each instruction we check if it can be the root of a combiner
 581     // pattern. Then for each pattern the new code sequence in form of MI is
 582     // generated and evaluated. When the efficiency criteria (don't lengthen
 583     // critical path, don't use more resources) is met the new sequence gets
 584     // hooked up into the basic block before the old sequence is removed.
 585     //
 586     // The algorithm does not try to evaluate all patterns and pick the best.
 587     // This is only an artificial restriction though. In practice there is
 588     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
 589     // based on an internal cost heuristic. If
 590     // machine-combiner-verify-pattern-order is enabled, all patterns are
 591     // checked to ensure later patterns do not provide better latency savings.
 592
 593     if (!TII->getMachineCombinerPatterns(MI, Patterns, DoRegPressureReduce))
 594       continue;
 595
 596     if (VerifyPatternOrder)
 597       verifyPatternOrder(MBB, MI, Patterns);
 598
 599     for (auto P : Patterns) {
 600       SmallVector<MachineInstr *, 16> InsInstrs;
 601       SmallVector<MachineInstr *, 16> DelInstrs;
 602       DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
 603       TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
 604                                       InstrIdxForVirtReg);
 605       unsigned NewInstCount = InsInstrs.size();
 606       unsigned OldInstCount = DelInstrs.size();
 607       // Found pattern, but did not generate alternative sequence.
 608       // This can happen e.g. when an immediate could not be materialized
 609       // in a single instruction.
 610       if (!NewInstCount)
 611         continue;
 612
 613       LLVM_DEBUG(if (dump_intrs) {
 614         dbgs() << "\tFor the Pattern (" << (int)P
 615                << ") these instructions could be removed\n";
 616         for (auto const *InstrPtr : DelInstrs)
 617           InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
 618                           /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
 619         dbgs() << "\tThese instructions could replace the removed ones\n";
 620         for (auto const *InstrPtr : InsInstrs)
 621           InstrPtr->print(dbgs(), /*IsStandalone*/false, /*SkipOpers*/false,
 622                           /*SkipDebugLoc*/false, /*AddNewLine*/true, TII);
 623       });
 624
 625       bool SubstituteAlways = false;
 626       if (ML && TII->isThroughputPattern(P))
 627         SubstituteAlways = true;
 628
 629       if (IncrementalUpdate && LastUpdate != BlockIter) {
 630         // Update depths since the last incremental update.
 631         MinInstr->updateDepths(LastUpdate, BlockIter, RegUnits);
 632         LastUpdate = BlockIter;
 633       }
 634
 635       if (DoRegPressureReduce &&
 636           getCombinerObjective(P) ==
 637               CombinerObjective::MustReduceRegisterPressure) {
 638         if (MBB->size() > inc_threshold) {
 639           // Use incremental depth updates for basic blocks above threshold
 640           IncrementalUpdate = true;
 641           LastUpdate = BlockIter;
 642         }
 643         if (reduceRegisterPressure(MI, MBB, InsInstrs, DelInstrs, P)) {
 644           // Replace DelInstrs with InsInstrs.
 645           insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
 646                                    RegUnits, TII, P, IncrementalUpdate);
 647           Changed |= true;
 648
 649           // Go back to previous instruction as it may have ILP reassociation
 650           // opportunity.
 651           BlockIter--;
 652           break;
 653         }
 654       }
 655
 656       // Substitute when we optimize for codesize and the new sequence has
 657       // fewer instructions OR
 658       // the new sequence neither lengthens the critical path nor increases
 659       // resource pressure.
 660       if (SubstituteAlways ||
 661           doSubstitute(NewInstCount, OldInstCount, OptForSize)) {
 662         insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
 663                                  RegUnits, TII, P, IncrementalUpdate);
 664         // Eagerly stop after the first pattern fires.
 665         Changed = true;
 666         break;
 667       } else {
 668         // For big basic blocks, we only compute the full trace the first time
 669         // we hit this. We do not invalidate the trace, but instead update the
 670         // instruction depths incrementally.
 671         // NOTE: Only the instruction depths up to MI are accurate. All other
 672         // trace information is not updated.
 673         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
 674         Traces->verifyAnalysis();
 675         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
 676                                     InstrIdxForVirtReg, P,
 677                                     !IncrementalUpdate) &&
 678             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
 679           if (MBB->size() > inc_threshold) {
 680             // Use incremental depth updates for basic blocks above treshold
 681             IncrementalUpdate = true;
 682             LastUpdate = BlockIter;
 683           }
 684
 685           insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
 686                                    RegUnits, TII, P, IncrementalUpdate);
 687
 688           // Eagerly stop after the first pattern fires.
 689           Changed = true;
 690           break;
 691         }
 692         // Cleanup instructions of the alternative code sequence. There is no
 693         // use for them.
 694         MachineFunction *MF = MBB->getParent();
 695         for (auto *InstrPtr : InsInstrs)
 696           MF->deleteMachineInstr(InstrPtr);
 697       }
 698       InstrIdxForVirtReg.clear();
 699     }
 700   }
 701
 702   if (Changed && IncrementalUpdate)
 703     Traces->invalidate(MBB);
 704   return Changed;
 705 }
 706
 707 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
 708   STI = &MF.getSubtarget();
 709   TII = STI->getInstrInfo();
 710   TRI = STI->getRegisterInfo();
 711   SchedModel = STI->getSchedModel();
 712   TSchedModel.init(STI);
 713   MRI = &MF.getRegInfo();
 714   MLI = &getAnalysis<MachineLoopInfo>();
 715   Traces = &getAnalysis<MachineTraceMetrics>();
 716   PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 717   MBFI = (PSI && PSI->hasProfileSummary()) ?
 718          &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :
 719          nullptr;
 720   MinInstr = nullptr;
 721   OptSize = MF.getFunction().hasOptSize();
 722   RegClassInfo.runOnMachineFunction(MF);
 723
 724   LLVM_DEBUG(dbgs() << getPassName() << ": " << MF.getName() << '\n');
 725   if (!TII->useMachineCombiner()) {
 726     LLVM_DEBUG(
 727         dbgs()
 728         << "  Skipping pass: Target does not support machine combiner\n");
 729     return false;
 730   }
 731
 732   bool Changed = false;
 733
 734   // Try to combine instructions.
 735   for (auto &MBB : MF)
 736     Changed |= combineInstructions(&MBB);
 737
 738   return Changed;
 739 }