contrib/llvm/lib/CodeGen/MachineCombiner.cpp

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