Index: lib/CodeGen/MachineCombiner.cpp
===================================================================
--- lib/CodeGen/MachineCombiner.cpp
+++ lib/CodeGen/MachineCombiner.cpp
@@ -415,7 +415,7 @@
 
   bool IncrementalUpdate = false;
   auto BlockIter = MBB->begin();
-  auto LastUpdate = BlockIter;
+  decltype(BlockIter) LastUpdate;
   // Check if the block is in a loop.
   const MachineLoop *ML = MLI->getLoopFor(MBB);
   if (!MinInstr)
@@ -503,9 +503,11 @@
                                     InstrIdxForVirtReg, P,
                                     !IncrementalUpdate) &&
             preservesResourceLen(MBB, BlockTrace, InsInstrs, DelInstrs)) {
-          if (MBB->size() > inc_threshold)
+          if (MBB->size() > inc_threshold) {
             // Use incremental depth updates for basic blocks above treshold
             IncrementalUpdate = true;
+            LastUpdate = BlockIter;
+          }
 
           insertDeleteInstructions(MBB, MI, InsInstrs, DelInstrs, MinInstr,
                                    RegUnits, IncrementalUpdate);
Index: test/CodeGen/AArch64/machine-combiner.mir
===================================================================
--- /dev/null
+++ test/CodeGen/AArch64/machine-combiner.mir
@@ -0,0 +1,48 @@
+# RUN: llc -mtriple=aarch64-none-linux-gnu -mcpu=cortex-a57 -enable-unsafe-fp-math \
+# RUN:     -run-pass machine-combiner -machine-combiner-inc-threshold=0 \
+# RUN:     -verify-machineinstrs  -o - %s | FileCheck %s
+---
+# Test incremental depth updates succeed when triggered after the removal of
+# the first instruction in a basic block.
+
+# CHECK-LABEL: name: inc_update_iterator_test
+name:            inc_update_iterator_test
+registers:
+  - { id: 0, class: fpr64 }
+  - { id: 1, class: gpr32 }
+  - { id: 2, class: gpr32 }
+  - { id: 3, class: gpr32 }
+  - { id: 4, class: gpr32 }
+  - { id: 5, class: gpr32 }
+  - { id: 6, class: gpr32 }
+  - { id: 7, class: fpr64 }
+  - { id: 8, class: fpr64 }
+  - { id: 9, class: fpr64 }
+body:             |
+  bb.0:
+    successors: %bb.1, %bb.2
+
+    %3 = COPY %w2
+    %2 = COPY %w1
+    %1 = COPY %w0
+    %0 = COPY %d0
+    %4 = SUBSWrr %1, %2, implicit-def %nzcv
+    Bcc 13, %bb.2, implicit %nzcv
+    B %bb.1
+
+  bb.1:
+    ; CHECK: MADDWrrr %1, %2, %3
+    %5 = MADDWrrr %1, %2, %wzr
+    %6 = ADDWrr %3, killed %5
+    %7 = SCVTFUWDri killed %6
+    ; CHECK: FMADDDrrr %7, %7, %0
+    %8 = FMULDrr %7, %7
+    %9 = FADDDrr %0, killed %8
+    %d0 = COPY %9
+    RET_ReallyLR implicit %d0
+
+  bb.2:
+    %d0 = COPY %0
+    RET_ReallyLR implicit %d0
+
+...