[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

309

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

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

436

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.

495

This probably can be moved into 'sortNestedRegions'.

[ikudrin]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

436

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?

495

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

436

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.

437

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

442

Can you just do

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

Active = I;
continue;

}

450

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

495

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

436

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

436

ack.

[davidxl]

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

442

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

 
 class SegmentBuilder {
   std::vector<CoverageSegment> &Segments;
   SmallVector<const CountedRegion *, 8> ActiveRegions;
 
   SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
 
   /// 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.
   void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
                     const CountedRegion &Region) {
-    if (Segments.empty())
-      Segments.emplace_back(Line, Col, IsRegionEntry);
-    CoverageSegment S = Segments.back();
     // 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);
-    }
+      Segments.emplace_back(Line, Col, Region.ExecutionCount, 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);
   }
 
   /// 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;
     ActiveRegions.pop_back();
     if (ActiveRegions.empty())
       startSegment(Line, Col);
     else
       startSegment(Line, Col, false, *ActiveRegions.back());
   }
 
   void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
-    const CountedRegion *PrevRegion = nullptr;
     for (const auto &Region : Regions) {
       // Pop any regions that end before this one starts.
       while (!ActiveRegions.empty() &&
              ActiveRegions.back()->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;
-    }
     // 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();
+              });
+  }
+
+  /// 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.
+        Active->ExecutionCount += I->ExecutionCount;
+    }
+    return Regions.drop_back(std::distance(++Active, End));
+  }
+
 public:
-  /// Build a list of CoverageSegments from a sorted list of Regions.
+  /// Build a list of CoverageSegments from a list of Regions.
   static std::vector<CoverageSegment>
-  buildSegments(ArrayRef<CountedRegion> Regions) {
+  buildSegments(MutableArrayRef<CountedRegion> Regions) {
     std::vector<CoverageSegment> Segments;
     SegmentBuilder Builder(Segments);
-    Builder.buildSegmentsImpl(Regions);
+
+    sortNestedRegions(Regions);
+    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
+
+    Builder.buildSegmentsImpl(CombinedRegions);
     return Segments;
   }
 };
 }
 
 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
   std::vector<StringRef> Filenames;
   for (const auto &Function : getCoveredFunctions())

 static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
                                              const FunctionRecord &Function) {
   Optional<unsigned> I = findMainViewFileID(Function);
   if (I && SourceFile == Function.Filenames[*I])
     return I;
   return None;
 }
 
-/// Sort a nested sequence of regions from a single file.
-template <class It> static void sortNestedRegions(It First, It Last) {
-  std::sort(First, Last,
-            [](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();
-  });
-}
-
 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);
     auto FileIDs = gatherFileIDs(Filename, Function);
     for (const auto &CR : Function.CountedRegions)
       if (FileIDs.test(CR.FileID)) {
         Regions.push_back(CR);
         if (MainFileID && 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);
 
   return FileCoverage;
 }
 
 std::vector<const FunctionRecord *>
 CoverageMapping::getInstantiations(StringRef Filename) {
CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
   std::vector<coverage::CountedRegion> Regions;
   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(
       Expansion.Function.Filenames[Expansion.FileID]);
   std::vector<coverage::CountedRegion> Regions;
   for (const auto &CR : Expansion.Function.CountedRegions)
     if (CR.FileID == Expansion.FileID) {
       Regions.push_back(CR);
       if (isExpansion(CR, Expansion.FileID))
         ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
     }
 
-  sortNestedRegions(Regions.begin(), Regions.end());
   DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
                << "\n");
   ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
 
   return ExpansionCoverage;
 }
 
 namespace {

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));
+
+  startFunction("func", 0x1234);
+  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();
+
+  CoverageData Data = LoadedCoverage->getCoverageForFile("file1");
+  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]);
+}
+
 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));
 
   startFunction("func", 0x1234);
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);