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/ADT/StringExtras.h"
18#include "llvm/ProfileData/InstrProf.h"
19#include "llvm/Support/Compression.h"
20#include "llvm/Support/LEB128.h"
21#include "llvm/Support/raw_ostream.h"
22#include <cassert>
23#include <limits>
24#include <vector>
25
26using namespace llvm;
27using namespace coverage;
28
29CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter(
30 ArrayRef<std::string> Filenames)
31 : Filenames(Filenames) {
32#ifndef NDEBUG
33 StringSet<> NameSet;
34 for (StringRef Name : Filenames)
35 assert(NameSet.insert(Name).second && "Duplicate filename");
36#endif
37}
38
39void CoverageFilenamesSectionWriter::write(raw_ostream &OS, bool Compress) {
40 std::string FilenamesStr;
41 {
42 raw_string_ostream FilenamesOS{FilenamesStr};
43 for (const auto &Filename : Filenames) {
44 encodeULEB128(Value: Filename.size(), OS&: FilenamesOS);
45 FilenamesOS << Filename;
46 }
47 }
48
49 SmallVector<uint8_t, 128> CompressedStr;
50 bool doCompression = Compress && compression::zlib::isAvailable() &&
51 DoInstrProfNameCompression;
52 if (doCompression)
53 compression::zlib::compress(Input: arrayRefFromStringRef(Input: FilenamesStr),
54 CompressedBuffer&: CompressedStr,
55 Level: compression::zlib::BestSizeCompression);
56
57 // ::= <num-filenames>
58 // <uncompressed-len>
59 // <compressed-len-or-zero>
60 // (<compressed-filenames> | <uncompressed-filenames>)
61 encodeULEB128(Value: Filenames.size(), OS);
62 encodeULEB128(Value: FilenamesStr.size(), OS);
63 encodeULEB128(Value: doCompression ? CompressedStr.size() : 0U, OS);
64 OS << (doCompression ? toStringRef(Input: CompressedStr) : StringRef(FilenamesStr));
65}
66
67namespace {
68
69/// Gather only the expressions that are used by the mapping
70/// regions in this function.
71class CounterExpressionsMinimizer {
72 ArrayRef<CounterExpression> Expressions;
73 SmallVector<CounterExpression, 16> UsedExpressions;
74 std::vector<unsigned> AdjustedExpressionIDs;
75
76public:
77 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
78 ArrayRef<CounterMappingRegion> MappingRegions)
79 : Expressions(Expressions) {
80 AdjustedExpressionIDs.resize(new_size: Expressions.size(), x: 0);
81 for (const auto &I : MappingRegions) {
82 mark(C: I.Count);
83 mark(C: I.FalseCount);
84 }
85 for (const auto &I : MappingRegions) {
86 gatherUsed(C: I.Count);
87 gatherUsed(C: I.FalseCount);
88 }
89 }
90
91 void mark(Counter C) {
92 if (!C.isExpression())
93 return;
94 unsigned ID = C.getExpressionID();
95 AdjustedExpressionIDs[ID] = 1;
96 mark(C: Expressions[ID].LHS);
97 mark(C: Expressions[ID].RHS);
98 }
99
100 void gatherUsed(Counter C) {
101 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
102 return;
103 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
104 const auto &E = Expressions[C.getExpressionID()];
105 UsedExpressions.push_back(Elt: E);
106 gatherUsed(C: E.LHS);
107 gatherUsed(C: E.RHS);
108 }
109
110 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
111
112 /// Adjust the given counter to correctly transition from the old
113 /// expression ids to the new expression ids.
114 Counter adjust(Counter C) const {
115 if (C.isExpression())
116 C = Counter::getExpression(ExpressionId: AdjustedExpressionIDs[C.getExpressionID()]);
117 return C;
118 }
119};
120
121} // end anonymous namespace
122
123/// Encode the counter.
124///
125/// The encoding uses the following format:
126/// Low 2 bits - Tag:
127/// Counter::Zero(0) - A Counter with kind Counter::Zero
128/// Counter::CounterValueReference(1) - A counter with kind
129/// Counter::CounterValueReference
130/// Counter::Expression(2) + CounterExpression::Subtract(0) -
131/// A counter with kind Counter::Expression and an expression
132/// with kind CounterExpression::Subtract
133/// Counter::Expression(2) + CounterExpression::Add(1) -
134/// A counter with kind Counter::Expression and an expression
135/// with kind CounterExpression::Add
136/// Remaining bits - Counter/Expression ID.
137static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
138 Counter C) {
139 unsigned Tag = unsigned(C.getKind());
140 if (C.isExpression())
141 Tag += Expressions[C.getExpressionID()].Kind;
142 unsigned ID = C.getCounterID();
143 assert(ID <=
144 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
145 return Tag | (ID << Counter::EncodingTagBits);
146}
147
148static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
149 raw_ostream &OS) {
150 encodeULEB128(Value: encodeCounter(Expressions, C), OS);
151}
152
153void CoverageMappingWriter::write(raw_ostream &OS) {
154 // Check that we don't have any bogus regions.
155 assert(all_of(MappingRegions,
156 [](const CounterMappingRegion &CMR) {
157 return CMR.startLoc() <= CMR.endLoc();
158 }) &&
159 "Source region does not begin before it ends");
160
161 // Sort the regions in an ascending order by the file id and the starting
162 // location. Sort by region kinds to ensure stable order for tests.
163 llvm::stable_sort(Range&: MappingRegions, C: [](const CounterMappingRegion &LHS,
164 const CounterMappingRegion &RHS) {
165 if (LHS.FileID != RHS.FileID)
166 return LHS.FileID < RHS.FileID;
167 if (LHS.startLoc() != RHS.startLoc())
168 return LHS.startLoc() < RHS.startLoc();
169
170 // Put `Decision` before `Expansion`.
171 auto getKindKey = [](CounterMappingRegion::RegionKind Kind) {
172 return (Kind == CounterMappingRegion::MCDCDecisionRegion
173 ? 2 * CounterMappingRegion::ExpansionRegion - 1
174 : 2 * Kind);
175 };
176
177 return getKindKey(LHS.Kind) < getKindKey(RHS.Kind);
178 });
179
180 // Write out the fileid -> filename mapping.
181 encodeULEB128(Value: VirtualFileMapping.size(), OS);
182 for (const auto &FileID : VirtualFileMapping)
183 encodeULEB128(Value: FileID, OS);
184
185 // Write out the expressions.
186 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
187 auto MinExpressions = Minimizer.getExpressions();
188 encodeULEB128(Value: MinExpressions.size(), OS);
189 for (const auto &E : MinExpressions) {
190 writeCounter(Expressions: MinExpressions, C: Minimizer.adjust(C: E.LHS), OS);
191 writeCounter(Expressions: MinExpressions, C: Minimizer.adjust(C: E.RHS), OS);
192 }
193
194 // Write out the mapping regions.
195 // Split the regions into subarrays where each region in a
196 // subarray has a fileID which is the index of that subarray.
197 unsigned PrevLineStart = 0;
198 unsigned CurrentFileID = ~0U;
199 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
200 if (I->FileID != CurrentFileID) {
201 // Ensure that all file ids have at least one mapping region.
202 assert(I->FileID == (CurrentFileID + 1));
203 // Find the number of regions with this file id.
204 unsigned RegionCount = 1;
205 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
206 ++RegionCount;
207 // Start a new region sub-array.
208 encodeULEB128(Value: RegionCount, OS);
209
210 CurrentFileID = I->FileID;
211 PrevLineStart = 0;
212 }
213 Counter Count = Minimizer.adjust(C: I->Count);
214 Counter FalseCount = Minimizer.adjust(C: I->FalseCount);
215 bool ParamsShouldBeNull = true;
216 switch (I->Kind) {
217 case CounterMappingRegion::CodeRegion:
218 case CounterMappingRegion::GapRegion:
219 writeCounter(Expressions: MinExpressions, C: Count, OS);
220 break;
221 case CounterMappingRegion::ExpansionRegion: {
222 assert(Count.isZero());
223 assert(I->ExpandedFileID <=
224 (std::numeric_limits<unsigned>::max() >>
225 Counter::EncodingCounterTagAndExpansionRegionTagBits));
226 // Mark an expansion region with a set bit that follows the counter tag,
227 // and pack the expanded file id into the remaining bits.
228 unsigned EncodedTagExpandedFileID =
229 (1 << Counter::EncodingTagBits) |
230 (I->ExpandedFileID
231 << Counter::EncodingCounterTagAndExpansionRegionTagBits);
232 encodeULEB128(Value: EncodedTagExpandedFileID, OS);
233 break;
234 }
235 case CounterMappingRegion::SkippedRegion:
236 assert(Count.isZero());
237 encodeULEB128(Value: unsigned(I->Kind)
238 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
239 OS);
240 break;
241 case CounterMappingRegion::BranchRegion:
242 encodeULEB128(Value: unsigned(I->Kind)
243 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
244 OS);
245 writeCounter(Expressions: MinExpressions, C: Count, OS);
246 writeCounter(Expressions: MinExpressions, C: FalseCount, OS);
247 break;
248 case CounterMappingRegion::MCDCBranchRegion:
249 encodeULEB128(Value: unsigned(I->Kind)
250 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
251 OS);
252 writeCounter(Expressions: MinExpressions, C: Count, OS);
253 writeCounter(Expressions: MinExpressions, C: FalseCount, OS);
254 {
255 // They are written as internal values plus 1.
256 const auto &BranchParams = I->getBranchParams();
257 ParamsShouldBeNull = false;
258 unsigned ID1 = BranchParams.ID + 1;
259 unsigned TID1 = BranchParams.Conds[true] + 1;
260 unsigned FID1 = BranchParams.Conds[false] + 1;
261 encodeULEB128(Value: ID1, OS);
262 encodeULEB128(Value: TID1, OS);
263 encodeULEB128(Value: FID1, OS);
264 }
265 break;
266 case CounterMappingRegion::MCDCDecisionRegion:
267 encodeULEB128(Value: unsigned(I->Kind)
268 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
269 OS);
270 {
271 const auto &DecisionParams = I->getDecisionParams();
272 ParamsShouldBeNull = false;
273 encodeULEB128(Value: static_cast<unsigned>(DecisionParams.BitmapIdx), OS);
274 encodeULEB128(Value: static_cast<unsigned>(DecisionParams.NumConditions), OS);
275 }
276 break;
277 }
278 assert(I->LineStart >= PrevLineStart);
279 encodeULEB128(Value: I->LineStart - PrevLineStart, OS);
280 encodeULEB128(Value: I->ColumnStart, OS);
281 assert(I->LineEnd >= I->LineStart);
282 encodeULEB128(Value: I->LineEnd - I->LineStart, OS);
283 encodeULEB128(Value: I->ColumnEnd, OS);
284 PrevLineStart = I->LineStart;
285 assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) &&
286 "MCDCParams should be empty");
287 (void)ParamsShouldBeNull;
288 }
289 // Ensure that all file ids have at least one mapping region.
290 assert(CurrentFileID == (VirtualFileMapping.size() - 1));
291}
292
293void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {
294 auto ByteSwap = [](uint64_t N) {
295 return support::endian::byte_swap<uint64_t, llvm::endianness::little>(value: N);
296 };
297
298 // Output a 64bit magic number.
299 auto Magic = ByteSwap(TestingFormatMagic);
300 OS.write(Ptr: reinterpret_cast<char *>(&Magic), Size: sizeof(Magic));
301
302 // Output a 64bit version field.
303 auto VersionLittle = ByteSwap(uint64_t(Version));
304 OS.write(Ptr: reinterpret_cast<char *>(&VersionLittle), Size: sizeof(VersionLittle));
305
306 // Output the ProfileNames data.
307 encodeULEB128(Value: ProfileNamesData.size(), OS);
308 encodeULEB128(Value: ProfileNamesAddr, OS);
309 OS << ProfileNamesData;
310
311 // Version2 adds an extra field to indicate the size of the
312 // CoverageMappingData.
313 if (Version == TestingFormatVersion::Version2)
314 encodeULEB128(Value: CoverageMappingData.size(), OS);
315
316 // Coverage mapping data is expected to have an alignment of 8.
317 for (unsigned Pad = offsetToAlignment(Value: OS.tell(), Alignment: Align(8)); Pad; --Pad)
318 OS.write(C: uint8_t(0));
319 OS << CoverageMappingData;
320
321 // Coverage records data is expected to have an alignment of 8.
322 for (unsigned Pad = offsetToAlignment(Value: OS.tell(), Alignment: Align(8)); Pad; --Pad)
323 OS.write(C: uint8_t(0));
324 OS << CoverageRecordsData;
325}
326