Index: llvm/lib/CodeGen/RegisterCoalescer.cpp
===================================================================
--- llvm/lib/CodeGen/RegisterCoalescer.cpp
+++ llvm/lib/CodeGen/RegisterCoalescer.cpp
@@ -119,6 +119,8 @@
 
 namespace {
 
+  class JoinVals;
+
   class RegisterCoalescer : public MachineFunctionPass,
                             private LiveRangeEdit::Delegate {
     MachineFunction* MF = nullptr;
@@ -130,6 +132,18 @@
     AliasAnalysis *AA = nullptr;
     RegisterClassInfo RegClassInfo;
 
+    /// Debug variable location tracking -- for each VReg, maintain an
+    /// ordered-by-slot-index set of DBG_VALUEs, to help quick
+    /// identification of whether coalescing may change location validity.
+    using DbgValueLoc = std::pair<SlotIndex, MachineInstr*>;
+    std::map<unsigned, std::set<DbgValueLoc>> DbgVRegToValues;
+
+    /// VRegs may be repeatedly coalesced, and have many DBG_VALUEs attached.
+    /// To avoid repeatedly merging sets of DbgValueLocs, instead record
+    /// which vregs have been coalesced, and where to. This map is from
+    /// vreg => {set of vregs merged in}.
+    DenseMap<unsigned, SmallVector<unsigned, 4>> DbgMergedVRegNums;
+
     /// A LaneMask to remember on which subregister live ranges we need to call
     /// shrinkToUses() later.
     LaneBitmask ShrinkMask;
@@ -265,14 +279,6 @@
     /// Return true if a copy involving a physreg should be joined.
     bool canJoinPhys(const CoalescerPair &CP);
 
-    /// When merging SrcReg and DstReg together, and the operand of the
-    /// specified DBG_VALUE refers to one of them, would the def that a
-    /// DBG_VALUE refers to change? This can happen when the DBG_VALUEs
-    /// operand is dead and it's merged into a different live value,
-    /// meaning the DBG_VALUE operands must be updated.
-    bool mergingChangesDbgValue(MachineInstr *DbgV, unsigned SrcReg,
-                                unsigned DstReg) const;
-
     /// Replace all defs and uses of SrcReg to DstReg and update the subregister
     /// number if it is not zero. If DstReg is a physical register and the
     /// existing subregister number of the def / use being updated is not zero,
@@ -333,6 +339,19 @@
       MI->eraseFromParent();
     }
 
+    /// Walk over function and initialize the DbgVRegToValues map.
+    void buildDebugMap(MachineFunction &MF);
+
+    /// Test whether, after merging, any DBG_VALUEs would refer to a
+    /// different value number than before merging, and whether this can
+    /// be resolved. If not, mark the DBG_VALUE as being undef.
+    void checkMergingChangesDbgValues(CoalescerPair &CP, LiveRange &LHS,
+                                      JoinVals &LHSVals, LiveRange &RHS,
+                                      JoinVals &RHSVals);
+
+    void checkMergingChangesDbgValuesImpl(unsigned Reg, LiveRange &OtherRange,
+                                          LiveRange &RegRange, JoinVals &Vals2);
+
   public:
     static char ID; ///< Class identification, replacement for typeinfo
 
@@ -1656,58 +1675,6 @@
   }
 }
 
-bool RegisterCoalescer::mergingChangesDbgValue(MachineInstr *DbgV,
-                                               unsigned SrcReg,
-                                               unsigned DstReg) const {
-  assert(DbgV->isDebugValue());
-  assert(DbgV->getParent() && "DbgValue with no parent");
-  assert(DbgV->getOperand(0).isReg());
-  unsigned DbgReg = DbgV->getOperand(0).getReg();
-
-  SlotIndex MIIdx = LIS->getSlotIndexes()->getIndexAfter(*DbgV);
-  const LiveInterval &SrcLI = LIS->getInterval(SrcReg);
-
-  // Is the source register live across the DBG_VALUE?
-  bool SrcLive = false;
-  auto LII = SrcLI.find(MIIdx);
-  if (LII != SrcLI.end() && LII->contains(MIIdx))
-    SrcLive = true;
-
-  bool DstLive = false;
-  // Destination register can be physical or virtual.
-  if (TargetRegisterInfo::isVirtualRegister(DstReg)) {
-    // Is DstReg live across the DBG_VALUE?
-    const LiveInterval &DstLI = LIS->getInterval(DstReg);
-    LII = DstLI.find(MIIdx);
-    DstLive = (LII != DstLI.end() && LII->contains(MIIdx));
-  } else if (MRI->isConstantPhysReg(DstReg)) {
-    // Constant physical registers are always live.
-    DstLive = true;
-  } else {
-    // For physical registers, see if any register unit containing DstReg
-    // is live across the DBG_VALUE.
-    for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) {
-      const LiveRange &DstLI = LIS->getRegUnit(*UI);
-      auto DstLII = DstLI.find(MIIdx);
-      if (DstLII != DstLI.end() && DstLII->contains(MIIdx)) {
-        DstLive = true;
-        break;
-      }
-    }
-  }
-
-  // We now know whether src and dst are live. Best case: we have a DBG_VALUE
-  // of a live register, coalesing won't change its value.
-  if ((DstLive && DbgReg == DstReg) || (SrcLive && DbgReg == SrcReg))
-    return false;
-  // If neither register are live, no damage done.
-  if (!DstLive && !SrcLive)
-    return false;
-  // Otherwise, we will end up resurrecting the DBG_VALUE with a different
-  // register, which is unsafe.
-  return true;
-}
-
 void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, unsigned DstReg,
                                           unsigned SubIdx) {
   bool DstIsPhys = Register::isPhysicalRegister(DstReg);
@@ -1920,20 +1887,6 @@
   ShrinkMask = LaneBitmask::getNone();
   ShrinkMainRange = false;
 
-  // Although we can update the DBG_VALUEs to the merged register, as debug uses
-  // do not contribute to liveness it might not be a sound update. Collect
-  // DBG_VALUEs that would change value were this interval merging to succeed.
-  SmallVector<MachineInstr *, 4> DbgValuesToChange;
-  auto CheckForDbgUser = [this, &CP, &DbgValuesToChange](MachineInstr &MI) {
-    if (MI.isDebugValue() && MI.getOperand(0).isReg() &&
-        mergingChangesDbgValue(&MI, CP.getSrcReg(), CP.getDstReg()))
-      DbgValuesToChange.push_back(&MI);
-  };
-  for (auto &RegIt : MRI->reg_instructions(CP.getSrcReg()))
-    CheckForDbgUser(RegIt);
-  for (auto &RegIt : MRI->reg_instructions(CP.getDstReg()))
-    CheckForDbgUser(RegIt);
-
   // Okay, attempt to join these two intervals.  On failure, this returns false.
   // Otherwise, if one of the intervals being joined is a physreg, this method
   // always canonicalizes DstInt to be it.  The output "SrcInt" will not have
@@ -2002,16 +1955,6 @@
     updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx());
   updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx());
 
-  // The updates to these DBG_VALUEs are not sound -- mark them undef.
-  // FIXME: further analysis might recover them, this is the minimal sound
-  // solution.
-  for (MachineInstr *MI : DbgValuesToChange) {
-    assert(MI->getOperand(0).isReg());
-    LLVM_DEBUG(dbgs() << "Update of " << MI->getOperand(0) << " would be "
-                      << "unsound, setting undef\n");
-    MI->getOperand(0).setReg(0);
-  }
-
   // Shrink subregister ranges if necessary.
   if (ShrinkMask.any()) {
     LiveInterval &LI = LIS->getInterval(CP.getDstReg());
@@ -2246,6 +2189,7 @@
 class JoinVals {
   /// Live range we work on.
   LiveRange &LR;
+  friend class RegisterCoalescer;
 
   /// (Main) register we work on.
   const unsigned Reg;
@@ -3467,6 +3411,9 @@
   while (!ShrinkRegs.empty())
     shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val()));
 
+  // Scan and mark undef any DBG_VALUEs that would refer to a different value.
+  checkMergingChangesDbgValues(CP, LHS, LHSVals, RHS, RHSVals);
+
   // Join RHS into LHS.
   LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo);
 
@@ -3498,6 +3445,142 @@
   return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP);
 }
 
+void RegisterCoalescer::buildDebugMap(MachineFunction &MF)
+{
+  const SlotIndexes &Slots = *LIS->getSlotIndexes();
+  SmallVector<MachineInstr *, 8> ToInsert;
+
+  // After collecting a block of DBG_VALUEs into ToInsert, enter them into the
+  // vreg => DbgValueLoc map.
+  auto CloseNewDVRange = [this, &ToInsert](SlotIndex Slot) {
+    for (auto *X : ToInsert)
+      DbgVRegToValues[X->getOperand(0).getReg()].insert({Slot, X});
+
+    ToInsert.clear();
+  };
+
+  // Iterate over all instructions, collecting them into the ToInsert vector.
+  // Once a non-debug instruction is found, record the slot index of the
+  // collected DBG_VALUEs.
+  for (auto &MBB : MF) {
+    SlotIndex CurrentSlot = Slots.getMBBStartIdx(&MBB);
+    bool DbgValuesSeen = false;
+
+    for (auto &MI : MBB) {
+      if (MI.isDebugValue() && MI.getOperand(0).isReg() &&
+          MI.getOperand(0).getReg().isVirtual()) {
+        ToInsert.push_back(&MI);
+        DbgValuesSeen = true;
+      } else if (!MI.isDebugInstr() && DbgValuesSeen) {
+        CurrentSlot = Slots.getInstructionIndex(MI);
+        CloseNewDVRange(CurrentSlot);
+        DbgValuesSeen = false;
+      }
+    }
+
+    // Close range of DBG_VALUEs at the end of blocks.
+    if (DbgValuesSeen)
+      CloseNewDVRange(Slots.getMBBEndIdx(&MBB));
+  }
+}
+
+void RegisterCoalescer::checkMergingChangesDbgValues(CoalescerPair &CP,
+                                                     LiveRange &LHS,
+                                                     JoinVals &LHSVals,
+                                                     LiveRange &RHS,
+                                                     JoinVals &RHSVals) {
+  auto ScanForDstReg = [&](unsigned Reg) {
+    checkMergingChangesDbgValuesImpl(Reg, RHS, LHS, LHSVals);
+  };
+
+  auto ScanForSrcReg = [&](unsigned Reg) {
+    checkMergingChangesDbgValuesImpl(Reg, LHS, RHS, RHSVals);
+  };
+
+  // Scan for potentially unsound DBG_VALUEs: examine first the register number
+  // Reg, and then any other vregs that may have been merged into  it.
+  auto PerformScan = [this](unsigned Reg, std::function<void(unsigned)> Func) {
+    Func(Reg);
+    if (DbgMergedVRegNums.count(Reg))
+      for (unsigned X : DbgMergedVRegNums[Reg])
+        Func(X);
+  };
+
+  // Scan for unsound updates of both the source and destination register.
+  PerformScan(CP.getSrcReg(), ScanForSrcReg);
+  PerformScan(CP.getDstReg(), ScanForDstReg);
+}
+
+void RegisterCoalescer::checkMergingChangesDbgValuesImpl(unsigned Reg,
+                                                         LiveRange &OtherLR,
+                                                         LiveRange &RegLR,
+                                                         JoinVals &RegVals) {
+  // Are there any DBG_VALUEs to examine?
+  auto VRegMapIt = DbgVRegToValues.find(Reg);
+  if (VRegMapIt == DbgVRegToValues.end())
+    return;
+
+  auto &DbgValueSet = VRegMapIt->second;
+  auto DbgValueSetIt = DbgValueSet.begin();
+  auto SegmentIt = OtherLR.begin();
+
+  bool LastUndefResult = false;
+  SlotIndex LastUndefIdx;
+
+  // If the "Other" register is live at a slot Idx, test whether Reg can
+  // safely be merged with it, or should be marked undef.
+  auto ShouldUndef = [&RegVals, &RegLR, &LastUndefResult,
+                      &LastUndefIdx](SlotIndex Idx) -> bool {
+    // Our worst-case performance typically happens with asan, causing very
+    // many DBG_VALUEs of the same location. Cache a copy of the most recent
+    // result for this edge-case.
+    if (LastUndefIdx == Idx)
+      return LastUndefResult;
+
+    // If the other range was live, and Reg's was not, the register coalescer
+    // will not have tried to resolve any conflicts. We don't know whether
+    // the DBG_VALUE will refer to the same value number, so it must be made
+    // undef.
+    auto OtherIt = RegLR.find(Idx);
+    if (OtherIt == RegLR.end())
+      return true;
+
+    // Both the registers were live: examine the conflict resolution record for
+    // the value number Reg refers to. CR_Keep meant that this value number
+    // "won" and the merged register definitely refers to that value. CR_Erase
+    // means the value number was a redundant copy of the other value, which
+    // was coalesced and Reg deleted. It's safe to refer to the other register
+    // (which will be the source of the copy).
+    auto &TheVal = RegVals.Vals[OtherIt->valno->id];
+    LastUndefResult = TheVal.Resolution != JoinVals::CR_Keep &&
+                      TheVal.Resolution != JoinVals::CR_Erase;
+    LastUndefIdx = Idx;
+    return LastUndefResult;
+  };
+
+  // Iterate over both the live-range of the "Other" register, and the set of
+  // DBG_VALUEs for Reg at the same time. Advance whichever one has the lowest
+  // slot index. This relies on the DbgValueSet being a std::set, and thus
+  // its iteration order.
+  while (DbgValueSetIt != DbgValueSet.end() && SegmentIt != OtherLR.end()) {
+    if (DbgValueSetIt->first < SegmentIt->end) {
+      // "Other" is live and there is a DBG_VALUE of Reg: test if we should
+      // set it undef.
+      if (ShouldUndef(DbgValueSetIt->first)) {
+        // Mark undef, erase record of this DBG_VALUE to avoid revisiting.
+        DbgValueSetIt->second->getOperand(0).setReg(0);
+        auto ToErase = DbgValueSetIt;
+        ++DbgValueSetIt;
+        DbgValueSet.erase(ToErase, DbgValueSetIt);
+        continue;
+      }
+      ++DbgValueSetIt;
+    } else {
+      ++SegmentIt;
+    }
+  }
+}
+
 namespace {
 
 /// Information concerning MBB coalescing priority.
@@ -3780,6 +3863,10 @@
   if (VerifyCoalescing)
     MF->verify(this, "Before register coalescing");
 
+  DbgVRegToValues.clear();
+  DbgMergedVRegNums.clear();
+  buildDebugMap(fn);
+
   RegClassInfo.runOnMachineFunction(fn);
 
   // Join (coalesce) intervals if requested.
Index: llvm/test/DebugInfo/MIR/X86/regcoalescing-clears-dead-dbgvals.mir
===================================================================
--- llvm/test/DebugInfo/MIR/X86/regcoalescing-clears-dead-dbgvals.mir
+++ llvm/test/DebugInfo/MIR/X86/regcoalescing-clears-dead-dbgvals.mir
@@ -137,6 +137,8 @@
     ;
     ; %0 should be merged into %7, but as %0 is live at this location the
     ; DBG_VALUE should be preserved and point at the operand of ADD32rr.
+    ; RegisterCoalescer resolves %0 as CR_Erase: %0 is a redundant copy and
+    ; can be erased.
     ;
     ; CHECK: %[[REG11:[0-9]+]]:gr32 = MOV32rm
     ; CHECK-NEXT: %[[REG12:[0-9]+]]:gr32 = XOR32rr %[[REG11]]
@@ -145,18 +147,16 @@
 
     %0:gr32 = COPY killed %7
     %8:gr32 = MOV32rm %2, 1, $noreg, 0, $noreg :: (load 4 from %ir.pin, align 1)
-    %5:gr32 = COPY killed %8
-    %5:gr32 = XOR32rr %5, %4, implicit-def dead $eflags
+    %8:gr32 = XOR32rr %8, %4, implicit-def dead $eflags
     DBG_VALUE %0, $noreg, !3, !DIExpression(), debug-location !5
-    %1:gr32 = COPY killed %0
-    %1:gr32 = ADD32rr %1, killed %5, implicit-def dead $eflags
-    CMP32ri %1, 1000001, implicit-def $eflags
-    %7:gr32 = COPY %1
+    %0:gr32 = ADD32rr %0, killed %8, implicit-def dead $eflags
+    CMP32ri %0, 1000001, implicit-def $eflags
+    %7:gr32 = COPY %0
     JCC_1 %bb.1, 2, implicit killed $eflags
     JMP_1 %bb.2
 
   bb.2.leave:
-    $eax = COPY killed %1
+    $eax = COPY killed %7
     RET 0, killed $eax
 
 ...