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/ProfileData/InstrProf.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/Endian.h"
26 #include "llvm/Support/ErrorOr.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include <system_error>
33 enum class coveragemap_error {
41 } // end of coverage namespace.
46 struct is_error_code_enum<llvm::coverage::coveragemap_error> : std::true_type {
51 class IndexedInstrProfReader;
54 class CoverageMappingReader;
56 class CoverageMapping;
57 struct CounterExpressions;
59 /// \brief A Counter is an abstract value that describes how to compute the
60 /// execution count for a region of code using the collected profile count data.
62 enum CounterKind { Zero, CounterValueReference, Expression };
63 static const unsigned EncodingTagBits = 2;
64 static const unsigned EncodingTagMask = 0x3;
65 static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
72 Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
75 Counter() : Kind(Zero), ID(0) {}
77 CounterKind getKind() const { return Kind; }
79 bool isZero() const { return Kind == Zero; }
81 bool isExpression() const { return Kind == Expression; }
83 unsigned getCounterID() const { return ID; }
85 unsigned getExpressionID() const { return ID; }
87 friend bool operator==(const Counter &LHS, const Counter &RHS) {
88 return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
91 friend bool operator!=(const Counter &LHS, const Counter &RHS) {
95 friend bool operator<(const Counter &LHS, const Counter &RHS) {
96 return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
99 /// \brief Return the counter that represents the number zero.
100 static Counter getZero() { return Counter(); }
102 /// \brief Return the counter that corresponds to a specific profile counter.
103 static Counter getCounter(unsigned CounterId) {
104 return Counter(CounterValueReference, CounterId);
107 /// \brief Return the counter that corresponds to a specific
108 /// addition counter expression.
109 static Counter getExpression(unsigned ExpressionId) {
110 return Counter(Expression, ExpressionId);
114 /// \brief A Counter expression is a value that represents an arithmetic
115 /// operation with two counters.
116 struct CounterExpression {
117 enum ExprKind { Subtract, Add };
121 CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
122 : Kind(Kind), LHS(LHS), RHS(RHS) {}
125 /// \brief A Counter expression builder is used to construct the
126 /// counter expressions. It avoids unnecessary duplication
127 /// and simplifies algebraic expressions.
128 class CounterExpressionBuilder {
129 /// \brief A list of all the counter expressions
130 std::vector<CounterExpression> Expressions;
131 /// \brief A lookup table for the index of a given expression.
132 llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
134 /// \brief Return the counter which corresponds to the given expression.
136 /// If the given expression is already stored in the builder, a counter
137 /// that references that expression is returned. Otherwise, the given
138 /// expression is added to the builder's collection of expressions.
139 Counter get(const CounterExpression &E);
141 /// \brief Gather the terms of the expression tree for processing.
143 /// This collects each addition and subtraction referenced by the counter into
144 /// a sequence that can be sorted and combined to build a simplified counter
146 void extractTerms(Counter C, int Sign,
147 SmallVectorImpl<std::pair<unsigned, int>> &Terms);
149 /// \brief Simplifies the given expression tree
150 /// by getting rid of algebraically redundant operations.
151 Counter simplify(Counter ExpressionTree);
154 ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
156 /// \brief Return a counter that represents the expression
157 /// that adds LHS and RHS.
158 Counter add(Counter LHS, Counter RHS);
160 /// \brief Return a counter that represents the expression
161 /// that subtracts RHS from LHS.
162 Counter subtract(Counter LHS, Counter RHS);
165 /// \brief A Counter mapping region associates a source range with
166 /// a specific counter.
167 struct CounterMappingRegion {
169 /// \brief A CodeRegion associates some code with a counter
172 /// \brief An ExpansionRegion represents a file expansion region that
173 /// associates a source range with the expansion of a virtual source file,
174 /// such as for a macro instantiation or #include file.
177 /// \brief A SkippedRegion represents a source range with code that
178 /// was skipped by a preprocessor or similar means.
183 unsigned FileID, ExpandedFileID;
184 unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
187 CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
188 unsigned LineStart, unsigned ColumnStart,
189 unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
190 : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
191 LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
192 ColumnEnd(ColumnEnd), Kind(Kind) {}
194 static CounterMappingRegion
195 makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
196 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
197 return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
198 LineEnd, ColumnEnd, CodeRegion);
201 static CounterMappingRegion
202 makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
203 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
204 return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
205 ColumnStart, LineEnd, ColumnEnd,
209 static CounterMappingRegion
210 makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
211 unsigned LineEnd, unsigned ColumnEnd) {
212 return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
213 LineEnd, ColumnEnd, SkippedRegion);
217 inline std::pair<unsigned, unsigned> startLoc() const {
218 return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
221 inline std::pair<unsigned, unsigned> endLoc() const {
222 return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
225 bool operator<(const CounterMappingRegion &Other) const {
226 if (FileID != Other.FileID)
227 return FileID < Other.FileID;
228 return startLoc() < Other.startLoc();
231 bool contains(const CounterMappingRegion &Other) const {
232 if (FileID != Other.FileID)
234 if (startLoc() > Other.startLoc())
236 if (endLoc() < Other.endLoc())
242 /// \brief Associates a source range with an execution count.
243 struct CountedRegion : public CounterMappingRegion {
244 uint64_t ExecutionCount;
246 CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
247 : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
250 /// \brief A Counter mapping context is used to connect the counters,
251 /// expressions and the obtained counter values.
252 class CounterMappingContext {
253 ArrayRef<CounterExpression> Expressions;
254 ArrayRef<uint64_t> CounterValues;
257 CounterMappingContext(ArrayRef<CounterExpression> Expressions,
258 ArrayRef<uint64_t> CounterValues = None)
259 : Expressions(Expressions), CounterValues(CounterValues) {}
261 void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
263 void dump(const Counter &C, llvm::raw_ostream &OS) const;
264 void dump(const Counter &C) const { dump(C, dbgs()); }
266 /// \brief Return the number of times that a region of code associated with
267 /// this counter was executed.
268 ErrorOr<int64_t> evaluate(const Counter &C) const;
271 /// \brief Code coverage information for a single function.
272 struct FunctionRecord {
273 /// \brief Raw function name.
275 /// \brief Associated files.
276 std::vector<std::string> Filenames;
277 /// \brief Regions in the function along with their counts.
278 std::vector<CountedRegion> CountedRegions;
279 /// \brief The number of times this function was executed.
280 uint64_t ExecutionCount;
282 FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
283 : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
285 void pushRegion(CounterMappingRegion Region, uint64_t Count) {
286 if (CountedRegions.empty())
287 ExecutionCount = Count;
288 CountedRegions.emplace_back(Region, Count);
292 /// \brief Iterator over Functions, optionally filtered to a single file.
293 class FunctionRecordIterator
294 : public iterator_facade_base<FunctionRecordIterator,
295 std::forward_iterator_tag, FunctionRecord> {
296 ArrayRef<FunctionRecord> Records;
297 ArrayRef<FunctionRecord>::iterator Current;
300 /// \brief Skip records whose primary file is not \c Filename.
301 void skipOtherFiles();
304 FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
305 StringRef Filename = "")
306 : Records(Records_), Current(Records.begin()), Filename(Filename) {
310 FunctionRecordIterator() : Current(Records.begin()) {}
312 bool operator==(const FunctionRecordIterator &RHS) const {
313 return Current == RHS.Current && Filename == RHS.Filename;
316 const FunctionRecord &operator*() const { return *Current; }
318 FunctionRecordIterator &operator++() {
319 assert(Current != Records.end() && "incremented past end");
326 /// \brief Coverage information for a macro expansion or #included file.
328 /// When covered code has pieces that can be expanded for more detail, such as a
329 /// preprocessor macro use and its definition, these are represented as
330 /// expansions whose coverage can be looked up independently.
331 struct ExpansionRecord {
332 /// \brief The abstract file this expansion covers.
334 /// \brief The region that expands to this record.
335 const CountedRegion &Region;
336 /// \brief Coverage for the expansion.
337 const FunctionRecord &Function;
339 ExpansionRecord(const CountedRegion &Region,
340 const FunctionRecord &Function)
341 : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
344 /// \brief The execution count information starting at a point in a file.
346 /// A sequence of CoverageSegments gives execution counts for a file in format
347 /// that's simple to iterate through for processing.
348 struct CoverageSegment {
349 /// \brief The line where this segment begins.
351 /// \brief The column where this segment begins.
353 /// \brief The execution count, or zero if no count was recorded.
355 /// \brief When false, the segment was uninstrumented or skipped.
357 /// \brief Whether this enters a new region or returns to a previous count.
360 CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
361 : Line(Line), Col(Col), Count(0), HasCount(false),
362 IsRegionEntry(IsRegionEntry) {}
364 CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
366 : Line(Line), Col(Col), Count(Count), HasCount(true),
367 IsRegionEntry(IsRegionEntry) {}
369 friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
370 return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
371 std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
374 void setCount(uint64_t NewCount) {
379 void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
382 /// \brief Coverage information to be processed or displayed.
384 /// This represents the coverage of an entire file, expansion, or function. It
385 /// provides a sequence of CoverageSegments to iterate through, as well as the
386 /// list of expansions that can be further processed.
388 std::string Filename;
389 std::vector<CoverageSegment> Segments;
390 std::vector<ExpansionRecord> Expansions;
391 friend class CoverageMapping;
396 CoverageData(StringRef Filename) : Filename(Filename) {}
398 CoverageData(CoverageData &&RHS)
399 : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
400 Expansions(std::move(RHS.Expansions)) {}
402 /// \brief Get the name of the file this data covers.
403 StringRef getFilename() { return Filename; }
405 std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
406 std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
407 bool empty() { return Segments.empty(); }
409 /// \brief Expansions that can be further processed.
410 std::vector<ExpansionRecord> getExpansions() { return Expansions; }
413 /// \brief The mapping of profile information to coverage data.
415 /// This is the main interface to get coverage information, using a profile to
416 /// fill out execution counts.
417 class CoverageMapping {
418 std::vector<FunctionRecord> Functions;
419 unsigned MismatchedFunctionCount;
421 CoverageMapping() : MismatchedFunctionCount(0) {}
424 /// \brief Load the coverage mapping using the given readers.
425 static ErrorOr<std::unique_ptr<CoverageMapping>>
426 load(CoverageMappingReader &CoverageReader,
427 IndexedInstrProfReader &ProfileReader);
429 /// \brief Load the coverage mapping from the given files.
430 static ErrorOr<std::unique_ptr<CoverageMapping>>
431 load(StringRef ObjectFilename, StringRef ProfileFilename,
432 StringRef Arch = StringRef());
434 /// \brief The number of functions that couldn't have their profiles mapped.
436 /// This is a count of functions whose profile is out of date or otherwise
437 /// can't be associated with any coverage information.
438 unsigned getMismatchedCount() { return MismatchedFunctionCount; }
440 /// \brief Returns the list of files that are covered.
441 std::vector<StringRef> getUniqueSourceFiles() const;
443 /// \brief Get the coverage for a particular file.
445 /// The given filename must be the name as recorded in the coverage
446 /// information. That is, only names returned from getUniqueSourceFiles will
448 CoverageData getCoverageForFile(StringRef Filename);
450 /// \brief Gets all of the functions covered by this profile.
451 iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
452 return make_range(FunctionRecordIterator(Functions),
453 FunctionRecordIterator());
456 /// \brief Gets all of the functions in a particular file.
457 iterator_range<FunctionRecordIterator>
458 getCoveredFunctions(StringRef Filename) const {
459 return make_range(FunctionRecordIterator(Functions, Filename),
460 FunctionRecordIterator());
463 /// \brief Get the list of function instantiations in the file.
465 /// Functions that are instantiated more than once, such as C++ template
466 /// specializations, have distinct coverage records for each instantiation.
467 std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
469 /// \brief Get the coverage for a particular function.
470 CoverageData getCoverageForFunction(const FunctionRecord &Function);
472 /// \brief Get the coverage for an expansion within a coverage set.
473 CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
476 const std::error_category &coveragemap_category();
478 inline std::error_code make_error_code(coveragemap_error E) {
479 return std::error_code(static_cast<int>(E), coveragemap_category());
482 // Profile coverage map has the following layout:
483 // [CoverageMapFileHeader]
485 // [CovMapFunctionRecord]
486 // [CovMapFunctionRecord]
489 // [Encoded Region Mapping Data]
491 template <class IntPtrT> struct CovMapFunctionRecord {
492 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
493 #include "llvm/ProfileData/InstrProfData.inc"
495 // Return the structural hash associated with the function.
496 template <support::endianness Endian> uint64_t getFuncHash() const {
497 return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
499 // Return the coverage map data size for the funciton.
500 template <support::endianness Endian> uint32_t getDataSize() const {
501 return support::endian::byte_swap<uint32_t, Endian>(DataSize);
503 // Return function lookup key. The value is consider opaque.
504 template <support::endianness Endian> IntPtrT getFuncNameRef() const {
505 return support::endian::byte_swap<IntPtrT, Endian>(NamePtr);
507 // Return the PGO name of the function */
508 template <support::endianness Endian>
509 std::error_code getFuncName(InstrProfSymtab &ProfileNames,
510 StringRef &FuncName) const {
511 IntPtrT NameRef = getFuncNameRef<Endian>();
512 uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize);
513 FuncName = ProfileNames.getFuncName(NameRef, NameS);
514 if (NameS && FuncName.empty())
515 return coveragemap_error::malformed;
516 return std::error_code();
519 // Per module coverage mapping data header, i.e. CoverageMapFileHeader
521 struct CovMapHeader {
522 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
523 #include "llvm/ProfileData/InstrProfData.inc"
524 template <support::endianness Endian> uint32_t getNRecords() const {
525 return support::endian::byte_swap<uint32_t, Endian>(NRecords);
527 template <support::endianness Endian> uint32_t getFilenamesSize() const {
528 return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
530 template <support::endianness Endian> uint32_t getCoverageSize() const {
531 return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
533 template <support::endianness Endian> uint32_t getVersion() const {
534 return support::endian::byte_swap<uint32_t, Endian>(Version);
540 enum CoverageMappingVersion {
541 CoverageMappingVersion1 = 0,
542 // The current versin is Version1
543 CoverageMappingCurrentVersion = INSTR_PROF_COVMAP_VERSION
546 } // end namespace coverage
548 /// \brief Provide DenseMapInfo for CounterExpression
549 template<> struct DenseMapInfo<coverage::CounterExpression> {
550 static inline coverage::CounterExpression getEmptyKey() {
551 using namespace coverage;
552 return CounterExpression(CounterExpression::ExprKind::Subtract,
553 Counter::getCounter(~0U),
554 Counter::getCounter(~0U));
557 static inline coverage::CounterExpression getTombstoneKey() {
558 using namespace coverage;
559 return CounterExpression(CounterExpression::ExprKind::Add,
560 Counter::getCounter(~0U),
561 Counter::getCounter(~0U));
564 static unsigned getHashValue(const coverage::CounterExpression &V) {
565 return static_cast<unsigned>(
566 hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
567 V.RHS.getKind(), V.RHS.getCounterID()));
570 static bool isEqual(const coverage::CounterExpression &LHS,
571 const coverage::CounterExpression &RHS) {
572 return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
576 } // end namespace llvm
578 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_