Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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/StringRef.h"
  22. #include "llvm/ADT/iterator.h"
  23. #include "llvm/ADT/iterator_range.h"
  24. #include "llvm/Object/BuildID.h"
  25. #include "llvm/ProfileData/InstrProf.h"
  26. #include "llvm/Support/Alignment.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 object {
  47. class BuildIDFetcher;
  48. } // namespace object
  49.  
  50. namespace coverage {
  51.  
  52. class CoverageMappingReader;
  53. struct CoverageMappingRecord;
  54.  
  55. enum class coveragemap_error {
  56.   success = 0,
  57.   eof,
  58.   no_data_found,
  59.   unsupported_version,
  60.   truncated,
  61.   malformed,
  62.   decompression_failed,
  63.   invalid_or_missing_arch_specifier
  64. };
  65.  
  66. const std::error_category &coveragemap_category();
  67.  
  68. inline std::error_code make_error_code(coveragemap_error E) {
  69.   return std::error_code(static_cast<int>(E), coveragemap_category());
  70. }
  71.  
  72. class CoverageMapError : public ErrorInfo<CoverageMapError> {
  73. public:
  74.   CoverageMapError(coveragemap_error Err) : Err(Err) {
  75.     assert(Err != coveragemap_error::success && "Not an error");
  76.   }
  77.  
  78.   std::string message() const override;
  79.  
  80.   void log(raw_ostream &OS) const override { OS << message(); }
  81.  
  82.   std::error_code convertToErrorCode() const override {
  83.     return make_error_code(Err);
  84.   }
  85.  
  86.   coveragemap_error get() const { return Err; }
  87.  
  88.   static char ID;
  89.  
  90. private:
  91.   coveragemap_error Err;
  92. };
  93.  
  94. /// A Counter is an abstract value that describes how to compute the
  95. /// execution count for a region of code using the collected profile count data.
  96. struct Counter {
  97.   /// The CounterExpression kind (Add or Subtract) is encoded in bit 0 next to
  98.   /// the CounterKind. This means CounterKind has to leave bit 0 free.
  99.   enum CounterKind { Zero, CounterValueReference, Expression };
  100.   static const unsigned EncodingTagBits = 2;
  101.   static const unsigned EncodingTagMask = 0x3;
  102.   static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
  103.       EncodingTagBits + 1;
  104.  
  105. private:
  106.   CounterKind Kind = Zero;
  107.   unsigned ID = 0;
  108.  
  109.   Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
  110.  
  111. public:
  112.   Counter() = default;
  113.  
  114.   CounterKind getKind() const { return Kind; }
  115.  
  116.   bool isZero() const { return Kind == Zero; }
  117.  
  118.   bool isExpression() const { return Kind == Expression; }
  119.  
  120.   unsigned getCounterID() const { return ID; }
  121.  
  122.   unsigned getExpressionID() const { return ID; }
  123.  
  124.   friend bool operator==(const Counter &LHS, const Counter &RHS) {
  125.     return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
  126.   }
  127.  
  128.   friend bool operator!=(const Counter &LHS, const Counter &RHS) {
  129.     return !(LHS == RHS);
  130.   }
  131.  
  132.   friend bool operator<(const Counter &LHS, const Counter &RHS) {
  133.     return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
  134.   }
  135.  
  136.   /// Return the counter that represents the number zero.
  137.   static Counter getZero() { return Counter(); }
  138.  
  139.   /// Return the counter that corresponds to a specific profile counter.
  140.   static Counter getCounter(unsigned CounterId) {
  141.     return Counter(CounterValueReference, CounterId);
  142.   }
  143.  
  144.   /// Return the counter that corresponds to a specific addition counter
  145.   /// expression.
  146.   static Counter getExpression(unsigned ExpressionId) {
  147.     return Counter(Expression, ExpressionId);
  148.   }
  149. };
  150.  
  151. /// A Counter expression is a value that represents an arithmetic operation
  152. /// with two counters.
  153. struct CounterExpression {
  154.   enum ExprKind { Subtract, Add };
  155.   ExprKind Kind;
  156.   Counter LHS, RHS;
  157.  
  158.   CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
  159.       : Kind(Kind), LHS(LHS), RHS(RHS) {}
  160. };
  161.  
  162. /// A Counter expression builder is used to construct the counter expressions.
  163. /// It avoids unnecessary duplication and simplifies algebraic expressions.
  164. class CounterExpressionBuilder {
  165.   /// A list of all the counter expressions
  166.   std::vector<CounterExpression> Expressions;
  167.  
  168.   /// A lookup table for the index of a given expression.
  169.   DenseMap<CounterExpression, unsigned> ExpressionIndices;
  170.  
  171.   /// Return the counter which corresponds to the given expression.
  172.   ///
  173.   /// If the given expression is already stored in the builder, a counter
  174.   /// that references that expression is returned. Otherwise, the given
  175.   /// expression is added to the builder's collection of expressions.
  176.   Counter get(const CounterExpression &E);
  177.  
  178.   /// Represents a term in a counter expression tree.
  179.   struct Term {
  180.     unsigned CounterID;
  181.     int Factor;
  182.  
  183.     Term(unsigned CounterID, int Factor)
  184.         : CounterID(CounterID), Factor(Factor) {}
  185.   };
  186.  
  187.   /// Gather the terms of the expression tree for processing.
  188.   ///
  189.   /// This collects each addition and subtraction referenced by the counter into
  190.   /// a sequence that can be sorted and combined to build a simplified counter
  191.   /// expression.
  192.   void extractTerms(Counter C, int Sign, SmallVectorImpl<Term> &Terms);
  193.  
  194.   /// Simplifies the given expression tree
  195.   /// by getting rid of algebraically redundant operations.
  196.   Counter simplify(Counter ExpressionTree);
  197.  
  198. public:
  199.   ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
  200.  
  201.   /// Return a counter that represents the expression that adds LHS and RHS.
  202.   Counter add(Counter LHS, Counter RHS, bool Simplify = true);
  203.  
  204.   /// Return a counter that represents the expression that subtracts RHS from
  205.   /// LHS.
  206.   Counter subtract(Counter LHS, Counter RHS, bool Simplify = true);
  207. };
  208.  
  209. using LineColPair = std::pair<unsigned, unsigned>;
  210.  
  211. /// A Counter mapping region associates a source range with a specific counter.
  212. struct CounterMappingRegion {
  213.   enum RegionKind {
  214.     /// A CodeRegion associates some code with a counter
  215.     CodeRegion,
  216.  
  217.     /// An ExpansionRegion represents a file expansion region that associates
  218.     /// a source range with the expansion of a virtual source file, such as
  219.     /// for a macro instantiation or #include file.
  220.     ExpansionRegion,
  221.  
  222.     /// A SkippedRegion represents a source range with code that was skipped
  223.     /// by a preprocessor or similar means.
  224.     SkippedRegion,
  225.  
  226.     /// A GapRegion is like a CodeRegion, but its count is only set as the
  227.     /// line execution count when its the only region in the line.
  228.     GapRegion,
  229.  
  230.     /// A BranchRegion represents leaf-level boolean expressions and is
  231.     /// associated with two counters, each representing the number of times the
  232.     /// expression evaluates to true or false.
  233.     BranchRegion
  234.   };
  235.  
  236.   /// Primary Counter that is also used for Branch Regions (TrueCount).
  237.   Counter Count;
  238.  
  239.   /// Secondary Counter used for Branch Regions (FalseCount).
  240.   Counter FalseCount;
  241.  
  242.   unsigned FileID, ExpandedFileID;
  243.   unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
  244.   RegionKind Kind;
  245.  
  246.   CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
  247.                        unsigned LineStart, unsigned ColumnStart,
  248.                        unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
  249.       : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
  250.         LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
  251.         ColumnEnd(ColumnEnd), Kind(Kind) {}
  252.  
  253.   CounterMappingRegion(Counter Count, Counter FalseCount, unsigned FileID,
  254.                        unsigned ExpandedFileID, unsigned LineStart,
  255.                        unsigned ColumnStart, unsigned LineEnd,
  256.                        unsigned ColumnEnd, RegionKind Kind)
  257.       : Count(Count), FalseCount(FalseCount), FileID(FileID),
  258.         ExpandedFileID(ExpandedFileID), LineStart(LineStart),
  259.         ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd),
  260.         Kind(Kind) {}
  261.  
  262.   static CounterMappingRegion
  263.   makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
  264.              unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
  265.     return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
  266.                                 LineEnd, ColumnEnd, CodeRegion);
  267.   }
  268.  
  269.   static CounterMappingRegion
  270.   makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
  271.                 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
  272.     return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
  273.                                 ColumnStart, LineEnd, ColumnEnd,
  274.                                 ExpansionRegion);
  275.   }
  276.  
  277.   static CounterMappingRegion
  278.   makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
  279.               unsigned LineEnd, unsigned ColumnEnd) {
  280.     return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
  281.                                 LineEnd, ColumnEnd, SkippedRegion);
  282.   }
  283.  
  284.   static CounterMappingRegion
  285.   makeGapRegion(Counter Count, unsigned FileID, unsigned LineStart,
  286.                 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
  287.     return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
  288.                                 LineEnd, (1U << 31) | ColumnEnd, GapRegion);
  289.   }
  290.  
  291.   static CounterMappingRegion
  292.   makeBranchRegion(Counter Count, Counter FalseCount, unsigned FileID,
  293.                    unsigned LineStart, unsigned ColumnStart, unsigned LineEnd,
  294.                    unsigned ColumnEnd) {
  295.     return CounterMappingRegion(Count, FalseCount, FileID, 0, LineStart,
  296.                                 ColumnStart, LineEnd, ColumnEnd, BranchRegion);
  297.   }
  298.  
  299.   inline LineColPair startLoc() const {
  300.     return LineColPair(LineStart, ColumnStart);
  301.   }
  302.  
  303.   inline LineColPair endLoc() const { return LineColPair(LineEnd, ColumnEnd); }
  304. };
  305.  
  306. /// Associates a source range with an execution count.
  307. struct CountedRegion : public CounterMappingRegion {
  308.   uint64_t ExecutionCount;
  309.   uint64_t FalseExecutionCount;
  310.   bool Folded;
  311.  
  312.   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
  313.       : CounterMappingRegion(R), ExecutionCount(ExecutionCount),
  314.         FalseExecutionCount(0), Folded(false) {}
  315.  
  316.   CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount,
  317.                 uint64_t FalseExecutionCount)
  318.       : CounterMappingRegion(R), ExecutionCount(ExecutionCount),
  319.         FalseExecutionCount(FalseExecutionCount), Folded(false) {}
  320. };
  321.  
  322. /// A Counter mapping context is used to connect the counters, expressions
  323. /// and the obtained counter values.
  324. class CounterMappingContext {
  325.   ArrayRef<CounterExpression> Expressions;
  326.   ArrayRef<uint64_t> CounterValues;
  327.  
  328. public:
  329.   CounterMappingContext(ArrayRef<CounterExpression> Expressions,
  330.                         ArrayRef<uint64_t> CounterValues = std::nullopt)
  331.       : Expressions(Expressions), CounterValues(CounterValues) {}
  332.  
  333.   void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
  334.  
  335.   void dump(const Counter &C, raw_ostream &OS) const;
  336.   void dump(const Counter &C) const { dump(C, dbgs()); }
  337.  
  338.   /// Return the number of times that a region of code associated with this
  339.   /// counter was executed.
  340.   Expected<int64_t> evaluate(const Counter &C) const;
  341.  
  342.   unsigned getMaxCounterID(const Counter &C) const;
  343. };
  344.  
  345. /// Code coverage information for a single function.
  346. struct FunctionRecord {
  347.   /// Raw function name.
  348.   std::string Name;
  349.   /// Mapping from FileID (i.e. vector index) to filename. Used to support
  350.   /// macro expansions within a function in which the macro and function are
  351.   /// defined in separate files.
  352.   ///
  353.   /// TODO: Uniquing filenames across all function records may be a performance
  354.   /// optimization.
  355.   std::vector<std::string> Filenames;
  356.   /// Regions in the function along with their counts.
  357.   std::vector<CountedRegion> CountedRegions;
  358.   /// Branch Regions in the function along with their counts.
  359.   std::vector<CountedRegion> CountedBranchRegions;
  360.   /// The number of times this function was executed.
  361.   uint64_t ExecutionCount = 0;
  362.  
  363.   FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
  364.       : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
  365.  
  366.   FunctionRecord(FunctionRecord &&FR) = default;
  367.   FunctionRecord &operator=(FunctionRecord &&) = default;
  368.  
  369.   void pushRegion(CounterMappingRegion Region, uint64_t Count,
  370.                   uint64_t FalseCount) {
  371.     if (Region.Kind == CounterMappingRegion::BranchRegion) {
  372.       CountedBranchRegions.emplace_back(Region, Count, FalseCount);
  373.       // If both counters are hard-coded to zero, then this region represents a
  374.       // constant-folded branch.
  375.       if (Region.Count.isZero() && Region.FalseCount.isZero())
  376.         CountedBranchRegions.back().Folded = true;
  377.       return;
  378.     }
  379.     if (CountedRegions.empty())
  380.       ExecutionCount = Count;
  381.     CountedRegions.emplace_back(Region, Count, FalseCount);
  382.   }
  383. };
  384.  
  385. /// Iterator over Functions, optionally filtered to a single file.
  386. class FunctionRecordIterator
  387.     : public iterator_facade_base<FunctionRecordIterator,
  388.                                   std::forward_iterator_tag, FunctionRecord> {
  389.   ArrayRef<FunctionRecord> Records;
  390.   ArrayRef<FunctionRecord>::iterator Current;
  391.   StringRef Filename;
  392.  
  393.   /// Skip records whose primary file is not \c Filename.
  394.   void skipOtherFiles();
  395.  
  396. public:
  397.   FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
  398.                          StringRef Filename = "")
  399.       : Records(Records_), Current(Records.begin()), Filename(Filename) {
  400.     skipOtherFiles();
  401.   }
  402.  
  403.   FunctionRecordIterator() : Current(Records.begin()) {}
  404.  
  405.   bool operator==(const FunctionRecordIterator &RHS) const {
  406.     return Current == RHS.Current && Filename == RHS.Filename;
  407.   }
  408.  
  409.   const FunctionRecord &operator*() const { return *Current; }
  410.  
  411.   FunctionRecordIterator &operator++() {
  412.     assert(Current != Records.end() && "incremented past end");
  413.     ++Current;
  414.     skipOtherFiles();
  415.     return *this;
  416.   }
  417. };
  418.  
  419. /// Coverage information for a macro expansion or #included file.
  420. ///
  421. /// When covered code has pieces that can be expanded for more detail, such as a
  422. /// preprocessor macro use and its definition, these are represented as
  423. /// expansions whose coverage can be looked up independently.
  424. struct ExpansionRecord {
  425.   /// The abstract file this expansion covers.
  426.   unsigned FileID;
  427.   /// The region that expands to this record.
  428.   const CountedRegion &Region;
  429.   /// Coverage for the expansion.
  430.   const FunctionRecord &Function;
  431.  
  432.   ExpansionRecord(const CountedRegion &Region,
  433.                   const FunctionRecord &Function)
  434.       : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
  435. };
  436.  
  437. /// The execution count information starting at a point in a file.
  438. ///
  439. /// A sequence of CoverageSegments gives execution counts for a file in format
  440. /// that's simple to iterate through for processing.
  441. struct CoverageSegment {
  442.   /// The line where this segment begins.
  443.   unsigned Line;
  444.   /// The column where this segment begins.
  445.   unsigned Col;
  446.   /// The execution count, or zero if no count was recorded.
  447.   uint64_t Count;
  448.   /// When false, the segment was uninstrumented or skipped.
  449.   bool HasCount;
  450.   /// Whether this enters a new region or returns to a previous count.
  451.   bool IsRegionEntry;
  452.   /// Whether this enters a gap region.
  453.   bool IsGapRegion;
  454.  
  455.   CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
  456.       : Line(Line), Col(Col), Count(0), HasCount(false),
  457.         IsRegionEntry(IsRegionEntry), IsGapRegion(false) {}
  458.  
  459.   CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
  460.                   bool IsRegionEntry, bool IsGapRegion = false,
  461.                   bool IsBranchRegion = false)
  462.       : Line(Line), Col(Col), Count(Count), HasCount(true),
  463.         IsRegionEntry(IsRegionEntry), IsGapRegion(IsGapRegion) {}
  464.  
  465.   friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
  466.     return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry,
  467.                     L.IsGapRegion) == std::tie(R.Line, R.Col, R.Count,
  468.                                                R.HasCount, R.IsRegionEntry,
  469.                                                R.IsGapRegion);
  470.   }
  471. };
  472.  
  473. /// An instantiation group contains a \c FunctionRecord list, such that each
  474. /// record corresponds to a distinct instantiation of the same function.
  475. ///
  476. /// Note that it's possible for a function to have more than one instantiation
  477. /// (consider C++ template specializations or static inline functions).
  478. class InstantiationGroup {
  479.   friend class CoverageMapping;
  480.  
  481.   unsigned Line;
  482.   unsigned Col;
  483.   std::vector<const FunctionRecord *> Instantiations;
  484.  
  485.   InstantiationGroup(unsigned Line, unsigned Col,
  486.                      std::vector<const FunctionRecord *> Instantiations)
  487.       : Line(Line), Col(Col), Instantiations(std::move(Instantiations)) {}
  488.  
  489. public:
  490.   InstantiationGroup(const InstantiationGroup &) = delete;
  491.   InstantiationGroup(InstantiationGroup &&) = default;
  492.  
  493.   /// Get the number of instantiations in this group.
  494.   size_t size() const { return Instantiations.size(); }
  495.  
  496.   /// Get the line where the common function was defined.
  497.   unsigned getLine() const { return Line; }
  498.  
  499.   /// Get the column where the common function was defined.
  500.   unsigned getColumn() const { return Col; }
  501.  
  502.   /// Check if the instantiations in this group have a common mangled name.
  503.   bool hasName() const {
  504.     for (unsigned I = 1, E = Instantiations.size(); I < E; ++I)
  505.       if (Instantiations[I]->Name != Instantiations[0]->Name)
  506.         return false;
  507.     return true;
  508.   }
  509.  
  510.   /// Get the common mangled name for instantiations in this group.
  511.   StringRef getName() const {
  512.     assert(hasName() && "Instantiations don't have a shared name");
  513.     return Instantiations[0]->Name;
  514.   }
  515.  
  516.   /// Get the total execution count of all instantiations in this group.
  517.   uint64_t getTotalExecutionCount() const {
  518.     uint64_t Count = 0;
  519.     for (const FunctionRecord *F : Instantiations)
  520.       Count += F->ExecutionCount;
  521.     return Count;
  522.   }
  523.  
  524.   /// Get the instantiations in this group.
  525.   ArrayRef<const FunctionRecord *> getInstantiations() const {
  526.     return Instantiations;
  527.   }
  528. };
  529.  
  530. /// Coverage information to be processed or displayed.
  531. ///
  532. /// This represents the coverage of an entire file, expansion, or function. It
  533. /// provides a sequence of CoverageSegments to iterate through, as well as the
  534. /// list of expansions that can be further processed.
  535. class CoverageData {
  536.   friend class CoverageMapping;
  537.  
  538.   std::string Filename;
  539.   std::vector<CoverageSegment> Segments;
  540.   std::vector<ExpansionRecord> Expansions;
  541.   std::vector<CountedRegion> BranchRegions;
  542.  
  543. public:
  544.   CoverageData() = default;
  545.  
  546.   CoverageData(StringRef Filename) : Filename(Filename) {}
  547.  
  548.   /// Get the name of the file this data covers.
  549.   StringRef getFilename() const { return Filename; }
  550.  
  551.   /// Get an iterator over the coverage segments for this object. The segments
  552.   /// are guaranteed to be uniqued and sorted by location.
  553.   std::vector<CoverageSegment>::const_iterator begin() const {
  554.     return Segments.begin();
  555.   }
  556.  
  557.   std::vector<CoverageSegment>::const_iterator end() const {
  558.     return Segments.end();
  559.   }
  560.  
  561.   bool empty() const { return Segments.empty(); }
  562.  
  563.   /// Expansions that can be further processed.
  564.   ArrayRef<ExpansionRecord> getExpansions() const { return Expansions; }
  565.  
  566.   /// Branches that can be further processed.
  567.   ArrayRef<CountedRegion> getBranches() const { return BranchRegions; }
  568. };
  569.  
  570. /// The mapping of profile information to coverage data.
  571. ///
  572. /// This is the main interface to get coverage information, using a profile to
  573. /// fill out execution counts.
  574. class CoverageMapping {
  575.   DenseMap<size_t, DenseSet<size_t>> RecordProvenance;
  576.   std::vector<FunctionRecord> Functions;
  577.   DenseMap<size_t, SmallVector<unsigned, 0>> FilenameHash2RecordIndices;
  578.   std::vector<std::pair<std::string, uint64_t>> FuncHashMismatches;
  579.  
  580.   CoverageMapping() = default;
  581.  
  582.   // Load coverage records from readers.
  583.   static Error loadFromReaders(
  584.       ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
  585.       IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage);
  586.  
  587.   // Load coverage records from file.
  588.   static Error
  589.   loadFromFile(StringRef Filename, StringRef Arch, StringRef CompilationDir,
  590.                IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage,
  591.                bool &DataFound,
  592.                SmallVectorImpl<object::BuildID> *FoundBinaryIDs = nullptr);
  593.  
  594.   /// Add a function record corresponding to \p Record.
  595.   Error loadFunctionRecord(const CoverageMappingRecord &Record,
  596.                            IndexedInstrProfReader &ProfileReader);
  597.  
  598.   /// Look up the indices for function records which are at least partially
  599.   /// defined in the specified file. This is guaranteed to return a superset of
  600.   /// such records: extra records not in the file may be included if there is
  601.   /// a hash collision on the filename. Clients must be robust to collisions.
  602.   ArrayRef<unsigned>
  603.   getImpreciseRecordIndicesForFilename(StringRef Filename) const;
  604.  
  605. public:
  606.   CoverageMapping(const CoverageMapping &) = delete;
  607.   CoverageMapping &operator=(const CoverageMapping &) = delete;
  608.  
  609.   /// Load the coverage mapping using the given readers.
  610.   static Expected<std::unique_ptr<CoverageMapping>>
  611.   load(ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
  612.        IndexedInstrProfReader &ProfileReader);
  613.  
  614.   /// Load the coverage mapping from the given object files and profile. If
  615.   /// \p Arches is non-empty, it must specify an architecture for each object.
  616.   /// Ignores non-instrumented object files unless all are not instrumented.
  617.   static Expected<std::unique_ptr<CoverageMapping>>
  618.   load(ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
  619.        ArrayRef<StringRef> Arches = std::nullopt, StringRef CompilationDir = "",
  620.        const object::BuildIDFetcher *BIDFetcher = nullptr);
  621.  
  622.   /// The number of functions that couldn't have their profiles mapped.
  623.   ///
  624.   /// This is a count of functions whose profile is out of date or otherwise
  625.   /// can't be associated with any coverage information.
  626.   unsigned getMismatchedCount() const { return FuncHashMismatches.size(); }
  627.  
  628.   /// A hash mismatch occurs when a profile record for a symbol does not have
  629.   /// the same hash as a coverage mapping record for the same symbol. This
  630.   /// returns a list of hash mismatches, where each mismatch is a pair of the
  631.   /// symbol name and its coverage mapping hash.
  632.   ArrayRef<std::pair<std::string, uint64_t>> getHashMismatches() const {
  633.     return FuncHashMismatches;
  634.   }
  635.  
  636.   /// Returns a lexicographically sorted, unique list of files that are
  637.   /// covered.
  638.   std::vector<StringRef> getUniqueSourceFiles() const;
  639.  
  640.   /// Get the coverage for a particular file.
  641.   ///
  642.   /// The given filename must be the name as recorded in the coverage
  643.   /// information. That is, only names returned from getUniqueSourceFiles will
  644.   /// yield a result.
  645.   CoverageData getCoverageForFile(StringRef Filename) const;
  646.  
  647.   /// Get the coverage for a particular function.
  648.   CoverageData getCoverageForFunction(const FunctionRecord &Function) const;
  649.  
  650.   /// Get the coverage for an expansion within a coverage set.
  651.   CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const;
  652.  
  653.   /// Gets all of the functions covered by this profile.
  654.   iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
  655.     return make_range(FunctionRecordIterator(Functions),
  656.                       FunctionRecordIterator());
  657.   }
  658.  
  659.   /// Gets all of the functions in a particular file.
  660.   iterator_range<FunctionRecordIterator>
  661.   getCoveredFunctions(StringRef Filename) const {
  662.     return make_range(FunctionRecordIterator(Functions, Filename),
  663.                       FunctionRecordIterator());
  664.   }
  665.  
  666.   /// Get the list of function instantiation groups in a particular file.
  667.   ///
  668.   /// Every instantiation group in a program is attributed to exactly one file:
  669.   /// the file in which the definition for the common function begins.
  670.   std::vector<InstantiationGroup>
  671.   getInstantiationGroups(StringRef Filename) const;
  672. };
  673.  
  674. /// Coverage statistics for a single line.
  675. class LineCoverageStats {
  676.   uint64_t ExecutionCount;
  677.   bool HasMultipleRegions;
  678.   bool Mapped;
  679.   unsigned Line;
  680.   ArrayRef<const CoverageSegment *> LineSegments;
  681.   const CoverageSegment *WrappedSegment;
  682.  
  683.   friend class LineCoverageIterator;
  684.   LineCoverageStats() = default;
  685.  
  686. public:
  687.   LineCoverageStats(ArrayRef<const CoverageSegment *> LineSegments,
  688.                     const CoverageSegment *WrappedSegment, unsigned Line);
  689.  
  690.   uint64_t getExecutionCount() const { return ExecutionCount; }
  691.  
  692.   bool hasMultipleRegions() const { return HasMultipleRegions; }
  693.  
  694.   bool isMapped() const { return Mapped; }
  695.  
  696.   unsigned getLine() const { return Line; }
  697.  
  698.   ArrayRef<const CoverageSegment *> getLineSegments() const {
  699.     return LineSegments;
  700.   }
  701.  
  702.   const CoverageSegment *getWrappedSegment() const { return WrappedSegment; }
  703. };
  704.  
  705. /// An iterator over the \c LineCoverageStats objects for lines described by
  706. /// a \c CoverageData instance.
  707. class LineCoverageIterator
  708.     : public iterator_facade_base<LineCoverageIterator,
  709.                                   std::forward_iterator_tag,
  710.                                   const LineCoverageStats> {
  711. public:
  712.   LineCoverageIterator(const CoverageData &CD)
  713.       : LineCoverageIterator(CD, CD.begin()->Line) {}
  714.  
  715.   LineCoverageIterator(const CoverageData &CD, unsigned Line)
  716.       : CD(CD), WrappedSegment(nullptr), Next(CD.begin()), Ended(false),
  717.         Line(Line) {
  718.     this->operator++();
  719.   }
  720.  
  721.   bool operator==(const LineCoverageIterator &R) const {
  722.     return &CD == &R.CD && Next == R.Next && Ended == R.Ended;
  723.   }
  724.  
  725.   const LineCoverageStats &operator*() const { return Stats; }
  726.  
  727.   LineCoverageIterator &operator++();
  728.  
  729.   LineCoverageIterator getEnd() const {
  730.     auto EndIt = *this;
  731.     EndIt.Next = CD.end();
  732.     EndIt.Ended = true;
  733.     return EndIt;
  734.   }
  735.  
  736. private:
  737.   const CoverageData &CD;
  738.   const CoverageSegment *WrappedSegment;
  739.   std::vector<CoverageSegment>::const_iterator Next;
  740.   bool Ended;
  741.   unsigned Line;
  742.   SmallVector<const CoverageSegment *, 4> Segments;
  743.   LineCoverageStats Stats;
  744. };
  745.  
  746. /// Get a \c LineCoverageIterator range for the lines described by \p CD.
  747. static inline iterator_range<LineCoverageIterator>
  748. getLineCoverageStats(const coverage::CoverageData &CD) {
  749.   auto Begin = LineCoverageIterator(CD);
  750.   auto End = Begin.getEnd();
  751.   return make_range(Begin, End);
  752. }
  753.  
  754. // Coverage mappping data (V2) has the following layout:
  755. // IPSK_covmap:
  756. //   [CoverageMapFileHeader]
  757. //   [ArrayStart]
  758. //    [CovMapFunctionRecordV2]
  759. //    [CovMapFunctionRecordV2]
  760. //    ...
  761. //   [ArrayEnd]
  762. //   [Encoded Filenames and Region Mapping Data]
  763. //
  764. // Coverage mappping data (V3) has the following layout:
  765. // IPSK_covmap:
  766. //   [CoverageMapFileHeader]
  767. //   [Encoded Filenames]
  768. // IPSK_covfun:
  769. //   [ArrayStart]
  770. //     odr_name_1: [CovMapFunctionRecordV3]
  771. //     odr_name_2: [CovMapFunctionRecordV3]
  772. //     ...
  773. //   [ArrayEnd]
  774. //
  775. // Both versions of the coverage mapping format encode the same information,
  776. // but the V3 format does so more compactly by taking advantage of linkonce_odr
  777. // semantics (it allows exactly 1 function record per name reference).
  778.  
  779. /// This namespace defines accessors shared by different versions of coverage
  780. /// mapping records.
  781. namespace accessors {
  782.  
  783. /// Return the structural hash associated with the function.
  784. template <class FuncRecordTy, support::endianness Endian>
  785. uint64_t getFuncHash(const FuncRecordTy *Record) {
  786.   return support::endian::byte_swap<uint64_t, Endian>(Record->FuncHash);
  787. }
  788.  
  789. /// Return the coverage map data size for the function.
  790. template <class FuncRecordTy, support::endianness Endian>
  791. uint64_t getDataSize(const FuncRecordTy *Record) {
  792.   return support::endian::byte_swap<uint32_t, Endian>(Record->DataSize);
  793. }
  794.  
  795. /// Return the function lookup key. The value is considered opaque.
  796. template <class FuncRecordTy, support::endianness Endian>
  797. uint64_t getFuncNameRef(const FuncRecordTy *Record) {
  798.   return support::endian::byte_swap<uint64_t, Endian>(Record->NameRef);
  799. }
  800.  
  801. /// Return the PGO name of the function. Used for formats in which the name is
  802. /// a hash.
  803. template <class FuncRecordTy, support::endianness Endian>
  804. Error getFuncNameViaRef(const FuncRecordTy *Record,
  805.                         InstrProfSymtab &ProfileNames, StringRef &FuncName) {
  806.   uint64_t NameRef = getFuncNameRef<FuncRecordTy, Endian>(Record);
  807.   FuncName = ProfileNames.getFuncName(NameRef);
  808.   return Error::success();
  809. }
  810.  
  811. /// Read coverage mapping out-of-line, from \p MappingBuf. This is used when the
  812. /// coverage mapping is attached to the file header, instead of to the function
  813. /// record.
  814. template <class FuncRecordTy, support::endianness Endian>
  815. StringRef getCoverageMappingOutOfLine(const FuncRecordTy *Record,
  816.                                       const char *MappingBuf) {
  817.   return {MappingBuf, size_t(getDataSize<FuncRecordTy, Endian>(Record))};
  818. }
  819.  
  820. /// Advance to the next out-of-line coverage mapping and its associated
  821. /// function record.
  822. template <class FuncRecordTy, support::endianness Endian>
  823. std::pair<const char *, const FuncRecordTy *>
  824. advanceByOneOutOfLine(const FuncRecordTy *Record, const char *MappingBuf) {
  825.   return {MappingBuf + getDataSize<FuncRecordTy, Endian>(Record), Record + 1};
  826. }
  827.  
  828. } // end namespace accessors
  829.  
  830. LLVM_PACKED_START
  831. template <class IntPtrT>
  832. struct CovMapFunctionRecordV1 {
  833.   using ThisT = CovMapFunctionRecordV1<IntPtrT>;
  834.  
  835. #define COVMAP_V1
  836. #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
  837. #include "llvm/ProfileData/InstrProfData.inc"
  838. #undef COVMAP_V1
  839.   CovMapFunctionRecordV1() = delete;
  840.  
  841.   template <support::endianness Endian> uint64_t getFuncHash() const {
  842.     return accessors::getFuncHash<ThisT, Endian>(this);
  843.   }
  844.  
  845.   template <support::endianness Endian> uint64_t getDataSize() const {
  846.     return accessors::getDataSize<ThisT, Endian>(this);
  847.   }
  848.  
  849.   /// Return function lookup key. The value is consider opaque.
  850.   template <support::endianness Endian> IntPtrT getFuncNameRef() const {
  851.     return support::endian::byte_swap<IntPtrT, Endian>(NamePtr);
  852.   }
  853.  
  854.   /// Return the PGO name of the function.
  855.   template <support::endianness Endian>
  856.   Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
  857.     IntPtrT NameRef = getFuncNameRef<Endian>();
  858.     uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize);
  859.     FuncName = ProfileNames.getFuncName(NameRef, NameS);
  860.     if (NameS && FuncName.empty())
  861.       return make_error<CoverageMapError>(coveragemap_error::malformed);
  862.     return Error::success();
  863.   }
  864.  
  865.   template <support::endianness Endian>
  866.   std::pair<const char *, const ThisT *>
  867.   advanceByOne(const char *MappingBuf) const {
  868.     return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf);
  869.   }
  870.  
  871.   template <support::endianness Endian> uint64_t getFilenamesRef() const {
  872.     llvm_unreachable("V1 function format does not contain a filenames ref");
  873.   }
  874.  
  875.   template <support::endianness Endian>
  876.   StringRef getCoverageMapping(const char *MappingBuf) const {
  877.     return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this,
  878.                                                                  MappingBuf);
  879.   }
  880. };
  881.  
  882. struct CovMapFunctionRecordV2 {
  883.   using ThisT = CovMapFunctionRecordV2;
  884.  
  885. #define COVMAP_V2
  886. #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
  887. #include "llvm/ProfileData/InstrProfData.inc"
  888. #undef COVMAP_V2
  889.   CovMapFunctionRecordV2() = delete;
  890.  
  891.   template <support::endianness Endian> uint64_t getFuncHash() const {
  892.     return accessors::getFuncHash<ThisT, Endian>(this);
  893.   }
  894.  
  895.   template <support::endianness Endian> uint64_t getDataSize() const {
  896.     return accessors::getDataSize<ThisT, Endian>(this);
  897.   }
  898.  
  899.   template <support::endianness Endian> uint64_t getFuncNameRef() const {
  900.     return accessors::getFuncNameRef<ThisT, Endian>(this);
  901.   }
  902.  
  903.   template <support::endianness Endian>
  904.   Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
  905.     return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames,
  906.                                                        FuncName);
  907.   }
  908.  
  909.   template <support::endianness Endian>
  910.   std::pair<const char *, const ThisT *>
  911.   advanceByOne(const char *MappingBuf) const {
  912.     return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf);
  913.   }
  914.  
  915.   template <support::endianness Endian> uint64_t getFilenamesRef() const {
  916.     llvm_unreachable("V2 function format does not contain a filenames ref");
  917.   }
  918.  
  919.   template <support::endianness Endian>
  920.   StringRef getCoverageMapping(const char *MappingBuf) const {
  921.     return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this,
  922.                                                                  MappingBuf);
  923.   }
  924. };
  925.  
  926. struct CovMapFunctionRecordV3 {
  927.   using ThisT = CovMapFunctionRecordV3;
  928.  
  929. #define COVMAP_V3
  930. #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
  931. #include "llvm/ProfileData/InstrProfData.inc"
  932. #undef COVMAP_V3
  933.   CovMapFunctionRecordV3() = delete;
  934.  
  935.   template <support::endianness Endian> uint64_t getFuncHash() const {
  936.     return accessors::getFuncHash<ThisT, Endian>(this);
  937.   }
  938.  
  939.   template <support::endianness Endian> uint64_t getDataSize() const {
  940.     return accessors::getDataSize<ThisT, Endian>(this);
  941.   }
  942.  
  943.   template <support::endianness Endian> uint64_t getFuncNameRef() const {
  944.     return accessors::getFuncNameRef<ThisT, Endian>(this);
  945.   }
  946.  
  947.   template <support::endianness Endian>
  948.   Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const {
  949.     return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames,
  950.                                                        FuncName);
  951.   }
  952.  
  953.   /// Get the filename set reference.
  954.   template <support::endianness Endian> uint64_t getFilenamesRef() const {
  955.     return support::endian::byte_swap<uint64_t, Endian>(FilenamesRef);
  956.   }
  957.  
  958.   /// Read the inline coverage mapping. Ignore the buffer parameter, it is for
  959.   /// out-of-line coverage mapping data only.
  960.   template <support::endianness Endian>
  961.   StringRef getCoverageMapping(const char *) const {
  962.     return StringRef(&CoverageMapping, getDataSize<Endian>());
  963.   }
  964.  
  965.   // Advance to the next inline coverage mapping and its associated function
  966.   // record. Ignore the out-of-line coverage mapping buffer.
  967.   template <support::endianness Endian>
  968.   std::pair<const char *, const CovMapFunctionRecordV3 *>
  969.   advanceByOne(const char *) const {
  970.     assert(isAddrAligned(Align(8), this) && "Function record not aligned");
  971.     const char *Next = ((const char *)this) + sizeof(CovMapFunctionRecordV3) -
  972.                        sizeof(char) + getDataSize<Endian>();
  973.     // Each function record has an alignment of 8, so we need to adjust
  974.     // alignment before reading the next record.
  975.     Next += offsetToAlignedAddr(Next, Align(8));
  976.     return {nullptr, reinterpret_cast<const CovMapFunctionRecordV3 *>(Next)};
  977.   }
  978. };
  979.  
  980. // Per module coverage mapping data header, i.e. CoverageMapFileHeader
  981. // documented above.
  982. struct CovMapHeader {
  983. #define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
  984. #include "llvm/ProfileData/InstrProfData.inc"
  985.   template <support::endianness Endian> uint32_t getNRecords() const {
  986.     return support::endian::byte_swap<uint32_t, Endian>(NRecords);
  987.   }
  988.  
  989.   template <support::endianness Endian> uint32_t getFilenamesSize() const {
  990.     return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
  991.   }
  992.  
  993.   template <support::endianness Endian> uint32_t getCoverageSize() const {
  994.     return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
  995.   }
  996.  
  997.   template <support::endianness Endian> uint32_t getVersion() const {
  998.     return support::endian::byte_swap<uint32_t, Endian>(Version);
  999.   }
  1000. };
  1001.  
  1002. LLVM_PACKED_END
  1003.  
  1004. enum CovMapVersion {
  1005.   Version1 = 0,
  1006.   // Function's name reference from CovMapFuncRecord is changed from raw
  1007.   // name string pointer to MD5 to support name section compression. Name
  1008.   // section is also compressed.
  1009.   Version2 = 1,
  1010.   // A new interpretation of the columnEnd field is added in order to mark
  1011.   // regions as gap areas.
  1012.   Version3 = 2,
  1013.   // Function records are named, uniqued, and moved to a dedicated section.
  1014.   Version4 = 3,
  1015.   // Branch regions referring to two counters are added
  1016.   Version5 = 4,
  1017.   // Compilation directory is stored separately and combined with relative
  1018.   // filenames to produce an absolute file path.
  1019.   Version6 = 5,
  1020.   // The current version is Version6.
  1021.   CurrentVersion = INSTR_PROF_COVMAP_VERSION
  1022. };
  1023.  
  1024. template <int CovMapVersion, class IntPtrT> struct CovMapTraits {
  1025.   using CovMapFuncRecordType = CovMapFunctionRecordV3;
  1026.   using NameRefType = uint64_t;
  1027. };
  1028.  
  1029. template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version3, IntPtrT> {
  1030.   using CovMapFuncRecordType = CovMapFunctionRecordV2;
  1031.   using NameRefType = uint64_t;
  1032. };
  1033.  
  1034. template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version2, IntPtrT> {
  1035.   using CovMapFuncRecordType = CovMapFunctionRecordV2;
  1036.   using NameRefType = uint64_t;
  1037. };
  1038.  
  1039. template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> {
  1040.   using CovMapFuncRecordType = CovMapFunctionRecordV1<IntPtrT>;
  1041.   using NameRefType = IntPtrT;
  1042. };
  1043.  
  1044. } // end namespace coverage
  1045.  
  1046. /// Provide DenseMapInfo for CounterExpression
  1047. template<> struct DenseMapInfo<coverage::CounterExpression> {
  1048.   static inline coverage::CounterExpression getEmptyKey() {
  1049.     using namespace coverage;
  1050.  
  1051.     return CounterExpression(CounterExpression::ExprKind::Subtract,
  1052.                              Counter::getCounter(~0U),
  1053.                              Counter::getCounter(~0U));
  1054.   }
  1055.  
  1056.   static inline coverage::CounterExpression getTombstoneKey() {
  1057.     using namespace coverage;
  1058.  
  1059.     return CounterExpression(CounterExpression::ExprKind::Add,
  1060.                              Counter::getCounter(~0U),
  1061.                              Counter::getCounter(~0U));
  1062.   }
  1063.  
  1064.   static unsigned getHashValue(const coverage::CounterExpression &V) {
  1065.     return static_cast<unsigned>(
  1066.         hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
  1067.                      V.RHS.getKind(), V.RHS.getCounterID()));
  1068.   }
  1069.  
  1070.   static bool isEqual(const coverage::CounterExpression &LHS,
  1071.                       const coverage::CounterExpression &RHS) {
  1072.     return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
  1073.   }
  1074. };
  1075.  
  1076. } // end namespace llvm
  1077.  
  1078. #endif // LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H
  1079.