CoverageMapping.cpp revision 344779
1321369Sdim//===- CoverageMapping.cpp - Code coverage mapping support ----------------===// 2303231Sdim// 3303231Sdim// The LLVM Compiler Infrastructure 4303231Sdim// 5303231Sdim// This file is distributed under the University of Illinois Open Source 6303231Sdim// License. See LICENSE.TXT for details. 7303231Sdim// 8303231Sdim//===----------------------------------------------------------------------===// 9303231Sdim// 10303231Sdim// This file contains support for clang's and llvm's instrumentation based 11303231Sdim// code coverage. 12303231Sdim// 13303231Sdim//===----------------------------------------------------------------------===// 14303231Sdim 15303231Sdim#include "llvm/ProfileData/Coverage/CoverageMapping.h" 16321369Sdim#include "llvm/ADT/ArrayRef.h" 17303231Sdim#include "llvm/ADT/DenseMap.h" 18321369Sdim#include "llvm/ADT/None.h" 19303231Sdim#include "llvm/ADT/Optional.h" 20303231Sdim#include "llvm/ADT/SmallBitVector.h" 21321369Sdim#include "llvm/ADT/SmallVector.h" 22321369Sdim#include "llvm/ADT/StringRef.h" 23303231Sdim#include "llvm/ProfileData/Coverage/CoverageMappingReader.h" 24303231Sdim#include "llvm/ProfileData/InstrProfReader.h" 25303231Sdim#include "llvm/Support/Debug.h" 26303231Sdim#include "llvm/Support/Errc.h" 27321369Sdim#include "llvm/Support/Error.h" 28303231Sdim#include "llvm/Support/ErrorHandling.h" 29303231Sdim#include "llvm/Support/ManagedStatic.h" 30321369Sdim#include "llvm/Support/MemoryBuffer.h" 31303231Sdim#include "llvm/Support/raw_ostream.h" 32321369Sdim#include <algorithm> 33321369Sdim#include <cassert> 34321369Sdim#include <cstdint> 35321369Sdim#include <iterator> 36327952Sdim#include <map> 37321369Sdim#include <memory> 38321369Sdim#include <string> 39321369Sdim#include <system_error> 40321369Sdim#include <utility> 41321369Sdim#include <vector> 42303231Sdim 43303231Sdimusing namespace llvm; 44303231Sdimusing namespace coverage; 45303231Sdim 46303231Sdim#define DEBUG_TYPE "coverage-mapping" 47303231Sdim 48303231SdimCounter CounterExpressionBuilder::get(const CounterExpression &E) { 49303231Sdim auto It = ExpressionIndices.find(E); 50303231Sdim if (It != ExpressionIndices.end()) 51303231Sdim return Counter::getExpression(It->second); 52303231Sdim unsigned I = Expressions.size(); 53303231Sdim Expressions.push_back(E); 54303231Sdim ExpressionIndices[E] = I; 55303231Sdim return Counter::getExpression(I); 56303231Sdim} 57303231Sdim 58321369Sdimvoid CounterExpressionBuilder::extractTerms(Counter C, int Factor, 59321369Sdim SmallVectorImpl<Term> &Terms) { 60303231Sdim switch (C.getKind()) { 61303231Sdim case Counter::Zero: 62303231Sdim break; 63303231Sdim case Counter::CounterValueReference: 64321369Sdim Terms.emplace_back(C.getCounterID(), Factor); 65303231Sdim break; 66303231Sdim case Counter::Expression: 67303231Sdim const auto &E = Expressions[C.getExpressionID()]; 68321369Sdim extractTerms(E.LHS, Factor, Terms); 69321369Sdim extractTerms( 70321369Sdim E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); 71303231Sdim break; 72303231Sdim } 73303231Sdim} 74303231Sdim 75303231SdimCounter CounterExpressionBuilder::simplify(Counter ExpressionTree) { 76303231Sdim // Gather constant terms. 77321369Sdim SmallVector<Term, 32> Terms; 78303231Sdim extractTerms(ExpressionTree, +1, Terms); 79303231Sdim 80303231Sdim // If there are no terms, this is just a zero. The algorithm below assumes at 81303231Sdim // least one term. 82303231Sdim if (Terms.size() == 0) 83303231Sdim return Counter::getZero(); 84303231Sdim 85303231Sdim // Group the terms by counter ID. 86344779Sdim llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { 87321369Sdim return LHS.CounterID < RHS.CounterID; 88303231Sdim }); 89303231Sdim 90303231Sdim // Combine terms by counter ID to eliminate counters that sum to zero. 91303231Sdim auto Prev = Terms.begin(); 92303231Sdim for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { 93321369Sdim if (I->CounterID == Prev->CounterID) { 94321369Sdim Prev->Factor += I->Factor; 95303231Sdim continue; 96303231Sdim } 97303231Sdim ++Prev; 98303231Sdim *Prev = *I; 99303231Sdim } 100303231Sdim Terms.erase(++Prev, Terms.end()); 101303231Sdim 102303231Sdim Counter C; 103303231Sdim // Create additions. We do this before subtractions to avoid constructs like 104303231Sdim // ((0 - X) + Y), as opposed to (Y - X). 105321369Sdim for (auto T : Terms) { 106321369Sdim if (T.Factor <= 0) 107303231Sdim continue; 108321369Sdim for (int I = 0; I < T.Factor; ++I) 109303231Sdim if (C.isZero()) 110321369Sdim C = Counter::getCounter(T.CounterID); 111303231Sdim else 112303231Sdim C = get(CounterExpression(CounterExpression::Add, C, 113321369Sdim Counter::getCounter(T.CounterID))); 114303231Sdim } 115303231Sdim 116303231Sdim // Create subtractions. 117321369Sdim for (auto T : Terms) { 118321369Sdim if (T.Factor >= 0) 119303231Sdim continue; 120321369Sdim for (int I = 0; I < -T.Factor; ++I) 121303231Sdim C = get(CounterExpression(CounterExpression::Subtract, C, 122321369Sdim Counter::getCounter(T.CounterID))); 123303231Sdim } 124303231Sdim return C; 125303231Sdim} 126303231Sdim 127303231SdimCounter CounterExpressionBuilder::add(Counter LHS, Counter RHS) { 128303231Sdim return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS))); 129303231Sdim} 130303231Sdim 131303231SdimCounter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) { 132303231Sdim return simplify( 133303231Sdim get(CounterExpression(CounterExpression::Subtract, LHS, RHS))); 134303231Sdim} 135303231Sdim 136321369Sdimvoid CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { 137303231Sdim switch (C.getKind()) { 138303231Sdim case Counter::Zero: 139303231Sdim OS << '0'; 140303231Sdim return; 141303231Sdim case Counter::CounterValueReference: 142303231Sdim OS << '#' << C.getCounterID(); 143303231Sdim break; 144303231Sdim case Counter::Expression: { 145303231Sdim if (C.getExpressionID() >= Expressions.size()) 146303231Sdim return; 147303231Sdim const auto &E = Expressions[C.getExpressionID()]; 148303231Sdim OS << '('; 149303231Sdim dump(E.LHS, OS); 150303231Sdim OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); 151303231Sdim dump(E.RHS, OS); 152303231Sdim OS << ')'; 153303231Sdim break; 154303231Sdim } 155303231Sdim } 156303231Sdim if (CounterValues.empty()) 157303231Sdim return; 158303231Sdim Expected<int64_t> Value = evaluate(C); 159303231Sdim if (auto E = Value.takeError()) { 160321369Sdim consumeError(std::move(E)); 161303231Sdim return; 162303231Sdim } 163303231Sdim OS << '[' << *Value << ']'; 164303231Sdim} 165303231Sdim 166303231SdimExpected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { 167303231Sdim switch (C.getKind()) { 168303231Sdim case Counter::Zero: 169303231Sdim return 0; 170303231Sdim case Counter::CounterValueReference: 171303231Sdim if (C.getCounterID() >= CounterValues.size()) 172303231Sdim return errorCodeToError(errc::argument_out_of_domain); 173303231Sdim return CounterValues[C.getCounterID()]; 174303231Sdim case Counter::Expression: { 175303231Sdim if (C.getExpressionID() >= Expressions.size()) 176303231Sdim return errorCodeToError(errc::argument_out_of_domain); 177303231Sdim const auto &E = Expressions[C.getExpressionID()]; 178303231Sdim Expected<int64_t> LHS = evaluate(E.LHS); 179303231Sdim if (!LHS) 180303231Sdim return LHS; 181303231Sdim Expected<int64_t> RHS = evaluate(E.RHS); 182303231Sdim if (!RHS) 183303231Sdim return RHS; 184303231Sdim return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS; 185303231Sdim } 186303231Sdim } 187303231Sdim llvm_unreachable("Unhandled CounterKind"); 188303231Sdim} 189303231Sdim 190303231Sdimvoid FunctionRecordIterator::skipOtherFiles() { 191303231Sdim while (Current != Records.end() && !Filename.empty() && 192303231Sdim Filename != Current->Filenames[0]) 193303231Sdim ++Current; 194303231Sdim if (Current == Records.end()) 195303231Sdim *this = FunctionRecordIterator(); 196303231Sdim} 197303231Sdim 198314564SdimError CoverageMapping::loadFunctionRecord( 199314564Sdim const CoverageMappingRecord &Record, 200314564Sdim IndexedInstrProfReader &ProfileReader) { 201314564Sdim StringRef OrigFuncName = Record.FunctionName; 202321369Sdim if (OrigFuncName.empty()) 203321369Sdim return make_error<CoverageMapError>(coveragemap_error::malformed); 204321369Sdim 205314564Sdim if (Record.Filenames.empty()) 206314564Sdim OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); 207314564Sdim else 208314564Sdim OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); 209314564Sdim 210314564Sdim CounterMappingContext Ctx(Record.Expressions); 211314564Sdim 212314564Sdim std::vector<uint64_t> Counts; 213314564Sdim if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, 214314564Sdim Record.FunctionHash, Counts)) { 215314564Sdim instrprof_error IPE = InstrProfError::take(std::move(E)); 216314564Sdim if (IPE == instrprof_error::hash_mismatch) { 217327952Sdim FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash); 218314564Sdim return Error::success(); 219314564Sdim } else if (IPE != instrprof_error::unknown_function) 220314564Sdim return make_error<InstrProfError>(IPE); 221314564Sdim Counts.assign(Record.MappingRegions.size(), 0); 222314564Sdim } 223314564Sdim Ctx.setCounts(Counts); 224314564Sdim 225314564Sdim assert(!Record.MappingRegions.empty() && "Function has no regions"); 226314564Sdim 227344779Sdim // This coverage record is a zero region for a function that's unused in 228344779Sdim // some TU, but used in a different TU. Ignore it. The coverage maps from the 229344779Sdim // the other TU will either be loaded (providing full region counts) or they 230344779Sdim // won't (in which case we don't unintuitively report functions as uncovered 231344779Sdim // when they have non-zero counts in the profile). 232344779Sdim if (Record.MappingRegions.size() == 1 && 233344779Sdim Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) 234344779Sdim return Error::success(); 235344779Sdim 236314564Sdim FunctionRecord Function(OrigFuncName, Record.Filenames); 237314564Sdim for (const auto &Region : Record.MappingRegions) { 238314564Sdim Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); 239314564Sdim if (auto E = ExecutionCount.takeError()) { 240321369Sdim consumeError(std::move(E)); 241314564Sdim return Error::success(); 242314564Sdim } 243314564Sdim Function.pushRegion(Region, *ExecutionCount); 244314564Sdim } 245344779Sdim 246344779Sdim // Don't create records for (filenames, function) pairs we've already seen. 247344779Sdim auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), 248344779Sdim Record.Filenames.end()); 249344779Sdim if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) 250314564Sdim return Error::success(); 251314564Sdim 252314564Sdim Functions.push_back(std::move(Function)); 253314564Sdim return Error::success(); 254314564Sdim} 255314564Sdim 256314564SdimExpected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( 257314564Sdim ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 258314564Sdim IndexedInstrProfReader &ProfileReader) { 259314564Sdim auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 260303231Sdim 261327952Sdim for (const auto &CoverageReader : CoverageReaders) { 262327952Sdim for (auto RecordOrErr : *CoverageReader) { 263327952Sdim if (Error E = RecordOrErr.takeError()) 264327952Sdim return std::move(E); 265327952Sdim const auto &Record = *RecordOrErr; 266314564Sdim if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader)) 267314564Sdim return std::move(E); 268327952Sdim } 269327952Sdim } 270303231Sdim 271303231Sdim return std::move(Coverage); 272303231Sdim} 273303231Sdim 274303231SdimExpected<std::unique_ptr<CoverageMapping>> 275314564SdimCoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, 276327952Sdim StringRef ProfileFilename, ArrayRef<StringRef> Arches) { 277303231Sdim auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); 278303231Sdim if (Error E = ProfileReaderOrErr.takeError()) 279303231Sdim return std::move(E); 280303231Sdim auto ProfileReader = std::move(ProfileReaderOrErr.get()); 281314564Sdim 282314564Sdim SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; 283314564Sdim SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; 284327952Sdim for (const auto &File : llvm::enumerate(ObjectFilenames)) { 285327952Sdim auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value()); 286314564Sdim if (std::error_code EC = CovMappingBufOrErr.getError()) 287314564Sdim return errorCodeToError(EC); 288327952Sdim StringRef Arch = Arches.empty() ? StringRef() : Arches[File.index()]; 289314564Sdim auto CoverageReaderOrErr = 290314564Sdim BinaryCoverageReader::create(CovMappingBufOrErr.get(), Arch); 291314564Sdim if (Error E = CoverageReaderOrErr.takeError()) 292314564Sdim return std::move(E); 293314564Sdim Readers.push_back(std::move(CoverageReaderOrErr.get())); 294314564Sdim Buffers.push_back(std::move(CovMappingBufOrErr.get())); 295314564Sdim } 296314564Sdim return load(Readers, *ProfileReader); 297303231Sdim} 298303231Sdim 299303231Sdimnamespace { 300321369Sdim 301341825Sdim/// Distributes functions into instantiation sets. 302303231Sdim/// 303303231Sdim/// An instantiation set is a collection of functions that have the same source 304303231Sdim/// code, ie, template functions specializations. 305303231Sdimclass FunctionInstantiationSetCollector { 306327952Sdim using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; 307303231Sdim MapT InstantiatedFunctions; 308303231Sdim 309303231Sdimpublic: 310303231Sdim void insert(const FunctionRecord &Function, unsigned FileID) { 311303231Sdim auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 312303231Sdim while (I != E && I->FileID != FileID) 313303231Sdim ++I; 314303231Sdim assert(I != E && "function does not cover the given file"); 315303231Sdim auto &Functions = InstantiatedFunctions[I->startLoc()]; 316303231Sdim Functions.push_back(&Function); 317303231Sdim } 318303231Sdim 319303231Sdim MapT::iterator begin() { return InstantiatedFunctions.begin(); } 320303231Sdim MapT::iterator end() { return InstantiatedFunctions.end(); } 321303231Sdim}; 322303231Sdim 323303231Sdimclass SegmentBuilder { 324303231Sdim std::vector<CoverageSegment> &Segments; 325303231Sdim SmallVector<const CountedRegion *, 8> ActiveRegions; 326303231Sdim 327303231Sdim SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} 328303231Sdim 329327952Sdim /// Emit a segment with the count from \p Region starting at \p StartLoc. 330327952Sdim // 331327952Sdim /// \p IsRegionEntry: The segment is at the start of a new non-gap region. 332327952Sdim /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. 333327952Sdim void startSegment(const CountedRegion &Region, LineColPair StartLoc, 334327952Sdim bool IsRegionEntry, bool EmitSkippedRegion = false) { 335327952Sdim bool HasCount = !EmitSkippedRegion && 336327952Sdim (Region.Kind != CounterMappingRegion::SkippedRegion); 337303231Sdim 338327952Sdim // If the new segment wouldn't affect coverage rendering, skip it. 339327952Sdim if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { 340327952Sdim const auto &Last = Segments.back(); 341327952Sdim if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && 342327952Sdim !Last.IsRegionEntry) 343327952Sdim return; 344327952Sdim } 345303231Sdim 346327952Sdim if (HasCount) 347327952Sdim Segments.emplace_back(StartLoc.first, StartLoc.second, 348327952Sdim Region.ExecutionCount, IsRegionEntry, 349327952Sdim Region.Kind == CounterMappingRegion::GapRegion); 350327952Sdim else 351327952Sdim Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); 352327952Sdim 353341825Sdim LLVM_DEBUG({ 354327952Sdim const auto &Last = Segments.back(); 355327952Sdim dbgs() << "Segment at " << Last.Line << ":" << Last.Col 356327952Sdim << " (count = " << Last.Count << ")" 357327952Sdim << (Last.IsRegionEntry ? ", RegionEntry" : "") 358327952Sdim << (!Last.HasCount ? ", Skipped" : "") 359327952Sdim << (Last.IsGapRegion ? ", Gap" : "") << "\n"; 360327952Sdim }); 361303231Sdim } 362303231Sdim 363327952Sdim /// Emit segments for active regions which end before \p Loc. 364327952Sdim /// 365327952Sdim /// \p Loc: The start location of the next region. If None, all active 366327952Sdim /// regions are completed. 367327952Sdim /// \p FirstCompletedRegion: Index of the first completed region. 368327952Sdim void completeRegionsUntil(Optional<LineColPair> Loc, 369327952Sdim unsigned FirstCompletedRegion) { 370327952Sdim // Sort the completed regions by end location. This makes it simple to 371327952Sdim // emit closing segments in sorted order. 372327952Sdim auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; 373327952Sdim std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), 374327952Sdim [](const CountedRegion *L, const CountedRegion *R) { 375327952Sdim return L->endLoc() < R->endLoc(); 376327952Sdim }); 377327952Sdim 378327952Sdim // Emit segments for all completed regions. 379327952Sdim for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; 380327952Sdim ++I) { 381327952Sdim const auto *CompletedRegion = ActiveRegions[I]; 382327952Sdim assert((!Loc || CompletedRegion->endLoc() <= *Loc) && 383327952Sdim "Completed region ends after start of new region"); 384327952Sdim 385327952Sdim const auto *PrevCompletedRegion = ActiveRegions[I - 1]; 386327952Sdim auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); 387327952Sdim 388327952Sdim // Don't emit any more segments if they start where the new region begins. 389327952Sdim if (Loc && CompletedSegmentLoc == *Loc) 390327952Sdim break; 391327952Sdim 392327952Sdim // Don't emit a segment if the next completed region ends at the same 393327952Sdim // location as this one. 394327952Sdim if (CompletedSegmentLoc == CompletedRegion->endLoc()) 395327952Sdim continue; 396327952Sdim 397327952Sdim // Use the count from the last completed region which ends at this loc. 398327952Sdim for (unsigned J = I + 1; J < E; ++J) 399327952Sdim if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) 400327952Sdim CompletedRegion = ActiveRegions[J]; 401327952Sdim 402327952Sdim startSegment(*CompletedRegion, CompletedSegmentLoc, false); 403327952Sdim } 404327952Sdim 405327952Sdim auto Last = ActiveRegions.back(); 406327952Sdim if (FirstCompletedRegion && Last->endLoc() != *Loc) { 407327952Sdim // If there's a gap after the end of the last completed region and the 408327952Sdim // start of the new region, use the last active region to fill the gap. 409327952Sdim startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), 410327952Sdim false); 411327952Sdim } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { 412327952Sdim // Emit a skipped segment if there are no more active regions. This 413327952Sdim // ensures that gaps between functions are marked correctly. 414327952Sdim startSegment(*Last, Last->endLoc(), false, true); 415327952Sdim } 416327952Sdim 417327952Sdim // Pop the completed regions. 418327952Sdim ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); 419303231Sdim } 420303231Sdim 421303231Sdim void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { 422327952Sdim for (const auto &CR : enumerate(Regions)) { 423327952Sdim auto CurStartLoc = CR.value().startLoc(); 424327952Sdim 425327952Sdim // Active regions which end before the current region need to be popped. 426327952Sdim auto CompletedRegions = 427327952Sdim std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), 428327952Sdim [&](const CountedRegion *Region) { 429327952Sdim return !(Region->endLoc() <= CurStartLoc); 430327952Sdim }); 431327952Sdim if (CompletedRegions != ActiveRegions.end()) { 432327952Sdim unsigned FirstCompletedRegion = 433327952Sdim std::distance(ActiveRegions.begin(), CompletedRegions); 434327952Sdim completeRegionsUntil(CurStartLoc, FirstCompletedRegion); 435327952Sdim } 436327952Sdim 437327952Sdim bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; 438327952Sdim 439327952Sdim // Try to emit a segment for the current region. 440327952Sdim if (CurStartLoc == CR.value().endLoc()) { 441327952Sdim // Avoid making zero-length regions active. If it's the last region, 442327952Sdim // emit a skipped segment. Otherwise use its predecessor's count. 443327952Sdim const bool Skipped = (CR.index() + 1) == Regions.size(); 444327952Sdim startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), 445327952Sdim CurStartLoc, !GapRegion, Skipped); 446327952Sdim continue; 447327952Sdim } 448327952Sdim if (CR.index() + 1 == Regions.size() || 449327952Sdim CurStartLoc != Regions[CR.index() + 1].startLoc()) { 450327952Sdim // Emit a segment if the next region doesn't start at the same location 451327952Sdim // as this one. 452327952Sdim startSegment(CR.value(), CurStartLoc, !GapRegion); 453327952Sdim } 454327952Sdim 455327952Sdim // This region is active (i.e not completed). 456327952Sdim ActiveRegions.push_back(&CR.value()); 457303231Sdim } 458327952Sdim 459327952Sdim // Complete any remaining active regions. 460327952Sdim if (!ActiveRegions.empty()) 461327952Sdim completeRegionsUntil(None, 0); 462303231Sdim } 463303231Sdim 464303231Sdim /// Sort a nested sequence of regions from a single file. 465303231Sdim static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { 466344779Sdim llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { 467303231Sdim if (LHS.startLoc() != RHS.startLoc()) 468303231Sdim return LHS.startLoc() < RHS.startLoc(); 469303231Sdim if (LHS.endLoc() != RHS.endLoc()) 470303231Sdim // When LHS completely contains RHS, we sort LHS first. 471303231Sdim return RHS.endLoc() < LHS.endLoc(); 472303231Sdim // If LHS and RHS cover the same area, we need to sort them according 473303231Sdim // to their kinds so that the most suitable region will become "active" 474303231Sdim // in combineRegions(). Because we accumulate counter values only from 475303231Sdim // regions of the same kind as the first region of the area, prefer 476303231Sdim // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. 477321369Sdim static_assert(CounterMappingRegion::CodeRegion < 478321369Sdim CounterMappingRegion::ExpansionRegion && 479321369Sdim CounterMappingRegion::ExpansionRegion < 480321369Sdim CounterMappingRegion::SkippedRegion, 481303231Sdim "Unexpected order of region kind values"); 482303231Sdim return LHS.Kind < RHS.Kind; 483303231Sdim }); 484303231Sdim } 485303231Sdim 486303231Sdim /// Combine counts of regions which cover the same area. 487303231Sdim static ArrayRef<CountedRegion> 488303231Sdim combineRegions(MutableArrayRef<CountedRegion> Regions) { 489303231Sdim if (Regions.empty()) 490303231Sdim return Regions; 491303231Sdim auto Active = Regions.begin(); 492303231Sdim auto End = Regions.end(); 493303231Sdim for (auto I = Regions.begin() + 1; I != End; ++I) { 494303231Sdim if (Active->startLoc() != I->startLoc() || 495303231Sdim Active->endLoc() != I->endLoc()) { 496303231Sdim // Shift to the next region. 497303231Sdim ++Active; 498303231Sdim if (Active != I) 499303231Sdim *Active = *I; 500303231Sdim continue; 501303231Sdim } 502303231Sdim // Merge duplicate region. 503303231Sdim // If CodeRegions and ExpansionRegions cover the same area, it's probably 504303231Sdim // a macro which is fully expanded to another macro. In that case, we need 505303231Sdim // to accumulate counts only from CodeRegions, or else the area will be 506303231Sdim // counted twice. 507303231Sdim // On the other hand, a macro may have a nested macro in its body. If the 508303231Sdim // outer macro is used several times, the ExpansionRegion for the nested 509303231Sdim // macro will also be added several times. These ExpansionRegions cover 510303231Sdim // the same source locations and have to be combined to reach the correct 511303231Sdim // value for that area. 512303231Sdim // We add counts of the regions of the same kind as the active region 513303231Sdim // to handle the both situations. 514303231Sdim if (I->Kind == Active->Kind) 515303231Sdim Active->ExecutionCount += I->ExecutionCount; 516303231Sdim } 517303231Sdim return Regions.drop_back(std::distance(++Active, End)); 518303231Sdim } 519303231Sdim 520303231Sdimpublic: 521327952Sdim /// Build a sorted list of CoverageSegments from a list of Regions. 522303231Sdim static std::vector<CoverageSegment> 523303231Sdim buildSegments(MutableArrayRef<CountedRegion> Regions) { 524303231Sdim std::vector<CoverageSegment> Segments; 525303231Sdim SegmentBuilder Builder(Segments); 526303231Sdim 527303231Sdim sortNestedRegions(Regions); 528303231Sdim ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); 529303231Sdim 530341825Sdim LLVM_DEBUG({ 531327952Sdim dbgs() << "Combined regions:\n"; 532327952Sdim for (const auto &CR : CombinedRegions) 533327952Sdim dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " 534327952Sdim << CR.LineEnd << ":" << CR.ColumnEnd 535327952Sdim << " (count=" << CR.ExecutionCount << ")\n"; 536327952Sdim }); 537327952Sdim 538303231Sdim Builder.buildSegmentsImpl(CombinedRegions); 539327952Sdim 540327952Sdim#ifndef NDEBUG 541327952Sdim for (unsigned I = 1, E = Segments.size(); I < E; ++I) { 542327952Sdim const auto &L = Segments[I - 1]; 543327952Sdim const auto &R = Segments[I]; 544327952Sdim if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { 545341825Sdim LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col 546341825Sdim << " followed by " << R.Line << ":" << R.Col << "\n"); 547327952Sdim assert(false && "Coverage segments not unique or sorted"); 548327952Sdim } 549327952Sdim } 550327952Sdim#endif 551327952Sdim 552303231Sdim return Segments; 553303231Sdim } 554303231Sdim}; 555303231Sdim 556321369Sdim} // end anonymous namespace 557321369Sdim 558303231Sdimstd::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 559303231Sdim std::vector<StringRef> Filenames; 560303231Sdim for (const auto &Function : getCoveredFunctions()) 561303231Sdim Filenames.insert(Filenames.end(), Function.Filenames.begin(), 562303231Sdim Function.Filenames.end()); 563344779Sdim llvm::sort(Filenames); 564303231Sdim auto Last = std::unique(Filenames.begin(), Filenames.end()); 565303231Sdim Filenames.erase(Last, Filenames.end()); 566303231Sdim return Filenames; 567303231Sdim} 568303231Sdim 569303231Sdimstatic SmallBitVector gatherFileIDs(StringRef SourceFile, 570303231Sdim const FunctionRecord &Function) { 571303231Sdim SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 572303231Sdim for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 573303231Sdim if (SourceFile == Function.Filenames[I]) 574303231Sdim FilenameEquivalence[I] = true; 575303231Sdim return FilenameEquivalence; 576303231Sdim} 577303231Sdim 578303231Sdim/// Return the ID of the file where the definition of the function is located. 579303231Sdimstatic Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) { 580303231Sdim SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 581303231Sdim for (const auto &CR : Function.CountedRegions) 582303231Sdim if (CR.Kind == CounterMappingRegion::ExpansionRegion) 583303231Sdim IsNotExpandedFile[CR.ExpandedFileID] = false; 584303231Sdim int I = IsNotExpandedFile.find_first(); 585303231Sdim if (I == -1) 586303231Sdim return None; 587303231Sdim return I; 588303231Sdim} 589303231Sdim 590303231Sdim/// Check if SourceFile is the file that contains the definition of 591303231Sdim/// the Function. Return the ID of the file in that case or None otherwise. 592303231Sdimstatic Optional<unsigned> findMainViewFileID(StringRef SourceFile, 593303231Sdim const FunctionRecord &Function) { 594303231Sdim Optional<unsigned> I = findMainViewFileID(Function); 595303231Sdim if (I && SourceFile == Function.Filenames[*I]) 596303231Sdim return I; 597303231Sdim return None; 598303231Sdim} 599303231Sdim 600303231Sdimstatic bool isExpansion(const CountedRegion &R, unsigned FileID) { 601303231Sdim return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 602303231Sdim} 603303231Sdim 604303231SdimCoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { 605303231Sdim CoverageData FileCoverage(Filename); 606321369Sdim std::vector<CountedRegion> Regions; 607303231Sdim 608303231Sdim for (const auto &Function : Functions) { 609303231Sdim auto MainFileID = findMainViewFileID(Filename, Function); 610303231Sdim auto FileIDs = gatherFileIDs(Filename, Function); 611303231Sdim for (const auto &CR : Function.CountedRegions) 612303231Sdim if (FileIDs.test(CR.FileID)) { 613303231Sdim Regions.push_back(CR); 614303231Sdim if (MainFileID && isExpansion(CR, *MainFileID)) 615303231Sdim FileCoverage.Expansions.emplace_back(CR, Function); 616303231Sdim } 617303231Sdim } 618303231Sdim 619341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 620303231Sdim FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); 621303231Sdim 622303231Sdim return FileCoverage; 623303231Sdim} 624303231Sdim 625327952Sdimstd::vector<InstantiationGroup> 626327952SdimCoverageMapping::getInstantiationGroups(StringRef Filename) const { 627303231Sdim FunctionInstantiationSetCollector InstantiationSetCollector; 628303231Sdim for (const auto &Function : Functions) { 629303231Sdim auto MainFileID = findMainViewFileID(Filename, Function); 630303231Sdim if (!MainFileID) 631303231Sdim continue; 632303231Sdim InstantiationSetCollector.insert(Function, *MainFileID); 633303231Sdim } 634303231Sdim 635327952Sdim std::vector<InstantiationGroup> Result; 636327952Sdim for (auto &InstantiationSet : InstantiationSetCollector) { 637327952Sdim InstantiationGroup IG{InstantiationSet.first.first, 638327952Sdim InstantiationSet.first.second, 639327952Sdim std::move(InstantiationSet.second)}; 640327952Sdim Result.emplace_back(std::move(IG)); 641303231Sdim } 642303231Sdim return Result; 643303231Sdim} 644303231Sdim 645303231SdimCoverageData 646303231SdimCoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { 647303231Sdim auto MainFileID = findMainViewFileID(Function); 648303231Sdim if (!MainFileID) 649303231Sdim return CoverageData(); 650303231Sdim 651303231Sdim CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 652321369Sdim std::vector<CountedRegion> Regions; 653303231Sdim for (const auto &CR : Function.CountedRegions) 654303231Sdim if (CR.FileID == *MainFileID) { 655303231Sdim Regions.push_back(CR); 656303231Sdim if (isExpansion(CR, *MainFileID)) 657303231Sdim FunctionCoverage.Expansions.emplace_back(CR, Function); 658303231Sdim } 659303231Sdim 660341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name 661341825Sdim << "\n"); 662303231Sdim FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 663303231Sdim 664303231Sdim return FunctionCoverage; 665303231Sdim} 666303231Sdim 667303231SdimCoverageData CoverageMapping::getCoverageForExpansion( 668303231Sdim const ExpansionRecord &Expansion) const { 669303231Sdim CoverageData ExpansionCoverage( 670303231Sdim Expansion.Function.Filenames[Expansion.FileID]); 671321369Sdim std::vector<CountedRegion> Regions; 672303231Sdim for (const auto &CR : Expansion.Function.CountedRegions) 673303231Sdim if (CR.FileID == Expansion.FileID) { 674303231Sdim Regions.push_back(CR); 675303231Sdim if (isExpansion(CR, Expansion.FileID)) 676303231Sdim ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 677303231Sdim } 678303231Sdim 679341825Sdim LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " 680341825Sdim << Expansion.FileID << "\n"); 681303231Sdim ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 682303231Sdim 683303231Sdim return ExpansionCoverage; 684303231Sdim} 685303231Sdim 686327952SdimLineCoverageStats::LineCoverageStats( 687327952Sdim ArrayRef<const CoverageSegment *> LineSegments, 688327952Sdim const CoverageSegment *WrappedSegment, unsigned Line) 689327952Sdim : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), 690327952Sdim LineSegments(LineSegments), WrappedSegment(WrappedSegment) { 691327952Sdim // Find the minimum number of regions which start in this line. 692327952Sdim unsigned MinRegionCount = 0; 693327952Sdim auto isStartOfRegion = [](const CoverageSegment *S) { 694327952Sdim return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; 695327952Sdim }; 696327952Sdim for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) 697327952Sdim if (isStartOfRegion(LineSegments[I])) 698327952Sdim ++MinRegionCount; 699327952Sdim 700327952Sdim bool StartOfSkippedRegion = !LineSegments.empty() && 701327952Sdim !LineSegments.front()->HasCount && 702327952Sdim LineSegments.front()->IsRegionEntry; 703327952Sdim 704327952Sdim HasMultipleRegions = MinRegionCount > 1; 705327952Sdim Mapped = 706327952Sdim !StartOfSkippedRegion && 707327952Sdim ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); 708327952Sdim 709327952Sdim if (!Mapped) 710327952Sdim return; 711327952Sdim 712327952Sdim // Pick the max count from the non-gap, region entry segments and the 713327952Sdim // wrapped count. 714327952Sdim if (WrappedSegment) 715327952Sdim ExecutionCount = WrappedSegment->Count; 716327952Sdim if (!MinRegionCount) 717327952Sdim return; 718327952Sdim for (const auto *LS : LineSegments) 719327952Sdim if (isStartOfRegion(LS)) 720327952Sdim ExecutionCount = std::max(ExecutionCount, LS->Count); 721327952Sdim} 722327952Sdim 723327952SdimLineCoverageIterator &LineCoverageIterator::operator++() { 724327952Sdim if (Next == CD.end()) { 725327952Sdim Stats = LineCoverageStats(); 726327952Sdim Ended = true; 727327952Sdim return *this; 728327952Sdim } 729327952Sdim if (Segments.size()) 730327952Sdim WrappedSegment = Segments.back(); 731327952Sdim Segments.clear(); 732327952Sdim while (Next != CD.end() && Next->Line == Line) 733327952Sdim Segments.push_back(&*Next++); 734327952Sdim Stats = LineCoverageStats(Segments, WrappedSegment, Line); 735327952Sdim ++Line; 736327952Sdim return *this; 737327952Sdim} 738327952Sdim 739321369Sdimstatic std::string getCoverageMapErrString(coveragemap_error Err) { 740303231Sdim switch (Err) { 741303231Sdim case coveragemap_error::success: 742303231Sdim return "Success"; 743303231Sdim case coveragemap_error::eof: 744303231Sdim return "End of File"; 745303231Sdim case coveragemap_error::no_data_found: 746303231Sdim return "No coverage data found"; 747303231Sdim case coveragemap_error::unsupported_version: 748303231Sdim return "Unsupported coverage format version"; 749303231Sdim case coveragemap_error::truncated: 750303231Sdim return "Truncated coverage data"; 751303231Sdim case coveragemap_error::malformed: 752303231Sdim return "Malformed coverage data"; 753303231Sdim } 754303231Sdim llvm_unreachable("A value of coveragemap_error has no message."); 755303231Sdim} 756303231Sdim 757321369Sdimnamespace { 758321369Sdim 759303231Sdim// FIXME: This class is only here to support the transition to llvm::Error. It 760303231Sdim// will be removed once this transition is complete. Clients should prefer to 761303231Sdim// deal with the Error value directly, rather than converting to error_code. 762303231Sdimclass CoverageMappingErrorCategoryType : public std::error_category { 763314564Sdim const char *name() const noexcept override { return "llvm.coveragemap"; } 764303231Sdim std::string message(int IE) const override { 765303231Sdim return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); 766303231Sdim } 767303231Sdim}; 768321369Sdim 769303231Sdim} // end anonymous namespace 770303231Sdim 771303231Sdimstd::string CoverageMapError::message() const { 772303231Sdim return getCoverageMapErrString(Err); 773303231Sdim} 774303231Sdim 775303231Sdimstatic ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory; 776303231Sdim 777303231Sdimconst std::error_category &llvm::coverage::coveragemap_category() { 778303231Sdim return *ErrorCategory; 779303231Sdim} 780303231Sdim 781303231Sdimchar CoverageMapError::ID = 0; 782