include/llvm/ProfileData/CoverageMapping.h

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