[Coverage] Suppress creating a code region if the same area is covered by an expansion region.

[ikudrin]

Summary

In many cases, these code regions are just redundant, but sometimes they could be assigned to the counter of the parent code region instead of the counter of the nested block.

[ikudrin]

This patch fixes the following issue:

$ cat > test.cpp << EOF
void dummy() {}

#define MACRO_1 dummy()

#define MACRO_2 MACRO_1

int main() {
  int i = 0;
  if (i > 5)
    MACRO_2;
}
EOF
$ clang++ -fprofile-instr-generate -fcoverage-mapping dummy.cpp test.cpp
$ ./a.out
$ llvm-profdata merge -o default.profdata default.profraw
$ llvm-cov show a.out -instr-profile --show-expansions default.profdata
    1|      0|void dummy() {}
    2|       |
    3|      0|#define MACRO_1 dummy()
    4|       |
    5|      1|#define MACRO_2 MACRO_1
    6|       |
    7|      1|int main() {
    8|      1|  int i = 0;
    9|      1|  if (i > 5)
   10|      1|    MACRO_2;
  ------------------
  |  |    5|      1|#define MACRO_2 MACRO_1
  |  |  ------------------
  |  |  |  |    3|      0|#define MACRO_1 dummy()
  |  |  ------------------
  ------------------
   11|      1|}

The result of the fixed version:

  1|      0|void dummy() {}
  2|       |
  3|      0|#define MACRO_1 dummy()
  4|       |
  5|      0|#define MACRO_2 MACRO_1
  6|       |
  7|      1|int main() {
  8|      1|  int i = 0;
  9|      1|  if (i > 5)
 10|      0|    MACRO_2;
------------------
|  |    5|      0|#define MACRO_2 MACRO_1
|  |  ------------------
|  |  |  |    3|      0|#define MACRO_1 dummy()
|  |  ------------------
------------------
 11|      1|}

[vsk]

Thanks for looking into this! I like the SourceRegionFilter setup.

lib/CodeGen/CoverageMappingGen.cpp

261

Nit, is the default value needed?

634

Out of curiosity, is this stable_sort step required for correctness? Or would our CHECK lines break without this?

In either case, would it be feasible to merge this step with the stable_sort in CoverageMappingWriter::write()?

[ikudrin]

• Removed a default value in emitSourceRegions(), added the corresponding argument to its call in EmptyCoverageMappingBuilder::write().
• Removed an additional sorting step in CounterCoverageMappingBuilder::write(), the patch is now depends on the extended sorting creteria in CoverageMappingWriter::write(), see D24034.

[ikudrin]

lib/CodeGen/CoverageMappingGen.cpp

262

Well, passing a distinct empty value from EmptyCoverageMappingBuilder::write() is a bit clearer.

640

I believe, it's mostly to make our tests happy, but I don't want to make more changes in the program's behaviour than needed.

[vsk]

Lgtm!

lib/CodeGen/CoverageMappingGen.cpp

llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
       FileIDMapping;
 
 public:
   /// \brief The coverage mapping regions for this function
   llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
   /// \brief The source mapping regions for this function.
   std::vector<SourceMappingRegion> SourceRegions;
 
+  /// \brief A set of regions which can be used as a filter.
+  ///
+  /// It is produced by emitExpansionRegions() and is used in
+  /// emitSourceRegions() to suppress producing code regions if
+  /// the same area is covered by expansion regions.
+  typedef llvm::SmallSet<std::pair<SourceLocation, SourceLocation>, 8>
+      SourceRegionFilter;
+
   CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
                          const LangOptions &LangOpts)
       : CVM(CVM), SM(SM), LangOpts(LangOpts) {}
 
   /// \brief Return the precise end location for the given token.
   SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
     // We avoid getLocForEndOfToken here, because it doesn't do what we want for
     // macro locations, which we just treat as expanded files.
for (const auto &I : SkippedRanges) {
       if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
           Region.LineEnd <= FileLineRanges[*CovFileID].second)
         MappingRegions.push_back(Region);
     }
   }
 
   /// \brief Generate the coverage counter mapping regions from collected
   /// source regions.
-  void emitSourceRegions() {
+  void
+  emitSourceRegions(const SourceRegionFilter &Filter = SourceRegionFilter()) {
     for (const auto &Region : SourceRegions) {
       assert(Region.hasEndLoc() && "incomplete region");
 
       SourceLocation LocStart = Region.getStartLoc();
       assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
 
       // Ignore regions from system headers.
       if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart)))
         continue;
 
       auto CovFileID = getCoverageFileID(LocStart);
       // Ignore regions that don't have a file, such as builtin macros.
       if (!CovFileID)
         continue;
 
       SourceLocation LocEnd = Region.getEndLoc();
       assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
              "region spans multiple files");
 
+      // Don't add code regions for the area covered by expansion regions.
+      // This not only suppresses redundant regions, but sometimes prevents
+      // creating regions with wrong counters if, for example, a statement's
+      // body ends at the end of a nested macro.
+      if (Filter.count(std::make_pair(LocStart, LocEnd)))
+        continue;
+
       // Find the spilling locations for the mapping region.
       unsigned LineStart = SM.getSpellingLineNumber(LocStart);
       unsigned ColumnStart = SM.getSpellingColumnNumber(LocStart);
       unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
       unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
 
       assert(LineStart <= LineEnd && "region start and end out of order");
       MappingRegions.push_back(CounterMappingRegion::makeRegion(
           Region.getCounter(), *CovFileID, LineStart, ColumnStart, LineEnd,
           ColumnEnd));
     }
   }
 
   /// \brief Generate expansion regions for each virtual file we've seen.
-  void emitExpansionRegions() {
+  SourceRegionFilter emitExpansionRegions() {
+    SourceRegionFilter Filter;
     for (const auto &FM : FileIDMapping) {
       SourceLocation ExpandedLoc = FM.second.second;
       SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc);
       if (ParentLoc.isInvalid())
         continue;
 
       auto ParentFileID = getCoverageFileID(ParentLoc);
       if (!ParentFileID)
         continue;
       auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
       assert(ExpandedFileID && "expansion in uncovered file");
 
       SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
       assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
              "region spans multiple files");
+      Filter.insert(std::make_pair(ParentLoc, LocEnd));
 
       unsigned LineStart = SM.getSpellingLineNumber(ParentLoc);
       unsigned ColumnStart = SM.getSpellingColumnNumber(ParentLoc);
       unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
       unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
 
       MappingRegions.push_back(CounterMappingRegion::makeExpansion(
           *ParentFileID, *ExpandedFileID, LineStart, ColumnStart, LineEnd,
           ColumnEnd));
     }
+    return Filter;
   }
 };
 
 /// \brief Creates unreachable coverage regions for the functions that
 /// are not emitted.
 struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
   EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
                               const LangOptions &LangOpts)
CounterCoverageMappingBuilder(
       llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
       const LangOptions &LangOpts)
       : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap) {}
 
   /// \brief Write the mapping data to the output stream
   void write(llvm::raw_ostream &OS) {
     llvm::SmallVector<unsigned, 8> VirtualFileMapping;
     gatherFileIDs(VirtualFileMapping);
-    emitSourceRegions();
-    emitExpansionRegions();
+    SourceRegionFilter Filter = emitExpansionRegions();
+    emitSourceRegions(Filter);
+    // Expansion regions are expected to be added after code regions.
+    std::stable_sort(
+        MappingRegions.begin(), MappingRegions.end(),
+        [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) {
+          return LHS.Kind < RHS.Kind;
+        });
     gatherSkippedRegions();
 
     if (MappingRegions.empty())
       return;
 
     CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
                                  MappingRegions);
     Writer.write(OS);
   }
 
   void VisitStmt(const Stmt *S) {
     if (S->getLocStart().isValid())
       extendRegion(S);
     for (const Stmt *Child : S->children())

test/CoverageMapping/macroception.c

 // RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name macroception.c %s | FileCheck %s
 
 #define M2 {
 #define M1 M2
 #define M22 }
 #define M11 M22
 
 // CHECK-LABEL: main:
 // CHECK-NEXT: Expansion,File 0, [[@LINE+2]]:12 -> [[@LINE+2]]:14 = #0
 // CHECK-NEXT: File 0, [[@LINE+1]]:14 -> [[@LINE+3]]:2 = #0
 int main() M1
   return 0;
 }
-// CHECK-NEXT: File 1, 4:12 -> 4:14 = #0
 // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0
 // CHECK-NEXT: File 2, 3:12 -> 3:13 = #0
 
 // CHECK-LABEL: func2:
 // CHECK-NEXT: File 0, [[@LINE+2]]:14 -> [[@LINE+4]]:4 = #0
 // CHECK-NEXT: Expansion,File 0, [[@LINE+3]]:1 -> [[@LINE+3]]:4 = #0
 void func2() {
   int x = 0;
 M11
-// CHECK-NEXT: File 1, 6:13 -> 6:16 = #0
 // CHECK-NEXT: Expansion,File 1, 6:13 -> 6:16 = #0
 // CHECK-NEXT: File 2, 5:13 -> 5:14 = #0
 
 // CHECK-LABEL: func3:
 // CHECK-NEXT: Expansion,File 0, [[@LINE+3]]:14 -> [[@LINE+3]]:16 = #0
 // CHECK-NEXT: File 0, [[@LINE+2]]:16 -> [[@LINE+4]]:4 = #0
 // CHECK-NEXT: Expansion,File 0, [[@LINE+3]]:1 -> [[@LINE+3]]:4 = #0
 void func3() M1
   int x = 0;
 M11
-// CHECK-NEXT: File 1, 4:12 -> 4:14 = #0
 // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0
-// CHECK-NEXT: File 2, 6:13 -> 6:16 = #0
 // CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0
 // CHECK-NEXT: File 3, 3:12 -> 3:13 = #0
 // CHECK-NEXT: File 4, 5:13 -> 5:14 = #0
 
 // CHECK-LABEL: func4:
 // CHECK-NEXT: Expansion,File 0, [[@LINE+3]]:14 -> [[@LINE+3]]:16 = #0
 // CHECK-NEXT: File 0, [[@LINE+2]]:16 -> [[@LINE+2]]:20 = #0
 // CHECK-NEXT: Expansion,File 0, [[@LINE+1]]:17 -> [[@LINE+1]]:20 = #0
 void func4() M1 M11
-// CHECK-NEXT: File 1, 4:12 -> 4:14 = #0
 // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0
-// CHECK-NEXT: File 2, 6:13 -> 6:16 = #0
 // CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0
 // CHECK-NEXT: File 3, 3:12 -> 3:13 = #0
 // CHECK-NEXT: File 4, 5:13 -> 5:14 = #0

test/CoverageMapping/macros.c

 // RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name macros.c %s | FileCheck %s
 
 #define MACRO return; bar()
 #define MACRO_2 bar()
 #define MACRO_1 return; MACRO_2
+#define MACRO_3 MACRO_2
 
 void bar() {}
 
 // CHECK: func
 void func() {  // CHECK-NEXT: File 0, [[@LINE]]:13 -> [[@LINE+5]]:2 = #0
   int i = 0;
   // CHECK-NEXT: Expansion,File 0, [[@LINE+1]]:3 -> [[@LINE+1]]:8 = #0
   MACRO;       // CHECK-NEXT: File 0, [[@LINE]]:8 -> [[@LINE+2]]:2 = 0
   i = 2;
 }
 // CHECK-NEXT: File 1, 3:15 -> 3:28 = #0
 // CHECK-NEXT: File 1, 3:23 -> 3:28 = 0
 
 // CHECK-NEXT: func2
 void func2() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+5]]:2 = #0
   int i = 0;
   // CHECK-NEXT: Expansion,File 0, [[@LINE+1]]:3 -> [[@LINE+1]]:10 = #0
   MACRO_1;     // CHECK-NEXT: File 0, [[@LINE]]:10 -> [[@LINE+2]]:2 = 0
   i = 2;
 }
 // CHECK-NEXT: File 1, 5:17 -> 5:32 = #0
-// CHECK-NEXT: File 1, 5:25 -> 5:32 = 0
 // CHECK-NEXT: Expansion,File 1, 5:25 -> 5:32 = 0
 // CHECK-NEXT: File 2, 4:17 -> 4:22 = 0
 
 // CHECK-NEXT: func3
 void func3() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+3]]:2 = #0
   MACRO_2; // CHECK-NEXT: Expansion,File 0, [[@LINE]]:3 -> [[@LINE]]:10 = #0
   MACRO_2; // CHECK-NEXT: Expansion,File 0, [[@LINE]]:3 -> [[@LINE]]:10 = #0
 }
 // CHECK-NEXT: File 1, 4:17 -> 4:22 = #0
 // CHECK-NEXT: File 2, 4:17 -> 4:22 = #0
 
 // CHECK-NEXT: func4
 void func4() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+6]]:2 = #0
   int i = 0;
   while (i++ < 10) // CHECK-NEXT: File 0, [[@LINE]]:10 -> [[@LINE]]:18 = (#0 + #1)
     if (i < 5) // CHECK-NEXT: File 0, [[@LINE]]:5 -> [[@LINE+2]]:14 = #1
                // CHECK-NEXT: File 0, [[@LINE-1]]:9 -> [[@LINE-1]]:14 = #1
       MACRO_2; // CHECK-NEXT: Expansion,File 0, [[@LINE]]:7 -> [[@LINE]]:14 = #2
 }
 // CHECK-NEXT: File 1, 4:17 -> 4:22 = #2
 // CHECK-NOT: File 1
 
+// CHECK-NEXT: func5
+void func5() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+4]]:2 = #0
+  int i = 0;
+  if (i > 5) // CHECK-NEXT: File 0, [[@LINE]]:7 -> [[@LINE]]:12 = #0
+    MACRO_3; // CHECK-NEXT: Expansion,File 0, [[@LINE]]:5 -> [[@LINE]]:12 = #1
+}
+// CHECK-NEXT: Expansion,File 1, 6:17 -> 6:24 = #1
+// CHECK-NEXT: File 2, 4:17 -> 4:22 = #1
+
 int main(int argc, const char *argv[]) {
   func();
   func2();
   func3();
   func4();
 }