diff --git a/llvm/lib/CodeGen/LiveRangeEdit.cpp b/llvm/lib/CodeGen/LiveRangeEdit.cpp
--- a/llvm/lib/CodeGen/LiveRangeEdit.cpp
+++ b/llvm/lib/CodeGen/LiveRangeEdit.cpp
@@ -305,6 +305,8 @@
       isOrigDef = SlotIndex::isSameInstr(OrigVNI->def, Idx);
   }
 
+  bool HasLiveVRegUses = false;
+
   // Check for live intervals that may shrink
   for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
          MOE = MI->operands_end(); MOI != MOE; ++MOI) {
@@ -328,6 +330,8 @@
     if ((MI->readsVirtualRegister(Reg) && (MI->isCopy() || MOI->isDef())) ||
         (MOI->readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, *MOI))))
       ToShrink.insert(&LI);
+    else if (MOI->readsReg())
+      HasLiveVRegUses = true;
 
     // Remove defined value.
     if (MOI->isDef()) {
@@ -362,7 +366,11 @@
     // the inst for remat of other siblings. The inst is saved in
     // LiveRangeEdit::DeadRemats and will be deleted after all the
     // allocations of the func are done.
-    if (isOrigDef && DeadRemats && TII.isTriviallyReMaterializable(*MI, AA)) {
+    // However, immediately delete instructions which have unshrunk virtual
+    // register uses. That may provoke RA to split an interval at the KILL
+    // and later result in an invalid live segment end.
+    if (isOrigDef && DeadRemats && !HasLiveVRegUses &&
+        TII.isTriviallyReMaterializable(*MI, AA)) {
       LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);
       VNInfo *VNI = NewLI.getNextValue(Idx, LIS.getVNInfoAllocator());
       NewLI.addSegment(LiveInterval::Segment(Idx, Idx.getDeadSlot(), VNI));
diff --git a/llvm/test/CodeGen/X86/delete-dead-instrs-with-live-uses.mir b/llvm/test/CodeGen/X86/delete-dead-instrs-with-live-uses.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/delete-dead-instrs-with-live-uses.mir
@@ -0,0 +1,59 @@
+# RUN: llc -mtriple=i386-apple-ios9.0.0-simulator --frame-pointer=all -verify-machineinstrs -start-before=greedy -o - %s | FileCheck %s
+
+# The test used to fail with "Live segment doesn't end at a valid instruction"
+# See PR51655.
+
+---
+# CHECK: jne
+# CHECK: andl    $-16, %edx
+# CHECK: xorl    %ebx, %ebx
+# CHECK: movl    %edx, -16(%ebp)
+# CHECK: xorl    %esi, %esi
+
+name:            test
+tracksRegLiveness: true
+fixedStack:
+  - { id: 0, type: default, offset: 4, size: 4, alignment: 4, stack-id: default,
+      isImmutable: true, isAliased: false, callee-saved-restored: true }
+  - { id: 1, type: default, offset: 0, size: 4, alignment: 16, stack-id: default,
+      isImmutable: true, isAliased: false, callee-saved-restored: true }
+body:             |
+  bb.0:
+    successors: %bb.3(0x40000000), %bb.1(0x40000000)
+
+    %0:gr32_nosp = MOV32rm %fixed-stack.1, 1, $noreg, 0, $noreg :: (load (s32) from %fixed-stack.1)
+    %1:gr32_nosp = MOV32rm %fixed-stack.0, 1, $noreg, 0, $noreg :: (load (s32) from %fixed-stack.0, align 16)
+    %2:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    JCC_1 %bb.3, 5, implicit undef $eflags
+    JMP_1 %bb.1
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    %2:gr32_abcd = AND32ri8 %2, -16, implicit-def dead $eflags
+    %3:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    %4:gr32 = LEA32r %0, 1, %1, -49, $noreg
+    %5:gr32_abcd = MOV32r0 implicit-def dead $eflags
+    %6:gr32 = IMPLICIT_DEF
+    JMP_1 %bb.2
+
+  bb.2:
+    successors: %bb.2(0x40000000), %bb.3(0x40000000)
+
+    %7:vr128 = MOVUPSrm %4, 1, %3, 0, $noreg :: (load (s128), align 1)
+    %5:gr32_abcd = nuw ADD32ri8 %5, 64, implicit-def dead $eflags
+    %6:gr32 = ADD32ri8 %6, -4, implicit-def $eflags
+    JCC_1 %bb.2, 5, implicit killed $eflags
+    JMP_1 %bb.3
+
+  bb.3:
+    successors: %bb.4(0x80000000)
+
+    %2:gr32_abcd = NEG32r %2, implicit-def dead $eflags
+    %8:gr32 = LEA32r %0, 1, %1, -5, $noreg
+    JMP_1 %bb.4
+
+  bb.4:
+    RET 0
+
+...