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/InstrProf.h"
15 #include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/Compression.h"
19 #include "llvm/Support/LEB128.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include <algorithm>
22 #include <cassert>
23 #include <limits>
24 #include <vector>
25 
26 using namespace llvm;
27 using namespace coverage;
28 
29 CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter(
30     ArrayRef<StringRef> 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 
39 void 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(Filename.size(), FilenamesOS);
45       FilenamesOS << Filename;
46     }
47   }
48 
49   SmallString<128> CompressedStr;
50   bool doCompression =
51       Compress && zlib::isAvailable() && DoInstrProfNameCompression;
52   if (doCompression) {
53     auto E =
54         zlib::compress(FilenamesStr, CompressedStr, zlib::BestSizeCompression);
55     if (E)
56       report_bad_alloc_error("Failed to zlib compress coverage data");
57   }
58 
59   // ::= <num-filenames>
60   //     <uncompressed-len>
61   //     <compressed-len-or-zero>
62   //     (<compressed-filenames> | <uncompressed-filenames>)
63   encodeULEB128(Filenames.size(), OS);
64   encodeULEB128(FilenamesStr.size(), OS);
65   encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);
66   OS << (doCompression ? StringRef(CompressedStr) : StringRef(FilenamesStr));
67 }
68 
69 namespace {
70 
71 /// Gather only the expressions that are used by the mapping
72 /// regions in this function.
73 class CounterExpressionsMinimizer {
74   ArrayRef<CounterExpression> Expressions;
75   SmallVector<CounterExpression, 16> UsedExpressions;
76   std::vector<unsigned> AdjustedExpressionIDs;
77 
78 public:
79   CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
80                               ArrayRef<CounterMappingRegion> MappingRegions)
81       : Expressions(Expressions) {
82     AdjustedExpressionIDs.resize(Expressions.size(), 0);
83     for (const auto &I : MappingRegions)
84       mark(I.Count);
85     for (const auto &I : MappingRegions)
86       gatherUsed(I.Count);
87   }
88 
89   void mark(Counter C) {
90     if (!C.isExpression())
91       return;
92     unsigned ID = C.getExpressionID();
93     AdjustedExpressionIDs[ID] = 1;
94     mark(Expressions[ID].LHS);
95     mark(Expressions[ID].RHS);
96   }
97 
98   void gatherUsed(Counter C) {
99     if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
100       return;
101     AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
102     const auto &E = Expressions[C.getExpressionID()];
103     UsedExpressions.push_back(E);
104     gatherUsed(E.LHS);
105     gatherUsed(E.RHS);
106   }
107 
108   ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
109 
110   /// Adjust the given counter to correctly transition from the old
111   /// expression ids to the new expression ids.
112   Counter adjust(Counter C) const {
113     if (C.isExpression())
114       C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
115     return C;
116   }
117 };
118 
119 } // end anonymous namespace
120 
121 /// Encode the counter.
122 ///
123 /// The encoding uses the following format:
124 /// Low 2 bits - Tag:
125 ///   Counter::Zero(0) - A Counter with kind Counter::Zero
126 ///   Counter::CounterValueReference(1) - A counter with kind
127 ///     Counter::CounterValueReference
128 ///   Counter::Expression(2) + CounterExpression::Subtract(0) -
129 ///     A counter with kind Counter::Expression and an expression
130 ///     with kind CounterExpression::Subtract
131 ///   Counter::Expression(2) + CounterExpression::Add(1) -
132 ///     A counter with kind Counter::Expression and an expression
133 ///     with kind CounterExpression::Add
134 /// Remaining bits - Counter/Expression ID.
135 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
136                               Counter C) {
137   unsigned Tag = unsigned(C.getKind());
138   if (C.isExpression())
139     Tag += Expressions[C.getExpressionID()].Kind;
140   unsigned ID = C.getCounterID();
141   assert(ID <=
142          (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
143   return Tag | (ID << Counter::EncodingTagBits);
144 }
145 
146 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
147                          raw_ostream &OS) {
148   encodeULEB128(encodeCounter(Expressions, C), OS);
149 }
150 
151 void CoverageMappingWriter::write(raw_ostream &OS) {
152   // Check that we don't have any bogus regions.
153   assert(all_of(MappingRegions,
154                 [](const CounterMappingRegion &CMR) {
155                   return CMR.startLoc() <= CMR.endLoc();
156                 }) &&
157          "Source region does not begin before it ends");
158 
159   // Sort the regions in an ascending order by the file id and the starting
160   // location. Sort by region kinds to ensure stable order for tests.
161   llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,
162                                        const CounterMappingRegion &RHS) {
163     if (LHS.FileID != RHS.FileID)
164       return LHS.FileID < RHS.FileID;
165     if (LHS.startLoc() != RHS.startLoc())
166       return LHS.startLoc() < RHS.startLoc();
167     return LHS.Kind < RHS.Kind;
168   });
169 
170   // Write out the fileid -> filename mapping.
171   encodeULEB128(VirtualFileMapping.size(), OS);
172   for (const auto &FileID : VirtualFileMapping)
173     encodeULEB128(FileID, OS);
174 
175   // Write out the expressions.
176   CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
177   auto MinExpressions = Minimizer.getExpressions();
178   encodeULEB128(MinExpressions.size(), OS);
179   for (const auto &E : MinExpressions) {
180     writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
181     writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
182   }
183 
184   // Write out the mapping regions.
185   // Split the regions into subarrays where each region in a
186   // subarray has a fileID which is the index of that subarray.
187   unsigned PrevLineStart = 0;
188   unsigned CurrentFileID = ~0U;
189   for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
190     if (I->FileID != CurrentFileID) {
191       // Ensure that all file ids have at least one mapping region.
192       assert(I->FileID == (CurrentFileID + 1));
193       // Find the number of regions with this file id.
194       unsigned RegionCount = 1;
195       for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
196         ++RegionCount;
197       // Start a new region sub-array.
198       encodeULEB128(RegionCount, OS);
199 
200       CurrentFileID = I->FileID;
201       PrevLineStart = 0;
202     }
203     Counter Count = Minimizer.adjust(I->Count);
204     switch (I->Kind) {
205     case CounterMappingRegion::CodeRegion:
206     case CounterMappingRegion::GapRegion:
207       writeCounter(MinExpressions, Count, OS);
208       break;
209     case CounterMappingRegion::ExpansionRegion: {
210       assert(Count.isZero());
211       assert(I->ExpandedFileID <=
212              (std::numeric_limits<unsigned>::max() >>
213               Counter::EncodingCounterTagAndExpansionRegionTagBits));
214       // Mark an expansion region with a set bit that follows the counter tag,
215       // and pack the expanded file id into the remaining bits.
216       unsigned EncodedTagExpandedFileID =
217           (1 << Counter::EncodingTagBits) |
218           (I->ExpandedFileID
219            << Counter::EncodingCounterTagAndExpansionRegionTagBits);
220       encodeULEB128(EncodedTagExpandedFileID, OS);
221       break;
222     }
223     case CounterMappingRegion::SkippedRegion:
224       assert(Count.isZero());
225       encodeULEB128(unsigned(I->Kind)
226                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
227                     OS);
228       break;
229     }
230     assert(I->LineStart >= PrevLineStart);
231     encodeULEB128(I->LineStart - PrevLineStart, OS);
232     encodeULEB128(I->ColumnStart, OS);
233     assert(I->LineEnd >= I->LineStart);
234     encodeULEB128(I->LineEnd - I->LineStart, OS);
235     encodeULEB128(I->ColumnEnd, OS);
236     PrevLineStart = I->LineStart;
237   }
238   // Ensure that all file ids have at least one mapping region.
239   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
240 }
241