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/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>
  29 #include <tuple>
  30
  31 namespace llvm {
  32 namespace coverage {
  33 enum class coveragemap_error {
  34   success = 0,
  35   eof,
  36   no_data_found,
  37   unsupported_version,
  38   truncated,
  39   malformed
  40 };
  41 } // end of coverage namespace.
  42 }
  43
  44 namespace std {
  45 template <>
  46 struct is_error_code_enum<llvm::coverage::coveragemap_error> : std::true_type {
  47 };
  48 }
  49
  50 namespace llvm {
  51 class IndexedInstrProfReader;
  52 namespace coverage {
  53
  54 class CoverageMappingReader;
  55
  56 class CoverageMapping;
  57 struct CounterExpressions;
  58
  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.
  61 struct Counter {
  62   enum CounterKind { Zero, CounterValueReference, Expression };
  63   static const unsigned EncodingTagBits = 2;
  64   static const unsigned EncodingTagMask = 0x3;
  65   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
  66       EncodingTagBits + 1;
  67
  68 private:
  69   CounterKind Kind;
  70   unsigned ID;
  71
  72   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
  73
  74 public:
  75   Counter() : Kind(Zero), ID(0) {}
  76
  77   CounterKind getKind() const { return Kind; }
  78
  79   bool isZero() const { return Kind == Zero; }
  80
  81   bool isExpression() const { return Kind == Expression; }
  82
  83   unsigned getCounterID() const { return ID; }
  84
  85   unsigned getExpressionID() const { return ID; }
  86
  87   friend bool operator==(const Counter &LHS, const Counter &RHS) {
  88     return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
  89   }
  90
  91   friend bool operator!=(const Counter &LHS, const Counter &RHS) {
  92     return !(LHS == RHS);
  93   }
  94
  95   friend bool operator<(const Counter &LHS, const Counter &RHS) {
  96     return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  97   }
  98
  99   /// \brief Return the counter that represents the number zero.
 100   static Counter getZero() { return Counter(); }
 101
 102   /// \brief Return the counter that corresponds to a specific profile counter.
 103   static Counter getCounter(unsigned CounterId) {
 104     return Counter(CounterValueReference, CounterId);
 105   }
 106
 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);
 111   }
 112 };
 113
 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 };
 118   ExprKind Kind;
 119   Counter LHS, RHS;
 120
 121   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
 122       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 123 };
 124
 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;
 133
 134   /// \brief Return the counter which corresponds to the given expression.
 135   ///
 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);
 140
 141   /// \brief Gather the terms of the expression tree for processing.
 142   ///
 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
 145   /// expression.
 146   void extractTerms(Counter C, int Sign,
 147                     SmallVectorImpl<std::pair<unsigned, int>> &Terms);
 148
 149   /// \brief Simplifies the given expression tree
 150   /// by getting rid of algebraically redundant operations.
 151   Counter simplify(Counter ExpressionTree);
 152
 153 public:
 154   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 155
 156   /// \brief Return a counter that represents the expression
 157   /// that adds LHS and RHS.
 158   Counter add(Counter LHS, Counter RHS);
 159
 160   /// \brief Return a counter that represents the expression
 161   /// that subtracts RHS from LHS.
 162   Counter subtract(Counter LHS, Counter RHS);
 163 };
 164
 165 /// \brief A Counter mapping region associates a source range with
 166 /// a specific counter.
 167 struct CounterMappingRegion {
 168   enum RegionKind {
 169     /// \brief A CodeRegion associates some code with a counter
 170     CodeRegion,
 171
 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.
 175     ExpansionRegion,
 176
 177     /// \brief A SkippedRegion represents a source range with code that
 178     /// was skipped by a preprocessor or similar means.
 179     SkippedRegion
 180   };
 181
 182   Counter Count;
 183   unsigned FileID, ExpandedFileID;
 184   unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
 185   RegionKind Kind;
 186
 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) {}
 193
 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);
 199   }
 200
 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,
 206                                 ExpansionRegion);
 207   }
 208
 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);
 214   }
 215
 216
 217   inline std::pair<unsigned, unsigned> startLoc() const {
 218     return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
 219   }
 220
 221   inline std::pair<unsigned, unsigned> endLoc() const {
 222     return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
 223   }
 224
 225   bool operator<(const CounterMappingRegion &Other) const {
 226     if (FileID != Other.FileID)
 227       return FileID < Other.FileID;
 228     return startLoc() < Other.startLoc();
 229   }
 230
 231   bool contains(const CounterMappingRegion &Other) const {
 232     if (FileID != Other.FileID)
 233       return false;
 234     if (startLoc() > Other.startLoc())
 235       return false;
 236     if (endLoc() < Other.endLoc())
 237       return false;
 238     return true;
 239   }
 240 };
 241
 242 /// \brief Associates a source range with an execution count.
 243 struct CountedRegion : public CounterMappingRegion {
 244   uint64_t ExecutionCount;
 245
 246   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
 247       : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
 248 };
 249
 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;
 255
 256 public:
 257   CounterMappingContext(ArrayRef<CounterExpression> Expressions,
 258                         ArrayRef<uint64_t> CounterValues = None)
 259       : Expressions(Expressions), CounterValues(CounterValues) {}
 260
 261   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
 262
 263   void dump(const Counter &C, llvm::raw_ostream &OS) const;
 264   void dump(const Counter &C) const { dump(C, dbgs()); }
 265
 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;
 269 };
 270
 271 /// \brief Code coverage information for a single function.
 272 struct FunctionRecord {
 273   /// \brief Raw function name.
 274   std::string 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;
 281
 282   FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
 283       : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
 284
 285   void pushRegion(CounterMappingRegion Region, uint64_t Count) {
 286     if (CountedRegions.empty())
 287       ExecutionCount = Count;
 288     CountedRegions.emplace_back(Region, Count);
 289   }
 290 };
 291
 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;
 298   StringRef Filename;
 299
 300   /// \brief Skip records whose primary file is not \c Filename.
 301   void skipOtherFiles();
 302
 303 public:
 304   FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
 305                          StringRef Filename = "")
 306       : Records(Records_), Current(Records.begin()), Filename(Filename) {
 307     skipOtherFiles();
 308   }
 309
 310   FunctionRecordIterator() : Current(Records.begin()) {}
 311
 312   bool operator==(const FunctionRecordIterator &RHS) const {
 313     return Current == RHS.Current && Filename == RHS.Filename;
 314   }
 315
 316   const FunctionRecord &operator*() const { return *Current; }
 317
 318   FunctionRecordIterator &operator++() {
 319     assert(Current != Records.end() && "incremented past end");
 320     ++Current;
 321     skipOtherFiles();
 322     return *this;
 323   }
 324 };
 325
 326 /// \brief Coverage information for a macro expansion or #included file.
 327 ///
 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.
 333   unsigned FileID;
 334   /// \brief The region that expands to this record.
 335   const CountedRegion &Region;
 336   /// \brief Coverage for the expansion.
 337   const FunctionRecord &Function;
 338
 339   ExpansionRecord(const CountedRegion &Region,
 340                   const FunctionRecord &Function)
 341       : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
 342 };
 343
 344 /// \brief The execution count information starting at a point in a file.
 345 ///
 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.
 350   unsigned Line;
 351   /// \brief The column where this segment begins.
 352   unsigned Col;
 353   /// \brief The execution count, or zero if no count was recorded.
 354   uint64_t Count;
 355   /// \brief When false, the segment was uninstrumented or skipped.
 356   bool HasCount;
 357   /// \brief Whether this enters a new region or returns to a previous count.
 358   bool IsRegionEntry;
 359
 360   CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
 361       : Line(Line), Col(Col), Count(0), HasCount(false),
 362         IsRegionEntry(IsRegionEntry) {}
 363
 364   CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
 365                   bool IsRegionEntry)
 366       : Line(Line), Col(Col), Count(Count), HasCount(true),
 367         IsRegionEntry(IsRegionEntry) {}
 368
 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);
 372   }
 373
 374   void setCount(uint64_t NewCount) {
 375     Count = NewCount;
 376     HasCount = true;
 377   }
 378
 379   void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
 380 };
 381
 382 /// \brief Coverage information to be processed or displayed.
 383 ///
 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.
 387 class CoverageData {
 388   std::string Filename;
 389   std::vector<CoverageSegment> Segments;
 390   std::vector<ExpansionRecord> Expansions;
 391   friend class CoverageMapping;
 392
 393 public:
 394   CoverageData() {}
 395
 396   CoverageData(StringRef Filename) : Filename(Filename) {}
 397
 398   CoverageData(CoverageData &&RHS)
 399       : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
 400         Expansions(std::move(RHS.Expansions)) {}
 401
 402   /// \brief Get the name of the file this data covers.
 403   StringRef getFilename() { return Filename; }
 404
 405   std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
 406   std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
 407   bool empty() { return Segments.empty(); }
 408
 409   /// \brief Expansions that can be further processed.
 410   std::vector<ExpansionRecord> getExpansions() { return Expansions; }
 411 };
 412
 413 /// \brief The mapping of profile information to coverage data.
 414 ///
 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;
 420
 421   CoverageMapping() : MismatchedFunctionCount(0) {}
 422
 423 public:
 424   /// \brief Load the coverage mapping using the given readers.
 425   static ErrorOr<std::unique_ptr<CoverageMapping>>
 426   load(CoverageMappingReader &CoverageReader,
 427        IndexedInstrProfReader &ProfileReader);
 428
 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());
 433
 434   /// \brief The number of functions that couldn't have their profiles mapped.
 435   ///
 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; }
 439
 440   /// \brief Returns the list of files that are covered.
 441   std::vector<StringRef> getUniqueSourceFiles() const;
 442
 443   /// \brief Get the coverage for a particular file.
 444   ///
 445   /// The given filename must be the name as recorded in the coverage
 446   /// information. That is, only names returned from getUniqueSourceFiles will
 447   /// yield a result.
 448   CoverageData getCoverageForFile(StringRef Filename);
 449
 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());
 454   }
 455
 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());
 461   }
 462
 463   /// \brief Get the list of function instantiations in the file.
 464   ///
 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);
 468
 469   /// \brief Get the coverage for a particular function.
 470   CoverageData getCoverageForFunction(const FunctionRecord &Function);
 471
 472   /// \brief Get the coverage for an expansion within a coverage set.
 473   CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
 474 };
 475
 476 const std::error_category &coveragemap_category();
 477
 478 inline std::error_code make_error_code(coveragemap_error E) {
 479   return std::error_code(static_cast<int>(E), coveragemap_category());
 480 }
 481
 482 // Profile coverage map has the following layout:
 483 // [CoverageMapFileHeader]
 484 // [ArrayStart]
 485 //  [CovMapFunctionRecord]
 486 //  [CovMapFunctionRecord]
 487 //  ...
 488 // [ArrayEnd]
 489 // [Encoded Region Mapping Data]
 490 LLVM_PACKED_START
 491 template <class IntPtrT> struct CovMapFunctionRecord {
 492 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
 493 #include "llvm/ProfileData/InstrProfData.inc"
 494
 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);
 498   }
 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);
 502   }
 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);
 506   }
 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();
 517   }
 518 };
 519 // Per module coverage mapping data header, i.e. CoverageMapFileHeader
 520 // documented above.
 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);
 526   }
 527   template <support::endianness Endian> uint32_t getFilenamesSize() const {
 528     return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
 529   }
 530   template <support::endianness Endian> uint32_t getCoverageSize() const {
 531     return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
 532   }
 533   template <support::endianness Endian> uint32_t getVersion() const {
 534     return support::endian::byte_swap<uint32_t, Endian>(Version);
 535   }
 536 };
 537
 538 LLVM_PACKED_END
 539
 540 enum CoverageMappingVersion {
 541   CoverageMappingVersion1 = 0,
 542   // The current versin is Version1
 543   CoverageMappingCurrentVersion = INSTR_PROF_COVMAP_VERSION
 544 };
 545
 546 } // end namespace coverage
 547
 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));
 555   }
 556
 557   static inline coverage::CounterExpression getTombstoneKey() {
 558     using namespace coverage;
 559     return CounterExpression(CounterExpression::ExprKind::Add,
 560                              Counter::getCounter(~0U),
 561                              Counter::getCounter(~0U));
 562   }
 563
 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()));
 568   }
 569
 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;
 573   }
 574 };
 575
 576 } // end namespace llvm
 577
 578 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_