include/llvm/ProfileData/Coverage/CoverageMapping.h

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