Index: include/llvm/ProfileData/CoverageMapping.h =================================================================== --- /dev/null +++ include/llvm/ProfileData/CoverageMapping.h @@ -0,0 +1,198 @@ +//=-- 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/Support/raw_ostream.h" +#include + +namespace llvm { +namespace coverage { + +struct CounterExpressions; + +enum CoverageMappingVersion { CoverageMappingVersion1 }; + +/// \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; } + + bool operator==(const Counter &Other) const { + return Kind == Other.Kind && ID == Other.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) {} + + bool operator==(const CounterExpression &Other) const { + return Kind == Other.Kind && LHS == Other.LHS && RHS == Other.RHS; + } +}; + +/// \brief A Counter expression builder is used to construct the +/// counter expressions. It avoids unecessary duplication +/// and simplifies algebraic expressions. +class CounterExpressionBuilder { + /// \brief A list of all the counter expressions + llvm::SmallVector Expressions; + /// \brief An array of terms used in expression simplification. + llvm::SmallVector Terms; + + /// \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 Convert the expression tree represented by a counter + /// into a polynomial in the form of K1Counter1 + .. + KNCounterN + /// where K1 .. KN are integer constants that are stored in the Terms array. + void extractTerms(Counter C, int Sign = 1); + + /// \brief Simplifies the given expression tree + /// by getting rid of algebraically redundant operations. + Counter simplify(Counter ExpressionTree); + +public: + CounterExpressionBuilder(unsigned NumCounterValues); + + ArrayRef 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 An EmptyRegion represents a source range without code, + /// but with a distinct counter. + EmptyRegion, + + /// \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 LineStart, + unsigned ColumnStart, unsigned LineEnd, + unsigned ColumnEnd, RegionKind Kind = CodeRegion) + : Count(Count), FileID(FileID), ExpandedFileID(0), LineStart(LineStart), + ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd), + Kind(Kind) {} + + bool operator<(const CounterMappingRegion &Other) const { + if (FileID != Other.FileID) + return FileID < Other.FileID; + if (LineStart == Other.LineStart) + return ColumnStart < Other.ColumnStart; + return LineStart < Other.LineStart; + } +}; + +/// \brief A Counter mapping context is used to connect the counters, +/// expressions and the obtained counter values. +class CounterMappingContext { + ArrayRef Expressions; + ArrayRef CounterValues; + +public: + CounterMappingContext(ArrayRef Expressions, + ArrayRef CounterValues = ArrayRef()) + : Expressions(Expressions), CounterValues(CounterValues) {} + + void dump(const Counter &C, llvm::raw_ostream &OS) const; + void dump(const Counter &C) const { dump(C, llvm::outs()); } + + /// \brief Return the number of times that a region of code + /// associated with this counter was executed. + int64_t evaluate(const Counter &C, std::error_code *Error) const; + int64_t evaluate(const Counter &C, std::error_code &Error) const { + Error.clear(); + return evaluate(C, &Error); + } +}; + +} // end namespace coverage +} // end namespace llvm + +#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_ Index: include/llvm/ProfileData/CoverageMappingReader.h =================================================================== --- /dev/null +++ include/llvm/ProfileData/CoverageMappingReader.h @@ -0,0 +1,207 @@ +//=-- 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_COVERAGEMAPPING_READER_H_ +#define LLVM_PROFILEDATA_COVERAGEMAPPING_READER_H_ + +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/ProfileData/CoverageMapping.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/FileSystem.h" + +#include + +namespace llvm { +namespace coverage { + +class ObjectFileCoverageMappingReader; + +/// \brief Coverage mapping information for a single function. +struct CoverageMappingRecord { + StringRef FunctionName; + ArrayRef Filenames; + ArrayRef Expressions; + ArrayRef MappingRegions; +}; + +/// \brief A file format agnostic iterator over coverage mapping data. +class CoverageMappingIterator + : public std::iterator { + ObjectFileCoverageMappingReader *Reader; + CoverageMappingRecord Record; + + void increment(); + +public: + CoverageMappingIterator() : Reader(nullptr) {} + CoverageMappingIterator(ObjectFileCoverageMappingReader *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; } +}; + +/// \brief Base class for the raw coverage mapping and filenames data readers. +class RawCoverageReader { +protected: + StringRef Data; + + /// \brief Return the error code. + std::error_code error(std::error_code EC) { return EC; } + + /// \brief Clear the current error code and return a successful one. + std::error_code success() { return error(instrprof_error::success); } + + 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 &Filenames; + + RawCoverageFilenamesReader(const RawCoverageFilenamesReader &) + LLVM_DELETED_FUNCTION; + RawCoverageFilenamesReader & + operator=(const RawCoverageFilenamesReader &) LLVM_DELETED_FUNCTION; + +public: + RawCoverageFilenamesReader(StringRef Data, std::vector &Filenames) + : RawCoverageReader(Data), Filenames(Filenames) {} + + std::error_code read(); +}; + +/// \brief Reader for the raw coverage mapping data. +class RawCoverageMappingReader : public RawCoverageReader { + StringRef FunctionName; + ArrayRef TranslationUnitFilenames; + std::vector &Filenames; + std::vector &Expressions; + std::vector &MappingRegions; + + RawCoverageMappingReader(const RawCoverageMappingReader &) + LLVM_DELETED_FUNCTION; + RawCoverageMappingReader & + operator=(const RawCoverageMappingReader &) LLVM_DELETED_FUNCTION; + +public: + RawCoverageMappingReader(StringRef FunctionName, StringRef MappingData, + ArrayRef TranslationUnitFilenames, + std::vector &Filenames, + std::vector &Expressions, + std::vector &MappingRegions) + : RawCoverageReader(MappingData), FunctionName(FunctionName), + TranslationUnitFilenames(TranslationUnitFilenames), + Filenames(Filenames), Expressions(Expressions), + MappingRegions(MappingRegions) {} + + std::error_code read(CoverageMappingRecord &Record); + +private: + std::error_code decodeCounter(unsigned Value, Counter &C); + std::error_code readCounter(Counter &C); + std::error_code + readMappingRegionsSubArray(std::vector &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 ObjectFileCoverageMappingReader { +public: + struct ProfileMappingRecord { + CoverageMappingVersion Version; + StringRef FunctionName; + StringRef CoverageMapping; + size_t FilenamesBegin; + size_t FilenamesSize; + + ProfileMappingRecord(CoverageMappingVersion Version, StringRef FunctionName, + StringRef CoverageMapping, size_t FilenamesBegin, + size_t FilenamesSize) + : Version(Version), FunctionName(FunctionName), + CoverageMapping(CoverageMapping), FilenamesBegin(FilenamesBegin), + FilenamesSize(FilenamesSize) {} + }; + +private: + std::error_code LastError; + std::unique_ptr Object; + std::vector Filenames; + std::vector MappingRecords; + size_t CurrentRecord; + std::vector FunctionsFilenames; + std::vector Expressions; + std::vector MappingRegions; + + ObjectFileCoverageMappingReader(const ObjectFileCoverageMappingReader &) + LLVM_DELETED_FUNCTION; + ObjectFileCoverageMappingReader & + operator=(const ObjectFileCoverageMappingReader &) LLVM_DELETED_FUNCTION; + + /// \brief Set the current error_code and return same. + std::error_code error(std::error_code EC) { + LastError = EC; + return EC; + } + + /// \brief Clear the current error code and return a successful one. + std::error_code success() { return error(instrprof_error::success); } + +public: + ObjectFileCoverageMappingReader(StringRef FileName); + ObjectFileCoverageMappingReader( + std::unique_ptr &ObjectBuffer, + sys::fs::file_magic Type = sys::fs::file_magic::unknown); + + std::error_code readHeader(); + std::error_code readNextRecord(CoverageMappingRecord &Record); + + /// Iterator over profile data. + CoverageMappingIterator begin() { return CoverageMappingIterator(this); } + CoverageMappingIterator end() { return CoverageMappingIterator(); } + + /// \brief Return true if the reader has finished reading the profile data. + bool isEOF() { return LastError == instrprof_error::eof; } + /// \brief Return true if the reader encountered an error reading profiling + /// data. + bool hasError() { return LastError && !isEOF(); } + /// \brief Get the current error code. + std::error_code getError() { return LastError; } +}; + +} // end namespace coverage +} // end namespace llvm + +#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_READER_H_ Index: include/llvm/ProfileData/CoverageMappingWriter.h =================================================================== --- /dev/null +++ include/llvm/ProfileData/CoverageMappingWriter.h @@ -0,0 +1,63 @@ +//=-- 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_COVERAGEMAPPING_WRITER_H_ +#define LLVM_PROFILEDATA_COVERAGEMAPPING_WRITER_H_ + +#include "llvm/ProfileData/CoverageMapping.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringMap.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 Filenames; + +public: + CoverageFilenamesSectionWriter(ArrayRef 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 VirtualFileMapping; + ArrayRef Expressions; + MutableArrayRef MappingRegions; + +public: + CoverageMappingWriter(ArrayRef VirtualFileMapping, + ArrayRef Expressions, + MutableArrayRef MappingRegions) + : VirtualFileMapping(VirtualFileMapping), Expressions(Expressions), + MappingRegions(MappingRegions) {} + + CoverageMappingWriter(ArrayRef Expressions, + MutableArrayRef 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_PROFILE_COVERAGEMAPPING_WRITER_H_ Index: lib/ProfileData/CMakeLists.txt =================================================================== --- lib/ProfileData/CMakeLists.txt +++ lib/ProfileData/CMakeLists.txt @@ -2,4 +2,7 @@ InstrProf.cpp InstrProfReader.cpp InstrProfWriter.cpp + CoverageMapping.cpp + CoverageMappingWriter.cpp + CoverageMappingReader.cpp ) Index: lib/ProfileData/CoverageMapping.cpp =================================================================== --- /dev/null +++ lib/ProfileData/CoverageMapping.cpp @@ -0,0 +1,149 @@ +//=-- 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" + +using namespace llvm; +using namespace coverage; + +CounterExpressionBuilder::CounterExpressionBuilder(unsigned NumCounterValues) { + Terms.resize(NumCounterValues); +} + +Counter CounterExpressionBuilder::get(const CounterExpression &E) { + for (unsigned I = 0, S = Expressions.size(); I < S; ++I) { + if (Expressions[I] == E) + return Counter::getExpression(I); + } + Expressions.push_back(E); + return Counter::getExpression(Expressions.size() - 1); +} + +void CounterExpressionBuilder::extractTerms(Counter C, int Sign) { + switch (C.getKind()) { + case Counter::Zero: + break; + case Counter::CounterValueReference: + Terms[C.getCounterID()] += Sign; + break; + case Counter::Expression: + const auto &E = Expressions[C.getExpressionID()]; + extractTerms(E.LHS, Sign); + extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign); + break; + } +} + +Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { + // Gather constant terms. + for (auto &I : Terms) + I = 0; + extractTerms(ExpressionTree); + + Counter C; + // Create additions. + // Note: the additions are created first + // to avoid creation of a tree like ((0 - X) + Y) instead of (Y - X). + for (unsigned I = 0, S = Terms.size(); I < S; ++I) { + if (Terms[I] <= 0) + continue; + for (int J = 0; J < Terms[I]; ++J) { + if (C.isZero()) + C = Counter::getCounter(I); + else + C = get(CounterExpression(CounterExpression::Add, C, + Counter::getCounter(I))); + } + } + + // Create subtractions. + for (unsigned I = 0, S = Terms.size(); I < S; ++I) { + if (Terms[I] >= 0) + continue; + for (int J = 0; J < (-Terms[I]); ++J) + C = get(CounterExpression(CounterExpression::Subtract, C, + Counter::getCounter(I))); + } + 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 << (E.Kind == CounterExpression::Subtract ? " - " : " + "); + dump(E.RHS); + OS << ')'; + break; + } + } + if (CounterValues.empty()) + return; + std::error_code Error; + auto Value = evaluate(C, Error); + if (Error) + return; + OS << '[' << Value << ']'; +} + +int64_t CounterMappingContext::evaluate(const Counter &C, + std::error_code *EC) const { + switch (C.getKind()) { + case Counter::Zero: + return 0; + case Counter::CounterValueReference: + if (C.getCounterID() >= CounterValues.size()) { + if (EC) + *EC = std::make_error_code(std::errc::argument_out_of_domain); + break; + } + return CounterValues[C.getCounterID()]; + case Counter::Expression: { + if (C.getExpressionID() >= Expressions.size()) { + if (EC) + *EC = std::make_error_code(std::errc::argument_out_of_domain); + break; + } + const auto &E = Expressions[C.getExpressionID()]; + auto LHS = evaluate(E.LHS, EC); + if (EC && *EC) + return 0; + auto RHS = evaluate(E.RHS, EC); + if (EC && *EC) + return 0; + return E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS; + } + } + return 0; +} Index: lib/ProfileData/CoverageMappingReader.cpp =================================================================== --- /dev/null +++ lib/ProfileData/CoverageMappingReader.cpp @@ -0,0 +1,482 @@ +//=-- 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/ObjectFile.h" +#include "llvm/Support/LEB128.h" + +using namespace llvm; +using namespace coverage; +using namespace object; + +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 error(instrprof_error::truncated); + unsigned N = 0; + Result = decodeULEB128(reinterpret_cast(Data.data()), &N); + if (N > Data.size()) + return error(instrprof_error::malformed); + Data = Data.substr(N); + return success(); +} + +std::error_code RawCoverageReader::readIntMax(uint64_t &Result, + uint64_t MaxPlus1) { + if (auto Err = readULEB128(Result)) + return Err; + if (Result >= MaxPlus1) + return error(instrprof_error::malformed); + return success(); +} + +std::error_code RawCoverageReader::readSize(uint64_t &Result) { + if (auto Err = readULEB128(Result)) + return Err; + // Sanity check the number. + if (Result > Data.size()) + return error(instrprof_error::malformed); + return success(); +} + +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 success(); +} + +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 success(); +} + +std::error_code RawCoverageMappingReader::decodeCounter(unsigned Value, + Counter &C) { + auto Tag = Value & Counter::EncodingTagMask; + switch (Tag) { + case Counter::Zero: + C = Counter::getZero(); + return success(); + case Counter::CounterValueReference: + C = Counter::getCounter(Value >> Counter::EncodingTagBits); + return success(); + default: + break; + } + Tag -= Counter::Expression; + switch (Tag) { + case CounterExpression::Subtract: + case CounterExpression::Add: { + auto ID = Value >> Counter::EncodingTagBits; + if (ID >= Expressions.size()) + return error(instrprof_error::malformed); + Expressions[ID].Kind = CounterExpression::ExprKind(Tag); + C = Counter::getExpression(ID); + break; + } + default: + return error(instrprof_error::malformed); + } + return success(); +} + +std::error_code RawCoverageMappingReader::readCounter(Counter &C) { + uint64_t EncodedCounter; + if (auto Err = + readIntMax(EncodedCounter, std::numeric_limits::max())) + return Err; + if (auto Err = decodeCounter(EncodedCounter, C)) + return Err; + return success(); +} + +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 &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::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 error(instrprof_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::EmptyRegion: + Kind = CounterMappingRegion::EmptyRegion; + break; + case CounterMappingRegion::SkippedRegion: + Kind = CounterMappingRegion::SkippedRegion; + break; + default: + return error(instrprof_error::malformed); + } + } + } + + // Read the source range. + uint64_t LineStartDelta, ColumnStart, NumLines, ColumnEnd; + if (auto Err = + readIntMax(LineStartDelta, std::numeric_limits::max())) + return Err; + if (auto Err = + readIntMax(ColumnStart, std::numeric_limits::max())) + return Err; + if (auto Err = readIntMax(NumLines, std::numeric_limits::max())) + return Err; + if (auto Err = readIntMax(ColumnEnd, std::numeric_limits::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::max()), but because + // the encoded std::numeric_limits::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::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::max(); + } + MappingRegions.push_back( + CounterMappingRegion(C, InferredFileID, LineStart, ColumnStart, + LineStart + NumLines, ColumnEnd, Kind)); + MappingRegions.back().ExpandedFileID = ExpandedFileID; + } + return success(); +} + +std::error_code RawCoverageMappingReader::read(CoverageMappingRecord &Record) { + + // Read the virtual file mapping. + llvm::SmallVector 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. + for (unsigned Pass = 1, S = VirtualFileMapping.size(); Pass < S; ++Pass) { + for (auto &I : MappingRegions) { + if (I.Kind == CounterMappingRegion::ExpansionRegion) { + for (const auto &J : MappingRegions) { + if (J.FileID == I.ExpandedFileID) { + I.Count = J.Count; + break; + } + } + } + } + } + + Record.FunctionName = FunctionName; + Record.Filenames = Filenames; + Record.Expressions = Expressions; + Record.MappingRegions = MappingRegions; + return success(); +} + +ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader( + StringRef FileName) + : CurrentRecord(0) { + auto File = llvm::object::ObjectFile::createObjectFile(FileName); + if (!File) + error(File.getError()); + else + Object.reset(File.get()); +} + +ObjectFileCoverageMappingReader::ObjectFileCoverageMappingReader( + std::unique_ptr &ObjectBuffer, sys::fs::file_magic Type) + : CurrentRecord(0) { + auto File = llvm::object::ObjectFile::createObjectFile(ObjectBuffer, Type); + if (!File) + error(File.getError()); + else + Object.reset(File.get()); +} + +namespace { +/// \brief The coverage mapping data for a single function. +/// It points to the function's name. +template struct CoverageMappingFunctionRecord { + IntPtrT FunctionNamePtr; + uint32_t FunctionNameSize; + uint32_t CoverageMappingSize; +}; + +/// \brief The coverage mapping data for a single translation unit. +/// It points to the array of function coverage mapping records and the encoded +/// filenames array. +template struct CoverageMappingTURecord { + uint32_t FunctionRecordsSize; + uint32_t FilenamesSize; + uint32_t CoverageMappingsSize; + uint32_t Version; +}; + +/// \brief A helper structure to access the data from a section +/// in an object file. +struct SectionData { + StringRef Data; + uint64_t Address; + + std::error_code load(SectionRef &Section) { + if (auto Err = Section.getContents(Data)) + return Err; + return Section.getAddress(Address); + } + + std::error_code get(uint64_t Pointer, size_t Size, StringRef &Result) { + if (Pointer < Address) + return instrprof_error::malformed; + auto Offset = Pointer - Address; + if (Offset + Size > Data.size()) + return instrprof_error::malformed; + Result = Data.substr(Pointer - Address, Size); + return instrprof_error::success; + } +}; +} + +template +std::error_code readCoverageMappingData( + SectionRef &ProfileNames, SectionRef &CoverageMapping, + std::vector &Records, + std::vector &Filenames) { + llvm::DenseSet UniqueFunctionMappingData; + + // Get the contents of the given sections. + StringRef Data; + if (auto Err = CoverageMapping.getContents(Data)) + return Err; + SectionData ProfileNamesData; + if (auto Err = ProfileNamesData.load(ProfileNames)) + return Err; + + // Read the records in the coverage data section. + while (!Data.empty()) { + if (Data.size() < sizeof(CoverageMappingTURecord)) + return instrprof_error::malformed; + auto TU = reinterpret_cast *>(Data.data()); + Data = Data.substr(sizeof(CoverageMappingTURecord)); + switch (TU->Version) { + case CoverageMappingVersion1: + break; + default: + return instrprof_error::unsupported_version; + } + auto Version = CoverageMappingVersion(TU->Version); + + // Get the function records. + auto FunctionRecords = + reinterpret_cast *>(Data.data()); + if (Data.size() < + sizeof(CoverageMappingFunctionRecord) * TU->FunctionRecordsSize) + return instrprof_error::malformed; + Data = Data.substr(sizeof(CoverageMappingFunctionRecord) * + TU->FunctionRecordsSize); + + // Get the filenames. + if (Data.size() < TU->FilenamesSize) + return instrprof_error::malformed; + auto RawFilenames = Data.substr(0, TU->FilenamesSize); + Data = Data.substr(TU->FilenamesSize); + size_t FilenamesBegin = Filenames.size(); + RawCoverageFilenamesReader Reader(RawFilenames, Filenames); + if (auto Err = Reader.read()) + return Err; + + // Get the coverage mappings. + if (Data.size() < TU->CoverageMappingsSize) + return instrprof_error::malformed; + auto CoverageMappings = Data.substr(0, TU->CoverageMappingsSize); + Data = Data.substr(TU->CoverageMappingsSize); + + for (unsigned I = 0; I < TU->FunctionRecordsSize; ++I) { + auto &MappingRecord = FunctionRecords[I]; + + // Get the coverage mapping. + if (CoverageMappings.size() < MappingRecord.CoverageMappingSize) + return instrprof_error::malformed; + auto Mapping = + CoverageMappings.substr(0, MappingRecord.CoverageMappingSize); + CoverageMappings = + CoverageMappings.substr(MappingRecord.CoverageMappingSize); + + // 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. + if (UniqueFunctionMappingData.count(MappingRecord.FunctionNamePtr)) + continue; + UniqueFunctionMappingData.insert(MappingRecord.FunctionNamePtr); + StringRef FunctionName; + if (auto Err = ProfileNamesData.get(MappingRecord.FunctionNamePtr, + MappingRecord.FunctionNameSize, + FunctionName)) + return Err; + Records.push_back(ObjectFileCoverageMappingReader::ProfileMappingRecord( + Version, FunctionName, Mapping, FilenamesBegin, + Filenames.size() - FilenamesBegin)); + } + } + + return instrprof_error::success; +} + +std::error_code ObjectFileCoverageMappingReader::readHeader() { + if (!Object) + return getError(); + auto BytesInAddress = Object->getBytesInAddress(); + if (BytesInAddress != 4 && BytesInAddress != 8) + return error(instrprof_error::malformed); + + // Look for the sections that we are interested in. + int FoundSectionCount = 0; + SectionRef ProfileNames, CoverageMapping; + for (const auto &Section : Object->sections()) { + StringRef Name; + if (auto Err = Section.getName(Name)) + return Err; + if (Name == "__llvm_prf_names") { + ProfileNames = Section; + } else if (Name == "__llvm_covmap") { + CoverageMapping = Section; + } else + continue; + ++FoundSectionCount; + } + if (FoundSectionCount != 2) + return error(instrprof_error::bad_header); + + // Load the data from the found sections. + std::error_code Err; + if (BytesInAddress == 4) + Err = readCoverageMappingData(ProfileNames, CoverageMapping, + MappingRecords, Filenames); + else + Err = readCoverageMappingData(ProfileNames, CoverageMapping, + MappingRecords, Filenames); + if (Err) + return error(Err); + + return success(); +} + +std::error_code +ObjectFileCoverageMappingReader::readNextRecord(CoverageMappingRecord &Record) { + if (CurrentRecord >= MappingRecords.size()) + return error(instrprof_error::eof); + + FunctionsFilenames.clear(); + Expressions.clear(); + MappingRegions.clear(); + auto &R = MappingRecords[CurrentRecord]; + RawCoverageMappingReader Reader( + R.FunctionName, R.CoverageMapping, + makeArrayRef(Filenames.data() + R.FilenamesBegin, R.FilenamesSize), + FunctionsFilenames, Expressions, MappingRegions); + if (auto Err = Reader.read(Record)) + return Err; + ++CurrentRecord; + return success(); +} Index: lib/ProfileData/CoverageMappingWriter.cpp =================================================================== --- /dev/null +++ lib/ProfileData/CoverageMappingWriter.cpp @@ -0,0 +1,197 @@ +//=-- 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 Expressions; + llvm::SmallVector UsedExpressions; + std::vector 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 Expressions, + ArrayRef 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 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 Return the number of regions that have the given FileID. +static unsigned countFileIDs(ArrayRef Regions, + unsigned FileID) { + unsigned Result = 0; + for (const auto &I : Regions) { + if (I.FileID == FileID) + ++Result; + if (I.FileID > FileID) + break; + } + return Result; +} + +/// \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. +unsigned encodeCounter(ArrayRef 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::max() >> Counter::EncodingTagBits)); + return Tag | (ID << Counter::EncodingTagBits); +} + +static void writeCounter(ArrayRef 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::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 = MappingRegions.front().FileID; + assert(CurrentFileID == 0); + encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS); + for (const auto &I : MappingRegions) { + if (I.FileID != CurrentFileID) { + // Ensure that all file ids have at least one mapping region. + assert(I.FileID == (CurrentFileID + 1)); + // Start a new region sub-array. + CurrentFileID = I.FileID; + encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS); + 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::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::EmptyRegion: + encodeULEB128(unsigned(I.Kind) + << Counter::EncodingCounterTagAndExpansionRegionTagBits, + 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)); +} Index: lib/ProfileData/LLVMBuild.txt =================================================================== --- lib/ProfileData/LLVMBuild.txt +++ lib/ProfileData/LLVMBuild.txt @@ -19,4 +19,4 @@ type = Library name = ProfileData parent = Libraries -required_libraries = Support +required_libraries = Support Object