1//=-- CoverageMapping.h - Code coverage mapping support ---------*- C++ -*-=//
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// Code coverage mapping data is generated by clang and read by
11// llvm-cov to show code coverage statistics for a file.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_
16#define LLVM_PROFILEDATA_COVERAGEMAPPING_H_
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/Hashing.h"
21#include "llvm/ADT/Triple.h"
22#include "llvm/ADT/iterator.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/ErrorOr.h"
25#include "llvm/Support/raw_ostream.h"
26#include <system_error>
27#include <tuple>
28
29namespace llvm {
30class IndexedInstrProfReader;
31namespace coverage {
32
33class CoverageMappingReader;
34
35class CoverageMapping;
36struct CounterExpressions;
37
38enum CoverageMappingVersion { CoverageMappingVersion1 };
39
40/// \brief A Counter is an abstract value that describes how to compute the
41/// execution count for a region of code using the collected profile count data.
42struct Counter {
43  enum CounterKind { Zero, CounterValueReference, Expression };
44  static const unsigned EncodingTagBits = 2;
45  static const unsigned EncodingTagMask = 0x3;
46  static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
47      EncodingTagBits + 1;
48
49private:
50  CounterKind Kind;
51  unsigned ID;
52
53  Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
54
55public:
56  Counter() : Kind(Zero), ID(0) {}
57
58  CounterKind getKind() const { return Kind; }
59
60  bool isZero() const { return Kind == Zero; }
61
62  bool isExpression() const { return Kind == Expression; }
63
64  unsigned getCounterID() const { return ID; }
65
66  unsigned getExpressionID() const { return ID; }
67
68  friend bool operator==(const Counter &LHS, const Counter &RHS) {
69    return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
70  }
71
72  friend bool operator!=(const Counter &LHS, const Counter &RHS) {
73    return !(LHS == RHS);
74  }
75
76  friend bool operator<(const Counter &LHS, const Counter &RHS) {
77    return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
78  }
79
80  /// \brief Return the counter that represents the number zero.
81  static Counter getZero() { return Counter(); }
82
83  /// \brief Return the counter that corresponds to a specific profile counter.
84  static Counter getCounter(unsigned CounterId) {
85    return Counter(CounterValueReference, CounterId);
86  }
87
88  /// \brief Return the counter that corresponds to a specific
89  /// addition counter expression.
90  static Counter getExpression(unsigned ExpressionId) {
91    return Counter(Expression, ExpressionId);
92  }
93};
94
95/// \brief A Counter expression is a value that represents an arithmetic
96/// operation with two counters.
97struct CounterExpression {
98  enum ExprKind { Subtract, Add };
99  ExprKind Kind;
100  Counter LHS, RHS;
101
102  CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
103      : Kind(Kind), LHS(LHS), RHS(RHS) {}
104};
105
106/// \brief A Counter expression builder is used to construct the
107/// counter expressions. It avoids unnecessary duplication
108/// and simplifies algebraic expressions.
109class CounterExpressionBuilder {
110  /// \brief A list of all the counter expressions
111  std::vector<CounterExpression> Expressions;
112  /// \brief A lookup table for the index of a given expression.
113  llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
114
115  /// \brief Return the counter which corresponds to the given expression.
116  ///
117  /// If the given expression is already stored in the builder, a counter
118  /// that references that expression is returned. Otherwise, the given
119  /// expression is added to the builder's collection of expressions.
120  Counter get(const CounterExpression &E);
121
122  /// \brief Gather the terms of the expression tree for processing.
123  ///
124  /// This collects each addition and subtraction referenced by the counter into
125  /// a sequence that can be sorted and combined to build a simplified counter
126  /// expression.
127  void extractTerms(Counter C, int Sign,
128                    SmallVectorImpl<std::pair<unsigned, int>> &Terms);
129
130  /// \brief Simplifies the given expression tree
131  /// by getting rid of algebraically redundant operations.
132  Counter simplify(Counter ExpressionTree);
133
134public:
135  ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
136
137  /// \brief Return a counter that represents the expression
138  /// that adds LHS and RHS.
139  Counter add(Counter LHS, Counter RHS);
140
141  /// \brief Return a counter that represents the expression
142  /// that subtracts RHS from LHS.
143  Counter subtract(Counter LHS, Counter RHS);
144};
145
146/// \brief A Counter mapping region associates a source range with
147/// a specific counter.
148struct CounterMappingRegion {
149  enum RegionKind {
150    /// \brief A CodeRegion associates some code with a counter
151    CodeRegion,
152
153    /// \brief An ExpansionRegion represents a file expansion region that
154    /// associates a source range with the expansion of a virtual source file,
155    /// such as for a macro instantiation or #include file.
156    ExpansionRegion,
157
158    /// \brief A SkippedRegion represents a source range with code that
159    /// was skipped by a preprocessor or similar means.
160    SkippedRegion
161  };
162
163  Counter Count;
164  unsigned FileID, ExpandedFileID;
165  unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
166  RegionKind Kind;
167
168  CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
169                       unsigned LineStart, unsigned ColumnStart,
170                       unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
171      : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
172        LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
173        ColumnEnd(ColumnEnd), Kind(Kind) {}
174
175  static CounterMappingRegion
176  makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
177             unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
178    return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
179                                LineEnd, ColumnEnd, CodeRegion);
180  }
181
182  static CounterMappingRegion
183  makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
184                unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
185    return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
186                                ColumnStart, LineEnd, ColumnEnd,
187                                ExpansionRegion);
188  }
189
190  static CounterMappingRegion
191  makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
192              unsigned LineEnd, unsigned ColumnEnd) {
193    return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
194                                LineEnd, ColumnEnd, SkippedRegion);
195  }
196
197
198  inline std::pair<unsigned, unsigned> startLoc() const {
199    return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
200  }
201
202  inline std::pair<unsigned, unsigned> endLoc() const {
203    return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
204  }
205
206  bool operator<(const CounterMappingRegion &Other) const {
207    if (FileID != Other.FileID)
208      return FileID < Other.FileID;
209    return startLoc() < Other.startLoc();
210  }
211
212  bool contains(const CounterMappingRegion &Other) const {
213    if (FileID != Other.FileID)
214      return false;
215    if (startLoc() > Other.startLoc())
216      return false;
217    if (endLoc() < Other.endLoc())
218      return false;
219    return true;
220  }
221};
222
223/// \brief Associates a source range with an execution count.
224struct CountedRegion : public CounterMappingRegion {
225  uint64_t ExecutionCount;
226
227  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
228      : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
229};
230
231/// \brief A Counter mapping context is used to connect the counters,
232/// expressions and the obtained counter values.
233class CounterMappingContext {
234  ArrayRef<CounterExpression> Expressions;
235  ArrayRef<uint64_t> CounterValues;
236
237public:
238  CounterMappingContext(ArrayRef<CounterExpression> Expressions,
239                        ArrayRef<uint64_t> CounterValues = None)
240      : Expressions(Expressions), CounterValues(CounterValues) {}
241
242  void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
243
244  void dump(const Counter &C, llvm::raw_ostream &OS) const;
245  void dump(const Counter &C) const { dump(C, dbgs()); }
246
247  /// \brief Return the number of times that a region of code associated with
248  /// this counter was executed.
249  ErrorOr<int64_t> evaluate(const Counter &C) const;
250};
251
252/// \brief Code coverage information for a single function.
253struct FunctionRecord {
254  /// \brief Raw function name.
255  std::string Name;
256  /// \brief Associated files.
257  std::vector<std::string> Filenames;
258  /// \brief Regions in the function along with their counts.
259  std::vector<CountedRegion> CountedRegions;
260  /// \brief The number of times this function was executed.
261  uint64_t ExecutionCount;
262
263  FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
264      : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
265
266  void pushRegion(CounterMappingRegion Region, uint64_t Count) {
267    if (CountedRegions.empty())
268      ExecutionCount = Count;
269    CountedRegions.emplace_back(Region, Count);
270  }
271};
272
273/// \brief Iterator over Functions, optionally filtered to a single file.
274class FunctionRecordIterator
275    : public iterator_facade_base<FunctionRecordIterator,
276                                  std::forward_iterator_tag, FunctionRecord> {
277  ArrayRef<FunctionRecord> Records;
278  ArrayRef<FunctionRecord>::iterator Current;
279  StringRef Filename;
280
281  /// \brief Skip records whose primary file is not \c Filename.
282  void skipOtherFiles();
283
284public:
285  FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
286                         StringRef Filename = "")
287      : Records(Records_), Current(Records.begin()), Filename(Filename) {
288    skipOtherFiles();
289  }
290
291  FunctionRecordIterator() : Current(Records.begin()) {}
292
293  bool operator==(const FunctionRecordIterator &RHS) const {
294    return Current == RHS.Current && Filename == RHS.Filename;
295  }
296
297  const FunctionRecord &operator*() const { return *Current; }
298
299  FunctionRecordIterator &operator++() {
300    assert(Current != Records.end() && "incremented past end");
301    ++Current;
302    skipOtherFiles();
303    return *this;
304  }
305};
306
307/// \brief Coverage information for a macro expansion or #included file.
308///
309/// When covered code has pieces that can be expanded for more detail, such as a
310/// preprocessor macro use and its definition, these are represented as
311/// expansions whose coverage can be looked up independently.
312struct ExpansionRecord {
313  /// \brief The abstract file this expansion covers.
314  unsigned FileID;
315  /// \brief The region that expands to this record.
316  const CountedRegion &Region;
317  /// \brief Coverage for the expansion.
318  const FunctionRecord &Function;
319
320  ExpansionRecord(const CountedRegion &Region,
321                  const FunctionRecord &Function)
322      : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
323};
324
325/// \brief The execution count information starting at a point in a file.
326///
327/// A sequence of CoverageSegments gives execution counts for a file in format
328/// that's simple to iterate through for processing.
329struct CoverageSegment {
330  /// \brief The line where this segment begins.
331  unsigned Line;
332  /// \brief The column where this segment begins.
333  unsigned Col;
334  /// \brief The execution count, or zero if no count was recorded.
335  uint64_t Count;
336  /// \brief When false, the segment was uninstrumented or skipped.
337  bool HasCount;
338  /// \brief Whether this enters a new region or returns to a previous count.
339  bool IsRegionEntry;
340
341  CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
342      : Line(Line), Col(Col), Count(0), HasCount(false),
343        IsRegionEntry(IsRegionEntry) {}
344
345  CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
346                  bool IsRegionEntry)
347      : Line(Line), Col(Col), Count(Count), HasCount(true),
348        IsRegionEntry(IsRegionEntry) {}
349
350  friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
351    return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
352           std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
353  }
354
355  void setCount(uint64_t NewCount) {
356    Count = NewCount;
357    HasCount = true;
358  }
359
360  void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
361};
362
363/// \brief Coverage information to be processed or displayed.
364///
365/// This represents the coverage of an entire file, expansion, or function. It
366/// provides a sequence of CoverageSegments to iterate through, as well as the
367/// list of expansions that can be further processed.
368class CoverageData {
369  std::string Filename;
370  std::vector<CoverageSegment> Segments;
371  std::vector<ExpansionRecord> Expansions;
372  friend class CoverageMapping;
373
374public:
375  CoverageData() {}
376
377  CoverageData(StringRef Filename) : Filename(Filename) {}
378
379  CoverageData(CoverageData &&RHS)
380      : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
381        Expansions(std::move(RHS.Expansions)) {}
382
383  /// \brief Get the name of the file this data covers.
384  StringRef getFilename() { return Filename; }
385
386  std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
387  std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
388  bool empty() { return Segments.empty(); }
389
390  /// \brief Expansions that can be further processed.
391  std::vector<ExpansionRecord> getExpansions() { return Expansions; }
392};
393
394/// \brief The mapping of profile information to coverage data.
395///
396/// This is the main interface to get coverage information, using a profile to
397/// fill out execution counts.
398class CoverageMapping {
399  std::vector<FunctionRecord> Functions;
400  unsigned MismatchedFunctionCount;
401
402  CoverageMapping() : MismatchedFunctionCount(0) {}
403
404public:
405  /// \brief Load the coverage mapping using the given readers.
406  static ErrorOr<std::unique_ptr<CoverageMapping>>
407  load(CoverageMappingReader &CoverageReader,
408       IndexedInstrProfReader &ProfileReader);
409
410  /// \brief Load the coverage mapping from the given files.
411  static ErrorOr<std::unique_ptr<CoverageMapping>>
412  load(StringRef ObjectFilename, StringRef ProfileFilename,
413       StringRef Arch = StringRef());
414
415  /// \brief The number of functions that couldn't have their profiles mapped.
416  ///
417  /// This is a count of functions whose profile is out of date or otherwise
418  /// can't be associated with any coverage information.
419  unsigned getMismatchedCount() { return MismatchedFunctionCount; }
420
421  /// \brief Returns the list of files that are covered.
422  std::vector<StringRef> getUniqueSourceFiles() const;
423
424  /// \brief Get the coverage for a particular file.
425  ///
426  /// The given filename must be the name as recorded in the coverage
427  /// information. That is, only names returned from getUniqueSourceFiles will
428  /// yield a result.
429  CoverageData getCoverageForFile(StringRef Filename);
430
431  /// \brief Gets all of the functions covered by this profile.
432  iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
433    return make_range(FunctionRecordIterator(Functions),
434                      FunctionRecordIterator());
435  }
436
437  /// \brief Gets all of the functions in a particular file.
438  iterator_range<FunctionRecordIterator>
439  getCoveredFunctions(StringRef Filename) const {
440    return make_range(FunctionRecordIterator(Functions, Filename),
441                      FunctionRecordIterator());
442  }
443
444  /// \brief Get the list of function instantiations in the file.
445  ///
446  /// Functions that are instantiated more than once, such as C++ template
447  /// specializations, have distinct coverage records for each instantiation.
448  std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
449
450  /// \brief Get the coverage for a particular function.
451  CoverageData getCoverageForFunction(const FunctionRecord &Function);
452
453  /// \brief Get the coverage for an expansion within a coverage set.
454  CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
455};
456
457} // end namespace coverage
458
459/// \brief Provide DenseMapInfo for CounterExpression
460template<> struct DenseMapInfo<coverage::CounterExpression> {
461  static inline coverage::CounterExpression getEmptyKey() {
462    using namespace coverage;
463    return CounterExpression(CounterExpression::ExprKind::Subtract,
464                             Counter::getCounter(~0U),
465                             Counter::getCounter(~0U));
466  }
467
468  static inline coverage::CounterExpression getTombstoneKey() {
469    using namespace coverage;
470    return CounterExpression(CounterExpression::ExprKind::Add,
471                             Counter::getCounter(~0U),
472                             Counter::getCounter(~0U));
473  }
474
475  static unsigned getHashValue(const coverage::CounterExpression &V) {
476    return static_cast<unsigned>(
477        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
478                     V.RHS.getKind(), V.RHS.getCounterID()));
479  }
480
481  static bool isEqual(const coverage::CounterExpression &LHS,
482                      const coverage::CounterExpression &RHS) {
483    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
484  }
485};
486
487const std::error_category &coveragemap_category();
488
489enum class coveragemap_error {
490  success = 0,
491  eof,
492  no_data_found,
493  unsupported_version,
494  truncated,
495  malformed
496};
497
498inline std::error_code make_error_code(coveragemap_error E) {
499  return std::error_code(static_cast<int>(E), coveragemap_category());
500}
501
502} // end namespace llvm
503
504namespace std {
505template <>
506struct is_error_code_enum<llvm::coveragemap_error> : std::true_type {};
507}
508
509#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_
510