CoverageMappingWriter.cpp revision 360784 
1//===- CoverageMappingWriter.cpp - Code coverage mapping writer -----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains support for writing coverage mapping data for
10// instrumentation based coverage.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/Support/LEB128.h"
18#include "llvm/Support/raw_ostream.h"
19#include <algorithm>
20#include <cassert>
21#include <limits>
22#include <vector>
23
24using namespace llvm;
25using namespace coverage;
26
27CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter(
28    ArrayRef<StringRef> Filenames)
29    : Filenames(Filenames) {
30#ifndef NDEBUG
31  StringSet<> NameSet;
32  for (StringRef Name : Filenames)
33    assert(NameSet.insert(Name).second && "Duplicate filename");
34#endif
35}
36
37void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
38  encodeULEB128(Filenames.size(), OS);
39  for (const auto &Filename : Filenames) {
40    encodeULEB128(Filename.size(), OS);
41    OS << Filename;
42  }
43}
44
45namespace {
46
47/// Gather only the expressions that are used by the mapping
48/// regions in this function.
49class CounterExpressionsMinimizer {
50  ArrayRef<CounterExpression> Expressions;
51  SmallVector<CounterExpression, 16> UsedExpressions;
52  std::vector<unsigned> AdjustedExpressionIDs;
53
54public:
55  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
56                              ArrayRef<CounterMappingRegion> MappingRegions)
57      : Expressions(Expressions) {
58    AdjustedExpressionIDs.resize(Expressions.size(), 0);
59    for (const auto &I : MappingRegions)
60      mark(I.Count);
61    for (const auto &I : MappingRegions)
62      gatherUsed(I.Count);
63  }
64
65  void mark(Counter C) {
66    if (!C.isExpression())
67      return;
68    unsigned ID = C.getExpressionID();
69    AdjustedExpressionIDs[ID] = 1;
70    mark(Expressions[ID].LHS);
71    mark(Expressions[ID].RHS);
72  }
73
74  void gatherUsed(Counter C) {
75    if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
76      return;
77    AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
78    const auto &E = Expressions[C.getExpressionID()];
79    UsedExpressions.push_back(E);
80    gatherUsed(E.LHS);
81    gatherUsed(E.RHS);
82  }
83
84  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
85
86  /// Adjust the given counter to correctly transition from the old
87  /// expression ids to the new expression ids.
88  Counter adjust(Counter C) const {
89    if (C.isExpression())
90      C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
91    return C;
92  }
93};
94
95} // end anonymous namespace
96
97/// Encode the counter.
98///
99/// The encoding uses the following format:
100/// Low 2 bits - Tag:
101///   Counter::Zero(0) - A Counter with kind Counter::Zero
102///   Counter::CounterValueReference(1) - A counter with kind
103///     Counter::CounterValueReference
104///   Counter::Expression(2) + CounterExpression::Subtract(0) -
105///     A counter with kind Counter::Expression and an expression
106///     with kind CounterExpression::Subtract
107///   Counter::Expression(2) + CounterExpression::Add(1) -
108///     A counter with kind Counter::Expression and an expression
109///     with kind CounterExpression::Add
110/// Remaining bits - Counter/Expression ID.
111static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
112                              Counter C) {
113  unsigned Tag = unsigned(C.getKind());
114  if (C.isExpression())
115    Tag += Expressions[C.getExpressionID()].Kind;
116  unsigned ID = C.getCounterID();
117  assert(ID <=
118         (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
119  return Tag | (ID << Counter::EncodingTagBits);
120}
121
122static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
123                         raw_ostream &OS) {
124  encodeULEB128(encodeCounter(Expressions, C), OS);
125}
126
127void CoverageMappingWriter::write(raw_ostream &OS) {
128  // Check that we don't have any bogus regions.
129  assert(all_of(MappingRegions,
130                [](const CounterMappingRegion &CMR) {
131                  return CMR.startLoc() <= CMR.endLoc();
132                }) &&
133         "Source region does not begin before it ends");
134
135  // Sort the regions in an ascending order by the file id and the starting
136  // location. Sort by region kinds to ensure stable order for tests.
137  llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,
138                                       const CounterMappingRegion &RHS) {
139    if (LHS.FileID != RHS.FileID)
140      return LHS.FileID < RHS.FileID;
141    if (LHS.startLoc() != RHS.startLoc())
142      return LHS.startLoc() < RHS.startLoc();
143    return LHS.Kind < RHS.Kind;
144  });
145
146  // Write out the fileid -> filename mapping.
147  encodeULEB128(VirtualFileMapping.size(), OS);
148  for (const auto &FileID : VirtualFileMapping)
149    encodeULEB128(FileID, OS);
150
151  // Write out the expressions.
152  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
153  auto MinExpressions = Minimizer.getExpressions();
154  encodeULEB128(MinExpressions.size(), OS);
155  for (const auto &E : MinExpressions) {
156    writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
157    writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
158  }
159
160  // Write out the mapping regions.
161  // Split the regions into subarrays where each region in a
162  // subarray has a fileID which is the index of that subarray.
163  unsigned PrevLineStart = 0;
164  unsigned CurrentFileID = ~0U;
165  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
166    if (I->FileID != CurrentFileID) {
167      // Ensure that all file ids have at least one mapping region.
168      assert(I->FileID == (CurrentFileID + 1));
169      // Find the number of regions with this file id.
170      unsigned RegionCount = 1;
171      for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
172        ++RegionCount;
173      // Start a new region sub-array.
174      encodeULEB128(RegionCount, OS);
175
176      CurrentFileID = I->FileID;
177      PrevLineStart = 0;
178    }
179    Counter Count = Minimizer.adjust(I->Count);
180    switch (I->Kind) {
181    case CounterMappingRegion::CodeRegion:
182    case CounterMappingRegion::GapRegion:
183      writeCounter(MinExpressions, Count, OS);
184      break;
185    case CounterMappingRegion::ExpansionRegion: {
186      assert(Count.isZero());
187      assert(I->ExpandedFileID <=
188             (std::numeric_limits<unsigned>::max() >>
189              Counter::EncodingCounterTagAndExpansionRegionTagBits));
190      // Mark an expansion region with a set bit that follows the counter tag,
191      // and pack the expanded file id into the remaining bits.
192      unsigned EncodedTagExpandedFileID =
193          (1 << Counter::EncodingTagBits) |
194          (I->ExpandedFileID
195           << Counter::EncodingCounterTagAndExpansionRegionTagBits);
196      encodeULEB128(EncodedTagExpandedFileID, OS);
197      break;
198    }
199    case CounterMappingRegion::SkippedRegion:
200      assert(Count.isZero());
201      encodeULEB128(unsigned(I->Kind)
202                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
203                    OS);
204      break;
205    }
206    assert(I->LineStart >= PrevLineStart);
207    encodeULEB128(I->LineStart - PrevLineStart, OS);
208    encodeULEB128(I->ColumnStart, OS);
209    assert(I->LineEnd >= I->LineStart);
210    encodeULEB128(I->LineEnd - I->LineStart, OS);
211    encodeULEB128(I->ColumnEnd, OS);
212    PrevLineStart = I->LineStart;
213  }
214  // Ensure that all file ids have at least one mapping region.
215  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
216}
217