1 //=-- CoverageMapping.h - Code coverage mapping support ---------*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Code coverage mapping data is generated by clang and read by
11 // llvm-cov to show code coverage statistics for a file.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_
16 #define LLVM_PROFILEDATA_COVERAGEMAPPING_H_
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>
30 class IndexedInstrProfReader;
33 class CoverageMappingReader;
35 class CoverageMapping;
36 struct CounterExpressions;
38 enum CoverageMappingVersion { CoverageMappingVersion1 };
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.
43 enum CounterKind { Zero, CounterValueReference, Expression };
44 static const unsigned EncodingTagBits = 2;
45 static const unsigned EncodingTagMask = 0x3;
46 static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
53 Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
56 Counter() : Kind(Zero), ID(0) {}
58 CounterKind getKind() const { return Kind; }
60 bool isZero() const { return Kind == Zero; }
62 bool isExpression() const { return Kind == Expression; }
64 unsigned getCounterID() const { return ID; }
66 unsigned getExpressionID() const { return ID; }
68 friend bool operator==(const Counter &LHS, const Counter &RHS) {
69 return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
72 friend bool operator!=(const Counter &LHS, const Counter &RHS) {
76 friend bool operator<(const Counter &LHS, const Counter &RHS) {
77 return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
80 /// \brief Return the counter that represents the number zero.
81 static Counter getZero() { return Counter(); }
83 /// \brief Return the counter that corresponds to a specific profile counter.
84 static Counter getCounter(unsigned CounterId) {
85 return Counter(CounterValueReference, CounterId);
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);
95 /// \brief A Counter expression is a value that represents an arithmetic
96 /// operation with two counters.
97 struct CounterExpression {
98 enum ExprKind { Subtract, Add };
102 CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
103 : Kind(Kind), LHS(LHS), RHS(RHS) {}
106 /// \brief A Counter expression builder is used to construct the
107 /// counter expressions. It avoids unecessary duplication
108 /// and simplifies algebraic expressions.
109 class 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;
115 /// \brief Return the counter which corresponds to the given expression.
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);
122 /// \brief Gather the terms of the expression tree for processing.
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
127 void extractTerms(Counter C, int Sign,
128 SmallVectorImpl<std::pair<unsigned, int>> &Terms);
130 /// \brief Simplifies the given expression tree
131 /// by getting rid of algebraically redundant operations.
132 Counter simplify(Counter ExpressionTree);
135 ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
137 /// \brief Return a counter that represents the expression
138 /// that adds LHS and RHS.
139 Counter add(Counter LHS, Counter RHS);
141 /// \brief Return a counter that represents the expression
142 /// that subtracts RHS from LHS.
143 Counter subtract(Counter LHS, Counter RHS);
146 /// \brief A Counter mapping region associates a source range with
147 /// a specific counter.
148 struct CounterMappingRegion {
150 /// \brief A CodeRegion associates some code with a counter
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.
158 /// \brief A SkippedRegion represents a source range with code that
159 /// was skipped by a preprocessor or similar means.
164 unsigned FileID, ExpandedFileID;
165 unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
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) {}
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);
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,
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);
198 inline std::pair<unsigned, unsigned> startLoc() const {
199 return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
202 inline std::pair<unsigned, unsigned> endLoc() const {
203 return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
206 bool operator<(const CounterMappingRegion &Other) const {
207 if (FileID != Other.FileID)
208 return FileID < Other.FileID;
209 return startLoc() < Other.startLoc();
212 bool contains(const CounterMappingRegion &Other) const {
213 if (FileID != Other.FileID)
215 if (startLoc() > Other.startLoc())
217 if (endLoc() < Other.endLoc())
223 /// \brief Associates a source range with an execution count.
224 struct CountedRegion : public CounterMappingRegion {
225 uint64_t ExecutionCount;
227 CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
228 : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
231 /// \brief A Counter mapping context is used to connect the counters,
232 /// expressions and the obtained counter values.
233 class CounterMappingContext {
234 ArrayRef<CounterExpression> Expressions;
235 ArrayRef<uint64_t> CounterValues;
238 CounterMappingContext(ArrayRef<CounterExpression> Expressions,
239 ArrayRef<uint64_t> CounterValues = ArrayRef<uint64_t>())
240 : Expressions(Expressions), CounterValues(CounterValues) {}
242 void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
244 void dump(const Counter &C, llvm::raw_ostream &OS) const;
245 void dump(const Counter &C) const { dump(C, dbgs()); }
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;
252 /// \brief Code coverage information for a single function.
253 struct FunctionRecord {
254 /// \brief Raw function 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;
263 FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
264 : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
266 void pushRegion(CounterMappingRegion Region, uint64_t Count) {
267 if (CountedRegions.empty())
268 ExecutionCount = Count;
269 CountedRegions.emplace_back(Region, Count);
273 /// \brief Iterator over Functions, optionally filtered to a single file.
274 class FunctionRecordIterator
275 : public iterator_facade_base<FunctionRecordIterator,
276 std::forward_iterator_tag, FunctionRecord> {
277 ArrayRef<FunctionRecord> Records;
278 ArrayRef<FunctionRecord>::iterator Current;
281 /// \brief Skip records whose primary file is not \c Filename.
282 void skipOtherFiles();
285 FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
286 StringRef Filename = "")
287 : Records(Records_), Current(Records.begin()), Filename(Filename) {
291 FunctionRecordIterator() : Current(Records.begin()) {}
293 bool operator==(const FunctionRecordIterator &RHS) const {
294 return Current == RHS.Current && Filename == RHS.Filename;
297 const FunctionRecord &operator*() const { return *Current; }
299 FunctionRecordIterator &operator++() {
300 assert(Current != Records.end() && "incremented past end");
307 /// \brief Coverage information for a macro expansion or #included file.
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.
312 struct ExpansionRecord {
313 /// \brief The abstract file this expansion covers.
315 /// \brief The region that expands to this record.
316 const CountedRegion &Region;
317 /// \brief Coverage for the expansion.
318 const FunctionRecord &Function;
320 ExpansionRecord(const CountedRegion &Region,
321 const FunctionRecord &Function)
322 : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
325 /// \brief The execution count information starting at a point in a file.
327 /// A sequence of CoverageSegments gives execution counts for a file in format
328 /// that's simple to iterate through for processing.
329 struct CoverageSegment {
330 /// \brief The line where this segment begins.
332 /// \brief The column where this segment begins.
334 /// \brief The execution count, or zero if no count was recorded.
336 /// \brief When false, the segment was uninstrumented or skipped.
338 /// \brief Whether this enters a new region or returns to a previous count.
341 CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
342 : Line(Line), Col(Col), Count(0), HasCount(false),
343 IsRegionEntry(IsRegionEntry) {}
345 CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
347 : Line(Line), Col(Col), Count(Count), HasCount(true),
348 IsRegionEntry(IsRegionEntry) {}
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);
355 void setCount(uint64_t NewCount) {
360 void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
363 /// \brief Coverage information to be processed or displayed.
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.
369 std::string Filename;
370 std::vector<CoverageSegment> Segments;
371 std::vector<ExpansionRecord> Expansions;
372 friend class CoverageMapping;
377 CoverageData(StringRef Filename) : Filename(Filename) {}
379 CoverageData(CoverageData &&RHS)
380 : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
381 Expansions(std::move(RHS.Expansions)) {}
383 /// \brief Get the name of the file this data covers.
384 StringRef getFilename() { return Filename; }
386 std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
387 std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
388 bool empty() { return Segments.empty(); }
390 /// \brief Expansions that can be further processed.
391 std::vector<ExpansionRecord> getExpansions() { return Expansions; }
394 /// \brief The mapping of profile information to coverage data.
396 /// This is the main interface to get coverage information, using a profile to
397 /// fill out execution counts.
398 class CoverageMapping {
399 std::vector<FunctionRecord> Functions;
400 unsigned MismatchedFunctionCount;
402 CoverageMapping() : MismatchedFunctionCount(0) {}
405 /// \brief Load the coverage mapping using the given readers.
406 static ErrorOr<std::unique_ptr<CoverageMapping>>
407 load(CoverageMappingReader &CoverageReader,
408 IndexedInstrProfReader &ProfileReader);
410 /// \brief Load the coverage mapping from the given files.
411 static ErrorOr<std::unique_ptr<CoverageMapping>>
412 load(StringRef ObjectFilename, StringRef ProfileFilename,
413 Triple::ArchType Arch = Triple::ArchType::UnknownArch);
415 /// \brief The number of functions that couldn't have their profiles mapped.
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; }
421 /// \brief Returns the list of files that are covered.
422 std::vector<StringRef> getUniqueSourceFiles() const;
424 /// \brief Get the coverage for a particular file.
426 /// The given filename must be the name as recorded in the coverage
427 /// information. That is, only names returned from getUniqueSourceFiles will
429 CoverageData getCoverageForFile(StringRef Filename);
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());
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());
444 /// \brief Get the list of function instantiations in the file.
446 /// Fucntions 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);
450 /// \brief Get the coverage for a particular function.
451 CoverageData getCoverageForFunction(const FunctionRecord &Function);
453 /// \brief Get the coverage for an expansion within a coverage set.
454 CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
457 } // end namespace coverage
459 /// \brief Provide DenseMapInfo for CounterExpression
460 template<> 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));
468 static inline coverage::CounterExpression getTombstoneKey() {
469 using namespace coverage;
470 return CounterExpression(CounterExpression::ExprKind::Add,
471 Counter::getCounter(~0U),
472 Counter::getCounter(~0U));
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()));
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;
488 } // end namespace llvm
490 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_