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/Support/Debug.h"
  24 #include "llvm/Support/ErrorOr.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <system_error>
  27 #include <tuple>
  28
  29 namespace llvm {
  30 class IndexedInstrProfReader;
  31 namespace coverage {
  32
  33 class CoverageMappingReader;
  34
  35 class CoverageMapping;
  36 struct CounterExpressions;
  37
  38 enum CoverageMappingVersion { CoverageMappingVersion1 };
  39
  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.
  42 struct Counter {
  43   enum CounterKind { Zero, CounterValueReference, Expression };
  44   static const unsigned EncodingTagBits = 2;
  45   static const unsigned EncodingTagMask = 0x3;
  46   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
  47       EncodingTagBits + 1;
  48
  49 private:
  50   CounterKind Kind;
  51   unsigned ID;
  52
  53   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
  54
  55 public:
  56   Counter() : Kind(Zero), ID(0) {}
  57
  58   CounterKind getKind() const { return Kind; }
  59
  60   bool isZero() const { return Kind == Zero; }
  61
  62   bool isExpression() const { return Kind == Expression; }
  63
  64   unsigned getCounterID() const { return ID; }
  65
  66   unsigned getExpressionID() const { return ID; }
  67
  68   friend bool operator==(const Counter &LHS, const Counter &RHS) {
  69     return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
  70   }
  71
  72   friend bool operator!=(const Counter &LHS, const Counter &RHS) {
  73     return !(LHS == RHS);
  74   }
  75
  76   friend bool operator<(const Counter &LHS, const Counter &RHS) {
  77     return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  78   }
  79
  80   /// \brief Return the counter that represents the number zero.
  81   static Counter getZero() { return Counter(); }
  82
  83   /// \brief Return the counter that corresponds to a specific profile counter.
  84   static Counter getCounter(unsigned CounterId) {
  85     return Counter(CounterValueReference, CounterId);
  86   }
  87
  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);
  92   }
  93 };
  94
  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 };
  99   ExprKind Kind;
 100   Counter LHS, RHS;
 101
 102   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
 103       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 104 };
 105
 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;
 114
 115   /// \brief Return the counter which corresponds to the given expression.
 116   ///
 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);
 121
 122   /// \brief Gather the terms of the expression tree for processing.
 123   ///
 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
 126   /// expression.
 127   void extractTerms(Counter C, int Sign,
 128                     SmallVectorImpl<std::pair<unsigned, int>> &Terms);
 129
 130   /// \brief Simplifies the given expression tree
 131   /// by getting rid of algebraically redundant operations.
 132   Counter simplify(Counter ExpressionTree);
 133
 134 public:
 135   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 136
 137   /// \brief Return a counter that represents the expression
 138   /// that adds LHS and RHS.
 139   Counter add(Counter LHS, Counter RHS);
 140
 141   /// \brief Return a counter that represents the expression
 142   /// that subtracts RHS from LHS.
 143   Counter subtract(Counter LHS, Counter RHS);
 144 };
 145
 146 /// \brief A Counter mapping region associates a source range with
 147 /// a specific counter.
 148 struct CounterMappingRegion {
 149   enum RegionKind {
 150     /// \brief A CodeRegion associates some code with a counter
 151     CodeRegion,
 152
 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.
 156     ExpansionRegion,
 157
 158     /// \brief A SkippedRegion represents a source range with code that
 159     /// was skipped by a preprocessor or similar means.
 160     SkippedRegion
 161   };
 162
 163   Counter Count;
 164   unsigned FileID, ExpandedFileID;
 165   unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
 166   RegionKind Kind;
 167
 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) {}
 174
 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);
 180   }
 181
 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,
 187                                 ExpansionRegion);
 188   }
 189
 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);
 195   }
 196
 197
 198   inline std::pair<unsigned, unsigned> startLoc() const {
 199     return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
 200   }
 201
 202   inline std::pair<unsigned, unsigned> endLoc() const {
 203     return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
 204   }
 205
 206   bool operator<(const CounterMappingRegion &Other) const {
 207     if (FileID != Other.FileID)
 208       return FileID < Other.FileID;
 209     return startLoc() < Other.startLoc();
 210   }
 211
 212   bool contains(const CounterMappingRegion &Other) const {
 213     if (FileID != Other.FileID)
 214       return false;
 215     if (startLoc() > Other.startLoc())
 216       return false;
 217     if (endLoc() < Other.endLoc())
 218       return false;
 219     return true;
 220   }
 221 };
 222
 223 /// \brief Associates a source range with an execution count.
 224 struct CountedRegion : public CounterMappingRegion {
 225   uint64_t ExecutionCount;
 226
 227   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
 228       : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
 229 };
 230
 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;
 236
 237 public:
 238   CounterMappingContext(ArrayRef<CounterExpression> Expressions,
 239                         ArrayRef<uint64_t> CounterValues = ArrayRef<uint64_t>())
 240       : Expressions(Expressions), CounterValues(CounterValues) {}
 241
 242   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
 243
 244   void dump(const Counter &C, llvm::raw_ostream &OS) const;
 245   void dump(const Counter &C) const { dump(C, dbgs()); }
 246
 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;
 250 };
 251
 252 /// \brief Code coverage information for a single function.
 253 struct FunctionRecord {
 254   /// \brief Raw function name.
 255   std::string 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;
 262
 263   FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
 264       : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
 265
 266   void pushRegion(CounterMappingRegion Region, uint64_t Count) {
 267     if (CountedRegions.empty())
 268       ExecutionCount = Count;
 269     CountedRegions.emplace_back(Region, Count);
 270   }
 271 };
 272
 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;
 279   StringRef Filename;
 280
 281   /// \brief Skip records whose primary file is not \c Filename.
 282   void skipOtherFiles();
 283
 284 public:
 285   FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
 286                          StringRef Filename = "")
 287       : Records(Records_), Current(Records.begin()), Filename(Filename) {
 288     skipOtherFiles();
 289   }
 290
 291   FunctionRecordIterator() : Current(Records.begin()) {}
 292
 293   bool operator==(const FunctionRecordIterator &RHS) const {
 294     return Current == RHS.Current && Filename == RHS.Filename;
 295   }
 296
 297   const FunctionRecord &operator*() const { return *Current; }
 298
 299   FunctionRecordIterator &operator++() {
 300     assert(Current != Records.end() && "incremented past end");
 301     ++Current;
 302     skipOtherFiles();
 303     return *this;
 304   }
 305 };
 306
 307 /// \brief Coverage information for a macro expansion or #included file.
 308 ///
 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.
 314   unsigned FileID;
 315   /// \brief The region that expands to this record.
 316   const CountedRegion &Region;
 317   /// \brief Coverage for the expansion.
 318   const FunctionRecord &Function;
 319
 320   ExpansionRecord(const CountedRegion &Region,
 321                   const FunctionRecord &Function)
 322       : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
 323 };
 324
 325 /// \brief The execution count information starting at a point in a file.
 326 ///
 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.
 331   unsigned Line;
 332   /// \brief The column where this segment begins.
 333   unsigned Col;
 334   /// \brief The execution count, or zero if no count was recorded.
 335   uint64_t Count;
 336   /// \brief When false, the segment was uninstrumented or skipped.
 337   bool HasCount;
 338   /// \brief Whether this enters a new region or returns to a previous count.
 339   bool IsRegionEntry;
 340
 341   CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
 342       : Line(Line), Col(Col), Count(0), HasCount(false),
 343         IsRegionEntry(IsRegionEntry) {}
 344
 345   CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
 346                   bool IsRegionEntry)
 347       : Line(Line), Col(Col), Count(Count), HasCount(true),
 348         IsRegionEntry(IsRegionEntry) {}
 349
 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);
 353   }
 354
 355   void setCount(uint64_t NewCount) {
 356     Count = NewCount;
 357     HasCount = true;
 358   }
 359
 360   void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
 361 };
 362
 363 /// \brief Coverage information to be processed or displayed.
 364 ///
 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.
 368 class CoverageData {
 369   std::string Filename;
 370   std::vector<CoverageSegment> Segments;
 371   std::vector<ExpansionRecord> Expansions;
 372   friend class CoverageMapping;
 373
 374 public:
 375   CoverageData() {}
 376
 377   CoverageData(StringRef Filename) : Filename(Filename) {}
 378
 379   CoverageData(CoverageData &&RHS)
 380       : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
 381         Expansions(std::move(RHS.Expansions)) {}
 382
 383   /// \brief Get the name of the file this data covers.
 384   StringRef getFilename() { return Filename; }
 385
 386   std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
 387   std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
 388   bool empty() { return Segments.empty(); }
 389
 390   /// \brief Expansions that can be further processed.
 391   std::vector<ExpansionRecord> getExpansions() { return Expansions; }
 392 };
 393
 394 /// \brief The mapping of profile information to coverage data.
 395 ///
 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;
 401
 402   CoverageMapping() : MismatchedFunctionCount(0) {}
 403
 404 public:
 405   /// \brief Load the coverage mapping using the given readers.
 406   static ErrorOr<std::unique_ptr<CoverageMapping>>
 407   load(CoverageMappingReader &CoverageReader,
 408        IndexedInstrProfReader &ProfileReader);
 409
 410   /// \brief Load the coverage mapping from the given files.
 411   static ErrorOr<std::unique_ptr<CoverageMapping>>
 412   load(StringRef ObjectFilename, StringRef ProfileFilename,
 413        StringRef Arch = StringRef());
 414
 415   /// \brief The number of functions that couldn't have their profiles mapped.
 416   ///
 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; }
 420
 421   /// \brief Returns the list of files that are covered.
 422   std::vector<StringRef> getUniqueSourceFiles() const;
 423
 424   /// \brief Get the coverage for a particular file.
 425   ///
 426   /// The given filename must be the name as recorded in the coverage
 427   /// information. That is, only names returned from getUniqueSourceFiles will
 428   /// yield a result.
 429   CoverageData getCoverageForFile(StringRef Filename);
 430
 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());
 435   }
 436
 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());
 442   }
 443
 444   /// \brief Get the list of function instantiations in the file.
 445   ///
 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);
 449
 450   /// \brief Get the coverage for a particular function.
 451   CoverageData getCoverageForFunction(const FunctionRecord &Function);
 452
 453   /// \brief Get the coverage for an expansion within a coverage set.
 454   CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
 455 };
 456
 457 } // end namespace coverage
 458
 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));
 466   }
 467
 468   static inline coverage::CounterExpression getTombstoneKey() {
 469     using namespace coverage;
 470     return CounterExpression(CounterExpression::ExprKind::Add,
 471                              Counter::getCounter(~0U),
 472                              Counter::getCounter(~0U));
 473   }
 474
 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()));
 479   }
 480
 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;
 484   }
 485 };
 486
 487 const std::error_category &coveragemap_category();
 488
 489 enum class coveragemap_error {
 490   success = 0,
 491   eof,
 492   no_data_found,
 493   unsupported_version,
 494   truncated,
 495   malformed
 496 };
 497
 498 inline std::error_code make_error_code(coveragemap_error E) {
 499   return std::error_code(static_cast<int>(E), coveragemap_category());
 500 }
 501
 502 } // end namespace llvm
 503
 504 namespace std {
 505 template <>
 506 struct is_error_code_enum<llvm::coveragemap_error> : std::true_type {};
 507 }
 508
 509 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_