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