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
27 using namespace llvm;
28 using namespace coverage;
29
CoverageFilenamesSectionWriter(ArrayRef<std::string> Filenames)30 CoverageFilenamesSectionWriter::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
write(raw_ostream & OS,bool Compress)40 void 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(Filename.size(), 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(arrayRefFromStringRef(FilenamesStr),
55 CompressedStr,
56 compression::zlib::BestSizeCompression);
57
58 // ::= <num-filenames>
59 // <uncompressed-len>
60 // <compressed-len-or-zero>
61 // (<compressed-filenames> | <uncompressed-filenames>)
62 encodeULEB128(Filenames.size(), OS);
63 encodeULEB128(FilenamesStr.size(), OS);
64 encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);
65 OS << (doCompression ? toStringRef(CompressedStr) : StringRef(FilenamesStr));
66 }
67
68 namespace {
69
70 /// Gather only the expressions that are used by the mapping
71 /// regions in this function.
72 class CounterExpressionsMinimizer {
73 ArrayRef<CounterExpression> Expressions;
74 SmallVector<CounterExpression, 16> UsedExpressions;
75 std::vector<unsigned> AdjustedExpressionIDs;
76
77 public:
CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,ArrayRef<CounterMappingRegion> MappingRegions)78 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
79 ArrayRef<CounterMappingRegion> MappingRegions)
80 : Expressions(Expressions) {
81 AdjustedExpressionIDs.resize(Expressions.size(), 0);
82 for (const auto &I : MappingRegions) {
83 mark(I.Count);
84 mark(I.FalseCount);
85 }
86 for (const auto &I : MappingRegions) {
87 gatherUsed(I.Count);
88 gatherUsed(I.FalseCount);
89 }
90 }
91
mark(Counter C)92 void mark(Counter C) {
93 if (!C.isExpression())
94 return;
95 unsigned ID = C.getExpressionID();
96 AdjustedExpressionIDs[ID] = 1;
97 mark(Expressions[ID].LHS);
98 mark(Expressions[ID].RHS);
99 }
100
gatherUsed(Counter C)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(E);
107 gatherUsed(E.LHS);
108 gatherUsed(E.RHS);
109 }
110
getExpressions() const111 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.
adjust(Counter C) const115 Counter adjust(Counter C) const {
116 if (C.isExpression())
117 C = Counter::getExpression(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.
encodeCounter(ArrayRef<CounterExpression> Expressions,Counter C)138 static 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
writeCounter(ArrayRef<CounterExpression> Expressions,Counter C,raw_ostream & OS)149 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
150 raw_ostream &OS) {
151 encodeULEB128(encodeCounter(Expressions, C), OS);
152 }
153
write(raw_ostream & OS)154 void 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(MappingRegions, [](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(VirtualFileMapping.size(), OS);
183 for (const auto &FileID : VirtualFileMapping)
184 encodeULEB128(FileID, OS);
185
186 // Write out the expressions.
187 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
188 auto MinExpressions = Minimizer.getExpressions();
189 encodeULEB128(MinExpressions.size(), OS);
190 for (const auto &E : MinExpressions) {
191 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
192 writeCounter(MinExpressions, Minimizer.adjust(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(RegionCount, OS);
210
211 CurrentFileID = I->FileID;
212 PrevLineStart = 0;
213 }
214 Counter Count = Minimizer.adjust(I->Count);
215 Counter FalseCount = Minimizer.adjust(I->FalseCount);
216 bool ParamsShouldBeNull = true;
217 switch (I->Kind) {
218 case CounterMappingRegion::CodeRegion:
219 case CounterMappingRegion::GapRegion:
220 writeCounter(MinExpressions, 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(EncodedTagExpandedFileID, OS);
234 break;
235 }
236 case CounterMappingRegion::SkippedRegion:
237 assert(Count.isZero());
238 encodeULEB128(unsigned(I->Kind)
239 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
240 OS);
241 break;
242 case CounterMappingRegion::BranchRegion:
243 encodeULEB128(unsigned(I->Kind)
244 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
245 OS);
246 writeCounter(MinExpressions, Count, OS);
247 writeCounter(MinExpressions, FalseCount, OS);
248 break;
249 case CounterMappingRegion::MCDCBranchRegion:
250 encodeULEB128(unsigned(I->Kind)
251 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
252 OS);
253 writeCounter(MinExpressions, Count, OS);
254 writeCounter(MinExpressions, 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(ID1, OS);
263 encodeULEB128(TID1, OS);
264 encodeULEB128(FID1, OS);
265 }
266 break;
267 case CounterMappingRegion::MCDCDecisionRegion:
268 encodeULEB128(unsigned(I->Kind)
269 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
270 OS);
271 {
272 const auto &DecisionParams = I->getDecisionParams();
273 ParamsShouldBeNull = false;
274 encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx), OS);
275 encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions), OS);
276 }
277 break;
278 }
279 assert(I->LineStart >= PrevLineStart);
280 encodeULEB128(I->LineStart - PrevLineStart, OS);
281 encodeULEB128(I->ColumnStart, OS);
282 assert(I->LineEnd >= I->LineStart);
283 encodeULEB128(I->LineEnd - I->LineStart, OS);
284 encodeULEB128(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
write(raw_ostream & OS,TestingFormatVersion Version)294 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {
295 auto ByteSwap = [](uint64_t N) {
296 return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N);
297 };
298
299 // Output a 64bit magic number.
300 auto Magic = ByteSwap(TestingFormatMagic);
301 OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic));
302
303 // Output a 64bit version field.
304 auto VersionLittle = ByteSwap(uint64_t(Version));
305 OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle));
306
307 // Output the ProfileNames data.
308 encodeULEB128(ProfileNamesData.size(), OS);
309 encodeULEB128(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(CoverageMappingData.size(), OS);
316
317 // Coverage mapping data is expected to have an alignment of 8.
318 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
319 OS.write(uint8_t(0));
320 OS << CoverageMappingData;
321
322 // Coverage records data is expected to have an alignment of 8.
323 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
324 OS.write(uint8_t(0));
325 OS << CoverageRecordsData;
326 }
327