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 auto LHSKindKey = getKindKey(LHS.Kind);
178 auto RHSKindKey = getKindKey(RHS.Kind);
179 if (LHSKindKey != RHSKindKey)
180 return LHSKindKey < RHSKindKey;
181
182 // Compares endLoc in descending order,
183 // to prioritize wider Regions with the same startLoc.
184 return LHS.endLoc() > RHS.endLoc();
185 });
186
187 // Write out the fileid -> filename mapping.
188 encodeULEB128(Value: VirtualFileMapping.size(), OS);
189 for (const auto &FileID : VirtualFileMapping)
190 encodeULEB128(Value: FileID, OS);
191
192 // Write out the expressions.
193 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
194 auto MinExpressions = Minimizer.getExpressions();
195 encodeULEB128(Value: MinExpressions.size(), OS);
196 for (const auto &E : MinExpressions) {
197 writeCounter(Expressions: MinExpressions, C: Minimizer.adjust(C: E.LHS), OS);
198 writeCounter(Expressions: MinExpressions, C: Minimizer.adjust(C: E.RHS), OS);
199 }
200
201 // Write out the mapping regions.
202 // Split the regions into subarrays where each region in a
203 // subarray has a fileID which is the index of that subarray.
204 unsigned PrevLineStart = 0;
205 unsigned CurrentFileID = ~0U;
206 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
207 if (I->FileID != CurrentFileID) {
208 // Ensure that all file ids have at least one mapping region.
209 assert(I->FileID == (CurrentFileID + 1));
210 // Find the number of regions with this file id.
211 unsigned RegionCount = 1;
212 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
213 ++RegionCount;
214 // Start a new region sub-array.
215 encodeULEB128(Value: RegionCount, OS);
216
217 CurrentFileID = I->FileID;
218 PrevLineStart = 0;
219 }
220 Counter Count = Minimizer.adjust(C: I->Count);
221 Counter FalseCount = Minimizer.adjust(C: I->FalseCount);
222 bool ParamsShouldBeNull = true;
223 switch (I->Kind) {
224 case CounterMappingRegion::CodeRegion:
225 case CounterMappingRegion::GapRegion:
226 writeCounter(Expressions: MinExpressions, C: Count, OS);
227 break;
228 case CounterMappingRegion::ExpansionRegion: {
229 assert(Count.isZero());
230 assert(I->ExpandedFileID <=
231 (std::numeric_limits<unsigned>::max() >>
232 Counter::EncodingCounterTagAndExpansionRegionTagBits));
233 // Mark an expansion region with a set bit that follows the counter tag,
234 // and pack the expanded file id into the remaining bits.
235 unsigned EncodedTagExpandedFileID =
236 (1 << Counter::EncodingTagBits) |
237 (I->ExpandedFileID
238 << Counter::EncodingCounterTagAndExpansionRegionTagBits);
239 encodeULEB128(Value: EncodedTagExpandedFileID, OS);
240 break;
241 }
242 case CounterMappingRegion::SkippedRegion:
243 assert(Count.isZero());
244 encodeULEB128(Value: unsigned(I->Kind)
245 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
246 OS);
247 break;
248 case CounterMappingRegion::BranchRegion:
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 break;
255 case CounterMappingRegion::MCDCBranchRegion:
256 encodeULEB128(Value: unsigned(I->Kind)
257 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
258 OS);
259 writeCounter(Expressions: MinExpressions, C: Count, OS);
260 writeCounter(Expressions: MinExpressions, C: FalseCount, OS);
261 {
262 // They are written as internal values plus 1.
263 const auto &BranchParams = I->getBranchParams();
264 ParamsShouldBeNull = false;
265 unsigned ID1 = BranchParams.ID + 1;
266 unsigned TID1 = BranchParams.Conds[true] + 1;
267 unsigned FID1 = BranchParams.Conds[false] + 1;
268 encodeULEB128(Value: ID1, OS);
269 encodeULEB128(Value: TID1, OS);
270 encodeULEB128(Value: FID1, OS);
271 }
272 break;
273 case CounterMappingRegion::MCDCDecisionRegion:
274 encodeULEB128(Value: unsigned(I->Kind)
275 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
276 OS);
277 {
278 const auto &DecisionParams = I->getDecisionParams();
279 ParamsShouldBeNull = false;
280 encodeULEB128(Value: static_cast<unsigned>(DecisionParams.BitmapIdx), OS);
281 encodeULEB128(Value: static_cast<unsigned>(DecisionParams.NumConditions), OS);
282 }
283 break;
284 }
285 assert(I->LineStart >= PrevLineStart);
286 encodeULEB128(Value: I->LineStart - PrevLineStart, OS);
287 encodeULEB128(Value: I->ColumnStart, OS);
288 assert(I->LineEnd >= I->LineStart);
289 encodeULEB128(Value: I->LineEnd - I->LineStart, OS);
290 encodeULEB128(Value: I->ColumnEnd, OS);
291 PrevLineStart = I->LineStart;
292 assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) &&
293 "MCDCParams should be empty");
294 (void)ParamsShouldBeNull;
295 }
296 // Ensure that all file ids have at least one mapping region.
297 assert(CurrentFileID == (VirtualFileMapping.size() - 1));
298}
299
300void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {
301 auto ByteSwap = [](uint64_t N) {
302 return support::endian::byte_swap<uint64_t>(value: N, endian: llvm::endianness::little);
303 };
304
305 // Output a 64bit magic number.
306 auto Magic = ByteSwap(TestingFormatMagic);
307 OS.write(Ptr: reinterpret_cast<char *>(&Magic), Size: sizeof(Magic));
308
309 // Output a 64bit version field.
310 auto VersionLittle = ByteSwap(uint64_t(Version));
311 OS.write(Ptr: reinterpret_cast<char *>(&VersionLittle), Size: sizeof(VersionLittle));
312
313 // Output the ProfileNames data.
314 encodeULEB128(Value: ProfileNamesData.size(), OS);
315 encodeULEB128(Value: ProfileNamesAddr, OS);
316 OS << ProfileNamesData;
317
318 // Version2 adds an extra field to indicate the size of the
319 // CoverageMappingData.
320 if (Version == TestingFormatVersion::Version2)
321 encodeULEB128(Value: CoverageMappingData.size(), OS);
322
323 // Coverage mapping data is expected to have an alignment of 8.
324 for (unsigned Pad = offsetToAlignment(Value: OS.tell(), Alignment: Align(8)); Pad; --Pad)
325 OS.write(C: uint8_t(0));
326 OS << CoverageMappingData;
327
328 // Coverage records data is expected to have an alignment of 8.
329 for (unsigned Pad = offsetToAlignment(Value: OS.tell(), Alignment: Align(8)); Pad; --Pad)
330 OS.write(C: uint8_t(0));
331 OS << CoverageRecordsData;
332}
333