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/iterator.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/ErrorOr.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include <system_error>
28 class IndexedInstrProfReader;
31 class ObjectFileCoverageMappingReader;
33 class CoverageMapping;
34 struct CounterExpressions;
36 enum CoverageMappingVersion { CoverageMappingVersion1 };
38 /// \brief A Counter is an abstract value that describes how to compute the
39 /// execution count for a region of code using the collected profile count data.
41 enum CounterKind { Zero, CounterValueReference, Expression };
42 static const unsigned EncodingTagBits = 2;
43 static const unsigned EncodingTagMask = 0x3;
44 static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
51 Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
54 Counter() : Kind(Zero), ID(0) {}
56 CounterKind getKind() const { return Kind; }
58 bool isZero() const { return Kind == Zero; }
60 bool isExpression() const { return Kind == Expression; }
62 unsigned getCounterID() const { return ID; }
64 unsigned getExpressionID() const { return ID; }
66 friend bool operator==(const Counter &LHS, const Counter &RHS) {
67 return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
70 friend bool operator!=(const Counter &LHS, const Counter &RHS) {
74 friend bool operator<(const Counter &LHS, const Counter &RHS) {
75 return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
78 /// \brief Return the counter that represents the number zero.
79 static Counter getZero() { return Counter(); }
81 /// \brief Return the counter that corresponds to a specific profile counter.
82 static Counter getCounter(unsigned CounterId) {
83 return Counter(CounterValueReference, CounterId);
86 /// \brief Return the counter that corresponds to a specific
87 /// addition counter expression.
88 static Counter getExpression(unsigned ExpressionId) {
89 return Counter(Expression, ExpressionId);
93 /// \brief A Counter expression is a value that represents an arithmetic
94 /// operation with two counters.
95 struct CounterExpression {
96 enum ExprKind { Subtract, Add };
100 CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
101 : Kind(Kind), LHS(LHS), RHS(RHS) {}
104 /// \brief A Counter expression builder is used to construct the
105 /// counter expressions. It avoids unecessary duplication
106 /// and simplifies algebraic expressions.
107 class CounterExpressionBuilder {
108 /// \brief A list of all the counter expressions
109 std::vector<CounterExpression> Expressions;
110 /// \brief A lookup table for the index of a given expression.
111 llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
113 /// \brief Return the counter which corresponds to the given expression.
115 /// If the given expression is already stored in the builder, a counter
116 /// that references that expression is returned. Otherwise, the given
117 /// expression is added to the builder's collection of expressions.
118 Counter get(const CounterExpression &E);
120 /// \brief Gather the terms of the expression tree for processing.
122 /// This collects each addition and subtraction referenced by the counter into
123 /// a sequence that can be sorted and combined to build a simplified counter
125 void extractTerms(Counter C, int Sign,
126 SmallVectorImpl<std::pair<unsigned, int>> &Terms);
128 /// \brief Simplifies the given expression tree
129 /// by getting rid of algebraically redundant operations.
130 Counter simplify(Counter ExpressionTree);
133 ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
135 /// \brief Return a counter that represents the expression
136 /// that adds LHS and RHS.
137 Counter add(Counter LHS, Counter RHS);
139 /// \brief Return a counter that represents the expression
140 /// that subtracts RHS from LHS.
141 Counter subtract(Counter LHS, Counter RHS);
144 /// \brief A Counter mapping region associates a source range with
145 /// a specific counter.
146 struct CounterMappingRegion {
148 /// \brief A CodeRegion associates some code with a counter
151 /// \brief An ExpansionRegion represents a file expansion region that
152 /// associates a source range with the expansion of a virtual source file,
153 /// such as for a macro instantiation or #include file.
156 /// \brief A SkippedRegion represents a source range with code that
157 /// was skipped by a preprocessor or similar means.
162 unsigned FileID, ExpandedFileID;
163 unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
166 CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
167 unsigned LineStart, unsigned ColumnStart,
168 unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
169 : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
170 LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
171 ColumnEnd(ColumnEnd), Kind(Kind) {}
173 static CounterMappingRegion
174 makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
175 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
176 return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
177 LineEnd, ColumnEnd, CodeRegion);
180 static CounterMappingRegion
181 makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
182 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
183 return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
184 ColumnStart, LineEnd, ColumnEnd,
188 static CounterMappingRegion
189 makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
190 unsigned LineEnd, unsigned ColumnEnd) {
191 return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
192 LineEnd, ColumnEnd, SkippedRegion);
196 inline std::pair<unsigned, unsigned> startLoc() const {
197 return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
200 inline std::pair<unsigned, unsigned> endLoc() const {
201 return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
204 bool operator<(const CounterMappingRegion &Other) const {
205 if (FileID != Other.FileID)
206 return FileID < Other.FileID;
207 return startLoc() < Other.startLoc();
210 bool contains(const CounterMappingRegion &Other) const {
211 if (FileID != Other.FileID)
213 if (startLoc() > Other.startLoc())
215 if (endLoc() < Other.endLoc())
221 /// \brief Associates a source range with an execution count.
222 struct CountedRegion : public CounterMappingRegion {
223 uint64_t ExecutionCount;
225 CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
226 : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
229 /// \brief A Counter mapping context is used to connect the counters,
230 /// expressions and the obtained counter values.
231 class CounterMappingContext {
232 ArrayRef<CounterExpression> Expressions;
233 ArrayRef<uint64_t> CounterValues;
236 CounterMappingContext(ArrayRef<CounterExpression> Expressions,
237 ArrayRef<uint64_t> CounterValues = ArrayRef<uint64_t>())
238 : Expressions(Expressions), CounterValues(CounterValues) {}
240 void dump(const Counter &C, llvm::raw_ostream &OS) const;
241 void dump(const Counter &C) const { dump(C, dbgs()); }
243 /// \brief Return the number of times that a region of code associated with
244 /// this counter was executed.
245 ErrorOr<int64_t> evaluate(const Counter &C) const;
248 /// \brief Code coverage information for a single function.
249 struct FunctionRecord {
250 /// \brief Raw function name.
252 /// \brief Associated files.
253 std::vector<std::string> Filenames;
254 /// \brief Regions in the function along with their counts.
255 std::vector<CountedRegion> CountedRegions;
256 /// \brief The number of times this function was executed.
257 uint64_t ExecutionCount;
259 FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames,
260 uint64_t ExecutionCount)
261 : Name(Name), Filenames(Filenames.begin(), Filenames.end()),
262 ExecutionCount(ExecutionCount) {}
265 /// \brief Iterator over Functions, optionally filtered to a single file.
266 class FunctionRecordIterator
267 : public iterator_facade_base<FunctionRecordIterator,
268 std::forward_iterator_tag, FunctionRecord> {
269 ArrayRef<FunctionRecord> Records;
270 ArrayRef<FunctionRecord>::iterator Current;
273 /// \brief Skip records whose primary file is not \c Filename.
274 void skipOtherFiles();
277 FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
278 StringRef Filename = "")
279 : Records(Records_), Current(Records.begin()), Filename(Filename) {
283 FunctionRecordIterator() : Current(Records.begin()) {}
285 bool operator==(const FunctionRecordIterator &RHS) const {
286 return Current == RHS.Current && Filename == RHS.Filename;
289 const FunctionRecord &operator*() const { return *Current; }
291 FunctionRecordIterator &operator++() {
292 assert(Current != Records.end() && "incremented past end");
299 /// \brief Coverage information for a macro expansion or #included file.
301 /// When covered code has pieces that can be expanded for more detail, such as a
302 /// preprocessor macro use and its definition, these are represented as
303 /// expansions whose coverage can be looked up independently.
304 struct ExpansionRecord {
305 /// \brief The abstract file this expansion covers.
307 /// \brief The region that expands to this record.
308 const CountedRegion &Region;
309 /// \brief Coverage for the expansion.
310 const FunctionRecord &Function;
312 ExpansionRecord(const CountedRegion &Region,
313 const FunctionRecord &Function)
314 : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
317 /// \brief The execution count information starting at a point in a file.
319 /// A sequence of CoverageSegments gives execution counts for a file in format
320 /// that's simple to iterate through for processing.
321 struct CoverageSegment {
322 /// \brief The line where this segment begins.
324 /// \brief The column where this segment begins.
326 /// \brief The execution count, or zero if no count was recorded.
328 /// \brief When false, the segment was uninstrumented or skipped.
330 /// \brief Whether this enters a new region or returns to a previous count.
333 CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
334 : Line(Line), Col(Col), Count(0), HasCount(false),
335 IsRegionEntry(IsRegionEntry) {}
336 void setCount(uint64_t NewCount) {
340 void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
343 /// \brief Coverage information to be processed or displayed.
345 /// This represents the coverage of an entire file, expansion, or function. It
346 /// provides a sequence of CoverageSegments to iterate through, as well as the
347 /// list of expansions that can be further processed.
349 std::string Filename;
350 std::vector<CoverageSegment> Segments;
351 std::vector<ExpansionRecord> Expansions;
352 friend class CoverageMapping;
357 CoverageData(StringRef Filename) : Filename(Filename) {}
359 CoverageData(CoverageData &&RHS)
360 : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
361 Expansions(std::move(RHS.Expansions)) {}
363 /// \brief Get the name of the file this data covers.
364 StringRef getFilename() { return Filename; }
366 std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
367 std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
368 bool empty() { return Segments.empty(); }
370 /// \brief Expansions that can be further processed.
371 std::vector<ExpansionRecord> getExpansions() { return Expansions; }
374 /// \brief The mapping of profile information to coverage data.
376 /// This is the main interface to get coverage information, using a profile to
377 /// fill out execution counts.
378 class CoverageMapping {
379 std::vector<FunctionRecord> Functions;
380 unsigned MismatchedFunctionCount;
382 CoverageMapping() : MismatchedFunctionCount(0) {}
385 /// \brief Load the coverage mapping using the given readers.
386 static ErrorOr<std::unique_ptr<CoverageMapping>>
387 load(ObjectFileCoverageMappingReader &CoverageReader,
388 IndexedInstrProfReader &ProfileReader);
390 /// \brief Load the coverage mapping from the given files.
391 static ErrorOr<std::unique_ptr<CoverageMapping>>
392 load(StringRef ObjectFilename, StringRef ProfileFilename);
394 /// \brief The number of functions that couldn't have their profiles mapped.
396 /// This is a count of functions whose profile is out of date or otherwise
397 /// can't be associated with any coverage information.
398 unsigned getMismatchedCount() { return MismatchedFunctionCount; }
400 /// \brief Returns the list of files that are covered.
401 std::vector<StringRef> getUniqueSourceFiles() const;
403 /// \brief Get the coverage for a particular file.
405 /// The given filename must be the name as recorded in the coverage
406 /// information. That is, only names returned from getUniqueSourceFiles will
408 CoverageData getCoverageForFile(StringRef Filename);
410 /// \brief Gets all of the functions covered by this profile.
411 iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
412 return make_range(FunctionRecordIterator(Functions),
413 FunctionRecordIterator());
416 /// \brief Gets all of the functions in a particular file.
417 iterator_range<FunctionRecordIterator>
418 getCoveredFunctions(StringRef Filename) const {
419 return make_range(FunctionRecordIterator(Functions, Filename),
420 FunctionRecordIterator());
423 /// \brief Get the list of function instantiations in the file.
425 /// Fucntions that are instantiated more than once, such as C++ template
426 /// specializations, have distinct coverage records for each instantiation.
427 std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
429 /// \brief Get the coverage for a particular function.
430 CoverageData getCoverageForFunction(const FunctionRecord &Function);
432 /// \brief Get the coverage for an expansion within a coverage set.
433 CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
436 } // end namespace coverage
438 /// \brief Provide DenseMapInfo for CounterExpression
439 template<> struct DenseMapInfo<coverage::CounterExpression> {
440 static inline coverage::CounterExpression getEmptyKey() {
441 using namespace coverage;
442 return CounterExpression(CounterExpression::ExprKind::Subtract,
443 Counter::getCounter(~0U),
444 Counter::getCounter(~0U));
447 static inline coverage::CounterExpression getTombstoneKey() {
448 using namespace coverage;
449 return CounterExpression(CounterExpression::ExprKind::Add,
450 Counter::getCounter(~0U),
451 Counter::getCounter(~0U));
454 static unsigned getHashValue(const coverage::CounterExpression &V) {
455 return static_cast<unsigned>(
456 hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
457 V.RHS.getKind(), V.RHS.getCounterID()));
460 static bool isEqual(const coverage::CounterExpression &LHS,
461 const coverage::CounterExpression &RHS) {
462 return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
467 } // end namespace llvm
469 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_