[MachineCombiner] Update instruction depths incrementally for large BBs.

[fhahn]

Summary

For large basic blocks with lots of combinable instructions, the
MachineTraceMetrics computations in MachineCombiner can dominate the compile
time, as computing the trace information is quadratic in the number of
instructions in a BB and it's relevant successors/predecessors.

In most cases, knowing the instruction depth should be enough to make
combination decisions. As we already iterate over all instructions in a basic
block, the instruction depth can be computed incrementally. This reduces the
cost of machine-combine drastically in cases where lots of instructions
are combined. The major drawback is that AFAIK, computing the critical path
length cannot be done incrementally. Therefore we only compute
instruction depths incrementally, for basic blocks with more
instructions than inc_threshold. The -machine-combiner-inc-threshold
option can be used to set the threshold and allows for easier
experimenting and checking if using incremental updates for all basic
blocks has any impact on the performance.

[efriedma]

For reference, I also ran into this problem at one point, and came up with a hack to just turn off trace-based optimizations for long basic blocks. This implementation looks nicer. :)

[fhahn]

Thanks for your feedback Eli. I've update the patch to only use incremental updates if the size of a BB is over a certain threshold. I've chosen 500 instructions for now, but a slightly higher one would probably be OK too.

I've also updated the patch to take the LiveRegUnits into account when doing incremental updates. Also, the code to compute the incremental info is only executed if we found viable patterns.

[fhahn]

ping

[Gerolf]

Hi Florian

This looks promising! Thanks for working on this nagging problem spot. More out of curiosity: Could you also share the data for your compile-time improvements?

Cheers
Gerolf

lib/CodeGen/MachineCombiner.cpp

280–284

What happened to the comment?

303

SlackIsAccurate is checked twice for OldCycleCount?! I think the old scheme is fine which just dumps the components of new and old root latencies. Perhaps only add whether or not SlackIsAccurate is set?

493–497

Typos (eg. Wwe -> We) and dups ('the first time'). What does 'relatively accurate' mean?

[fhahn]

Thanks for having a look!
Address review comments.

As for data for your compile-time improvements: I was looking into compile-time outliers for a proprietary benchmark suite, so unfortunately I cannot share the source. There was a module with a few large basic block (one with ~35000 instructions and a couple with > 3000 instructions), with lots of combinable instructions on AArch64 . Without this patch, time-passes on llc shows

Total Execution Time: 18.2227 seconds (18.2513 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
14.0113 ( 77.4%)   0.0338 ( 28.5%)  14.0451 ( 77.1%)  14.0672 ( 77.1%)  Machine InstCombiner
 2.0149 ( 11.1%)   0.0552 ( 46.5%)   2.0701 ( 11.4%)   2.0726 ( 11.4%)  Greedy Register Allocator
 0.9370 (  5.2%)   0.0184 ( 15.5%)   0.9554 (  5.2%)   0.9577 (  5.2%)  AArch64 Instruction Selection
 0.3403 (  1.9%)   0.0010 (  0.8%)   0.3413 (  1.9%)   0.3417 (  1.9%)  Machine Instruction Scheduler

With this patch

Total Execution Time: 4.9057 seconds (4.9158 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 2.0272 ( 42.1%)   0.0612 ( 64.8%)   2.0884 ( 42.6%)   2.0931 ( 42.6%)  Greedy Register Allocator
 0.9621 ( 20.0%)   0.0190 ( 20.1%)   0.9810 ( 20.0%)   0.9829 ( 20.0%)  AArch64 Instruction Selection
 0.6782 ( 14.1%)   0.0021 (  2.2%)   0.6803 ( 13.9%)   0.6812 ( 13.9%)  Machine InstCombiner

lib/CodeGen/MachineCombiner.cpp

280–284

I've added the comment again. Removing the comment was a left-over from an earlier iteration of the patch.

493–497

I am not sure how to put that. updateDepth() uses the live register info in RegUnits to track dependencies of physical registers. In the following case, the depths could be wrong (R1 being a physical register):

R1 <- I0 ....
R2 <- I1 R1
R1 <- I2 ...
.. <- I3 R2

If we replace I1 and I2 with ... <- I4 R1, when we are updating the depth of I4, RegUnits would contain something like (R1 defined by I2), and it would use that dependency for the depth calculation. But when the MachineCombiner is run, combined instructions should still use virtual registers. At least for the AArch64, it seems like physical registers are used only for argument passing at this stage.

[Gerolf]

Thank you for sharing your numbers. I was hoping you had that show-off case.
I just have a few minor comments about readability and asserts. I still need bit more time to convince myself that all the pieces fit together. I was wondering if you could add a test that dumps the depths w/ and w/o the incremental updates (compile w/ full comination + dumps depths, compile with a threashold of 1 + dump depths, diff the dump)?

Thanks
Gerolf

lib/CodeGen/MachineCombiner.cpp

375

Please add comments what the parameters mean. More parameters make it harder to read now.

386

The assumption is that LastUpdate and End are never Null. Would it make sense to document this with an assertion.

386

The loops under IncrementalUpdate in this function could be wrapped in a function (with start and end iterators as parameters).

386–401

Would it make sense for the RegUnit update be part of eraseFromParent...(),? E.g. have a bool parameter for that function indicating it?

[fhahn]

I really appreciate you taking time to review this change!

As a sanity check for the incremental update I did the following:

1. check-llvm-codegen passes with only using incremental depth computation (the full trace is computed before the main loop and IncremenalUpdate is initialized with true.

2. As you suggested, I compiled the MultiSource/Benchmarks programs from the LLVM test suite with 2 version of LLVM, one only using incremental depth computations and the other only using the existing mechanics. I printed the depths of all instructions of changed basic blocks and compared them. The depths are the same for both versions, with a few exceptions. The minor differences in heights are caused by nodes that depend on the depths of instructions in previous basic blocks (PHI nodes). In a few cases, the previous basic block has been invalidated, but is not in the set of basic blocks for which the depths are re-computed in getTrace(). If we do not invalidate the trace, all depths match. Maybe it would be worth to only invalidate the traces for all basic block we changed, at the end of MachineCombiner::runOnMachineFunction

lib/CodeGen/MachineCombiner.cpp

386

I think I am missing something about the assertion, but neither LatestUpdate nor End are pointers.

I've added an updateDepths function

386–401

I think updating RegUnits is only relevant for the incremental updates here and I am not sure if it is worth making Instruction::eraseFromParent... more compilcated.

[fhahn]

ping. @Gerolf did my last comments answer your questions adequately?

[Gerolf]

LGTM.

I added a few minor remarks that you might want to consider before commit. Again, thanks for working on this and your patience!

Cheers
Gerolf

lib/CodeGen/MachineCombiner.cpp

396

You could call updateDepths here as well. Also if you had code like if (IncrementalUpdate) MinInstr->updateDepths(...) else MinInstr->invalidate(MBB) you could spare two parameters (at the cost of adding such a line after each call). It feels more natural to me than packing the code inside the insertDelete...() procedure.

417

LastUpdate = BlockIter like in the code below?

[fhahn]

Thank you very much for having a look! I'll address your comments tomorrow and go ahead committing the patch. Also, this patch depends on D36696, which is a NFC that moves the code to update the instruction depths to a separate function (in MachineTraceMetrics.cpp). Pending further objections, I'll commit this patch as well tomorrow.

[fhahn]

lib/CodeGen/MachineCombiner.cpp

396

This is slightly more difficult, I think, as MachineBasicBlock::iterator iterates over instruction references while InsInstrs contains instruction pointers. I'll leave it as it is for now and will think a bit more if we can make this nicer.

I think it is slightly safer to update the state of the trace here, as this should always be done if we modify the basic block.

[fhahn]

Accepted in Phabricator to make arc happy.

include/llvm/CodeGen/MachineTraceMetrics.h

public:
 
     /// Get the trace that passes through MBB.
     /// The trace is computed on demand.
     Trace getTrace(const MachineBasicBlock *MBB);
 
     /// Updates the depth of an machine instruction, given RegUnits.
     void updateDepth(const MachineBasicBlock *, const MachineInstr&,
                      SparseSet<LiveRegUnit> &RegUnits);
+
+    /// Updates the depth of the instructions from Start to End.
+    void updateDepths(MachineBasicBlock::iterator Start,
+                      MachineBasicBlock::iterator End,
+                      SparseSet<LiveRegUnit> &RegUnits);
+
   };
 
   /// Strategies for selecting traces.
   enum Strategy {
     /// Select the trace through a block that has the fewest instructions.
     TS_MinInstrCount,
 
     TS_NumStrategies

lib/CodeGen/MachineCombiner.cpp

 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineTraceMetrics.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetSchedule.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "machine-combiner"
 
 STATISTIC(NumInstCombined, "Number of machineinst combined");
 
+static cl::opt<unsigned>
+inc_threshold("machine-combiner-inc-threshold", cl::Hidden,
+              cl::desc("Incremental depth computation will be used for basic "
+                       "blocks with more instructions."), cl::init(500));
+
 namespace {
+
 class MachineCombiner : public MachineFunctionPass {
   const TargetInstrInfo *TII;
   const TargetRegisterInfo *TRI;
   MCSchedModel SchedModel;
   MachineRegisterInfo *MRI;
   MachineLoopInfo *MLI; // Current MachineLoopInfo
   MachineTraceMetrics *Traces;
   MachineTraceMetrics::Ensemble *MinInstr;
private:
   unsigned getLatency(MachineInstr *Root, MachineInstr *NewRoot,
                       MachineTraceMetrics::Trace BlockTrace);
   bool
   improvesCriticalPathLen(MachineBasicBlock *MBB, MachineInstr *Root,
                           MachineTraceMetrics::Trace BlockTrace,
                           SmallVectorImpl<MachineInstr *> &InsInstrs,
                           SmallVectorImpl<MachineInstr *> &DelInstrs,
                           DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
-                          MachineCombinerPattern Pattern);
+                          MachineCombinerPattern Pattern, bool SlackIsAccurate);
   bool preservesResourceLen(MachineBasicBlock *MBB,
                             MachineTraceMetrics::Trace BlockTrace,
                             SmallVectorImpl<MachineInstr *> &InsInstrs,
                             SmallVectorImpl<MachineInstr *> &DelInstrs);
   void instr2instrSC(SmallVectorImpl<MachineInstr *> &Instrs,
                      SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC);
 };
 }

 /// path. The definition of "improve" may be restricted by specifying that the
 /// new path improves the data dependency chain (MustReduceDepth).
 bool MachineCombiner::improvesCriticalPathLen(
     MachineBasicBlock *MBB, MachineInstr *Root,
     MachineTraceMetrics::Trace BlockTrace,
     SmallVectorImpl<MachineInstr *> &InsInstrs,
     SmallVectorImpl<MachineInstr *> &DelInstrs,
     DenseMap<unsigned, unsigned> &InstrIdxForVirtReg,
-    MachineCombinerPattern Pattern) {
+    MachineCombinerPattern Pattern,
+    bool SlackIsAccurate) {
   assert(TSchedModel.hasInstrSchedModelOrItineraries() &&
          "Missing machine model\n");
   // NewRoot is the last instruction in the \p InsInstrs vector.
   unsigned NewRootIdx = InsInstrs.size() - 1;
   MachineInstr *NewRoot = InsInstrs[NewRootIdx];
 
   // Get depth and latency of NewRoot and Root.
   unsigned NewRootDepth = getDepth(InsInstrs, InstrIdxForVirtReg, BlockTrace);
   unsigned RootDepth = BlockTrace.getInstrCycles(*Root).Depth;
 
-  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << Root << "\n";
+  DEBUG(dbgs() << "DEPENDENCE DATA FOR " << *Root << "\n";
         dbgs() << " NewRootDepth: " << NewRootDepth << "\n";
         dbgs() << " RootDepth: " << RootDepth << "\n");
 
   // For a transform such as reassociation, the cost equation is
   // conservatively calculated so that we must improve the depth (data
   // dependency cycles) in the critical path to proceed with the transform.
   // Being conservative also protects against inaccuracies in the underlying
   // machine trace metrics and CPU models.
   if (getCombinerObjective(Pattern) == CombinerObjective::MustReduceDepth)
     return NewRootDepth < RootDepth;
 
   // A more flexible cost calculation for the critical path includes the slack
   // of the original code sequence. This may allow the transform to proceed
   // even if the instruction depths (data dependency cycles) become worse.
 
   unsigned NewRootLatency = getLatency(Root, NewRoot, BlockTrace);
   unsigned RootLatency = 0;
 
   for (auto I : DelInstrs)
     RootLatency += TSchedModel.computeInstrLatency(I);
 
   unsigned RootSlack = BlockTrace.getInstrSlack(*Root);
-
+  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
+  unsigned OldCycleCount = RootDepth + RootLatency +
+                           (SlackIsAccurate ? RootSlack : 0);
   DEBUG(dbgs() << " NewRootLatency: " << NewRootLatency << "\n";
         dbgs() << " RootLatency: " << RootLatency << "\n";
-        dbgs() << " RootSlack: " << RootSlack << "\n";
+        dbgs() << " RootSlack: " << RootSlack << " SlackIsAccurate="
+               << SlackIsAccurate << "\n";
         dbgs() << " NewRootDepth + NewRootLatency = "
-               << NewRootDepth + NewRootLatency << "\n";
+               << NewCycleCount << "\n";
         dbgs() << " RootDepth + RootLatency + RootSlack = "
-               << RootDepth + RootLatency + RootSlack << "\n";);
-
-  unsigned NewCycleCount = NewRootDepth + NewRootLatency;
-  unsigned OldCycleCount = RootDepth + RootLatency + RootSlack;
+               << OldCycleCount << "\n";
+        );
 
   return NewCycleCount <= OldCycleCount;
 }
 
 /// helper routine to convert instructions into SC
 void MachineCombiner::instr2instrSC(
     SmallVectorImpl<MachineInstr *> &Instrs,
     SmallVectorImpl<const MCSchedClassDesc *> &InstrsSC) {

 bool MachineCombiner::doSubstitute(unsigned NewSize, unsigned OldSize) {
   if (OptSize && (NewSize < OldSize))
     return true;
   if (!TSchedModel.hasInstrSchedModelOrItineraries())
     return true;
   return false;
 }
 
+/// Inserts InsInstrs and deletes DelInstrs. Incrementally updates instruction
+/// depths if requested.
+///
+/// \param InsInstrs new instructions to insert in \p MBB
+/// \param DelInstrs instruction to delete from \p MBB
+/// \param MinInstr is a pointer to the machine trace information
+/// \param RegUnits set of live registers, needed to compute instruction depths
+/// \param IncrementalUpdate if true, compute instruction depths incrementally,
+///                          otherwise invalidate the trace
 static void insertDeleteInstructions(MachineBasicBlock *MBB, MachineInstr &MI,
                                      SmallVector<MachineInstr *, 16> InsInstrs,
                                      SmallVector<MachineInstr *, 16> DelInstrs,
-                                     MachineTraceMetrics *Traces) {
+                                     MachineTraceMetrics::Ensemble *MinInstr,
+                                     SparseSet<LiveRegUnit> &RegUnits,
+                                     bool IncrementalUpdate) {
   for (auto *InstrPtr : InsInstrs)
-    MBB->insert((MachineBasicBlock::iterator)&MI, InstrPtr);
-  for (auto *InstrPtr : DelInstrs)
+    MBB->insert((MachineBasicBlock::iterator) &MI, InstrPtr);
+
+  for (auto *InstrPtr : DelInstrs) {
     InstrPtr->eraseFromParentAndMarkDBGValuesForRemoval();
-  ++NumInstCombined;
-  Traces->invalidate(MBB);
-  Traces->verifyAnalysis();
+    // Erase all LiveRegs defined by the removed instruction
+    for (auto I = RegUnits.begin(); I != RegUnits.end(); ) {
+      if (I->MI == InstrPtr)
+        I = RegUnits.erase(I);
+      else
+        I++;
+    }
+  }
+
+  if (IncrementalUpdate)
+    for (auto *InstrPtr : InsInstrs)
+      MinInstr->updateDepth(MBB, *InstrPtr, RegUnits);
+  else
+    MinInstr->invalidate(MBB);
+
+  NumInstCombined++;
 }
 
 /// Substitute a slow code sequence with a faster one by
 /// evaluating instruction combining pattern.
 /// The prototype of such a pattern is MUl + ADD -> MADD. Performs instruction
 /// combining based on machine trace metrics. Only combine a sequence of
 /// instructions  when this neither lengthens the critical path nor increases
 /// resource pressure. When optimizing for codesize always combine when the new
 /// sequence is shorter.
 bool MachineCombiner::combineInstructions(MachineBasicBlock *MBB) {
   bool Changed = false;
   DEBUG(dbgs() << "Combining MBB " << MBB->getName() << "\n");
 
+  bool IncrementalUpdate = false;
   auto BlockIter = MBB->begin();
+  auto LastUpdate = MBB->begin();
   // Check if the block is in a loop.
   const MachineLoop *ML = MLI->getLoopFor(MBB);
+  if (!MinInstr)
+    MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
+
+  SparseSet<LiveRegUnit> RegUnits;
+  RegUnits.setUniverse(TRI->getNumRegUnits());
 
   while (BlockIter != MBB->end()) {
     auto &MI = *BlockIter++;
 
     DEBUG(dbgs() << "INSTR "; MI.dump(); dbgs() << "\n";);
     SmallVector<MachineCombinerPattern, 16> Patterns;
     // The motivating example is:
     //
while (BlockIter != MBB->end()) {
     // generated and evaluated. When the efficiency criteria (don't lengthen
     // critical path, don't use more resources) is met the new sequence gets
     // hooked up into the basic block before the old sequence is removed.
     //
     // The algorithm does not try to evaluate all patterns and pick the best.
     // This is only an artificial restriction though. In practice there is
     // mostly one pattern, and getMachineCombinerPatterns() can order patterns
     // based on an internal cost heuristic.
-
     if (!TII->getMachineCombinerPatterns(MI, Patterns))
       continue;
 
     for (auto P : Patterns) {
       SmallVector<MachineInstr *, 16> InsInstrs;
       SmallVector<MachineInstr *, 16> DelInstrs;
       DenseMap<unsigned, unsigned> InstrIdxForVirtReg;
-      if (!MinInstr)
-        MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
-      Traces->verifyAnalysis();
       TII->genAlternativeCodeSequence(MI, P, InsInstrs, DelInstrs,
                                       InstrIdxForVirtReg);
       unsigned NewInstCount = InsInstrs.size();
       unsigned OldInstCount = DelInstrs.size();
       // Found pattern, but did not generate alternative sequence.
       // This can happen e.g. when an immediate could not be materialized
       // in a single instruction.
       if (!NewInstCount)
         continue;
 
       bool SubstituteAlways = false;
       if (ML && TII->isThroughputPattern(P))
         SubstituteAlways = true;
 
+      if (IncrementalUpdate) {
+        // Update depths since the last incremental update.
+        MinInstr->updateDepths(LastUpdate, std::next(BlockIter), RegUnits);
+        LastUpdate = BlockIter;
+      }
+
       // Substitute when we optimize for codesize and the new sequence has
       // fewer instructions OR
       // the new sequence neither lengthens the critical path nor increases
       // resource pressure.
       if (SubstituteAlways || doSubstitute(NewInstCount, OldInstCount)) {
-        insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, Traces);
+        insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
+                                 RegUnits, IncrementalUpdate);
         // Eagerly stop after the first pattern fires.
         Changed = true;
         break;
       } else {
-        // Calculating the trace metrics may be expensive,
-        // so only do this when necessary.
+        // For big basic blocks, we only compute the full trace the first time
+        // we hit this. We do not invalidate the trace, but instead update the
+        // instruction depths incrementally.
+        // NOTE: Only the instruction depths up to MI are accurate. All other
+        // trace information is not updated.
         MachineTraceMetrics::Trace BlockTrace = MinInstr->getTrace(MBB);
+        Traces->verifyAnalysis();
         if (improvesCriticalPathLen(MBB, &MI, BlockTrace, InsInstrs, DelInstrs,
-                                    InstrIdxForVirtReg, P) &&
+                                    InstrIdxForVirtReg, P,
+                                    !IncrementalUpdate) &&
             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
-          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, Traces);
+          if (MBB->size() > inc_threshold)
+            // Use incremental depth updates for basic blocks above treshold
+            IncrementalUpdate = true;
+
+          insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
+                                   RegUnits, IncrementalUpdate);
+
           // Eagerly stop after the first pattern fires.
           Changed = true;
           break;
         }
         // Cleanup instructions of the alternative code sequence. There is no
         // use for them.
         MachineFunction *MF = MBB->getParent();
         for (auto *InstrPtr : InsInstrs)
           MF->DeleteMachineInstr(InstrPtr);
       }
       InstrIdxForVirtReg.clear();
     }
   }
 
+  if (IncrementalUpdate)
+    Traces->invalidate(MBB);
   return Changed;
 }
 
 bool MachineCombiner::runOnMachineFunction(MachineFunction &MF) {
   const TargetSubtargetInfo &STI = MF.getSubtarget();
   TII = STI.getInstrInfo();
   TRI = STI.getRegisterInfo();
   SchedModel = STI.getSchedModel();

lib/CodeGen/MachineTraceMetrics.cpp

updateDepth(const MachineBasicBlock *MBB, const MachineInstr &UseMI,
 
 
   // Update critical path length.
   TBI.CriticalPath = std::max(TBI.CriticalPath, Cycle + MICycles.Height);
   DEBUG(dbgs() << TBI.CriticalPath << '\t' << Cycle << '\t' << UseMI);
 
 }
 
+void MachineTraceMetrics::Ensemble::
+updateDepths(MachineBasicBlock::iterator Start,
+             MachineBasicBlock::iterator End,
+             SparseSet<LiveRegUnit> &RegUnits) {
+    for (; Start != End; Start++)
+      updateDepth(Start->getParent(), *Start, RegUnits);
+}
+
 /// Compute instruction depths for all instructions above or in MBB in its
 /// trace. This assumes that the trace through MBB has already been computed.
 void MachineTraceMetrics::Ensemble::
 computeInstrDepths(const MachineBasicBlock *MBB) {
   // The top of the trace may already be computed, and HasValidInstrDepths
   // implies Head->HasValidInstrDepths, so we only need to start from the first
   // block in the trace that needs to be recomputed.
   SmallVector<const MachineBasicBlock*, 8> Stack;

test/CodeGen/AArch64/machine-combiner.ll

 ; RUN: llc -mtriple=aarch64-gnu-linux -mcpu=cortex-a57 -enable-unsafe-fp-math -disable-post-ra < %s | FileCheck %s
 
+; Incremental updates of the instruction depths should be enough for this test
+; case.
+; RUN: llc -mtriple=aarch64-gnu-linux -mcpu=cortex-a57 -enable-unsafe-fp-math \
+; RUN:     -disable-post-ra -machine-combiner-inc-threshold=0 < %s | FileCheck %s
+
 ; Verify that the first two adds are independent regardless of how the inputs are
 ; commuted. The destination registers are used as source registers for the third add.
 
 define float @reassociate_adds1(float %x0, float %x1, float %x2, float %x3) {
 ; CHECK-LABEL:   reassociate_adds1:
 ; CHECK:         fadd  s0, s0, s1
 ; CHECK-NEXT:    fadd  s1, s2, s3
 ; CHECK-NEXT:    fadd  s0, s0, s1

test/CodeGen/X86/machine-combiner.ll

 ; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 -mattr=sse -enable-unsafe-fp-math < %s | FileCheck %s --check-prefix=SSE
 ; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 -mattr=avx -enable-unsafe-fp-math < %s | FileCheck %s --check-prefix=AVX
 
+; Incremental updates of the instruction depths should be enough for this test
+; case.
+; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 -mattr=sse -enable-unsafe-fp-math -machine-combiner-inc-threshold=0 < %s | FileCheck %s --check-prefix=SSE
+; RUN: llc -mtriple=x86_64-unknown-unknown -mcpu=x86-64 -mattr=avx -enable-unsafe-fp-math -machine-combiner-inc-threshold=0 < %s | FileCheck %s --check-prefix=AVX
+
 ; Verify that the first two adds are independent regardless of how the inputs are
 ; commuted. The destination registers are used as source registers for the third add.
 
 define float @reassociate_adds1(float %x0, float %x1, float %x2, float %x3) {
 ; SSE-LABEL: reassociate_adds1:
 ; SSE:       # BB#0:
 ; SSE-NEXT:    addss %xmm1, %xmm0
 ; SSE-NEXT:    addss %xmm3, %xmm2

test/CodeGen/X86/mul-constant-result.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown | FileCheck %s --check-prefix=X86
-; RUN: llc < %s -mtriple=x86_64-unknown -mcpu=haswell| FileCheck %s --check-prefix=X64-HSW
+
+; Incremental updates of the instruction depths should be enough for this test
+; case.
+; RUN: llc < %s -mtriple=x86_64-unknown -mcpu=haswell -machine-combiner-inc-threshold=0| FileCheck %s --check-prefix=X64-HSW
 
 ; Function Attrs: norecurse nounwind readnone uwtable
 define i32 @mult(i32, i32) local_unnamed_addr #0 {
 ; X86-LABEL: mult:
 ; X86:       # BB#0:
 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:  .Lcfi0:
 ; X86-NEXT:    .cfi_def_cfa_offset 8