diff options
Diffstat (limited to 'llvm/lib/ProfileData/Coverage')
| -rw-r--r-- | llvm/lib/ProfileData/Coverage/CoverageMapping.cpp | 835 | ||||
| -rw-r--r-- | llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp | 831 | ||||
| -rw-r--r-- | llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp | 216 |
3 files changed, 1882 insertions, 0 deletions
diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp new file mode 100644 index 000000000000..8d5e56e26c0f --- /dev/null +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -0,0 +1,835 @@ +//===- CoverageMapping.cpp - Code coverage mapping support ----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains support for clang's and llvm's instrumentation based +// code coverage. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ProfileData/Coverage/CoverageMapping.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallBitVector.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.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/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/ManagedStatic.h" +#include "llvm/Support/MemoryBuffer.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cstdint> +#include <iterator> +#include <map> +#include <memory> +#include <string> +#include <system_error> +#include <utility> +#include <vector> + +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 Factor, + SmallVectorImpl<Term> &Terms) { + switch (C.getKind()) { + case Counter::Zero: + break; + case Counter::CounterValueReference: + Terms.emplace_back(C.getCounterID(), Factor); + break; + case Counter::Expression: + const auto &E = Expressions[C.getExpressionID()]; + extractTerms(E.LHS, Factor, Terms); + extractTerms( + E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); + break; + } +} + +Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { + // Gather constant terms. + SmallVector<Term, 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. + llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { + return LHS.CounterID < RHS.CounterID; + }); + + // 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->CounterID == Prev->CounterID) { + Prev->Factor += I->Factor; + 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 T : Terms) { + if (T.Factor <= 0) + continue; + for (int I = 0; I < T.Factor; ++I) + if (C.isZero()) + C = Counter::getCounter(T.CounterID); + else + C = get(CounterExpression(CounterExpression::Add, C, + Counter::getCounter(T.CounterID))); + } + + // Create subtractions. + for (auto T : Terms) { + if (T.Factor >= 0) + continue; + for (int I = 0; I < -T.Factor; ++I) + C = get(CounterExpression(CounterExpression::Subtract, C, + Counter::getCounter(T.CounterID))); + } + 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, 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; + Expected<int64_t> Value = evaluate(C); + if (auto E = Value.takeError()) { + consumeError(std::move(E)); + return; + } + OS << '[' << *Value << ']'; +} + +Expected<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 errorCodeToError(errc::argument_out_of_domain); + return CounterValues[C.getCounterID()]; + case Counter::Expression: { + if (C.getExpressionID() >= Expressions.size()) + return errorCodeToError(errc::argument_out_of_domain); + const auto &E = Expressions[C.getExpressionID()]; + Expected<int64_t> LHS = evaluate(E.LHS); + if (!LHS) + return LHS; + Expected<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(); +} + +ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename( + StringRef Filename) const { + size_t FilenameHash = hash_value(Filename); + auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash); + if (RecordIt == FilenameHash2RecordIndices.end()) + return {}; + return RecordIt->second; +} + +Error CoverageMapping::loadFunctionRecord( + const CoverageMappingRecord &Record, + IndexedInstrProfReader &ProfileReader) { + StringRef OrigFuncName = Record.FunctionName; + if (OrigFuncName.empty()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + + if (Record.Filenames.empty()) + OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); + else + OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); + + CounterMappingContext Ctx(Record.Expressions); + + std::vector<uint64_t> Counts; + if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, + Record.FunctionHash, Counts)) { + instrprof_error IPE = InstrProfError::take(std::move(E)); + if (IPE == instrprof_error::hash_mismatch) { + FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash); + return Error::success(); + } else if (IPE != instrprof_error::unknown_function) + return make_error<InstrProfError>(IPE); + Counts.assign(Record.MappingRegions.size(), 0); + } + Ctx.setCounts(Counts); + + assert(!Record.MappingRegions.empty() && "Function has no regions"); + + // This coverage record is a zero region for a function that's unused in + // some TU, but used in a different TU. Ignore it. The coverage maps from the + // the other TU will either be loaded (providing full region counts) or they + // won't (in which case we don't unintuitively report functions as uncovered + // when they have non-zero counts in the profile). + if (Record.MappingRegions.size() == 1 && + Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) + return Error::success(); + + FunctionRecord Function(OrigFuncName, Record.Filenames); + for (const auto &Region : Record.MappingRegions) { + Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); + if (auto E = ExecutionCount.takeError()) { + consumeError(std::move(E)); + return Error::success(); + } + Function.pushRegion(Region, *ExecutionCount); + } + + // Don't create records for (filenames, function) pairs we've already seen. + auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), + Record.Filenames.end()); + if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) + return Error::success(); + + Functions.push_back(std::move(Function)); + + // Performance optimization: keep track of the indices of the function records + // which correspond to each filename. This can be used to substantially speed + // up queries for coverage info in a file. + unsigned RecordIndex = Functions.size() - 1; + for (StringRef Filename : Record.Filenames) { + auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)]; + // Note that there may be duplicates in the filename set for a function + // record, because of e.g. macro expansions in the function in which both + // the macro and the function are defined in the same file. + if (RecordIndices.empty() || RecordIndices.back() != RecordIndex) + RecordIndices.push_back(RecordIndex); + } + + return Error::success(); +} + +Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( + ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, + IndexedInstrProfReader &ProfileReader) { + auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); + + for (const auto &CoverageReader : CoverageReaders) { + for (auto RecordOrErr : *CoverageReader) { + if (Error E = RecordOrErr.takeError()) + return std::move(E); + const auto &Record = *RecordOrErr; + if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader)) + return std::move(E); + } + } + + return std::move(Coverage); +} + +// If E is a no_data_found error, returns success. Otherwise returns E. +static Error handleMaybeNoDataFoundError(Error E) { + return handleErrors( + std::move(E), [](const CoverageMapError &CME) { + if (CME.get() == coveragemap_error::no_data_found) + return static_cast<Error>(Error::success()); + return make_error<CoverageMapError>(CME.get()); + }); +} + +Expected<std::unique_ptr<CoverageMapping>> +CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, + StringRef ProfileFilename, ArrayRef<StringRef> Arches) { + auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); + if (Error E = ProfileReaderOrErr.takeError()) + return std::move(E); + auto ProfileReader = std::move(ProfileReaderOrErr.get()); + + SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; + SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; + for (const auto &File : llvm::enumerate(ObjectFilenames)) { + auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value()); + if (std::error_code EC = CovMappingBufOrErr.getError()) + return errorCodeToError(EC); + StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()]; + MemoryBufferRef CovMappingBufRef = + CovMappingBufOrErr.get()->getMemBufferRef(); + auto CoverageReadersOrErr = + BinaryCoverageReader::create(CovMappingBufRef, Arch, Buffers); + if (Error E = CoverageReadersOrErr.takeError()) { + E = handleMaybeNoDataFoundError(std::move(E)); + if (E) + return std::move(E); + // E == success (originally a no_data_found error). + continue; + } + for (auto &Reader : CoverageReadersOrErr.get()) + Readers.push_back(std::move(Reader)); + Buffers.push_back(std::move(CovMappingBufOrErr.get())); + } + // If no readers were created, either no objects were provided or none of them + // had coverage data. Return an error in the latter case. + if (Readers.empty() && !ObjectFilenames.empty()) + return make_error<CoverageMapError>(coveragemap_error::no_data_found); + return load(Readers, *ProfileReader); +} + +namespace { + +/// 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 { + using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; + 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) {} + + /// Emit a segment with the count from \p Region starting at \p StartLoc. + // + /// \p IsRegionEntry: The segment is at the start of a new non-gap region. + /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. + void startSegment(const CountedRegion &Region, LineColPair StartLoc, + bool IsRegionEntry, bool EmitSkippedRegion = false) { + bool HasCount = !EmitSkippedRegion && + (Region.Kind != CounterMappingRegion::SkippedRegion); + + // If the new segment wouldn't affect coverage rendering, skip it. + if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { + const auto &Last = Segments.back(); + if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && + !Last.IsRegionEntry) + return; + } + + if (HasCount) + Segments.emplace_back(StartLoc.first, StartLoc.second, + Region.ExecutionCount, IsRegionEntry, + Region.Kind == CounterMappingRegion::GapRegion); + else + Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); + + LLVM_DEBUG({ + const auto &Last = Segments.back(); + dbgs() << "Segment at " << Last.Line << ":" << Last.Col + << " (count = " << Last.Count << ")" + << (Last.IsRegionEntry ? ", RegionEntry" : "") + << (!Last.HasCount ? ", Skipped" : "") + << (Last.IsGapRegion ? ", Gap" : "") << "\n"; + }); + } + + /// Emit segments for active regions which end before \p Loc. + /// + /// \p Loc: The start location of the next region. If None, all active + /// regions are completed. + /// \p FirstCompletedRegion: Index of the first completed region. + void completeRegionsUntil(Optional<LineColPair> Loc, + unsigned FirstCompletedRegion) { + // Sort the completed regions by end location. This makes it simple to + // emit closing segments in sorted order. + auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; + std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), + [](const CountedRegion *L, const CountedRegion *R) { + return L->endLoc() < R->endLoc(); + }); + + // Emit segments for all completed regions. + for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; + ++I) { + const auto *CompletedRegion = ActiveRegions[I]; + assert((!Loc || CompletedRegion->endLoc() <= *Loc) && + "Completed region ends after start of new region"); + + const auto *PrevCompletedRegion = ActiveRegions[I - 1]; + auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); + + // Don't emit any more segments if they start where the new region begins. + if (Loc && CompletedSegmentLoc == *Loc) + break; + + // Don't emit a segment if the next completed region ends at the same + // location as this one. + if (CompletedSegmentLoc == CompletedRegion->endLoc()) + continue; + + // Use the count from the last completed region which ends at this loc. + for (unsigned J = I + 1; J < E; ++J) + if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) + CompletedRegion = ActiveRegions[J]; + + startSegment(*CompletedRegion, CompletedSegmentLoc, false); + } + + auto Last = ActiveRegions.back(); + if (FirstCompletedRegion && Last->endLoc() != *Loc) { + // If there's a gap after the end of the last completed region and the + // start of the new region, use the last active region to fill the gap. + startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), + false); + } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { + // Emit a skipped segment if there are no more active regions. This + // ensures that gaps between functions are marked correctly. + startSegment(*Last, Last->endLoc(), false, true); + } + + // Pop the completed regions. + ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); + } + + void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { + for (const auto &CR : enumerate(Regions)) { + auto CurStartLoc = CR.value().startLoc(); + + // Active regions which end before the current region need to be popped. + auto CompletedRegions = + std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), + [&](const CountedRegion *Region) { + return !(Region->endLoc() <= CurStartLoc); + }); + if (CompletedRegions != ActiveRegions.end()) { + unsigned FirstCompletedRegion = + std::distance(ActiveRegions.begin(), CompletedRegions); + completeRegionsUntil(CurStartLoc, FirstCompletedRegion); + } + + bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; + + // Try to emit a segment for the current region. + if (CurStartLoc == CR.value().endLoc()) { + // Avoid making zero-length regions active. If it's the last region, + // emit a skipped segment. Otherwise use its predecessor's count. + const bool Skipped = (CR.index() + 1) == Regions.size(); + startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), + CurStartLoc, !GapRegion, Skipped); + continue; + } + if (CR.index() + 1 == Regions.size() || + CurStartLoc != Regions[CR.index() + 1].startLoc()) { + // Emit a segment if the next region doesn't start at the same location + // as this one. + startSegment(CR.value(), CurStartLoc, !GapRegion); + } + + // This region is active (i.e not completed). + ActiveRegions.push_back(&CR.value()); + } + + // Complete any remaining active regions. + if (!ActiveRegions.empty()) + completeRegionsUntil(None, 0); + } + + /// Sort a nested sequence of regions from a single file. + static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { + llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { + if (LHS.startLoc() != RHS.startLoc()) + return LHS.startLoc() < RHS.startLoc(); + if (LHS.endLoc() != RHS.endLoc()) + // When LHS completely contains RHS, we sort LHS first. + return RHS.endLoc() < LHS.endLoc(); + // If LHS and RHS cover the same area, we need to sort them according + // to their kinds so that the most suitable region will become "active" + // in combineRegions(). Because we accumulate counter values only from + // regions of the same kind as the first region of the area, prefer + // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. + static_assert(CounterMappingRegion::CodeRegion < + CounterMappingRegion::ExpansionRegion && + CounterMappingRegion::ExpansionRegion < + CounterMappingRegion::SkippedRegion, + "Unexpected order of region kind values"); + return LHS.Kind < RHS.Kind; + }); + } + + /// 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 CodeRegions and ExpansionRegions cover the same area, it's probably + // a macro which is fully expanded to another macro. In that case, we need + // to accumulate counts only from CodeRegions, or else the area will be + // counted twice. + // On the other hand, a macro may have a nested macro in its body. If the + // outer macro is used several times, the ExpansionRegion for the nested + // macro will also be added several times. These ExpansionRegions cover + // the same source locations and have to be combined to reach the correct + // value for that area. + // We add counts of the regions of the same kind as the active region + // to handle the both situations. + if (I->Kind == Active->Kind) + Active->ExecutionCount += I->ExecutionCount; + } + return Regions.drop_back(std::distance(++Active, End)); + } + +public: + /// Build a sorted 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); + + LLVM_DEBUG({ + dbgs() << "Combined regions:\n"; + for (const auto &CR : CombinedRegions) + dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " + << CR.LineEnd << ":" << CR.ColumnEnd + << " (count=" << CR.ExecutionCount << ")\n"; + }); + + Builder.buildSegmentsImpl(CombinedRegions); + +#ifndef NDEBUG + for (unsigned I = 1, E = Segments.size(); I < E; ++I) { + const auto &L = Segments[I - 1]; + const auto &R = Segments[I]; + if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { + LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col + << " followed by " << R.Line << ":" << R.Col << "\n"); + assert(false && "Coverage segments not unique or sorted"); + } + } +#endif + + return Segments; + } +}; + +} // end anonymous namespace + +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()); + llvm::sort(Filenames); + 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) const { + CoverageData FileCoverage(Filename); + std::vector<CountedRegion> Regions; + + // Look up the function records in the given file. Due to hash collisions on + // the filename, we may get back some records that are not in the file. + ArrayRef<unsigned> RecordIndices = + getImpreciseRecordIndicesForFilename(Filename); + for (unsigned RecordIndex : RecordIndices) { + const FunctionRecord &Function = Functions[RecordIndex]; + 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); + } + } + + LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); + FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return FileCoverage; +} + +std::vector<InstantiationGroup> +CoverageMapping::getInstantiationGroups(StringRef Filename) const { + FunctionInstantiationSetCollector InstantiationSetCollector; + // Look up the function records in the given file. Due to hash collisions on + // the filename, we may get back some records that are not in the file. + ArrayRef<unsigned> RecordIndices = + getImpreciseRecordIndicesForFilename(Filename); + for (unsigned RecordIndex : RecordIndices) { + const FunctionRecord &Function = Functions[RecordIndex]; + auto MainFileID = findMainViewFileID(Filename, Function); + if (!MainFileID) + continue; + InstantiationSetCollector.insert(Function, *MainFileID); + } + + std::vector<InstantiationGroup> Result; + for (auto &InstantiationSet : InstantiationSetCollector) { + InstantiationGroup IG{InstantiationSet.first.first, + InstantiationSet.first.second, + std::move(InstantiationSet.second)}; + Result.emplace_back(std::move(IG)); + } + return Result; +} + +CoverageData +CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { + auto MainFileID = findMainViewFileID(Function); + if (!MainFileID) + return CoverageData(); + + CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); + std::vector<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); + } + + LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name + << "\n"); + FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return FunctionCoverage; +} + +CoverageData CoverageMapping::getCoverageForExpansion( + const ExpansionRecord &Expansion) const { + CoverageData ExpansionCoverage( + Expansion.Function.Filenames[Expansion.FileID]); + std::vector<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); + } + + LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " + << Expansion.FileID << "\n"); + ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); + + return ExpansionCoverage; +} + +LineCoverageStats::LineCoverageStats( + ArrayRef<const CoverageSegment *> LineSegments, + const CoverageSegment *WrappedSegment, unsigned Line) + : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), + LineSegments(LineSegments), WrappedSegment(WrappedSegment) { + // Find the minimum number of regions which start in this line. + unsigned MinRegionCount = 0; + auto isStartOfRegion = [](const CoverageSegment *S) { + return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; + }; + for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) + if (isStartOfRegion(LineSegments[I])) + ++MinRegionCount; + + bool StartOfSkippedRegion = !LineSegments.empty() && + !LineSegments.front()->HasCount && + LineSegments.front()->IsRegionEntry; + + HasMultipleRegions = MinRegionCount > 1; + Mapped = + !StartOfSkippedRegion && + ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); + + if (!Mapped) + return; + + // Pick the max count from the non-gap, region entry segments and the + // wrapped count. + if (WrappedSegment) + ExecutionCount = WrappedSegment->Count; + if (!MinRegionCount) + return; + for (const auto *LS : LineSegments) + if (isStartOfRegion(LS)) + ExecutionCount = std::max(ExecutionCount, LS->Count); +} + +LineCoverageIterator &LineCoverageIterator::operator++() { + if (Next == CD.end()) { + Stats = LineCoverageStats(); + Ended = true; + return *this; + } + if (Segments.size()) + WrappedSegment = Segments.back(); + Segments.clear(); + while (Next != CD.end() && Next->Line == Line) + Segments.push_back(&*Next++); + Stats = LineCoverageStats(Segments, WrappedSegment, Line); + ++Line; + return *this; +} + +static std::string getCoverageMapErrString(coveragemap_error Err) { + switch (Err) { + 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."); +} + +namespace { + +// FIXME: This class is only here to support the transition to llvm::Error. It +// will be removed once this transition is complete. Clients should prefer to +// deal with the Error value directly, rather than converting to error_code. +class CoverageMappingErrorCategoryType : public std::error_category { + const char *name() const noexcept override { return "llvm.coveragemap"; } + std::string message(int IE) const override { + return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); + } +}; + +} // end anonymous namespace + +std::string CoverageMapError::message() const { + return getCoverageMapErrString(Err); +} + +static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory; + +const std::error_category &llvm::coverage::coveragemap_category() { + return *ErrorCategory; +} + +char CoverageMapError::ID = 0; diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp new file mode 100644 index 000000000000..679ff3525eeb --- /dev/null +++ b/llvm/lib/ProfileData/Coverage/CoverageMappingReader.cpp @@ -0,0 +1,831 @@ +//===- CoverageMappingReader.cpp - Code coverage mapping reader -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains support for reading coverage mapping data for +// instrumentation based coverage. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ProfileData/Coverage/CoverageMappingReader.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/Triple.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/Error.h" +#include "llvm/Object/MachOUniversal.h" +#include "llvm/Object/ObjectFile.h" +#include "llvm/Object/COFF.h" +#include "llvm/ProfileData/InstrProf.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Endian.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/LEB128.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include <vector> + +using namespace llvm; +using namespace coverage; +using namespace object; + +#define DEBUG_TYPE "coverage-mapping" + +void CoverageMappingIterator::increment() { + if (ReadErr != coveragemap_error::success) + return; + + // Check if all the records were read or if an error occurred while reading + // the next record. + if (auto E = Reader->readNextRecord(Record)) + handleAllErrors(std::move(E), [&](const CoverageMapError &CME) { + if (CME.get() == coveragemap_error::eof) + *this = CoverageMappingIterator(); + else + ReadErr = CME.get(); + }); +} + +Error RawCoverageReader::readULEB128(uint64_t &Result) { + if (Data.empty()) + return make_error<CoverageMapError>(coveragemap_error::truncated); + unsigned N = 0; + Result = decodeULEB128(Data.bytes_begin(), &N); + if (N > Data.size()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + Data = Data.substr(N); + return Error::success(); +} + +Error RawCoverageReader::readIntMax(uint64_t &Result, uint64_t MaxPlus1) { + if (auto Err = readULEB128(Result)) + return Err; + if (Result >= MaxPlus1) + return make_error<CoverageMapError>(coveragemap_error::malformed); + return Error::success(); +} + +Error RawCoverageReader::readSize(uint64_t &Result) { + if (auto Err = readULEB128(Result)) + return Err; + // Sanity check the number. + if (Result > Data.size()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + return Error::success(); +} + +Error RawCoverageReader::readString(StringRef &Result) { + uint64_t Length; + if (auto Err = readSize(Length)) + return Err; + Result = Data.substr(0, Length); + Data = Data.substr(Length); + return Error::success(); +} + +Error 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 Error::success(); +} + +Error RawCoverageMappingReader::decodeCounter(unsigned Value, Counter &C) { + auto Tag = Value & Counter::EncodingTagMask; + switch (Tag) { + case Counter::Zero: + C = Counter::getZero(); + return Error::success(); + case Counter::CounterValueReference: + C = Counter::getCounter(Value >> Counter::EncodingTagBits); + return Error::success(); + default: + break; + } + Tag -= Counter::Expression; + switch (Tag) { + case CounterExpression::Subtract: + case CounterExpression::Add: { + auto ID = Value >> Counter::EncodingTagBits; + if (ID >= Expressions.size()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + Expressions[ID].Kind = CounterExpression::ExprKind(Tag); + C = Counter::getExpression(ID); + break; + } + default: + return make_error<CoverageMapError>(coveragemap_error::malformed); + } + return Error::success(); +} + +Error 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 Error::success(); +} + +static const unsigned EncodingExpansionRegionBit = 1 + << Counter::EncodingTagBits; + +/// 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. +Error 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 make_error<CoverageMapError>(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 make_error<CoverageMapError>(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 make_error<CoverageMapError>(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; + + // If the high bit of ColumnEnd is set, this is a gap region. + if (ColumnEnd & (1U << 31)) { + Kind = CounterMappingRegion::GapRegion; + ColumnEnd &= ~(1U << 31); + } + + // 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(); + } + + LLVM_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"; + }); + + auto CMR = CounterMappingRegion(C, InferredFileID, ExpandedFileID, + LineStart, ColumnStart, + LineStart + NumLines, ColumnEnd, Kind); + if (CMR.startLoc() > CMR.endLoc()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + MappingRegions.push_back(CMR); + } + return Error::success(); +} + +Error RawCoverageMappingReader::read() { + // Read the virtual file mapping. + 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 Error::success(); +} + +Expected<bool> RawCoverageMappingDummyChecker::isDummy() { + // A dummy coverage mapping data consists of just one region with zero count. + uint64_t NumFileMappings; + if (Error Err = readSize(NumFileMappings)) + return std::move(Err); + if (NumFileMappings != 1) + return false; + // We don't expect any specific value for the filename index, just skip it. + uint64_t FilenameIndex; + if (Error Err = + readIntMax(FilenameIndex, std::numeric_limits<unsigned>::max())) + return std::move(Err); + uint64_t NumExpressions; + if (Error Err = readSize(NumExpressions)) + return std::move(Err); + if (NumExpressions != 0) + return false; + uint64_t NumRegions; + if (Error Err = readSize(NumRegions)) + return std::move(Err); + if (NumRegions != 1) + return false; + uint64_t EncodedCounterAndRegion; + if (Error Err = readIntMax(EncodedCounterAndRegion, + std::numeric_limits<unsigned>::max())) + return std::move(Err); + unsigned Tag = EncodedCounterAndRegion & Counter::EncodingTagMask; + return Tag == Counter::Zero; +} + +Error InstrProfSymtab::create(SectionRef &Section) { + Expected<StringRef> DataOrErr = Section.getContents(); + if (!DataOrErr) + return DataOrErr.takeError(); + Data = *DataOrErr; + Address = Section.getAddress(); + + // If this is a linked PE/COFF file, then we have to skip over the null byte + // that is allocated in the .lprfn$A section in the LLVM profiling runtime. + const ObjectFile *Obj = Section.getObject(); + if (isa<COFFObjectFile>(Obj) && !Obj->isRelocatableObject()) + Data = Data.drop_front(1); + + return Error::success(); +} + +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); +} + +// Check if the mapping data is a dummy, i.e. is emitted for an unused function. +static Expected<bool> isCoverageMappingDummy(uint64_t Hash, StringRef Mapping) { + // The hash value of dummy mapping records is always zero. + if (Hash) + return false; + return RawCoverageMappingDummyChecker(Mapping).isDummy(); +} + +namespace { + +struct CovMapFuncRecordReader { + virtual ~CovMapFuncRecordReader() = default; + + // The interface to read coverage mapping function records for a module. + // + // \p Buf points to the buffer containing the \c CovHeader of the coverage + // mapping data associated with the module. + // + // Returns a pointer to the next \c CovHeader if it exists, or a pointer + // greater than \p End if not. + virtual Expected<const char *> readFunctionRecords(const char *Buf, + const char *End) = 0; + + template <class IntPtrT, support::endianness Endian> + static Expected<std::unique_ptr<CovMapFuncRecordReader>> + get(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 <CovMapVersion Version, class IntPtrT, support::endianness Endian> +class VersionedCovMapFuncRecordReader : public CovMapFuncRecordReader { + using FuncRecordType = + typename CovMapTraits<Version, IntPtrT>::CovMapFuncRecordType; + using NameRefType = typename CovMapTraits<Version, IntPtrT>::NameRefType; + + // Maps function's name references to the indexes of their records + // in \c Records. + DenseMap<NameRefType, size_t> FunctionRecords; + InstrProfSymtab &ProfileNames; + std::vector<StringRef> &Filenames; + std::vector<BinaryCoverageReader::ProfileMappingRecord> &Records; + + // Add the record to the collection if we don't 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. + // In addition, prefer records with real coverage mapping data to dummy + // records, which were emitted for inline functions which were seen but + // not used in the corresponding translation unit. + Error insertFunctionRecordIfNeeded(const FuncRecordType *CFR, + StringRef Mapping, size_t FilenamesBegin) { + uint64_t FuncHash = CFR->template getFuncHash<Endian>(); + NameRefType NameRef = CFR->template getFuncNameRef<Endian>(); + auto InsertResult = + FunctionRecords.insert(std::make_pair(NameRef, Records.size())); + if (InsertResult.second) { + StringRef FuncName; + if (Error Err = CFR->template getFuncName<Endian>(ProfileNames, FuncName)) + return Err; + if (FuncName.empty()) + return make_error<InstrProfError>(instrprof_error::malformed); + Records.emplace_back(Version, FuncName, FuncHash, Mapping, FilenamesBegin, + Filenames.size() - FilenamesBegin); + return Error::success(); + } + // Update the existing record if it's a dummy and the new record is real. + size_t OldRecordIndex = InsertResult.first->second; + BinaryCoverageReader::ProfileMappingRecord &OldRecord = + Records[OldRecordIndex]; + Expected<bool> OldIsDummyExpected = isCoverageMappingDummy( + OldRecord.FunctionHash, OldRecord.CoverageMapping); + if (Error Err = OldIsDummyExpected.takeError()) + return Err; + if (!*OldIsDummyExpected) + return Error::success(); + Expected<bool> NewIsDummyExpected = + isCoverageMappingDummy(FuncHash, Mapping); + if (Error Err = NewIsDummyExpected.takeError()) + return Err; + if (*NewIsDummyExpected) + return Error::success(); + OldRecord.FunctionHash = FuncHash; + OldRecord.CoverageMapping = Mapping; + OldRecord.FilenamesBegin = FilenamesBegin; + OldRecord.FilenamesSize = Filenames.size() - FilenamesBegin; + return Error::success(); + } + +public: + VersionedCovMapFuncRecordReader( + InstrProfSymtab &P, + std::vector<BinaryCoverageReader::ProfileMappingRecord> &R, + std::vector<StringRef> &F) + : ProfileNames(P), Filenames(F), Records(R) {} + + ~VersionedCovMapFuncRecordReader() override = default; + + Expected<const char *> readFunctionRecords(const char *Buf, + const char *End) override { + using namespace support; + + if (Buf + sizeof(CovMapHeader) > End) + return make_error<CoverageMapError>(coveragemap_error::malformed); + auto CovHeader = reinterpret_cast<const 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 make_error<CoverageMapError>(coveragemap_error::malformed); + size_t FilenamesBegin = Filenames.size(); + RawCoverageFilenamesReader Reader(StringRef(Buf, FilenamesSize), Filenames); + if (auto Err = Reader.read()) + return std::move(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 make_error<CoverageMapError>(coveragemap_error::malformed); + // Each coverage map has an alignment of 8, so we need to adjust alignment + // before reading the next map. + Buf += offsetToAlignedAddr(Buf, Align(8)); + + auto CFR = reinterpret_cast<const FuncRecordType *>(FunBuf); + while ((const char *)CFR < FunEnd) { + // Read the function information + uint32_t DataSize = CFR->template getDataSize<Endian>(); + + // Now use that to read the coverage data. + if (CovBuf + DataSize > CovEnd) + return make_error<CoverageMapError>(coveragemap_error::malformed); + auto Mapping = StringRef(CovBuf, DataSize); + CovBuf += DataSize; + + if (Error Err = + insertFunctionRecordIfNeeded(CFR, Mapping, FilenamesBegin)) + return std::move(Err); + CFR++; + } + return Buf; + } +}; + +} // end anonymous namespace + +template <class IntPtrT, support::endianness Endian> +Expected<std::unique_ptr<CovMapFuncRecordReader>> CovMapFuncRecordReader::get( + CovMapVersion Version, InstrProfSymtab &P, + std::vector<BinaryCoverageReader::ProfileMappingRecord> &R, + std::vector<StringRef> &F) { + using namespace coverage; + + switch (Version) { + case CovMapVersion::Version1: + return std::make_unique<VersionedCovMapFuncRecordReader< + CovMapVersion::Version1, IntPtrT, Endian>>(P, R, F); + case CovMapVersion::Version2: + case CovMapVersion::Version3: + // Decompress the name data. + if (Error E = P.create(P.getNameData())) + return std::move(E); + if (Version == CovMapVersion::Version2) + return std::make_unique<VersionedCovMapFuncRecordReader< + CovMapVersion::Version2, IntPtrT, Endian>>(P, R, F); + else + return std::make_unique<VersionedCovMapFuncRecordReader< + CovMapVersion::Version3, IntPtrT, Endian>>(P, R, F); + } + llvm_unreachable("Unsupported version"); +} + +template <typename T, support::endianness Endian> +static Error 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 CovMapHeader *>(Data.data()); + CovMapVersion Version = (CovMapVersion)CovHeader->getVersion<Endian>(); + if (Version > CovMapVersion::CurrentVersion) + return make_error<CoverageMapError>(coveragemap_error::unsupported_version); + Expected<std::unique_ptr<CovMapFuncRecordReader>> ReaderExpected = + CovMapFuncRecordReader::get<T, Endian>(Version, ProfileNames, Records, + Filenames); + if (Error E = ReaderExpected.takeError()) + return E; + auto Reader = std::move(ReaderExpected.get()); + for (const char *Buf = Data.data(), *End = Buf + Data.size(); Buf < End;) { + auto NextHeaderOrErr = Reader->readFunctionRecords(Buf, End); + if (auto E = NextHeaderOrErr.takeError()) + return E; + Buf = NextHeaderOrErr.get(); + } + return Error::success(); +} + +static const char *TestingFormatMagic = "llvmcovmtestdata"; + +Expected<std::unique_ptr<BinaryCoverageReader>> +BinaryCoverageReader::createCoverageReaderFromBuffer( + StringRef Coverage, InstrProfSymtab &&ProfileNames, uint8_t BytesInAddress, + support::endianness Endian) { + std::unique_ptr<BinaryCoverageReader> Reader(new BinaryCoverageReader()); + Reader->ProfileNames = std::move(ProfileNames); + if (BytesInAddress == 4 && Endian == support::endianness::little) { + if (Error E = + readCoverageMappingData<uint32_t, support::endianness::little>( + Reader->ProfileNames, Coverage, Reader->MappingRecords, + Reader->Filenames)) + return std::move(E); + } else if (BytesInAddress == 4 && Endian == support::endianness::big) { + if (Error E = readCoverageMappingData<uint32_t, support::endianness::big>( + Reader->ProfileNames, Coverage, Reader->MappingRecords, + Reader->Filenames)) + return std::move(E); + } else if (BytesInAddress == 8 && Endian == support::endianness::little) { + if (Error E = + readCoverageMappingData<uint64_t, support::endianness::little>( + Reader->ProfileNames, Coverage, Reader->MappingRecords, + Reader->Filenames)) + return std::move(E); + } else if (BytesInAddress == 8 && Endian == support::endianness::big) { + if (Error E = readCoverageMappingData<uint64_t, support::endianness::big>( + Reader->ProfileNames, Coverage, Reader->MappingRecords, + Reader->Filenames)) + return std::move(E); + } else + return make_error<CoverageMapError>(coveragemap_error::malformed); + return std::move(Reader); +} + +static Expected<std::unique_ptr<BinaryCoverageReader>> +loadTestingFormat(StringRef Data) { + uint8_t BytesInAddress = 8; + support::endianness Endian = support::endianness::little; + + Data = Data.substr(StringRef(TestingFormatMagic).size()); + if (Data.empty()) + return make_error<CoverageMapError>(coveragemap_error::truncated); + unsigned N = 0; + uint64_t ProfileNamesSize = decodeULEB128(Data.bytes_begin(), &N); + if (N > Data.size()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + Data = Data.substr(N); + if (Data.empty()) + return make_error<CoverageMapError>(coveragemap_error::truncated); + N = 0; + uint64_t Address = decodeULEB128(Data.bytes_begin(), &N); + if (N > Data.size()) + return make_error<CoverageMapError>(coveragemap_error::malformed); + Data = Data.substr(N); + if (Data.size() < ProfileNamesSize) + return make_error<CoverageMapError>(coveragemap_error::malformed); + InstrProfSymtab ProfileNames; + if (Error E = ProfileNames.create(Data.substr(0, ProfileNamesSize), Address)) + return std::move(E); + StringRef CoverageMapping = Data.substr(ProfileNamesSize); + // Skip the padding bytes because coverage map data has an alignment of 8. + if (CoverageMapping.empty()) + return make_error<CoverageMapError>(coveragemap_error::truncated); + size_t Pad = offsetToAlignedAddr(CoverageMapping.data(), Align(8)); + if (CoverageMapping.size() < Pad) + return make_error<CoverageMapError>(coveragemap_error::malformed); + CoverageMapping = CoverageMapping.substr(Pad); + return BinaryCoverageReader::createCoverageReaderFromBuffer( + CoverageMapping, std::move(ProfileNames), BytesInAddress, Endian); +} + +static Expected<SectionRef> lookupSection(ObjectFile &OF, StringRef Name) { + // On COFF, the object file section name may end in "$M". This tells the + // linker to sort these sections between "$A" and "$Z". The linker removes the + // dollar and everything after it in the final binary. Do the same to match. + bool IsCOFF = isa<COFFObjectFile>(OF); + auto stripSuffix = [IsCOFF](StringRef N) { + return IsCOFF ? N.split('$').first : N; + }; + Name = stripSuffix(Name); + + for (const auto &Section : OF.sections()) { + Expected<StringRef> NameOrErr = Section.getName(); + if (!NameOrErr) + return NameOrErr.takeError(); + if (stripSuffix(*NameOrErr) == Name) + return Section; + } + return make_error<CoverageMapError>(coveragemap_error::no_data_found); +} + +static Expected<std::unique_ptr<BinaryCoverageReader>> +loadBinaryFormat(std::unique_ptr<Binary> Bin, StringRef Arch) { + std::unique_ptr<ObjectFile> OF; + if (auto *Universal = dyn_cast<MachOUniversalBinary>(Bin.get())) { + // If we have a universal binary, try to look up the object for the + // appropriate architecture. + auto ObjectFileOrErr = Universal->getMachOObjectForArch(Arch); + if (!ObjectFileOrErr) + return ObjectFileOrErr.takeError(); + OF = std::move(ObjectFileOrErr.get()); + } else if (isa<ObjectFile>(Bin.get())) { + // For any other object file, upcast and take ownership. + OF.reset(cast<ObjectFile>(Bin.release())); + // If we've asked for a particular arch, make sure they match. + if (!Arch.empty() && OF->getArch() != Triple(Arch).getArch()) + return errorCodeToError(object_error::arch_not_found); + } else + // We can only handle object files. + return make_error<CoverageMapError>(coveragemap_error::malformed); + + // The coverage uses native pointer sizes for the object it's written in. + uint8_t BytesInAddress = OF->getBytesInAddress(); + support::endianness Endian = OF->isLittleEndian() + ? support::endianness::little + : support::endianness::big; + + // Look for the sections that we are interested in. + auto ObjFormat = OF->getTripleObjectFormat(); + auto NamesSection = + lookupSection(*OF, getInstrProfSectionName(IPSK_name, ObjFormat, + /*AddSegmentInfo=*/false)); + if (auto E = NamesSection.takeError()) + return std::move(E); + auto CoverageSection = + lookupSection(*OF, getInstrProfSectionName(IPSK_covmap, ObjFormat, + /*AddSegmentInfo=*/false)); + if (auto E = CoverageSection.takeError()) + return std::move(E); + + // Get the contents of the given sections. + auto CoverageMappingOrErr = CoverageSection->getContents(); + if (!CoverageMappingOrErr) + return CoverageMappingOrErr.takeError(); + + InstrProfSymtab ProfileNames; + if (Error E = ProfileNames.create(*NamesSection)) + return std::move(E); + + return BinaryCoverageReader::createCoverageReaderFromBuffer( + CoverageMappingOrErr.get(), std::move(ProfileNames), BytesInAddress, + Endian); +} + +Expected<std::vector<std::unique_ptr<BinaryCoverageReader>>> +BinaryCoverageReader::create( + MemoryBufferRef ObjectBuffer, StringRef Arch, + SmallVectorImpl<std::unique_ptr<MemoryBuffer>> &ObjectFileBuffers) { + std::vector<std::unique_ptr<BinaryCoverageReader>> Readers; + + if (ObjectBuffer.getBuffer().startswith(TestingFormatMagic)) { + // This is a special format used for testing. + auto ReaderOrErr = loadTestingFormat(ObjectBuffer.getBuffer()); + if (!ReaderOrErr) + return ReaderOrErr.takeError(); + Readers.push_back(std::move(ReaderOrErr.get())); + return std::move(Readers); + } + + auto BinOrErr = createBinary(ObjectBuffer); + if (!BinOrErr) + return BinOrErr.takeError(); + std::unique_ptr<Binary> Bin = std::move(BinOrErr.get()); + + // MachO universal binaries which contain archives need to be treated as + // archives, not as regular binaries. + if (auto *Universal = dyn_cast<MachOUniversalBinary>(Bin.get())) { + for (auto &ObjForArch : Universal->objects()) { + // Skip slices within the universal binary which target the wrong arch. + std::string ObjArch = ObjForArch.getArchFlagName(); + if (Arch != ObjArch) + continue; + + auto ArchiveOrErr = ObjForArch.getAsArchive(); + if (!ArchiveOrErr) { + // If this is not an archive, try treating it as a regular object. + consumeError(ArchiveOrErr.takeError()); + break; + } + + return BinaryCoverageReader::create( + ArchiveOrErr.get()->getMemoryBufferRef(), Arch, ObjectFileBuffers); + } + } + + // Load coverage out of archive members. + if (auto *Ar = dyn_cast<Archive>(Bin.get())) { + Error Err = Error::success(); + for (auto &Child : Ar->children(Err)) { + Expected<MemoryBufferRef> ChildBufOrErr = Child.getMemoryBufferRef(); + if (!ChildBufOrErr) + return ChildBufOrErr.takeError(); + + auto ChildReadersOrErr = BinaryCoverageReader::create( + ChildBufOrErr.get(), Arch, ObjectFileBuffers); + if (!ChildReadersOrErr) + return ChildReadersOrErr.takeError(); + for (auto &Reader : ChildReadersOrErr.get()) + Readers.push_back(std::move(Reader)); + } + if (Err) + return std::move(Err); + + // Thin archives reference object files outside of the archive file, i.e. + // files which reside in memory not owned by the caller. Transfer ownership + // to the caller. + if (Ar->isThin()) + for (auto &Buffer : Ar->takeThinBuffers()) + ObjectFileBuffers.push_back(std::move(Buffer)); + + return std::move(Readers); + } + + auto ReaderOrErr = loadBinaryFormat(std::move(Bin), Arch); + if (!ReaderOrErr) + return ReaderOrErr.takeError(); + Readers.push_back(std::move(ReaderOrErr.get())); + return std::move(Readers); +} + +Error BinaryCoverageReader::readNextRecord(CoverageMappingRecord &Record) { + if (CurrentRecord >= MappingRecords.size()) + return make_error<CoverageMapError>(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 Error::success(); +} diff --git a/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp new file mode 100644 index 000000000000..d75854a60d1e --- /dev/null +++ b/llvm/lib/ProfileData/Coverage/CoverageMappingWriter.cpp @@ -0,0 +1,216 @@ +//===- CoverageMappingWriter.cpp - Code coverage mapping writer -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains support for writing coverage mapping data for +// instrumentation based coverage. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/LEB128.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <limits> +#include <vector> + +using namespace llvm; +using namespace coverage; + +CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter( + ArrayRef<StringRef> Filenames) + : Filenames(Filenames) { +#ifndef NDEBUG + StringSet<> NameSet; + for (StringRef Name : Filenames) + assert(NameSet.insert(Name).second && "Duplicate filename"); +#endif +} + +void CoverageFilenamesSectionWriter::write(raw_ostream &OS) { + encodeULEB128(Filenames.size(), OS); + for (const auto &Filename : Filenames) { + encodeULEB128(Filename.size(), OS); + OS << Filename; + } +} + +namespace { + +/// Gather only the expressions that are used by the mapping +/// regions in this function. +class CounterExpressionsMinimizer { + ArrayRef<CounterExpression> Expressions; + SmallVector<CounterExpression, 16> UsedExpressions; + std::vector<unsigned> AdjustedExpressionIDs; + +public: + 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); + } + + 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); + } + + ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; } + + /// 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; + } +}; + +} // end anonymous namespace + +/// 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) { + // Check that we don't have any bogus regions. + assert(all_of(MappingRegions, + [](const CounterMappingRegion &CMR) { + return CMR.startLoc() <= CMR.endLoc(); + }) && + "Source region does not begin before it ends"); + + // Sort the regions in an ascending order by the file id and the starting + // location. Sort by region kinds to ensure stable order for tests. + llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS, + const CounterMappingRegion &RHS) { + if (LHS.FileID != RHS.FileID) + return LHS.FileID < RHS.FileID; + if (LHS.startLoc() != RHS.startLoc()) + return LHS.startLoc() < RHS.startLoc(); + return LHS.Kind < RHS.Kind; + }); + + // 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: + case CounterMappingRegion::GapRegion: + 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)); +} |