[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

526 ↗

(On Diff #52813)

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

453

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

377

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.

lib/ProfileData/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 region, prefer CodeRegion to
+      // ExpansionRegion, and ExpansionRegion to SkippedRegion.
+      // That feature is required for correct working of
+      // combineRegions() and fixExpansionRegions().
+      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>
+  static MutableArrayRef<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.
+      // As long as Regions are sorted by sortNestedRegions(),
+      // we expect the following conditions:
+      // * If *I is CodeRegion, *Active is CodeRegion;
+      // * If *Active is ExpansionRegion, *I cannot be CodeRegion;
+      // * If *Active is SkippedRegion, *I can only be SkippedRegion.
+      // We need to add counts only for CodeRegions because:
+      // * ExapnsionRegions will inherit their counts from the outer region;
+      // * SkippedRegions do not need to be combined at all.
+      if (I->Kind == coverage::CounterMappingRegion::CodeRegion) {
+        assert(Active->Kind == coverage::CounterMappingRegion::CodeRegion);
         Active->ExecutionCount += I->ExecutionCount;
       }
+    }
     return Regions.drop_back(std::distance(++Active, End));
   }
 
+  /// Set counts of ExpansionRegions to the value of the outer region.
+  static void fixExpansionRegions(MutableArrayRef<CountedRegion> Regions) {
+    for (auto Begin = Regions.begin(), I = Regions.begin(), End = Regions.end();
+         I != End; ++I) {
+      if (I->Kind != coverage::CounterMappingRegion::ExpansionRegion)
+        continue;
+      // Find the nearest region containing the current region.
+      for (auto Outer = I; Outer != Begin;) {
+        --Outer;
+        assert(Outer->startLoc() <= I->startLoc());
+        if (Outer->endLoc() >= I->endLoc()) {
+          I->ExecutionCount = Outer->ExecutionCount;
+          break;
+        }
+      }
+    }
+  }
+
 public:
   /// Build a list of CoverageSegments from a list of Regions.
   static std::vector<CoverageSegment>
   buildSegments(MutableArrayRef<CountedRegion> Regions) {
     std::vector<CoverageSegment> Segments;
     SegmentBuilder Builder(Segments);
 
     sortNestedRegions(Regions);
-    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
+    Regions = combineRegions(Regions);
+    fixExpansionRegions(Regions);
 
-    Builder.buildSegmentsImpl(CombinedRegions);
+    Builder.buildSegmentsImpl(Regions);
     return Segments;
   }
 };
 }
 
 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
   std::vector<StringRef> Filenames;
   for (const auto &Function : getCoveredFunctions())

unittests/ProfileData/CoverageMappingTest.cpp

 }
 
 TEST_P(MaybeSparseCoverageMappingTest, strip_filename_prefix) {
   InstrProfRecord Record("file1:func", 0x1234, {0});
   ProfileWriter.addRecord(std::move(Record));
 
   startFunction("file1:func", 0x1234);
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   loadCoverageMapping();
 
   std::vector<std::string> Names;
   for (const auto &Func : LoadedCoverage->getCoveredFunctions())
     Names.push_back(Func.Name);
   ASSERT_EQ(1U, Names.size());
   ASSERT_EQ("func", Names[0]);
 }
 
TEST_P(MaybeSparseCoverageMappingTest, load_coverage_for_expanded_file) {
 
   CoverageData Data = LoadedCoverage->getCoverageForFile("expanded");
   std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
   ASSERT_EQ(2U, Segments.size());
   EXPECT_EQ(CoverageSegment(1, 1, 10, true), Segments[0]);
   EXPECT_EQ(CoverageSegment(1, 10, false), Segments[1]);
 }
 
+TEST_P(MaybeSparseCoverageMappingTest,
+       expansion_region_uses_count_of_outer_region) {
+  InstrProfRecord Record("func", 0x1234, {10, 20});
+  ProfileWriter.addRecord(std::move(Record));
+
+  startFunction("func", 0x1234);
+  addCMR(Counter::getCounter(1), "include", 1, 1, 1, 10);
+  addCMR(Counter::getCounter(0), "file", 1, 1, 5, 5);
+  addExpansionCMR("file", "include", 3, 1, 3, 5);
+
+  loadCoverageMapping();
+
+  CoverageData DataI = LoadedCoverage->getCoverageForFile("include");
+  std::vector<CoverageSegment> SegmentsI(DataI.begin(), DataI.end());
+  ASSERT_EQ(2U, SegmentsI.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 20, true), SegmentsI[0]);
+  EXPECT_EQ(CoverageSegment(1, 10, false), SegmentsI[1]);
+
+  // Despite the fact that the count value for the segment in "include" is "20",
+  // the corresponding segment in "file" should have value "10", inheriting
+  // it from its outer region.
+  CoverageData DataF = LoadedCoverage->getCoverageForFile("file");
+  std::vector<CoverageSegment> SegmentsF(DataF.begin(), DataF.end());
+  ASSERT_EQ(4U, SegmentsF.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 10, true), SegmentsF[0]);
+  EXPECT_EQ(CoverageSegment(3, 1, 10, true), SegmentsF[1]);
+  EXPECT_EQ(CoverageSegment(3, 5, 10, false), SegmentsF[2]);
+  EXPECT_EQ(CoverageSegment(5, 5, false), SegmentsF[3]);
+}
+
 INSTANTIATE_TEST_CASE_P(MaybeSparse, MaybeSparseCoverageMappingTest,
                         ::testing::Bool());
 
 } // end anonymous namespace