llvm.org GIT mirror llvm / 1b27914 include / llvm / ProfileData / CoverageMapping.h
1b27914

Tree @1b27914 (Download .tar.gz)

CoverageMapping.h @1b27914raw · history · blame

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
//=-- CoverageMapping.h - Code coverage mapping support ---------*- C++ -*-=//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Code coverage mapping data is generated by clang and read by
// llvm-cov to show code coverage statistics for a file.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_
#define LLVM_PROFILEDATA_COVERAGEMAPPING_H_

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/iterator.h"
#include "llvm/Support/ErrorOr.h"
#include "llvm/Support/raw_ostream.h"
#include <system_error>

namespace llvm {
class IndexedInstrProfReader;
namespace coverage {

class ObjectFileCoverageMappingReader;

class CoverageMapping;
struct CounterExpressions;

enum CoverageMappingVersion { CoverageMappingVersion1 };

/// \brief A Counter is an abstract value that describes how to compute the
/// execution count for a region of code using the collected profile count data.
struct Counter {
  enum CounterKind { Zero, CounterValueReference, Expression };
  static const unsigned EncodingTagBits = 2;
  static const unsigned EncodingTagMask = 0x3;
  static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
      EncodingTagBits + 1;

private:
  CounterKind Kind;
  unsigned ID;

  Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}

public:
  Counter() : Kind(Zero), ID(0) {}

  CounterKind getKind() const { return Kind; }

  bool isZero() const { return Kind == Zero; }

  bool isExpression() const { return Kind == Expression; }

  unsigned getCounterID() const { return ID; }

  unsigned getExpressionID() const { return ID; }

  bool operator==(const Counter &Other) const {
    return Kind == Other.Kind && ID == Other.ID;
  }

  friend bool operator<(const Counter &LHS, const Counter &RHS) {
    return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  }

  /// \brief Return the counter that represents the number zero.
  static Counter getZero() { return Counter(); }

  /// \brief Return the counter that corresponds to a specific profile counter.
  static Counter getCounter(unsigned CounterId) {
    return Counter(CounterValueReference, CounterId);
  }

  /// \brief Return the counter that corresponds to a specific
  /// addition counter expression.
  static Counter getExpression(unsigned ExpressionId) {
    return Counter(Expression, ExpressionId);
  }
};

/// \brief A Counter expression is a value that represents an arithmetic
/// operation with two counters.
struct CounterExpression {
  enum ExprKind { Subtract, Add };
  ExprKind Kind;
  Counter LHS, RHS;

  CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
      : Kind(Kind), LHS(LHS), RHS(RHS) {}
};

/// \brief A Counter expression builder is used to construct the
/// counter expressions. It avoids unecessary duplication
/// and simplifies algebraic expressions.
class CounterExpressionBuilder {
  /// \brief A list of all the counter expressions
  std::vector<CounterExpression> Expressions;
  /// \brief A lookup table for the index of a given expression.
  llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;

  /// \brief Return the counter which corresponds to the given expression.
  ///
  /// If the given expression is already stored in the builder, a counter
  /// that references that expression is returned. Otherwise, the given
  /// expression is added to the builder's collection of expressions.
  Counter get(const CounterExpression &E);

  /// \brief Gather the terms of the expression tree for processing.
  ///
  /// This collects each addition and subtraction referenced by the counter into
  /// a sequence that can be sorted and combined to build a simplified counter
  /// expression.
  void extractTerms(Counter C, int Sign,
                    SmallVectorImpl<std::pair<unsigned, int>> &Terms);

  /// \brief Simplifies the given expression tree
  /// by getting rid of algebraically redundant operations.
  Counter simplify(Counter ExpressionTree);

public:
  ArrayRef<CounterExpression> getExpressions() const { return Expressions; }

  /// \brief Return a counter that represents the expression
  /// that adds LHS and RHS.
  Counter add(Counter LHS, Counter RHS);

  /// \brief Return a counter that represents the expression
  /// that subtracts RHS from LHS.
  Counter subtract(Counter LHS, Counter RHS);
};

/// \brief A Counter mapping region associates a source range with
/// a specific counter.
struct CounterMappingRegion {
  enum RegionKind {
    /// \brief A CodeRegion associates some code with a counter
    CodeRegion,

    /// \brief An ExpansionRegion represents a file expansion region that
    /// associates a source range with the expansion of a virtual source file,
    /// such as for a macro instantiation or #include file.
    ExpansionRegion,

    /// \brief A SkippedRegion represents a source range with code that
    /// was skipped by a preprocessor or similar means.
    SkippedRegion
  };

  static const unsigned EncodingHasCodeBeforeBits = 1;

  Counter Count;
  unsigned FileID, ExpandedFileID;
  unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
  RegionKind Kind;
  /// \brief A flag that is set to true when there is already code before
  /// this region on the same line.
  /// This is useful to accurately compute the execution counts for a line.
  bool HasCodeBefore;

  CounterMappingRegion(Counter Count, unsigned FileID, unsigned LineStart,
                       unsigned ColumnStart, unsigned LineEnd,
                       unsigned ColumnEnd, bool HasCodeBefore = false,
                       RegionKind Kind = CodeRegion)
      : Count(Count), FileID(FileID), ExpandedFileID(0), LineStart(LineStart),
        ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd),
        Kind(Kind), HasCodeBefore(HasCodeBefore) {}

  inline std::pair<unsigned, unsigned> startLoc() const {
    return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
  }

  inline std::pair<unsigned, unsigned> endLoc() const {
    return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
  }

  bool operator<(const CounterMappingRegion &Other) const {
    if (FileID != Other.FileID)
      return FileID < Other.FileID;
    return startLoc() < Other.startLoc();
  }

  bool contains(const CounterMappingRegion &Other) const {
    if (FileID != Other.FileID)
      return false;
    if (startLoc() > Other.startLoc())
      return false;
    if (endLoc() < Other.endLoc())
      return false;
    return true;
  }
};

/// \brief Associates a source range with an execution count.
struct CountedRegion : public CounterMappingRegion {
  uint64_t ExecutionCount;

  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
      : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
};

/// \brief A Counter mapping context is used to connect the counters,
/// expressions and the obtained counter values.
class CounterMappingContext {
  ArrayRef<CounterExpression> Expressions;
  ArrayRef<uint64_t> CounterValues;

public:
  CounterMappingContext(ArrayRef<CounterExpression> Expressions,
                        ArrayRef<uint64_t> CounterValues = ArrayRef<uint64_t>())
      : Expressions(Expressions), CounterValues(CounterValues) {}

  void dump(const Counter &C, llvm::raw_ostream &OS) const;
  void dump(const Counter &C) const { dump(C, llvm::outs()); }

  /// \brief Return the number of times that a region of code associated with
  /// this counter was executed.
  ErrorOr<int64_t> evaluate(const Counter &C) const;
};

/// \brief Code coverage information for a single function.
struct FunctionRecord {
  /// \brief Raw function name.
  std::string Name;
  /// \brief Associated files.
  std::vector<std::string> Filenames;
  /// \brief Regions in the function along with their counts.
  std::vector<CountedRegion> CountedRegions;
  /// \brief The number of times this function was executed.
  uint64_t ExecutionCount;

  FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames,
                 uint64_t ExecutionCount)
      : Name(Name), Filenames(Filenames.begin(), Filenames.end()),
        ExecutionCount(ExecutionCount) {}
};

/// \brief Iterator over Functions, optionally filtered to a single file.
class FunctionRecordIterator
    : public iterator_facade_base<FunctionRecordIterator,
                                  std::forward_iterator_tag, FunctionRecord> {
  ArrayRef<FunctionRecord> Records;
  ArrayRef<FunctionRecord>::iterator Current;
  StringRef Filename;

  /// \brief Skip records whose primary file is not \c Filename.
  void skipOtherFiles();

public:
  FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
                         StringRef Filename = "")
      : Records(Records_), Current(Records.begin()), Filename(Filename) {
    skipOtherFiles();
  }

  FunctionRecordIterator() : Current(Records.begin()) {}

  bool operator==(const FunctionRecordIterator &RHS) const {
    return Current == RHS.Current && Filename == RHS.Filename;
  }

  const FunctionRecord &operator*() const { return *Current; }

  FunctionRecordIterator &operator++() {
    assert(Current != Records.end() && "incremented past end");
    ++Current;
    skipOtherFiles();
    return *this;
  }
};

/// \brief Coverage information for a macro expansion or #included file.
///
/// When covered code has pieces that can be expanded for more detail, such as a
/// preprocessor macro use and its definition, these are represented as
/// expansions whose coverage can be looked up independently.
struct ExpansionRecord {
  /// \brief The abstract file this expansion covers.
  unsigned FileID;
  /// \brief The region that expands to this record.
  const CountedRegion &Region;
  /// \brief Coverage for the expansion.
  const FunctionRecord &Function;

  ExpansionRecord(const CountedRegion &Region,
                  const FunctionRecord &Function)
      : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
};

/// \brief The execution count information starting at a point in a file.
///
/// A sequence of CoverageSegments gives execution counts for a file in format
/// that's simple to iterate through for processing.
struct CoverageSegment {
  /// \brief The line where this segment begins.
  unsigned Line;
  /// \brief The column where this segment begins.
  unsigned Col;
  /// \brief The execution count, or zero if no count was recorded.
  uint64_t Count;
  /// \brief When false, the segment was uninstrumented or skipped.
  bool HasCount;
  /// \brief Whether this enters a new region or returns to a previous count.
  bool IsRegionEntry;

  CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
      : Line(Line), Col(Col), Count(0), HasCount(false),
        IsRegionEntry(IsRegionEntry) {}
  void setCount(uint64_t NewCount) {
    Count = NewCount;
    HasCount = true;
  }
  void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
};

/// \brief Coverage information to be processed or displayed.
///
/// This represents the coverage of an entire file, expansion, or function. It
/// provides a sequence of CoverageSegments to iterate through, as well as the
/// list of expansions that can be further processed.
class CoverageData {
  std::string Filename;
  std::vector<CoverageSegment> Segments;
  std::vector<ExpansionRecord> Expansions;
  friend class CoverageMapping;

public:
  CoverageData() {}

  CoverageData(StringRef Filename) : Filename(Filename) {}

  CoverageData(CoverageData &&RHS)
      : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
        Expansions(std::move(RHS.Expansions)) {}

  /// \brief Get the name of the file this data covers.
  StringRef getFilename() { return Filename; }

  std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
  std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
  bool empty() { return Segments.empty(); }

  /// \brief Expansions that can be further processed.
  std::vector<ExpansionRecord> getExpansions() { return Expansions; }
};

/// \brief The mapping of profile information to coverage data.
///
/// This is the main interface to get coverage information, using a profile to
/// fill out execution counts.
class CoverageMapping {
  std::vector<FunctionRecord> Functions;
  unsigned MismatchedFunctionCount;

  CoverageMapping() : MismatchedFunctionCount(0) {}

public:
  /// \brief Load the coverage mapping using the given readers.
  static ErrorOr<std::unique_ptr<CoverageMapping>>
  load(ObjectFileCoverageMappingReader &CoverageReader,
       IndexedInstrProfReader &ProfileReader);

  /// \brief Load the coverage mapping from the given files.
  static ErrorOr<std::unique_ptr<CoverageMapping>>
  load(StringRef ObjectFilename, StringRef ProfileFilename);

  /// \brief The number of functions that couldn't have their profiles mapped.
  ///
  /// This is a count of functions whose profile is out of date or otherwise
  /// can't be associated with any coverage information.
  unsigned getMismatchedCount() { return MismatchedFunctionCount; }

  /// \brief Returns the list of files that are covered.
  std::vector<StringRef> getUniqueSourceFiles() const;

  /// \brief Get the coverage for a particular file.
  ///
  /// The given filename must be the name as recorded in the coverage
  /// information. That is, only names returned from getUniqueSourceFiles will
  /// yield a result.
  CoverageData getCoverageForFile(StringRef Filename);

  /// \brief Gets all of the functions covered by this profile.
  iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
    return make_range(FunctionRecordIterator(Functions),
                      FunctionRecordIterator());
  }

  /// \brief Gets all of the functions in a particular file.
  iterator_range<FunctionRecordIterator>
  getCoveredFunctions(StringRef Filename) const {
    return make_range(FunctionRecordIterator(Functions, Filename),
                      FunctionRecordIterator());
  }

  /// \brief Get the list of function instantiations in the file.
  ///
  /// Fucntions that are instantiated more than once, such as C++ template
  /// specializations, have distinct coverage records for each instantiation.
  std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);

  /// \brief Get the coverage for a particular function.
  CoverageData getCoverageForFunction(const FunctionRecord &Function);

  /// \brief Get the coverage for an expansion within a coverage set.
  CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
};

} // end namespace coverage

/// \brief Provide DenseMapInfo for CounterExpression
template<> struct DenseMapInfo<coverage::CounterExpression> {
  static inline coverage::CounterExpression getEmptyKey() {
    using namespace coverage;
    return CounterExpression(CounterExpression::ExprKind::Subtract,
                             Counter::getCounter(~0U),
                             Counter::getCounter(~0U));
  }

  static inline coverage::CounterExpression getTombstoneKey() {
    using namespace coverage;
    return CounterExpression(CounterExpression::ExprKind::Add,
                             Counter::getCounter(~0U),
                             Counter::getCounter(~0U));
  }

  static unsigned getHashValue(const coverage::CounterExpression &V) {
    return static_cast<unsigned>(
        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
                     V.RHS.getKind(), V.RHS.getCounterID()));
  }

  static bool isEqual(const coverage::CounterExpression &LHS,
                      const coverage::CounterExpression &RHS) {
    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
  }
};


} // end namespace llvm

#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_