diff --git a/llvm/lib/CodeGen/RegAllocFast.cpp b/llvm/lib/CodeGen/RegAllocFast.cpp
--- a/llvm/lib/CodeGen/RegAllocFast.cpp
+++ b/llvm/lib/CodeGen/RegAllocFast.cpp
@@ -436,10 +436,17 @@
       SpilledOperandsMap;
   for (MachineOperand *MO : LRIDbgOperands)
     SpilledOperandsMap[MO->getParent()].push_back(MO);
-  for (auto MISpilledOperands : SpilledOperandsMap) {
-    MachineInstr &DBG = *MISpilledOperands.first;
-    MachineInstr *NewDV = buildDbgValueForSpill(
-        *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
+  // We can't iterate over SpilledOperandsMap directly as it can result in
+  // non-deterministic ordering. Instead we iterate over LRIDbgOperands again
+  // but keep track of already processed instructions.
+  SmallDenseSet<MachineInstr *> ProcessedSet;
+  for (MachineOperand *MO : LRIDbgOperands) {
+    auto DBG = MO->getParent();
+    if (ProcessedSet.contains(DBG))
+      continue;
+    ProcessedSet.insert(DBG);
+    MachineInstr *NewDV =
+        buildDbgValueForSpill(*MBB, Before, *DBG, FI, SpilledOperandsMap[DBG]);
     assert(NewDV->getParent() == MBB && "dangling parent pointer");
     (void)NewDV;
     LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);
@@ -457,10 +464,10 @@
     // Rewrite unassigned dbg_values to use the stack slot.
     // TODO We can potentially do this for list debug values as well if we know
     // how the dbg_values are getting unassigned.
-    if (DBG.isNonListDebugValue()) {
-      MachineOperand &MO = DBG.getDebugOperand(0);
+    if (DBG->isNonListDebugValue()) {
+      MachineOperand &MO = DBG->getDebugOperand(0);
       if (MO.isReg() && MO.getReg() == 0) {
-        updateDbgValueForSpill(DBG, FI, 0);
+        updateDbgValueForSpill(*DBG, FI, 0);
       }
     }
   }