[Coverage] Combine counts of expansion region if there are no code regions for the same area.

[ikudrin]

The motivation case for this patch is the following:

$ cat > sample.cpp << EOF
#define DO_LOOP1() \
    for (int K = 0; K < 2; ++K) {}

#define DO_LOOP2() \
    for (int K = 0; K < 2; ++K) {}

#define JUST_EXPAND() DO_LOOP2()

int main() {
    DO_LOOP1();
    JUST_EXPAND();
    return 0;
}
EOF
$ clang++ -fprofile-instr-generate -fcoverage-mapping sample.cpp 
$ ./a.out
$ llvm-profdata merge -o default.profdata default.profraw
$ llvm-cov show a.out -instr-profile default.profdata
       |    1|#define DO_LOOP1() \
      3|    2|    for (int K = 0; K < 2; ++K) {}
       |    3|
       |    4|#define DO_LOOP2() \
      3|    5|    for (int K = 0; K < 2; ++K) {}
       |    6|
      3|    7|#define JUST_EXPAND() DO_LOOP2()
       |    8|
      1|    9|int main() {
      3|   10|    DO_LOOP1();
      1|   11|    JUST_EXPAND();
      1|   12|    return 0;
      1|   13|}

As you may see, the counts for DO_LOOP macroses are 3, and these values are propagated to the outer code. As a result, counts for lines 7 and 10 are shown as 3 which looks quite weird.
After applying the patch, the output of llvm-cov looks more predictable:

$ llvm-cov show a.out -instr-profile default.profdata
       |    1|#define DO_LOOP1() \
      3|    2|    for (int K = 0; K < 2; ++K) {}
       |    3|
       |    4|#define DO_LOOP2() \
      3|    5|    for (int K = 0; K < 2; ++K) {}
       |    6|
      1|    7|#define JUST_EXPAND() DO_LOOP2()
       |    8|
      1|    9|int main() {
      1|   10|    DO_LOOP1();
      1|   11|    JUST_EXPAND();
      1|   12|    return 0;
      1|   13|}

[ikudrin]

Another example which is also fixed by this patch:

$ cat > sample.cpp << EOF
#define DO_LOOP() \
    for (int k = 0; k < 2; ++k) {}

#define DO_SOMETHING() \
    { \
        DO_LOOP(); \
    }

int main() {
    DO_SOMETHING();
    DO_SOMETHING();
    return 0;
}
EOF
$ clang++ -fprofile-instr-generate -fcoverage-mapping sample.cpp 
$ ./a.out
$ llvm-profdata merge -o default.profdata default.profraw
$ llvm-cov show a.out -instr-profile default.profdata
       |    1|#define DO_LOOP() \
      6|    2|    for (int k = 0; k < 2; ++k) {}
       |    3|
       |    4|#define DO_SOMETHING() \
      2|    5|    { \
      3|    6|        DO_LOOP(); \
      2|    7|    }
       |    8|
      1|    9|int main() {
      1|   10|    DO_SOMETHING();
      1|   11|    DO_SOMETHING();
      1|   12|    return 0;
      1|   13|}

Pay attention to line 6. The patched llvm-cov generates the following output:

$ llvm-cov show a.out -instr-profile default.profdata
       |    1|#define DO_LOOP() \
      6|    2|    for (int k = 0; k < 2; ++k) {}
       |    3|
       |    4|#define DO_SOMETHING() \
      2|    5|    { \
      2|    6|        DO_LOOP(); \
      2|    7|    }
       |    8|
      1|    9|int main() {
      1|   10|    DO_SOMETHING();
      1|   11|    DO_SOMETHING();
      1|   12|    return 0;
      1|   13|}

[davidxl]

Your little motivating examples are great -- please add them as test cases as well.

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

327 ↗

(On Diff #52813)

what is this change about?

410 ↗

(On Diff #52813)

Can you add a comment here with more explanation?

llvm/trunk/unittests/ProfileData/CoverageMappingTest.cpp

553

Also add a test for "include".

[ikudrin]

• Reworked to correspond the changes of D18610.
• Expanded the test.
• Added some comments.

I'll add test cases for llvm-cov with the next update.

[ikudrin]

• Added a test for llvm-cov.

[davidxl]

The code looks correct, but after a second though, I wonder if the logic in
fixExpansionRegion

should really be done in Clang: tools/clang/lib/CodeGen/CoverageMappingGen.cpp

The counter expression for the expansion region should really be the counter of the enclosing region, instead of 'enclosing region counter + ....'.

[ikudrin]

In D18831#411576, @davidxl wrote:

The code looks correct, but after a second though, I wonder if the logic in
fixExpansionRegion

should really be done in Clang: tools/clang/lib/CodeGen/CoverageMappingGen.cpp

The counter expression for the expansion region should really be the counter of the enclosing region, instead of 'enclosing region counter + ....'.

Thanks! Sounds reasonable, I'll see if the issue can be fixed there.

[ikudrin]

• To fully fix the original issue, D19725 is required.
• Simplified the logic of combining regions.
• Improved comments.
• Reworked test cases to check only the issue with combining expansions.

[vsk]

Thanks, this is great!

unittests/ProfileData/CoverageMappingTest.cpp

455 ↗

(On Diff #55606)

Could you use distinct counters here (e.g {2,3,5,7})? It would help show that the right regions are merged together.

[davidxl]

other than vsk's comments, lgtm.

lib/ProfileData/CoverageMapping.cpp

378 ↗

(On Diff #55606)

Clarify that ExpansionRegions from expanding a macro nested in another macro will have the same source locations. For such a case, the expansion regions's counts need to be combined.

llvm/trunk/lib/ProfileData/Coverage/CoverageMapping.cpp

void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
     }
     // Pop any regions that are left in the stack.
     while (!ActiveRegions.empty())
       popRegion();
   }
 
   /// Sort a nested sequence of regions from a single file.
   static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
-    std::sort(Regions.begin(), Regions.end(),
-              [](const CountedRegion &LHS, const CountedRegion &RHS) {
-                if (LHS.startLoc() == RHS.startLoc())
-                  // When LHS completely contains RHS, we sort LHS first.
-                  return RHS.endLoc() < LHS.endLoc();
-                return LHS.startLoc() < RHS.startLoc();
-              });
+    std::sort(Regions.begin(), Regions.end(), [](const CountedRegion &LHS,
+                                                 const CountedRegion &RHS) {
+      if (LHS.startLoc() != RHS.startLoc())
+        return LHS.startLoc() < RHS.startLoc();
+      if (LHS.endLoc() != RHS.endLoc())
+      // If LHS and RHS cover the same area, we need to sort them according
+      // to their kinds so that the most suitable region will become "active"
+      // in combineRegions(). Because we accumulate counter values only from
+      // regions of the same kind as the first region of the area, prefer
+      // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
+      static_assert(coverage::CounterMappingRegion::CodeRegion <
+                            coverage::CounterMappingRegion::ExpansionRegion &&
+                        coverage::CounterMappingRegion::ExpansionRegion <
+                            coverage::CounterMappingRegion::SkippedRegion,
+                    "Unexpected order of region kind values");
+      return LHS.Kind < RHS.Kind;
   }
 
   /// Combine counts of regions which cover the same area.
   static ArrayRef<CountedRegion>
   combineRegions(MutableArrayRef<CountedRegion> Regions) {
     if (Regions.empty())
       return Regions;
     auto Active = Regions.begin();
     auto End = Regions.end();
     for (auto I = Regions.begin() + 1; I != End; ++I) {
       if (Active->startLoc() != I->startLoc() ||
           Active->endLoc() != I->endLoc()) {
         // Shift to the next region.
         ++Active;
         if (Active != I)
           *Active = *I;
         continue;
       }
       // Merge duplicate region.
-      if (I->Kind != coverage::CounterMappingRegion::CodeRegion)
-        // Add counts only from CodeRegions.
-        continue;
-      if (Active->Kind == coverage::CounterMappingRegion::SkippedRegion)
-        // We have to overwrite SkippedRegions because of special handling
-        // of them in startSegment().
-        *Active = *I;
-      else
-        // Otherwise, just append the count.
+      // If CodeRegions and ExpansionRegions cover the same area, it's probably
+      // a macro which is fully expanded to another macro. In that case, we need
+      // to accumulate counts only from CodeRegions, or else the area will be
+      // counted twice.
+      // On the other hand, a macro may have a nested macro in its body. If the
+      // outer macro is used several times, the ExpansionRegion for the nested
+      // macro will also be added several times. These ExpansionRegions cover
+      // the same source locations and have to be combined to reach the correct
+      // value for that area.
+      // We add counts of the regions of the same kind as the active region
+      // to handle the both situations.
+      if (I->Kind == Active->Kind)
         Active->ExecutionCount += I->ExecutionCount;
     }
     return Regions.drop_back(std::distance(++Active, End));
   }
 
 public:
   /// Build a list of CoverageSegments from a list of Regions.
   static std::vector<CoverageSegment>

llvm/trunk/test/tools/llvm-cov/Inputs/combine_expansions.proftext

+main
+# Func Hash:
+0
+# Num Counters:
+1
+# Counter Values:
+1
+

llvm/trunk/test/tools/llvm-cov/combine_expansions.cpp

+// Check that we combine expansion regions.
+
+// RUN: llvm-profdata merge %S/Inputs/combine_expansions.proftext -o %t.profdata
+// RUN: llvm-cov show %S/Inputs/combine_expansions.covmapping -instr-profile %t.profdata -filename-equivalence %s | FileCheck %s
+
+#define SIMPLE_OP \
+  ++x
+// CHECK:       | [[@LINE-2]]|#define SIMPLE_OP
+// CHECK-NEXT: 2| [[@LINE-2]]|  ++x
+
+#define DO_SOMETHING \
+  {                  \
+    int x = 0;       \
+    SIMPLE_OP;       \
+  }
+// CHECK:       | [[@LINE-5]]|#define DO_SOMETHING
+// CHECK-NEXT: 2| [[@LINE-5]]|  {
+// CHECK-NEXT: 2| [[@LINE-5]]|    int x = 0;
+// CHECK-NEXT: 2| [[@LINE-5]]|    SIMPLE_OP;
+// CHECK-NEXT: 2| [[@LINE-5]]|  }
+
+int main() {    // CHECK:      1| [[@LINE]]|int main() {
+  DO_SOMETHING; // CHECK-NEXT: 1| [[@LINE]]|  DO_SOMETHING;
+  DO_SOMETHING; // CHECK-NEXT: 1| [[@LINE]]|  DO_SOMETHING;
+  return 0;     // CHECK-NEXT: 1| [[@LINE]]|  return 0;
+}               // CHECK-NEXT: 1| [[@LINE]]|}

llvm/trunk/unittests/ProfileData/CoverageMappingTest.cpp

TEST_P(MaybeSparseCoverageMappingTest,
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(4U, Segments.size());
   EXPECT_EQ(CoverageSegment(1, 1, 30, true), Segments[0]);
   EXPECT_EQ(CoverageSegment(3, 3, 40, true), Segments[1]);
   EXPECT_EQ(CoverageSegment(5, 5, 30, false), Segments[2]);
   EXPECT_EQ(CoverageSegment(9, 9, false), Segments[3]);
 }
 
+// If CodeRegions and ExpansionRegions cover the same area,
+// only counts of CodeRegions should be used.
 TEST_P(MaybeSparseCoverageMappingTest, dont_combine_expansions) {
   InstrProfRecord Record1("func", 0x1234, {10, 20});
   InstrProfRecord Record2("func", 0x1234, {0, 0});
   NoError(ProfileWriter.addRecord(std::move(Record1)));
   NoError(ProfileWriter.addRecord(std::move(Record2)));
 
   startFunction("func", 0x1234);
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   addCMR(Counter::getCounter(1), "file1", 3, 3, 4, 4);
   addCMR(Counter::getCounter(1), "include1", 6, 6, 7, 7);
   addExpansionCMR("file1", "include1", 3, 3, 4, 4);
   loadCoverageMapping();
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(4U, Segments.size());
   ASSERT_EQ(CoverageSegment(1, 1, 10, true), Segments[0]);
   ASSERT_EQ(CoverageSegment(3, 3, 20, true), Segments[1]);
   ASSERT_EQ(CoverageSegment(4, 4, 10, false), Segments[2]);
   ASSERT_EQ(CoverageSegment(9, 9, false), Segments[3]);
 }
 
+// If an area is covered only by ExpansionRegions, they should be combinated.
+TEST_P(MaybeSparseCoverageMappingTest, combine_expansions) {
+  InstrProfRecord Record("func", 0x1234, {2, 3, 7});
+  NoError(ProfileWriter.addRecord(std::move(Record)));
+
+  startFunction("func", 0x1234);
+  addCMR(Counter::getCounter(1), "include1", 1, 1, 1, 10);
+  addCMR(Counter::getCounter(2), "include2", 1, 1, 1, 10);
+  addCMR(Counter::getCounter(0), "file", 1, 1, 5, 5);
+  addExpansionCMR("file", "include1", 3, 1, 3, 5);
+  addExpansionCMR("file", "include2", 3, 1, 3, 5);
+
+  loadCoverageMapping();
+
+  CoverageData Data = LoadedCoverage->getCoverageForFile("file");
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+  ASSERT_EQ(4U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 2, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(3, 1, 10, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(3, 5, 2, false), Segments[2]);
+  EXPECT_EQ(CoverageSegment(5, 5, false), Segments[3]);
+}
+
 TEST_P(MaybeSparseCoverageMappingTest, strip_filename_prefix) {
   InstrProfRecord Record("file1:func", 0x1234, {0});
   NoError(ProfileWriter.addRecord(std::move(Record)));
 
   startFunction("file1:func", 0x1234);
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   loadCoverageMapping();
 
TEST_P(MaybeSparseCoverageMappingTest, load_coverage_for_expanded_file) {
   ASSERT_EQ(2U, Segments.size());
   EXPECT_EQ(CoverageSegment(1, 1, 10, true), Segments[0]);
   EXPECT_EQ(CoverageSegment(1, 10, false), Segments[1]);
 }
 
 INSTANTIATE_TEST_CASE_P(MaybeSparse, MaybeSparseCoverageMappingTest,
                         ::testing::Bool());
 
 } // end anonymous namespace