Move coverage related code into a separate library

[eraman]

Summary

Recently, I ran into a circular dependency problem when I made Analysis depend on ProfileData. See http://lists.llvm.org/pipermail/llvm-dev/2016-April/098400.html for more context. ProfileData has an existing dependence on Analysis through Object and Bitcode. Only the Coverage code depends on Object. Splitting Coverage data into its own library removes the ProfileData->Analysis dependence. Does this seem reasonable?

Notes:

• I have modeled this on Codegen which has some files underneath as well as subdirs that correspond to separate libraries.
• Clang code that includes coverage headers need to be changed as well. Will send a patch once there is a general agreement on this patch.
• I have used "svn mv" to move coverage related code into the new directory to preserver history.
• I have not split the ProfileData unittest to a separate Coverage directory thinking there will be only one file there, but perhaps that also needs to be split?
• check-all runs successfully, but it's quite likely that I have overlooked something.

[vsk]

Thanks for doing this. I don't see any 'gotchas' here. This lgtm so long as it passes check-{llvm,profile}.

[eraman]

Justin, does this look good?

[eraman]

Justin, independent of the fact that this is really not a blocker for the profile summary change (as you point out in another thread), this seems like a desirable change to separate coverage from the rest of the ProfileData. Does that make sense?

llvm/trunk/include/llvm/ProfileData/Coverage/CoverageMapping.h

+//=-- CoverageMapping.h - Code coverage mapping support ---------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Code coverage mapping data is generated by clang and read by
+// llvm-cov to show code coverage statistics for a file.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_
+#define LLVM_PROFILEDATA_COVERAGEMAPPING_H_
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ProfileData/InstrProf.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/ErrorOr.h"
+#include "llvm/Support/raw_ostream.h"
+#include <system_error>
+#include <tuple>
+
+namespace llvm {
+namespace coverage {
+enum class coveragemap_error {
+  success = 0,
+  eof,
+  no_data_found,
+  unsupported_version,
+  truncated,
+  malformed
+};
+} // end of coverage namespace.
+}
+
+namespace std {
+template <>
+struct is_error_code_enum<llvm::coverage::coveragemap_error> : std::true_type {
+};
+}
+
+namespace llvm {
+class IndexedInstrProfReader;
+namespace coverage {
+
+class CoverageMappingReader;
+
+class CoverageMapping;
+struct CounterExpressions;
+
+/// \brief A Counter is an abstract value that describes how to compute the
+/// execution count for a region of code using the collected profile count data.
+struct Counter {
+  enum CounterKind { Zero, CounterValueReference, Expression };
+  static const unsigned EncodingTagBits = 2;
+  static const unsigned EncodingTagMask = 0x3;
+  static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
+      EncodingTagBits + 1;
+
+private:
+  CounterKind Kind;
+  unsigned ID;
+
+  Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
+
+public:
+  Counter() : Kind(Zero), ID(0) {}
+
+  CounterKind getKind() const { return Kind; }
+
+  bool isZero() const { return Kind == Zero; }
+
+  bool isExpression() const { return Kind == Expression; }
+
+  unsigned getCounterID() const { return ID; }
+
+  unsigned getExpressionID() const { return ID; }
+
+  friend bool operator==(const Counter &LHS, const Counter &RHS) {
+    return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
+  }
+
+  friend bool operator!=(const Counter &LHS, const Counter &RHS) {
+    return !(LHS == RHS);
+  }
+
+  friend bool operator<(const Counter &LHS, const Counter &RHS) {
+    return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
+  }
+
+  /// \brief Return the counter that represents the number zero.
+  static Counter getZero() { return Counter(); }
+
+  /// \brief Return the counter that corresponds to a specific profile counter.
+  static Counter getCounter(unsigned CounterId) {
+    return Counter(CounterValueReference, CounterId);
+  }
+
+  /// \brief Return the counter that corresponds to a specific
+  /// addition counter expression.
+  static Counter getExpression(unsigned ExpressionId) {
+    return Counter(Expression, ExpressionId);
+  }
+};
+
+/// \brief A Counter expression is a value that represents an arithmetic
+/// operation with two counters.
+struct CounterExpression {
+  enum ExprKind { Subtract, Add };
+  ExprKind Kind;
+  Counter LHS, RHS;
+
+  CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
+      : Kind(Kind), LHS(LHS), RHS(RHS) {}
+};
+
+/// \brief A Counter expression builder is used to construct the
+/// counter expressions. It avoids unnecessary duplication
+/// and simplifies algebraic expressions.
+class CounterExpressionBuilder {
+  /// \brief A list of all the counter expressions
+  std::vector<CounterExpression> Expressions;
+  /// \brief A lookup table for the index of a given expression.
+  llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
+
+  /// \brief Return the counter which corresponds to the given expression.
+  ///
+  /// If the given expression is already stored in the builder, a counter
+  /// that references that expression is returned. Otherwise, the given
+  /// expression is added to the builder's collection of expressions.
+  Counter get(const CounterExpression &E);
+
+  /// \brief Gather the terms of the expression tree for processing.
+  ///
+  /// This collects each addition and subtraction referenced by the counter into
+  /// a sequence that can be sorted and combined to build a simplified counter
+  /// expression.
+  void extractTerms(Counter C, int Sign,
+                    SmallVectorImpl<std::pair<unsigned, int>> &Terms);
+
+  /// \brief Simplifies the given expression tree
+  /// by getting rid of algebraically redundant operations.
+  Counter simplify(Counter ExpressionTree);
+
+public:
+  ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
+
+  /// \brief Return a counter that represents the expression
+  /// that adds LHS and RHS.
+  Counter add(Counter LHS, Counter RHS);
+
+  /// \brief Return a counter that represents the expression
+  /// that subtracts RHS from LHS.
+  Counter subtract(Counter LHS, Counter RHS);
+};
+
+/// \brief A Counter mapping region associates a source range with
+/// a specific counter.
+struct CounterMappingRegion {
+  enum RegionKind {
+    /// \brief A CodeRegion associates some code with a counter
+    CodeRegion,
+
+    /// \brief An ExpansionRegion represents a file expansion region that
+    /// associates a source range with the expansion of a virtual source file,
+    /// such as for a macro instantiation or #include file.
+    ExpansionRegion,
+
+    /// \brief A SkippedRegion represents a source range with code that
+    /// was skipped by a preprocessor or similar means.
+    SkippedRegion
+  };
+
+  Counter Count;
+  unsigned FileID, ExpandedFileID;
+  unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
+  RegionKind Kind;
+
+  CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
+                       unsigned LineStart, unsigned ColumnStart,
+                       unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
+      : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
+        LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
+        ColumnEnd(ColumnEnd), Kind(Kind) {}
+
+  static CounterMappingRegion
+  makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
+             unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
+    return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
+                                LineEnd, ColumnEnd, CodeRegion);
+  }
+
+  static CounterMappingRegion
+  makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
+                unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
+    return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
+                                ColumnStart, LineEnd, ColumnEnd,
+                                ExpansionRegion);
+  }
+
+  static CounterMappingRegion
+  makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
+              unsigned LineEnd, unsigned ColumnEnd) {
+    return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
+                                LineEnd, ColumnEnd, SkippedRegion);
+  }
+
+
+  inline std::pair<unsigned, unsigned> startLoc() const {
+    return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
+  }
+
+  inline std::pair<unsigned, unsigned> endLoc() const {
+    return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
+  }
+
+  bool operator<(const CounterMappingRegion &Other) const {
+    if (FileID != Other.FileID)
+      return FileID < Other.FileID;
+    return startLoc() < Other.startLoc();
+  }
+
+  bool contains(const CounterMappingRegion &Other) const {
+    if (FileID != Other.FileID)
+      return false;
+    if (startLoc() > Other.startLoc())
+      return false;
+    if (endLoc() < Other.endLoc())
+      return false;
+    return true;
+  }
+};
+
+/// \brief Associates a source range with an execution count.
+struct CountedRegion : public CounterMappingRegion {
+  uint64_t ExecutionCount;
+
+  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
+      : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
+};
+
+/// \brief A Counter mapping context is used to connect the counters,
+/// expressions and the obtained counter values.
+class CounterMappingContext {
+  ArrayRef<CounterExpression> Expressions;
+  ArrayRef<uint64_t> CounterValues;
+
+public:
+  CounterMappingContext(ArrayRef<CounterExpression> Expressions,
+                        ArrayRef<uint64_t> CounterValues = None)
+      : Expressions(Expressions), CounterValues(CounterValues) {}
+
+  void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
+
+  void dump(const Counter &C, llvm::raw_ostream &OS) const;
+  void dump(const Counter &C) const { dump(C, dbgs()); }
+
+  /// \brief Return the number of times that a region of code associated with
+  /// this counter was executed.
+  ErrorOr<int64_t> evaluate(const Counter &C) const;
+};
+
+/// \brief Code coverage information for a single function.
+struct FunctionRecord {
+  /// \brief Raw function name.
+  std::string Name;
+  /// \brief Associated files.
+  std::vector<std::string> Filenames;
+  /// \brief Regions in the function along with their counts.
+  std::vector<CountedRegion> CountedRegions;
+  /// \brief The number of times this function was executed.
+  uint64_t ExecutionCount;
+
+  FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
+      : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
+
+  void pushRegion(CounterMappingRegion Region, uint64_t Count) {
+    if (CountedRegions.empty())
+      ExecutionCount = Count;
+    CountedRegions.emplace_back(Region, Count);
+  }
+};
+
+/// \brief Iterator over Functions, optionally filtered to a single file.
+class FunctionRecordIterator
+    : public iterator_facade_base<FunctionRecordIterator,
+                                  std::forward_iterator_tag, FunctionRecord> {
+  ArrayRef<FunctionRecord> Records;
+  ArrayRef<FunctionRecord>::iterator Current;
+  StringRef Filename;
+
+  /// \brief Skip records whose primary file is not \c Filename.
+  void skipOtherFiles();
+
+public:
+  FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
+                         StringRef Filename = "")
+      : Records(Records_), Current(Records.begin()), Filename(Filename) {
+    skipOtherFiles();
+  }
+
+  FunctionRecordIterator() : Current(Records.begin()) {}
+
+  bool operator==(const FunctionRecordIterator &RHS) const {
+    return Current == RHS.Current && Filename == RHS.Filename;
+  }
+
+  const FunctionRecord &operator*() const { return *Current; }
+
+  FunctionRecordIterator &operator++() {
+    assert(Current != Records.end() && "incremented past end");
+    ++Current;
+    skipOtherFiles();
+    return *this;
+  }
+};
+
+/// \brief Coverage information for a macro expansion or #included file.
+///
+/// When covered code has pieces that can be expanded for more detail, such as a
+/// preprocessor macro use and its definition, these are represented as
+/// expansions whose coverage can be looked up independently.
+struct ExpansionRecord {
+  /// \brief The abstract file this expansion covers.
+  unsigned FileID;
+  /// \brief The region that expands to this record.
+  const CountedRegion &Region;
+  /// \brief Coverage for the expansion.
+  const FunctionRecord &Function;
+
+  ExpansionRecord(const CountedRegion &Region,
+                  const FunctionRecord &Function)
+      : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
+};
+
+/// \brief The execution count information starting at a point in a file.
+///
+/// A sequence of CoverageSegments gives execution counts for a file in format
+/// that's simple to iterate through for processing.
+struct CoverageSegment {
+  /// \brief The line where this segment begins.
+  unsigned Line;
+  /// \brief The column where this segment begins.
+  unsigned Col;
+  /// \brief The execution count, or zero if no count was recorded.
+  uint64_t Count;
+  /// \brief When false, the segment was uninstrumented or skipped.
+  bool HasCount;
+  /// \brief Whether this enters a new region or returns to a previous count.
+  bool IsRegionEntry;
+
+  CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
+      : Line(Line), Col(Col), Count(0), HasCount(false),
+        IsRegionEntry(IsRegionEntry) {}
+
+  CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
+                  bool IsRegionEntry)
+      : Line(Line), Col(Col), Count(Count), HasCount(true),
+        IsRegionEntry(IsRegionEntry) {}
+
+  friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
+    return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
+           std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
+  }
+};
+
+/// \brief Coverage information to be processed or displayed.
+///
+/// This represents the coverage of an entire file, expansion, or function. It
+/// provides a sequence of CoverageSegments to iterate through, as well as the
+/// list of expansions that can be further processed.
+class CoverageData {
+  std::string Filename;
+  std::vector<CoverageSegment> Segments;
+  std::vector<ExpansionRecord> Expansions;
+  friend class CoverageMapping;
+
+public:
+  CoverageData() {}
+
+  CoverageData(StringRef Filename) : Filename(Filename) {}
+
+  CoverageData(CoverageData &&RHS)
+      : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
+        Expansions(std::move(RHS.Expansions)) {}
+
+  /// \brief Get the name of the file this data covers.
+  StringRef getFilename() { return Filename; }
+
+  std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
+  std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
+  bool empty() { return Segments.empty(); }
+
+  /// \brief Expansions that can be further processed.
+  std::vector<ExpansionRecord> getExpansions() { return Expansions; }
+};
+
+/// \brief The mapping of profile information to coverage data.
+///
+/// This is the main interface to get coverage information, using a profile to
+/// fill out execution counts.
+class CoverageMapping {
+  std::vector<FunctionRecord> Functions;
+  unsigned MismatchedFunctionCount;
+
+  CoverageMapping() : MismatchedFunctionCount(0) {}
+
+public:
+  /// \brief Load the coverage mapping using the given readers.
+  static ErrorOr<std::unique_ptr<CoverageMapping>>
+  load(CoverageMappingReader &CoverageReader,
+       IndexedInstrProfReader &ProfileReader);
+
+  /// \brief Load the coverage mapping from the given files.
+  static ErrorOr<std::unique_ptr<CoverageMapping>>
+  load(StringRef ObjectFilename, StringRef ProfileFilename,
+       StringRef Arch = StringRef());
+
+  /// \brief The number of functions that couldn't have their profiles mapped.
+  ///
+  /// This is a count of functions whose profile is out of date or otherwise
+  /// can't be associated with any coverage information.
+  unsigned getMismatchedCount() { return MismatchedFunctionCount; }
+
+  /// \brief Returns the list of files that are covered.
+  std::vector<StringRef> getUniqueSourceFiles() const;
+
+  /// \brief Get the coverage for a particular file.
+  ///
+  /// The given filename must be the name as recorded in the coverage
+  /// information. That is, only names returned from getUniqueSourceFiles will
+  /// yield a result.
+  CoverageData getCoverageForFile(StringRef Filename);
+
+  /// \brief Gets all of the functions covered by this profile.
+  iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
+    return make_range(FunctionRecordIterator(Functions),
+                      FunctionRecordIterator());
+  }
+
+  /// \brief Gets all of the functions in a particular file.
+  iterator_range<FunctionRecordIterator>
+  getCoveredFunctions(StringRef Filename) const {
+    return make_range(FunctionRecordIterator(Functions, Filename),
+                      FunctionRecordIterator());
+  }
+
+  /// \brief Get the list of function instantiations in the file.
+  ///
+  /// Functions that are instantiated more than once, such as C++ template
+  /// specializations, have distinct coverage records for each instantiation.
+  std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
+
+  /// \brief Get the coverage for a particular function.
+  CoverageData getCoverageForFunction(const FunctionRecord &Function);
+
+  /// \brief Get the coverage for an expansion within a coverage set.
+  CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
+};
+
+const std::error_category &coveragemap_category();
+
+inline std::error_code make_error_code(coveragemap_error E) {
+  return std::error_code(static_cast<int>(E), coveragemap_category());
+}
+
+// Profile coverage map has the following layout:
+// [CoverageMapFileHeader]
+// [ArrayStart]
+//  [CovMapFunctionRecord]
+//  [CovMapFunctionRecord]
+//  ...
+// [ArrayEnd]
+// [Encoded Region Mapping Data]
+LLVM_PACKED_START
+template <class IntPtrT> struct CovMapFunctionRecordV1 {
+#define COVMAP_V1
+#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
+#include "llvm/ProfileData/InstrProfData.inc"
+#undef COVMAP_V1
+
+  // Return the structural hash associated with the function.
+  template <support::endianness Endian> uint64_t getFuncHash() const {
+    return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
+  }
+  // Return the coverage map data size for the funciton.
+  template <support::endianness Endian> uint32_t getDataSize() const {
+    return support::endian::byte_swap<uint32_t, Endian>(DataSize);
+  }
+  // Return function lookup key. The value is consider opaque.
+  template <support::endianness Endian> IntPtrT getFuncNameRef() const {
+    return support::endian::byte_swap<IntPtrT, Endian>(NamePtr);
+  }
+  // Return the PGO name of the function */
+  template <support::endianness Endian>
+  std::error_code getFuncName(InstrProfSymtab &ProfileNames,
+                              StringRef &FuncName) const {
+    IntPtrT NameRef = getFuncNameRef<Endian>();
+    uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize);
+    FuncName = ProfileNames.getFuncName(NameRef, NameS);
+    if (NameS && FuncName.empty())
+      return coveragemap_error::malformed;
+    return std::error_code();
+  }
+};
+
+struct CovMapFunctionRecord {
+#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
+#include "llvm/ProfileData/InstrProfData.inc"
+
+  // Return the structural hash associated with the function.
+  template <support::endianness Endian> uint64_t getFuncHash() const {
+    return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
+  }
+  // Return the coverage map data size for the funciton.
+  template <support::endianness Endian> uint32_t getDataSize() const {
+    return support::endian::byte_swap<uint32_t, Endian>(DataSize);
+  }
+  // Return function lookup key. The value is consider opaque.
+  template <support::endianness Endian> uint64_t getFuncNameRef() const {
+    return support::endian::byte_swap<uint64_t, Endian>(NameRef);
+  }
+  // Return the PGO name of the function */
+  template <support::endianness Endian>
+  std::error_code getFuncName(InstrProfSymtab &ProfileNames,
+                              StringRef &FuncName) const {
+    uint64_t NameRef = getFuncNameRef<Endian>();
+    FuncName = ProfileNames.getFuncName(NameRef);
+    return std::error_code();
+  }
+};
+
+// Per module coverage mapping data header, i.e. CoverageMapFileHeader
+// documented above.
+struct CovMapHeader {
+#define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
+#include "llvm/ProfileData/InstrProfData.inc"
+  template <support::endianness Endian> uint32_t getNRecords() const {
+    return support::endian::byte_swap<uint32_t, Endian>(NRecords);
+  }
+  template <support::endianness Endian> uint32_t getFilenamesSize() const {
+    return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
+  }
+  template <support::endianness Endian> uint32_t getCoverageSize() const {
+    return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
+  }
+  template <support::endianness Endian> uint32_t getVersion() const {
+    return support::endian::byte_swap<uint32_t, Endian>(Version);
+  }
+};
+
+LLVM_PACKED_END
+
+enum CovMapVersion {
+  Version1 = 0,
+  // Function's name reference from CovMapFuncRecord is changed from raw
+  // name string pointer to MD5 to support name section compression. Name
+  // section is also compressed.
+  Version2 = 1,
+  // The current version is Version2
+  CurrentVersion = INSTR_PROF_COVMAP_VERSION
+};
+
+template <int CovMapVersion, class IntPtrT> struct CovMapTraits {
+  typedef CovMapFunctionRecord CovMapFuncRecordType;
+  typedef uint64_t NameRefType;
+};
+
+template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> {
+  typedef CovMapFunctionRecordV1<IntPtrT> CovMapFuncRecordType;
+  typedef IntPtrT NameRefType;
+};
+
+} // end namespace coverage
+
+/// \brief Provide DenseMapInfo for CounterExpression
+template<> struct DenseMapInfo<coverage::CounterExpression> {
+  static inline coverage::CounterExpression getEmptyKey() {
+    using namespace coverage;
+    return CounterExpression(CounterExpression::ExprKind::Subtract,
+                             Counter::getCounter(~0U),
+                             Counter::getCounter(~0U));
+  }
+
+  static inline coverage::CounterExpression getTombstoneKey() {
+    using namespace coverage;
+    return CounterExpression(CounterExpression::ExprKind::Add,
+                             Counter::getCounter(~0U),
+                             Counter::getCounter(~0U));
+  }
+
+  static unsigned getHashValue(const coverage::CounterExpression &V) {
+    return static_cast<unsigned>(
+        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
+                     V.RHS.getKind(), V.RHS.getCounterID()));
+  }
+
+  static bool isEqual(const coverage::CounterExpression &LHS,
+                      const coverage::CounterExpression &RHS) {
+    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
+  }
+};
+
+} // end namespace llvm
+
+#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_

llvm/trunk/include/llvm/ProfileData/Coverage/CoverageMappingReader.h

+//=-- CoverageMappingReader.h - Code coverage mapping reader ------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for reading coverage mapping data for
+// instrumentation based coverage.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PROFILEDATA_COVERAGEMAPPINGREADER_H
+#define LLVM_PROFILEDATA_COVERAGEMAPPINGREADER_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
+#include "llvm/ProfileData/InstrProf.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include <iterator>
+
+namespace llvm {
+namespace coverage {
+
+class CoverageMappingReader;
+
+/// \brief Coverage mapping information for a single function.
+struct CoverageMappingRecord {
+  StringRef FunctionName;
+  uint64_t FunctionHash;
+  ArrayRef<StringRef> Filenames;
+  ArrayRef<CounterExpression> Expressions;
+  ArrayRef<CounterMappingRegion> MappingRegions;
+};
+
+/// \brief A file format agnostic iterator over coverage mapping data.
+class CoverageMappingIterator
+    : public std::iterator<std::input_iterator_tag, CoverageMappingRecord> {
+  CoverageMappingReader *Reader;
+  CoverageMappingRecord Record;
+
+  void increment();
+
+public:
+  CoverageMappingIterator() : Reader(nullptr) {}
+  CoverageMappingIterator(CoverageMappingReader *Reader) : Reader(Reader) {
+    increment();
+  }
+
+  CoverageMappingIterator &operator++() {
+    increment();
+    return *this;
+  }
+  bool operator==(const CoverageMappingIterator &RHS) {
+    return Reader == RHS.Reader;
+  }
+  bool operator!=(const CoverageMappingIterator &RHS) {
+    return Reader != RHS.Reader;
+  }
+  CoverageMappingRecord &operator*() { return Record; }
+  CoverageMappingRecord *operator->() { return &Record; }
+};
+
+class CoverageMappingReader {
+public:
+  virtual std::error_code readNextRecord(CoverageMappingRecord &Record) = 0;
+  CoverageMappingIterator begin() { return CoverageMappingIterator(this); }
+  CoverageMappingIterator end() { return CoverageMappingIterator(); }
+  virtual ~CoverageMappingReader() {}
+};
+
+/// \brief Base class for the raw coverage mapping and filenames data readers.
+class RawCoverageReader {
+protected:
+  StringRef Data;
+
+  RawCoverageReader(StringRef Data) : Data(Data) {}
+
+  std::error_code readULEB128(uint64_t &Result);
+  std::error_code readIntMax(uint64_t &Result, uint64_t MaxPlus1);
+  std::error_code readSize(uint64_t &Result);
+  std::error_code readString(StringRef &Result);
+};
+
+/// \brief Reader for the raw coverage filenames.
+class RawCoverageFilenamesReader : public RawCoverageReader {
+  std::vector<StringRef> &Filenames;
+
+  RawCoverageFilenamesReader(const RawCoverageFilenamesReader &) = delete;
+  RawCoverageFilenamesReader &
+  operator=(const RawCoverageFilenamesReader &) = delete;
+
+public:
+  RawCoverageFilenamesReader(StringRef Data, std::vector<StringRef> &Filenames)
+      : RawCoverageReader(Data), Filenames(Filenames) {}
+
+  std::error_code read();
+};
+
+/// \brief Reader for the raw coverage mapping data.
+class RawCoverageMappingReader : public RawCoverageReader {
+  ArrayRef<StringRef> TranslationUnitFilenames;
+  std::vector<StringRef> &Filenames;
+  std::vector<CounterExpression> &Expressions;
+  std::vector<CounterMappingRegion> &MappingRegions;
+
+  RawCoverageMappingReader(const RawCoverageMappingReader &) = delete;
+  RawCoverageMappingReader &
+  operator=(const RawCoverageMappingReader &) = delete;
+
+public:
+  RawCoverageMappingReader(StringRef MappingData,
+                           ArrayRef<StringRef> TranslationUnitFilenames,
+                           std::vector<StringRef> &Filenames,
+                           std::vector<CounterExpression> &Expressions,
+                           std::vector<CounterMappingRegion> &MappingRegions)
+      : RawCoverageReader(MappingData),
+        TranslationUnitFilenames(TranslationUnitFilenames),
+        Filenames(Filenames), Expressions(Expressions),
+        MappingRegions(MappingRegions) {}
+
+  std::error_code read();
+
+private:
+  std::error_code decodeCounter(unsigned Value, Counter &C);
+  std::error_code readCounter(Counter &C);
+  std::error_code
+  readMappingRegionsSubArray(std::vector<CounterMappingRegion> &MappingRegions,
+                             unsigned InferredFileID, size_t NumFileIDs);
+};
+
+/// \brief Reader for the coverage mapping data that is emitted by the
+/// frontend and stored in an object file.
+class BinaryCoverageReader : public CoverageMappingReader {
+public:
+  struct ProfileMappingRecord {
+    CovMapVersion Version;
+    StringRef FunctionName;
+    uint64_t FunctionHash;
+    StringRef CoverageMapping;
+    size_t FilenamesBegin;
+    size_t FilenamesSize;
+
+    ProfileMappingRecord(CovMapVersion Version, StringRef FunctionName,
+                         uint64_t FunctionHash, StringRef CoverageMapping,
+                         size_t FilenamesBegin, size_t FilenamesSize)
+        : Version(Version), FunctionName(FunctionName),
+          FunctionHash(FunctionHash), CoverageMapping(CoverageMapping),
+          FilenamesBegin(FilenamesBegin), FilenamesSize(FilenamesSize) {}
+  };
+
+private:
+  std::vector<StringRef> Filenames;
+  std::vector<ProfileMappingRecord> MappingRecords;
+  InstrProfSymtab ProfileNames;
+  size_t CurrentRecord;
+  std::vector<StringRef> FunctionsFilenames;
+  std::vector<CounterExpression> Expressions;
+  std::vector<CounterMappingRegion> MappingRegions;
+
+  BinaryCoverageReader(const BinaryCoverageReader &) = delete;
+  BinaryCoverageReader &operator=(const BinaryCoverageReader &) = delete;
+
+  BinaryCoverageReader() : CurrentRecord(0) {}
+
+public:
+  static ErrorOr<std::unique_ptr<BinaryCoverageReader>>
+  create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
+         StringRef Arch);
+
+  std::error_code readNextRecord(CoverageMappingRecord &Record) override;
+};
+
+} // end namespace coverage
+} // end namespace llvm
+
+#endif

llvm/trunk/include/llvm/ProfileData/Coverage/CoverageMappingWriter.h

+//=-- CoverageMappingWriter.h - Code coverage mapping writer ------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for writing coverage mapping data for
+// instrumentation based coverage.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PROFILEDATA_COVERAGEMAPPINGWRITER_H
+#define LLVM_PROFILEDATA_COVERAGEMAPPINGWRITER_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+namespace coverage {
+
+/// \brief Writer of the filenames section for the instrumentation
+/// based code coverage.
+class CoverageFilenamesSectionWriter {
+  ArrayRef<StringRef> Filenames;
+
+public:
+  CoverageFilenamesSectionWriter(ArrayRef<StringRef> Filenames)
+      : Filenames(Filenames) {}
+
+  /// \brief Write encoded filenames to the given output stream.
+  void write(raw_ostream &OS);
+};
+
+/// \brief Writer for instrumentation based coverage mapping data.
+class CoverageMappingWriter {
+  ArrayRef<unsigned> VirtualFileMapping;
+  ArrayRef<CounterExpression> Expressions;
+  MutableArrayRef<CounterMappingRegion> MappingRegions;
+
+public:
+  CoverageMappingWriter(ArrayRef<unsigned> VirtualFileMapping,
+                        ArrayRef<CounterExpression> Expressions,
+                        MutableArrayRef<CounterMappingRegion> MappingRegions)
+      : VirtualFileMapping(VirtualFileMapping), Expressions(Expressions),
+        MappingRegions(MappingRegions) {}
+
+  CoverageMappingWriter(ArrayRef<CounterExpression> Expressions,
+                        MutableArrayRef<CounterMappingRegion> MappingRegions)
+      : Expressions(Expressions), MappingRegions(MappingRegions) {}
+
+  /// \brief Write encoded coverage mapping data to the given output stream.
+  void write(raw_ostream &OS);
+};
+
+} // end namespace coverage
+} // end namespace llvm
+
+#endif

llvm/trunk/include/llvm/ProfileData/CoverageMapping.h

-//=-- CoverageMapping.h - Code coverage mapping support ---------*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Code coverage mapping data is generated by clang and read by
-// llvm-cov to show code coverage statistics for a file.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_
-#define LLVM_PROFILEDATA_COVERAGEMAPPING_H_
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Hashing.h"
-#include "llvm/ADT/Triple.h"
-#include "llvm/ADT/iterator.h"
-#include "llvm/ProfileData/InstrProf.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Endian.h"
-#include "llvm/Support/ErrorOr.h"
-#include "llvm/Support/raw_ostream.h"
-#include <system_error>
-#include <tuple>
-
-namespace llvm {
-namespace coverage {
-enum class coveragemap_error {
-  success = 0,
-  eof,
-  no_data_found,
-  unsupported_version,
-  truncated,
-  malformed
-};
-} // end of coverage namespace.
-}
-
-namespace std {
-template <>
-struct is_error_code_enum<llvm::coverage::coveragemap_error> : std::true_type {
-};
-}
-
-namespace llvm {
-class IndexedInstrProfReader;
-namespace coverage {
-
-class CoverageMappingReader;
-
-class CoverageMapping;
-struct CounterExpressions;
-
-/// \brief A Counter is an abstract value that describes how to compute the
-/// execution count for a region of code using the collected profile count data.
-struct Counter {
-  enum CounterKind { Zero, CounterValueReference, Expression };
-  static const unsigned EncodingTagBits = 2;
-  static const unsigned EncodingTagMask = 0x3;
-  static const unsigned EncodingCounterTagAndExpansionRegionTagBits =
-      EncodingTagBits + 1;
-
-private:
-  CounterKind Kind;
-  unsigned ID;
-
-  Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {}
-
-public:
-  Counter() : Kind(Zero), ID(0) {}
-
-  CounterKind getKind() const { return Kind; }
-
-  bool isZero() const { return Kind == Zero; }
-
-  bool isExpression() const { return Kind == Expression; }
-
-  unsigned getCounterID() const { return ID; }
-
-  unsigned getExpressionID() const { return ID; }
-
-  friend bool operator==(const Counter &LHS, const Counter &RHS) {
-    return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID;
-  }
-
-  friend bool operator!=(const Counter &LHS, const Counter &RHS) {
-    return !(LHS == RHS);
-  }
-
-  friend bool operator<(const Counter &LHS, const Counter &RHS) {
-    return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID);
-  }
-
-  /// \brief Return the counter that represents the number zero.
-  static Counter getZero() { return Counter(); }
-
-  /// \brief Return the counter that corresponds to a specific profile counter.
-  static Counter getCounter(unsigned CounterId) {
-    return Counter(CounterValueReference, CounterId);
-  }
-
-  /// \brief Return the counter that corresponds to a specific
-  /// addition counter expression.
-  static Counter getExpression(unsigned ExpressionId) {
-    return Counter(Expression, ExpressionId);
-  }
-};
-
-/// \brief A Counter expression is a value that represents an arithmetic
-/// operation with two counters.
-struct CounterExpression {
-  enum ExprKind { Subtract, Add };
-  ExprKind Kind;
-  Counter LHS, RHS;
-
-  CounterExpression(ExprKind Kind, Counter LHS, Counter RHS)
-      : Kind(Kind), LHS(LHS), RHS(RHS) {}
-};
-
-/// \brief A Counter expression builder is used to construct the
-/// counter expressions. It avoids unnecessary duplication
-/// and simplifies algebraic expressions.
-class CounterExpressionBuilder {
-  /// \brief A list of all the counter expressions
-  std::vector<CounterExpression> Expressions;
-  /// \brief A lookup table for the index of a given expression.
-  llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices;
-
-  /// \brief Return the counter which corresponds to the given expression.
-  ///
-  /// If the given expression is already stored in the builder, a counter
-  /// that references that expression is returned. Otherwise, the given
-  /// expression is added to the builder's collection of expressions.
-  Counter get(const CounterExpression &E);
-
-  /// \brief Gather the terms of the expression tree for processing.
-  ///
-  /// This collects each addition and subtraction referenced by the counter into
-  /// a sequence that can be sorted and combined to build a simplified counter
-  /// expression.
-  void extractTerms(Counter C, int Sign,
-                    SmallVectorImpl<std::pair<unsigned, int>> &Terms);
-
-  /// \brief Simplifies the given expression tree
-  /// by getting rid of algebraically redundant operations.
-  Counter simplify(Counter ExpressionTree);
-
-public:
-  ArrayRef<CounterExpression> getExpressions() const { return Expressions; }
-
-  /// \brief Return a counter that represents the expression
-  /// that adds LHS and RHS.
-  Counter add(Counter LHS, Counter RHS);
-
-  /// \brief Return a counter that represents the expression
-  /// that subtracts RHS from LHS.
-  Counter subtract(Counter LHS, Counter RHS);
-};
-
-/// \brief A Counter mapping region associates a source range with
-/// a specific counter.
-struct CounterMappingRegion {
-  enum RegionKind {
-    /// \brief A CodeRegion associates some code with a counter
-    CodeRegion,
-
-    /// \brief An ExpansionRegion represents a file expansion region that
-    /// associates a source range with the expansion of a virtual source file,
-    /// such as for a macro instantiation or #include file.
-    ExpansionRegion,
-
-    /// \brief A SkippedRegion represents a source range with code that
-    /// was skipped by a preprocessor or similar means.
-    SkippedRegion
-  };
-
-  Counter Count;
-  unsigned FileID, ExpandedFileID;
-  unsigned LineStart, ColumnStart, LineEnd, ColumnEnd;
-  RegionKind Kind;
-
-  CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID,
-                       unsigned LineStart, unsigned ColumnStart,
-                       unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind)
-      : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID),
-        LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd),
-        ColumnEnd(ColumnEnd), Kind(Kind) {}
-
-  static CounterMappingRegion
-  makeRegion(Counter Count, unsigned FileID, unsigned LineStart,
-             unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
-    return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart,
-                                LineEnd, ColumnEnd, CodeRegion);
-  }
-
-  static CounterMappingRegion
-  makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart,
-                unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) {
-    return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart,
-                                ColumnStart, LineEnd, ColumnEnd,
-                                ExpansionRegion);
-  }
-
-  static CounterMappingRegion
-  makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart,
-              unsigned LineEnd, unsigned ColumnEnd) {
-    return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart,
-                                LineEnd, ColumnEnd, SkippedRegion);
-  }
-
-
-  inline std::pair<unsigned, unsigned> startLoc() const {
-    return std::pair<unsigned, unsigned>(LineStart, ColumnStart);
-  }
-
-  inline std::pair<unsigned, unsigned> endLoc() const {
-    return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd);
-  }
-
-  bool operator<(const CounterMappingRegion &Other) const {
-    if (FileID != Other.FileID)
-      return FileID < Other.FileID;
-    return startLoc() < Other.startLoc();
-  }
-
-  bool contains(const CounterMappingRegion &Other) const {
-    if (FileID != Other.FileID)
-      return false;
-    if (startLoc() > Other.startLoc())
-      return false;
-    if (endLoc() < Other.endLoc())
-      return false;
-    return true;
-  }
-};
-
-/// \brief Associates a source range with an execution count.
-struct CountedRegion : public CounterMappingRegion {
-  uint64_t ExecutionCount;
-
-  CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount)
-      : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {}
-};
-
-/// \brief A Counter mapping context is used to connect the counters,
-/// expressions and the obtained counter values.
-class CounterMappingContext {
-  ArrayRef<CounterExpression> Expressions;
-  ArrayRef<uint64_t> CounterValues;
-
-public:
-  CounterMappingContext(ArrayRef<CounterExpression> Expressions,
-                        ArrayRef<uint64_t> CounterValues = None)
-      : Expressions(Expressions), CounterValues(CounterValues) {}
-
-  void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; }
-
-  void dump(const Counter &C, llvm::raw_ostream &OS) const;
-  void dump(const Counter &C) const { dump(C, dbgs()); }
-
-  /// \brief Return the number of times that a region of code associated with
-  /// this counter was executed.
-  ErrorOr<int64_t> evaluate(const Counter &C) const;
-};
-
-/// \brief Code coverage information for a single function.
-struct FunctionRecord {
-  /// \brief Raw function name.
-  std::string Name;
-  /// \brief Associated files.
-  std::vector<std::string> Filenames;
-  /// \brief Regions in the function along with their counts.
-  std::vector<CountedRegion> CountedRegions;
-  /// \brief The number of times this function was executed.
-  uint64_t ExecutionCount;
-
-  FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames)
-      : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {}
-
-  void pushRegion(CounterMappingRegion Region, uint64_t Count) {
-    if (CountedRegions.empty())
-      ExecutionCount = Count;
-    CountedRegions.emplace_back(Region, Count);
-  }
-};
-
-/// \brief Iterator over Functions, optionally filtered to a single file.
-class FunctionRecordIterator
-    : public iterator_facade_base<FunctionRecordIterator,
-                                  std::forward_iterator_tag, FunctionRecord> {
-  ArrayRef<FunctionRecord> Records;
-  ArrayRef<FunctionRecord>::iterator Current;
-  StringRef Filename;
-
-  /// \brief Skip records whose primary file is not \c Filename.
-  void skipOtherFiles();
-
-public:
-  FunctionRecordIterator(ArrayRef<FunctionRecord> Records_,
-                         StringRef Filename = "")
-      : Records(Records_), Current(Records.begin()), Filename(Filename) {
-    skipOtherFiles();
-  }
-
-  FunctionRecordIterator() : Current(Records.begin()) {}
-
-  bool operator==(const FunctionRecordIterator &RHS) const {
-    return Current == RHS.Current && Filename == RHS.Filename;
-  }
-
-  const FunctionRecord &operator*() const { return *Current; }
-
-  FunctionRecordIterator &operator++() {
-    assert(Current != Records.end() && "incremented past end");
-    ++Current;
-    skipOtherFiles();
-    return *this;
-  }
-};
-
-/// \brief Coverage information for a macro expansion or #included file.
-///
-/// When covered code has pieces that can be expanded for more detail, such as a
-/// preprocessor macro use and its definition, these are represented as
-/// expansions whose coverage can be looked up independently.
-struct ExpansionRecord {
-  /// \brief The abstract file this expansion covers.
-  unsigned FileID;
-  /// \brief The region that expands to this record.
-  const CountedRegion &Region;
-  /// \brief Coverage for the expansion.
-  const FunctionRecord &Function;
-
-  ExpansionRecord(const CountedRegion &Region,
-                  const FunctionRecord &Function)
-      : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {}
-};
-
-/// \brief The execution count information starting at a point in a file.
-///
-/// A sequence of CoverageSegments gives execution counts for a file in format
-/// that's simple to iterate through for processing.
-struct CoverageSegment {
-  /// \brief The line where this segment begins.
-  unsigned Line;
-  /// \brief The column where this segment begins.
-  unsigned Col;
-  /// \brief The execution count, or zero if no count was recorded.
-  uint64_t Count;
-  /// \brief When false, the segment was uninstrumented or skipped.
-  bool HasCount;
-  /// \brief Whether this enters a new region or returns to a previous count.
-  bool IsRegionEntry;
-
-  CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry)
-      : Line(Line), Col(Col), Count(0), HasCount(false),
-        IsRegionEntry(IsRegionEntry) {}
-
-  CoverageSegment(unsigned Line, unsigned Col, uint64_t Count,
-                  bool IsRegionEntry)
-      : Line(Line), Col(Col), Count(Count), HasCount(true),
-        IsRegionEntry(IsRegionEntry) {}
-
-  friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) {
-    return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) ==
-           std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry);
-  }
-};
-
-/// \brief Coverage information to be processed or displayed.
-///
-/// This represents the coverage of an entire file, expansion, or function. It
-/// provides a sequence of CoverageSegments to iterate through, as well as the
-/// list of expansions that can be further processed.
-class CoverageData {
-  std::string Filename;
-  std::vector<CoverageSegment> Segments;
-  std::vector<ExpansionRecord> Expansions;
-  friend class CoverageMapping;
-
-public:
-  CoverageData() {}
-
-  CoverageData(StringRef Filename) : Filename(Filename) {}
-
-  CoverageData(CoverageData &&RHS)
-      : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)),
-        Expansions(std::move(RHS.Expansions)) {}
-
-  /// \brief Get the name of the file this data covers.
-  StringRef getFilename() { return Filename; }
-
-  std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); }
-  std::vector<CoverageSegment>::iterator end() { return Segments.end(); }
-  bool empty() { return Segments.empty(); }
-
-  /// \brief Expansions that can be further processed.
-  std::vector<ExpansionRecord> getExpansions() { return Expansions; }
-};
-
-/// \brief The mapping of profile information to coverage data.
-///
-/// This is the main interface to get coverage information, using a profile to
-/// fill out execution counts.
-class CoverageMapping {
-  std::vector<FunctionRecord> Functions;
-  unsigned MismatchedFunctionCount;
-
-  CoverageMapping() : MismatchedFunctionCount(0) {}
-
-public:
-  /// \brief Load the coverage mapping using the given readers.
-  static ErrorOr<std::unique_ptr<CoverageMapping>>
-  load(CoverageMappingReader &CoverageReader,
-       IndexedInstrProfReader &ProfileReader);
-
-  /// \brief Load the coverage mapping from the given files.
-  static ErrorOr<std::unique_ptr<CoverageMapping>>
-  load(StringRef ObjectFilename, StringRef ProfileFilename,
-       StringRef Arch = StringRef());
-
-  /// \brief The number of functions that couldn't have their profiles mapped.
-  ///
-  /// This is a count of functions whose profile is out of date or otherwise
-  /// can't be associated with any coverage information.
-  unsigned getMismatchedCount() { return MismatchedFunctionCount; }
-
-  /// \brief Returns the list of files that are covered.
-  std::vector<StringRef> getUniqueSourceFiles() const;
-
-  /// \brief Get the coverage for a particular file.
-  ///
-  /// The given filename must be the name as recorded in the coverage
-  /// information. That is, only names returned from getUniqueSourceFiles will
-  /// yield a result.
-  CoverageData getCoverageForFile(StringRef Filename);
-
-  /// \brief Gets all of the functions covered by this profile.
-  iterator_range<FunctionRecordIterator> getCoveredFunctions() const {
-    return make_range(FunctionRecordIterator(Functions),
-                      FunctionRecordIterator());
-  }
-
-  /// \brief Gets all of the functions in a particular file.
-  iterator_range<FunctionRecordIterator>
-  getCoveredFunctions(StringRef Filename) const {
-    return make_range(FunctionRecordIterator(Functions, Filename),
-                      FunctionRecordIterator());
-  }
-
-  /// \brief Get the list of function instantiations in the file.
-  ///
-  /// Functions that are instantiated more than once, such as C++ template
-  /// specializations, have distinct coverage records for each instantiation.
-  std::vector<const FunctionRecord *> getInstantiations(StringRef Filename);
-
-  /// \brief Get the coverage for a particular function.
-  CoverageData getCoverageForFunction(const FunctionRecord &Function);
-
-  /// \brief Get the coverage for an expansion within a coverage set.
-  CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion);
-};
-
-const std::error_category &coveragemap_category();
-
-inline std::error_code make_error_code(coveragemap_error E) {
-  return std::error_code(static_cast<int>(E), coveragemap_category());
-}
-
-// Profile coverage map has the following layout:
-// [CoverageMapFileHeader]
-// [ArrayStart]
-//  [CovMapFunctionRecord]
-//  [CovMapFunctionRecord]
-//  ...
-// [ArrayEnd]
-// [Encoded Region Mapping Data]
-LLVM_PACKED_START
-template <class IntPtrT> struct CovMapFunctionRecordV1 {
-#define COVMAP_V1
-#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
-#include "llvm/ProfileData/InstrProfData.inc"
-#undef COVMAP_V1
-
-  // Return the structural hash associated with the function.
-  template <support::endianness Endian> uint64_t getFuncHash() const {
-    return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
-  }
-  // Return the coverage map data size for the funciton.
-  template <support::endianness Endian> uint32_t getDataSize() const {
-    return support::endian::byte_swap<uint32_t, Endian>(DataSize);
-  }
-  // Return function lookup key. The value is consider opaque.
-  template <support::endianness Endian> IntPtrT getFuncNameRef() const {
-    return support::endian::byte_swap<IntPtrT, Endian>(NamePtr);
-  }
-  // Return the PGO name of the function */
-  template <support::endianness Endian>
-  std::error_code getFuncName(InstrProfSymtab &ProfileNames,
-                              StringRef &FuncName) const {
-    IntPtrT NameRef = getFuncNameRef<Endian>();
-    uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize);
-    FuncName = ProfileNames.getFuncName(NameRef, NameS);
-    if (NameS && FuncName.empty())
-      return coveragemap_error::malformed;
-    return std::error_code();
-  }
-};
-
-struct CovMapFunctionRecord {
-#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
-#include "llvm/ProfileData/InstrProfData.inc"
-
-  // Return the structural hash associated with the function.
-  template <support::endianness Endian> uint64_t getFuncHash() const {
-    return support::endian::byte_swap<uint64_t, Endian>(FuncHash);
-  }
-  // Return the coverage map data size for the funciton.
-  template <support::endianness Endian> uint32_t getDataSize() const {
-    return support::endian::byte_swap<uint32_t, Endian>(DataSize);
-  }
-  // Return function lookup key. The value is consider opaque.
-  template <support::endianness Endian> uint64_t getFuncNameRef() const {
-    return support::endian::byte_swap<uint64_t, Endian>(NameRef);
-  }
-  // Return the PGO name of the function */
-  template <support::endianness Endian>
-  std::error_code getFuncName(InstrProfSymtab &ProfileNames,
-                              StringRef &FuncName) const {
-    uint64_t NameRef = getFuncNameRef<Endian>();
-    FuncName = ProfileNames.getFuncName(NameRef);
-    return std::error_code();
-  }
-};
-
-// Per module coverage mapping data header, i.e. CoverageMapFileHeader
-// documented above.
-struct CovMapHeader {
-#define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name;
-#include "llvm/ProfileData/InstrProfData.inc"
-  template <support::endianness Endian> uint32_t getNRecords() const {
-    return support::endian::byte_swap<uint32_t, Endian>(NRecords);
-  }
-  template <support::endianness Endian> uint32_t getFilenamesSize() const {
-    return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize);
-  }
-  template <support::endianness Endian> uint32_t getCoverageSize() const {
-    return support::endian::byte_swap<uint32_t, Endian>(CoverageSize);
-  }
-  template <support::endianness Endian> uint32_t getVersion() const {
-    return support::endian::byte_swap<uint32_t, Endian>(Version);
-  }
-};
-
-LLVM_PACKED_END
-
-enum CovMapVersion {
-  Version1 = 0,
-  // Function's name reference from CovMapFuncRecord is changed from raw
-  // name string pointer to MD5 to support name section compression. Name
-  // section is also compressed.
-  Version2 = 1,
-  // The current version is Version2
-  CurrentVersion = INSTR_PROF_COVMAP_VERSION
-};
-
-template <int CovMapVersion, class IntPtrT> struct CovMapTraits {
-  typedef CovMapFunctionRecord CovMapFuncRecordType;
-  typedef uint64_t NameRefType;
-};
-
-template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> {
-  typedef CovMapFunctionRecordV1<IntPtrT> CovMapFuncRecordType;
-  typedef IntPtrT NameRefType;
-};
-
-} // end namespace coverage
-
-/// \brief Provide DenseMapInfo for CounterExpression
-template<> struct DenseMapInfo<coverage::CounterExpression> {
-  static inline coverage::CounterExpression getEmptyKey() {
-    using namespace coverage;
-    return CounterExpression(CounterExpression::ExprKind::Subtract,
-                             Counter::getCounter(~0U),
-                             Counter::getCounter(~0U));
-  }
-
-  static inline coverage::CounterExpression getTombstoneKey() {
-    using namespace coverage;
-    return CounterExpression(CounterExpression::ExprKind::Add,
-                             Counter::getCounter(~0U),
-                             Counter::getCounter(~0U));
-  }
-
-  static unsigned getHashValue(const coverage::CounterExpression &V) {
-    return static_cast<unsigned>(
-        hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(),
-                     V.RHS.getKind(), V.RHS.getCounterID()));
-  }
-
-  static bool isEqual(const coverage::CounterExpression &LHS,
-                      const coverage::CounterExpression &RHS) {
-    return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS;
-  }
-};
-
-} // end namespace llvm
-
-#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_

llvm/trunk/include/llvm/ProfileData/CoverageMappingReader.h

-//=-- CoverageMappingReader.h - Code coverage mapping reader ------*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains support for reading coverage mapping data for
-// instrumentation based coverage.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_PROFILEDATA_COVERAGEMAPPINGREADER_H
-#define LLVM_PROFILEDATA_COVERAGEMAPPINGREADER_H
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/ADT/Triple.h"
-#include "llvm/Object/ObjectFile.h"
-#include "llvm/ProfileData/CoverageMapping.h"
-#include "llvm/ProfileData/InstrProf.h"
-#include "llvm/Support/FileSystem.h"
-#include "llvm/Support/MemoryBuffer.h"
-#include <iterator>
-
-namespace llvm {
-namespace coverage {
-
-class CoverageMappingReader;
-
-/// \brief Coverage mapping information for a single function.
-struct CoverageMappingRecord {
-  StringRef FunctionName;
-  uint64_t FunctionHash;
-  ArrayRef<StringRef> Filenames;
-  ArrayRef<CounterExpression> Expressions;
-  ArrayRef<CounterMappingRegion> MappingRegions;
-};
-
-/// \brief A file format agnostic iterator over coverage mapping data.
-class CoverageMappingIterator
-    : public std::iterator<std::input_iterator_tag, CoverageMappingRecord> {
-  CoverageMappingReader *Reader;
-  CoverageMappingRecord Record;
-
-  void increment();
-
-public:
-  CoverageMappingIterator() : Reader(nullptr) {}
-  CoverageMappingIterator(CoverageMappingReader *Reader) : Reader(Reader) {
-    increment();
-  }
-
-  CoverageMappingIterator &operator++() {
-    increment();
-    return *this;
-  }
-  bool operator==(const CoverageMappingIterator &RHS) {
-    return Reader == RHS.Reader;
-  }
-  bool operator!=(const CoverageMappingIterator &RHS) {
-    return Reader != RHS.Reader;
-  }
-  CoverageMappingRecord &operator*() { return Record; }
-  CoverageMappingRecord *operator->() { return &Record; }
-};
-
-class CoverageMappingReader {
-public:
-  virtual std::error_code readNextRecord(CoverageMappingRecord &Record) = 0;
-  CoverageMappingIterator begin() { return CoverageMappingIterator(this); }
-  CoverageMappingIterator end() { return CoverageMappingIterator(); }
-  virtual ~CoverageMappingReader() {}
-};
-
-/// \brief Base class for the raw coverage mapping and filenames data readers.
-class RawCoverageReader {
-protected:
-  StringRef Data;
-
-  RawCoverageReader(StringRef Data) : Data(Data) {}
-
-  std::error_code readULEB128(uint64_t &Result);
-  std::error_code readIntMax(uint64_t &Result, uint64_t MaxPlus1);
-  std::error_code readSize(uint64_t &Result);
-  std::error_code readString(StringRef &Result);
-};
-
-/// \brief Reader for the raw coverage filenames.
-class RawCoverageFilenamesReader : public RawCoverageReader {
-  std::vector<StringRef> &Filenames;
-
-  RawCoverageFilenamesReader(const RawCoverageFilenamesReader &) = delete;
-  RawCoverageFilenamesReader &
-  operator=(const RawCoverageFilenamesReader &) = delete;
-
-public:
-  RawCoverageFilenamesReader(StringRef Data, std::vector<StringRef> &Filenames)
-      : RawCoverageReader(Data), Filenames(Filenames) {}
-
-  std::error_code read();
-};
-
-/// \brief Reader for the raw coverage mapping data.
-class RawCoverageMappingReader : public RawCoverageReader {
-  ArrayRef<StringRef> TranslationUnitFilenames;
-  std::vector<StringRef> &Filenames;
-  std::vector<CounterExpression> &Expressions;
-  std::vector<CounterMappingRegion> &MappingRegions;
-
-  RawCoverageMappingReader(const RawCoverageMappingReader &) = delete;
-  RawCoverageMappingReader &
-  operator=(const RawCoverageMappingReader &) = delete;
-
-public:
-  RawCoverageMappingReader(StringRef MappingData,
-                           ArrayRef<StringRef> TranslationUnitFilenames,
-                           std::vector<StringRef> &Filenames,
-                           std::vector<CounterExpression> &Expressions,
-                           std::vector<CounterMappingRegion> &MappingRegions)
-      : RawCoverageReader(MappingData),
-        TranslationUnitFilenames(TranslationUnitFilenames),
-        Filenames(Filenames), Expressions(Expressions),
-        MappingRegions(MappingRegions) {}
-
-  std::error_code read();
-
-private:
-  std::error_code decodeCounter(unsigned Value, Counter &C);
-  std::error_code readCounter(Counter &C);
-  std::error_code
-  readMappingRegionsSubArray(std::vector<CounterMappingRegion> &MappingRegions,
-                             unsigned InferredFileID, size_t NumFileIDs);
-};
-
-/// \brief Reader for the coverage mapping data that is emitted by the
-/// frontend and stored in an object file.
-class BinaryCoverageReader : public CoverageMappingReader {
-public:
-  struct ProfileMappingRecord {
-    CovMapVersion Version;
-    StringRef FunctionName;
-    uint64_t FunctionHash;
-    StringRef CoverageMapping;
-    size_t FilenamesBegin;
-    size_t FilenamesSize;
-
-    ProfileMappingRecord(CovMapVersion Version, StringRef FunctionName,
-                         uint64_t FunctionHash, StringRef CoverageMapping,
-                         size_t FilenamesBegin, size_t FilenamesSize)
-        : Version(Version), FunctionName(FunctionName),
-          FunctionHash(FunctionHash), CoverageMapping(CoverageMapping),
-          FilenamesBegin(FilenamesBegin), FilenamesSize(FilenamesSize) {}
-  };
-
-private:
-  std::vector<StringRef> Filenames;
-  std::vector<ProfileMappingRecord> MappingRecords;
-  InstrProfSymtab ProfileNames;
-  size_t CurrentRecord;
-  std::vector<StringRef> FunctionsFilenames;
-  std::vector<CounterExpression> Expressions;
-  std::vector<CounterMappingRegion> MappingRegions;
-
-  BinaryCoverageReader(const BinaryCoverageReader &) = delete;
-  BinaryCoverageReader &operator=(const BinaryCoverageReader &) = delete;
-
-  BinaryCoverageReader() : CurrentRecord(0) {}
-
-public:
-  static ErrorOr<std::unique_ptr<BinaryCoverageReader>>
-  create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
-         StringRef Arch);
-
-  std::error_code readNextRecord(CoverageMappingRecord &Record) override;
-};
-
-} // end namespace coverage
-} // end namespace llvm
-
-#endif

llvm/trunk/include/llvm/ProfileData/CoverageMappingWriter.h

-//=-- CoverageMappingWriter.h - Code coverage mapping writer ------*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains support for writing coverage mapping data for
-// instrumentation based coverage.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_PROFILEDATA_COVERAGEMAPPINGWRITER_H
-#define LLVM_PROFILEDATA_COVERAGEMAPPINGWRITER_H
-
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/StringMap.h"
-#include "llvm/ProfileData/CoverageMapping.h"
-#include "llvm/Support/raw_ostream.h"
-
-namespace llvm {
-namespace coverage {
-
-/// \brief Writer of the filenames section for the instrumentation
-/// based code coverage.
-class CoverageFilenamesSectionWriter {
-  ArrayRef<StringRef> Filenames;
-
-public:
-  CoverageFilenamesSectionWriter(ArrayRef<StringRef> Filenames)
-      : Filenames(Filenames) {}
-
-  /// \brief Write encoded filenames to the given output stream.
-  void write(raw_ostream &OS);
-};
-
-/// \brief Writer for instrumentation based coverage mapping data.
-class CoverageMappingWriter {
-  ArrayRef<unsigned> VirtualFileMapping;
-  ArrayRef<CounterExpression> Expressions;
-  MutableArrayRef<CounterMappingRegion> MappingRegions;
-
-public:
-  CoverageMappingWriter(ArrayRef<unsigned> VirtualFileMapping,
-                        ArrayRef<CounterExpression> Expressions,
-                        MutableArrayRef<CounterMappingRegion> MappingRegions)
-      : VirtualFileMapping(VirtualFileMapping), Expressions(Expressions),
-        MappingRegions(MappingRegions) {}
-
-  CoverageMappingWriter(ArrayRef<CounterExpression> Expressions,
-                        MutableArrayRef<CounterMappingRegion> MappingRegions)
-      : Expressions(Expressions), MappingRegions(MappingRegions) {}
-
-  /// \brief Write encoded coverage mapping data to the given output stream.
-  void write(raw_ostream &OS);
-};
-
-} // end namespace coverage
-} // end namespace llvm
-
-#endif

llvm/trunk/lib/ProfileData/CMakeLists.txt

 add_llvm_library(LLVMProfileData
   InstrProf.cpp
   InstrProfReader.cpp
   InstrProfWriter.cpp
-  CoverageMapping.cpp
-  CoverageMappingWriter.cpp
-  CoverageMappingReader.cpp
   ProfileSummary.cpp
   SampleProf.cpp
   SampleProfReader.cpp
   SampleProfWriter.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/ProfileData
 
   DEPENDS
   intrinsics_gen
   )
+
+add_subdirectory(Coverage)

llvm/trunk/lib/ProfileData/Coverage/CMakeLists.txt

+add_llvm_library(LLVMCoverage
+  CoverageMapping.cpp
+  CoverageMappingWriter.cpp
+  CoverageMappingReader.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/ProfileData/Coverage
+
+  DEPENDS
+  intrinsics_gen
+  )

llvm/trunk/lib/ProfileData/Coverage/CoverageMapping.cpp

+//=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for clang's and llvm's instrumentation based
+// code coverage.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallBitVector.h"
+#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
+#include "llvm/ProfileData/InstrProfReader.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Errc.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/ManagedStatic.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace coverage;
+
+#define DEBUG_TYPE "coverage-mapping"
+
+Counter CounterExpressionBuilder::get(const CounterExpression &E) {
+  auto It = ExpressionIndices.find(E);
+  if (It != ExpressionIndices.end())
+    return Counter::getExpression(It->second);
+  unsigned I = Expressions.size();
+  Expressions.push_back(E);
+  ExpressionIndices[E] = I;
+  return Counter::getExpression(I);
+}
+
+void CounterExpressionBuilder::extractTerms(
+    Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
+  switch (C.getKind()) {
+  case Counter::Zero:
+    break;
+  case Counter::CounterValueReference:
+    Terms.push_back(std::make_pair(C.getCounterID(), Sign));
+    break;
+  case Counter::Expression:
+    const auto &E = Expressions[C.getExpressionID()];
+    extractTerms(E.LHS, Sign, Terms);
+    extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
+                 Terms);
+    break;
+  }
+}
+
+Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
+  // Gather constant terms.
+  llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
+  extractTerms(ExpressionTree, +1, Terms);
+
+  // If there are no terms, this is just a zero. The algorithm below assumes at
+  // least one term.
+  if (Terms.size() == 0)
+    return Counter::getZero();
+
+  // Group the terms by counter ID.
+  std::sort(Terms.begin(), Terms.end(),
+            [](const std::pair<unsigned, int> &LHS,
+               const std::pair<unsigned, int> &RHS) {
+    return LHS.first < RHS.first;
+  });
+
+  // Combine terms by counter ID to eliminate counters that sum to zero.
+  auto Prev = Terms.begin();
+  for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
+    if (I->first == Prev->first) {
+      Prev->second += I->second;
+      continue;
+    }
+    ++Prev;
+    *Prev = *I;
+  }
+  Terms.erase(++Prev, Terms.end());
+
+  Counter C;
+  // Create additions. We do this before subtractions to avoid constructs like
+  // ((0 - X) + Y), as opposed to (Y - X).
+  for (auto Term : Terms) {
+    if (Term.second <= 0)
+      continue;
+    for (int I = 0; I < Term.second; ++I)
+      if (C.isZero())
+        C = Counter::getCounter(Term.first);
+      else
+        C = get(CounterExpression(CounterExpression::Add, C,
+                                  Counter::getCounter(Term.first)));
+  }
+
+  // Create subtractions.
+  for (auto Term : Terms) {
+    if (Term.second >= 0)
+      continue;
+    for (int I = 0; I < -Term.second; ++I)
+      C = get(CounterExpression(CounterExpression::Subtract, C,
+                                Counter::getCounter(Term.first)));
+  }
+  return C;
+}
+
+Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
+  return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
+}
+
+Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
+  return simplify(
+      get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
+}
+
+void CounterMappingContext::dump(const Counter &C,
+                                 llvm::raw_ostream &OS) const {
+  switch (C.getKind()) {
+  case Counter::Zero:
+    OS << '0';
+    return;
+  case Counter::CounterValueReference:
+    OS << '#' << C.getCounterID();
+    break;
+  case Counter::Expression: {
+    if (C.getExpressionID() >= Expressions.size())
+      return;
+    const auto &E = Expressions[C.getExpressionID()];
+    OS << '(';
+    dump(E.LHS, OS);
+    OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
+    dump(E.RHS, OS);
+    OS << ')';
+    break;
+  }
+  }
+  if (CounterValues.empty())
+    return;
+  ErrorOr<int64_t> Value = evaluate(C);
+  if (!Value)
+    return;
+  OS << '[' << *Value << ']';
+}
+
+ErrorOr<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
+  switch (C.getKind()) {
+  case Counter::Zero:
+    return 0;
+  case Counter::CounterValueReference:
+    if (C.getCounterID() >= CounterValues.size())
+      return make_error_code(errc::argument_out_of_domain);
+    return CounterValues[C.getCounterID()];
+  case Counter::Expression: {
+    if (C.getExpressionID() >= Expressions.size())
+      return make_error_code(errc::argument_out_of_domain);
+    const auto &E = Expressions[C.getExpressionID()];
+    ErrorOr<int64_t> LHS = evaluate(E.LHS);
+    if (!LHS)
+      return LHS;
+    ErrorOr<int64_t> RHS = evaluate(E.RHS);
+    if (!RHS)
+      return RHS;
+    return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
+  }
+  }
+  llvm_unreachable("Unhandled CounterKind");
+}
+
+void FunctionRecordIterator::skipOtherFiles() {
+  while (Current != Records.end() && !Filename.empty() &&
+         Filename != Current->Filenames[0])
+    ++Current;
+  if (Current == Records.end())
+    *this = FunctionRecordIterator();
+}
+
+ErrorOr<std::unique_ptr<CoverageMapping>>
+CoverageMapping::load(CoverageMappingReader &CoverageReader,
+                      IndexedInstrProfReader &ProfileReader) {
+  auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
+
+  std::vector<uint64_t> Counts;
+  for (const auto &Record : CoverageReader) {
+    CounterMappingContext Ctx(Record.Expressions);
+
+    Counts.clear();
+    if (std::error_code EC = ProfileReader.getFunctionCounts(
+            Record.FunctionName, Record.FunctionHash, Counts)) {
+      if (EC == instrprof_error::hash_mismatch) {
+        Coverage->MismatchedFunctionCount++;
+        continue;
+      } else if (EC != instrprof_error::unknown_function)
+        return EC;
+      Counts.assign(Record.MappingRegions.size(), 0);
+    }
+    Ctx.setCounts(Counts);
+
+    assert(!Record.MappingRegions.empty() && "Function has no regions");
+
+    StringRef OrigFuncName = Record.FunctionName;
+    if (Record.Filenames.empty())
+      OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
+    else
+      OrigFuncName =
+          getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
+    FunctionRecord Function(OrigFuncName, Record.Filenames);
+    for (const auto &Region : Record.MappingRegions) {
+      ErrorOr<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
+      if (!ExecutionCount)
+        break;
+      Function.pushRegion(Region, *ExecutionCount);
+    }
+    if (Function.CountedRegions.size() != Record.MappingRegions.size()) {
+      Coverage->MismatchedFunctionCount++;
+      continue;
+    }
+
+    Coverage->Functions.push_back(std::move(Function));
+  }
+
+  return std::move(Coverage);
+}
+
+ErrorOr<std::unique_ptr<CoverageMapping>>
+CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename,
+                      StringRef Arch) {
+  auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename);
+  if (std::error_code EC = CounterMappingBuff.getError())
+    return EC;
+  auto CoverageReaderOrErr =
+      BinaryCoverageReader::create(CounterMappingBuff.get(), Arch);
+  if (std::error_code EC = CoverageReaderOrErr.getError())
+    return EC;
+  auto CoverageReader = std::move(CoverageReaderOrErr.get());
+  auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
+  if (auto EC = ProfileReaderOrErr.getError())
+    return EC;
+  auto ProfileReader = std::move(ProfileReaderOrErr.get());
+  return load(*CoverageReader, *ProfileReader);
+}
+
+namespace {
+/// \brief Distributes functions into instantiation sets.
+///
+/// An instantiation set is a collection of functions that have the same source
+/// code, ie, template functions specializations.
+class FunctionInstantiationSetCollector {
+  typedef DenseMap<std::pair<unsigned, unsigned>,
+                   std::vector<const FunctionRecord *>> MapT;
+  MapT InstantiatedFunctions;
+
+public:
+  void insert(const FunctionRecord &Function, unsigned FileID) {
+    auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
+    while (I != E && I->FileID != FileID)
+      ++I;
+    assert(I != E && "function does not cover the given file");
+    auto &Functions = InstantiatedFunctions[I->startLoc()];
+    Functions.push_back(&Function);
+  }
+
+  MapT::iterator begin() { return InstantiatedFunctions.begin(); }
+
+  MapT::iterator end() { return InstantiatedFunctions.end(); }
+};
+
+class SegmentBuilder {
+  std::vector<CoverageSegment> &Segments;
+  SmallVector<const CountedRegion *, 8> ActiveRegions;
+
+  SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
+
+  /// Start a segment with no count specified.
+  void startSegment(unsigned Line, unsigned Col) {
+    DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
+    Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
+  }
+
+  /// Start a segment with the given Region's count.
+  void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
+                    const CountedRegion &Region) {
+    // Avoid creating empty regions.
+    if (!Segments.empty() && Segments.back().Line == Line &&
+        Segments.back().Col == Col)
+      Segments.pop_back();
+    DEBUG(dbgs() << "Segment at " << Line << ":" << Col);
+    // Set this region's count.
+    if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) {
+      DEBUG(dbgs() << " with count " << Region.ExecutionCount);
+      Segments.emplace_back(Line, Col, Region.ExecutionCount, IsRegionEntry);
+    } else
+      Segments.emplace_back(Line, Col, IsRegionEntry);
+    DEBUG(dbgs() << "\n");
+  }
+
+  /// Start a segment for the given region.
+  void startSegment(const CountedRegion &Region) {
+    startSegment(Region.LineStart, Region.ColumnStart, true, Region);
+  }
+
+  /// Pop the top region off of the active stack, starting a new segment with
+  /// the containing Region's count.
+  void popRegion() {
+    const CountedRegion *Active = ActiveRegions.back();
+    unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
+    ActiveRegions.pop_back();
+    if (ActiveRegions.empty())
+      startSegment(Line, Col);
+    else
+      startSegment(Line, Col, false, *ActiveRegions.back());
+  }
+
+  void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
+    for (const auto &Region : Regions) {
+      // Pop any regions that end before this one starts.
+      while (!ActiveRegions.empty() &&
+             ActiveRegions.back()->endLoc() <= Region.startLoc())
+        popRegion();
+      // Add this region to the stack.
+      ActiveRegions.push_back(&Region);
+      startSegment(Region);
+    }
+    // Pop any regions that are left in the stack.
+    while (!ActiveRegions.empty())
+      popRegion();
+  }
+
+  /// Sort a nested sequence of regions from a single file.
+  static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
+    std::sort(Regions.begin(), Regions.end(),
+              [](const CountedRegion &LHS, const CountedRegion &RHS) {
+                if (LHS.startLoc() == RHS.startLoc())
+                  // When LHS completely contains RHS, we sort LHS first.
+                  return RHS.endLoc() < LHS.endLoc();
+                return LHS.startLoc() < RHS.startLoc();
+              });
+  }
+
+  /// Combine counts of regions which cover the same area.
+  static ArrayRef<CountedRegion>
+  combineRegions(MutableArrayRef<CountedRegion> Regions) {
+    if (Regions.empty())
+      return Regions;
+    auto Active = Regions.begin();
+    auto End = Regions.end();
+    for (auto I = Regions.begin() + 1; I != End; ++I) {
+      if (Active->startLoc() != I->startLoc() ||
+          Active->endLoc() != I->endLoc()) {
+        // Shift to the next region.
+        ++Active;
+        if (Active != I)
+          *Active = *I;
+        continue;
+      }
+      // Merge duplicate region.
+      if (I->Kind != coverage::CounterMappingRegion::CodeRegion)
+        // Add counts only from CodeRegions.
+        continue;
+      if (Active->Kind == coverage::CounterMappingRegion::SkippedRegion)
+        // We have to overwrite SkippedRegions because of special handling
+        // of them in startSegment().
+        *Active = *I;
+      else
+        // Otherwise, just append the count.
+        Active->ExecutionCount += I->ExecutionCount;
+    }
+    return Regions.drop_back(std::distance(++Active, End));
+  }
+
+public:
+  /// Build a list of CoverageSegments from a list of Regions.
+  static std::vector<CoverageSegment>
+  buildSegments(MutableArrayRef<CountedRegion> Regions) {
+    std::vector<CoverageSegment> Segments;
+    SegmentBuilder Builder(Segments);
+
+    sortNestedRegions(Regions);
+    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
+
+    Builder.buildSegmentsImpl(CombinedRegions);
+    return Segments;
+  }
+};
+}
+
+std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
+  std::vector<StringRef> Filenames;
+  for (const auto &Function : getCoveredFunctions())
+    Filenames.insert(Filenames.end(), Function.Filenames.begin(),
+                     Function.Filenames.end());
+  std::sort(Filenames.begin(), Filenames.end());
+  auto Last = std::unique(Filenames.begin(), Filenames.end());
+  Filenames.erase(Last, Filenames.end());
+  return Filenames;
+}
+
+static SmallBitVector gatherFileIDs(StringRef SourceFile,
+                                    const FunctionRecord &Function) {
+  SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
+  for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
+    if (SourceFile == Function.Filenames[I])
+      FilenameEquivalence[I] = true;
+  return FilenameEquivalence;
+}
+
+/// Return the ID of the file where the definition of the function is located.
+static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
+  SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
+  for (const auto &CR : Function.CountedRegions)
+    if (CR.Kind == CounterMappingRegion::ExpansionRegion)
+      IsNotExpandedFile[CR.ExpandedFileID] = false;
+  int I = IsNotExpandedFile.find_first();
+  if (I == -1)
+    return None;
+  return I;
+}
+
+/// Check if SourceFile is the file that contains the definition of
+/// the Function. Return the ID of the file in that case or None otherwise.
+static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
+                                             const FunctionRecord &Function) {
+  Optional<unsigned> I = findMainViewFileID(Function);
+  if (I && SourceFile == Function.Filenames[*I])
+    return I;
+  return None;
+}
+
+static bool isExpansion(const CountedRegion &R, unsigned FileID) {
+  return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
+}
+
+CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) {
+  CoverageData FileCoverage(Filename);
+  std::vector<coverage::CountedRegion> Regions;
+
+  for (const auto &Function : Functions) {
+    auto MainFileID = findMainViewFileID(Filename, Function);
+    auto FileIDs = gatherFileIDs(Filename, Function);
+    for (const auto &CR : Function.CountedRegions)
+      if (FileIDs.test(CR.FileID)) {
+        Regions.push_back(CR);
+        if (MainFileID && isExpansion(CR, *MainFileID))
+          FileCoverage.Expansions.emplace_back(CR, Function);
+      }
+  }
+
+  DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
+  FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
+
+  return FileCoverage;
+}
+
+std::vector<const FunctionRecord *>
+CoverageMapping::getInstantiations(StringRef Filename) {
+  FunctionInstantiationSetCollector InstantiationSetCollector;
+  for (const auto &Function : Functions) {
+    auto MainFileID = findMainViewFileID(Filename, Function);
+    if (!MainFileID)
+      continue;
+    InstantiationSetCollector.insert(Function, *MainFileID);
+  }
+
+  std::vector<const FunctionRecord *> Result;
+  for (const auto &InstantiationSet : InstantiationSetCollector) {
+    if (InstantiationSet.second.size() < 2)
+      continue;
+    Result.insert(Result.end(), InstantiationSet.second.begin(),
+                  InstantiationSet.second.end());
+  }
+  return Result;
+}
+
+CoverageData
+CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
+  auto MainFileID = findMainViewFileID(Function);
+  if (!MainFileID)
+    return CoverageData();
+
+  CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
+  std::vector<coverage::CountedRegion> Regions;
+  for (const auto &CR : Function.CountedRegions)
+    if (CR.FileID == *MainFileID) {
+      Regions.push_back(CR);
+      if (isExpansion(CR, *MainFileID))
+        FunctionCoverage.Expansions.emplace_back(CR, Function);
+    }
+
+  DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
+  FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
+
+  return FunctionCoverage;
+}
+
+CoverageData
+CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) {
+  CoverageData ExpansionCoverage(
+      Expansion.Function.Filenames[Expansion.FileID]);
+  std::vector<coverage::CountedRegion> Regions;
+  for (const auto &CR : Expansion.Function.CountedRegions)
+    if (CR.FileID == Expansion.FileID) {
+      Regions.push_back(CR);
+      if (isExpansion(CR, Expansion.FileID))
+        ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
+    }
+
+  DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
+               << "\n");
+  ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
+
+  return ExpansionCoverage;
+}
+
+namespace {
+class CoverageMappingErrorCategoryType : public std::error_category {
+  const char *name() const LLVM_NOEXCEPT override { return "llvm.coveragemap"; }
+  std::string message(int IE) const override {
+    auto E = static_cast<coveragemap_error>(IE);
+    switch (E) {
+    case coveragemap_error::success:
+      return "Success";
+    case coveragemap_error::eof:
+      return "End of File";
+    case coveragemap_error::no_data_found:
+      return "No coverage data found";
+    case coveragemap_error::unsupported_version:
+      return "Unsupported coverage format version";
+    case coveragemap_error::truncated:
+      return "Truncated coverage data";
+    case coveragemap_error::malformed:
+      return "Malformed coverage data";
+    }
+    llvm_unreachable("A value of coveragemap_error has no message.");
+  }
+};
+}
+
+static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;
+
+const std::error_category &llvm::coverage::coveragemap_category() {
+  return *ErrorCategory;
+}

llvm/trunk/lib/ProfileData/Coverage/CoverageMappingReader.cpp

+//=-- CoverageMappingReader.cpp - Code coverage mapping reader ----*- C++ -*-=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for reading coverage mapping data for
+// instrumentation based coverage.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/Object/MachOUniversal.h"
+#include "llvm/Object/ObjectFile.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Endian.h"
+#include "llvm/Support/LEB128.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+using namespace coverage;
+using namespace object;
+
+#define DEBUG_TYPE "coverage-mapping"
+
+void CoverageMappingIterator::increment() {
+  // Check if all the records were read or if an error occurred while reading
+  // the next record.
+  if (Reader->readNextRecord(Record))
+    *this = CoverageMappingIterator();
+}
+
+std::error_code RawCoverageReader::readULEB128(uint64_t &Result) {
+  if (Data.size() < 1)
+    return coveragemap_error::truncated;
+  unsigned N = 0;
+  Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
+  if (N > Data.size())
+    return coveragemap_error::malformed;
+  Data = Data.substr(N);
+  return std::error_code();
+}
+
+std::error_code RawCoverageReader::readIntMax(uint64_t &Result,
+                                              uint64_t MaxPlus1) {
+  if (auto Err = readULEB128(Result))
+    return Err;
+  if (Result >= MaxPlus1)
+    return coveragemap_error::malformed;
+  return std::error_code();
+}
+
+std::error_code RawCoverageReader::readSize(uint64_t &Result) {
+  if (auto Err = readULEB128(Result))
+    return Err;
+  // Sanity check the number.
+  if (Result > Data.size())
+    return coveragemap_error::malformed;
+  return std::error_code();
+}
+
+std::error_code RawCoverageReader::readString(StringRef &Result) {
+  uint64_t Length;
+  if (auto Err = readSize(Length))
+    return Err;
+  Result = Data.substr(0, Length);
+  Data = Data.substr(Length);
+  return std::error_code();
+}
+
+std::error_code RawCoverageFilenamesReader::read() {
+  uint64_t NumFilenames;
+  if (auto Err = readSize(NumFilenames))
+    return Err;
+  for (size_t I = 0; I < NumFilenames; ++I) {
+    StringRef Filename;
+    if (auto Err = readString(Filename))
+      return Err;
+    Filenames.push_back(Filename);
+  }
+  return std::error_code();
+}
+
+std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value,
+                                                        Counter &C) {
+  auto Tag = Value & Counter::EncodingTagMask;
+  switch (Tag) {
+  case Counter::Zero:
+    C = Counter::getZero();
+    return std::error_code();
+  case Counter::CounterValueReference:
+    C = Counter::getCounter(Value >> Counter::EncodingTagBits);
+    return std::error_code();
+  default:
+    break;
+  }
+  Tag -= Counter::Expression;
+  switch (Tag) {
+  case CounterExpression::Subtract:
+  case CounterExpression::Add: {
+    auto ID = Value >> Counter::EncodingTagBits;
+    if (ID >= Expressions.size())
+      return coveragemap_error::malformed;
+    Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
+    C = Counter::getExpression(ID);
+    break;
+  }
+  default:
+    return coveragemap_error::malformed;
+  }
+  return std::error_code();
+}
+
+std::error_code RawCoverageMappingReader::readCounter(Counter &C) {
+  uint64_t EncodedCounter;
+  if (auto Err =
+          readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
+    return Err;
+  if (auto Err = decodeCounter(EncodedCounter, C))
+    return Err;
+  return std::error_code();
+}
+
+static const unsigned EncodingExpansionRegionBit = 1
+                                                   << Counter::EncodingTagBits;
+
+/// \brief Read the sub-array of regions for the given inferred file id.
+/// \param NumFileIDs the number of file ids that are defined for this
+/// function.
+std::error_code RawCoverageMappingReader::readMappingRegionsSubArray(
+    std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
+    size_t NumFileIDs) {
+  uint64_t NumRegions;
+  if (auto Err = readSize(NumRegions))
+    return Err;
+  unsigned LineStart = 0;
+  for (size_t I = 0; I < NumRegions; ++I) {
+    Counter C;
+    CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
+
+    // Read the combined counter + region kind.
+    uint64_t EncodedCounterAndRegion;
+    if (auto Err = readIntMax(EncodedCounterAndRegion,
+                              std::numeric_limits<unsigned>::max()))
+      return Err;
+    unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
+    uint64_t ExpandedFileID = 0;
+    if (Tag != Counter::Zero) {
+      if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
+        return Err;
+    } else {
+      // Is it an expansion region?
+      if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
+        Kind = CounterMappingRegion::ExpansionRegion;
+        ExpandedFileID = EncodedCounterAndRegion >>
+                         Counter::EncodingCounterTagAndExpansionRegionTagBits;
+        if (ExpandedFileID >= NumFileIDs)
+          return coveragemap_error::malformed;
+      } else {
+        switch (EncodedCounterAndRegion >>
+                Counter::EncodingCounterTagAndExpansionRegionTagBits) {
+        case CounterMappingRegion::CodeRegion:
+          // Don't do anything when we have a code region with a zero counter.
+          break;
+        case CounterMappingRegion::SkippedRegion:
+          Kind = CounterMappingRegion::SkippedRegion;
+          break;
+        default:
+          return coveragemap_error::malformed;
+        }
+      }
+    }
+
+    // Read the source range.
+    uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd;
+    if (auto Err =
+            readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
+      return Err;
+    if (auto Err = readULEB128(ColumnStart))
+      return Err;
+    if (ColumnStart > std::numeric_limits<unsigned>::max())
+      return coveragemap_error::malformed;
+    if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
+      return Err;
+    if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
+      return Err;
+    LineStart += LineStartDelta;
+    // Adjust the column locations for the empty regions that are supposed to
+    // cover whole lines. Those regions should be encoded with the
+    // column range (1 -> std::numeric_limits<unsigned>::max()), but because
+    // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
+    // we set the column range to (0 -> 0) to ensure that the column start and
+    // column end take up one byte each.
+    // The std::numeric_limits<unsigned>::max() is used to represent a column
+    // position at the end of the line without knowing the length of that line.
+    if (ColumnStart == 0 && ColumnEnd == 0) {
+      ColumnStart = 1;
+      ColumnEnd = std::numeric_limits<unsigned>::max();
+    }
+
+    DEBUG({
+      dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"
+             << ColumnStart << " -> " << (LineStart + NumLines) << ":"
+             << ColumnEnd << ", ";
+      if (Kind == CounterMappingRegion::ExpansionRegion)
+        dbgs() << "Expands to file " << ExpandedFileID;
+      else
+        CounterMappingContext(Expressions).dump(C, dbgs());
+      dbgs() << "\n";
+    });
+
+    MappingRegions.push_back(CounterMappingRegion(
+        C, InferredFileID, ExpandedFileID, LineStart, ColumnStart,
+        LineStart + NumLines, ColumnEnd, Kind));
+  }
+  return std::error_code();
+}
+
+std::error_code RawCoverageMappingReader::read() {
+
+  // Read the virtual file mapping.
+  llvm::SmallVector<unsigned, 8> VirtualFileMapping;
+  uint64_t NumFileMappings;
+  if (auto Err = readSize(NumFileMappings))
+    return Err;
+  for (size_t I = 0; I < NumFileMappings; ++I) {
+    uint64_t FilenameIndex;
+    if (auto Err = readIntMax(FilenameIndex, TranslationUnitFilenames.size()))
+      return Err;
+    VirtualFileMapping.push_back(FilenameIndex);
+  }
+
+  // Construct the files using unique filenames and virtual file mapping.
+  for (auto I : VirtualFileMapping) {
+    Filenames.push_back(TranslationUnitFilenames[I]);
+  }
+
+  // Read the expressions.
+  uint64_t NumExpressions;
+  if (auto Err = readSize(NumExpressions))
+    return Err;
+  // Create an array of dummy expressions that get the proper counters
+  // when the expressions are read, and the proper kinds when the counters
+  // are decoded.
+  Expressions.resize(
+      NumExpressions,
+      CounterExpression(CounterExpression::Subtract, Counter(), Counter()));
+  for (size_t I = 0; I < NumExpressions; ++I) {
+    if (auto Err = readCounter(Expressions[I].LHS))
+      return Err;
+    if (auto Err = readCounter(Expressions[I].RHS))
+      return Err;
+  }
+
+  // Read the mapping regions sub-arrays.
+  for (unsigned InferredFileID = 0, S = VirtualFileMapping.size();
+       InferredFileID < S; ++InferredFileID) {
+    if (auto Err = readMappingRegionsSubArray(MappingRegions, InferredFileID,
+                                              VirtualFileMapping.size()))
+      return Err;
+  }
+
+  // Set the counters for the expansion regions.
+  // i.e. Counter of expansion region = counter of the first region
+  // from the expanded file.
+  // Perform multiple passes to correctly propagate the counters through
+  // all the nested expansion regions.
+  SmallVector<CounterMappingRegion *, 8> FileIDExpansionRegionMapping;
+  FileIDExpansionRegionMapping.resize(VirtualFileMapping.size(), nullptr);
+  for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) {
+    for (auto &R : MappingRegions) {
+      if (R.Kind != CounterMappingRegion::ExpansionRegion)
+        continue;
+      assert(!FileIDExpansionRegionMapping[R.ExpandedFileID]);
+      FileIDExpansionRegionMapping[R.ExpandedFileID] = &R;
+    }
+    for (auto &R : MappingRegions) {
+      if (FileIDExpansionRegionMapping[R.FileID]) {
+        FileIDExpansionRegionMapping[R.FileID]->Count = R.Count;
+        FileIDExpansionRegionMapping[R.FileID] = nullptr;
+      }
+    }
+  }
+
+  return std::error_code();
+}
+
+std::error_code InstrProfSymtab::create(SectionRef &Section) {
+  if (auto Err = Section.getContents(Data))
+    return Err;
+  Address = Section.getAddress();
+  return std::error_code();
+}
+
+StringRef InstrProfSymtab::getFuncName(uint64_t Pointer, size_t Size) {
+  if (Pointer < Address)
+    return StringRef();
+  auto Offset = Pointer - Address;
+  if (Offset + Size > Data.size())
+    return StringRef();
+  return Data.substr(Pointer - Address, Size);
+}
+
+namespace {
+struct CovMapFuncRecordReader {
+  // The interface to read coverage mapping function records for
+  // a module. \p Buf is a reference to the buffer pointer pointing
+  // to the \c CovHeader of coverage mapping data associated with
+  // the module.
+  virtual std::error_code readFunctionRecords(const char *&Buf,
+                                              const char *End) = 0;
+  virtual ~CovMapFuncRecordReader() {}
+  template <class IntPtrT, support::endianness Endian>
+  static std::unique_ptr<CovMapFuncRecordReader>
+  get(coverage::CovMapVersion Version, InstrProfSymtab &P,
+      std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
+      std::vector<StringRef> &F);
+};
+
+// A class for reading coverage mapping function records for a module.
+template <coverage::CovMapVersion Version, class IntPtrT,
+          support::endianness Endian>
+class VersionedCovMapFuncRecordReader : public CovMapFuncRecordReader {
+  typedef typename coverage::CovMapTraits<
+      Version, IntPtrT>::CovMapFuncRecordType FuncRecordType;
+  typedef typename coverage::CovMapTraits<Version, IntPtrT>::NameRefType
+      NameRefType;
+
+  llvm::DenseSet<NameRefType> UniqueFunctionMappingData;
+  InstrProfSymtab &ProfileNames;
+  std::vector<StringRef> &Filenames;
+  std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records;
+
+public:
+  VersionedCovMapFuncRecordReader(
+      InstrProfSymtab &P,
+      std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
+      std::vector<StringRef> &F)
+      : ProfileNames(P), Filenames(F), Records(R) {}
+  ~VersionedCovMapFuncRecordReader() override {}
+
+  std::error_code readFunctionRecords(const char *&Buf,
+                                      const char *End) override {
+    using namespace support;
+    if (Buf + sizeof(CovMapHeader) > End)
+      return coveragemap_error::malformed;
+    auto CovHeader = reinterpret_cast<const coverage::CovMapHeader *>(Buf);
+    uint32_t NRecords = CovHeader->getNRecords<Endian>();
+    uint32_t FilenamesSize = CovHeader->getFilenamesSize<Endian>();
+    uint32_t CoverageSize = CovHeader->getCoverageSize<Endian>();
+    assert((CovMapVersion)CovHeader->getVersion<Endian>() == Version);
+    Buf = reinterpret_cast<const char *>(CovHeader + 1);
+
+    // Skip past the function records, saving the start and end for later.
+    const char *FunBuf = Buf;
+    Buf += NRecords * sizeof(FuncRecordType);
+    const char *FunEnd = Buf;
+
+    // Get the filenames.
+    if (Buf + FilenamesSize > End)
+      return coveragemap_error::malformed;
+    size_t FilenamesBegin = Filenames.size();
+    RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames);
+    if (auto Err = Reader.read())
+      return Err;
+    Buf += FilenamesSize;
+
+    // We'll read the coverage mapping records in the loop below.
+    const char *CovBuf = Buf;
+    Buf += CoverageSize;
+    const char *CovEnd = Buf;
+
+    if (Buf > End)
+      return coveragemap_error::malformed;
+    // Each coverage map has an alignment of 8, so we need to adjust alignment
+    // before reading the next map.
+    Buf += alignmentAdjustment(Buf, 8);
+
+    auto CFR = reinterpret_cast<const FuncRecordType *>(FunBuf);
+    while ((const char *)CFR < FunEnd) {
+      // Read the function information
+      uint32_t DataSize = CFR->template getDataSize<Endian>();
+      uint64_t FuncHash = CFR->template getFuncHash<Endian>();
+
+      // Now use that to read the coverage data.
+      if (CovBuf + DataSize > CovEnd)
+        return coveragemap_error::malformed;
+      auto Mapping = StringRef(CovBuf, DataSize);
+      CovBuf += DataSize;
+
+      // Ignore this record if we already have a record that points to the same
+      // function name. This is useful to ignore the redundant records for the
+      // functions with ODR linkage.
+      NameRefType NameRef = CFR->template getFuncNameRef<Endian>();
+      if (!UniqueFunctionMappingData.insert(NameRef).second) {
+        CFR++;
+        continue;
+      }
+
+      StringRef FuncName;
+      if (std::error_code EC =
+              CFR->template getFuncName<Endian>(ProfileNames, FuncName))
+        return EC;
+      Records.push_back(BinaryCoverageReader::ProfileMappingRecord(
+          Version, FuncName, FuncHash, Mapping, FilenamesBegin,
+          Filenames.size() - FilenamesBegin));
+      CFR++;
+    }
+    return std::error_code();
+  }
+};
+} // end anonymous namespace
+
+template <class IntPtrT, support::endianness Endian>
+std::unique_ptr<CovMapFuncRecordReader> CovMapFuncRecordReader::get(
+    coverage::CovMapVersion Version, InstrProfSymtab &P,
+    std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
+    std::vector<StringRef> &F) {
+  using namespace coverage;
+  switch (Version) {
+  case CovMapVersion::Version1:
+    return llvm::make_unique<VersionedCovMapFuncRecordReader<
+        CovMapVersion::Version1, IntPtrT, Endian>>(P, R, F);
+  case CovMapVersion::Version2:
+    // Decompress the name data.
+    P.create(P.getNameData());
+    return llvm::make_unique<VersionedCovMapFuncRecordReader<
+        CovMapVersion::Version2, IntPtrT, Endian>>(P, R, F);
+  }
+  llvm_unreachable("Unsupported version");
+}
+
+template <typename T, support::endianness Endian>
+static std::error_code readCoverageMappingData(
+    InstrProfSymtab &ProfileNames, StringRef Data,
+    std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records,
+    std::vector<StringRef> &Filenames) {
+  using namespace coverage;
+  // Read the records in the coverage data section.
+  auto CovHeader =
+      reinterpret_cast<const coverage::CovMapHeader *>(Data.data());
+  CovMapVersion Version = (CovMapVersion)CovHeader->getVersion<Endian>();
+  if (Version > coverage::CovMapVersion::CurrentVersion)
+    return coveragemap_error::unsupported_version;
+  std::unique_ptr<CovMapFuncRecordReader> Reader =
+      CovMapFuncRecordReader::get<T, Endian>(Version, ProfileNames, Records,
+                                             Filenames);
+  for (const char *Buf = Data.data(), *End = Buf + Data.size(); Buf < End;) {
+    if (std::error_code EC = Reader->readFunctionRecords(Buf, End))
+      return EC;
+  }
+  return std::error_code();
+}
+static const char *TestingFormatMagic = "llvmcovmtestdata";
+
+static std::error_code loadTestingFormat(StringRef Data,
+                                         InstrProfSymtab &ProfileNames,
+                                         StringRef &CoverageMapping,
+                                         uint8_t &BytesInAddress,
+                                         support::endianness &Endian) {
+  BytesInAddress = 8;
+  Endian = support::endianness::little;
+
+  Data = Data.substr(StringRef(TestingFormatMagic).size());
+  if (Data.size() < 1)
+    return coveragemap_error::truncated;
+  unsigned N = 0;
+  auto ProfileNamesSize =
+      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
+  if (N > Data.size())
+    return coveragemap_error::malformed;
+  Data = Data.substr(N);
+  if (Data.size() < 1)
+    return coveragemap_error::truncated;
+  N = 0;
+  uint64_t Address =
+      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
+  if (N > Data.size())
+    return coveragemap_error::malformed;
+  Data = Data.substr(N);
+  if (Data.size() < ProfileNamesSize)
+    return coveragemap_error::malformed;
+  ProfileNames.create(Data.substr(0, ProfileNamesSize), Address);
+  CoverageMapping = Data.substr(ProfileNamesSize);
+  return std::error_code();
+}
+
+static ErrorOr<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) {
+  StringRef FoundName;
+  for (const auto &Section : OF.sections()) {
+    if (auto EC = Section.getName(FoundName))
+      return EC;
+    if (FoundName == Name)
+      return Section;
+  }
+  return coveragemap_error::no_data_found;
+}
+
+static std::error_code
+loadBinaryFormat(MemoryBufferRef ObjectBuffer, InstrProfSymtab &ProfileNames,
+                 StringRef &CoverageMapping, uint8_t &BytesInAddress,
+                 support::endianness &Endian, StringRef Arch) {
+  auto BinOrErr = object::createBinary(ObjectBuffer);
+  if (!BinOrErr)
+    return errorToErrorCode(BinOrErr.takeError());
+  auto Bin = std::move(BinOrErr.get());
+  std::unique_ptr<ObjectFile> OF;
+  if (auto *Universal = dyn_cast<object::MachOUniversalBinary>(Bin.get())) {
+    // If we have a universal binary, try to look up the object for the
+    // appropriate architecture.
+    auto ObjectFileOrErr = Universal->getObjectForArch(Arch);
+    if (std::error_code EC = ObjectFileOrErr.getError())
+      return EC;
+    OF = std::move(ObjectFileOrErr.get());
+  } else if (isa<object::ObjectFile>(Bin.get())) {
+    // For any other object file, upcast and take ownership.
+    OF.reset(cast<object::ObjectFile>(Bin.release()));
+    // If we've asked for a particular arch, make sure they match.
+    if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
+      return object_error::arch_not_found;
+  } else
+    // We can only handle object files.
+    return coveragemap_error::malformed;
+
+  // The coverage uses native pointer sizes for the object it's written in.
+  BytesInAddress = OF->getBytesInAddress();
+  Endian = OF->isLittleEndian() ? support::endianness::little
+                                : support::endianness::big;
+
+  // Look for the sections that we are interested in.
+  auto NamesSection = lookupSection(*OF, getInstrProfNameSectionName(false));
+  if (auto EC = NamesSection.getError())
+    return EC;
+  auto CoverageSection =
+      lookupSection(*OF, getInstrProfCoverageSectionName(false));
+  if (auto EC = CoverageSection.getError())
+    return EC;
+
+  // Get the contents of the given sections.
+  if (std::error_code EC = CoverageSection->getContents(CoverageMapping))
+    return EC;
+  if (std::error_code EC = ProfileNames.create(*NamesSection))
+    return EC;
+
+  return std::error_code();
+}
+
+ErrorOr<std::unique_ptr<BinaryCoverageReader>>
+BinaryCoverageReader::create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
+                             StringRef Arch) {
+  std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader());
+
+  StringRef Coverage;
+  uint8_t BytesInAddress;
+  support::endianness Endian;
+  std::error_code EC;
+  if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic))
+    // This is a special format used for testing.
+    EC = loadTestingFormat(ObjectBuffer->getBuffer(), Reader->ProfileNames,
+                           Coverage, BytesInAddress, Endian);
+  else
+    EC = loadBinaryFormat(ObjectBuffer->getMemBufferRef(), Reader->ProfileNames,
+                          Coverage, BytesInAddress, Endian, Arch);
+  if (EC)
+    return EC;
+
+  if (BytesInAddress == 4 && Endian == support::endianness::little)
+    EC = readCoverageMappingData<uint32_t, support::endianness::little>(
+        Reader->ProfileNames, Coverage, Reader->MappingRecords,
+        Reader->Filenames);
+  else if (BytesInAddress == 4 && Endian == support::endianness::big)
+    EC = readCoverageMappingData<uint32_t, support::endianness::big>(
+        Reader->ProfileNames, Coverage, Reader->MappingRecords,
+        Reader->Filenames);
+  else if (BytesInAddress == 8 && Endian == support::endianness::little)
+    EC = readCoverageMappingData<uint64_t, support::endianness::little>(
+        Reader->ProfileNames, Coverage, Reader->MappingRecords,
+        Reader->Filenames);
+  else if (BytesInAddress == 8 && Endian == support::endianness::big)
+    EC = readCoverageMappingData<uint64_t, support::endianness::big>(
+        Reader->ProfileNames, Coverage, Reader->MappingRecords,
+        Reader->Filenames);
+  else
+    return coveragemap_error::malformed;
+  if (EC)
+    return EC;
+  return std::move(Reader);
+}
+
+std::error_code
+BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
+  if (CurrentRecord >= MappingRecords.size())
+    return coveragemap_error::eof;
+
+  FunctionsFilenames.clear();
+  Expressions.clear();
+  MappingRegions.clear();
+  auto &R = MappingRecords[CurrentRecord];
+  RawCoverageMappingReader Reader(
+      R.CoverageMapping,
+      makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
+      FunctionsFilenames, Expressions, MappingRegions);
+  if (auto Err = Reader.read())
+    return Err;
+
+  Record.FunctionName = R.FunctionName;
+  Record.FunctionHash = R.FunctionHash;
+  Record.Filenames = FunctionsFilenames;
+  Record.Expressions = Expressions;
+  Record.MappingRegions = MappingRegions;
+
+  ++CurrentRecord;
+  return std::error_code();
+}

llvm/trunk/lib/ProfileData/Coverage/CoverageMappingWriter.cpp

+//=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains support for writing coverage mapping data for
+// instrumentation based coverage.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
+#include "llvm/Support/LEB128.h"
+
+using namespace llvm;
+using namespace coverage;
+
+void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
+  encodeULEB128(Filenames.size(), OS);
+  for (const auto &Filename : Filenames) {
+    encodeULEB128(Filename.size(), OS);
+    OS << Filename;
+  }
+}
+
+namespace {
+/// \brief Gather only the expressions that are used by the mapping
+/// regions in this function.
+class CounterExpressionsMinimizer {
+  ArrayRef<CounterExpression> Expressions;
+  llvm::SmallVector<CounterExpression, 16> UsedExpressions;
+  std::vector<unsigned> AdjustedExpressionIDs;
+
+public:
+  void mark(Counter C) {
+    if (!C.isExpression())
+      return;
+    unsigned ID = C.getExpressionID();
+    AdjustedExpressionIDs[ID] = 1;
+    mark(Expressions[ID].LHS);
+    mark(Expressions[ID].RHS);
+  }
+
+  void gatherUsed(Counter C) {
+    if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
+      return;
+    AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
+    const auto &E = Expressions[C.getExpressionID()];
+    UsedExpressions.push_back(E);
+    gatherUsed(E.LHS);
+    gatherUsed(E.RHS);
+  }
+
+  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
+                              ArrayRef<CounterMappingRegion> MappingRegions)
+      : Expressions(Expressions) {
+    AdjustedExpressionIDs.resize(Expressions.size(), 0);
+    for (const auto &I : MappingRegions)
+      mark(I.Count);
+    for (const auto &I : MappingRegions)
+      gatherUsed(I.Count);
+  }
+
+  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
+
+  /// \brief Adjust the given counter to correctly transition from the old
+  /// expression ids to the new expression ids.
+  Counter adjust(Counter C) const {
+    if (C.isExpression())
+      C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
+    return C;
+  }
+};
+}
+
+/// \brief Encode the counter.
+///
+/// The encoding uses the following format:
+/// Low 2 bits - Tag:
+///   Counter::Zero(0) - A Counter with kind Counter::Zero
+///   Counter::CounterValueReference(1) - A counter with kind
+///     Counter::CounterValueReference
+///   Counter::Expression(2) + CounterExpression::Subtract(0) -
+///     A counter with kind Counter::Expression and an expression
+///     with kind CounterExpression::Subtract
+///   Counter::Expression(2) + CounterExpression::Add(1) -
+///     A counter with kind Counter::Expression and an expression
+///     with kind CounterExpression::Add
+/// Remaining bits - Counter/Expression ID.
+static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
+                              Counter C) {
+  unsigned Tag = unsigned(C.getKind());
+  if (C.isExpression())
+    Tag += Expressions[C.getExpressionID()].Kind;
+  unsigned ID = C.getCounterID();
+  assert(ID <=
+         (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
+  return Tag | (ID << Counter::EncodingTagBits);
+}
+
+static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
+                         raw_ostream &OS) {
+  encodeULEB128(encodeCounter(Expressions, C), OS);
+}
+
+void CoverageMappingWriter::write(raw_ostream &OS) {
+  // Sort the regions in an ascending order by the file id and the starting
+  // location.
+  std::stable_sort(MappingRegions.begin(), MappingRegions.end());
+
+  // Write out the fileid -> filename mapping.
+  encodeULEB128(VirtualFileMapping.size(), OS);
+  for (const auto &FileID : VirtualFileMapping)
+    encodeULEB128(FileID, OS);
+
+  // Write out the expressions.
+  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
+  auto MinExpressions = Minimizer.getExpressions();
+  encodeULEB128(MinExpressions.size(), OS);
+  for (const auto &E : MinExpressions) {
+    writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
+    writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
+  }
+
+  // Write out the mapping regions.
+  // Split the regions into subarrays where each region in a
+  // subarray has a fileID which is the index of that subarray.
+  unsigned PrevLineStart = 0;
+  unsigned CurrentFileID = ~0U;
+  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
+    if (I->FileID != CurrentFileID) {
+      // Ensure that all file ids have at least one mapping region.
+      assert(I->FileID == (CurrentFileID + 1));
+      // Find the number of regions with this file id.
+      unsigned RegionCount = 1;
+      for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
+        ++RegionCount;
+      // Start a new region sub-array.
+      encodeULEB128(RegionCount, OS);
+
+      CurrentFileID = I->FileID;
+      PrevLineStart = 0;
+    }
+    Counter Count = Minimizer.adjust(I->Count);
+    switch (I->Kind) {
+    case CounterMappingRegion::CodeRegion:
+      writeCounter(MinExpressions, Count, OS);
+      break;
+    case CounterMappingRegion::ExpansionRegion: {
+      assert(Count.isZero());
+      assert(I->ExpandedFileID <=
+             (std::numeric_limits<unsigned>::max() >>
+              Counter::EncodingCounterTagAndExpansionRegionTagBits));
+      // Mark an expansion region with a set bit that follows the counter tag,
+      // and pack the expanded file id into the remaining bits.
+      unsigned EncodedTagExpandedFileID =
+          (1 << Counter::EncodingTagBits) |
+          (I->ExpandedFileID
+           << Counter::EncodingCounterTagAndExpansionRegionTagBits);
+      encodeULEB128(EncodedTagExpandedFileID, OS);
+      break;
+    }
+    case CounterMappingRegion::SkippedRegion:
+      assert(Count.isZero());
+      encodeULEB128(unsigned(I->Kind)
+                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
+                    OS);
+      break;
+    }
+    assert(I->LineStart >= PrevLineStart);
+    encodeULEB128(I->LineStart - PrevLineStart, OS);
+    encodeULEB128(I->ColumnStart, OS);
+    assert(I->LineEnd >= I->LineStart);
+    encodeULEB128(I->LineEnd - I->LineStart, OS);
+    encodeULEB128(I->ColumnEnd, OS);
+    PrevLineStart = I->LineStart;
+  }
+  // Ensure that all file ids have at least one mapping region.
+  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
+}

llvm/trunk/lib/ProfileData/Coverage/LLVMBuild.txt

+;===- ./lib/ProfileData/Coverage/LLVMBuild.txt -----------------*- Conf -*--===;
+;
+;                     The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+;   http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = Coverage
+parent = ProfileData
+required_libraries = Core Object ProfileData Support
+

llvm/trunk/lib/ProfileData/CoverageMapping.cpp

-//=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains support for clang's and llvm's instrumentation based
-// code coverage.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ProfileData/CoverageMapping.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Optional.h"
-#include "llvm/ADT/SmallBitVector.h"
-#include "llvm/ProfileData/CoverageMappingReader.h"
-#include "llvm/ProfileData/InstrProfReader.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Errc.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/ManagedStatic.h"
-#include "llvm/Support/Path.h"
-#include "llvm/Support/raw_ostream.h"
-
-using namespace llvm;
-using namespace coverage;
-
-#define DEBUG_TYPE "coverage-mapping"
-
-Counter CounterExpressionBuilder::get(const CounterExpression &E) {
-  auto It = ExpressionIndices.find(E);
-  if (It != ExpressionIndices.end())
-    return Counter::getExpression(It->second);
-  unsigned I = Expressions.size();
-  Expressions.push_back(E);
-  ExpressionIndices[E] = I;
-  return Counter::getExpression(I);
-}
-
-void CounterExpressionBuilder::extractTerms(
-    Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
-  switch (C.getKind()) {
-  case Counter::Zero:
-    break;
-  case Counter::CounterValueReference:
-    Terms.push_back(std::make_pair(C.getCounterID(), Sign));
-    break;
-  case Counter::Expression:
-    const auto &E = Expressions[C.getExpressionID()];
-    extractTerms(E.LHS, Sign, Terms);
-    extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
-                 Terms);
-    break;
-  }
-}
-
-Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
-  // Gather constant terms.
-  llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
-  extractTerms(ExpressionTree, +1, Terms);
-
-  // If there are no terms, this is just a zero. The algorithm below assumes at
-  // least one term.
-  if (Terms.size() == 0)
-    return Counter::getZero();
-
-  // Group the terms by counter ID.
-  std::sort(Terms.begin(), Terms.end(),
-            [](const std::pair<unsigned, int> &LHS,
-               const std::pair<unsigned, int> &RHS) {
-    return LHS.first < RHS.first;
-  });
-
-  // Combine terms by counter ID to eliminate counters that sum to zero.
-  auto Prev = Terms.begin();
-  for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
-    if (I->first == Prev->first) {
-      Prev->second += I->second;
-      continue;
-    }
-    ++Prev;
-    *Prev = *I;
-  }
-  Terms.erase(++Prev, Terms.end());
-
-  Counter C;
-  // Create additions. We do this before subtractions to avoid constructs like
-  // ((0 - X) + Y), as opposed to (Y - X).
-  for (auto Term : Terms) {
-    if (Term.second <= 0)
-      continue;
-    for (int I = 0; I < Term.second; ++I)
-      if (C.isZero())
-        C = Counter::getCounter(Term.first);
-      else
-        C = get(CounterExpression(CounterExpression::Add, C,
-                                  Counter::getCounter(Term.first)));
-  }
-
-  // Create subtractions.
-  for (auto Term : Terms) {
-    if (Term.second >= 0)
-      continue;
-    for (int I = 0; I < -Term.second; ++I)
-      C = get(CounterExpression(CounterExpression::Subtract, C,
-                                Counter::getCounter(Term.first)));
-  }
-  return C;
-}
-
-Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
-  return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
-}
-
-Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
-  return simplify(
-      get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
-}
-
-void CounterMappingContext::dump(const Counter &C,
-                                 llvm::raw_ostream &OS) const {
-  switch (C.getKind()) {
-  case Counter::Zero:
-    OS << '0';
-    return;
-  case Counter::CounterValueReference:
-    OS << '#' << C.getCounterID();
-    break;
-  case Counter::Expression: {
-    if (C.getExpressionID() >= Expressions.size())
-      return;
-    const auto &E = Expressions[C.getExpressionID()];
-    OS << '(';
-    dump(E.LHS, OS);
-    OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
-    dump(E.RHS, OS);
-    OS << ')';
-    break;
-  }
-  }
-  if (CounterValues.empty())
-    return;
-  ErrorOr<int64_t> Value = evaluate(C);
-  if (!Value)
-    return;
-  OS << '[' << *Value << ']';
-}
-
-ErrorOr<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
-  switch (C.getKind()) {
-  case Counter::Zero:
-    return 0;
-  case Counter::CounterValueReference:
-    if (C.getCounterID() >= CounterValues.size())
-      return make_error_code(errc::argument_out_of_domain);
-    return CounterValues[C.getCounterID()];
-  case Counter::Expression: {
-    if (C.getExpressionID() >= Expressions.size())
-      return make_error_code(errc::argument_out_of_domain);
-    const auto &E = Expressions[C.getExpressionID()];
-    ErrorOr<int64_t> LHS = evaluate(E.LHS);
-    if (!LHS)
-      return LHS;
-    ErrorOr<int64_t> RHS = evaluate(E.RHS);
-    if (!RHS)
-      return RHS;
-    return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
-  }
-  }
-  llvm_unreachable("Unhandled CounterKind");
-}
-
-void FunctionRecordIterator::skipOtherFiles() {
-  while (Current != Records.end() && !Filename.empty() &&
-         Filename != Current->Filenames[0])
-    ++Current;
-  if (Current == Records.end())
-    *this = FunctionRecordIterator();
-}
-
-ErrorOr<std::unique_ptr<CoverageMapping>>
-CoverageMapping::load(CoverageMappingReader &CoverageReader,
-                      IndexedInstrProfReader &ProfileReader) {
-  auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
-
-  std::vector<uint64_t> Counts;
-  for (const auto &Record : CoverageReader) {
-    CounterMappingContext Ctx(Record.Expressions);
-
-    Counts.clear();
-    if (std::error_code EC = ProfileReader.getFunctionCounts(
-            Record.FunctionName, Record.FunctionHash, Counts)) {
-      if (EC == instrprof_error::hash_mismatch) {
-        Coverage->MismatchedFunctionCount++;
-        continue;
-      } else if (EC != instrprof_error::unknown_function)
-        return EC;
-      Counts.assign(Record.MappingRegions.size(), 0);
-    }
-    Ctx.setCounts(Counts);
-
-    assert(!Record.MappingRegions.empty() && "Function has no regions");
-
-    StringRef OrigFuncName = Record.FunctionName;
-    if (Record.Filenames.empty())
-      OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
-    else
-      OrigFuncName =
-          getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
-    FunctionRecord Function(OrigFuncName, Record.Filenames);
-    for (const auto &Region : Record.MappingRegions) {
-      ErrorOr<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
-      if (!ExecutionCount)
-        break;
-      Function.pushRegion(Region, *ExecutionCount);
-    }
-    if (Function.CountedRegions.size() != Record.MappingRegions.size()) {
-      Coverage->MismatchedFunctionCount++;
-      continue;
-    }
-
-    Coverage->Functions.push_back(std::move(Function));
-  }
-
-  return std::move(Coverage);
-}
-
-ErrorOr<std::unique_ptr<CoverageMapping>>
-CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename,
-                      StringRef Arch) {
-  auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename);
-  if (std::error_code EC = CounterMappingBuff.getError())
-    return EC;
-  auto CoverageReaderOrErr =
-      BinaryCoverageReader::create(CounterMappingBuff.get(), Arch);
-  if (std::error_code EC = CoverageReaderOrErr.getError())
-    return EC;
-  auto CoverageReader = std::move(CoverageReaderOrErr.get());
-  auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
-  if (auto EC = ProfileReaderOrErr.getError())
-    return EC;
-  auto ProfileReader = std::move(ProfileReaderOrErr.get());
-  return load(*CoverageReader, *ProfileReader);
-}
-
-namespace {
-/// \brief Distributes functions into instantiation sets.
-///
-/// An instantiation set is a collection of functions that have the same source
-/// code, ie, template functions specializations.
-class FunctionInstantiationSetCollector {
-  typedef DenseMap<std::pair<unsigned, unsigned>,
-                   std::vector<const FunctionRecord *>> MapT;
-  MapT InstantiatedFunctions;
-
-public:
-  void insert(const FunctionRecord &Function, unsigned FileID) {
-    auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
-    while (I != E && I->FileID != FileID)
-      ++I;
-    assert(I != E && "function does not cover the given file");
-    auto &Functions = InstantiatedFunctions[I->startLoc()];
-    Functions.push_back(&Function);
-  }
-
-  MapT::iterator begin() { return InstantiatedFunctions.begin(); }
-
-  MapT::iterator end() { return InstantiatedFunctions.end(); }
-};
-
-class SegmentBuilder {
-  std::vector<CoverageSegment> &Segments;
-  SmallVector<const CountedRegion *, 8> ActiveRegions;
-
-  SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
-
-  /// Start a segment with no count specified.
-  void startSegment(unsigned Line, unsigned Col) {
-    DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
-    Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
-  }
-
-  /// Start a segment with the given Region's count.
-  void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
-                    const CountedRegion &Region) {
-    // Avoid creating empty regions.
-    if (!Segments.empty() && Segments.back().Line == Line &&
-        Segments.back().Col == Col)
-      Segments.pop_back();
-    DEBUG(dbgs() << "Segment at " << Line << ":" << Col);
-    // Set this region's count.
-    if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) {
-      DEBUG(dbgs() << " with count " << Region.ExecutionCount);
-      Segments.emplace_back(Line, Col, Region.ExecutionCount, IsRegionEntry);
-    } else
-      Segments.emplace_back(Line, Col, IsRegionEntry);
-    DEBUG(dbgs() << "\n");
-  }
-
-  /// Start a segment for the given region.
-  void startSegment(const CountedRegion &Region) {
-    startSegment(Region.LineStart, Region.ColumnStart, true, Region);
-  }
-
-  /// Pop the top region off of the active stack, starting a new segment with
-  /// the containing Region's count.
-  void popRegion() {
-    const CountedRegion *Active = ActiveRegions.back();
-    unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
-    ActiveRegions.pop_back();
-    if (ActiveRegions.empty())
-      startSegment(Line, Col);
-    else
-      startSegment(Line, Col, false, *ActiveRegions.back());
-  }
-
-  void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
-    for (const auto &Region : Regions) {
-      // Pop any regions that end before this one starts.
-      while (!ActiveRegions.empty() &&
-             ActiveRegions.back()->endLoc() <= Region.startLoc())
-        popRegion();
-      // Add this region to the stack.
-      ActiveRegions.push_back(&Region);
-      startSegment(Region);
-    }
-    // Pop any regions that are left in the stack.
-    while (!ActiveRegions.empty())
-      popRegion();
-  }
-
-  /// Sort a nested sequence of regions from a single file.
-  static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
-    std::sort(Regions.begin(), Regions.end(),
-              [](const CountedRegion &LHS, const CountedRegion &RHS) {
-                if (LHS.startLoc() == RHS.startLoc())
-                  // When LHS completely contains RHS, we sort LHS first.
-                  return RHS.endLoc() < LHS.endLoc();
-                return LHS.startLoc() < RHS.startLoc();
-              });
-  }
-
-  /// Combine counts of regions which cover the same area.
-  static ArrayRef<CountedRegion>
-  combineRegions(MutableArrayRef<CountedRegion> Regions) {
-    if (Regions.empty())
-      return Regions;
-    auto Active = Regions.begin();
-    auto End = Regions.end();
-    for (auto I = Regions.begin() + 1; I != End; ++I) {
-      if (Active->startLoc() != I->startLoc() ||
-          Active->endLoc() != I->endLoc()) {
-        // Shift to the next region.
-        ++Active;
-        if (Active != I)
-          *Active = *I;
-        continue;
-      }
-      // Merge duplicate region.
-      if (I->Kind != coverage::CounterMappingRegion::CodeRegion)
-        // Add counts only from CodeRegions.
-        continue;
-      if (Active->Kind == coverage::CounterMappingRegion::SkippedRegion)
-        // We have to overwrite SkippedRegions because of special handling
-        // of them in startSegment().
-        *Active = *I;
-      else
-        // Otherwise, just append the count.
-        Active->ExecutionCount += I->ExecutionCount;
-    }
-    return Regions.drop_back(std::distance(++Active, End));
-  }
-
-public:
-  /// Build a list of CoverageSegments from a list of Regions.
-  static std::vector<CoverageSegment>
-  buildSegments(MutableArrayRef<CountedRegion> Regions) {
-    std::vector<CoverageSegment> Segments;
-    SegmentBuilder Builder(Segments);
-
-    sortNestedRegions(Regions);
-    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
-
-    Builder.buildSegmentsImpl(CombinedRegions);
-    return Segments;
-  }
-};
-}
-
-std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
-  std::vector<StringRef> Filenames;
-  for (const auto &Function : getCoveredFunctions())
-    Filenames.insert(Filenames.end(), Function.Filenames.begin(),
-                     Function.Filenames.end());
-  std::sort(Filenames.begin(), Filenames.end());
-  auto Last = std::unique(Filenames.begin(), Filenames.end());
-  Filenames.erase(Last, Filenames.end());
-  return Filenames;
-}
-
-static SmallBitVector gatherFileIDs(StringRef SourceFile,
-                                    const FunctionRecord &Function) {
-  SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
-  for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
-    if (SourceFile == Function.Filenames[I])
-      FilenameEquivalence[I] = true;
-  return FilenameEquivalence;
-}
-
-/// Return the ID of the file where the definition of the function is located.
-static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
-  SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
-  for (const auto &CR : Function.CountedRegions)
-    if (CR.Kind == CounterMappingRegion::ExpansionRegion)
-      IsNotExpandedFile[CR.ExpandedFileID] = false;
-  int I = IsNotExpandedFile.find_first();
-  if (I == -1)
-    return None;
-  return I;
-}
-
-/// Check if SourceFile is the file that contains the definition of
-/// the Function. Return the ID of the file in that case or None otherwise.
-static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
-                                             const FunctionRecord &Function) {
-  Optional<unsigned> I = findMainViewFileID(Function);
-  if (I && SourceFile == Function.Filenames[*I])
-    return I;
-  return None;
-}
-
-static bool isExpansion(const CountedRegion &R, unsigned FileID) {
-  return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
-}
-
-CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) {
-  CoverageData FileCoverage(Filename);
-  std::vector<coverage::CountedRegion> Regions;
-
-  for (const auto &Function : Functions) {
-    auto MainFileID = findMainViewFileID(Filename, Function);
-    auto FileIDs = gatherFileIDs(Filename, Function);
-    for (const auto &CR : Function.CountedRegions)
-      if (FileIDs.test(CR.FileID)) {
-        Regions.push_back(CR);
-        if (MainFileID && isExpansion(CR, *MainFileID))
-          FileCoverage.Expansions.emplace_back(CR, Function);
-      }
-  }
-
-  DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
-  FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
-
-  return FileCoverage;
-}
-
-std::vector<const FunctionRecord *>
-CoverageMapping::getInstantiations(StringRef Filename) {
-  FunctionInstantiationSetCollector InstantiationSetCollector;
-  for (const auto &Function : Functions) {
-    auto MainFileID = findMainViewFileID(Filename, Function);
-    if (!MainFileID)
-      continue;
-    InstantiationSetCollector.insert(Function, *MainFileID);
-  }
-
-  std::vector<const FunctionRecord *> Result;
-  for (const auto &InstantiationSet : InstantiationSetCollector) {
-    if (InstantiationSet.second.size() < 2)
-      continue;
-    Result.insert(Result.end(), InstantiationSet.second.begin(),
-                  InstantiationSet.second.end());
-  }
-  return Result;
-}
-
-CoverageData
-CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
-  auto MainFileID = findMainViewFileID(Function);
-  if (!MainFileID)
-    return CoverageData();
-
-  CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
-  std::vector<coverage::CountedRegion> Regions;
-  for (const auto &CR : Function.CountedRegions)
-    if (CR.FileID == *MainFileID) {
-      Regions.push_back(CR);
-      if (isExpansion(CR, *MainFileID))
-        FunctionCoverage.Expansions.emplace_back(CR, Function);
-    }
-
-  DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
-  FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
-
-  return FunctionCoverage;
-}
-
-CoverageData
-CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) {
-  CoverageData ExpansionCoverage(
-      Expansion.Function.Filenames[Expansion.FileID]);
-  std::vector<coverage::CountedRegion> Regions;
-  for (const auto &CR : Expansion.Function.CountedRegions)
-    if (CR.FileID == Expansion.FileID) {
-      Regions.push_back(CR);
-      if (isExpansion(CR, Expansion.FileID))
-        ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
-    }
-
-  DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
-               << "\n");
-  ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
-
-  return ExpansionCoverage;
-}
-
-namespace {
-class CoverageMappingErrorCategoryType : public std::error_category {
-  const char *name() const LLVM_NOEXCEPT override { return "llvm.coveragemap"; }
-  std::string message(int IE) const override {
-    auto E = static_cast<coveragemap_error>(IE);
-    switch (E) {
-    case coveragemap_error::success:
-      return "Success";
-    case coveragemap_error::eof:
-      return "End of File";
-    case coveragemap_error::no_data_found:
-      return "No coverage data found";
-    case coveragemap_error::unsupported_version:
-      return "Unsupported coverage format version";
-    case coveragemap_error::truncated:
-      return "Truncated coverage data";
-    case coveragemap_error::malformed:
-      return "Malformed coverage data";
-    }
-    llvm_unreachable("A value of coveragemap_error has no message.");
-  }
-};
-}
-
-static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;
-
-const std::error_category &llvm::coverage::coveragemap_category() {
-  return *ErrorCategory;
-}

llvm/trunk/lib/ProfileData/CoverageMappingReader.cpp

-//=-- CoverageMappingReader.cpp - Code coverage mapping reader ----*- C++ -*-=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains support for reading coverage mapping data for
-// instrumentation based coverage.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ProfileData/CoverageMappingReader.h"
-#include "llvm/ADT/DenseSet.h"
-#include "llvm/Object/MachOUniversal.h"
-#include "llvm/Object/ObjectFile.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Endian.h"
-#include "llvm/Support/LEB128.h"
-#include "llvm/Support/MathExtras.h"
-#include "llvm/Support/raw_ostream.h"
-
-using namespace llvm;
-using namespace coverage;
-using namespace object;
-
-#define DEBUG_TYPE "coverage-mapping"
-
-void CoverageMappingIterator::increment() {
-  // Check if all the records were read or if an error occurred while reading
-  // the next record.
-  if (Reader->readNextRecord(Record))
-    *this = CoverageMappingIterator();
-}
-
-std::error_code RawCoverageReader::readULEB128(uint64_t &Result) {
-  if (Data.size() < 1)
-    return coveragemap_error::truncated;
-  unsigned N = 0;
-  Result = decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
-  if (N > Data.size())
-    return coveragemap_error::malformed;
-  Data = Data.substr(N);
-  return std::error_code();
-}
-
-std::error_code RawCoverageReader::readIntMax(uint64_t &Result,
-                                              uint64_t MaxPlus1) {
-  if (auto Err = readULEB128(Result))
-    return Err;
-  if (Result >= MaxPlus1)
-    return coveragemap_error::malformed;
-  return std::error_code();
-}
-
-std::error_code RawCoverageReader::readSize(uint64_t &Result) {
-  if (auto Err = readULEB128(Result))
-    return Err;
-  // Sanity check the number.
-  if (Result > Data.size())
-    return coveragemap_error::malformed;
-  return std::error_code();
-}
-
-std::error_code RawCoverageReader::readString(StringRef &Result) {
-  uint64_t Length;
-  if (auto Err = readSize(Length))
-    return Err;
-  Result = Data.substr(0, Length);
-  Data = Data.substr(Length);
-  return std::error_code();
-}
-
-std::error_code RawCoverageFilenamesReader::read() {
-  uint64_t NumFilenames;
-  if (auto Err = readSize(NumFilenames))
-    return Err;
-  for (size_t I = 0; I < NumFilenames; ++I) {
-    StringRef Filename;
-    if (auto Err = readString(Filename))
-      return Err;
-    Filenames.push_back(Filename);
-  }
-  return std::error_code();
-}
-
-std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value,
-                                                        Counter &C) {
-  auto Tag = Value & Counter::EncodingTagMask;
-  switch (Tag) {
-  case Counter::Zero:
-    C = Counter::getZero();
-    return std::error_code();
-  case Counter::CounterValueReference:
-    C = Counter::getCounter(Value >> Counter::EncodingTagBits);
-    return std::error_code();
-  default:
-    break;
-  }
-  Tag -= Counter::Expression;
-  switch (Tag) {
-  case CounterExpression::Subtract:
-  case CounterExpression::Add: {
-    auto ID = Value >> Counter::EncodingTagBits;
-    if (ID >= Expressions.size())
-      return coveragemap_error::malformed;
-    Expressions[ID].Kind = CounterExpression::ExprKind(Tag);
-    C = Counter::getExpression(ID);
-    break;
-  }
-  default:
-    return coveragemap_error::malformed;
-  }
-  return std::error_code();
-}
-
-std::error_code RawCoverageMappingReader::readCounter(Counter &C) {
-  uint64_t EncodedCounter;
-  if (auto Err =
-          readIntMax(EncodedCounter, std::numeric_limits<unsigned>::max()))
-    return Err;
-  if (auto Err = decodeCounter(EncodedCounter, C))
-    return Err;
-  return std::error_code();
-}
-
-static const unsigned EncodingExpansionRegionBit = 1
-                                                   << Counter::EncodingTagBits;
-
-/// \brief Read the sub-array of regions for the given inferred file id.
-/// \param NumFileIDs the number of file ids that are defined for this
-/// function.
-std::error_code RawCoverageMappingReader::readMappingRegionsSubArray(
-    std::vector<CounterMappingRegion> &MappingRegions, unsigned InferredFileID,
-    size_t NumFileIDs) {
-  uint64_t NumRegions;
-  if (auto Err = readSize(NumRegions))
-    return Err;
-  unsigned LineStart = 0;
-  for (size_t I = 0; I < NumRegions; ++I) {
-    Counter C;
-    CounterMappingRegion::RegionKind Kind = CounterMappingRegion::CodeRegion;
-
-    // Read the combined counter + region kind.
-    uint64_t EncodedCounterAndRegion;
-    if (auto Err = readIntMax(EncodedCounterAndRegion,
-                              std::numeric_limits<unsigned>::max()))
-      return Err;
-    unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask;
-    uint64_t ExpandedFileID = 0;
-    if (Tag != Counter::Zero) {
-      if (auto Err = decodeCounter(EncodedCounterAndRegion, C))
-        return Err;
-    } else {
-      // Is it an expansion region?
-      if (EncodedCounterAndRegion & EncodingExpansionRegionBit) {
-        Kind = CounterMappingRegion::ExpansionRegion;
-        ExpandedFileID = EncodedCounterAndRegion >>
-                         Counter::EncodingCounterTagAndExpansionRegionTagBits;
-        if (ExpandedFileID >= NumFileIDs)
-          return coveragemap_error::malformed;
-      } else {
-        switch (EncodedCounterAndRegion >>
-                Counter::EncodingCounterTagAndExpansionRegionTagBits) {
-        case CounterMappingRegion::CodeRegion:
-          // Don't do anything when we have a code region with a zero counter.
-          break;
-        case CounterMappingRegion::SkippedRegion:
-          Kind = CounterMappingRegion::SkippedRegion;
-          break;
-        default:
-          return coveragemap_error::malformed;
-        }
-      }
-    }
-
-    // Read the source range.
-    uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd;
-    if (auto Err =
-            readIntMax(LineStartDelta, std::numeric_limits<unsigned>::max()))
-      return Err;
-    if (auto Err = readULEB128(ColumnStart))
-      return Err;
-    if (ColumnStart > std::numeric_limits<unsigned>::max())
-      return coveragemap_error::malformed;
-    if (auto Err = readIntMax(NumLines, std::numeric_limits<unsigned>::max()))
-      return Err;
-    if (auto Err = readIntMax(ColumnEnd, std::numeric_limits<unsigned>::max()))
-      return Err;
-    LineStart += LineStartDelta;
-    // Adjust the column locations for the empty regions that are supposed to
-    // cover whole lines. Those regions should be encoded with the
-    // column range (1 -> std::numeric_limits<unsigned>::max()), but because
-    // the encoded std::numeric_limits<unsigned>::max() is several bytes long,
-    // we set the column range to (0 -> 0) to ensure that the column start and
-    // column end take up one byte each.
-    // The std::numeric_limits<unsigned>::max() is used to represent a column
-    // position at the end of the line without knowing the length of that line.
-    if (ColumnStart == 0 && ColumnEnd == 0) {
-      ColumnStart = 1;
-      ColumnEnd = std::numeric_limits<unsigned>::max();
-    }
-
-    DEBUG({
-      dbgs() << "Counter in file " << InferredFileID << " " << LineStart << ":"
-             << ColumnStart << " -> " << (LineStart + NumLines) << ":"
-             << ColumnEnd << ", ";
-      if (Kind == CounterMappingRegion::ExpansionRegion)
-        dbgs() << "Expands to file " << ExpandedFileID;
-      else
-        CounterMappingContext(Expressions).dump(C, dbgs());
-      dbgs() << "\n";
-    });
-
-    MappingRegions.push_back(CounterMappingRegion(
-        C, InferredFileID, ExpandedFileID, LineStart, ColumnStart,
-        LineStart + NumLines, ColumnEnd, Kind));
-  }
-  return std::error_code();
-}
-
-std::error_code RawCoverageMappingReader::read() {
-
-  // Read the virtual file mapping.
-  llvm::SmallVector<unsigned, 8> VirtualFileMapping;
-  uint64_t NumFileMappings;
-  if (auto Err = readSize(NumFileMappings))
-    return Err;
-  for (size_t I = 0; I < NumFileMappings; ++I) {
-    uint64_t FilenameIndex;
-    if (auto Err = readIntMax(FilenameIndex, TranslationUnitFilenames.size()))
-      return Err;
-    VirtualFileMapping.push_back(FilenameIndex);
-  }
-
-  // Construct the files using unique filenames and virtual file mapping.
-  for (auto I : VirtualFileMapping) {
-    Filenames.push_back(TranslationUnitFilenames[I]);
-  }
-
-  // Read the expressions.
-  uint64_t NumExpressions;
-  if (auto Err = readSize(NumExpressions))
-    return Err;
-  // Create an array of dummy expressions that get the proper counters
-  // when the expressions are read, and the proper kinds when the counters
-  // are decoded.
-  Expressions.resize(
-      NumExpressions,
-      CounterExpression(CounterExpression::Subtract, Counter(), Counter()));
-  for (size_t I = 0; I < NumExpressions; ++I) {
-    if (auto Err = readCounter(Expressions[I].LHS))
-      return Err;
-    if (auto Err = readCounter(Expressions[I].RHS))
-      return Err;
-  }
-
-  // Read the mapping regions sub-arrays.
-  for (unsigned InferredFileID = 0, S = VirtualFileMapping.size();
-       InferredFileID < S; ++InferredFileID) {
-    if (auto Err = readMappingRegionsSubArray(MappingRegions, InferredFileID,
-                                              VirtualFileMapping.size()))
-      return Err;
-  }
-
-  // Set the counters for the expansion regions.
-  // i.e. Counter of expansion region = counter of the first region
-  // from the expanded file.
-  // Perform multiple passes to correctly propagate the counters through
-  // all the nested expansion regions.
-  SmallVector<CounterMappingRegion *, 8> FileIDExpansionRegionMapping;
-  FileIDExpansionRegionMapping.resize(VirtualFileMapping.size(), nullptr);
-  for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) {
-    for (auto &R : MappingRegions) {
-      if (R.Kind != CounterMappingRegion::ExpansionRegion)
-        continue;
-      assert(!FileIDExpansionRegionMapping[R.ExpandedFileID]);
-      FileIDExpansionRegionMapping[R.ExpandedFileID] = &R;
-    }
-    for (auto &R : MappingRegions) {
-      if (FileIDExpansionRegionMapping[R.FileID]) {
-        FileIDExpansionRegionMapping[R.FileID]->Count = R.Count;
-        FileIDExpansionRegionMapping[R.FileID] = nullptr;
-      }
-    }
-  }
-
-  return std::error_code();
-}
-
-std::error_code InstrProfSymtab::create(SectionRef &Section) {
-  if (auto Err = Section.getContents(Data))
-    return Err;
-  Address = Section.getAddress();
-  return std::error_code();
-}
-
-StringRef InstrProfSymtab::getFuncName(uint64_t Pointer, size_t Size) {
-  if (Pointer < Address)
-    return StringRef();
-  auto Offset = Pointer - Address;
-  if (Offset + Size > Data.size())
-    return StringRef();
-  return Data.substr(Pointer - Address, Size);
-}
-
-namespace {
-struct CovMapFuncRecordReader {
-  // The interface to read coverage mapping function records for
-  // a module. \p Buf is a reference to the buffer pointer pointing
-  // to the \c CovHeader of coverage mapping data associated with
-  // the module.
-  virtual std::error_code readFunctionRecords(const char *&Buf,
-                                              const char *End) = 0;
-  virtual ~CovMapFuncRecordReader() {}
-  template <class IntPtrT, support::endianness Endian>
-  static std::unique_ptr<CovMapFuncRecordReader>
-  get(coverage::CovMapVersion Version, InstrProfSymtab &P,
-      std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
-      std::vector<StringRef> &F);
-};
-
-// A class for reading coverage mapping function records for a module.
-template <coverage::CovMapVersion Version, class IntPtrT,
-          support::endianness Endian>
-class VersionedCovMapFuncRecordReader : public CovMapFuncRecordReader {
-  typedef typename coverage::CovMapTraits<
-      Version, IntPtrT>::CovMapFuncRecordType FuncRecordType;
-  typedef typename coverage::CovMapTraits<Version, IntPtrT>::NameRefType
-      NameRefType;
-
-  llvm::DenseSet<NameRefType> UniqueFunctionMappingData;
-  InstrProfSymtab &ProfileNames;
-  std::vector<StringRef> &Filenames;
-  std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records;
-
-public:
-  VersionedCovMapFuncRecordReader(
-      InstrProfSymtab &P,
-      std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
-      std::vector<StringRef> &F)
-      : ProfileNames(P), Filenames(F), Records(R) {}
-  ~VersionedCovMapFuncRecordReader() override {}
-
-  std::error_code readFunctionRecords(const char *&Buf,
-                                      const char *End) override {
-    using namespace support;
-    if (Buf + sizeof(CovMapHeader) > End)
-      return coveragemap_error::malformed;
-    auto CovHeader = reinterpret_cast<const coverage::CovMapHeader *>(Buf);
-    uint32_t NRecords = CovHeader->getNRecords<Endian>();
-    uint32_t FilenamesSize = CovHeader->getFilenamesSize<Endian>();
-    uint32_t CoverageSize = CovHeader->getCoverageSize<Endian>();
-    assert((CovMapVersion)CovHeader->getVersion<Endian>() == Version);
-    Buf = reinterpret_cast<const char *>(CovHeader + 1);
-
-    // Skip past the function records, saving the start and end for later.
-    const char *FunBuf = Buf;
-    Buf += NRecords * sizeof(FuncRecordType);
-    const char *FunEnd = Buf;
-
-    // Get the filenames.
-    if (Buf + FilenamesSize > End)
-      return coveragemap_error::malformed;
-    size_t FilenamesBegin = Filenames.size();
-    RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames);
-    if (auto Err = Reader.read())
-      return Err;
-    Buf += FilenamesSize;
-
-    // We'll read the coverage mapping records in the loop below.
-    const char *CovBuf = Buf;
-    Buf += CoverageSize;
-    const char *CovEnd = Buf;
-
-    if (Buf > End)
-      return coveragemap_error::malformed;
-    // Each coverage map has an alignment of 8, so we need to adjust alignment
-    // before reading the next map.
-    Buf += alignmentAdjustment(Buf, 8);
-
-    auto CFR = reinterpret_cast<const FuncRecordType *>(FunBuf);
-    while ((const char *)CFR < FunEnd) {
-      // Read the function information
-      uint32_t DataSize = CFR->template getDataSize<Endian>();
-      uint64_t FuncHash = CFR->template getFuncHash<Endian>();
-
-      // Now use that to read the coverage data.
-      if (CovBuf + DataSize > CovEnd)
-        return coveragemap_error::malformed;
-      auto Mapping = StringRef(CovBuf, DataSize);
-      CovBuf += DataSize;
-
-      // Ignore this record if we already have a record that points to the same
-      // function name. This is useful to ignore the redundant records for the
-      // functions with ODR linkage.
-      NameRefType NameRef = CFR->template getFuncNameRef<Endian>();
-      if (!UniqueFunctionMappingData.insert(NameRef).second) {
-        CFR++;
-        continue;
-      }
-
-      StringRef FuncName;
-      if (std::error_code EC =
-              CFR->template getFuncName<Endian>(ProfileNames, FuncName))
-        return EC;
-      Records.push_back(BinaryCoverageReader::ProfileMappingRecord(
-          Version, FuncName, FuncHash, Mapping, FilenamesBegin,
-          Filenames.size() - FilenamesBegin));
-      CFR++;
-    }
-    return std::error_code();
-  }
-};
-} // end anonymous namespace
-
-template <class IntPtrT, support::endianness Endian>
-std::unique_ptr<CovMapFuncRecordReader> CovMapFuncRecordReader::get(
-    coverage::CovMapVersion Version, InstrProfSymtab &P,
-    std::vector<BinaryCoverageReader::ProfileMappingRecord> &R,
-    std::vector<StringRef> &F) {
-  using namespace coverage;
-  switch (Version) {
-  case CovMapVersion::Version1:
-    return llvm::make_unique<VersionedCovMapFuncRecordReader<
-        CovMapVersion::Version1, IntPtrT, Endian>>(P, R, F);
-  case CovMapVersion::Version2:
-    // Decompress the name data.
-    P.create(P.getNameData());
-    return llvm::make_unique<VersionedCovMapFuncRecordReader<
-        CovMapVersion::Version2, IntPtrT, Endian>>(P, R, F);
-  }
-  llvm_unreachable("Unsupported version");
-}
-
-template <typename T, support::endianness Endian>
-static std::error_code readCoverageMappingData(
-    InstrProfSymtab &ProfileNames, StringRef Data,
-    std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records,
-    std::vector<StringRef> &Filenames) {
-  using namespace coverage;
-  // Read the records in the coverage data section.
-  auto CovHeader =
-      reinterpret_cast<const coverage::CovMapHeader *>(Data.data());
-  CovMapVersion Version = (CovMapVersion)CovHeader->getVersion<Endian>();
-  if (Version > coverage::CovMapVersion::CurrentVersion)
-    return coveragemap_error::unsupported_version;
-  std::unique_ptr<CovMapFuncRecordReader> Reader =
-      CovMapFuncRecordReader::get<T, Endian>(Version, ProfileNames, Records,
-                                             Filenames);
-  for (const char *Buf = Data.data(), *End = Buf + Data.size(); Buf < End;) {
-    if (std::error_code EC = Reader->readFunctionRecords(Buf, End))
-      return EC;
-  }
-  return std::error_code();
-}
-static const char *TestingFormatMagic = "llvmcovmtestdata";
-
-static std::error_code loadTestingFormat(StringRef Data,
-                                         InstrProfSymtab &ProfileNames,
-                                         StringRef &CoverageMapping,
-                                         uint8_t &BytesInAddress,
-                                         support::endianness &Endian) {
-  BytesInAddress = 8;
-  Endian = support::endianness::little;
-
-  Data = Data.substr(StringRef(TestingFormatMagic).size());
-  if (Data.size() < 1)
-    return coveragemap_error::truncated;
-  unsigned N = 0;
-  auto ProfileNamesSize =
-      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
-  if (N > Data.size())
-    return coveragemap_error::malformed;
-  Data = Data.substr(N);
-  if (Data.size() < 1)
-    return coveragemap_error::truncated;
-  N = 0;
-  uint64_t Address =
-      decodeULEB128(reinterpret_cast<const uint8_t *>(Data.data()), &N);
-  if (N > Data.size())
-    return coveragemap_error::malformed;
-  Data = Data.substr(N);
-  if (Data.size() < ProfileNamesSize)
-    return coveragemap_error::malformed;
-  ProfileNames.create(Data.substr(0, ProfileNamesSize), Address);
-  CoverageMapping = Data.substr(ProfileNamesSize);
-  return std::error_code();
-}
-
-static ErrorOr<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) {
-  StringRef FoundName;
-  for (const auto &Section : OF.sections()) {
-    if (auto EC = Section.getName(FoundName))
-      return EC;
-    if (FoundName == Name)
-      return Section;
-  }
-  return coveragemap_error::no_data_found;
-}
-
-static std::error_code
-loadBinaryFormat(MemoryBufferRef ObjectBuffer, InstrProfSymtab &ProfileNames,
-                 StringRef &CoverageMapping, uint8_t &BytesInAddress,
-                 support::endianness &Endian, StringRef Arch) {
-  auto BinOrErr = object::createBinary(ObjectBuffer);
-  if (!BinOrErr)
-    return errorToErrorCode(BinOrErr.takeError());
-  auto Bin = std::move(BinOrErr.get());
-  std::unique_ptr<ObjectFile> OF;
-  if (auto *Universal = dyn_cast<object::MachOUniversalBinary>(Bin.get())) {
-    // If we have a universal binary, try to look up the object for the
-    // appropriate architecture.
-    auto ObjectFileOrErr = Universal->getObjectForArch(Arch);
-    if (std::error_code EC = ObjectFileOrErr.getError())
-      return EC;
-    OF = std::move(ObjectFileOrErr.get());
-  } else if (isa<object::ObjectFile>(Bin.get())) {
-    // For any other object file, upcast and take ownership.
-    OF.reset(cast<object::ObjectFile>(Bin.release()));
-    // If we've asked for a particular arch, make sure they match.
-    if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch())
-      return object_error::arch_not_found;
-  } else
-    // We can only handle object files.
-    return coveragemap_error::malformed;
-
-  // The coverage uses native pointer sizes for the object it's written in.
-  BytesInAddress = OF->getBytesInAddress();
-  Endian = OF->isLittleEndian() ? support::endianness::little
-                                : support::endianness::big;
-
-  // Look for the sections that we are interested in.
-  auto NamesSection = lookupSection(*OF, getInstrProfNameSectionName(false));
-  if (auto EC = NamesSection.getError())
-    return EC;
-  auto CoverageSection =
-      lookupSection(*OF, getInstrProfCoverageSectionName(false));
-  if (auto EC = CoverageSection.getError())
-    return EC;
-
-  // Get the contents of the given sections.
-  if (std::error_code EC = CoverageSection->getContents(CoverageMapping))
-    return EC;
-  if (std::error_code EC = ProfileNames.create(*NamesSection))
-    return EC;
-
-  return std::error_code();
-}
-
-ErrorOr<std::unique_ptr<BinaryCoverageReader>>
-BinaryCoverageReader::create(std::unique_ptr<MemoryBuffer> &ObjectBuffer,
-                             StringRef Arch) {
-  std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader());
-
-  StringRef Coverage;
-  uint8_t BytesInAddress;
-  support::endianness Endian;
-  std::error_code EC;
-  if (ObjectBuffer->getBuffer().startswith(TestingFormatMagic))
-    // This is a special format used for testing.
-    EC = loadTestingFormat(ObjectBuffer->getBuffer(), Reader->ProfileNames,
-                           Coverage, BytesInAddress, Endian);
-  else
-    EC = loadBinaryFormat(ObjectBuffer->getMemBufferRef(), Reader->ProfileNames,
-                          Coverage, BytesInAddress, Endian, Arch);
-  if (EC)
-    return EC;
-
-  if (BytesInAddress == 4 && Endian == support::endianness::little)
-    EC = readCoverageMappingData<uint32_t, support::endianness::little>(
-        Reader->ProfileNames, Coverage, Reader->MappingRecords,
-        Reader->Filenames);
-  else if (BytesInAddress == 4 && Endian == support::endianness::big)
-    EC = readCoverageMappingData<uint32_t, support::endianness::big>(
-        Reader->ProfileNames, Coverage, Reader->MappingRecords,
-        Reader->Filenames);
-  else if (BytesInAddress == 8 && Endian == support::endianness::little)
-    EC = readCoverageMappingData<uint64_t, support::endianness::little>(
-        Reader->ProfileNames, Coverage, Reader->MappingRecords,
-        Reader->Filenames);
-  else if (BytesInAddress == 8 && Endian == support::endianness::big)
-    EC = readCoverageMappingData<uint64_t, support::endianness::big>(
-        Reader->ProfileNames, Coverage, Reader->MappingRecords,
-        Reader->Filenames);
-  else
-    return coveragemap_error::malformed;
-  if (EC)
-    return EC;
-  return std::move(Reader);
-}
-
-std::error_code
-BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) {
-  if (CurrentRecord >= MappingRecords.size())
-    return coveragemap_error::eof;
-
-  FunctionsFilenames.clear();
-  Expressions.clear();
-  MappingRegions.clear();
-  auto &R = MappingRecords[CurrentRecord];
-  RawCoverageMappingReader Reader(
-      R.CoverageMapping,
-      makeArrayRef(Filenames).slice(R.FilenamesBegin, R.FilenamesSize),
-      FunctionsFilenames, Expressions, MappingRegions);
-  if (auto Err = Reader.read())
-    return Err;
-
-  Record.FunctionName = R.FunctionName;
-  Record.FunctionHash = R.FunctionHash;
-  Record.Filenames = FunctionsFilenames;
-  Record.Expressions = Expressions;
-  Record.MappingRegions = MappingRegions;
-
-  ++CurrentRecord;
-  return std::error_code();
-}

llvm/trunk/lib/ProfileData/CoverageMappingWriter.cpp

-//=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file contains support for writing coverage mapping data for
-// instrumentation based coverage.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/ProfileData/CoverageMappingWriter.h"
-#include "llvm/Support/LEB128.h"
-
-using namespace llvm;
-using namespace coverage;
-
-void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
-  encodeULEB128(Filenames.size(), OS);
-  for (const auto &Filename : Filenames) {
-    encodeULEB128(Filename.size(), OS);
-    OS << Filename;
-  }
-}
-
-namespace {
-/// \brief Gather only the expressions that are used by the mapping
-/// regions in this function.
-class CounterExpressionsMinimizer {
-  ArrayRef<CounterExpression> Expressions;
-  llvm::SmallVector<CounterExpression, 16> UsedExpressions;
-  std::vector<unsigned> AdjustedExpressionIDs;
-
-public:
-  void mark(Counter C) {
-    if (!C.isExpression())
-      return;
-    unsigned ID = C.getExpressionID();
-    AdjustedExpressionIDs[ID] = 1;
-    mark(Expressions[ID].LHS);
-    mark(Expressions[ID].RHS);
-  }
-
-  void gatherUsed(Counter C) {
-    if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
-      return;
-    AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
-    const auto &E = Expressions[C.getExpressionID()];
-    UsedExpressions.push_back(E);
-    gatherUsed(E.LHS);
-    gatherUsed(E.RHS);
-  }
-
-  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
-                              ArrayRef<CounterMappingRegion> MappingRegions)
-      : Expressions(Expressions) {
-    AdjustedExpressionIDs.resize(Expressions.size(), 0);
-    for (const auto &I : MappingRegions)
-      mark(I.Count);
-    for (const auto &I : MappingRegions)
-      gatherUsed(I.Count);
-  }
-
-  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
-
-  /// \brief Adjust the given counter to correctly transition from the old
-  /// expression ids to the new expression ids.
-  Counter adjust(Counter C) const {
-    if (C.isExpression())
-      C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
-    return C;
-  }
-};
-}
-
-/// \brief Encode the counter.
-///
-/// The encoding uses the following format:
-/// Low 2 bits - Tag:
-///   Counter::Zero(0) - A Counter with kind Counter::Zero
-///   Counter::CounterValueReference(1) - A counter with kind
-///     Counter::CounterValueReference
-///   Counter::Expression(2) + CounterExpression::Subtract(0) -
-///     A counter with kind Counter::Expression and an expression
-///     with kind CounterExpression::Subtract
-///   Counter::Expression(2) + CounterExpression::Add(1) -
-///     A counter with kind Counter::Expression and an expression
-///     with kind CounterExpression::Add
-/// Remaining bits - Counter/Expression ID.
-static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
-                              Counter C) {
-  unsigned Tag = unsigned(C.getKind());
-  if (C.isExpression())
-    Tag += Expressions[C.getExpressionID()].Kind;
-  unsigned ID = C.getCounterID();
-  assert(ID <=
-         (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
-  return Tag | (ID << Counter::EncodingTagBits);
-}
-
-static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
-                         raw_ostream &OS) {
-  encodeULEB128(encodeCounter(Expressions, C), OS);
-}
-
-void CoverageMappingWriter::write(raw_ostream &OS) {
-  // Sort the regions in an ascending order by the file id and the starting
-  // location.
-  std::stable_sort(MappingRegions.begin(), MappingRegions.end());
-
-  // Write out the fileid -> filename mapping.
-  encodeULEB128(VirtualFileMapping.size(), OS);
-  for (const auto &FileID : VirtualFileMapping)
-    encodeULEB128(FileID, OS);
-
-  // Write out the expressions.
-  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
-  auto MinExpressions = Minimizer.getExpressions();
-  encodeULEB128(MinExpressions.size(), OS);
-  for (const auto &E : MinExpressions) {
-    writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
-    writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
-  }
-
-  // Write out the mapping regions.
-  // Split the regions into subarrays where each region in a
-  // subarray has a fileID which is the index of that subarray.
-  unsigned PrevLineStart = 0;
-  unsigned CurrentFileID = ~0U;
-  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
-    if (I->FileID != CurrentFileID) {
-      // Ensure that all file ids have at least one mapping region.
-      assert(I->FileID == (CurrentFileID + 1));
-      // Find the number of regions with this file id.
-      unsigned RegionCount = 1;
-      for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
-        ++RegionCount;
-      // Start a new region sub-array.
-      encodeULEB128(RegionCount, OS);
-
-      CurrentFileID = I->FileID;
-      PrevLineStart = 0;
-    }
-    Counter Count = Minimizer.adjust(I->Count);
-    switch (I->Kind) {
-    case CounterMappingRegion::CodeRegion:
-      writeCounter(MinExpressions, Count, OS);
-      break;
-    case CounterMappingRegion::ExpansionRegion: {
-      assert(Count.isZero());
-      assert(I->ExpandedFileID <=
-             (std::numeric_limits<unsigned>::max() >>
-              Counter::EncodingCounterTagAndExpansionRegionTagBits));
-      // Mark an expansion region with a set bit that follows the counter tag,
-      // and pack the expanded file id into the remaining bits.
-      unsigned EncodedTagExpandedFileID =
-          (1 << Counter::EncodingTagBits) |
-          (I->ExpandedFileID
-           << Counter::EncodingCounterTagAndExpansionRegionTagBits);
-      encodeULEB128(EncodedTagExpandedFileID, OS);
-      break;
-    }
-    case CounterMappingRegion::SkippedRegion:
-      assert(Count.isZero());
-      encodeULEB128(unsigned(I->Kind)
-                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
-                    OS);
-      break;
-    }
-    assert(I->LineStart >= PrevLineStart);
-    encodeULEB128(I->LineStart - PrevLineStart, OS);
-    encodeULEB128(I->ColumnStart, OS);
-    assert(I->LineEnd >= I->LineStart);
-    encodeULEB128(I->LineEnd - I->LineStart, OS);
-    encodeULEB128(I->ColumnEnd, OS);
-    PrevLineStart = I->LineStart;
-  }
-  // Ensure that all file ids have at least one mapping region.
-  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
-}

llvm/trunk/lib/ProfileData/LLVMBuild.txt

 ; This is an LLVMBuild description file for the components in this subdirectory.
 ;
 ; For more information on the LLVMBuild system, please see:
 ;
 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
+[common]
+subdirectories = Coverage
+
 [component_0]
 type = Library
 name = ProfileData
 parent = Libraries
-required_libraries = Core Support Object
+required_libraries = Core Support

llvm/trunk/tools/llvm-cov/CMakeLists.txt

-set(LLVM_LINK_COMPONENTS core support object profiledata)
+set(LLVM_LINK_COMPONENTS core support object coverage profiledata)
 
 add_llvm_tool(llvm-cov
   llvm-cov.cpp
   gcov.cpp
   CodeCoverage.cpp
   CoverageFilters.cpp
   CoverageReport.cpp
   CoverageSummaryInfo.cpp
   SourceCoverageView.cpp
   TestingSupport.cpp
   )

llvm/trunk/tools/llvm-cov/CodeCoverage.cpp

 //===- CodeCoverage.cpp - Coverage tool based on profiling instrumentation-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // The 'CodeCoverageTool' class implements a command line tool to analyze and
 // report coverage information using the profiling instrumentation and code
 // coverage mapping.
 //
 //===----------------------------------------------------------------------===//
 
-#include "RenderingSupport.h"
 #include "CoverageFilters.h"
 #include "CoverageReport.h"
 #include "CoverageViewOptions.h"
+#include "RenderingSupport.h"
 #include "SourceCoverageView.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
-#include "llvm/ProfileData/CoverageMapping.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Process.h"

llvm/trunk/tools/llvm-cov/CoverageFilters.h

 //===- CoverageFilters.h - Function coverage mapping filters --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // These classes provide filtering for function coverage mapping records.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_COV_COVERAGEFILTERS_H
 #define LLVM_COV_COVERAGEFILTERS_H
 
-#include "llvm/ProfileData/CoverageMapping.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
 #include <memory>
 #include <vector>
 
 namespace llvm {
 
 /// \brief Matches specific functions that pass the requirement of this filter.
 class CoverageFilter {
 public:

llvm/trunk/tools/llvm-cov/CoverageSummaryInfo.h

 // These structures are used to represent code coverage metrics
 // for functions/files.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_COV_COVERAGESUMMARYINFO_H
 #define LLVM_COV_COVERAGESUMMARYINFO_H
 
-#include "llvm/ProfileData/CoverageMapping.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 /// \brief Provides information about region coverage for a function/file.
 struct RegionCoverageInfo {
   /// \brief The number of regions that were executed at least once.
   size_t Covered;

llvm/trunk/tools/llvm-cov/LLVMBuild.txt

 ;   http://llvm.org/docs/LLVMBuild.html
 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Tool
 name = llvm-cov
 parent = Tools
-required_libraries = ProfileData Support Instrumentation
+required_libraries = Coverage Support Instrumentation

llvm/trunk/tools/llvm-cov/SourceCoverageView.h

 // This class implements rendering for code coverage of source code.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_COV_SOURCECOVERAGEVIEW_H
 #define LLVM_COV_SOURCECOVERAGEVIEW_H
 
 #include "CoverageViewOptions.h"
-#include "llvm/ProfileData/CoverageMapping.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <vector>
 
 namespace llvm {
 
 class SourceCoverageView;
 
 /// \brief A view that represents a macro or include expansion

llvm/trunk/unittests/ProfileData/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Core
+  Coverage
   ProfileData
   Support
   )
 
 add_llvm_unittest(ProfileDataTests
   CoverageMappingTest.cpp
   InstrProfTest.cpp
   SampleProfTest.cpp
   )

llvm/trunk/unittests/ProfileData/CoverageMappingTest.cpp

 //===- unittest/ProfileData/CoverageMappingTest.cpp -------------------------=//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/ProfileData/CoverageMapping.h"
-#include "llvm/ProfileData/CoverageMappingReader.h"
-#include "llvm/ProfileData/CoverageMappingWriter.h"
+#include "llvm/ProfileData/Coverage/CoverageMapping.h"
+#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
+#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/ProfileData/InstrProfWriter.h"
 #include "llvm/Support/raw_ostream.h"
 #include "gtest/gtest.h"
 
 #include <ostream>
 
 using namespace llvm;