Index: llvm/include/llvm/CodeGen/MachineFunction.h
===================================================================
--- llvm/include/llvm/CodeGen/MachineFunction.h
+++ llvm/include/llvm/CodeGen/MachineFunction.h
@@ -451,24 +451,38 @@
   /// Pair of instruction number and operand number.
   using DebugInstrOperandPair = std::pair<unsigned, unsigned>;
 
-  /// Replacement definition for a debug instruction reference. Made up of an
-  /// instruction / operand pair, and a qualifying subregister indicating what
-  /// bits in the operand make up the substitution. For example, a debug user
+  /// Replacement definition for a debug instruction reference. Made up of a
+  /// source instruction / operand pair, destination pair, and a qualifying
+  /// subregister indicating what bits in the operand make up the substitution.
+  // For example, a debug user
   /// of %1:
-  ///    %0:gr32 = someinst, debug-instr-number 2
-  ///    %1:gr16 = %0.some_16_bit_subreg
-  /// Would receive the substitution {{2, 0}, $subreg}, where $subreg is the
-  /// subregister number for some_16_bit_subreg.
-  struct DebugSubstitution {
+  ///    %0:gr32 = someinst, debug-instr-number 1
+  ///    %1:gr16 = %0.some_16_bit_subreg, debug-instr-number 2
+  /// Would receive the substitution {{2, 0}, {1, 0}, $subreg}, where $subreg is
+  /// the subregister number for some_16_bit_subreg.
+  class DebugSubstitution {
+  public:
+    DebugInstrOperandPair Src;  ///< Source instruction / operand pair.
     DebugInstrOperandPair Dest; ///< Replacement instruction / operand pair.
     unsigned Subreg;            ///< Qualifier for which part of Dest is read.
+
+    DebugSubstitution(const DebugInstrOperandPair &Src,
+                      const DebugInstrOperandPair &Dest, unsigned Subreg)
+        : Src(Src), Dest(Dest), Subreg(Subreg) {}
+
+    /// Order only by source instruction / operand pair: there should never
+    /// be duplicate entries for the same source in any collection.
+    bool operator<(const DebugSubstitution &Other) const {
+      assert(Src != Other.Src && "Duplicate substitution seen?");
+      return Src < Other.Src;
+    }
   };
 
-  /// Substitution map: from one <inst,operand> pair identifying a value,
-  /// to a DebugSubstitution identifying another. Used to record changes in
-  /// where a value is defined, so that debug variable locations can find it
-  /// later.
-  std::map<DebugInstrOperandPair, DebugSubstitution> DebugValueSubstitutions;
+  /// Debug value substitutions: a collection of DebugSubstitution objects,
+  /// recording changes in where a value is defined. For example, when one
+  /// instruction is substituted for another. Keeping a record allows recovery
+  /// of variable locations after compilation finishes.
+  SmallVector<DebugSubstitution, 8> DebugValueSubstitutions;
 
   /// Location of a PHI instruction that is also a debug-info variable value,
   /// for the duration of register allocation. Loaded by the PHI-elimination
Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
===================================================================
--- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
+++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
@@ -1821,11 +1821,14 @@
   // Various optimizations may have happened to the value during codegen,
   // recorded in the value substitution table. Apply any substitutions to
   // the instruction / operand number in this DBG_INSTR_REF.
-  auto Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
-  while (Sub != MF.DebugValueSubstitutions.end()) {
-    InstNo = Sub->second.first;
-    OpNo = Sub->second.second;
-    Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
+  // Create dummy substitution with Src set, for lookup.
+  auto SoughtSub = MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
+  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
+  while (LowerBoundIt != MF.DebugValueSubstitutions.end() && LowerBoundIt->Src == SoughtSub.Src) {
+    InstNo = LowerBoundIt->Dest.first;
+    OpNo = LowerBoundIt->Dest.second;
+    SoughtSub.Src = {InstNo, OpNo};
+    LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
   }
 
   // Default machine value number is <None> -- if no instruction defines
@@ -3456,6 +3459,9 @@
     BBNumToRPO[MBB->getNumber()] = RPONumber;
     ++RPONumber;
   }
+
+  // Order value substitutions by their "source" operand pair, for quick lookup.
+  llvm::sort(MF.DebugValueSubstitutions);
 }
 
 /// Calculate the liveness information for the given machine function and
Index: llvm/lib/CodeGen/MIRPrinter.cpp
===================================================================
--- llvm/lib/CodeGen/MIRPrinter.cpp
+++ llvm/lib/CodeGen/MIRPrinter.cpp
@@ -221,12 +221,12 @@
   convertStackObjects(YamlMF, MF, MST);
   convertCallSiteObjects(YamlMF, MF, MST);
   for (auto &Sub : MF.DebugValueSubstitutions) {
-    auto &SubSrc = Sub.first;
-    const MachineFunction::DebugSubstitution &SubDest = Sub.second;
+    const auto &SubSrc = Sub.Src;
+    const auto &SubDest = Sub.Dest;
     YamlMF.DebugValueSubstitutions.push_back({SubSrc.first, SubSrc.second,
-                                              SubDest.Dest.first,
-                                              SubDest.Dest.second,
-                                              SubDest.Subreg});
+                                              SubDest.first,
+                                              SubDest.second,
+                                              Sub.Subreg});
   }
   if (const auto *ConstantPool = MF.getConstantPool())
     convert(YamlMF, *ConstantPool);
Index: llvm/lib/CodeGen/MachineFunction.cpp
===================================================================
--- llvm/lib/CodeGen/MachineFunction.cpp
+++ llvm/lib/CodeGen/MachineFunction.cpp
@@ -954,9 +954,7 @@
                                                  unsigned Subreg) {
   // Catch any accidental self-loops.
   assert(A.first != B.first);
-  auto Result = DebugValueSubstitutions.insert({A, {B, Subreg}});
-  (void)Result;
-  assert(Result.second && "Substitution for an already substituted value?");
+  DebugValueSubstitutions.push_back({A, B, Subreg});
 }
 
 void MachineFunction::substituteDebugValuesForInst(const MachineInstr &Old,