LLVM  6.0.0svn
CoverageMappingWriter.cpp
Go to the documentation of this file.
1 //===- CoverageMappingWriter.cpp - Code coverage mapping writer -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file contains support for writing coverage mapping data for
11 // instrumentation based coverage.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Support/LEB128.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <limits>
23 #include <vector>
24 
25 using namespace llvm;
26 using namespace coverage;
27 
29  encodeULEB128(Filenames.size(), OS);
30  for (const auto &Filename : Filenames) {
31  encodeULEB128(Filename.size(), OS);
32  OS << Filename;
33  }
34 }
35 
36 namespace {
37 
38 /// \brief Gather only the expressions that are used by the mapping
39 /// regions in this function.
40 class CounterExpressionsMinimizer {
42  SmallVector<CounterExpression, 16> UsedExpressions;
43  std::vector<unsigned> AdjustedExpressionIDs;
44 
45 public:
46  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
47  ArrayRef<CounterMappingRegion> MappingRegions)
48  : Expressions(Expressions) {
49  AdjustedExpressionIDs.resize(Expressions.size(), 0);
50  for (const auto &I : MappingRegions)
51  mark(I.Count);
52  for (const auto &I : MappingRegions)
53  gatherUsed(I.Count);
54  }
55 
56  void mark(Counter C) {
57  if (!C.isExpression())
58  return;
59  unsigned ID = C.getExpressionID();
60  AdjustedExpressionIDs[ID] = 1;
61  mark(Expressions[ID].LHS);
62  mark(Expressions[ID].RHS);
63  }
64 
65  void gatherUsed(Counter C) {
66  if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
67  return;
68  AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
69  const auto &E = Expressions[C.getExpressionID()];
70  UsedExpressions.push_back(E);
71  gatherUsed(E.LHS);
72  gatherUsed(E.RHS);
73  }
74 
75  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
76 
77  /// \brief Adjust the given counter to correctly transition from the old
78  /// expression ids to the new expression ids.
79  Counter adjust(Counter C) const {
80  if (C.isExpression())
81  C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
82  return C;
83  }
84 };
85 
86 } // end anonymous namespace
87 
88 /// \brief Encode the counter.
89 ///
90 /// The encoding uses the following format:
91 /// Low 2 bits - Tag:
92 /// Counter::Zero(0) - A Counter with kind Counter::Zero
93 /// Counter::CounterValueReference(1) - A counter with kind
94 /// Counter::CounterValueReference
95 /// Counter::Expression(2) + CounterExpression::Subtract(0) -
96 /// A counter with kind Counter::Expression and an expression
97 /// with kind CounterExpression::Subtract
98 /// Counter::Expression(2) + CounterExpression::Add(1) -
99 /// A counter with kind Counter::Expression and an expression
100 /// with kind CounterExpression::Add
101 /// Remaining bits - Counter/Expression ID.
103  Counter C) {
104  unsigned Tag = unsigned(C.getKind());
105  if (C.isExpression())
106  Tag += Expressions[C.getExpressionID()].Kind;
107  unsigned ID = C.getCounterID();
108  assert(ID <=
110  return Tag | (ID << Counter::EncodingTagBits);
111 }
112 
114  raw_ostream &OS) {
115  encodeULEB128(encodeCounter(Expressions, C), OS);
116 }
117 
119  // Check that we don't have any bogus regions.
120  assert(all_of(MappingRegions,
121  [](const CounterMappingRegion &CMR) {
122  return CMR.startLoc() <= CMR.endLoc();
123  }) &&
124  "Source region does not begin before it ends");
125 
126  // Sort the regions in an ascending order by the file id and the starting
127  // location. Sort by region kinds to ensure stable order for tests.
128  std::stable_sort(
129  MappingRegions.begin(), MappingRegions.end(),
130  [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) {
131  if (LHS.FileID != RHS.FileID)
132  return LHS.FileID < RHS.FileID;
133  if (LHS.startLoc() != RHS.startLoc())
134  return LHS.startLoc() < RHS.startLoc();
135  return LHS.Kind < RHS.Kind;
136  });
137 
138  // Write out the fileid -> filename mapping.
139  encodeULEB128(VirtualFileMapping.size(), OS);
140  for (const auto &FileID : VirtualFileMapping)
141  encodeULEB128(FileID, OS);
142 
143  // Write out the expressions.
144  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
145  auto MinExpressions = Minimizer.getExpressions();
146  encodeULEB128(MinExpressions.size(), OS);
147  for (const auto &E : MinExpressions) {
148  writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
149  writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
150  }
151 
152  // Write out the mapping regions.
153  // Split the regions into subarrays where each region in a
154  // subarray has a fileID which is the index of that subarray.
155  unsigned PrevLineStart = 0;
156  unsigned CurrentFileID = ~0U;
157  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
158  if (I->FileID != CurrentFileID) {
159  // Ensure that all file ids have at least one mapping region.
160  assert(I->FileID == (CurrentFileID + 1));
161  // Find the number of regions with this file id.
162  unsigned RegionCount = 1;
163  for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
164  ++RegionCount;
165  // Start a new region sub-array.
166  encodeULEB128(RegionCount, OS);
167 
168  CurrentFileID = I->FileID;
169  PrevLineStart = 0;
170  }
171  Counter Count = Minimizer.adjust(I->Count);
172  switch (I->Kind) {
175  writeCounter(MinExpressions, Count, OS);
176  break;
178  assert(Count.isZero());
179  assert(I->ExpandedFileID <=
182  // Mark an expansion region with a set bit that follows the counter tag,
183  // and pack the expanded file id into the remaining bits.
184  unsigned EncodedTagExpandedFileID =
185  (1 << Counter::EncodingTagBits) |
186  (I->ExpandedFileID
188  encodeULEB128(EncodedTagExpandedFileID, OS);
189  break;
190  }
192  assert(Count.isZero());
193  encodeULEB128(unsigned(I->Kind)
195  OS);
196  break;
197  }
198  assert(I->LineStart >= PrevLineStart);
199  encodeULEB128(I->LineStart - PrevLineStart, OS);
200  encodeULEB128(I->ColumnStart, OS);
201  assert(I->LineEnd >= I->LineStart);
202  encodeULEB128(I->LineEnd - I->LineStart, OS);
203  encodeULEB128(I->ColumnEnd, OS);
204  PrevLineStart = I->LineStart;
205  }
206  // Ensure that all file ids have at least one mapping region.
207  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
208 }
uint64_t CallInst * C
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
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:813
gvn Early GVN Hoisting of Expressions
Definition: GVNHoist.cpp:1204
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:33
static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)
Encode the counter.
void encodeULEB128(uint64_t Value, raw_ostream &OS, unsigned PadTo=0)
Utility function to encode a ULEB128 value to an output stream.
Definition: LEB128.h:77
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
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.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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
unsigned getCounterID() const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
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...