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