[clang] Apply -fcoverage-prefix-map reverse order

[gulfem]

Summary

This patch changes handling multiple -fcoverage-prefix-map options to
match GCC's behavior. GCC applies prefix remappings that are provided
in reverse order (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109591).

[MaskRay]

Can you add example options in the description and say how this patch is going to change it?

I think std::map is intended so that for -f*-prefix-map values, if both a/b=... and a/b/c=... match an input path, the longest wins, not the latest wins.

[gulfem]

In D148757#4282002, @MaskRay wrote:

Can you add example options in the description and say how this patch is going to change it?

I think std::map is intended so that for -f*-prefix-map values, if both a/b=... and a/b/c=... match an input path, the longest wins, not the latest wins.

We discovered the issue in the context of supporting source-based code coverage in the Pigweed project.
The project provides two -ffile-prefix-map paths that can impact coverage:
https://cs.opensource.google/pigweed/pigweed/+/main:pw_build/BUILD.gn;l=251-256

1. -ffile-prefix-map=../= to remove the relative path from the build directory to the root
2. -ffile-prefix-map==out/ to prepend out/ to any unmatched files

If the user-specified order is applied, 1) should be applied, but in this case 2) is applied because the std::map iteration order is not the same of the insertion order. Applying 2) appends out to beginning of file paths in coverage mapping records.

The question that we need to answer is whether following the user-specified order for -f*-prefix-map is the expected behavior. If that's the case, Clang does not follow that.
https://github.com/llvm/llvm-project/blob/main/clang/lib/CodeGen/CoverageMappingGen.cpp#L1653

[gulfem]

Modified the test case

[gulfem]

I compared Clang and GCC behavior.
1) Following user-specified prefix mapping order
GCC uses a linked list to store the prefix mappings, so it applies the prefix mappings based on the user-provided order.
https://github.com/gcc-mirror/gcc/blob/master/gcc/file-prefix-map.cc#L27
Whereas, Clang currently uses an std::map, which does NOT follow user-provided order. So, Clang and GCC behavior do not match on that.

2) Applying multiple prefix mappings
Both Clang and GCC apply the first matching prefix mapping, and does not apply the following prefix mappings. So, they are consistent in that.

https://github.com/gcc-mirror/gcc/blob/master/gcc/file-prefix-map.cc#L88
https://github.com/llvm/llvm-project/blob/main/clang/lib/CodeGen/CoverageMappingGen.cpp#L1653

[phosek]

LGTM

[MaskRay]

In D148757#4285735, @gulfem wrote:

I compared Clang and GCC behavior.
1) Following user-specified prefix mapping order
GCC uses a linked list to store the prefix mappings, so it applies the prefix mappings based on the user-provided order.
https://github.com/gcc-mirror/gcc/blob/master/gcc/file-prefix-map.cc#L27
Whereas, Clang currently uses an std::map, which does NOT follow user-provided order. So, Clang and GCC behavior do not match on that.

2) Applying multiple prefix mappings
Both Clang and GCC apply the first matching prefix mapping, and does not apply the following prefix mappings. So, they are consistent in that.

https://github.com/gcc-mirror/gcc/blob/master/gcc/file-prefix-map.cc#L88
https://github.com/llvm/llvm-project/blob/main/clang/lib/CodeGen/CoverageMappingGen.cpp#L1653

Sorry, request changes as I think I see conflicting needs and I think this needs more discussions. Cc debug-info

We have DebugPrefixMap and CoveragePrefixMap, and I think their order behavior should be the same.

D49466 added DebugPrefixMap to Clang which prefers a long prefix.
D132390 is a MC version of DebugPrefixMap that prefers a long prefix.

The current order of CoveragePrefixMap is definitely weird as it prefers a shorter prefix.
This patch is going to change the order to the command line option order, but it will be different from DebugPrefixMap.

Can CoveragePrefixMap be made to prefer a long prefix as DebugPrefixMap does?

-ffile-prefix-map==out/ to prepend out/ to any unmatched files

This operation feels a bit strange to me...

[MaskRay]

Created https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109591 (Multiple -fdebug-prefix-map= prefixes match, which one wins?) to discuss GCC's behavior.

[phosek]

I wasn't aware that debug-prefix-map prefers longest prefix. I agree that ideally coverage-prefix-map, debug-prefix-map and macro-prefix-map should be consistent across all LLVM tools and ideally also across compilers.

[MaskRay]

I'm creating a patch to change DebugPrefixMap to respect the command line option order...

[MaskRay]

In D148757#4289076, @MaskRay wrote:

I'm creating a patch to change DebugPrefixMap to respect the command line option order...

Created D148975 to follow GCC's behavior (the last applicable option wins).

In this patch, you may drop the DebugPrefixMap (clang/include/clang/Basic/CodeGenOptions.h) change (a no-op without other changes to DebugPrefixMap ).

[gulfem]

Remove the changes from debuginfo, which is handled in D14897.

[gulfem]

In D148757#4289152, @MaskRay wrote:

In D148757#4289076, @MaskRay wrote:

I'm creating a patch to change DebugPrefixMap to respect the command line option order...

Created D148975 to follow GCC's behavior (the last applicable option wins).

In this patch, you may drop the DebugPrefixMap (clang/include/clang/Basic/CodeGenOptions.h) change (a no-op without other changes to DebugPrefixMap ).

Thanks for you guidance on this @MaskRay, and I removed the changes to debuginfo in the new revision.

[gulfem]

Updated the text.

[MaskRay]

LGTM

clang/include/clang/Basic/CodeGenOptions.h

211

While adding a comment, clarify what coverage it is? There are multiple coverage instrumentation features in Clang.

clang/lib/CodeGen/CoverageMappingGen.cpp

1638–1639

CoveragePrefixMap can be removed. I just removed DebugPrefixMap as well:)

[gulfem]

Addressed feedback and rebased.

[gulfem]

Added a comment about reverse traversal.

[gulfem]

clang/lib/CodeGen/CoverageMappingGen.cpp

1638–1639

I'm marking this Done as you removed it in https://github.com/llvm/llvm-project/commit/d3e121780ac2724969a030415f3092170f3c7589.

[gulfem]

Added more info into HelpText and reversed prefix map in the first place to incorporate coworker feedback.
GCC uses a linked list to store the prefix mappings in reverse order:
https://github.com/gcc-mirror/gcc/blob/master/gcc/file-prefix-map.cc#L27

[gulfem]

Add text to document that coverage prefix map should be traversed in reverse order.

[MaskRay]

clang/include/clang/Basic/CodeGenOptions.h

211

The declaration should not repeat the comment at the use site.

I am asking for what coverage features this CoveragePrefixMap is used for...

[gulfem]

clang/include/clang/Basic/CodeGenOptions.h

211

@MaskRay does this sound good to you?

/// Prefix replacement map for source-based code coverage to remap source
/// file paths in coverage mapping.
llvm::SmallVector<std::pair<std::string, std::string>, 0> CoveragePrefixMap;

[gulfem]

Extend the comment about the usage of CoveragePrefixMap.

clang/include/clang/Basic/CodeGenOptions.h

public:
   /// non-empty.
   std::string DwarfDebugFlags;
 
   /// The string containing the commandline for the llvm.commandline metadata,
   /// 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::SmallVector<std::pair<std::string, std::string>, 0> CoveragePrefixMap;
 
   /// The ABI to use for passing floating point arguments.
   std::string FloatABI;
 
   /// The file to use for dumping bug report by `Debugify` for original
   /// debug info.
   std::string DIBugsReportFilePath;
 

clang/lib/CodeGen/CoverageMappingGen.h

struct FunctionInfo {
     bool IsUsed;
   };
 
   CodeGenModule &CGM;
   CoverageSourceInfo &SourceInfo;
   llvm::SmallDenseMap<const FileEntry *, unsigned, 8> FileEntries;
   std::vector<llvm::Constant *> FunctionNames;
   std::vector<FunctionInfo> FunctionRecords;
-  std::map<std::string, std::string> CoveragePrefixMap;
+
+  /// Prefix replacement map for coverage.
+  llvm::SmallVector<std::pair<llvm::StringRef, llvm::StringRef>, 0>
+      CoveragePrefixMap;
 
   std::string getCurrentDirname();
   std::string normalizeFilename(StringRef Filename);
 
   /// Emit a function record.
   void emitFunctionMappingRecord(const FunctionInfo &Info,
                                  uint64_t FilenamesRef);
 

clang/lib/CodeGen/CoverageMappingGen.cpp

if (R.Kind == CounterMappingRegion::ExpansionRegion)
       OS << " (Expanded file = " << R.ExpandedFileID << ")";
     OS << "\n";
   }
 }
 
 CoverageMappingModuleGen::CoverageMappingModuleGen(
     CodeGenModule &CGM, CoverageSourceInfo &SourceInfo)
     : CGM(CGM), SourceInfo(SourceInfo) {
-  CoveragePrefixMap = CGM.getCodeGenOpts().CoveragePrefixMap;
+  for (const auto &[From, To] : CGM.getCodeGenOpts().CoveragePrefixMap)
+    CoveragePrefixMap.emplace_back(From, To);
 }
 
 std::string CoverageMappingModuleGen::getCurrentDirname() {
   if (!CGM.getCodeGenOpts().CoverageCompilationDir.empty())
     return CGM.getCodeGenOpts().CoverageCompilationDir;
 
   SmallString<256> CWD;
   llvm::sys::fs::current_path(CWD);
   return CWD.str().str();
 }
 
 std::string CoverageMappingModuleGen::normalizeFilename(StringRef Filename) {
   llvm::SmallString<256> Path(Filename);
   llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
-  for (const auto &Entry : CoveragePrefixMap) {
-    if (llvm::sys::path::replace_path_prefix(Path, Entry.first, Entry.second))
+
+  // Traverse CoveragePrefixMap in reverse order to apply the last provided path
+  // prefix replacement when multiple -fcoverage-prefix-map options are
+  // provided.
+  for (const auto &[From, To] : llvm::reverse(CoveragePrefixMap))
+    if (llvm::sys::path::replace_path_prefix(Path, From, To))
       break;
-  }
+
   return Path.str().str();
 }
 
 static std::string getInstrProfSection(const CodeGenModule &CGM,
                                        llvm::InstrProfSectKind SK) {
   return llvm::getInstrProfSectionName(
       SK, CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
 }

clang/lib/Frontend/CompilerInvocation.cpp

#undef CODEGEN_OPTION_WITH_MARSHALLING
   for (const auto &Arg : Args.getAllArgValues(OPT_fdebug_prefix_map_EQ)) {
     auto Split = StringRef(Arg).split('=');
     Opts.DebugPrefixMap.insert(
         {std::string(Split.first), std::string(Split.second)});
   }
 
   for (const auto &Arg : Args.getAllArgValues(OPT_fcoverage_prefix_map_EQ)) {
     auto Split = StringRef(Arg).split('=');
-    Opts.CoveragePrefixMap.insert(
-        {std::string(Split.first), std::string(Split.second)});
+    Opts.CoveragePrefixMap.emplace_back(Split.first, Split.second);
   }
 
   const llvm::Triple::ArchType DebugEntryValueArchs[] = {
       llvm::Triple::x86, llvm::Triple::x86_64, llvm::Triple::aarch64,
       llvm::Triple::arm, llvm::Triple::armeb, llvm::Triple::mips,
       llvm::Triple::mipsel, llvm::Triple::mips64, llvm::Triple::mips64el};
 
   if (Opts.OptimizationLevel > 0 && Opts.hasReducedDebugInfo() &&

clang/test/Profile/coverage-prefix-map.c

 // RELATIVE: @__llvm_coverage_mapping = {{.*"\\02.*}}..{{/|\\+}}root{{/|\\+}}nested{{.*coverage-prefix-map\.c}}
 
 // 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=. -o - | FileCheck --check-prefix=COVERAGE-PREFIX-MAP %s
 // RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -emit-llvm -mllvm -enable-name-compression=false -main-file-name coverage-prefix-map.c ../root/nested/coverage-prefix-map.c -fcoverage-prefix-map=../root=. -o - | FileCheck --check-prefix=COVERAGE-PREFIX-MAP %s
 // COVERAGE-PREFIX-MAP: @__llvm_coverage_mapping = {{.*"\\02.*}}.{{/|\\+}}nested{{.*coverage-prefix-map\.c}}
 
 // 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 last -fcoverage-prefix-map option (-fcoverage-prefix-map==newpath) is applied.
+// 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-ORDER %s
+// COVERAGE-PREFIX-MAP-ORDER: @__llvm_coverage_mapping = {{.*"\\02.*newpath.*root.*nested.*coverage-prefix-map\.c}}
+
+// Test that last -fcoverage-prefix-map option (-fcoverage-prefix-map=%/t/root=.) is applied.
+// 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-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}}