CoverageMapping.cpp revision 360784
1321369Sdim//===- CoverageMapping.cpp - Code coverage mapping support ----------------===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim// 9303231Sdim// This file contains support for clang's and llvm's instrumentation based 10303231Sdim// code coverage. 11303231Sdim// 12303231Sdim//===----------------------------------------------------------------------===// 13303231Sdim 14303231Sdim#include "llvm/ProfileData/Coverage/CoverageMapping.h" 15321369Sdim#include "llvm/ADT/ArrayRef.h" 16303231Sdim#include "llvm/ADT/DenseMap.h" 17321369Sdim#include "llvm/ADT/None.h" 18303231Sdim#include "llvm/ADT/Optional.h" 19303231Sdim#include "llvm/ADT/SmallBitVector.h" 20321369Sdim#include "llvm/ADT/SmallVector.h" 21321369Sdim#include "llvm/ADT/StringRef.h" 22303231Sdim#include "llvm/ProfileData/Coverage/CoverageMappingReader.h" 23303231Sdim#include "llvm/ProfileData/InstrProfReader.h" 24303231Sdim#include "llvm/Support/Debug.h" 25303231Sdim#include "llvm/Support/Errc.h" 26321369Sdim#include "llvm/Support/Error.h" 27303231Sdim#include "llvm/Support/ErrorHandling.h" 28303231Sdim#include "llvm/Support/ManagedStatic.h" 29321369Sdim#include "llvm/Support/MemoryBuffer.h" 30303231Sdim#include "llvm/Support/raw_ostream.h" 31321369Sdim#include <algorithm> 32321369Sdim#include <cassert> 33321369Sdim#include <cstdint> 34321369Sdim#include <iterator> 35327952Sdim#include <map> 36321369Sdim#include <memory> 37321369Sdim#include <string> 38321369Sdim#include <system_error> 39321369Sdim#include <utility> 40321369Sdim#include <vector> 41303231Sdim 42303231Sdimusing namespace llvm; 43303231Sdimusing namespace coverage; 44303231Sdim 45303231Sdim#define DEBUG_TYPE "coverage-mapping" 46303231Sdim 47303231SdimCounter CounterExpressionBuilder::get(const CounterExpression &E) { 48303231Sdim auto It = ExpressionIndices.find(E); 49303231Sdim if (It != ExpressionIndices.end()) 50303231Sdim return Counter::getExpression(It->second); 51303231Sdim unsigned I = Expressions.size(); 52303231Sdim Expressions.push_back(E); 53303231Sdim ExpressionIndices[E] = I; 54303231Sdim return Counter::getExpression(I); 55303231Sdim} 56303231Sdim 57321369Sdimvoid CounterExpressionBuilder::extractTerms(Counter C, int Factor, 58321369Sdim SmallVectorImpl<Term> &Terms) { 59303231Sdim switch (C.getKind()) { 60303231Sdim case Counter::Zero: 61303231Sdim break; 62303231Sdim case Counter::CounterValueReference: 63321369Sdim Terms.emplace_back(C.getCounterID(), Factor); 64303231Sdim break; 65303231Sdim case Counter::Expression: 66303231Sdim const auto &E = Expressions[C.getExpressionID()]; 67321369Sdim extractTerms(E.LHS, Factor, Terms); 68321369Sdim extractTerms( 69321369Sdim E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); 70303231Sdim break; 71303231Sdim } 72303231Sdim} 73303231Sdim 74303231SdimCounter CounterExpressionBuilder::simplify(Counter ExpressionTree) { 75303231Sdim // Gather constant terms. 76321369Sdim SmallVector<Term, 32> Terms; 77303231Sdim extractTerms(ExpressionTree, +1, Terms); 78303231Sdim 79303231Sdim // If there are no terms, this is just a zero. The algorithm below assumes at 80303231Sdim // least one term. 81303231Sdim if (Terms.size() == 0) 82303231Sdim return Counter::getZero(); 83303231Sdim 84303231Sdim // Group the terms by counter ID. 85344779Sdim llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { 86321369Sdim return LHS.CounterID < RHS.CounterID; 87303231Sdim }); 88303231Sdim 89303231Sdim // Combine terms by counter ID to eliminate counters that sum to zero. 90303231Sdim auto Prev = Terms.begin(); 91303231Sdim for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { 92321369Sdim if (I->CounterID == Prev->CounterID) { 93321369Sdim Prev->Factor += I->Factor; 94303231Sdim continue; 95303231Sdim } 96303231Sdim ++Prev; 97303231Sdim *Prev = *I; 98303231Sdim } 99303231Sdim Terms.erase(++Prev, Terms.end()); 100303231Sdim 101303231Sdim Counter C; 102303231Sdim // Create additions. We do this before subtractions to avoid constructs like 103303231Sdim // ((0 - X) + Y), as opposed to (Y - X). 104321369Sdim for (auto T : Terms) { 105321369Sdim if (T.Factor <= 0) 106303231Sdim continue; 107321369Sdim for (int I = 0; I < T.Factor; ++I) 108303231Sdim if (C.isZero()) 109321369Sdim C = Counter::getCounter(T.CounterID); 110303231Sdim else 111303231Sdim C = get(CounterExpression(CounterExpression::Add, C, 112321369Sdim Counter::getCounter(T.CounterID))); 113303231Sdim } 114303231Sdim 115303231Sdim // Create subtractions. 116321369Sdim for (auto T : Terms) { 117321369Sdim if (T.Factor >= 0) 118303231Sdim continue; 119321369Sdim for (int I = 0; I < -T.Factor; ++I) 120303231Sdim C = get(CounterExpression(CounterExpression::Subtract, C, 121321369Sdim Counter::getCounter(T.CounterID))); 122303231Sdim } 123303231Sdim return C; 124303231Sdim} 125303231Sdim 126303231SdimCounter CounterExpressionBuilder::add(Counter LHS, Counter RHS) { 127303231Sdim return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS))); 128303231Sdim} 129303231Sdim 130303231SdimCounter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) { 131303231Sdim return simplify( 132303231Sdim get(CounterExpression(CounterExpression::Subtract, LHS, RHS))); 133303231Sdim} 134303231Sdim 135321369Sdimvoid CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { 136303231Sdim switch (C.getKind()) { 137303231Sdim case Counter::Zero: 138303231Sdim OS << '0'; 139303231Sdim return; 140303231Sdim case Counter::CounterValueReference: 141303231Sdim OS << '#' << C.getCounterID(); 142303231Sdim break; 143303231Sdim case Counter::Expression: { 144303231Sdim if (C.getExpressionID() >= Expressions.size()) 145303231Sdim return; 146303231Sdim const auto &E = Expressions[C.getExpressionID()]; 147303231Sdim OS << '('; 148303231Sdim dump(E.LHS, OS); 149303231Sdim OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); 150303231Sdim dump(E.RHS, OS); 151303231Sdim OS << ')'; 152303231Sdim break; 153303231Sdim } 154303231Sdim } 155303231Sdim if (CounterValues.empty()) 156303231Sdim return; 157303231Sdim Expected<int64_t> Value = evaluate(C); 158303231Sdim if (auto E = Value.takeError()) { 159321369Sdim consumeError(std::move(E)); 160303231Sdim return; 161303231Sdim } 162303231Sdim OS << '[' << *Value << ']'; 163303231Sdim} 164303231Sdim 165303231SdimExpected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { 166303231Sdim switch (C.getKind()) { 167303231Sdim case Counter::Zero: 168303231Sdim return 0; 169303231Sdim case Counter::CounterValueReference: 170303231Sdim if (C.getCounterID() >= CounterValues.size()) 171303231Sdim return errorCodeToError(errc::argument_out_of_domain); 172303231Sdim return CounterValues[C.getCounterID()]; 173303231Sdim case Counter::Expression: { 174303231Sdim if (C.getExpressionID() >= Expressions.size()) 175303231Sdim return errorCodeToError(errc::argument_out_of_domain); 176303231Sdim const auto &E = Expressions[C.getExpressionID()]; 177303231Sdim Expected<int64_t> LHS = evaluate(E.LHS); 178303231Sdim if (!LHS) 179303231Sdim return LHS; 180303231Sdim Expected<int64_t> RHS = evaluate(E.RHS); 181303231Sdim if (!RHS) 182303231Sdim return RHS; 183303231Sdim return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS; 184303231Sdim } 185303231Sdim } 186303231Sdim llvm_unreachable("Unhandled CounterKind"); 187303231Sdim} 188303231Sdim 189303231Sdimvoid FunctionRecordIterator::skipOtherFiles() { 190303231Sdim while (Current != Records.end() && !Filename.empty() && 191303231Sdim Filename != Current->Filenames[0]) 192303231Sdim ++Current; 193303231Sdim if (Current == Records.end()) 194303231Sdim *this = FunctionRecordIterator(); 195303231Sdim} 196303231Sdim 197360784SdimArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename( 198360784Sdim StringRef Filename) const { 199360784Sdim size_t FilenameHash = hash_value(Filename); 200360784Sdim auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash); 201360784Sdim if (RecordIt == FilenameHash2RecordIndices.end()) 202360784Sdim return {}; 203360784Sdim return RecordIt->second; 204360784Sdim} 205360784Sdim 206314564SdimError CoverageMapping::loadFunctionRecord( 207314564Sdim const CoverageMappingRecord &Record, 208314564Sdim IndexedInstrProfReader &ProfileReader) { 209314564Sdim StringRef OrigFuncName = Record.FunctionName; 210321369Sdim if (OrigFuncName.empty()) 211321369Sdim return make_error<CoverageMapError>(coveragemap_error::malformed); 212321369Sdim 213314564Sdim if (Record.Filenames.empty()) 214314564Sdim OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); 215314564Sdim else 216314564Sdim OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); 217314564Sdim 218314564Sdim CounterMappingContext Ctx(Record.Expressions); 219314564Sdim 220314564Sdim std::vector<uint64_t> Counts; 221314564Sdim if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, 222314564Sdim Record.FunctionHash, Counts)) { 223314564Sdim instrprof_error IPE = InstrProfError::take(std::move(E)); 224314564Sdim if (IPE == instrprof_error::hash_mismatch) { 225327952Sdim FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash); 226314564Sdim return Error::success(); 227314564Sdim } else if (IPE != instrprof_error::unknown_function) 228314564Sdim return make_error<InstrProfError>(IPE); 229314564Sdim Counts.assign(Record.MappingRegions.size(), 0); 230314564Sdim } 231314564Sdim Ctx.setCounts(Counts); 232314564Sdim 233314564Sdim assert(!Record.MappingRegions.empty() && "Function has no regions"); 234314564Sdim 235344779Sdim // This coverage record is a zero region for a function that's unused in 236344779Sdim // some TU, but used in a different TU. Ignore it. The coverage maps from the 237344779Sdim // the other TU will either be loaded (providing full region counts) or they 238344779Sdim // won't (in which case we don't unintuitively report functions as uncovered 239344779Sdim // when they have non-zero counts in the profile). 240344779Sdim if (Record.MappingRegions.size() == 1 && 241344779Sdim Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) 242344779Sdim return Error::success(); 243344779Sdim 244314564Sdim FunctionRecord Function(OrigFuncName, Record.Filenames); 245314564Sdim for (const auto &Region : Record.MappingRegions) { 246314564Sdim Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); 247314564Sdim if (auto E = ExecutionCount.takeError()) { 248321369Sdim consumeError(std::move(E)); 249314564Sdim return Error::success(); 250314564Sdim } 251314564Sdim Function.pushRegion(Region, *ExecutionCount); 252314564Sdim } 253344779Sdim 254344779Sdim // Don't create records for (filenames, function) pairs we've already seen. 255344779Sdim auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), 256344779Sdim Record.Filenames.end()); 257344779Sdim if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) 258314564Sdim return Error::success(); 259314564Sdim 260314564Sdim Functions.push_back(std::move(Function)); 261360784Sdim 262360784Sdim // Performance optimization: keep track of the indices of the function records 263360784Sdim // which correspond to each filename. This can be used to substantially speed 264360784Sdim // up queries for coverage info in a file. 265360784Sdim unsigned RecordIndex = Functions.size() - 1; 266360784Sdim for (StringRef Filename : Record.Filenames) { 267360784Sdim auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)]; 268360784Sdim // Note that there may be duplicates in the filename set for a function 269360784Sdim // record, because of e.g. macro expansions in the function in which both 270360784Sdim // the macro and the function are defined in the same file. 271360784Sdim if (RecordIndices.empty() || RecordIndices.back() != RecordIndex) 272360784Sdim RecordIndices.push_back(RecordIndex); 273360784Sdim } 274360784Sdim 275314564Sdim return Error::success(); 276314564Sdim} 277314564Sdim 278314564SdimExpected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( 279314564Sdim ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 280314564Sdim IndexedInstrProfReader &ProfileReader) { 281314564Sdim auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 282303231Sdim 283327952Sdim for (const auto &CoverageReader : CoverageReaders) { 284327952Sdim for (auto RecordOrErr : *CoverageReader) { 285327952Sdim if (Error E = RecordOrErr.takeError()) 286327952Sdim return std::move(E); 287327952Sdim const auto &Record = *RecordOrErr; 288314564Sdim if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader)) 289314564Sdim return std::move(E); 290327952Sdim } 291327952Sdim } 292303231Sdim 293303231Sdim return std::move(Coverage); 294303231Sdim} 295303231Sdim 296360784Sdim// If E is a no_data_found error, returns success. Otherwise returns E. 297360784Sdimstatic Error handleMaybeNoDataFoundError(Error E) { 298360784Sdim return handleErrors( 299360784Sdim std::move(E), [](const CoverageMapError &CME) { 300360784Sdim if (CME.get() == coveragemap_error::no_data_found) 301360784Sdim return static_cast<Error>(Error::success()); 302360784Sdim return make_error<CoverageMapError>(CME.get()); 303360784Sdim }); 304360784Sdim} 305360784Sdim 306303231SdimExpected<std::unique_ptr<CoverageMapping>> 307314564SdimCoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, 308327952Sdim StringRef ProfileFilename, ArrayRef<StringRef> Arches) { 309303231Sdim auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); 310303231Sdim if (Error E = ProfileReaderOrErr.takeError()) 311303231Sdim return std::move(E); 312303231Sdim auto ProfileReader = std::move(ProfileReaderOrErr.get()); 313314564Sdim 314314564Sdim SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; 315314564Sdim SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; 316327952Sdim for (const auto &File : llvm::enumerate(ObjectFilenames)) { 317327952Sdim auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value()); 318314564Sdim if (std::error_code EC = CovMappingBufOrErr.getError()) 319314564Sdim return errorCodeToError(EC); 320327952Sdim StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()]; 321353358Sdim MemoryBufferRef CovMappingBufRef = 322353358Sdim CovMappingBufOrErr.get()->getMemBufferRef(); 323353358Sdim auto CoverageReadersOrErr = 324353358Sdim BinaryCoverageReader::create(CovMappingBufRef, Arch, Buffers); 325360784Sdim if (Error E = CoverageReadersOrErr.takeError()) { 326360784Sdim E = handleMaybeNoDataFoundError(std::move(E)); 327360784Sdim if (E) 328360784Sdim return std::move(E); 329360784Sdim // E == success (originally a no_data_found error). 330360784Sdim continue; 331360784Sdim } 332353358Sdim for (auto &Reader : CoverageReadersOrErr.get()) 333353358Sdim Readers.push_back(std::move(Reader)); 334314564Sdim Buffers.push_back(std::move(CovMappingBufOrErr.get())); 335314564Sdim } 336360784Sdim // If no readers were created, either no objects were provided or none of them 337360784Sdim // had coverage data. Return an error in the latter case. 338360784Sdim if (Readers.empty() && !ObjectFilenames.empty()) 339360784Sdim return make_error<CoverageMapError>(coveragemap_error::no_data_found); 340314564Sdim return load(Readers, *ProfileReader); 341303231Sdim} 342303231Sdim 343303231Sdimnamespace { 344321369Sdim 345341825Sdim/// Distributes functions into instantiation sets. 346303231Sdim/// 347303231Sdim/// An instantiation set is a collection of functions that have the same source 348303231Sdim/// code, ie, template functions specializations. 349303231Sdimclass FunctionInstantiationSetCollector { 350327952Sdim using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; 351303231Sdim MapT InstantiatedFunctions; 352303231Sdim 353303231Sdimpublic: 354303231Sdim void insert(const FunctionRecord &Function, unsigned FileID) { 355303231Sdim auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 356303231Sdim while (I != E && I->FileID != FileID) 357303231Sdim ++I; 358303231Sdim assert(I != E && "function does not cover the given file"); 359303231Sdim auto &Functions = InstantiatedFunctions[I->startLoc()]; 360303231Sdim Functions.push_back(&Function); 361303231Sdim } 362303231Sdim 363303231Sdim MapT::iterator begin() { return InstantiatedFunctions.begin(); } 364303231Sdim MapT::iterator end() { return InstantiatedFunctions.end(); } 365303231Sdim}; 366303231Sdim 367303231Sdimclass SegmentBuilder { 368303231Sdim std::vector<CoverageSegment> &Segments; 369303231Sdim SmallVector<const CountedRegion *, 8> ActiveRegions; 370303231Sdim 371303231Sdim SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} 372303231Sdim 373327952Sdim /// Emit a segment with the count from \p Region starting at \p StartLoc. 374327952Sdim // 375327952Sdim /// \p IsRegionEntry: The segment is at the start of a new non-gap region. 376327952Sdim /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. 377327952Sdim void startSegment(const CountedRegion &Region, LineColPair StartLoc, 378327952Sdim bool IsRegionEntry, bool EmitSkippedRegion = false) { 379327952Sdim bool HasCount = !EmitSkippedRegion && 380327952Sdim (Region.Kind != CounterMappingRegion::SkippedRegion); 381303231Sdim 382327952Sdim // If the new segment wouldn't affect coverage rendering, skip it. 383327952Sdim if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { 384327952Sdim const auto &Last = Segments.back(); 385327952Sdim if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && 386327952Sdim !Last.IsRegionEntry) 387327952Sdim return; 388327952Sdim } 389303231Sdim 390327952Sdim if (HasCount) 391327952Sdim Segments.emplace_back(StartLoc.first, StartLoc.second, 392327952Sdim Region.ExecutionCount, IsRegionEntry, 393327952Sdim Region.Kind == CounterMappingRegion::GapRegion); 394327952Sdim else 395327952Sdim Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); 396327952Sdim 397341825Sdim LLVM_DEBUG({ 398327952Sdim const auto &Last = Segments.back(); 399327952Sdim dbgs() << "Segment at " << Last.Line << ":" << Last.Col 400327952Sdim << " (count = " << Last.Count << ")" 401327952Sdim << (Last.IsRegionEntry ? ", RegionEntry" : "") 402327952Sdim << (!Last.HasCount ? ", Skipped" : "") 403327952Sdim << (Last.IsGapRegion ? ", Gap" : "") << "\n"; 404327952Sdim }); 405303231Sdim } 406303231Sdim 407327952Sdim /// Emit segments for active regions which end before \p Loc. 408327952Sdim /// 409327952Sdim /// \p Loc: The start location of the next region. If None, all active 410327952Sdim /// regions are completed. 411327952Sdim /// \p FirstCompletedRegion: Index of the first completed region. 412327952Sdim void completeRegionsUntil(Optional<LineColPair> Loc, 413327952Sdim unsigned FirstCompletedRegion) { 414327952Sdim // Sort the completed regions by end location. This makes it simple to 415327952Sdim // emit closing segments in sorted order. 416327952Sdim auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; 417327952Sdim std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), 418327952Sdim [](const CountedRegion *L, const CountedRegion *R) { 419327952Sdim return L->endLoc() < R->endLoc(); 420327952Sdim }); 421327952Sdim 422327952Sdim // Emit segments for all completed regions. 423327952Sdim for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; 424327952Sdim ++I) { 425327952Sdim const auto *CompletedRegion = ActiveRegions[I]; 426327952Sdim assert((!Loc || CompletedRegion->endLoc() <= *Loc) && 427327952Sdim "Completed region ends after start of new region"); 428327952Sdim 429327952Sdim const auto *PrevCompletedRegion = ActiveRegions[I - 1]; 430327952Sdim auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); 431327952Sdim 432327952Sdim // Don't emit any more segments if they start where the new region begins. 433327952Sdim if (Loc && CompletedSegmentLoc == *Loc) 434327952Sdim break; 435327952Sdim 436327952Sdim // Don't emit a segment if the next completed region ends at the same 437327952Sdim // location as this one. 438327952Sdim if (CompletedSegmentLoc == CompletedRegion->endLoc()) 439327952Sdim continue; 440327952Sdim 441327952Sdim // Use the count from the last completed region which ends at this loc. 442327952Sdim for (unsigned J = I + 1; J < E; ++J) 443327952Sdim if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) 444327952Sdim CompletedRegion = ActiveRegions[J]; 445327952Sdim 446327952Sdim startSegment(*CompletedRegion, CompletedSegmentLoc, false); 447327952Sdim } 448327952Sdim 449327952Sdim auto Last = ActiveRegions.back(); 450327952Sdim if (FirstCompletedRegion && Last->endLoc() != *Loc) { 451327952Sdim // If there's a gap after the end of the last completed region and the 452327952Sdim // start of the new region, use the last active region to fill the gap. 453327952Sdim startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), 454327952Sdim false); 455327952Sdim } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { 456327952Sdim // Emit a skipped segment if there are no more active regions. This 457327952Sdim // ensures that gaps between functions are marked correctly. 458327952Sdim startSegment(*Last, Last->endLoc(), false, true); 459327952Sdim } 460327952Sdim 461327952Sdim // Pop the completed regions. 462327952Sdim ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); 463303231Sdim } 464303231Sdim 465303231Sdim void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { 466327952Sdim for (const auto &CR : enumerate(Regions)) { 467327952Sdim auto CurStartLoc = CR.value().startLoc(); 468327952Sdim 469327952Sdim // Active regions which end before the current region need to be popped. 470327952Sdim auto CompletedRegions = 471327952Sdim std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), 472327952Sdim [&](const CountedRegion *Region) { 473327952Sdim return !(Region->endLoc() <= CurStartLoc); 474327952Sdim }); 475327952Sdim if (CompletedRegions != ActiveRegions.end()) { 476327952Sdim unsigned FirstCompletedRegion = 477327952Sdim std::distance(ActiveRegions.begin(), CompletedRegions); 478327952Sdim completeRegionsUntil(CurStartLoc, FirstCompletedRegion); 479327952Sdim } 480327952Sdim 481327952Sdim bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; 482327952Sdim 483327952Sdim // Try to emit a segment for the current region. 484327952Sdim if (CurStartLoc == CR.value().endLoc()) { 485327952Sdim // Avoid making zero-length regions active. If it's the last region, 486327952Sdim // emit a skipped segment. Otherwise use its predecessor's count. 487327952Sdim const bool Skipped = (CR.index() + 1) == Regions.size(); 488327952Sdim startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), 489327952Sdim CurStartLoc, !GapRegion, Skipped); 490327952Sdim continue; 491327952Sdim } 492327952Sdim if (CR.index() + 1 == Regions.size() || 493327952Sdim CurStartLoc != Regions[CR.index() + 1].startLoc()) { 494327952Sdim // Emit a segment if the next region doesn't start at the same location 495327952Sdim // as this one. 496327952Sdim startSegment(CR.value(), CurStartLoc, !GapRegion); 497327952Sdim } 498327952Sdim 499327952Sdim // This region is active (i.e not completed). 500327952Sdim ActiveRegions.push_back(&CR.value()); 501303231Sdim } 502327952Sdim 503327952Sdim // Complete any remaining active regions. 504327952Sdim if (!ActiveRegions.empty()) 505327952Sdim completeRegionsUntil(None, 0); 506303231Sdim } 507303231Sdim 508303231Sdim /// Sort a nested sequence of regions from a single file. 509303231Sdim static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { 510344779Sdim llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { 511303231Sdim if (LHS.startLoc() != RHS.startLoc()) 512303231Sdim return LHS.startLoc() < RHS.startLoc(); 513303231Sdim if (LHS.endLoc() != RHS.endLoc()) 514303231Sdim // When LHS completely contains RHS, we sort LHS first. 515303231Sdim return RHS.endLoc() < LHS.endLoc(); 516303231Sdim // If LHS and RHS cover the same area, we need to sort them according 517303231Sdim // to their kinds so that the most suitable region will become "active" 518303231Sdim // in combineRegions(). Because we accumulate counter values only from 519303231Sdim // regions of the same kind as the first region of the area, prefer 520303231Sdim // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. 521321369Sdim static_assert(CounterMappingRegion::CodeRegion < 522321369Sdim CounterMappingRegion::ExpansionRegion && 523321369Sdim CounterMappingRegion::ExpansionRegion < 524321369Sdim CounterMappingRegion::SkippedRegion, 525303231Sdim "Unexpected order of region kind values"); 526303231Sdim return LHS.Kind < RHS.Kind; 527303231Sdim }); 528303231Sdim } 529303231Sdim 530303231Sdim /// Combine counts of regions which cover the same area. 531303231Sdim static ArrayRef<CountedRegion> 532303231Sdim combineRegions(MutableArrayRef<CountedRegion> Regions) { 533303231Sdim if (Regions.empty()) 534303231Sdim return Regions; 535303231Sdim auto Active = Regions.begin(); 536303231Sdim auto End = Regions.end(); 537303231Sdim for (auto I = Regions.begin() + 1; I != End; ++I) { 538303231Sdim if (Active->startLoc() != I->startLoc() || 539303231Sdim Active->endLoc() != I->endLoc()) { 540303231Sdim // Shift to the next region. 541303231Sdim ++Active; 542303231Sdim if (Active != I) 543303231Sdim *Active = *I; 544303231Sdim continue; 545303231Sdim } 546303231Sdim // Merge duplicate region. 547303231Sdim // If CodeRegions and ExpansionRegions cover the same area, it's probably 548303231Sdim // a macro which is fully expanded to another macro. In that case, we need 549303231Sdim // to accumulate counts only from CodeRegions, or else the area will be 550303231Sdim // counted twice. 551303231Sdim // On the other hand, a macro may have a nested macro in its body. If the 552303231Sdim // outer macro is used several times, the ExpansionRegion for the nested 553303231Sdim // macro will also be added several times. These ExpansionRegions cover 554303231Sdim // the same source locations and have to be combined to reach the correct 555303231Sdim // value for that area. 556303231Sdim // We add counts of the regions of the same kind as the active region 557303231Sdim // to handle the both situations. 558303231Sdim if (I->Kind == Active->Kind) 559303231Sdim Active->ExecutionCount += I->ExecutionCount; 560303231Sdim } 561303231Sdim return Regions.drop_back(std::distance(++Active, End)); 562303231Sdim } 563303231Sdim 564303231Sdimpublic: 565327952Sdim /// Build a sorted list of CoverageSegments from a list of Regions. 566303231Sdim static std::vector<CoverageSegment> 567303231Sdim buildSegments(MutableArrayRef<CountedRegion> Regions) { 568303231Sdim std::vector<CoverageSegment> Segments; 569303231Sdim SegmentBuilder Builder(Segments); 570303231Sdim 571303231Sdim sortNestedRegions(Regions); 572303231Sdim ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); 573303231Sdim 574341825Sdim LLVM_DEBUG({ 575327952Sdim dbgs() << "Combined regions:\n"; 576327952Sdim for (const auto &CR : CombinedRegions) 577327952Sdim dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " 578327952Sdim << CR.LineEnd << ":" << CR.ColumnEnd 579327952Sdim << " (count=" << CR.ExecutionCount << ")\n"; 580327952Sdim }); 581327952Sdim 582303231Sdim Builder.buildSegmentsImpl(CombinedRegions); 583327952Sdim 584327952Sdim#ifndef NDEBUG 585327952Sdim for (unsigned I = 1, E = Segments.size(); I < E; ++I) { 586327952Sdim const auto &L = Segments[I - 1]; 587327952Sdim const auto &R = Segments[I]; 588327952Sdim if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { 589341825Sdim LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col 590341825Sdim << " followed by " << R.Line << ":" << R.Col << "\n"); 591327952Sdim assert(false && "Coverage segments not unique or sorted"); 592327952Sdim } 593327952Sdim } 594327952Sdim#endif 595327952Sdim 596303231Sdim return Segments; 597303231Sdim } 598303231Sdim}; 599303231Sdim 600321369Sdim} // end anonymous namespace 601321369Sdim 602303231Sdimstd::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 603303231Sdim std::vector<StringRef> Filenames; 604303231Sdim for (const auto &Function : getCoveredFunctions()) 605303231Sdim Filenames.insert(Filenames.end(), Function.Filenames.begin(), 606303231Sdim Function.Filenames.end()); 607344779Sdim llvm::sort(Filenames); 608303231Sdim auto Last = std::unique(Filenames.begin(), Filenames.end()); 609303231Sdim Filenames.erase(Last, Filenames.end()); 610303231Sdim return Filenames; 611303231Sdim} 612303231Sdim 613303231Sdimstatic SmallBitVector gatherFileIDs(StringRef SourceFile, 614303231Sdim const FunctionRecord &Function) { 615303231Sdim SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 616303231Sdim for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 617303231Sdim if (SourceFile == Function.Filenames[I]) 618303231Sdim FilenameEquivalence[I] = true; 619303231Sdim return FilenameEquivalence; 620303231Sdim} 621303231Sdim 622303231Sdim/// Return the ID of the file where the definition of the function is located. 623303231Sdimstatic Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) { 624303231Sdim SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 625303231Sdim for (const auto &CR : Function.CountedRegions) 626303231Sdim if (CR.Kind == CounterMappingRegion::ExpansionRegion) 627303231Sdim IsNotExpandedFile[CR.ExpandedFileID] = false; 628303231Sdim int I = IsNotExpandedFile.find_first(); 629303231Sdim if (I == -1) 630303231Sdim return None; 631303231Sdim return I; 632303231Sdim} 633303231Sdim 634303231Sdim/// Check if SourceFile is the file that contains the definition of 635303231Sdim/// the Function. Return the ID of the file in that case or None otherwise. 636303231Sdimstatic Optional<unsigned> findMainViewFileID(StringRef SourceFile, 637303231Sdim const FunctionRecord &Function) { 638303231Sdim Optional<unsigned> I = findMainViewFileID(Function); 639303231Sdim if (I && SourceFile == Function.Filenames[*I]) 640303231Sdim return I; 641303231Sdim return None; 642303231Sdim} 643303231Sdim 644303231Sdimstatic bool isExpansion(const CountedRegion &R, unsigned FileID) { 645303231Sdim return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 646303231Sdim} 647303231Sdim 648303231SdimCoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { 649303231Sdim CoverageData FileCoverage(Filename); 650321369Sdim std::vector<CountedRegion> Regions; 651303231Sdim 652360784Sdim // Look up the function records in the given file. Due to hash collisions on 653360784Sdim // the filename, we may get back some records that are not in the file. 654360784Sdim ArrayRef<unsigned> RecordIndices = 655360784Sdim getImpreciseRecordIndicesForFilename(Filename); 656360784Sdim for (unsigned RecordIndex : RecordIndices) { 657360784Sdim const FunctionRecord &Function = Functions[RecordIndex]; 658303231Sdim auto MainFileID = findMainViewFileID(Filename, Function); 659303231Sdim auto FileIDs = gatherFileIDs(Filename, Function); 660303231Sdim for (const auto &CR : Function.CountedRegions) 661303231Sdim if (FileIDs.test(CR.FileID)) { 662303231Sdim Regions.push_back(CR); 663303231Sdim if (MainFileID && isExpansion(CR, *MainFileID)) 664303231Sdim FileCoverage.Expansions.emplace_back(CR, Function); 665303231Sdim } 666303231Sdim } 667303231Sdim 668341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 669303231Sdim FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); 670303231Sdim 671303231Sdim return FileCoverage; 672303231Sdim} 673303231Sdim 674327952Sdimstd::vector<InstantiationGroup> 675327952SdimCoverageMapping::getInstantiationGroups(StringRef Filename) const { 676303231Sdim FunctionInstantiationSetCollector InstantiationSetCollector; 677360784Sdim // Look up the function records in the given file. Due to hash collisions on 678360784Sdim // the filename, we may get back some records that are not in the file. 679360784Sdim ArrayRef<unsigned> RecordIndices = 680360784Sdim getImpreciseRecordIndicesForFilename(Filename); 681360784Sdim for (unsigned RecordIndex : RecordIndices) { 682360784Sdim const FunctionRecord &Function = Functions[RecordIndex]; 683303231Sdim auto MainFileID = findMainViewFileID(Filename, Function); 684303231Sdim if (!MainFileID) 685303231Sdim continue; 686303231Sdim InstantiationSetCollector.insert(Function, *MainFileID); 687303231Sdim } 688303231Sdim 689327952Sdim std::vector<InstantiationGroup> Result; 690327952Sdim for (auto &InstantiationSet : InstantiationSetCollector) { 691327952Sdim InstantiationGroup IG{InstantiationSet.first.first, 692327952Sdim InstantiationSet.first.second, 693327952Sdim std::move(InstantiationSet.second)}; 694327952Sdim Result.emplace_back(std::move(IG)); 695303231Sdim } 696303231Sdim return Result; 697303231Sdim} 698303231Sdim 699303231SdimCoverageData 700303231SdimCoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { 701303231Sdim auto MainFileID = findMainViewFileID(Function); 702303231Sdim if (!MainFileID) 703303231Sdim return CoverageData(); 704303231Sdim 705303231Sdim CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 706321369Sdim std::vector<CountedRegion> Regions; 707303231Sdim for (const auto &CR : Function.CountedRegions) 708303231Sdim if (CR.FileID == *MainFileID) { 709303231Sdim Regions.push_back(CR); 710303231Sdim if (isExpansion(CR, *MainFileID)) 711303231Sdim FunctionCoverage.Expansions.emplace_back(CR, Function); 712303231Sdim } 713303231Sdim 714341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name 715341825Sdim << "\n"); 716303231Sdim FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 717303231Sdim 718303231Sdim return FunctionCoverage; 719303231Sdim} 720303231Sdim 721303231SdimCoverageData CoverageMapping::getCoverageForExpansion( 722303231Sdim const ExpansionRecord &Expansion) const { 723303231Sdim CoverageData ExpansionCoverage( 724303231Sdim Expansion.Function.Filenames[Expansion.FileID]); 725321369Sdim std::vector<CountedRegion> Regions; 726303231Sdim for (const auto &CR : Expansion.Function.CountedRegions) 727303231Sdim if (CR.FileID == Expansion.FileID) { 728303231Sdim Regions.push_back(CR); 729303231Sdim if (isExpansion(CR, Expansion.FileID)) 730303231Sdim ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 731303231Sdim } 732303231Sdim 733341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " 734341825Sdim << Expansion.FileID << "\n"); 735303231Sdim ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 736303231Sdim 737303231Sdim return ExpansionCoverage; 738303231Sdim} 739303231Sdim 740327952SdimLineCoverageStats::LineCoverageStats( 741327952Sdim ArrayRef<const CoverageSegment *> LineSegments, 742327952Sdim const CoverageSegment *WrappedSegment, unsigned Line) 743327952Sdim : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), 744327952Sdim LineSegments(LineSegments), WrappedSegment(WrappedSegment) { 745327952Sdim // Find the minimum number of regions which start in this line. 746327952Sdim unsigned MinRegionCount = 0; 747327952Sdim auto isStartOfRegion = [](const CoverageSegment *S) { 748327952Sdim return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; 749327952Sdim }; 750327952Sdim for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) 751327952Sdim if (isStartOfRegion(LineSegments[I])) 752327952Sdim ++MinRegionCount; 753327952Sdim 754327952Sdim bool StartOfSkippedRegion = !LineSegments.empty() && 755327952Sdim !LineSegments.front()->HasCount && 756327952Sdim LineSegments.front()->IsRegionEntry; 757327952Sdim 758327952Sdim HasMultipleRegions = MinRegionCount > 1; 759327952Sdim Mapped = 760327952Sdim !StartOfSkippedRegion && 761327952Sdim ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); 762327952Sdim 763327952Sdim if (!Mapped) 764327952Sdim return; 765327952Sdim 766327952Sdim // Pick the max count from the non-gap, region entry segments and the 767327952Sdim // wrapped count. 768327952Sdim if (WrappedSegment) 769327952Sdim ExecutionCount = WrappedSegment->Count; 770327952Sdim if (!MinRegionCount) 771327952Sdim return; 772327952Sdim for (const auto *LS : LineSegments) 773327952Sdim if (isStartOfRegion(LS)) 774327952Sdim ExecutionCount = std::max(ExecutionCount, LS->Count); 775327952Sdim} 776327952Sdim 777327952SdimLineCoverageIterator &LineCoverageIterator::operator++() { 778327952Sdim if (Next == CD.end()) { 779327952Sdim Stats = LineCoverageStats(); 780327952Sdim Ended = true; 781327952Sdim return *this; 782327952Sdim } 783327952Sdim if (Segments.size()) 784327952Sdim WrappedSegment = Segments.back(); 785327952Sdim Segments.clear(); 786327952Sdim while (Next != CD.end() && Next->Line == Line) 787327952Sdim Segments.push_back(&*Next++); 788327952Sdim Stats = LineCoverageStats(Segments, WrappedSegment, Line); 789327952Sdim ++Line; 790327952Sdim return *this; 791327952Sdim} 792327952Sdim 793321369Sdimstatic std::string getCoverageMapErrString(coveragemap_error Err) { 794303231Sdim switch (Err) { 795303231Sdim case coveragemap_error::success: 796303231Sdim return "Success"; 797303231Sdim case coveragemap_error::eof: 798303231Sdim return "End of File"; 799303231Sdim case coveragemap_error::no_data_found: 800303231Sdim return "No coverage data found"; 801303231Sdim case coveragemap_error::unsupported_version: 802303231Sdim return "Unsupported coverage format version"; 803303231Sdim case coveragemap_error::truncated: 804303231Sdim return "Truncated coverage data"; 805303231Sdim case coveragemap_error::malformed: 806303231Sdim return "Malformed coverage data"; 807303231Sdim } 808303231Sdim llvm_unreachable("A value of coveragemap_error has no message."); 809303231Sdim} 810303231Sdim 811321369Sdimnamespace { 812321369Sdim 813303231Sdim// FIXME: This class is only here to support the transition to llvm::Error. It 814303231Sdim// will be removed once this transition is complete. Clients should prefer to 815303231Sdim// deal with the Error value directly, rather than converting to error_code. 816303231Sdimclass CoverageMappingErrorCategoryType : public std::error_category { 817314564Sdim const char *name() const noexcept override { return "llvm.coveragemap"; } 818303231Sdim std::string message(int IE) const override { 819303231Sdim return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); 820303231Sdim } 821303231Sdim}; 822321369Sdim 823303231Sdim} // end anonymous namespace 824303231Sdim 825303231Sdimstd::string CoverageMapError::message() const { 826303231Sdim return getCoverageMapErrString(Err); 827303231Sdim} 828303231Sdim 829303231Sdimstatic ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory; 830303231Sdim 831303231Sdimconst std::error_category &llvm::coverage::coveragemap_category() { 832303231Sdim return *ErrorCategory; 833303231Sdim} 834303231Sdim 835303231Sdimchar CoverageMapError::ID = 0; 836