LLVM 17.0.0git
CoverageMappingWriter.cpp
Go to the documentation of this file.
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
16#include "llvm/ADT/ArrayRef.h"
19#include "llvm/Support/LEB128.h"
21#include <algorithm>
22#include <cassert>
23#include <limits>
24#include <vector>
25
26using namespace llvm;
27using namespace coverage;
28
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
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 SmallVector<uint8_t, 128> CompressedStr;
50 bool doCompression = Compress && compression::zlib::isAvailable() &&
52 if (doCompression)
53 compression::zlib::compress(arrayRefFromStringRef(FilenamesStr),
54 CompressedStr,
56
57 // ::= <num-filenames>
58 // <uncompressed-len>
59 // <compressed-len-or-zero>
60 // (<compressed-filenames> | <uncompressed-filenames>)
61 encodeULEB128(Filenames.size(), OS);
62 encodeULEB128(FilenamesStr.size(), OS);
63 encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);
64 OS << (doCompression ? toStringRef(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 {
74 std::vector<unsigned> AdjustedExpressionIDs;
75
76public:
77 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
78 ArrayRef<CounterMappingRegion> MappingRegions)
79 : Expressions(Expressions) {
80 AdjustedExpressionIDs.resize(Expressions.size(), 0);
81 for (const auto &I : MappingRegions) {
82 mark(I.Count);
83 mark(I.FalseCount);
84 }
85 for (const auto &I : MappingRegions) {
86 gatherUsed(I.Count);
87 gatherUsed(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(Expressions[ID].LHS);
97 mark(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(E);
106 gatherUsed(E.LHS);
107 gatherUsed(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(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
149 raw_ostream &OS) {
150 encodeULEB128(encodeCounter(Expressions, C), OS);
151}
152
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(MappingRegions, [](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 return LHS.Kind < RHS.Kind;
170 });
171
172 // Write out the fileid -> filename mapping.
173 encodeULEB128(VirtualFileMapping.size(), OS);
174 for (const auto &FileID : VirtualFileMapping)
175 encodeULEB128(FileID, OS);
176
177 // Write out the expressions.
178 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
179 auto MinExpressions = Minimizer.getExpressions();
180 encodeULEB128(MinExpressions.size(), OS);
181 for (const auto &E : MinExpressions) {
182 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
183 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
184 }
185
186 // Write out the mapping regions.
187 // Split the regions into subarrays where each region in a
188 // subarray has a fileID which is the index of that subarray.
189 unsigned PrevLineStart = 0;
190 unsigned CurrentFileID = ~0U;
191 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
192 if (I->FileID != CurrentFileID) {
193 // Ensure that all file ids have at least one mapping region.
194 assert(I->FileID == (CurrentFileID + 1));
195 // Find the number of regions with this file id.
196 unsigned RegionCount = 1;
197 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
198 ++RegionCount;
199 // Start a new region sub-array.
200 encodeULEB128(RegionCount, OS);
201
202 CurrentFileID = I->FileID;
203 PrevLineStart = 0;
204 }
205 Counter Count = Minimizer.adjust(I->Count);
206 Counter FalseCount = Minimizer.adjust(I->FalseCount);
207 switch (I->Kind) {
210 writeCounter(MinExpressions, Count, OS);
211 break;
213 assert(Count.isZero());
214 assert(I->ExpandedFileID <=
215 (std::numeric_limits<unsigned>::max() >>
217 // Mark an expansion region with a set bit that follows the counter tag,
218 // and pack the expanded file id into the remaining bits.
219 unsigned EncodedTagExpandedFileID =
221 (I->ExpandedFileID
223 encodeULEB128(EncodedTagExpandedFileID, OS);
224 break;
225 }
227 assert(Count.isZero());
228 encodeULEB128(unsigned(I->Kind)
230 OS);
231 break;
233 encodeULEB128(unsigned(I->Kind)
235 OS);
236 writeCounter(MinExpressions, Count, OS);
237 writeCounter(MinExpressions, FalseCount, OS);
238 break;
239 }
240 assert(I->LineStart >= PrevLineStart);
241 encodeULEB128(I->LineStart - PrevLineStart, OS);
242 encodeULEB128(I->ColumnStart, OS);
243 assert(I->LineEnd >= I->LineStart);
244 encodeULEB128(I->LineEnd - I->LineStart, OS);
245 encodeULEB128(I->ColumnEnd, OS);
246 PrevLineStart = I->LineStart;
247 }
248 // Ensure that all file ids have at least one mapping region.
249 assert(CurrentFileID == (VirtualFileMapping.size() - 1));
250}
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static void writeCounter(ArrayRef< CounterExpression > Expressions, Counter C, raw_ostream &OS)
static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)
Encode the counter.
std::string Name
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallVector class.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:23
std::pair< typename Base::iterator, bool > insert(StringRef key)
Definition: StringSet.h:34
void write(raw_ostream &OS, bool Compress=true)
Write encoded filenames to the given output stream.
CoverageFilenamesSectionWriter(ArrayRef< std::string > Filenames)
void write(raw_ostream &OS)
Write encoded coverage mapping data to the given output stream.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
void compress(ArrayRef< uint8_t > Input, SmallVectorImpl< uint8_t > &CompressedBuffer, int Level=DefaultCompression)
constexpr int BestSizeCompression
Definition: Compression.h:39
StringRef toStringRef(const std::optional< DWARFFormValue > &V, StringRef Default={})
Take an optional DWARFFormValue and try to extract a string value from it.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void stable_sort(R &&Range)
Definition: STLExtras.h:2063
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1819
cl::opt< bool > DoInstrProfNameCompression
unsigned encodeULEB128(uint64_t Value, raw_ostream &OS, unsigned PadTo=0)
Utility function to encode a ULEB128 value to an output stream.
Definition: LEB128.h:80
A Counter mapping region associates a source range with a specific counter.
@ ExpansionRegion
An ExpansionRegion represents a file expansion region that associates a source range with the expansi...
@ SkippedRegion
A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...
@ GapRegion
A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...
@ BranchRegion
A BranchRegion represents leaf-level boolean expressions and is associated with two counters,...
@ CodeRegion
A CodeRegion associates some code with a counter.
A Counter is an abstract value that describes how to compute the execution count for a region of code...
static const unsigned EncodingTagBits
static const unsigned EncodingCounterTagAndExpansionRegionTagBits
static Counter getExpression(unsigned ExpressionId)
Return the counter that corresponds to a specific addition counter expression.