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