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     switch (I->Kind) {
217     case CounterMappingRegion::CodeRegion:
218     case CounterMappingRegion::GapRegion:
219       writeCounter(MinExpressions, 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(EncodedTagExpandedFileID, OS);
233       break;
234     }
235     case CounterMappingRegion::SkippedRegion:
236       assert(Count.isZero());
237       encodeULEB128(unsigned(I->Kind)
238                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
239                     OS);
240       break;
241     case CounterMappingRegion::BranchRegion:
242       encodeULEB128(unsigned(I->Kind)
243                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
244                     OS);
245       writeCounter(MinExpressions, Count, OS);
246       writeCounter(MinExpressions, FalseCount, OS);
247       break;
248     case CounterMappingRegion::MCDCBranchRegion:
249       encodeULEB128(unsigned(I->Kind)
250                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
251                     OS);
252       writeCounter(MinExpressions, Count, OS);
253       writeCounter(MinExpressions, FalseCount, OS);
254       encodeULEB128(unsigned(I->MCDCParams.ID), OS);
255       encodeULEB128(unsigned(I->MCDCParams.TrueID), OS);
256       encodeULEB128(unsigned(I->MCDCParams.FalseID), OS);
257       break;
258     case CounterMappingRegion::MCDCDecisionRegion:
259       encodeULEB128(unsigned(I->Kind)
260                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
261                     OS);
262       encodeULEB128(unsigned(I->MCDCParams.BitmapIdx), OS);
263       encodeULEB128(unsigned(I->MCDCParams.NumConditions), OS);
264       break;
265     }
266     assert(I->LineStart >= PrevLineStart);
267     encodeULEB128(I->LineStart - PrevLineStart, OS);
268     encodeULEB128(I->ColumnStart, OS);
269     assert(I->LineEnd >= I->LineStart);
270     encodeULEB128(I->LineEnd - I->LineStart, OS);
271     encodeULEB128(I->ColumnEnd, OS);
272     PrevLineStart = I->LineStart;
273   }
274   // Ensure that all file ids have at least one mapping region.
275   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
276 }
277 
write(raw_ostream & OS,TestingFormatVersion Version)278 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {
279   auto ByteSwap = [](uint64_t N) {
280     return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N);
281   };
282 
283   // Output a 64bit magic number.
284   auto Magic = ByteSwap(TestingFormatMagic);
285   OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic));
286 
287   // Output a 64bit version field.
288   auto VersionLittle = ByteSwap(uint64_t(Version));
289   OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle));
290 
291   // Output the ProfileNames data.
292   encodeULEB128(ProfileNamesData.size(), OS);
293   encodeULEB128(ProfileNamesAddr, OS);
294   OS << ProfileNamesData;
295 
296   // Version2 adds an extra field to indicate the size of the
297   // CoverageMappingData.
298   if (Version == TestingFormatVersion::Version2)
299     encodeULEB128(CoverageMappingData.size(), OS);
300 
301   // Coverage mapping data is expected to have an alignment of 8.
302   for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
303     OS.write(uint8_t(0));
304   OS << CoverageMappingData;
305 
306   // Coverage records data is expected to have an alignment of 8.
307   for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
308     OS.write(uint8_t(0));
309   OS << CoverageRecordsData;
310 }
311