Index: include/clang/Frontend/CodeGenOptions.h
===================================================================
--- include/clang/Frontend/CodeGenOptions.h
+++ include/clang/Frontend/CodeGenOptions.h
@@ -132,7 +132,7 @@
   /// non-empty.
   std::string DwarfDebugFlags;
 
-  std::map<std::string, std::string> DebugPrefixMap;
+  std::vector<std::pair<std::string, std::string>> DebugPrefixMap;
 
   /// The ABI to use for passing floating point arguments.
   std::string FloatABI;
Index: lib/CodeGen/CGDebugInfo.h
===================================================================
--- lib/CodeGen/CGDebugInfo.h
+++ lib/CodeGen/CGDebugInfo.h
@@ -80,7 +80,7 @@
   /// Cache of previously constructed Types.
   llvm::DenseMap<const void *, llvm::TrackingMDRef> TypeCache;
 
-  llvm::SmallDenseMap<llvm::StringRef, llvm::StringRef> DebugPrefixMap;
+  llvm::SmallVector<std::pair<llvm::StringRef, llvm::StringRef>, 4> DebugPrefixMap;
 
   /// Cache that maps VLA types to size expressions for that type,
   /// represented by instantiated Metadata nodes.
Index: lib/CodeGen/CGDebugInfo.cpp
===================================================================
--- lib/CodeGen/CGDebugInfo.cpp
+++ lib/CodeGen/CGDebugInfo.cpp
@@ -65,8 +65,9 @@
     : CGM(CGM), DebugKind(CGM.getCodeGenOpts().getDebugInfo()),
       DebugTypeExtRefs(CGM.getCodeGenOpts().DebugTypeExtRefs),
       DBuilder(CGM.getModule()) {
-  for (const auto &KV : CGM.getCodeGenOpts().DebugPrefixMap)
-    DebugPrefixMap[KV.first] = KV.second;
+  for (auto C = CGM.getCodeGenOpts().DebugPrefixMap,
+            I = C.rbegin(), E = C.rend(); I != E; ++I)
+    DebugPrefixMap.push_back(std::make_pair((*I).first, (*I).second));
   CreateCompileUnit();
 }
 
Index: lib/Frontend/CompilerInvocation.cpp
===================================================================
--- lib/Frontend/CompilerInvocation.cpp
+++ lib/Frontend/CompilerInvocation.cpp
@@ -604,7 +604,7 @@
   Opts.EmbedSource = Args.hasArg(OPT_gembed_source);
 
   for (const auto &Arg : Args.getAllArgValues(OPT_fdebug_prefix_map_EQ))
-    Opts.DebugPrefixMap.insert(StringRef(Arg).split('='));
+    Opts.DebugPrefixMap.push_back(StringRef(Arg).split('='));
 
   if (const Arg *A =
           Args.getLastArg(OPT_emit_llvm_uselists, OPT_no_emit_llvm_uselists))