[CoverageMapping] Handle gaps in counter IDs for source-based coverage

[pirama]

Summary

For source-based coverage, the frontend sets the counter IDs and the
constraints of counter IDs is not defined. For e.g., the Rust frontend
until recently had a reserved counter #0
(https://github.com/rust-lang/rust/pull/83774). Rust coverage
instrumentation also creates counters on edges in addition to basic
blocks. Some functions may have more counters than regions.

This breaks an assumption in CoverageMapping.cpp where the number of
counters in a function is assumed to be bounded by the number of
regions:

Counts.assign(Record.MappingRegions.size(), 0);

This assumption causes CounterMappingContext::evaluate() to fail since
there are not enough counter values created in the above call to
Counts.assign. Consequently, some uncovered functions are not
reported in coverage reports.

This change walks a Function's CoverageMappingRecord to find the maximum
counter ID, and uses it to initialize the counter array when instrprof
records are missing for a function in sparse profiles.

[vsk]

Thanks for digging into this. Could you explain why it's necessary to use more coverage counters than there are regions? If there's no longer a reserved counter (counter #0), then are counters N >= Regions.size() somehow redundant (and if so, are they worth deduplicating in the Rust FE)?

[pirama]

In D101780#2744912, @vsk wrote:

Thanks for digging into this. Could you explain why it's necessary to use more coverage counters than there are regions? If there's no longer a reserved counter (counter #0), then are counters N >= Regions.size() somehow redundant (and if so, are they worth deduplicating in the Rust FE)?

I'm not very familiar with the Rust FE. Here's one example I see when we build this for Android:

Counter in file 0 520:20 -> 520:21, #1
Counter in file 0 520:24 -> 520:25, (#6 + ((((#5 + #4) + #3) + #2) + (#1 - (#6 + (#5 + (#4 + (#3 + #2)))))))

There are only two regions in this function which seems to be a generated function for a map.

ok_or(
    LOG_LEVEL_NAMES
        .iter()
        .position(|&name| eq_ignore_ascii_case(name, level))
        .into_iter()
        .filter(|&idx| idx != 0)
        .map(|idx| Level::from_usize(idx).unwrap())
        .next(),

Line 520 corresponds to the map call.

Adding @richkadel in case he has more details. IIUC, Rust FE adds counters before frontend DCE. The coverage mapping is written after DCE, so is skipped for any deleted regions. But the counter expressions may remain and refer to these deleted counters. Also, this example is from an older version of Rust FE. There may be new fixes in the Rust nightly builds but not sure if this pass ordering issue would still be present.

At a high level, we don't currently document this assumption or requirement for LLVM coverage and there's no error/warning when it is violated. So other frontends can make similar errors as well. Making llmv-cov accept this would prevent this assumption from tripping other FEs. An alternate to this change would be detect violations and have LLVM issue a warning/error.

[vsk]

Thanks for the context. I haven't looked at the Rust FE's coverage implementation, so I'm not familiar with any tradeoffs inherent to the implementation approach. One thing you wrote does concern me:

Rust FE adds counters before frontend DCE. The coverage mapping is written after DCE, so is skipped for any deleted regions.

While it isn't a hard requirement that the source -> coverage mapping become immutable before optimization begins, that is the traditional approach taken by clang & swiftc. (We nod towards this in https://clang.llvm.org/docs/SourceBasedCodeCoverage.html#impact-of-llvm-optimizations-on-coverage-reports, but you're right that the documentation could be improved.) IIUC Rust's behavior is a bit of a departure. Although it probably saves some binary size in *.prof{raw,data} files (I wonder how much?), it does also introduce additional complexity.

I see two options for moving forward:

1. Have llvm be more permissive about the number of counters when loading sparse .profdata (this patch)
2. Have llvm be less permissive (assert that #counters < #regions), document the new requirement and change the Rust FE to emit counters before DCE

I think (2) would lead to less complexity overall in both Rust & llvm, but both sound reasonable to me. Wdyt?

[richkadel]

While it isn't a hard requirement that the source -> coverage mapping become immutable before optimization begins, that is the traditional approach taken by clang & swiftc. (We nod towards this in https://clang.llvm.org/docs/SourceBasedCodeCoverage.html#impact-of-llvm-optimizations-on-coverage-reports,

@vsk - Just so I'm clear, are you saying that every Counter and Expression generated is guaranteed to be added to the coverage map (so there are no index gaps), even if the counter is part of an unreachable (and therefore eliminated) branch/block?

And, if so, I assume it's OK for a dead branch/block to be eliminated (so the instrprof.increment call for that branch's counter is never added.) But even if the code to increment that counter is not in the code, the coverage map includes the counter. Right?

I recently added support for reporting code regions for dead blocks, but I am replacing them with Zero counters. If I'm understanding you correctly, then I may be able to just retain the original counter id and/or expression and add them to the map instead of converting them to Zero counters, and therefore meet your expectations.

I see two options for moving forward:

1. Have llvm be more permissive about the number of counters when loading sparse .profdata (this patch)
2. Have llvm be less permissive (assert that #counters < #regions), document the new requirement and change the Rust FE to emit counters before DCE

I think (2) would lead to less complexity overall in both Rust & llvm, but both sound reasonable to me. Wdyt?

Unless I misunderstand the above, then yes, option 2. And the assertion error message needs to explain the problem (something like, "non-contiguous counter IDs are not allowed") if you discover a coverage map has counter ID gaps or expressions that refer to missing counters.

Thanks for pointing this out and let me know what I have wrong here.

[richkadel]

cc: @tmandry

[richkadel]

@vsk - Also, I want to confirm that it is OK to have counters that are incremented (via instrprof.increment intrinsic) that are not associated with a code region.

Without a code region, I can't add that counter to the coverage map, so, assuming this is not violating LLVM's assumptions, I guess there may be counter ID gaps.

I'm not sure what clang or swiftc does, but in the Rust FE, I sometimes need to count edges between nodes in the CFG (branches taken, between two blocks) since the target block can be executed from multiple incoming edges.

This seems to work fine so far, but I want to make sure. And my suggested error message (prior comment) is probably not accurate (I now realize).

This stuff is hard to explain :-)

[pirama]

In D101780#2752061, @richkadel wrote:

@vsk - Also, I want to confirm that it is OK to have counters that are incremented (via instrprof.increment intrinsic) that are not associated with a code region.

The expectation is that No. of code regions > Max. counter ID. If there are no gaps in counter IDs, and counters IDs start at 0, then Max. counter ID = No. of counters - 1, so we'd need No. of code regions >= No. of counters.

The underlying reasoning is that for line coverage, we can assign one counter per code region and so we'd need any more counters than regions.

Without a code region, I can't add that counter to the coverage map, so, assuming this is not violating LLVM's assumptions, I guess there may be counter ID gaps.

I'm not sure what clang or swiftc does, but in the Rust FE, I sometimes need to count edges between nodes in the CFG (branches taken, between two blocks) since the target block can be executed from multiple incoming edges.

Do we need counters on edges if we're only interested in line segment coverage?

This seems to work fine so far, but I want to make sure. And my suggested error message (prior comment) is probably not accurate (I now realize).

This stuff is hard to explain :-)

[richkadel]

Do we need counters on edges if we're only interested in line segment coverage?

Edge counters exist so they can be operands in expressions, and since they don't have a code region, they would not be referenced directly by a code region in a report; but the expression might, and that's we we need them.

(I don't think "line coverage" is a factor. The coverage map only concerns itself with the regions. If the region happens to have one or more newlines, or if there are multiple regions on a line, that isn't relevant to the coverage map; at least not for Rust. llvm-cov computes line coverages when generating the report.)

[pirama]

In D101780#2752181, @richkadel wrote:

Do we need counters on edges if we're only interested in line segment coverage?

Edge counters exist so they can be operands in expressions, and since they don't have a code region, they would not be referenced directly by a code region in a report; but the expression might, and that's we we need them.

Edge counters help my understanding of the following example I had posted earlier. Here, counters #2-#6 are presumably edge counters.

Counter in file 0 520:20 -> 520:21, #1
Counter in file 0 520:24 -> 520:25, (#6 + ((((#5 + #4) + #3) + #2) + (#1 - (#6 + (#5 + (#4 + (#3 + #2)))))))

My question was based o the following strategy: use one counter per region and then attempt to reduce the number of counters using counter expressions. Does using edge counters result in fewer counters compared to the above strategy? It's entirely possible I'm missing some knowledge about Rust semantics that requires edge counters.

The above example, even if we account for your Rust FE fix to remove the reserved counter #0 breaks the assumption that No. of code regions >= No. of counters. So I feel like this patch would be needed to accommodate this scenario.

As an aside, the counter expression above would reduce to #1 but don't think LLVM or the FE can simplify this.

(I don't think "line coverage" is a factor. The coverage map only concerns itself with the regions. If the region happens to have one or more newlines, or if there are multiple regions on a line, that isn't relevant to the coverage map; at least not for Rust. llvm-cov computes line coverages when generating the report.)

I should have used "region coverage" instead of "line segment coverage" in my original question.

[richkadel]

An "edge counter", as I'm calling it, is a counter (not an expression). It gets converted into a call to the instrprof.increment intrinsic (so there is executable code behind it), but there is no source code represented by that count.

I don't think this is unique to Rust, but I'm not sure how quickly I can come up with an example in code. From a CFG perspective:

  B
 / \
C   D

We can use an expression to compute the count for one of the branches:

D = B - C

But that assumes C is only reached by B.

Consider a loop. The block inside the loop is reached via 2 or more edges: 1) from above the loop; 2) from the bottom of the loop (the backedge); and maybe from one or more continue statements.

So you can have something like this:

A   B
 \ / \
  C   D

Now the previous expression won't work.

I could count D, and then compute:

C = A + (B - D)

But this isn't always possible or practical (from my experience).

But if I create a counter that counts the edge B->C, I can do this:

C = A + B->C
D = B - B->C

The B->C edge counter is an actual instrprof.increment counter in the LLVM IR, and it represents part of the control flow of the program, but there is no way to tie that to a code region, and it wouldn't be useful in a report. The counters/regions that USE the edge counter are what you want to know.

[vsk]

Just so I'm clear, are you saying that every Counter and Expression generated is guaranteed to be added to the coverage map (so there are no index gaps), even if the counter is part of an unreachable (and therefore eliminated) branch/block?

Yes, that's traditionally how we've done it. For example, in clang, we walk the function AST, prepare all the requisite counters & expressions, and emit an immutable coverage mapping into the llvm IR all before optimization begins:

// CodeGenPGO::assignRegionCounters
mapRegionCounters(D);
if (CGM.getCodeGenOpts().CoverageMapping)
  emitCounterRegionMapping(D);

And, if so, I assume it's OK for a dead branch/block to be eliminated (so the instrprof.increment call for that branch's counter is never added.) But even if the code to increment that counter is not in the code, the coverage map includes the counter. Right?

Yes, exactly. So long as a single instrprof.increment call within a function survives optimization, the profile will contain a full set of region counts for the function. If no instrprof.increment calls survive optimization, llvm behaves as if each counter referenced by the function's coverage mapping is 0.

I recently added support for reporting code regions for dead blocks, but I am replacing them with Zero counters. If I'm understanding you correctly, then I may be able to just retain the original counter id and/or expression and add them to the map instead of converting them to Zero counters, and therefore meet your expectations.

That sounds right. The expectation is that either the profile will contain a 0 count for the dead region/block, or (if the profile record is missing) llvm will infer that the entire function is dead. But this doesn't require any changes to the coverage mapping itself.

And the assertion error message needs to explain the problem (something like, "non-contiguous counter IDs are not allowed")

Right, I might suggest assert(getMaxCounterID(...) < Record.MappingRegions.size() && "Didn't expect to see more regions-with-counters than regions").

Also, I want to confirm that it is OK to have counters that are incremented (via instrprof.increment intrinsic) that are not associated with a code region.

Ah, interesting! I think that is OK. However it does mean that the assert written above is broken, and that we'd want llvm to become more permissive (along the line of @pirama's patch).

(An aside: maybe this is only of historical interest, but I suspect it's somewhat of an accident that this works at all. As far as I know, it was always assumed that each counter was associated with a specific ::CodeRegion.)

I don't think dispensing with the assert is a big loss. The alternative would be to have the FE create a special CounterMappingRegion::EdgeRegion every time it creates a counter that otherwise wouldn't have a region; this would be wasteful unless the extra regions would actually be used.

I'm not sure what clang or swiftc does, but in the Rust FE, I sometimes need to count edges between nodes in the CFG (branches taken, between two blocks) since the target block can be executed from multiple incoming edges

Clang recently picked up branch coverage support via (among other format changes) CoverageMappingRegion::BranchRegion. @alanphipps is the expert on this. Prior to Alan's change, clang simply didn't support branch/edge coverage.

Edge counters exist so they can be operands in expressions, and since they don't have a code region, they would not be referenced directly by a code region in a report; but the expression might, and that's we we need them.

Thanks for sharing the example. For context, in clang, when there's a block of code that has multiple entry points, we either assign a fresh counter to that block or come up with a workable counter expression purely in terms of other block counts. That's not to say it's not useful or valid to use edge counters instead, though.

[richkadel]

OK, great. Thanks for confirming this!

[vsk]

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

196

I'm not sure how this case can arise. Would it be preferable to assert C.getExpressionID() < Expressions.size() instead?

llvm/unittests/ProfileData/CoverageMappingTest.cpp

805

A bit of a nit, but: based on our discussion it seems like we want to allow counters to not be associated with code regions. That's not necessarily the same as allowing non-contiguous counter ID's (although it's fine that this patch does that).

I think it'd be helpful for the comments / test case name to reflect the former (maybe something like 'non_code_region_counter'): that'd leave the door open to disallowing non-contiguous counter ID's down the line.

819

It would tighten the test up to check that the first FunctionRecord has a .CountedRegions field with the expected size.

[pirama]

Tighten and reword test. Also fix lint suggestion.

[pirama]

Thanks for the detail about the edge counters @richkadel.

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

196

I mirrorred CounterMappingContext::evaluate() above, which implies this case could happen. Not sure if an assert is needed here since evaluate() would report an error anyway.

[vsk]

Thanks, lgtm.

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

public:
   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
 
   void dump(const Counter &C, raw_ostream &OS) const;
   void dump(const Counter &C) const { dump(C, dbgs()); }
 
   /// Return the number of times that a region of code associated with this
   /// counter was executed.
   Expected<int64_t> evaluate(const Counter &C) const;
+
+  unsigned getMaxCounterID(const Counter &C) const;
 };
 
 /// Code coverage information for a single function.
 struct FunctionRecord {
   /// Raw function name.
   std::string Name;
   /// Mapping from FileID (i.e. vector index) to filename. Used to support
   /// macro expansions within a function in which the macro and function are

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

case Counter::Expression: {
     if (!RHS)
       return RHS;
     return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
   }
   }
   llvm_unreachable("Unhandled CounterKind");
 }
 
+unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
+  switch (C.getKind()) {
+  case Counter::Zero:
+    return 0;
+  case Counter::CounterValueReference:
+    return C.getCounterID();
+  case Counter::Expression: {
+    if (C.getExpressionID() >= Expressions.size())
+      return 0;
+    const auto &E = Expressions[C.getExpressionID()];
+    return std::max(getMaxCounterID(E.LHS), getMaxCounterID(E.RHS));
+  }
+  }
+  llvm_unreachable("Unhandled CounterKind");
+}
+
 void FunctionRecordIterator::skipOtherFiles() {
   while (Current != Records.end() && !Filename.empty() &&
          Filename != Current->Filenames[0])
     ++Current;
   if (Current == Records.end())
     *this = FunctionRecordIterator();
 }
 
 ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(
     StringRef Filename) const {
   size_t FilenameHash = hash_value(Filename);
   auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);
   if (RecordIt == FilenameHash2RecordIndices.end())
     return {};
   return RecordIt->second;
 }
 
+static unsigned getMaxCounterID(const CounterMappingContext &Ctx,
+                                const CoverageMappingRecord &Record) {
+  unsigned maxCounterID = 0;
+  for (const auto &Region : Record.MappingRegions) {
+    maxCounterID = std::max(maxCounterID, Ctx.getMaxCounterID(Region.Count));
+  }
+  return maxCounterID;
+}
+
 Error CoverageMapping::loadFunctionRecord(
     const CoverageMappingRecord &Record,
     IndexedInstrProfReader &ProfileReader) {
   StringRef OrigFuncName = Record.FunctionName;
   if (OrigFuncName.empty())
     return make_error<CoverageMapError>(coveragemap_error::malformed);
 
   if (Record.Filenames.empty())
     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
   else
     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
 
   CounterMappingContext Ctx(Record.Expressions);
 
   std::vector<uint64_t> Counts;
   if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
                                                 Record.FunctionHash, Counts)) {
     instrprof_error IPE = InstrProfError::take(std::move(E));
     if (IPE == instrprof_error::hash_mismatch) {
       FuncHashMismatches.emplace_back(std::string(Record.FunctionName),
                                       Record.FunctionHash);
       return Error::success();
     } else if (IPE != instrprof_error::unknown_function)
       return make_error<InstrProfError>(IPE);
-    Counts.assign(Record.MappingRegions.size(), 0);
+    Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);
   }
   Ctx.setCounts(Counts);
 
   assert(!Record.MappingRegions.empty() && "Function has no regions");
 
   // This coverage record is a zero region for a function that's unused in
   // some TU, but used in a different TU. Ignore it. The coverage maps from the
   // the other TU will either be loaded (providing full region counts) or they

llvm/unittests/ProfileData/CoverageMappingTest.cpp

 
 namespace {
 
 struct OutputFunctionCoverageData {
   StringRef Name;
   uint64_t Hash;
   std::vector<StringRef> Filenames;
   std::vector<CounterMappingRegion> Regions;
+  std::vector<CounterExpression> Expressions;
 
   OutputFunctionCoverageData() : Hash(0) {}
 
   OutputFunctionCoverageData(OutputFunctionCoverageData &&OFCD)
       : Name(OFCD.Name), Hash(OFCD.Hash), Filenames(std::move(OFCD.Filenames)),
         Regions(std::move(OFCD.Regions)) {}
 
   OutputFunctionCoverageData(const OutputFunctionCoverageData &) = delete;
   OutputFunctionCoverageData &
   operator=(const OutputFunctionCoverageData &) = delete;
   OutputFunctionCoverageData &operator=(OutputFunctionCoverageData &&) = delete;
 
   void fillCoverageMappingRecord(CoverageMappingRecord &Record) const {
     Record.FunctionName = Name;
     Record.FunctionHash = Hash;
     Record.Filenames = Filenames;
-    Record.Expressions = {};
+    Record.Expressions = Expressions;
     Record.MappingRegions = Regions;
   }
 };
 
 struct CoverageMappingReaderMock : CoverageMappingReader {
   ArrayRef<OutputFunctionCoverageData> Functions;
 
   CoverageMappingReaderMock(ArrayRef<OutputFunctionCoverageData> Functions)
struct InputFunctionCoverageData {
   // global file indexes here because local indexes have to be dense.
   // This map is used during serialization to create the virtual file mapping
   // (from local fileId to global Index) in the head of the per-function
   // coverage mapping data.
   SmallDenseMap<unsigned, unsigned> ReverseVirtualFileMapping;
   std::string Name;
   uint64_t Hash;
   std::vector<CounterMappingRegion> Regions;
+  std::vector<CounterExpression> Expressions;
 
   InputFunctionCoverageData(std::string Name, uint64_t Hash)
       : Name(std::move(Name)), Hash(Hash) {}
 
   InputFunctionCoverageData(InputFunctionCoverageData &&IFCD)
       : ReverseVirtualFileMapping(std::move(IFCD.ReverseVirtualFileMapping)),
         Name(std::move(IFCD.Name)), Hash(IFCD.Hash),
         Regions(std::move(IFCD.Regions)) {}
struct CoverageMappingTest : ::testing::TestWithParam<std::pair<bool, bool>> {
 
   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));
   }
 
+  void addExpression(CounterExpression CE) {
+    InputFunctions.back().Expressions.push_back(CE);
+  }
+
   std::string writeCoverageRegions(InputFunctionCoverageData &Data) {
     SmallVector<unsigned, 8> FileIDs(Data.ReverseVirtualFileMapping.size());
     for (const auto &E : Data.ReverseVirtualFileMapping)
       FileIDs[E.second] = E.first;
     std::string Coverage;
     llvm::raw_string_ostream OS(Coverage);
-    CoverageMappingWriter(FileIDs, None, Data.Regions).write(OS);
+    CoverageMappingWriter(FileIDs, Data.Expressions, Data.Regions).write(OS);
     return OS.str();
   }
 
   void readCoverageRegions(const std::string &Coverage,
                            OutputFunctionCoverageData &Data) {
     // We will re-use the StringRef in duplicate tests, clear it to avoid
     // clobber previous ones.
     Filenames.clear();
     Filenames.resize(Files.size() + 1);
     for (const auto &E : Files)
       Filenames[E.getValue()] = E.getKey().str();
-    std::vector<CounterExpression> Expressions;
     ArrayRef<std::string> FilenameRefs = llvm::makeArrayRef(Filenames);
     RawCoverageMappingReader Reader(Coverage, FilenameRefs, Data.Filenames,
-                                    Expressions, Data.Regions);
+                                    Data.Expressions, Data.Regions);
     EXPECT_THAT_ERROR(Reader.read(), Succeeded());
   }
 
   void writeAndReadCoverageRegions(bool EmitFilenames = true) {
     OutputFunctions.resize(InputFunctions.size());
     for (unsigned I = 0; I < InputFunctions.size(); ++I) {
       std::string Regions = writeCoverageRegions(InputFunctions[I]);
       readCoverageRegions(Regions, OutputFunctions[I]);
TEST_P(CoverageMappingTest, combine_expansions) {
   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 that non-contiguous counter ids are handled.
+TEST_P(CoverageMappingTest, non_contiguous_counter_ids) {
+  // No records in profdata
+
+  startFunction("func", 0x1234);
+  addCMR(Counter::getCounter(0), "file", 1, 1, 5, 5);
+  addCMR(Counter::getExpression(0), "file", 6, 1, 6, 5);
+  addExpression(CounterExpression(CounterExpression::Add,
+                                  Counter::getCounter(10),
+                                  Counter::getCounter(20)));
+
+  EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
+
+  std::vector<std::string> Names;
+  for (const auto &Func : LoadedCoverage->getCoveredFunctions())
+    Names.push_back(Func.Name);
+  ASSERT_EQ(1U, Names.size());
+}
+
 TEST_P(CoverageMappingTest, strip_filename_prefix) {
   ProfileWriter.addRecord({"file1:func", 0x1234, {0}}, Err);
 
   startFunction("file1:func", 0x1234);
   addCMR(Counter::getCounter(0), "file1", 1, 1, 9, 9);
   EXPECT_THAT_ERROR(loadCoverageMapping(), Succeeded());
 
   std::vector<std::string> Names;