LLVM  16.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  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 
67 namespace {
68 
69 /// Gather only the expressions that are used by the mapping
70 /// regions in this function.
71 class CounterExpressionsMinimizer {
73  SmallVector<CounterExpression, 16> UsedExpressions;
74  std::vector<unsigned> AdjustedExpressionIDs;
75 
76 public:
77  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
78  ArrayRef<CounterMappingRegion> MappingRegions)
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.
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 <=
145  return Tag | (ID << Counter::EncodingTagBits);
146 }
147 
149  raw_ostream &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 <=
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 =
220  (1 << Counter::EncodingTagBits) |
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 }
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:148
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:18
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:628
llvm::SmallVector< uint8_t, 128 >
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:137
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:1590
llvm::compression::zlib::BestSizeCompression
constexpr int BestSizeCompression
Definition: Compression.h:39
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::dwarf::toStringRef
StringRef toStringRef(const Optional< DWARFFormValue > &V, StringRef Default={})
Take an optional DWARFFormValue and try to extract a string value from it.
Definition: DWARFFormValue.h:193
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:52
llvm::compression::zlib::isAvailable
bool isAvailable()
Definition: Compression.cpp:105
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:153
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::coverage::CounterMappingRegion::startLoc
LineColPair startLoc() const
Definition: CoverageMapping.h:295
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:50
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:1752
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::compression::zlib::compress
void compress(ArrayRef< uint8_t > Input, SmallVectorImpl< uint8_t > &CompressedBuffer, int Level=DefaultCompression)
Definition: Compression.cpp:107
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