LLVM  10.0.0svn
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 
15 #include "llvm/ADT/ArrayRef.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/Support/LEB128.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <limits>
22 #include <vector>
23 
24 using namespace llvm;
25 using namespace coverage;
26 
28  ArrayRef<StringRef> Filenames)
29  : Filenames(Filenames) {
30 #ifndef NDEBUG
31  StringSet<> NameSet;
32  for (StringRef Name : Filenames)
33  assert(NameSet.insert(Name).second && "Duplicate filename");
34 #endif
35 }
36 
38  encodeULEB128(Filenames.size(), OS);
39  for (const auto &Filename : Filenames) {
40  encodeULEB128(Filename.size(), OS);
41  OS << Filename;
42  }
43 }
44 
45 namespace {
46 
47 /// Gather only the expressions that are used by the mapping
48 /// regions in this function.
49 class CounterExpressionsMinimizer {
51  SmallVector<CounterExpression, 16> UsedExpressions;
52  std::vector<unsigned> AdjustedExpressionIDs;
53 
54 public:
55  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
56  ArrayRef<CounterMappingRegion> MappingRegions)
57  : Expressions(Expressions) {
58  AdjustedExpressionIDs.resize(Expressions.size(), 0);
59  for (const auto &I : MappingRegions)
60  mark(I.Count);
61  for (const auto &I : MappingRegions)
62  gatherUsed(I.Count);
63  }
64 
65  void mark(Counter C) {
66  if (!C.isExpression())
67  return;
68  unsigned ID = C.getExpressionID();
69  AdjustedExpressionIDs[ID] = 1;
70  mark(Expressions[ID].LHS);
71  mark(Expressions[ID].RHS);
72  }
73 
74  void gatherUsed(Counter C) {
75  if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
76  return;
77  AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
78  const auto &E = Expressions[C.getExpressionID()];
79  UsedExpressions.push_back(E);
80  gatherUsed(E.LHS);
81  gatherUsed(E.RHS);
82  }
83 
84  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
85 
86  /// Adjust the given counter to correctly transition from the old
87  /// expression ids to the new expression ids.
88  Counter adjust(Counter C) const {
89  if (C.isExpression())
90  C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
91  return C;
92  }
93 };
94 
95 } // end anonymous namespace
96 
97 /// Encode the counter.
98 ///
99 /// The encoding uses the following format:
100 /// Low 2 bits - Tag:
101 /// Counter::Zero(0) - A Counter with kind Counter::Zero
102 /// Counter::CounterValueReference(1) - A counter with kind
103 /// Counter::CounterValueReference
104 /// Counter::Expression(2) + CounterExpression::Subtract(0) -
105 /// A counter with kind Counter::Expression and an expression
106 /// with kind CounterExpression::Subtract
107 /// Counter::Expression(2) + CounterExpression::Add(1) -
108 /// A counter with kind Counter::Expression and an expression
109 /// with kind CounterExpression::Add
110 /// Remaining bits - Counter/Expression ID.
112  Counter C) {
113  unsigned Tag = unsigned(C.getKind());
114  if (C.isExpression())
115  Tag += Expressions[C.getExpressionID()].Kind;
116  unsigned ID = C.getCounterID();
117  assert(ID <=
119  return Tag | (ID << Counter::EncodingTagBits);
120 }
121 
123  raw_ostream &OS) {
124  encodeULEB128(encodeCounter(Expressions, C), OS);
125 }
126 
128  // Check that we don't have any bogus regions.
129  assert(all_of(MappingRegions,
130  [](const CounterMappingRegion &CMR) {
131  return CMR.startLoc() <= CMR.endLoc();
132  }) &&
133  "Source region does not begin before it ends");
134 
135  // Sort the regions in an ascending order by the file id and the starting
136  // location. Sort by region kinds to ensure stable order for tests.
137  llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,
138  const CounterMappingRegion &RHS) {
139  if (LHS.FileID != RHS.FileID)
140  return LHS.FileID < RHS.FileID;
141  if (LHS.startLoc() != RHS.startLoc())
142  return LHS.startLoc() < RHS.startLoc();
143  return LHS.Kind < RHS.Kind;
144  });
145 
146  // Write out the fileid -> filename mapping.
147  encodeULEB128(VirtualFileMapping.size(), OS);
148  for (const auto &FileID : VirtualFileMapping)
149  encodeULEB128(FileID, OS);
150 
151  // Write out the expressions.
152  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
153  auto MinExpressions = Minimizer.getExpressions();
154  encodeULEB128(MinExpressions.size(), OS);
155  for (const auto &E : MinExpressions) {
156  writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
157  writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
158  }
159 
160  // Write out the mapping regions.
161  // Split the regions into subarrays where each region in a
162  // subarray has a fileID which is the index of that subarray.
163  unsigned PrevLineStart = 0;
164  unsigned CurrentFileID = ~0U;
165  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
166  if (I->FileID != CurrentFileID) {
167  // Ensure that all file ids have at least one mapping region.
168  assert(I->FileID == (CurrentFileID + 1));
169  // Find the number of regions with this file id.
170  unsigned RegionCount = 1;
171  for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
172  ++RegionCount;
173  // Start a new region sub-array.
174  encodeULEB128(RegionCount, OS);
175 
176  CurrentFileID = I->FileID;
177  PrevLineStart = 0;
178  }
179  Counter Count = Minimizer.adjust(I->Count);
180  switch (I->Kind) {
183  writeCounter(MinExpressions, Count, OS);
184  break;
186  assert(Count.isZero());
187  assert(I->ExpandedFileID <=
190  // Mark an expansion region with a set bit that follows the counter tag,
191  // and pack the expanded file id into the remaining bits.
192  unsigned EncodedTagExpandedFileID =
193  (1 << Counter::EncodingTagBits) |
194  (I->ExpandedFileID
196  encodeULEB128(EncodedTagExpandedFileID, OS);
197  break;
198  }
200  assert(Count.isZero());
201  encodeULEB128(unsigned(I->Kind)
203  OS);
204  break;
205  }
206  assert(I->LineStart >= PrevLineStart);
207  encodeULEB128(I->LineStart - PrevLineStart, OS);
208  encodeULEB128(I->ColumnStart, OS);
209  assert(I->LineEnd >= I->LineStart);
210  encodeULEB128(I->LineEnd - I->LineStart, OS);
211  encodeULEB128(I->ColumnEnd, OS);
212  PrevLineStart = I->LineStart;
213  }
214  // Ensure that all file ids have at least one mapping region.
215  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
216 }
uint64_t CallInst * C
This class represents lattice values for constants.
Definition: AllocatorList.h:23
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
void write(raw_ostream &OS)
Write encoded coverage mapping data to the given output stream.
void write(raw_ostream &OS)
Write encoded filenames to the given output stream.
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:1165
CoverageFilenamesSectionWriter(ArrayRef< StringRef > Filenames)
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1202
A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)
Encode the counter.
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
A CodeRegion associates some code with a counter.
A Counter mapping region associates a source range with a specific counter.
size_t size() const
Definition: SmallVector.h:52
std::pair< typename base::iterator, bool > insert(StringRef Key)
Definition: StringSet.h:38
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
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
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
An ExpansionRegion represents a file expansion region that associates a source range with the expansi...
A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...
static void writeCounter(ArrayRef< CounterExpression > Expressions, Counter C, raw_ostream &OS)
static const unsigned EncodingCounterTagAndExpansionRegionTagBits
unsigned getExpressionID() const
CounterKind getKind() const
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const unsigned EncodingTagBits
void stable_sort(R &&Range)
Definition: STLExtras.h:1289
unsigned getCounterID() const
StringSet - A wrapper for StringMap that provides set-like functionality.
Definition: StringSet.h:27
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
static Counter getExpression(unsigned ExpressionId)
Return the counter that corresponds to a specific addition counter expression.
A Counter is an abstract value that describes how to compute the execution count for a region of code...