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 CoverageMappingReader;
  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   friend bool operator==(const Counter &LHS, const Counter &RHS) {
  67     return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
  68   }
  69
  70   friend bool operator!=(const Counter &LHS, const Counter &RHS) {
  71     return !(LHS == RHS);
  72   }
  73
  74   friend bool operator<(const Counter &LHS, const Counter &RHS) {
  75     return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  76   }
  77
  78   /// \brief Return the counter that represents the number zero.
  79   static Counter getZero() { return Counter(); }
  80
  81   /// \brief Return the counter that corresponds to a specific profile counter.
  82   static Counter getCounter(unsigned CounterId) {
  83     return Counter(CounterValueReference, CounterId);
  84   }
  85
  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);
  90   }
  91 };
  92
  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 };
  97   ExprKind Kind;
  98   Counter LHS, RHS;
  99
 100   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
 101       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 102 };
 103
 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;
 112
 113   /// \brief Return the counter which corresponds to the given expression.
 114   ///
 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);
 119
 120   /// \brief Gather the terms of the expression tree for processing.
 121   ///
 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
 124   /// expression.
 125   void extractTerms(Counter C, int Sign,
 126                     SmallVectorImpl<std::pair<unsigned, int>> &Terms);
 127
 128   /// \brief Simplifies the given expression tree
 129   /// by getting rid of algebraically redundant operations.
 130   Counter simplify(Counter ExpressionTree);
 131
 132 public:
 133   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 134
 135   /// \brief Return a counter that represents the expression
 136   /// that adds LHS and RHS.
 137   Counter add(Counter LHS, Counter RHS);
 138
 139   /// \brief Return a counter that represents the expression
 140   /// that subtracts RHS from LHS.
 141   Counter subtract(Counter LHS, Counter RHS);
 142 };
 143
 144 /// \brief A Counter mapping region associates a source range with
 145 /// a specific counter.
 146 struct CounterMappingRegion {
 147   enum RegionKind {
 148     /// \brief A CodeRegion associates some code with a counter
 149     CodeRegion,
 150
 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.
 154     ExpansionRegion,
 155
 156     /// \brief A SkippedRegion represents a source range with code that
 157     /// was skipped by a preprocessor or similar means.
 158     SkippedRegion
 159   };
 160
 161   Counter Count;
 162   unsigned FileID, ExpandedFileID;
 163   unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
 164   RegionKind Kind;
 165
 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) {}
 172
 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);
 178   }
 179
 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,
 185                                 ExpansionRegion);
 186   }
 187
 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);
 193   }
 194
 195
 196   inline std::pair<unsigned, unsigned> startLoc() const {
 197     return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
 198   }
 199
 200   inline std::pair<unsigned, unsigned> endLoc() const {
 201     return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
 202   }
 203
 204   bool operator<(const CounterMappingRegion &Other) const {
 205     if (FileID != Other.FileID)
 206       return FileID < Other.FileID;
 207     return startLoc() < Other.startLoc();
 208   }
 209
 210   bool contains(const CounterMappingRegion &Other) const {
 211     if (FileID != Other.FileID)
 212       return false;
 213     if (startLoc() > Other.startLoc())
 214       return false;
 215     if (endLoc() < Other.endLoc())
 216       return false;
 217     return true;
 218   }
 219 };
 220
 221 /// \brief Associates a source range with an execution count.
 222 struct CountedRegion : public CounterMappingRegion {
 223   uint64_t ExecutionCount;
 224
 225   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
 226       : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
 227 };
 228
 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;
 234
 235 public:
 236   CounterMappingContext(ArrayRef<CounterExpression> Expressions,
 237                         ArrayRef<uint64_t> CounterValues = ArrayRef<uint64_t>())
 238       : Expressions(Expressions), CounterValues(CounterValues) {}
 239
 240   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
 241
 242   void dump(const Counter &C, llvm::raw_ostream &OS) const;
 243   void dump(const Counter &C) const { dump(C, dbgs()); }
 244
 245   /// \brief Return the number of times that a region of code associated with
 246   /// this counter was executed.
 247   ErrorOr<int64_t> evaluate(const Counter &C) const;
 248 };
 249
 250 /// \brief Code coverage information for a single function.
 251 struct FunctionRecord {
 252   /// \brief Raw function name.
 253   std::string Name;
 254   /// \brief Associated files.
 255   std::vector<std::string> Filenames;
 256   /// \brief Regions in the function along with their counts.
 257   std::vector<CountedRegion> CountedRegions;
 258   /// \brief The number of times this function was executed.
 259   uint64_t ExecutionCount;
 260
 261   FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
 262       : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
 263
 264   void pushRegion(CounterMappingRegion Region, uint64_t Count) {
 265     if (CountedRegions.empty())
 266       ExecutionCount = Count;
 267     CountedRegions.emplace_back(Region, Count);
 268   }
 269 };
 270
 271 /// \brief Iterator over Functions, optionally filtered to a single file.
 272 class FunctionRecordIterator
 273     : public iterator_facade_base<FunctionRecordIterator,
 274                                   std::forward_iterator_tag, FunctionRecord> {
 275   ArrayRef<FunctionRecord> Records;
 276   ArrayRef<FunctionRecord>::iterator Current;
 277   StringRef Filename;
 278
 279   /// \brief Skip records whose primary file is not \c Filename.
 280   void skipOtherFiles();
 281
 282 public:
 283   FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
 284                          StringRef Filename = "")
 285       : Records(Records_), Current(Records.begin()), Filename(Filename) {
 286     skipOtherFiles();
 287   }
 288
 289   FunctionRecordIterator() : Current(Records.begin()) {}
 290
 291   bool operator==(const FunctionRecordIterator &RHS) const {
 292     return Current == RHS.Current && Filename == RHS.Filename;
 293   }
 294
 295   const FunctionRecord &operator*() const { return *Current; }
 296
 297   FunctionRecordIterator &operator++() {
 298     assert(Current != Records.end() && "incremented past end");
 299     ++Current;
 300     skipOtherFiles();
 301     return *this;
 302   }
 303 };
 304
 305 /// \brief Coverage information for a macro expansion or #included file.
 306 ///
 307 /// When covered code has pieces that can be expanded for more detail, such as a
 308 /// preprocessor macro use and its definition, these are represented as
 309 /// expansions whose coverage can be looked up independently.
 310 struct ExpansionRecord {
 311   /// \brief The abstract file this expansion covers.
 312   unsigned FileID;
 313   /// \brief The region that expands to this record.
 314   const CountedRegion &Region;
 315   /// \brief Coverage for the expansion.
 316   const FunctionRecord &Function;
 317
 318   ExpansionRecord(const CountedRegion &Region,
 319                   const FunctionRecord &Function)
 320       : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
 321 };
 322
 323 /// \brief The execution count information starting at a point in a file.
 324 ///
 325 /// A sequence of CoverageSegments gives execution counts for a file in format
 326 /// that's simple to iterate through for processing.
 327 struct CoverageSegment {
 328   /// \brief The line where this segment begins.
 329   unsigned Line;
 330   /// \brief The column where this segment begins.
 331   unsigned Col;
 332   /// \brief The execution count, or zero if no count was recorded.
 333   uint64_t Count;
 334   /// \brief When false, the segment was uninstrumented or skipped.
 335   bool HasCount;
 336   /// \brief Whether this enters a new region or returns to a previous count.
 337   bool IsRegionEntry;
 338
 339   CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
 340       : Line(Line), Col(Col), Count(0), HasCount(false),
 341         IsRegionEntry(IsRegionEntry) {}
 342
 343   CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
 344                   bool IsRegionEntry)
 345       : Line(Line), Col(Col), Count(Count), HasCount(true),
 346         IsRegionEntry(IsRegionEntry) {}
 347
 348   friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
 349     return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
 350            std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
 351   }
 352
 353   void setCount(uint64_t NewCount) {
 354     Count = NewCount;
 355     HasCount = true;
 356   }
 357
 358   void addCount(uint64_t NewCount) { setCount(Count + NewCount); }
 359 };
 360
 361 /// \brief Coverage information to be processed or displayed.
 362 ///
 363 /// This represents the coverage of an entire file, expansion, or function. It
 364 /// provides a sequence of CoverageSegments to iterate through, as well as the
 365 /// list of expansions that can be further processed.
 366 class CoverageData {
 367   std::string Filename;
 368   std::vector<CoverageSegment> Segments;
 369   std::vector<ExpansionRecord> Expansions;
 370   friend class CoverageMapping;
 371
 372 public:
 373   CoverageData() {}
 374
 375   CoverageData(StringRef Filename) : Filename(Filename) {}
 376
 377   CoverageData(CoverageData &&RHS)
 378       : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
 379         Expansions(std::move(RHS.Expansions)) {}
 380
 381   /// \brief Get the name of the file this data covers.
 382   StringRef getFilename() { return Filename; }
 383
 384   std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
 385   std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
 386   bool empty() { return Segments.empty(); }
 387
 388   /// \brief Expansions that can be further processed.
 389   std::vector<ExpansionRecord> getExpansions() { return Expansions; }
 390 };
 391
 392 /// \brief The mapping of profile information to coverage data.
 393 ///
 394 /// This is the main interface to get coverage information, using a profile to
 395 /// fill out execution counts.
 396 class CoverageMapping {
 397   std::vector<FunctionRecord> Functions;
 398   unsigned MismatchedFunctionCount;
 399
 400   CoverageMapping() : MismatchedFunctionCount(0) {}
 401
 402 public:
 403   /// \brief Load the coverage mapping using the given readers.
 404   static ErrorOr<std::unique_ptr<CoverageMapping>>
 405   load(CoverageMappingReader &CoverageReader,
 406        IndexedInstrProfReader &ProfileReader);
 407
 408   /// \brief Load the coverage mapping from the given files.
 409   static ErrorOr<std::unique_ptr<CoverageMapping>>
 410   load(StringRef ObjectFilename, StringRef ProfileFilename);
 411
 412   /// \brief The number of functions that couldn't have their profiles mapped.
 413   ///
 414   /// This is a count of functions whose profile is out of date or otherwise
 415   /// can't be associated with any coverage information.
 416   unsigned getMismatchedCount() { return MismatchedFunctionCount; }
 417
 418   /// \brief Returns the list of files that are covered.
 419   std::vector<StringRef> getUniqueSourceFiles() const;
 420
 421   /// \brief Get the coverage for a particular file.
 422   ///
 423   /// The given filename must be the name as recorded in the coverage
 424   /// information. That is, only names returned from getUniqueSourceFiles will
 425   /// yield a result.
 426   CoverageData getCoverageForFile(StringRef Filename);
 427
 428   /// \brief Gets all of the functions covered by this profile.
 429   iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
 430     return make_range(FunctionRecordIterator(Functions),
 431                       FunctionRecordIterator());
 432   }
 433
 434   /// \brief Gets all of the functions in a particular file.
 435   iterator_range<FunctionRecordIterator>
 436   getCoveredFunctions(StringRef Filename) const {
 437     return make_range(FunctionRecordIterator(Functions, Filename),
 438                       FunctionRecordIterator());
 439   }
 440
 441   /// \brief Get the list of function instantiations in the file.
 442   ///
 443   /// Fucntions that are instantiated more than once, such as C++ template
 444   /// specializations, have distinct coverage records for each instantiation.
 445   std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
 446
 447   /// \brief Get the coverage for a particular function.
 448   CoverageData getCoverageForFunction(const FunctionRecord &Function);
 449
 450   /// \brief Get the coverage for an expansion within a coverage set.
 451   CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
 452 };
 453
 454 } // end namespace coverage
 455
 456 /// \brief Provide DenseMapInfo for CounterExpression
 457 template<> struct DenseMapInfo<coverage::CounterExpression> {
 458   static inline coverage::CounterExpression getEmptyKey() {
 459     using namespace coverage;
 460     return CounterExpression(CounterExpression::ExprKind::Subtract,
 461                              Counter::getCounter(~0U),
 462                              Counter::getCounter(~0U));
 463   }
 464
 465   static inline coverage::CounterExpression getTombstoneKey() {
 466     using namespace coverage;
 467     return CounterExpression(CounterExpression::ExprKind::Add,
 468                              Counter::getCounter(~0U),
 469                              Counter::getCounter(~0U));
 470   }
 471
 472   static unsigned getHashValue(const coverage::CounterExpression &V) {
 473     return static_cast<unsigned>(
 474         hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
 475                      V.RHS.getKind(), V.RHS.getCounterID()));
 476   }
 477
 478   static bool isEqual(const coverage::CounterExpression &LHS,
 479                       const coverage::CounterExpression &RHS) {
 480     return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
 481   }
 482 };
 483
 484
 485 } // end namespace llvm
 486
 487 #endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_