[Coverage] Build sorted and unique segments

[vsk]

Summary

A coverage segment contains a starting line and column, an execution
count, and some other metadata. Clients of the coverage library use
segments to prepare line-oriented reports.

Users of the coverage library depend on segments being unique and sorted
in source order. Currently this is not guaranteed (this is why the clang
change which introduced deferred regions was reverted).

This commit documents the "unique and sorted" condition and asserts that
it holds. It also fixes the SegmentBuilder so that it produces correct
output in some edge cases.

Testing: I've added unit tests for some edge cases. I've also checked
that the new SegmentBuilder implementation is fully covered. Apart from
running check-profile and the llvm-cov tests, I've successfully used a
stage1 llvm-cov to prepare a coverage report for an instrumented clang
binary.

[ikudrin]

include/llvm/ProfileData/Coverage/CoverageMapping.h

201 ↗

(On Diff #111456)

I love this change! But maybe it deserves a separate patch?

unittests/ProfileData/CoverageMappingTest.cpp

566 ↗

(On Diff #111456)

Could you remind me where zero-length regions like (3:21) might come from?
Right now, it looks like the area from 3:21 to 4:4 has no counter associated with it, but I'd expect that a counter from the top-level region (1:5 - 4:4) was used here.

[vsk]

• Address two comments by @ikudrin (split out an NFC change, emit better segments when handling 0-length regions).
• I tested the updated patch in the same way, and was able to prepare a coverage report for clang without issue.

include/llvm/ProfileData/Coverage/CoverageMapping.h

201 ↗

(On Diff #111456)

I have split this change out (NFC) and rebased this patch on top of it (the new diff will still use LineColPair).

unittests/ProfileData/CoverageMappingTest.cpp

566 ↗

(On Diff #111456)

Zero-length regions can be emitted when we enter a macro expansion. And you're right, creating a segment at 3:21 with the count from 1:5 -> 4:4 would be more appropriate here. I will fix this.

[vsk]

Friendly ping.

[ikudrin]

The patch doesn't apply to the current tip clearly. And after applying it manually and fix compilation errors, I have two failing tests for llvm-cov: tools/llvm-cov/showLineExecutionCounts.cpp and tools/llvm-cov/threads.c, both of which fail with "Coverage segments not unique or sorted" assertion.

I'd also prefer a set of patches where each corner case is fixed in a separate patch and which gradually lead to the final code. Of course, if it's possible. Right now it looks like just changing an old implementation to a new one, and it could be hard to investigate later and understand each particular decision in the code. What do you think?

[vsk]

In D36813#857562, @ikudrin wrote:

The patch doesn't apply to the current tip clearly. And after applying it manually and fix compilation errors, I have two failing tests for llvm-cov: tools/llvm-cov/showLineExecutionCounts.cpp and tools/llvm-cov/threads.c, both of which fail with "Coverage segments not unique or sorted" assertion.

Both of these tests load the same covmapping file. That file was generated by an older, buggy clang. That version of clang produced coverage mapping regions where the start of the region actually ended after the end of the region. I have separate patches locally which (1) teach the coverage mapping reader and writer to report a recoverable Error when they find bogus mapping regions produced by the frontend, and (2) regenerate the buggy covmapping file. The clang bug was fixed long ago.

I had planned on landing the changes in one go but I can commit those fixes right away if you'd prefer.

I'd also prefer a set of patches where each corner case is fixed in a separate patch and which gradually lead to the final code. Of course, if it's possible. Right now it looks like just changing an old implementation to a new one, and it could be hard to investigate later and understand each particular decision in the code. What do you think?

I'm a bit hesitant to do that. I'm not sure that splitting up the logic would result in individual patches which are easier to understand. It would also mean that none of the patches could be committed, since the stage2 coverage bot would hit the 'sorted & unique' assertion.

If there's any new logic which is obscure or not well-commented, I'd be happy to explain it in more detail or improve the comments.

[ikudrin]

Yes, if it's possible, I'd like to see all the patches (one way or another), just to have the whole picture.

I don't insist on dividing the patch if you find it impractical. Do I understand it right that you've added all the found edge cases as unit tests in ProfileData/CoverageMappingTest.cpp?

[vsk]

In D36813#858542, @ikudrin wrote:

Yes, if it's possible, I'd like to see all the patches (one way or another), just to have the whole picture.

Understood, D37387 is the only extra patch needed.

I don't insist on dividing the patch if you find it impractical. Do I understand it right that you've added all the found edge cases as unit tests in ProfileData/CoverageMappingTest.cpp?

Thanks, I do find it a bit impractical. I've added all the edge cases I found as separate unit tests. I've also completed a stage2 coverage-enabled run with an asserts-enabled clang/llvm-cov, and checked that the segment builder changes are fully covered.

[ikudrin]

lib/ProfileData/Coverage/CoverageMapping.cpp

373 ↗

(On Diff #111592)

We can't get here with Loc == None because the only call where it is None sets FirstCompletedRegion to 0. So, the check for Loc in assert is a bit misleading. I'd add a separate asset to check that Loc is set.

382 ↗

(On Diff #111592)

The last of completed regions might not be processed completely, here is the test:

ProfileWriter.addRecord({"func1", 0x1234, {1, 2, 3, 4}}, Err);
startFunction("func1", 0x1234);

addCMR(Counter::getCounter(0), "file1", 1, 1, 8, 8);
addCMR(Counter::getCounter(1), "file1", 2, 2, 5, 5);
addCMR(Counter::getCounter(2), "file1", 3, 3, 4, 4);
addCMR(Counter::getCounter(3), "file1", 6, 6, 7, 7);

EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
const auto &FunctionRecord = *FunctionRecords.begin();
CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
std::vector<CoverageSegment> Segments(Data.begin(), Data.end());

ASSERT_EQ(8U, Segments.size());
EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
EXPECT_EQ(CoverageSegment(2, 2, 2, true), Segments[1]);
EXPECT_EQ(CoverageSegment(3, 3, 3, true), Segments[2]);
EXPECT_EQ(CoverageSegment(4, 4, 2, false), Segments[3]);
EXPECT_EQ(CoverageSegment(5, 5, 1, false), Segments[4]);
EXPECT_EQ(CoverageSegment(6, 6, 4, true), Segments[5]);
EXPECT_EQ(CoverageSegment(7, 7, 1, false), Segments[6]);
EXPECT_EQ(CoverageSegment(8, 8, false), Segments[7]);

432 ↗

(On Diff #111592)

There can't be another region after a zero-length region with the same StartLoc, right?
So, if you check this condition first, it'll simplify the code because there will be no need for 'else' branches and an empty 'then' block.

436 ↗

(On Diff #111592)

I'd prefer seeing these expressions as separate statements, like

// If it's the last region, emit a skipped segment.
const bool Skipped = (CR.index() + 1) == Regions.size();
startSegment(..., Skipped);

but it's for you to decide.

[vsk]

Thanks for your comments, I'll update the patch shortly.

lib/ProfileData/Coverage/CoverageMapping.cpp

373 ↗

(On Diff #111592)

Right, I'll tighten the assertion and the logic here.

382 ↗

(On Diff #111592)

Thank you very much for the catch and the test case! The problem is that there may be a "gap" between the end of the last completed region (5:5), and the start of the new region (6:6). In this case, the count from the last active region (1:1 -> 8:8, count=1) should apply to 5:5 -> 6:6.

This scenario was handled correctly in the case where there's only one completed region.

432 ↗

(On Diff #111592)

I think there can. If I'm understanding you correctly, this should be handled by the "handle_consecutive_regions_with_zero_length" unit test.

[vsk]

Address review feedback.

[ikudrin]

lib/ProfileData/Coverage/CoverageMapping.cpp

432 ↗

(On Diff #111592)

At this point, Regions are already sorted and combined. Thus:

• if B follows A and A.startLoc() == B.startLoc() then A.endLoc() < B.endLoc().
• You fixed the malformed case in the other patch, so for any region startLoc() <= endLoc().
• Consequently, if B follows A and A.startLoc() == A.endLoc(), then B can't have the same startLoc() as A because it violates one of previous statements.

As a result, the code might be simplified to something like this:

if (CurStartLoc == CR.value.endLoc()) {
  ...
  continue;
}
if (CR.index + 1 == Regions.size() || CurStartLoc != Regions[CR.index() + 1].startLoc()
  startSegment(CR.value(), CurStartLoc, true);

ActiveRegions.push_back(&CR.value());

What do you think?

370 ↗

(On Diff #114034)

I believe that this specific case, as long as the special handling of the last segment in the loop and adding a skipped segment in the end, all of them might be joined together. The function would be divided into the following simple steps:

1. std_stable_sort
2. In the loop, process all completed regions, apart from the last.
3. Remeber a pointer to the last region.
4. Remove completed regions from the list.
5. Decide if we need to add a segment started at endLoc of the last region (only if it differs from Loc)
6. Add a skipped or regular segment depending on ActiveRegions (if it is empty or not).

[vsk]

Thanks for your comments, I'll update the patch shortly.

lib/ProfileData/Coverage/CoverageMapping.cpp

432 ↗

(On Diff #111592)

That makes sense.

370 ↗

(On Diff #114034)

Good point, I think this makes the change substantially simpler. I tested the updated patch in the same way (prepare a coverage report for clang with an asserts-enabled binary + unit/lit tests).

[vsk]

Address review feedback.

[ikudrin]

LGTM.

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

 public:
   CoverageData() = default;
 
   CoverageData(StringRef Filename) : Filename(Filename) {}
 
   /// Get the name of the file this data covers.
   StringRef getFilename() const { return Filename; }
 
+  /// Get an iterator over the coverage segments for this object. The segments
+  /// are guaranteed to be uniqued and sorted by location.
   std::vector<CoverageSegment>::const_iterator begin() const {
     return Segments.begin();
   }
 
   std::vector<CoverageSegment>::const_iterator end() const {
     return Segments.end();
   }
 

llvm/trunk/lib/ProfileData/Coverage/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) {
-    // Avoid creating empty regions.
-    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 != CounterMappingRegion::SkippedRegion) {
-      DEBUG(dbgs() << " with count " << 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);
+  /// Emit a segment with the count from \p Region starting at \p StartLoc.
+  //
+  /// \p IsRegionEntry: The segment is at the start of a new region.
+  /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
+  void startSegment(const CountedRegion &Region, LineColPair StartLoc,
+                    bool IsRegionEntry, bool EmitSkippedRegion = false) {
+    bool HasCount = !EmitSkippedRegion &&
+                    (Region.Kind != CounterMappingRegion::SkippedRegion);
+
+    // If the new segment wouldn't affect coverage rendering, skip it.
+    if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
+      const auto &Last = Segments.back();
+      if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
+          !Last.IsRegionEntry)
+        return;
+    }
+
+    if (HasCount)
+      Segments.emplace_back(StartLoc.first, StartLoc.second,
+                            Region.ExecutionCount, IsRegionEntry);
     else
-      startSegment(Line, Col, false, *ActiveRegions.back());
+      Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
+
+    DEBUG({
+      const auto &Last = Segments.back();
+      dbgs() << "Segment at " << Last.Line << ":" << Last.Col
+             << " (count = " << Last.Count << ")"
+             << (Last.IsRegionEntry ? ", RegionEntry" : "")
+             << (!Last.HasCount ? ", Skipped" : "") << "\n";
+    });
+  }
+
+  /// Emit segments for active regions which end before \p Loc.
+  ///
+  /// \p Loc: The start location of the next region. If None, all active
+  /// regions are completed.
+  /// \p FirstCompletedRegion: Index of the first completed region.
+  void completeRegionsUntil(Optional<LineColPair> Loc,
+                            unsigned FirstCompletedRegion) {
+    // Sort the completed regions by end location. This makes it simple to
+    // emit closing segments in sorted order.
+    auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
+    std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
+                      [](const CountedRegion *L, const CountedRegion *R) {
+                        return L->endLoc() < R->endLoc();
+                      });
+
+    // Emit segments for all completed regions.
+    for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
+         ++I) {
+      const auto *CompletedRegion = ActiveRegions[I];
+      assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
+             "Completed region ends after start of new region");
+
+      const auto *PrevCompletedRegion = ActiveRegions[I - 1];
+      auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
+
+      // Don't emit any more segments if they start where the new region begins.
+      if (Loc && CompletedSegmentLoc == *Loc)
+        break;
+
+      // Don't emit a segment if the next completed region ends at the same
+      // location as this one.
+      if (CompletedSegmentLoc == CompletedRegion->endLoc())
+        continue;
+
+      startSegment(*CompletedRegion, CompletedSegmentLoc, false);
+    }
+
+    auto Last = ActiveRegions.back();
+    if (FirstCompletedRegion && Last->endLoc() != *Loc) {
+      // If there's a gap after the end of the last completed region and the
+      // start of the new region, use the last active region to fill the gap.
+      startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
+                   false);
+    } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
+      // Emit a skipped segment if there are no more active regions. This
+      // ensures that gaps between functions are marked correctly.
+      startSegment(*Last, Last->endLoc(), false, true);
+    }
+
+    // Pop the completed regions.
+    ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
   }
 
   void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
-    for (const auto &Region : Regions) {
-      // Pop any regions that end before this one starts.
-      while (!ActiveRegions.empty() &&
-             ActiveRegions.back()->endLoc() <= Region.startLoc())
-        popRegion();
-      // Add this region to the stack.
-      ActiveRegions.push_back(&Region);
-      startSegment(Region);
-    }
-    // Pop any regions that are left in the stack.
-    while (!ActiveRegions.empty())
-      popRegion();
+    for (const auto &CR : enumerate(Regions)) {
+      auto CurStartLoc = CR.value().startLoc();
+
+      // Active regions which end before the current region need to be popped.
+      auto CompletedRegions =
+          std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
+                                [&](const CountedRegion *Region) {
+                                  return !(Region->endLoc() <= CurStartLoc);
+                                });
+      if (CompletedRegions != ActiveRegions.end()) {
+        unsigned FirstCompletedRegion =
+            std::distance(ActiveRegions.begin(), CompletedRegions);
+        completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
+      }
+
+      // Try to emit a segment for the current region.
+      if (CurStartLoc == CR.value().endLoc()) {
+        // Avoid making zero-length regions active. If it's the last region,
+        // emit a skipped segment. Otherwise use its predecessor's count.
+        const bool Skipped = (CR.index() + 1) == Regions.size();
+        startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
+                     CurStartLoc, true, Skipped);
+        continue;
+      }
+      if (CR.index() + 1 == Regions.size() ||
+          CurStartLoc != Regions[CR.index() + 1].startLoc()) {
+        // Emit a segment if the next region doesn't start at the same location
+        // as this one.
+        startSegment(CR.value(), CurStartLoc, true);
+      }
+
+      // This region is active (i.e not completed).
+      ActiveRegions.push_back(&CR.value());
+    }
+
+    // Complete any remaining active regions.
+    if (!ActiveRegions.empty())
+      completeRegionsUntil(None, 0);
   }
 
   /// 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())
         return LHS.startLoc() < RHS.startLoc();
for (auto I = Regions.begin() + 1; I != End; ++I) {
       // 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.
+  /// Build a sorted 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);
 
+    DEBUG({
+      dbgs() << "Combined regions:\n";
+      for (const auto &CR : CombinedRegions)
+        dbgs() << "  " << CR.LineStart << ":" << CR.ColumnStart << " -> "
+               << CR.LineEnd << ":" << CR.ColumnEnd
+               << " (count=" << CR.ExecutionCount << ")\n";
+    });
+
     Builder.buildSegmentsImpl(CombinedRegions);
+
+#ifndef NDEBUG
+    for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
+      const auto &L = Segments[I - 1];
+      const auto &R = Segments[I];
+      if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
+        DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
+                     << " followed by " << R.Line << ":" << R.Col << "\n");
+        assert(false && "Coverage segments not unique or sorted");
+      }
+    }
+#endif
+
     return Segments;
   }
 };
 
 } // end anonymous namespace
 
 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
   std::vector<StringRef> Filenames;

llvm/trunk/test/tools/llvm-cov/deferred-region.cpp

 // RUN: llvm-cov show %S/Inputs/deferred-regions.covmapping -instr-profile %S/Inputs/deferred-regions.profdata -show-line-counts-or-regions -dump -path-equivalence=/Users/vk/src/llvm.org-coverage-braces/llvm/test/tools,%S/.. %s &> %t.out && FileCheck %s -input-file %t.out && FileCheck %s -input-file %t.out -check-prefix=MARKER
 
 void foo(int x) {
   if (x == 0) {
     return; // CHECK: [[@LINE]]|{{ +}}1|
   }
 
-} // CHECK: [[@LINE]]|{{ +}}2|
+} // CHECK: [[@LINE]]|{{ +}}1|
 
 void bar() {
   return;
 
 } // CHECK: [[@LINE]]|{{ +}}1|
 
 void for_loop() {
   if (false)

 // MARKER-NEXT: Highlighted line 45, 14 -> ?
 // MARKER-NEXT: Marker at 45:9 = 1
 // MARKER-NEXT: Highlighted line 46, 1 -> ?
 // MARKER-NEXT: Highlighted line 47, 1 -> 7
 // MARKER-NEXT: Highlighted line 47, 7 -> 14
 // MARKER-NEXT: Highlighted line 47, 14 -> 21
 // MARKER-NEXT: Highlighted line 47, 21 -> 23
 // MARKER-NEXT: Highlighted line 47, 23 -> 25
-// MARKER-NEXT: Highlighted line 47, 25 -> ?
 // MARKER-NEXT: Marker at 47:7 = 0
 // MARKER-NEXT: Marker at 47:14 = 0
 // MARKER-NEXT: Marker at 47:23 = 0
-// MARKER-NEXT: Highlighted line 48, 1 -> 6
 // MARKER-NEXT: Highlighted line 51, 7 -> 20
 // MARKER-NEXT: Marker at 51:7 = 0
 // MARKER-NEXT: Marker at 53:5 = 1
 // MARKER-NEXT: Marker at 53:12 = 6
 // MARKER-NEXT: Highlighted line 55, 9 -> 14
 // MARKER-NEXT: Highlighted line 63, 5 -> 13
 // MARKER-NEXT: Marker at 63:5 = 0
 // MARKER-NEXT: Highlighted line 67, 1 -> ?
 // MARKER-NEXT: Highlighted line 68, 1 -> 8
 // MARKER-NEXT: Highlighted line 68, 8 -> ?
 // MARKER-NEXT: Highlighted line 69, 1 -> 2

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

 // RUN: llvm-cov show %S/Inputs/highlightedRanges.covmapping -instr-profile %S/Inputs/highlightedRanges.profdata -dump -path-equivalence=/Users/bogner/code/llvm/test/tools,%S/.. %s 2>&1 | FileCheck %s -check-prefixes=TEXT,SHARED
 
 void func() {
   return;
   int i = 0;                     // SHARED: Highlighted line [[@LINE]], 3 ->
 }                                // SHARED: Highlighted line [[@LINE]], 1 -> 2
 
 void func2(int x) {
   if(x > 5) {
     while(x >= 9) {
       return;
       --x;                       // SHARED: Highlighted line [[@LINE]], 7 ->
-    }                            // SHARED: Highlighted line [[@LINE]], 1 -> 6
+    }
     int i = 0;                   // SHARED: Highlighted line [[@LINE]], 5 ->
   }                              // SHARED: Highlighted line [[@LINE]], 1 -> 4
 }
 
 void test() {
   int x = 0;
 
   if (x) {                       // SHARED: Highlighted line [[@LINE]], 10 ->

llvm/trunk/unittests/ProfileData/CoverageMappingTest.cpp

unsigned getFileIndexForFunction(StringRef Name) {
     return IndexInFunction;
   }
 
   void startFunction(StringRef FuncName, uint64_t Hash) {
     InputFunctions.emplace_back(FuncName.str(), Hash);
   }
 
   void addCMR(Counter C, StringRef File, unsigned LS, unsigned CS, unsigned LE,
-              unsigned CE) {
-    InputFunctions.back().Regions.push_back(CounterMappingRegion::makeRegion(
-        C, getFileIndexForFunction(File), LS, CS, LE, CE));
+              unsigned CE, bool Skipped = false) {
+    auto &Regions = InputFunctions.back().Regions;
+    unsigned FileID = getFileIndexForFunction(File);
+    Regions.push_back(
+        Skipped ? CounterMappingRegion::makeSkipped(FileID, LS, CS, LE, CE)
+                : CounterMappingRegion::makeRegion(C, FileID, LS, CS, LE, CE));
   }
 
   void addExpansionCMR(StringRef File, StringRef ExpandedFile, unsigned LS,
                        unsigned CS, unsigned LE, unsigned CE) {
     InputFunctions.back().Regions.push_back(CounterMappingRegion::makeExpansion(
         getFileIndexForFunction(File), getFileIndexForFunction(ExpandedFile),
         LS, CS, LE, CE));
   }
for (const auto &FunctionRecord : FunctionRecords) {
     } else {
       ASSERT_EQ("func2", FunctionRecord.Name);
       EXPECT_EQ(CoverageSegment(2, 2, 20, true), Segments[0]);
       EXPECT_EQ(CoverageSegment(6, 6, false), Segments[1]);
     }
   }
 }
 
+TEST_P(CoverageMappingTest, create_combined_regions) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1, 2, 3}}, Err);
+  startFunction("func1", 0x1234);
+
+  // Given regions which start at the same location, emit a segment for the
+  // last region.
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 2, 2);
+  addCMR(Counter::getCounter(1), "file1", 1, 1, 2, 2);
+  addCMR(Counter::getCounter(2), "file1", 1, 1, 2, 2);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(2U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 6, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(2, 2, false), Segments[1]);
+}
+
+TEST_P(CoverageMappingTest, skipped_segments_have_no_count) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 5, 5);
+  addCMR(Counter::getCounter(0), "file1", 5, 1, 5, 5, /*Skipped=*/true);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(3U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(5, 1, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(5, 5, false), Segments[2]);
+}
+
+TEST_P(CoverageMappingTest, multiple_regions_end_after_parent_ends) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1, 0}}, Err);
+  startFunction("func1", 0x1234);
+
+  // 1| F{ a{
+  // 2|
+  // 3|    a} b{ c{
+  // 4|
+  // 5|    b}
+  // 6|
+  // 7| c} d{   e{
+  // 8|
+  // 9| d}      e} F}
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9); //< F
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 3, 5); //< a
+  addCMR(Counter::getCounter(0), "file1", 3, 5, 5, 4); //< b
+  addCMR(Counter::getCounter(1), "file1", 3, 5, 7, 3); //< c
+  addCMR(Counter::getCounter(1), "file1", 7, 3, 9, 2); //< d
+  addCMR(Counter::getCounter(1), "file1", 7, 7, 9, 7); //< e
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  // Old output (not sorted or unique):
+  //   Segment at 1:1 with count 1
+  //   Segment at 1:1 with count 1
+  //   Segment at 3:5 with count 1
+  //   Segment at 3:5 with count 0
+  //   Segment at 3:5 with count 1
+  //   Segment at 5:4 with count 0
+  //   Segment at 7:3 with count 1
+  //   Segment at 7:3 with count 0
+  //   Segment at 7:7 with count 0
+  //   Segment at 9:7 with count 0
+  //   Segment at 9:2 with count 1
+  //   Top level segment at 9:9
+
+  // New output (sorted and unique):
+  //   Segment at 1:1 (count = 1), RegionEntry
+  //   Segment at 3:5 (count = 1), RegionEntry
+  //   Segment at 5:4 (count = 0)
+  //   Segment at 7:3 (count = 0), RegionEntry
+  //   Segment at 7:7 (count = 0), RegionEntry
+  //   Segment at 9:2 (count = 0)
+  //   Segment at 9:7 (count = 1)
+  //   Segment at 9:9 (count = 0), Skipped
+
+  ASSERT_EQ(8U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(3, 5, 1, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(5, 4, 0, false), Segments[2]);
+  EXPECT_EQ(CoverageSegment(7, 3, 0, true), Segments[3]);
+  EXPECT_EQ(CoverageSegment(7, 7, 0, true), Segments[4]);
+  EXPECT_EQ(CoverageSegment(9, 2, 0, false), Segments[5]);
+  EXPECT_EQ(CoverageSegment(9, 7, 1, false), Segments[6]);
+  EXPECT_EQ(CoverageSegment(9, 9, false), Segments[7]);
+}
+
+TEST_P(CoverageMappingTest, dont_emit_redundant_segments) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1, 1}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 4, 4);
+  addCMR(Counter::getCounter(1), "file1", 2, 2, 5, 5);
+  addCMR(Counter::getCounter(0), "file1", 3, 3, 6, 6);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(5U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(2, 2, 1, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(3, 3, 1, true), Segments[2]);
+  EXPECT_EQ(CoverageSegment(4, 4, 1, false), Segments[3]);
+  // A closing segment starting at 5:5 would be redundant: it would have the
+  // same count as the segment starting at 4:4, and has all the same metadata.
+  EXPECT_EQ(CoverageSegment(6, 6, false), Segments[4]);
+}
+
+TEST_P(CoverageMappingTest, dont_emit_closing_segment_at_new_region_start) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 6, 5);
+  addCMR(Counter::getCounter(0), "file1", 2, 2, 6, 5);
+  addCMR(Counter::getCounter(0), "file1", 3, 3, 6, 5);
+  addCMR(Counter::getCounter(0), "file1", 6, 5, 7, 7);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(5U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(2, 2, 1, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(3, 3, 1, true), Segments[2]);
+  EXPECT_EQ(CoverageSegment(6, 5, 1, true), Segments[3]);
+  // The old segment builder would get this wrong by emitting multiple segments
+  // which start at 6:5 (a few of which were skipped segments). We should just
+  // get a segment for the region entry.
+  EXPECT_EQ(CoverageSegment(7, 7, false), Segments[4]);
+}
+
+TEST_P(CoverageMappingTest, handle_consecutive_regions_with_zero_length) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1, 2}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 1, 1);
+  addCMR(Counter::getCounter(1), "file1", 1, 1, 1, 1);
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 1, 1);
+  addCMR(Counter::getCounter(1), "file1", 1, 1, 1, 1);
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 1, 1);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(1U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, true), Segments[0]);
+  // We need to get a skipped segment starting at 1:1. In this case there is
+  // also a region entry at 1:1.
+}
+
+TEST_P(CoverageMappingTest, handle_sandwiched_zero_length_region) {
+  ProfileWriter.addRecord({"func1", 0x1234, {2, 1}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 5, 4, 4);
+  addCMR(Counter::getCounter(1), "file1", 1, 9, 1, 50);
+  addCMR(Counter::getCounter(1), "file1", 2, 7, 2, 34);
+  addCMR(Counter::getCounter(1), "file1", 3, 5, 3, 21);
+  addCMR(Counter::getCounter(1), "file1", 3, 21, 3, 21);
+  addCMR(Counter::getCounter(1), "file1", 4, 12, 4, 17);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(10U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 5, 2, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(1, 9, 1, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(1, 50, 2, false), Segments[2]);
+  EXPECT_EQ(CoverageSegment(2, 7, 1, true), Segments[3]);
+  EXPECT_EQ(CoverageSegment(2, 34, 2, false), Segments[4]);
+  EXPECT_EQ(CoverageSegment(3, 5, 1, true), Segments[5]);
+  EXPECT_EQ(CoverageSegment(3, 21, 2, true), Segments[6]);
+  // Handle the zero-length region by creating a segment with its predecessor's
+  // count (i.e the count from 1:5 -> 4:4).
+  EXPECT_EQ(CoverageSegment(4, 4, false), Segments[7]);
+  // The area between 4:4 and 4:12 is skipped.
+  EXPECT_EQ(CoverageSegment(4, 12, 1, true), Segments[8]);
+  EXPECT_EQ(CoverageSegment(4, 17, false), Segments[9]);
+}
+
+TEST_P(CoverageMappingTest, handle_last_completed_region) {
+  ProfileWriter.addRecord({"func1", 0x1234, {1, 2, 3, 4}}, Err);
+  startFunction("func1", 0x1234);
+
+  addCMR(Counter::getCounter(0), "file1", 1, 1, 8, 8);
+  addCMR(Counter::getCounter(1), "file1", 2, 2, 5, 5);
+  addCMR(Counter::getCounter(2), "file1", 3, 3, 4, 4);
+  addCMR(Counter::getCounter(3), "file1", 6, 6, 7, 7);
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+  const auto FunctionRecords = LoadedCoverage->getCoveredFunctions();
+  const auto &FunctionRecord = *FunctionRecords.begin();
+  CoverageData Data = LoadedCoverage->getCoverageForFunction(FunctionRecord);
+  std::vector<CoverageSegment> Segments(Data.begin(), Data.end());
+
+  ASSERT_EQ(8U, Segments.size());
+  EXPECT_EQ(CoverageSegment(1, 1, 1, true), Segments[0]);
+  EXPECT_EQ(CoverageSegment(2, 2, 2, true), Segments[1]);
+  EXPECT_EQ(CoverageSegment(3, 3, 3, true), Segments[2]);
+  EXPECT_EQ(CoverageSegment(4, 4, 2, false), Segments[3]);
+  EXPECT_EQ(CoverageSegment(5, 5, 1, false), Segments[4]);
+  EXPECT_EQ(CoverageSegment(6, 6, 4, true), Segments[5]);
+  EXPECT_EQ(CoverageSegment(7, 7, 1, false), Segments[6]);
+  EXPECT_EQ(CoverageSegment(8, 8, false), Segments[7]);
+}
+
 TEST_P(CoverageMappingTest, expansion_gets_first_counter) {
   startFunction("func", 0x1234);
   addCMR(Counter::getCounter(1), "foo", 10, 1, 10, 2);
   // This starts earlier in "foo", so the expansion should get its counter.
   addCMR(Counter::getCounter(2), "foo", 1, 1, 20, 1);
   addExpansionCMR("bar", "foo", 3, 3, 3, 3);
 
   writeAndReadCoverageRegions();