LLVM  14.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"
17 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Support/LEB128.h"
21 #include <algorithm>
22 #include <cassert>
23 #include <limits>
24 #include <vector>
25 
26 using namespace llvm;
27 using 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  SmallString<128> CompressedStr;
50  bool doCompression =
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 ? CompressedStr.str() : 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 {
75  SmallVector<CounterExpression, 16> UsedExpressions;
76  std::vector<unsigned> AdjustedExpressionIDs;
77 
78 public:
79  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
80  ArrayRef<CounterMappingRegion> MappingRegions)
82  AdjustedExpressionIDs.resize(Expressions.size(), 0);
83  for (const auto &I : MappingRegions) {
84  mark(I.Count);
85  mark(I.FalseCount);
86  }
87  for (const auto &I : MappingRegions) {
88  gatherUsed(I.Count);
89  gatherUsed(I.FalseCount);
90  }
91  }
92 
93  void mark(Counter C) {
94  if (!C.isExpression())
95  return;
96  unsigned ID = C.getExpressionID();
97  AdjustedExpressionIDs[ID] = 1;
98  mark(Expressions[ID].LHS);
99  mark(Expressions[ID].RHS);
100  }
101 
102  void gatherUsed(Counter C) {
103  if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
104  return;
105  AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
106  const auto &E = Expressions[C.getExpressionID()];
107  UsedExpressions.push_back(E);
108  gatherUsed(E.LHS);
109  gatherUsed(E.RHS);
110  }
111 
112  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
113 
114  /// Adjust the given counter to correctly transition from the old
115  /// expression ids to the new expression ids.
116  Counter adjust(Counter C) const {
117  if (C.isExpression())
118  C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
119  return C;
120  }
121 };
122 
123 } // end anonymous namespace
124 
125 /// Encode the counter.
126 ///
127 /// The encoding uses the following format:
128 /// Low 2 bits - Tag:
129 /// Counter::Zero(0) - A Counter with kind Counter::Zero
130 /// Counter::CounterValueReference(1) - A counter with kind
131 /// Counter::CounterValueReference
132 /// Counter::Expression(2) + CounterExpression::Subtract(0) -
133 /// A counter with kind Counter::Expression and an expression
134 /// with kind CounterExpression::Subtract
135 /// Counter::Expression(2) + CounterExpression::Add(1) -
136 /// A counter with kind Counter::Expression and an expression
137 /// with kind CounterExpression::Add
138 /// Remaining bits - Counter/Expression ID.
140  Counter C) {
141  unsigned Tag = unsigned(C.getKind());
142  if (C.isExpression())
143  Tag += Expressions[C.getExpressionID()].Kind;
144  unsigned ID = C.getCounterID();
145  assert(ID <=
147  return Tag | (ID << Counter::EncodingTagBits);
148 }
149 
151  raw_ostream &OS) {
153 }
154 
156  // Check that we don't have any bogus regions.
157  assert(all_of(MappingRegions,
158  [](const CounterMappingRegion &CMR) {
159  return CMR.startLoc() <= CMR.endLoc();
160  }) &&
161  "Source region does not begin before it ends");
162 
163  // Sort the regions in an ascending order by the file id and the starting
164  // location. Sort by region kinds to ensure stable order for tests.
165  llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,
166  const CounterMappingRegion &RHS) {
167  if (LHS.FileID != RHS.FileID)
168  return LHS.FileID < RHS.FileID;
169  if (LHS.startLoc() != RHS.startLoc())
170  return LHS.startLoc() < RHS.startLoc();
171  return LHS.Kind < RHS.Kind;
172  });
173 
174  // Write out the fileid -> filename mapping.
175  encodeULEB128(VirtualFileMapping.size(), OS);
176  for (const auto &FileID : VirtualFileMapping)
177  encodeULEB128(FileID, OS);
178 
179  // Write out the expressions.
180  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
181  auto MinExpressions = Minimizer.getExpressions();
182  encodeULEB128(MinExpressions.size(), OS);
183  for (const auto &E : MinExpressions) {
184  writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
185  writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
186  }
187 
188  // Write out the mapping regions.
189  // Split the regions into subarrays where each region in a
190  // subarray has a fileID which is the index of that subarray.
191  unsigned PrevLineStart = 0;
192  unsigned CurrentFileID = ~0U;
193  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
194  if (I->FileID != CurrentFileID) {
195  // Ensure that all file ids have at least one mapping region.
196  assert(I->FileID == (CurrentFileID + 1));
197  // Find the number of regions with this file id.
198  unsigned RegionCount = 1;
199  for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
200  ++RegionCount;
201  // Start a new region sub-array.
202  encodeULEB128(RegionCount, OS);
203 
204  CurrentFileID = I->FileID;
205  PrevLineStart = 0;
206  }
207  Counter Count = Minimizer.adjust(I->Count);
208  Counter FalseCount = Minimizer.adjust(I->FalseCount);
209  switch (I->Kind) {
212  writeCounter(MinExpressions, Count, OS);
213  break;
215  assert(Count.isZero());
216  assert(I->ExpandedFileID <=
219  // Mark an expansion region with a set bit that follows the counter tag,
220  // and pack the expanded file id into the remaining bits.
221  unsigned EncodedTagExpandedFileID =
222  (1 << Counter::EncodingTagBits) |
223  (I->ExpandedFileID
225  encodeULEB128(EncodedTagExpandedFileID, OS);
226  break;
227  }
229  assert(Count.isZero());
230  encodeULEB128(unsigned(I->Kind)
232  OS);
233  break;
235  encodeULEB128(unsigned(I->Kind)
237  OS);
238  writeCounter(MinExpressions, Count, OS);
239  writeCounter(MinExpressions, FalseCount, OS);
240  break;
241  }
242  assert(I->LineStart >= PrevLineStart);
243  encodeULEB128(I->LineStart - PrevLineStart, OS);
244  encodeULEB128(I->ColumnStart, OS);
245  assert(I->LineEnd >= I->LineStart);
246  encodeULEB128(I->LineEnd - I->LineStart, OS);
247  encodeULEB128(I->ColumnEnd, OS);
248  PrevLineStart = I->LineStart;
249  }
250  // Ensure that all file ids have at least one mapping region.
251  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
252 }
llvm::coverage::Counter::getExpression
static Counter getExpression(unsigned ExpressionId)
Return the counter that corresponds to a specific addition counter expression.
Definition: CoverageMapping.h:142
writeCounter
static void writeCounter(ArrayRef< CounterExpression > Expressions, Counter C, raw_ostream &OS)
Definition: CoverageMappingWriter.cpp:150
Compression.h
llvm::coverage::Counter::isZero
bool isZero() const
Definition: CoverageMapping.h:112
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::coverage::CounterMappingRegion::endLoc
LineColPair endLoc() const
Definition: CoverageMapping.h:299
llvm::coverage::CounterMappingRegion::FileID
unsigned FileID
Definition: CoverageMapping.h:238
llvm::coverage::CounterMappingRegion
A Counter mapping region associates a source range with a specific counter.
Definition: CoverageMapping.h:208
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:625
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::coverage::CounterMappingRegion::ExpansionRegion
@ ExpansionRegion
An ExpansionRegion represents a file expansion region that associates a source range with the expansi...
Definition: CoverageMapping.h:216
llvm::StringSet::insert
std::pair< typename Base::iterator, bool > insert(StringRef key)
Definition: StringSet.h:33
llvm::coverage::CounterMappingRegion::Kind
RegionKind Kind
Definition: CoverageMapping.h:240
encodeCounter
static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)
Encode the counter.
Definition: CoverageMappingWriter.cpp:139
llvm::all_of
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:1547
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::zlib::BestSizeCompression
static constexpr int BestSizeCompression
Definition: Compression.h:28
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrProf.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::zlib::compress
Error compress(StringRef InputBuffer, SmallVectorImpl< char > &CompressedBuffer, int Level=DefaultCompression)
Definition: Compression.cpp:49
llvm::SmallString< 128 >
llvm::report_bad_alloc_error
void report_bad_alloc_error(const char *Reason, bool GenCrashDiag=true)
Reports a bad alloc error, calling any user defined bad alloc error handler.
Definition: ErrorHandling.cpp:147
LEB128.h
llvm::coverage::CoverageFilenamesSectionWriter::write
void write(raw_ostream &OS, bool Compress=true)
Write encoded filenames to the given output stream.
Definition: CoverageMappingWriter.cpp:39
llvm::coverage::Counter
A Counter is an abstract value that describes how to compute the execution count for a region of code...
Definition: CoverageMapping.h:92
I
#define I(x, y, z)
Definition: MD5.cpp:59
CoverageMappingWriter.h
llvm::coverage::CoverageMappingWriter::write
void write(raw_ostream &OS)
Write encoded coverage mapping data to the given output stream.
Definition: CoverageMappingWriter.cpp:155
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::coverage::CounterMappingRegion::startLoc
LineColPair startLoc() const
Definition: CoverageMapping.h:295
llvm::zlib::isAvailable
bool isAvailable()
Definition: Compression.cpp:47
llvm::coverage::CounterMappingRegion::BranchRegion
@ BranchRegion
A BranchRegion represents leaf-level boolean expressions and is associated with two counters,...
Definition: CoverageMapping.h:229
llvm::coverage::CounterMappingRegion::GapRegion
@ GapRegion
A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...
Definition: CoverageMapping.h:224
llvm::StringSet
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:22
llvm::ArrayRef< std::string >
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::coverage::Counter::EncodingCounterTagAndExpansionRegionTagBits
static const unsigned EncodingCounterTagAndExpansionRegionTagBits
Definition: CoverageMapping.h:98
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::DoInstrProfNameCompression
cl::opt< bool > DoInstrProfNameCompression
adjust
Definition: AVRAsmBackend.cpp:33
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1682
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::SmallString::str
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:259
SmallVector.h
Expressions
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1261
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::encodeULEB128
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
llvm::coverage::CounterMappingRegion::CodeRegion
@ CodeRegion
A CodeRegion associates some code with a counter.
Definition: CoverageMapping.h:211
raw_ostream.h
llvm::coverage::Counter::EncodingTagBits
static const unsigned EncodingTagBits
Definition: CoverageMapping.h:96
llvm::coverage::CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter
CoverageFilenamesSectionWriter(ArrayRef< std::string > Filenames)
Definition: CoverageMappingWriter.cpp:29
llvm::coverage::CounterMappingRegion::SkippedRegion
@ SkippedRegion
A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...
Definition: CoverageMapping.h:220
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37