Move coverage related code into a separate library.

Differential Revision: http://reviews.llvm.org/D19333

llvm-svn: 268089

5 files changed, 1384 insertions, 0 deletions

diff --git a/llvm/lib/ProfileData/Coverage/CMakeLists.txt b/llvm/lib/ProfileData/Coverage/CMakeLists.txt
new file mode 100644
index 00000000000..035b8fdb8b3
--- /dev/null
+++ b/llvm/lib/ProfileData/Coverage/CMakeLists.txt
@@ -0,0 +1,11 @@
+add_llvm_library(LLVMCoverage
+  CoverageMapping.cpp
+  CoverageMappingWriter.cpp
+  CoverageMappingReader.cpp
+
+  ADDITIONAL_HEADER_DIRS
+  ${LLVM_MAIN_INCLUDE_DIR}/llvm/ProfileData/Coverage
+
+  DEPENDS
+  intrinsics_gen
+  )
diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
new file mode 100644
index 00000000000..5d86f1de3ad
--- /dev/null
+++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
@@ -0,0 +1,548 @@
+//=-- 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;
+}
diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp
new file mode 100644
index 00000000000..78f7186eac8
--- /dev/null
+++ b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp
@@ -0,0 +1,619 @@
+//=-- 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();
+}
diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp
new file mode 100644
index 00000000000..8ff90d62cfd
--- /dev/null
+++ b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp
@@ -0,0 +1,183 @@
+//=-- 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));
+}
diff --git a/llvm/lib/ProfileData/Coverage/LLVMBuild.txt b/llvm/lib/ProfileData/Coverage/LLVMBuild.txt
new file mode 100644
index 00000000000..fc8284b0ef3
--- /dev/null
+++ b/llvm/lib/ProfileData/Coverage/LLVMBuild.txt
@@ -0,0 +1,23 @@
+;===- ./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
+