diff --git a/clang/include/clang/Basic/CodeGenOptions.h b/clang/include/clang/Basic/CodeGenOptions.h
--- a/clang/include/clang/Basic/CodeGenOptions.h
+++ b/clang/include/clang/Basic/CodeGenOptions.h
@@ -17,6 +17,8 @@
 #include "clang/Basic/XRayInstr.h"
 #include "llvm/ADT/FloatingPointMode.h"
 #include "llvm/Frontend/Debug/Options.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Target/TargetOptions.h"
@@ -206,8 +208,13 @@
   /// if non-empty.
   std::string RecordCommandLine;
 
-  std::map<std::string, std::string> DebugPrefixMap;
-  std::map<std::string, std::string> CoveragePrefixMap;
+  /// Prefix replacement map for coverage.
+  llvm::MapVector<std::string, std::string, llvm::StringMap<unsigned>>
+      CoveragePrefixMap;
+
+  /// Prefix replacement map for debug info.
+  llvm::MapVector<std::string, std::string, llvm::StringMap<unsigned>>
+      DebugPrefixMap;
 
   /// The ABI to use for passing floating point arguments.
   std::string FloatABI;
diff --git a/clang/lib/CodeGen/CoverageMappingGen.h b/clang/lib/CodeGen/CoverageMappingGen.h
--- a/clang/lib/CodeGen/CoverageMappingGen.h
+++ b/clang/lib/CodeGen/CoverageMappingGen.h
@@ -18,6 +18,8 @@
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/Support/raw_ostream.h"
 
@@ -107,7 +109,8 @@
   llvm::SmallDenseMap<const FileEntry *, unsigned, 8> FileEntries;
   std::vector<llvm::Constant *> FunctionNames;
   std::vector<FunctionInfo> FunctionRecords;
-  std::map<std::string, std::string> CoveragePrefixMap;
+  llvm::MapVector<std::string, std::string, llvm::StringMap<unsigned>>
+      CoveragePrefixMap;
 
   std::string getCurrentDirname();
   std::string normalizeFilename(StringRef Filename);
diff --git a/clang/test/Profile/coverage-prefix-map.c b/clang/test/Profile/coverage-prefix-map.c
--- a/clang/test/Profile/coverage-prefix-map.c
+++ b/clang/test/Profile/coverage-prefix-map.c
@@ -19,3 +19,13 @@
 
 // RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -emit-llvm -mllvm -enable-name-compression=false -main-file-name coverage-prefix-map.c %t/root/nested/coverage-prefix-map.c -fcoverage-compilation-dir=/custom -fcoverage-prefix-map=/custom=/nonsense -o - | FileCheck --check-prefix=COVERAGE-COMPILATION-DIR %s
 // COVERAGE-COMPILATION-DIR: @__llvm_coverage_mapping = {{.*"\\02.*}}nonsense
+
+// Test that user provided prefix replacement order is followed (-fcoverage-prefix-map==newpath is applied because it is the first one in the user-provided prefix-map order).
+// RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -emit-llvm -mllvm -enable-name-compression=false -main-file-name coverage-prefix-map.c %t/root/nested/coverage-prefix-map.c -fcoverage-prefix-map==newpath -fcoverage-prefix-map=%/t/root=. -o - | FileCheck --check-prefix=COVERAGE-PREFIX-MAP-ORDER %s
+// COVERAGE-PREFIX-MAP-ORDER: @__llvm_coverage_mapping = {{.*"\\02.*newpath.*root.*nested.*coverage-prefix-map\.c}}
+
+// Test that -fcoverage-prefix-map=%/t/root=. is applied but -fcoverage-prefix-map==newpath is NOT because of the order.
+// RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -emit-llvm -mllvm -enable-name-compression=false -main-file-name coverage-prefix-map.c %t/root/nested/coverage-prefix-map.c -fcoverage-prefix-map=%/t/root=. -fcoverage-prefix-map==newpath -o - | FileCheck --check-prefix=COVERAGE-PREFIX-MAP-REORDER %s
+// COVERAGE-PREFIX-MAP-REORDER: @__llvm_coverage_mapping =
+// COVERAGE-PREFIX-MAP-REORDER-NOT: newpath
+// COVERAGE-PREFIX-MAP-REORDER-SAME: nested{{.*coverage-prefix-map\.c}}