LLVM  15.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  zlib::compress(FilenamesStr, CompressedStr, zlib::BestSizeCompression);
54 
55  // ::= <num-filenames>
56  // <uncompressed-len>
57  // <compressed-len-or-zero>
58  // (<compressed-filenames> | <uncompressed-filenames>)
59  encodeULEB128(Filenames.size(), OS);
60  encodeULEB128(FilenamesStr.size(), OS);
61  encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);
62  OS << (doCompression ? CompressedStr.str() : StringRef(FilenamesStr));
63 }
64 
65 namespace {
66 
67 /// Gather only the expressions that are used by the mapping
68 /// regions in this function.
69 class CounterExpressionsMinimizer {
71  SmallVector<CounterExpression, 16> UsedExpressions;
72  std::vector<unsigned> AdjustedExpressionIDs;
73 
74 public:
75  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
76  ArrayRef<CounterMappingRegion> MappingRegions)
78  AdjustedExpressionIDs.resize(Expressions.size(), 0);
79  for (const auto &I : MappingRegions) {
80  mark(I.Count);
81  mark(I.FalseCount);
82  }
83  for (const auto &I : MappingRegions) {
84  gatherUsed(I.Count);
85  gatherUsed(I.FalseCount);
86  }
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.
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 <=
143  return Tag | (ID << Counter::EncodingTagBits);
144 }
145 
147  raw_ostream &OS) {
149 }
150 
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  Counter FalseCount = Minimizer.adjust(I->FalseCount);
205  switch (I->Kind) {
208  writeCounter(MinExpressions, Count, OS);
209  break;
211  assert(Count.isZero());
212  assert(I->ExpandedFileID <=
215  // Mark an expansion region with a set bit that follows the counter tag,
216  // and pack the expanded file id into the remaining bits.
217  unsigned EncodedTagExpandedFileID =
218  (1 << Counter::EncodingTagBits) |
219  (I->ExpandedFileID
221  encodeULEB128(EncodedTagExpandedFileID, OS);
222  break;
223  }
225  assert(Count.isZero());
226  encodeULEB128(unsigned(I->Kind)
228  OS);
229  break;
231  encodeULEB128(unsigned(I->Kind)
233  OS);
234  writeCounter(MinExpressions, Count, OS);
235  writeCounter(MinExpressions, FalseCount, OS);
236  break;
237  }
238  assert(I->LineStart >= PrevLineStart);
239  encodeULEB128(I->LineStart - PrevLineStart, OS);
240  encodeULEB128(I->ColumnStart, OS);
241  assert(I->LineEnd >= I->LineStart);
242  encodeULEB128(I->LineEnd - I->LineStart, OS);
243  encodeULEB128(I->ColumnEnd, OS);
244  PrevLineStart = I->LineStart;
245  }
246  // Ensure that all file ids have at least one mapping region.
247  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
248 }
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:146
Compression.h
llvm::coverage::Counter::isZero
bool isZero() const
Definition: CoverageMapping.h:112
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::coverage::CounterMappingRegion::endLoc
LineColPair endLoc() const
Definition: CoverageMapping.h:299
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:632
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::StringSet::insert
std::pair< typename Base::iterator, bool > insert(StringRef key)
Definition: StringSet.h:34
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:105
encodeCounter
static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)
Encode the counter.
Definition: CoverageMappingWriter.cpp:135
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:1617
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::zlib::BestSizeCompression
static constexpr int BestSizeCompression
Definition: Compression.h:28
llvm::zlib::compress
void compress(StringRef InputBuffer, SmallVectorImpl< char > &CompressedBuffer, int Level=DefaultCompression)
Definition: Compression.cpp:49
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:54
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::SmallString< 128 >
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:58
CoverageMappingWriter.h
llvm::coverage::CoverageMappingWriter::write
void write(raw_ostream &OS)
Write encoded coverage mapping data to the given output stream.
Definition: CoverageMappingWriter.cpp:151
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:23
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:1761
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::SmallString::str
StringRef str() const
Explicit conversion to StringRef.
Definition: SmallString.h:260
SmallVector.h
Expressions
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1265
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
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:38