[Coverage] Restore the correct count value after processing a nested region in case of combined regions.

[ikudrin]

Summary

If we have several regions which cover the same code area, we should restore
the combined value for that region when return from a nested region.

This patch achieves that goal by combining regions before calling buildSegments.

[vsk]

Thanks for the patch.

+ 1 to Justin's comments.

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

302

nit: I think we can reduce repetition here by computing the Optional<uint64_t> first, and then calling startSegment.

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

10

Could you explain why the line containing the else is marked as having executed twice? It seems like it should only be executed once.

[davidxl]

I think a better fix is to change the active region stack into a stack of entry segments. The resulting code will be more readable.

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

281–282

This seems like a dead function now.

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

10

The 'else' line is not included by any region. It gets its count from the End segment of the previous region. The count of the end segment of a region is defined here to be the count of its parent region which makes sense for case like

if (...) {

// region 1

}
// non exec line

The non exec line's count is region 1's parent region's count, not region 1.

[ikudrin]

Thanks a lot for the comments! Please review the new version of the code.

• Added a new unit test.
• Eliminated dead code.
• Reworked the whole SegmentBuilder class.
• Addressed all other comments.

[davidxl]

Is it possible to combine identical regions (covering same area) before calling buildSegments? I think the resulting code would be a lot more readable.

[ikudrin]

• Implemented David's idea of combining identical regions before calling buildSegments.

[davidxl]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

412

I think this can be simplified by calling std::unique

Followed by a scan of the duplicate entries. For each dup entry, call lower_bound to to find the matching entry and update it if it exists.

475

This probably can be moved into 'sortNestedRegions'.

[ikudrin]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

412

I'm afraid I can't fully understand your idea. std::unique just removes duplicate entries and provides no way to work with removed items. So, I can't catch, how you suppose to scan dupes. Moreover, std::lower_bound requires O(log(N)) comparisons which leads to O(N*log(N)) complexity for the whole method. At the same time, the current code requires only one scan of an array and doesn't require additional dynamic memory.
Could you provide some code to illustrate your approach?

475

As they are separate and mostly independent tasks, I don't think it's good to merge them in one function. On the other hand, we can move both sortNestedRegions and combineRegionCounts into the SegmentBuilder class and simplify callers this way.

[davidxl]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

412

unique call returns a iterator pointing to the new logical end of the vector. The dups are from logical end to the original end. You are right that lower_bound O(log(N)), but the overall complexity is O(N*log(N)) only when the # of dups is linear to the total number of regions. I doubt it is the case in real case, but your concern is legit.

413

Last --> End (which is one past last)

418

Can you just do

// Find a new region
if (Active->StartLoc() != ... ) {

Active = I;
continue;

}

426

Add a comment before this line -- "// merge duplicate region"

475

yes -- since sortNestedRegions and combineRegions are always called together side by side -- having a wrapper call will be nicer.

[ikudrin]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

412

According to http://en.cppreference.com/w/cpp/algorithm/unique:

Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values.

So, you can't expect the dupes to be stored there.

[davidxl]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

412

ack.

[davidxl]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

418

Discard this comment -- your code is correct.

[ikudrin]

• Rebased to the top.
• Moved sortNestedRegions and combineRegions into SegmentBuilder.
• buildSegments now receives MutableArrayRef and performs sorting and combining regions internally.
• Some ASSERT_EQ was changed to EXPECT_EQ in the added test.

[davidxl]

looks ok to me. Check with Justin to see if he likes this cleanup.

[ikudrin]

• Reworked initialization of I according to Justin's comment.
• Added some explanation comments for the "Merge duplicate region" code block.

Please note that I've tried to make the behavior of the new code as close to the original as possible, apart from changes required for fix the described issue. More changes are coming, which will also change this block of code, so it's anyway not the final variant. See D18831.

llvm/trunk/include/llvm/ProfileData/CoverageMapping.h

CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
                   bool IsRegionEntry)
       : Line(Line), Col(Col), Count(Count), HasCount(true),
         IsRegionEntry(IsRegionEntry) {}
 
   friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
     return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
            std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
   }
-
-  void setCount(uint64_t NewCount) {
-    Count = NewCount;
-    HasCount = true;
-  }
-
-  void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
 };
 
 /// \brief Coverage information to be processed or displayed.
 ///
 /// This represents the coverage of an entire file, expansion, or function. It
 /// provides a sequence of CoverageSegments to iterate through, as well as the
 /// list of expansions that can be further processed.
 class CoverageData {

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

public:
 
   MapT::iterator begin() { return InstantiatedFunctions.begin(); }
 
   MapT::iterator end() { return InstantiatedFunctions.end(); }
 };
 
 class SegmentBuilder {
   std::vector<CoverageSegment> Segments;
-  SmallVector<const CountedRegion *, 8> ActiveRegions;
+  /// Each entry corresponds to the area of code covered by one or more regions
+  /// with the same bounds. It consists of the first region found for that area
+  /// and the combined counter.
+  SmallVector<std::pair<const CountedRegion *, Optional<uint64_t>>, 8>
+      ActiveRegions;
 
-  /// Start a segment with no count specified.
-  void startSegment(unsigned Line, unsigned Col) {
-    DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
-    Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
-  }
-
-  /// Start a segment with the given Region's count.
+  /// Start a segment at the given position with the given count.
   void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
-                    const CountedRegion &Region) {
-    if (Segments.empty())
-      Segments.emplace_back(Line, Col, IsRegionEntry);
-    CoverageSegment S = Segments.back();
+                    const Optional<uint64_t> &Count) {
     // Avoid creating empty regions.
-    if (S.Line != Line || S.Col != Col) {
-      Segments.emplace_back(Line, Col, IsRegionEntry);
-      S = Segments.back();
-    }
+    if (!Segments.empty() && Segments.back().Line == Line &&
+        Segments.back().Col == Col)
+      Segments.pop_back();
     DEBUG(dbgs() << "Segment at " << Line << ":" << Col);
-    // Set this region's count.
-    if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) {
-      DEBUG(dbgs() << " with count " << Region.ExecutionCount);
-      Segments.back().setCount(Region.ExecutionCount);
-    }
+    if (Count.hasValue()) {
+      DEBUG(dbgs() << " with count " << Count.getValue());
+      Segments.emplace_back(Line, Col, Count.getValue(), IsRegionEntry);
+    } else
+      Segments.emplace_back(Line, Col, IsRegionEntry);
     DEBUG(dbgs() << "\n");
   }
 
-  /// Start a segment for the given region.
-  void startSegment(const CountedRegion &Region) {
-    startSegment(Region.LineStart, Region.ColumnStart, true, Region);
+  /// Add the region to the top of the active stack and start
+  /// a new segment with the given count.
+  void pushRegion(const CountedRegion *Region,
+                  const Optional<uint64_t> &Count) {
+    startSegment(Region->LineStart, Region->ColumnStart, true, Count);
+    ActiveRegions.emplace_back(Region, Count);
   }
 
   /// Pop the top region off of the active stack, starting a new segment with
   /// the containing Region's count.
   void popRegion() {
-    const CountedRegion *Active = ActiveRegions.back();
-    unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
+    const CountedRegion *Active = ActiveRegions.back().first;
     ActiveRegions.pop_back();
-    if (ActiveRegions.empty())
-      startSegment(Line, Col);
-    else
-      startSegment(Line, Col, false, *ActiveRegions.back());
+    Optional<uint64_t> Count = None;
+    if (!ActiveRegions.empty())
+      Count = ActiveRegions.back().second;
+    startSegment(Active->LineEnd, Active->ColumnEnd, false, Count);
   }
 
 public:
   /// Build a list of CoverageSegments from a sorted list of Regions.
   std::vector<CoverageSegment> buildSegments(ArrayRef<CountedRegion> Regions) {
-    const CountedRegion *PrevRegion = nullptr;
+    const CountedRegion *ReferenceRegion = nullptr;
+    Optional<uint64_t> Count = None;
     for (const auto &Region : Regions) {
+      // Combine counters of the regions which cover the same area.
+      if (ReferenceRegion && ReferenceRegion->startLoc() == Region.startLoc() &&
+          ReferenceRegion->endLoc() == Region.endLoc()) {
+        if (Region.Kind == coverage::CounterMappingRegion::CodeRegion)
+          Count = Count.getValueOr(0) + Region.ExecutionCount;
+        continue;
+      }
+      // Add the previous region with the combined counter to the stack.
+      if (ReferenceRegion)
+        pushRegion(ReferenceRegion, Count);
       // Pop any regions that end before this one starts.
       while (!ActiveRegions.empty() &&
-             ActiveRegions.back()->endLoc() <= Region.startLoc())
+             ActiveRegions.back().first->endLoc() <= Region.startLoc())
         popRegion();
-      if (PrevRegion && PrevRegion->startLoc() == Region.startLoc() &&
-          PrevRegion->endLoc() == Region.endLoc()) {
-        if (Region.Kind == coverage::CounterMappingRegion::CodeRegion)
-          Segments.back().addCount(Region.ExecutionCount);
-      } else {
-        // Add this region to the stack.
-        ActiveRegions.push_back(&Region);
-        startSegment(Region);
-      }
-      PrevRegion = &Region;
+      ReferenceRegion = &Region;
+      if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion)
+        Count = Region.ExecutionCount;
+      else
+        Count = None;
     }
+    // Add the last region to the stack.
+    if (ReferenceRegion)
+      pushRegion(ReferenceRegion, Count);
     // Pop any regions that are left in the stack.
     while (!ActiveRegions.empty())
       popRegion();
     return Segments;
   }
 };
 }
 
std::sort(First, Last,
     if (LHS.startLoc() == RHS.startLoc())
       // When LHS completely contains RHS, we sort LHS first.
       return RHS.endLoc() < LHS.endLoc();
     return LHS.startLoc() < RHS.startLoc();
   });
 }
 
 static bool isExpansion(const CountedRegion &R, unsigned FileID) {
   return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
 }
 
 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) {
   CoverageData FileCoverage(Filename);
   std::vector<coverage::CountedRegion> Regions;
 
   for (const auto &Function : Functions) {
     auto MainFileID = findMainViewFileID(Filename, Function);
     if (!MainFileID)
       continue;
     auto FileIDs = gatherFileIDs(Filename, Function);
     for (const auto &CR : Function.CountedRegions)
       if (FileIDs.test(CR.FileID)) {
         Regions.push_back(CR);
         if (isExpansion(CR, *MainFileID))
           FileCoverage.Expansions.emplace_back(CR, Function);
       }
   }
 
   sortNestedRegions(Regions.begin(), Regions.end());
   DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
   FileCoverage.Segments = SegmentBuilder().buildSegments(Regions);
CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
   for (const auto &CR : Function.CountedRegions)
     if (CR.FileID == *MainFileID) {
       Regions.push_back(CR);
       if (isExpansion(CR, *MainFileID))
         FunctionCoverage.Expansions.emplace_back(CR, Function);
     }
 
   sortNestedRegions(Regions.begin(), Regions.end());
   DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
   FunctionCoverage.Segments = SegmentBuilder().buildSegments(Regions);
 
   return FunctionCoverage;
 }
 
 CoverageData
 CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) {
   CoverageData ExpansionCoverage(

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

 // RUN: llvm-cov show %S/Inputs/templateInstantiations.covmapping -instr-profile %S/Inputs/templateInstantiations.profdata -filename-equivalence %s | FileCheck -check-prefix=CHECK -check-prefix=ALL %s
 // RUN: llvm-cov show %S/Inputs/templateInstantiations.covmapping -instr-profile %S/Inputs/templateInstantiations.profdata -filename-equivalence -name=_Z4funcIbEiT_ %s | FileCheck -check-prefix=CHECK -check-prefix=FILTER %s
 
 // before coverage   // WHOLE-FILE:   | [[@LINE]]|// before
                      // FILTER-NOT:   | [[@LINE-1]]|// before
 template<typename T> // ALL:          | [[@LINE]]|template<typename T>
 int func(T x) {      // ALL-NEXT:    2| [[@LINE]]|int func(T x) {
   if(x)              // ALL-NEXT:    2| [[@LINE]]|  if(x)
     return 0;        // ALL-NEXT:    1| [[@LINE]]|    return 0;
-  else               // ALL-NEXT:    1| [[@LINE]]|  else
+  else               // ALL-NEXT:    2| [[@LINE]]|  else
     return 1;        // ALL-NEXT:    1| [[@LINE]]|    return 1;
   int j = 1;         // ALL-NEXT:    0| [[@LINE]]|  int j = 1;
-}                    // ALL-NEXT:    1| [[@LINE]]|}
+}                    // ALL-NEXT:    2| [[@LINE]]|}
 
                      // CHECK:       {{^ *(\| )?}}_Z4funcIbEiT_:
                      // CHECK-NEXT:  1| [[@LINE-9]]|int func(T x) {
                      // CHECK-NEXT:  1| [[@LINE-9]]|  if(x)
                      // CHECK-NEXT:  1| [[@LINE-9]]|    return 0;
                      // CHECK-NEXT:  1| [[@LINE-9]]|  else
                      // CHECK-NEXT:  0| [[@LINE-9]]|    return 1;
                      // CHECK-NEXT:  0| [[@LINE-9]]|  int j = 1;

llvm/trunk/unittests/ProfileData/CoverageMappingTest.cpp

TEST_P(MaybeSparseCoverageMappingTest, combine_regions) {
   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, 50, true), Segments[1]);
   ASSERT_EQ(CoverageSegment(4, 4, 10, false), Segments[2]);
   ASSERT_EQ(CoverageSegment(9, 9, false), Segments[3]);
 }
 
+TEST_P(MaybeSparseCoverageMappingTest, restore_combined_counter_after_nested_region) {
+  InstrProfRecord Record("func", 0x1234, { 10, 20, 40 });
+  ProfileWriter.addRecord(std::move(Record));
+  readProfCounts();
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
+  addCMR(Counter::getCounter(1), "file1", 1, 1, 9, 9);
+  addCMR(Counter::getCounter(2), "file1", 3, 3, 5, 5);
+  loadCoverageMapping("func", 0x1234);
+
+  CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+  ASSERT_EQ(4U, Segments.size());
+  ASSERT_EQ(CoverageSegment(1, 1, 30, true), Segments[0]);
+  ASSERT_EQ(CoverageSegment(3, 3, 40, true), Segments[1]);
+  ASSERT_EQ(CoverageSegment(5, 5, 30, false), Segments[2]);
+  ASSERT_EQ(CoverageSegment(9, 9, false), Segments[3]);
+}
+
 TEST_P(MaybeSparseCoverageMappingTest, dont_combine_expansions) {
   InstrProfRecord Record1("func", 0x1234, {10, 20});
   InstrProfRecord Record2("func", 0x1234, {0, 0});
   ProfileWriter.addRecord(std::move(Record1));
   ProfileWriter.addRecord(std::move(Record2));
   readProfCounts();
 
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);