contrib/llvm/include/llvm/ProfileData/Coverage/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_COVERAGE_COVERAGEMAPPING_H
  16 #define LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H
  17
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/DenseSet.h"
  21 #include "llvm/ADT/Hashing.h"
  22 #include "llvm/ADT/None.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/ADT/StringSet.h"
  25 #include "llvm/ADT/iterator.h"
  26 #include "llvm/ADT/iterator_range.h"
  27 #include "llvm/ProfileData/InstrProf.h"
  28 #include "llvm/Support/Compiler.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/Endian.h"
  31 #include "llvm/Support/Error.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include <cassert>
  34 #include <cstdint>
  35 #include <iterator>
  36 #include <memory>
  37 #include <string>
  38 #include <system_error>
  39 #include <tuple>
  40 #include <utility>
  41 #include <vector>
  42
  43 namespace llvm {
  44
  45 class IndexedInstrProfReader;
  46
  47 namespace coverage {
  48
  49 class CoverageMappingReader;
  50 struct CoverageMappingRecord;
  51
  52 enum class coveragemap_error {
  53   success = 0,
  54   eof,
  55   no_data_found,
  56   unsupported_version,
  57   truncated,
  58   malformed
  59 };
  60
  61 const std::error_category &coveragemap_category();
  62
  63 inline std::error_code make_error_code(coveragemap_error E) {
  64   return std::error_code(static_cast<int>(E), coveragemap_category());
  65 }
  66
  67 class CoverageMapError : public ErrorInfo<CoverageMapError> {
  68 public:
  69   CoverageMapError(coveragemap_error Err) : Err(Err) {
  70     assert(Err != coveragemap_error::success && "Not an error");
  71   }
  72
  73   std::string message() const override;
  74
  75   void log(raw_ostream &OS) const override { OS << message(); }
  76
  77   std::error_code convertToErrorCode() const override {
  78     return make_error_code(Err);
  79   }
  80
  81   coveragemap_error get() const { return Err; }
  82
  83   static char ID;
  84
  85 private:
  86   coveragemap_error Err;
  87 };
  88
  89 /// A Counter is an abstract value that describes how to compute the
  90 /// execution count for a region of code using the collected profile count data.
  91 struct Counter {
  92   enum CounterKind { Zero, CounterValueReference, Expression };
  93   static const unsigned EncodingTagBits = 2;
  94   static const unsigned EncodingTagMask = 0x3;
  95   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
  96       EncodingTagBits + 1;
  97
  98 private:
  99   CounterKind Kind = Zero;
 100   unsigned ID = 0;
 101
 102   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
 103
 104 public:
 105   Counter() = default;
 106
 107   CounterKind getKind() const { return Kind; }
 108
 109   bool isZero() const { return Kind == Zero; }
 110
 111   bool isExpression() const { return Kind == Expression; }
 112
 113   unsigned getCounterID() const { return ID; }
 114
 115   unsigned getExpressionID() const { return ID; }
 116
 117   friend bool operator==(const Counter &LHS, const Counter &RHS) {
 118     return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
 119   }
 120
 121   friend bool operator!=(const Counter &LHS, const Counter &RHS) {
 122     return !(LHS == RHS);
 123   }
 124
 125   friend bool operator<(const Counter &LHS, const Counter &RHS) {
 126     return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
 127   }
 128
 129   /// Return the counter that represents the number zero.
 130   static Counter getZero() { return Counter(); }
 131
 132   /// Return the counter that corresponds to a specific profile counter.
 133   static Counter getCounter(unsigned CounterId) {
 134     return Counter(CounterValueReference, CounterId);
 135   }
 136
 137   /// Return the counter that corresponds to a specific addition counter
 138   /// expression.
 139   static Counter getExpression(unsigned ExpressionId) {
 140     return Counter(Expression, ExpressionId);
 141   }
 142 };
 143
 144 /// A Counter expression is a value that represents an arithmetic operation
 145 /// with two counters.
 146 struct CounterExpression {
 147   enum ExprKind { Subtract, Add };
 148   ExprKind Kind;
 149   Counter LHS, RHS;
 150
 151   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
 152       : Kind(Kind), LHS(LHS), RHS(RHS) {}
 153 };
 154
 155 /// A Counter expression builder is used to construct the counter expressions.
 156 /// It avoids unnecessary duplication and simplifies algebraic expressions.
 157 class CounterExpressionBuilder {
 158   /// A list of all the counter expressions
 159   std::vector<CounterExpression> Expressions;
 160
 161   /// A lookup table for the index of a given expression.
 162   DenseMap<CounterExpression, unsigned> ExpressionIndices;
 163
 164   /// Return the counter which corresponds to the given expression.
 165   ///
 166   /// If the given expression is already stored in the builder, a counter
 167   /// that references that expression is returned. Otherwise, the given
 168   /// expression is added to the builder's collection of expressions.
 169   Counter get(const CounterExpression &E);
 170
 171   /// Represents a term in a counter expression tree.
 172   struct Term {
 173     unsigned CounterID;
 174     int Factor;
 175
 176     Term(unsigned CounterID, int Factor)
 177         : CounterID(CounterID), Factor(Factor) {}
 178   };
 179
 180   /// Gather the terms of the expression tree for processing.
 181   ///
 182   /// This collects each addition and subtraction referenced by the counter into
 183   /// a sequence that can be sorted and combined to build a simplified counter
 184   /// expression.
 185   void extractTerms(Counter C, int Sign, SmallVectorImpl<Term> &Terms);
 186
 187   /// Simplifies the given expression tree
 188   /// by getting rid of algebraically redundant operations.
 189   Counter simplify(Counter ExpressionTree);
 190
 191 public:
 192   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
 193
 194   /// Return a counter that represents the expression that adds LHS and RHS.
 195   Counter add(Counter LHS, Counter RHS);
 196
 197   /// Return a counter that represents the expression that subtracts RHS from
 198   /// LHS.
 199   Counter subtract(Counter LHS, Counter RHS);
 200 };
 201
 202 using LineColPair = std::pair<unsigned, unsigned>;
 203
 204 /// A Counter mapping region associates a source range with a specific counter.
 205 struct CounterMappingRegion {
 206   enum RegionKind {
 207     /// A CodeRegion associates some code with a counter
 208     CodeRegion,
 209
 210     /// An ExpansionRegion represents a file expansion region that associates
 211     /// a source range with the expansion of a virtual source file, such as
 212     /// for a macro instantiation or #include file.
 213     ExpansionRegion,
 214
 215     /// A SkippedRegion represents a source range with code that was skipped
 216     /// by a preprocessor or similar means.
 217     SkippedRegion,
 218
 219     /// A GapRegion is like a CodeRegion, but its count is only set as the
 220     /// line execution count when its the only region in the line.
 221     GapRegion
 222   };
 223
 224   Counter Count;
 225   unsigned FileID, ExpandedFileID;
 226   unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
 227   RegionKind Kind;
 228
 229   CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
 230                        unsigned LineStart, unsigned ColumnStart,
 231                        unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
 232       : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
 233         LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
 234         ColumnEnd(ColumnEnd), Kind(Kind) {}
 235
 236   static CounterMappingRegion
 237   makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
 238              unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
 239     return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
 240                                 LineEnd, ColumnEnd, CodeRegion);
 241   }
 242
 243   static CounterMappingRegion
 244   makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
 245                 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
 246     return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
 247                                 ColumnStart, LineEnd, ColumnEnd,
 248                                 ExpansionRegion);
 249   }
 250
 251   static CounterMappingRegion
 252   makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
 253               unsigned LineEnd, unsigned ColumnEnd) {
 254     return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
 255                                 LineEnd, ColumnEnd, SkippedRegion);
 256   }
 257
 258   static CounterMappingRegion
 259   makeGapRegion(Counter Count, unsigned FileID, unsigned LineStart,
 260                 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
 261     return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
 262                                 LineEnd, (1U << 31) | ColumnEnd, GapRegion);
 263   }
 264
 265   inline LineColPair startLoc() const {
 266     return LineColPair(LineStart, ColumnStart);
 267   }
 268
 269   inline LineColPair endLoc() const { return LineColPair(LineEnd, ColumnEnd); }
 270 };
 271
 272 /// Associates a source range with an execution count.
 273 struct CountedRegion : public CounterMappingRegion {
 274   uint64_t ExecutionCount;
 275
 276   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
 277       : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
 278 };
 279
 280 /// A Counter mapping context is used to connect the counters, expressions
 281 /// and the obtained counter values.
 282 class CounterMappingContext {
 283   ArrayRef<CounterExpression> Expressions;
 284   ArrayRef<uint64_t> CounterValues;
 285
 286 public:
 287   CounterMappingContext(ArrayRef<CounterExpression> Expressions,
 288                         ArrayRef<uint64_t> CounterValues = None)
 289       : Expressions(Expressions), CounterValues(CounterValues) {}
 290
 291   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
 292
 293   void dump(const Counter &C, raw_ostream &OS) const;
 294   void dump(const Counter &C) const { dump(C, dbgs()); }
 295
 296   /// Return the number of times that a region of code associated with this
 297   /// counter was executed.
 298   Expected<int64_t> evaluate(const Counter &C) const;
 299 };
 300
 301 /// Code coverage information for a single function.
 302 struct FunctionRecord {
 303   /// Raw function name.
 304   std::string Name;
 305   /// Associated files.
 306   std::vector<std::string> Filenames;
 307   /// Regions in the function along with their counts.
 308   std::vector<CountedRegion> CountedRegions;
 309   /// The number of times this function was executed.
 310   uint64_t ExecutionCount;
 311
 312   FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
 313       : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
 314
 315   FunctionRecord(FunctionRecord &&FR) = default;
 316   FunctionRecord &operator=(FunctionRecord &&) = default;
 317
 318   void pushRegion(CounterMappingRegion Region, uint64_t Count) {
 319     if (CountedRegions.empty())
 320       ExecutionCount = Count;
 321     CountedRegions.emplace_back(Region, Count);
 322   }
 323 };
 324
 325 /// Iterator over Functions, optionally filtered to a single file.
 326 class FunctionRecordIterator
 327     : public iterator_facade_base<FunctionRecordIterator,
 328                                   std::forward_iterator_tag, FunctionRecord> {
 329   ArrayRef<FunctionRecord> Records;
 330   ArrayRef<FunctionRecord>::iterator Current;
 331   StringRef Filename;
 332
 333   /// Skip records whose primary file is not \c Filename.
 334   void skipOtherFiles();
 335
 336 public:
 337   FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
 338                          StringRef Filename = "")
 339       : Records(Records_), Current(Records.begin()), Filename(Filename) {
 340     skipOtherFiles();
 341   }
 342
 343   FunctionRecordIterator() : Current(Records.begin()) {}
 344
 345   bool operator==(const FunctionRecordIterator &RHS) const {
 346     return Current == RHS.Current && Filename == RHS.Filename;
 347   }
 348
 349   const FunctionRecord &operator*() const { return *Current; }
 350
 351   FunctionRecordIterator &operator++() {
 352     assert(Current != Records.end() && "incremented past end");
 353     ++Current;
 354     skipOtherFiles();
 355     return *this;
 356   }
 357 };
 358
 359 /// Coverage information for a macro expansion or #included file.
 360 ///
 361 /// When covered code has pieces that can be expanded for more detail, such as a
 362 /// preprocessor macro use and its definition, these are represented as
 363 /// expansions whose coverage can be looked up independently.
 364 struct ExpansionRecord {
 365   /// The abstract file this expansion covers.
 366   unsigned FileID;
 367   /// The region that expands to this record.
 368   const CountedRegion &Region;
 369   /// Coverage for the expansion.
 370   const FunctionRecord &Function;
 371
 372   ExpansionRecord(const CountedRegion &Region,
 373                   const FunctionRecord &Function)
 374       : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
 375 };
 376
 377 /// The execution count information starting at a point in a file.
 378 ///
 379 /// A sequence of CoverageSegments gives execution counts for a file in format
 380 /// that's simple to iterate through for processing.
 381 struct CoverageSegment {
 382   /// The line where this segment begins.
 383   unsigned Line;
 384   /// The column where this segment begins.
 385   unsigned Col;
 386   /// The execution count, or zero if no count was recorded.
 387   uint64_t Count;
 388   /// When false, the segment was uninstrumented or skipped.
 389   bool HasCount;
 390   /// Whether this enters a new region or returns to a previous count.
 391   bool IsRegionEntry;
 392   /// Whether this enters a gap region.
 393   bool IsGapRegion;
 394
 395   CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
 396       : Line(Line), Col(Col), Count(0), HasCount(false),
 397         IsRegionEntry(IsRegionEntry), IsGapRegion(false) {}
 398
 399   CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
 400                   bool IsRegionEntry, bool IsGapRegion = false)
 401       : Line(Line), Col(Col), Count(Count), HasCount(true),
 402         IsRegionEntry(IsRegionEntry), IsGapRegion(IsGapRegion) {}
 403
 404   friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
 405     return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry,
 406                     L.IsGapRegion) == std::tie(R.Line, R.Col, R.Count,
 407                                                R.HasCount, R.IsRegionEntry,
 408                                                R.IsGapRegion);
 409   }
 410 };
 411
 412 /// An instantiation group contains a \c FunctionRecord list, such that each
 413 /// record corresponds to a distinct instantiation of the same function.
 414 ///
 415 /// Note that it's possible for a function to have more than one instantiation
 416 /// (consider C++ template specializations or static inline functions).
 417 class InstantiationGroup {
 418   friend class CoverageMapping;
 419
 420   unsigned Line;
 421   unsigned Col;
 422   std::vector<const FunctionRecord *> Instantiations;
 423
 424   InstantiationGroup(unsigned Line, unsigned Col,
 425                      std::vector<const FunctionRecord *> Instantiations)
 426       : Line(Line), Col(Col), Instantiations(std::move(Instantiations)) {}
 427
 428 public:
 429   InstantiationGroup(const InstantiationGroup &) = delete;
 430   InstantiationGroup(InstantiationGroup &&) = default;
 431
 432   /// Get the number of instantiations in this group.
 433   size_t size() const { return Instantiations.size(); }
 434
 435   /// Get the line where the common function was defined.
 436   unsigned getLine() const { return Line; }
 437
 438   /// Get the column where the common function was defined.
 439   unsigned getColumn() const { return Col; }
 440
 441   /// Check if the instantiations in this group have a common mangled name.
 442   bool hasName() const {
 443     for (unsigned I = 1, E = Instantiations.size(); I < E; ++I)
 444       if (Instantiations[I]->Name != Instantiations[0]->Name)
 445         return false;
 446     return true;
 447   }
 448
 449   /// Get the common mangled name for instantiations in this group.
 450   StringRef getName() const {
 451     assert(hasName() && "Instantiations don't have a shared name");
 452     return Instantiations[0]->Name;
 453   }
 454
 455   /// Get the total execution count of all instantiations in this group.
 456   uint64_t getTotalExecutionCount() const {
 457     uint64_t Count = 0;
 458     for (const FunctionRecord *F : Instantiations)
 459       Count += F->ExecutionCount;
 460     return Count;
 461   }
 462
 463   /// Get the instantiations in this group.
 464   ArrayRef<const FunctionRecord *> getInstantiations() const {
 465     return Instantiations;
 466   }
 467 };
 468
 469 /// Coverage information to be processed or displayed.
 470 ///
 471 /// This represents the coverage of an entire file, expansion, or function. It
 472 /// provides a sequence of CoverageSegments to iterate through, as well as the
 473 /// list of expansions that can be further processed.
 474 class CoverageData {
 475   friend class CoverageMapping;
 476
 477   std::string Filename;
 478   std::vector<CoverageSegment> Segments;
 479   std::vector<ExpansionRecord> Expansions;
 480
 481 public:
 482   CoverageData() = default;
 483
 484   CoverageData(StringRef Filename) : Filename(Filename) {}
 485
 486   /// Get the name of the file this data covers.
 487   StringRef getFilename() const { return Filename; }
 488
 489   /// Get an iterator over the coverage segments for this object. The segments
 490   /// are guaranteed to be uniqued and sorted by location.
 491   std::vector<CoverageSegment>::const_iterator begin() const {
 492     return Segments.begin();
 493   }
 494
 495   std::vector<CoverageSegment>::const_iterator end() const {
 496     return Segments.end();
 497   }
 498
 499   bool empty() const { return Segments.empty(); }
 500
 501   /// Expansions that can be further processed.
 502   ArrayRef<ExpansionRecord> getExpansions() const { return Expansions; }
 503 };
 504
 505 /// The mapping of profile information to coverage data.
 506 ///
 507 /// This is the main interface to get coverage information, using a profile to
 508 /// fill out execution counts.
 509 class CoverageMapping {
 510   DenseMap<size_t, DenseSet<size_t>> RecordProvenance;
 511   std::vector<FunctionRecord> Functions;
 512   std::vector<std::pair<std::string, uint64_t>> FuncHashMismatches;
 513
 514   CoverageMapping() = default;
 515
 516   /// Add a function record corresponding to \p Record.
 517   Error loadFunctionRecord(const CoverageMappingRecord &Record,
 518                            IndexedInstrProfReader &ProfileReader);
 519
 520 public:
 521   CoverageMapping(const CoverageMapping &) = delete;
 522   CoverageMapping &operator=(const CoverageMapping &) = delete;
 523
 524   /// Load the coverage mapping using the given readers.
 525   static Expected<std::unique_ptr<CoverageMapping>>
 526   load(ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
 527        IndexedInstrProfReader &ProfileReader);
 528
 529   /// Load the coverage mapping from the given object files and profile. If
 530   /// \p Arches is non-empty, it must specify an architecture for each object.
 531   static Expected<std::unique_ptr<CoverageMapping>>
 532   load(ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
 533        ArrayRef<StringRef> Arches = None);
 534
 535   /// The number of functions that couldn't have their profiles mapped.
 536   ///
 537   /// This is a count of functions whose profile is out of date or otherwise
 538   /// can't be associated with any coverage information.
 539   unsigned getMismatchedCount() const { return FuncHashMismatches.size(); }
 540
 541   /// A hash mismatch occurs when a profile record for a symbol does not have
 542   /// the same hash as a coverage mapping record for the same symbol. This
 543   /// returns a list of hash mismatches, where each mismatch is a pair of the
 544   /// symbol name and its coverage mapping hash.
 545   ArrayRef<std::pair<std::string, uint64_t>> getHashMismatches() const {
 546     return FuncHashMismatches;
 547   }
 548
 549   /// Returns a lexicographically sorted, unique list of files that are
 550   /// covered.
 551   std::vector<StringRef> getUniqueSourceFiles() const;
 552
 553   /// Get the coverage for a particular file.
 554   ///
 555   /// The given filename must be the name as recorded in the coverage
 556   /// information. That is, only names returned from getUniqueSourceFiles will
 557   /// yield a result.
 558   CoverageData getCoverageForFile(StringRef Filename) const;
 559
 560   /// Get the coverage for a particular function.
 561   CoverageData getCoverageForFunction(const FunctionRecord &Function) const;
 562
 563   /// Get the coverage for an expansion within a coverage set.
 564   CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const;
 565
 566   /// Gets all of the functions covered by this profile.
 567   iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
 568     return make_range(FunctionRecordIterator(Functions),
 569                       FunctionRecordIterator());
 570   }
 571
 572   /// Gets all of the functions in a particular file.
 573   iterator_range<FunctionRecordIterator>
 574   getCoveredFunctions(StringRef Filename) const {
 575     return make_range(FunctionRecordIterator(Functions, Filename),
 576                       FunctionRecordIterator());
 577   }
 578
 579   /// Get the list of function instantiation groups in a particular file.
 580   ///
 581   /// Every instantiation group in a program is attributed to exactly one file:
 582   /// the file in which the definition for the common function begins.
 583   std::vector<InstantiationGroup>
 584   getInstantiationGroups(StringRef Filename) const;
 585 };
 586
 587 /// Coverage statistics for a single line.
 588 class LineCoverageStats {
 589   uint64_t ExecutionCount;
 590   bool HasMultipleRegions;
 591   bool Mapped;
 592   unsigned Line;
 593   ArrayRef<const CoverageSegment *> LineSegments;
 594   const CoverageSegment *WrappedSegment;
 595
 596   friend class LineCoverageIterator;
 597   LineCoverageStats() = default;
 598
 599 public:
 600   LineCoverageStats(ArrayRef<const CoverageSegment *> LineSegments,
 601                     const CoverageSegment *WrappedSegment, unsigned Line);
 602
 603   uint64_t getExecutionCount() const { return ExecutionCount; }
 604
 605   bool hasMultipleRegions() const { return HasMultipleRegions; }
 606
 607   bool isMapped() const { return Mapped; }
 608
 609   unsigned getLine() const { return Line; }
 610
 611   ArrayRef<const CoverageSegment *> getLineSegments() const {
 612     return LineSegments;
 613   }
 614
 615   const CoverageSegment *getWrappedSegment() const { return WrappedSegment; }
 616 };
 617
 618 /// An iterator over the \c LineCoverageStats objects for lines described by
 619 /// a \c CoverageData instance.
 620 class LineCoverageIterator
 621     : public iterator_facade_base<
 622           LineCoverageIterator, std::forward_iterator_tag, LineCoverageStats> {
 623 public:
 624   LineCoverageIterator(const CoverageData &CD)
 625       : LineCoverageIterator(CD, CD.begin()->Line) {}
 626
 627   LineCoverageIterator(const CoverageData &CD, unsigned Line)
 628       : CD(CD), WrappedSegment(nullptr), Next(CD.begin()), Ended(false),
 629         Line(Line), Segments(), Stats() {
 630     this->operator++();
 631   }
 632
 633   bool operator==(const LineCoverageIterator &R) const {
 634     return &CD == &R.CD && Next == R.Next && Ended == R.Ended;
 635   }
 636
 637   const LineCoverageStats &operator*() const { return Stats; }
 638
 639   LineCoverageStats &operator*() { return Stats; }
 640
 641   LineCoverageIterator &operator++();
 642
 643   LineCoverageIterator getEnd() const {
 644     auto EndIt = *this;
 645     EndIt.Next = CD.end();
 646     EndIt.Ended = true;
 647     return EndIt;
 648   }
 649
 650 private:
 651   const CoverageData &CD;
 652   const CoverageSegment *WrappedSegment;
 653   std::vector<CoverageSegment>::const_iterator Next;
 654   bool Ended;
 655   unsigned Line;
 656   SmallVector<const CoverageSegment *, 4> Segments;
 657   LineCoverageStats Stats;
 658 };
 659
 660 /// Get a \c LineCoverageIterator range for the lines described by \p CD.
 661 static inline iterator_range<LineCoverageIterator>
 662 getLineCoverageStats(const coverage::CoverageData &CD) {
 663   auto Begin = LineCoverageIterator(CD);
 664   auto End = Begin.getEnd();
 665   return make_range(Begin, End);
 666 }
 667
 668 // Profile coverage map has the following layout:
 669 // [CoverageMapFileHeader]
 670 // [ArrayStart]
 671 //  [CovMapFunctionRecord]
 672 //  [CovMapFunctionRecord]
 673 //  ...
 674 // [ArrayEnd]
 675 // [Encoded Region Mapping Data]
 676 LLVM_PACKED_START
 677 template <class IntPtrT> struct CovMapFunctionRecordV1 {
 678 #define COVMAP_V1
 679 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
 680 #include "llvm/ProfileData/InstrProfData.inc"
 681 #undef COVMAP_V1
 682
 683   // Return the structural hash associated with the function.
 684   template <support::endianness Endian> uint64_t getFuncHash() const {
 685     return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
 686   }
 687
 688   // Return the coverage map data size for the funciton.
 689   template <support::endianness Endian> uint32_t getDataSize() const {
 690     return support::endian::byte_swap<uint32_t, Endian>(DataSize);
 691   }
 692
 693   // Return function lookup key. The value is consider opaque.
 694   template <support::endianness Endian> IntPtrT getFuncNameRef() const {
 695     return support::endian::byte_swap<IntPtrT, Endian>(NamePtr);
 696   }
 697
 698   // Return the PGO name of the function */
 699   template <support::endianness Endian>
 700   Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
 701     IntPtrT NameRef = getFuncNameRef<Endian>();
 702     uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize);
 703     FuncName = ProfileNames.getFuncName(NameRef, NameS);
 704     if (NameS && FuncName.empty())
 705       return make_error<CoverageMapError>(coveragemap_error::malformed);
 706     return Error::success();
 707   }
 708 };
 709
 710 struct CovMapFunctionRecord {
 711 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
 712 #include "llvm/ProfileData/InstrProfData.inc"
 713
 714   // Return the structural hash associated with the function.
 715   template <support::endianness Endian> uint64_t getFuncHash() const {
 716     return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
 717   }
 718
 719   // Return the coverage map data size for the funciton.
 720   template <support::endianness Endian> uint32_t getDataSize() const {
 721     return support::endian::byte_swap<uint32_t, Endian>(DataSize);
 722   }
 723
 724   // Return function lookup key. The value is consider opaque.
 725   template <support::endianness Endian> uint64_t getFuncNameRef() const {
 726     return support::endian::byte_swap<uint64_t, Endian>(NameRef);
 727   }
 728
 729   // Return the PGO name of the function */
 730   template <support::endianness Endian>
 731   Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
 732     uint64_t NameRef = getFuncNameRef<Endian>();
 733     FuncName = ProfileNames.getFuncName(NameRef);
 734     return Error::success();
 735   }
 736 };
 737
 738 // Per module coverage mapping data header, i.e. CoverageMapFileHeader
 739 // documented above.
 740 struct CovMapHeader {
 741 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
 742 #include "llvm/ProfileData/InstrProfData.inc"
 743   template <support::endianness Endian> uint32_t getNRecords() const {
 744     return support::endian::byte_swap<uint32_t, Endian>(NRecords);
 745   }
 746
 747   template <support::endianness Endian> uint32_t getFilenamesSize() const {
 748     return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
 749   }
 750
 751   template <support::endianness Endian> uint32_t getCoverageSize() const {
 752     return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
 753   }
 754
 755   template <support::endianness Endian> uint32_t getVersion() const {
 756     return support::endian::byte_swap<uint32_t, Endian>(Version);
 757   }
 758 };
 759
 760 LLVM_PACKED_END
 761
 762 enum CovMapVersion {
 763   Version1 = 0,
 764   // Function's name reference from CovMapFuncRecord is changed from raw
 765   // name string pointer to MD5 to support name section compression. Name
 766   // section is also compressed.
 767   Version2 = 1,
 768   // A new interpretation of the columnEnd field is added in order to mark
 769   // regions as gap areas.
 770   Version3 = 2,
 771   // The current version is Version3
 772   CurrentVersion = INSTR_PROF_COVMAP_VERSION
 773 };
 774
 775 template <int CovMapVersion, class IntPtrT> struct CovMapTraits {
 776   using CovMapFuncRecordType = CovMapFunctionRecord;
 777   using NameRefType = uint64_t;
 778 };
 779
 780 template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> {
 781   using CovMapFuncRecordType = CovMapFunctionRecordV1<IntPtrT>;
 782   using NameRefType = IntPtrT;
 783 };
 784
 785 } // end namespace coverage
 786
 787 /// Provide DenseMapInfo for CounterExpression
 788 template<> struct DenseMapInfo<coverage::CounterExpression> {
 789   static inline coverage::CounterExpression getEmptyKey() {
 790     using namespace coverage;
 791
 792     return CounterExpression(CounterExpression::ExprKind::Subtract,
 793                              Counter::getCounter(~0U),
 794                              Counter::getCounter(~0U));
 795   }
 796
 797   static inline coverage::CounterExpression getTombstoneKey() {
 798     using namespace coverage;
 799
 800     return CounterExpression(CounterExpression::ExprKind::Add,
 801                              Counter::getCounter(~0U),
 802                              Counter::getCounter(~0U));
 803   }
 804
 805   static unsigned getHashValue(const coverage::CounterExpression &V) {
 806     return static_cast<unsigned>(
 807         hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
 808                      V.RHS.getKind(), V.RHS.getCounterID()));
 809   }
 810
 811   static bool isEqual(const coverage::CounterExpression &LHS,
 812                       const coverage::CounterExpression &RHS) {
 813     return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
 814   }
 815 };
 816
 817 } // end namespace llvm
 818
 819 #endif // LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H