diff --git a/llvm/include/llvm/CodeGen/MachineSSAUpdater.h b/llvm/include/llvm/CodeGen/MachineSSAUpdater.h
--- a/llvm/include/llvm/CodeGen/MachineSSAUpdater.h
+++ b/llvm/include/llvm/CodeGen/MachineSSAUpdater.h
@@ -95,6 +95,10 @@
   /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
   /// merge the appropriate values, and this value isn't live out of the block.
   Register GetValueInMiddleOfBlock(MachineBasicBlock *BB);
+  /// As the above, but it will never create new values or instructions - only
+  /// use an existing inserted value; if no such value exists, returns $noreg.
+  /// Used for debug values, which are not allowed to effect CodeGen.
+  Register GetExistingValueInMiddleOfBlock(MachineBasicBlock *BB);
 
   /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
   /// which use their value in the corresponding predecessor.  Note that this
@@ -105,6 +109,9 @@
 
 private:
   Register GetValueAtEndOfBlockInternal(MachineBasicBlock *BB);
+  /// As above, but will not insert any new defs. Used for debug values, which
+  /// cannot modify Codegen.
+  Register GetExistingValueAtEndOfBlockInternal(MachineBasicBlock *BB);
 };
 
 } // end namespace llvm
diff --git a/llvm/lib/CodeGen/MachineSSAUpdater.cpp b/llvm/lib/CodeGen/MachineSSAUpdater.cpp
--- a/llvm/lib/CodeGen/MachineSSAUpdater.cpp
+++ b/llvm/lib/CodeGen/MachineSSAUpdater.cpp
@@ -208,6 +208,38 @@
   return InsertedPHI.getReg(0);
 }
 
+Register
+MachineSSAUpdater::GetExistingValueInMiddleOfBlock(MachineBasicBlock *BB) {
+  // If there is no definition of the renamed variable in this block, or there
+  // are no predecessors, we have no value to return so return undef.
+  if (!HasValueForBlock(BB) || BB->pred_empty())
+    return Register();
+
+  // Otherwise, get any existing live-in values for each predecessor.
+  SmallVector<std::pair<MachineBasicBlock *, Register>, 8> PredValues;
+  Register SingularValue;
+
+  bool isFirstPred = true;
+  for (MachineBasicBlock *PredBB : BB->predecessors()) {
+    Register PredVal = GetExistingValueAtEndOfBlockInternal(PredBB);
+    PredValues.push_back(std::make_pair(PredBB, PredVal));
+
+    // Compute SingularValue.
+    if (isFirstPred) {
+      SingularValue = PredVal;
+      isFirstPred = false;
+    } else if (PredVal != SingularValue)
+      SingularValue = Register();
+  }
+
+  // Otherwise, if all the merged values are the same, just use it.
+  if (SingularValue)
+    return SingularValue;
+
+  // If there is an identical PHI already in BB, reuse it.
+  return LookForIdenticalPHI(BB, PredValues);
+}
+
 static
 MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
                                          MachineOperand *U) {
@@ -358,3 +390,7 @@
   SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
   return Impl.GetValue(BB);
 }
+Register
+MachineSSAUpdater::GetExistingValueAtEndOfBlockInternal(MachineBasicBlock *BB) {
+  return getAvailableVals(AV).lookup(BB);
+}
diff --git a/llvm/lib/CodeGen/TailDuplicator.cpp b/llvm/lib/CodeGen/TailDuplicator.cpp
--- a/llvm/lib/CodeGen/TailDuplicator.cpp
+++ b/llvm/lib/CodeGen/TailDuplicator.cpp
@@ -216,27 +216,30 @@
 
       // Rewrite uses that are outside of the original def's block.
       MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
-      // Only remove instructions after loop, as DBG_VALUE_LISTs with multiple
-      // uses of VReg may invalidate the use iterator when erased.
-      SmallPtrSet<MachineInstr *, 4> InstrsToRemove;
       while (UI != MRI->use_end()) {
         MachineOperand &UseMO = *UI;
         MachineInstr *UseMI = UseMO.getParent();
         ++UI;
-        if (UseMI->isDebugValue()) {
-          // SSAUpdate can replace the use with an undef. That creates
-          // a debug instruction that is a kill.
-          // FIXME: Should it SSAUpdate job to delete debug instructions
-          // instead of replacing the use with undef?
-          InstrsToRemove.insert(UseMI);
+        // Rewrite debug uses last so that they can take advantage of any
+        // register mappings introduced by other users in its BB, since we
+        // cannot create new register definitions specifically for the debug
+        // instruction (as debug instructions cannot affect CodeGen).
+        if (UseMI->isDebugValue())
           continue;
-        }
         if (UseMI->getParent() == DefBB && !UseMI->isPHI())
           continue;
         SSAUpdate.RewriteUse(UseMO);
       }
-      for (auto *MI : InstrsToRemove)
-        MI->eraseFromParent();
+      UI = MRI->use_begin(VReg);
+      while (UI != MRI->use_end()) {
+        MachineOperand &UseMO = *UI;
+        MachineInstr *UseMI = UseMO.getParent();
+        ++UI;
+        if (!UseMI->isDebugValue())
+          continue;
+        UseMO.setReg(
+            SSAUpdate.GetExistingValueInMiddleOfBlock(UseMI->getParent()));
+      }
     }
 
     SSAUpdateVRs.clear();
diff --git a/llvm/test/CodeGen/X86/tail-dup-debugvalue.mir b/llvm/test/CodeGen/X86/tail-dup-debugvalue.mir
--- a/llvm/test/CodeGen/X86/tail-dup-debugvalue.mir
+++ b/llvm/test/CodeGen/X86/tail-dup-debugvalue.mir
@@ -4,7 +4,15 @@
 # use those values; those DBG_VALUEs should be deleted. This behaviour is tested
 # for DBG_VALUE users, and DBG_VALUE_LISTs that use the value multiple times.
 
-# CHECK-NOT: DBG_VALUE
+# CHECK: ![[VAR_J:[0-9]+]] = !DILocalVariable(name: "j"
+# CHECK: ![[VAR_K:[0-9]+]] = !DILocalVariable(name: "k"
+# CHECK-LABEL: bb.1.L:
+# CHECK: %[[REGISTER:[0-9]+]]:gr32 = PHI
+# CHECK-LABEL: bb.2.if.end4:
+# CHECK: DBG_VALUE_LIST ![[VAR_J]],
+# CHECK-SAME: %[[REGISTER]], 1, %[[REGISTER]]
+# CHECK: DBG_VALUE %[[REGISTER]], $noreg, ![[VAR_K]]
+
 --- |
   target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"