1 //===- CoverageMapping.cpp - Code coverage mapping support ----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains support for clang's and llvm's instrumentation based 10 // code coverage. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/ProfileData/Coverage/CoverageMapping.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/SmallBitVector.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/StringRef.h" 20 #include "llvm/Object/BuildID.h" 21 #include "llvm/ProfileData/Coverage/CoverageMappingReader.h" 22 #include "llvm/ProfileData/InstrProfReader.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/Errc.h" 25 #include "llvm/Support/Error.h" 26 #include "llvm/Support/ErrorHandling.h" 27 #include "llvm/Support/MemoryBuffer.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include <algorithm> 30 #include <cassert> 31 #include <cstdint> 32 #include <iterator> 33 #include <map> 34 #include <memory> 35 #include <optional> 36 #include <string> 37 #include <system_error> 38 #include <utility> 39 #include <vector> 40 41 using namespace llvm; 42 using namespace coverage; 43 44 #define DEBUG_TYPE "coverage-mapping" 45 46 Counter CounterExpressionBuilder::get(const CounterExpression &E) { 47 auto It = ExpressionIndices.find(E); 48 if (It != ExpressionIndices.end()) 49 return Counter::getExpression(It->second); 50 unsigned I = Expressions.size(); 51 Expressions.push_back(E); 52 ExpressionIndices[E] = I; 53 return Counter::getExpression(I); 54 } 55 56 void CounterExpressionBuilder::extractTerms(Counter C, int Factor, 57 SmallVectorImpl<Term> &Terms) { 58 switch (C.getKind()) { 59 case Counter::Zero: 60 break; 61 case Counter::CounterValueReference: 62 Terms.emplace_back(C.getCounterID(), Factor); 63 break; 64 case Counter::Expression: 65 const auto &E = Expressions[C.getExpressionID()]; 66 extractTerms(E.LHS, Factor, Terms); 67 extractTerms( 68 E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms); 69 break; 70 } 71 } 72 73 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { 74 // Gather constant terms. 75 SmallVector<Term, 32> Terms; 76 extractTerms(ExpressionTree, +1, Terms); 77 78 // If there are no terms, this is just a zero. The algorithm below assumes at 79 // least one term. 80 if (Terms.size() == 0) 81 return Counter::getZero(); 82 83 // Group the terms by counter ID. 84 llvm::sort(Terms, [](const Term &LHS, const Term &RHS) { 85 return LHS.CounterID < RHS.CounterID; 86 }); 87 88 // Combine terms by counter ID to eliminate counters that sum to zero. 89 auto Prev = Terms.begin(); 90 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) { 91 if (I->CounterID == Prev->CounterID) { 92 Prev->Factor += I->Factor; 93 continue; 94 } 95 ++Prev; 96 *Prev = *I; 97 } 98 Terms.erase(++Prev, Terms.end()); 99 100 Counter C; 101 // Create additions. We do this before subtractions to avoid constructs like 102 // ((0 - X) + Y), as opposed to (Y - X). 103 for (auto T : Terms) { 104 if (T.Factor <= 0) 105 continue; 106 for (int I = 0; I < T.Factor; ++I) 107 if (C.isZero()) 108 C = Counter::getCounter(T.CounterID); 109 else 110 C = get(CounterExpression(CounterExpression::Add, C, 111 Counter::getCounter(T.CounterID))); 112 } 113 114 // Create subtractions. 115 for (auto T : Terms) { 116 if (T.Factor >= 0) 117 continue; 118 for (int I = 0; I < -T.Factor; ++I) 119 C = get(CounterExpression(CounterExpression::Subtract, C, 120 Counter::getCounter(T.CounterID))); 121 } 122 return C; 123 } 124 125 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) { 126 auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS)); 127 return Simplify ? simplify(Cnt) : Cnt; 128 } 129 130 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS, 131 bool Simplify) { 132 auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS)); 133 return Simplify ? simplify(Cnt) : Cnt; 134 } 135 136 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { 137 switch (C.getKind()) { 138 case Counter::Zero: 139 OS << '0'; 140 return; 141 case Counter::CounterValueReference: 142 OS << '#' << C.getCounterID(); 143 break; 144 case Counter::Expression: { 145 if (C.getExpressionID() >= Expressions.size()) 146 return; 147 const auto &E = Expressions[C.getExpressionID()]; 148 OS << '('; 149 dump(E.LHS, OS); 150 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + "); 151 dump(E.RHS, OS); 152 OS << ')'; 153 break; 154 } 155 } 156 if (CounterValues.empty()) 157 return; 158 Expected<int64_t> Value = evaluate(C); 159 if (auto E = Value.takeError()) { 160 consumeError(std::move(E)); 161 return; 162 } 163 OS << '[' << *Value << ']'; 164 } 165 166 Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { 167 switch (C.getKind()) { 168 case Counter::Zero: 169 return 0; 170 case Counter::CounterValueReference: 171 if (C.getCounterID() >= CounterValues.size()) 172 return errorCodeToError(errc::argument_out_of_domain); 173 return CounterValues[C.getCounterID()]; 174 case Counter::Expression: { 175 if (C.getExpressionID() >= Expressions.size()) 176 return errorCodeToError(errc::argument_out_of_domain); 177 const auto &E = Expressions[C.getExpressionID()]; 178 Expected<int64_t> LHS = evaluate(E.LHS); 179 if (!LHS) 180 return LHS; 181 Expected<int64_t> RHS = evaluate(E.RHS); 182 if (!RHS) 183 return RHS; 184 return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS; 185 } 186 } 187 llvm_unreachable("Unhandled CounterKind"); 188 } 189 190 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const { 191 switch (C.getKind()) { 192 case Counter::Zero: 193 return 0; 194 case Counter::CounterValueReference: 195 return C.getCounterID(); 196 case Counter::Expression: { 197 if (C.getExpressionID() >= Expressions.size()) 198 return 0; 199 const auto &E = Expressions[C.getExpressionID()]; 200 return std::max(getMaxCounterID(E.LHS), getMaxCounterID(E.RHS)); 201 } 202 } 203 llvm_unreachable("Unhandled CounterKind"); 204 } 205 206 void FunctionRecordIterator::skipOtherFiles() { 207 while (Current != Records.end() && !Filename.empty() && 208 Filename != Current->Filenames[0]) 209 ++Current; 210 if (Current == Records.end()) 211 *this = FunctionRecordIterator(); 212 } 213 214 ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename( 215 StringRef Filename) const { 216 size_t FilenameHash = hash_value(Filename); 217 auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash); 218 if (RecordIt == FilenameHash2RecordIndices.end()) 219 return {}; 220 return RecordIt->second; 221 } 222 223 static unsigned getMaxCounterID(const CounterMappingContext &Ctx, 224 const CoverageMappingRecord &Record) { 225 unsigned MaxCounterID = 0; 226 for (const auto &Region : Record.MappingRegions) { 227 MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count)); 228 } 229 return MaxCounterID; 230 } 231 232 Error CoverageMapping::loadFunctionRecord( 233 const CoverageMappingRecord &Record, 234 IndexedInstrProfReader &ProfileReader) { 235 StringRef OrigFuncName = Record.FunctionName; 236 if (OrigFuncName.empty()) 237 return make_error<CoverageMapError>(coveragemap_error::malformed); 238 239 if (Record.Filenames.empty()) 240 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); 241 else 242 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); 243 244 CounterMappingContext Ctx(Record.Expressions); 245 246 std::vector<uint64_t> Counts; 247 if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, 248 Record.FunctionHash, Counts)) { 249 instrprof_error IPE = InstrProfError::take(std::move(E)); 250 if (IPE == instrprof_error::hash_mismatch) { 251 FuncHashMismatches.emplace_back(std::string(Record.FunctionName), 252 Record.FunctionHash); 253 return Error::success(); 254 } else if (IPE != instrprof_error::unknown_function) 255 return make_error<InstrProfError>(IPE); 256 Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0); 257 } 258 Ctx.setCounts(Counts); 259 260 assert(!Record.MappingRegions.empty() && "Function has no regions"); 261 262 // This coverage record is a zero region for a function that's unused in 263 // some TU, but used in a different TU. Ignore it. The coverage maps from the 264 // the other TU will either be loaded (providing full region counts) or they 265 // won't (in which case we don't unintuitively report functions as uncovered 266 // when they have non-zero counts in the profile). 267 if (Record.MappingRegions.size() == 1 && 268 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0) 269 return Error::success(); 270 271 FunctionRecord Function(OrigFuncName, Record.Filenames); 272 for (const auto &Region : Record.MappingRegions) { 273 Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); 274 if (auto E = ExecutionCount.takeError()) { 275 consumeError(std::move(E)); 276 return Error::success(); 277 } 278 Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount); 279 if (auto E = AltExecutionCount.takeError()) { 280 consumeError(std::move(E)); 281 return Error::success(); 282 } 283 Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount); 284 } 285 286 // Don't create records for (filenames, function) pairs we've already seen. 287 auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), 288 Record.Filenames.end()); 289 if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) 290 return Error::success(); 291 292 Functions.push_back(std::move(Function)); 293 294 // Performance optimization: keep track of the indices of the function records 295 // which correspond to each filename. This can be used to substantially speed 296 // up queries for coverage info in a file. 297 unsigned RecordIndex = Functions.size() - 1; 298 for (StringRef Filename : Record.Filenames) { 299 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)]; 300 // Note that there may be duplicates in the filename set for a function 301 // record, because of e.g. macro expansions in the function in which both 302 // the macro and the function are defined in the same file. 303 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex) 304 RecordIndices.push_back(RecordIndex); 305 } 306 307 return Error::success(); 308 } 309 310 // This function is for memory optimization by shortening the lifetimes 311 // of CoverageMappingReader instances. 312 Error CoverageMapping::loadFromReaders( 313 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 314 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) { 315 for (const auto &CoverageReader : CoverageReaders) { 316 for (auto RecordOrErr : *CoverageReader) { 317 if (Error E = RecordOrErr.takeError()) 318 return E; 319 const auto &Record = *RecordOrErr; 320 if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader)) 321 return E; 322 } 323 } 324 return Error::success(); 325 } 326 327 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( 328 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 329 IndexedInstrProfReader &ProfileReader) { 330 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 331 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage)) 332 return std::move(E); 333 return std::move(Coverage); 334 } 335 336 // If E is a no_data_found error, returns success. Otherwise returns E. 337 static Error handleMaybeNoDataFoundError(Error E) { 338 return handleErrors( 339 std::move(E), [](const CoverageMapError &CME) { 340 if (CME.get() == coveragemap_error::no_data_found) 341 return static_cast<Error>(Error::success()); 342 return make_error<CoverageMapError>(CME.get()); 343 }); 344 } 345 346 Error CoverageMapping::loadFromFile( 347 StringRef Filename, StringRef Arch, StringRef CompilationDir, 348 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage, 349 bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) { 350 auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN( 351 Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false); 352 if (std::error_code EC = CovMappingBufOrErr.getError()) 353 return createFileError(Filename, errorCodeToError(EC)); 354 MemoryBufferRef CovMappingBufRef = 355 CovMappingBufOrErr.get()->getMemBufferRef(); 356 SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; 357 358 SmallVector<object::BuildIDRef> BinaryIDs; 359 auto CoverageReadersOrErr = BinaryCoverageReader::create( 360 CovMappingBufRef, Arch, Buffers, CompilationDir, 361 FoundBinaryIDs ? &BinaryIDs : nullptr); 362 if (Error E = CoverageReadersOrErr.takeError()) { 363 E = handleMaybeNoDataFoundError(std::move(E)); 364 if (E) 365 return createFileError(Filename, std::move(E)); 366 return E; 367 } 368 369 SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; 370 for (auto &Reader : CoverageReadersOrErr.get()) 371 Readers.push_back(std::move(Reader)); 372 if (FoundBinaryIDs && !Readers.empty()) { 373 llvm::append_range(*FoundBinaryIDs, 374 llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) { 375 return object::BuildID(BID); 376 })); 377 } 378 DataFound |= !Readers.empty(); 379 if (Error E = loadFromReaders(Readers, ProfileReader, Coverage)) 380 return createFileError(Filename, std::move(E)); 381 return Error::success(); 382 } 383 384 Expected<std::unique_ptr<CoverageMapping>> 385 CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, 386 StringRef ProfileFilename, ArrayRef<StringRef> Arches, 387 StringRef CompilationDir, 388 const object::BuildIDFetcher *BIDFetcher) { 389 auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); 390 if (Error E = ProfileReaderOrErr.takeError()) 391 return createFileError(ProfileFilename, std::move(E)); 392 auto ProfileReader = std::move(ProfileReaderOrErr.get()); 393 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); 394 bool DataFound = false; 395 396 auto GetArch = [&](size_t Idx) { 397 if (Arches.empty()) 398 return StringRef(); 399 if (Arches.size() == 1) 400 return Arches.front(); 401 return Arches[Idx]; 402 }; 403 404 SmallVector<object::BuildID> FoundBinaryIDs; 405 for (const auto &File : llvm::enumerate(ObjectFilenames)) { 406 if (Error E = 407 loadFromFile(File.value(), GetArch(File.index()), CompilationDir, 408 *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs)) 409 return std::move(E); 410 } 411 412 if (BIDFetcher) { 413 std::vector<object::BuildID> ProfileBinaryIDs; 414 if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs)) 415 return createFileError(ProfileFilename, std::move(E)); 416 417 SmallVector<object::BuildIDRef> BinaryIDsToFetch; 418 if (!ProfileBinaryIDs.empty()) { 419 const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) { 420 return std::lexicographical_compare(A.begin(), A.end(), B.begin(), 421 B.end()); 422 }; 423 llvm::sort(FoundBinaryIDs, Compare); 424 std::set_difference( 425 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(), 426 FoundBinaryIDs.begin(), FoundBinaryIDs.end(), 427 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare); 428 } 429 430 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) { 431 std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID); 432 if (!PathOpt) 433 continue; 434 std::string Path = std::move(*PathOpt); 435 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef(); 436 if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader, 437 *Coverage, DataFound)) 438 return std::move(E); 439 } 440 } 441 442 if (!DataFound) 443 return createFileError( 444 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "), 445 make_error<CoverageMapError>(coveragemap_error::no_data_found)); 446 return std::move(Coverage); 447 } 448 449 namespace { 450 451 /// Distributes functions into instantiation sets. 452 /// 453 /// An instantiation set is a collection of functions that have the same source 454 /// code, ie, template functions specializations. 455 class FunctionInstantiationSetCollector { 456 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; 457 MapT InstantiatedFunctions; 458 459 public: 460 void insert(const FunctionRecord &Function, unsigned FileID) { 461 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 462 while (I != E && I->FileID != FileID) 463 ++I; 464 assert(I != E && "function does not cover the given file"); 465 auto &Functions = InstantiatedFunctions[I->startLoc()]; 466 Functions.push_back(&Function); 467 } 468 469 MapT::iterator begin() { return InstantiatedFunctions.begin(); } 470 MapT::iterator end() { return InstantiatedFunctions.end(); } 471 }; 472 473 class SegmentBuilder { 474 std::vector<CoverageSegment> &Segments; 475 SmallVector<const CountedRegion *, 8> ActiveRegions; 476 477 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} 478 479 /// Emit a segment with the count from \p Region starting at \p StartLoc. 480 // 481 /// \p IsRegionEntry: The segment is at the start of a new non-gap region. 482 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. 483 void startSegment(const CountedRegion &Region, LineColPair StartLoc, 484 bool IsRegionEntry, bool EmitSkippedRegion = false) { 485 bool HasCount = !EmitSkippedRegion && 486 (Region.Kind != CounterMappingRegion::SkippedRegion); 487 488 // If the new segment wouldn't affect coverage rendering, skip it. 489 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { 490 const auto &Last = Segments.back(); 491 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && 492 !Last.IsRegionEntry) 493 return; 494 } 495 496 if (HasCount) 497 Segments.emplace_back(StartLoc.first, StartLoc.second, 498 Region.ExecutionCount, IsRegionEntry, 499 Region.Kind == CounterMappingRegion::GapRegion); 500 else 501 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); 502 503 LLVM_DEBUG({ 504 const auto &Last = Segments.back(); 505 dbgs() << "Segment at " << Last.Line << ":" << Last.Col 506 << " (count = " << Last.Count << ")" 507 << (Last.IsRegionEntry ? ", RegionEntry" : "") 508 << (!Last.HasCount ? ", Skipped" : "") 509 << (Last.IsGapRegion ? ", Gap" : "") << "\n"; 510 }); 511 } 512 513 /// Emit segments for active regions which end before \p Loc. 514 /// 515 /// \p Loc: The start location of the next region. If std::nullopt, all active 516 /// regions are completed. 517 /// \p FirstCompletedRegion: Index of the first completed region. 518 void completeRegionsUntil(std::optional<LineColPair> Loc, 519 unsigned FirstCompletedRegion) { 520 // Sort the completed regions by end location. This makes it simple to 521 // emit closing segments in sorted order. 522 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; 523 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), 524 [](const CountedRegion *L, const CountedRegion *R) { 525 return L->endLoc() < R->endLoc(); 526 }); 527 528 // Emit segments for all completed regions. 529 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; 530 ++I) { 531 const auto *CompletedRegion = ActiveRegions[I]; 532 assert((!Loc || CompletedRegion->endLoc() <= *Loc) && 533 "Completed region ends after start of new region"); 534 535 const auto *PrevCompletedRegion = ActiveRegions[I - 1]; 536 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); 537 538 // Don't emit any more segments if they start where the new region begins. 539 if (Loc && CompletedSegmentLoc == *Loc) 540 break; 541 542 // Don't emit a segment if the next completed region ends at the same 543 // location as this one. 544 if (CompletedSegmentLoc == CompletedRegion->endLoc()) 545 continue; 546 547 // Use the count from the last completed region which ends at this loc. 548 for (unsigned J = I + 1; J < E; ++J) 549 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) 550 CompletedRegion = ActiveRegions[J]; 551 552 startSegment(*CompletedRegion, CompletedSegmentLoc, false); 553 } 554 555 auto Last = ActiveRegions.back(); 556 if (FirstCompletedRegion && Last->endLoc() != *Loc) { 557 // If there's a gap after the end of the last completed region and the 558 // start of the new region, use the last active region to fill the gap. 559 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), 560 false); 561 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { 562 // Emit a skipped segment if there are no more active regions. This 563 // ensures that gaps between functions are marked correctly. 564 startSegment(*Last, Last->endLoc(), false, true); 565 } 566 567 // Pop the completed regions. 568 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); 569 } 570 571 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { 572 for (const auto &CR : enumerate(Regions)) { 573 auto CurStartLoc = CR.value().startLoc(); 574 575 // Active regions which end before the current region need to be popped. 576 auto CompletedRegions = 577 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), 578 [&](const CountedRegion *Region) { 579 return !(Region->endLoc() <= CurStartLoc); 580 }); 581 if (CompletedRegions != ActiveRegions.end()) { 582 unsigned FirstCompletedRegion = 583 std::distance(ActiveRegions.begin(), CompletedRegions); 584 completeRegionsUntil(CurStartLoc, FirstCompletedRegion); 585 } 586 587 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; 588 589 // Try to emit a segment for the current region. 590 if (CurStartLoc == CR.value().endLoc()) { 591 // Avoid making zero-length regions active. If it's the last region, 592 // emit a skipped segment. Otherwise use its predecessor's count. 593 const bool Skipped = 594 (CR.index() + 1) == Regions.size() || 595 CR.value().Kind == CounterMappingRegion::SkippedRegion; 596 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), 597 CurStartLoc, !GapRegion, Skipped); 598 // If it is skipped segment, create a segment with last pushed 599 // regions's count at CurStartLoc. 600 if (Skipped && !ActiveRegions.empty()) 601 startSegment(*ActiveRegions.back(), CurStartLoc, false); 602 continue; 603 } 604 if (CR.index() + 1 == Regions.size() || 605 CurStartLoc != Regions[CR.index() + 1].startLoc()) { 606 // Emit a segment if the next region doesn't start at the same location 607 // as this one. 608 startSegment(CR.value(), CurStartLoc, !GapRegion); 609 } 610 611 // This region is active (i.e not completed). 612 ActiveRegions.push_back(&CR.value()); 613 } 614 615 // Complete any remaining active regions. 616 if (!ActiveRegions.empty()) 617 completeRegionsUntil(std::nullopt, 0); 618 } 619 620 /// Sort a nested sequence of regions from a single file. 621 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { 622 llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { 623 if (LHS.startLoc() != RHS.startLoc()) 624 return LHS.startLoc() < RHS.startLoc(); 625 if (LHS.endLoc() != RHS.endLoc()) 626 // When LHS completely contains RHS, we sort LHS first. 627 return RHS.endLoc() < LHS.endLoc(); 628 // If LHS and RHS cover the same area, we need to sort them according 629 // to their kinds so that the most suitable region will become "active" 630 // in combineRegions(). Because we accumulate counter values only from 631 // regions of the same kind as the first region of the area, prefer 632 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. 633 static_assert(CounterMappingRegion::CodeRegion < 634 CounterMappingRegion::ExpansionRegion && 635 CounterMappingRegion::ExpansionRegion < 636 CounterMappingRegion::SkippedRegion, 637 "Unexpected order of region kind values"); 638 return LHS.Kind < RHS.Kind; 639 }); 640 } 641 642 /// Combine counts of regions which cover the same area. 643 static ArrayRef<CountedRegion> 644 combineRegions(MutableArrayRef<CountedRegion> Regions) { 645 if (Regions.empty()) 646 return Regions; 647 auto Active = Regions.begin(); 648 auto End = Regions.end(); 649 for (auto I = Regions.begin() + 1; I != End; ++I) { 650 if (Active->startLoc() != I->startLoc() || 651 Active->endLoc() != I->endLoc()) { 652 // Shift to the next region. 653 ++Active; 654 if (Active != I) 655 *Active = *I; 656 continue; 657 } 658 // Merge duplicate region. 659 // If CodeRegions and ExpansionRegions cover the same area, it's probably 660 // a macro which is fully expanded to another macro. In that case, we need 661 // to accumulate counts only from CodeRegions, or else the area will be 662 // counted twice. 663 // On the other hand, a macro may have a nested macro in its body. If the 664 // outer macro is used several times, the ExpansionRegion for the nested 665 // macro will also be added several times. These ExpansionRegions cover 666 // the same source locations and have to be combined to reach the correct 667 // value for that area. 668 // We add counts of the regions of the same kind as the active region 669 // to handle the both situations. 670 if (I->Kind == Active->Kind) 671 Active->ExecutionCount += I->ExecutionCount; 672 } 673 return Regions.drop_back(std::distance(++Active, End)); 674 } 675 676 public: 677 /// Build a sorted list of CoverageSegments from a list of Regions. 678 static std::vector<CoverageSegment> 679 buildSegments(MutableArrayRef<CountedRegion> Regions) { 680 std::vector<CoverageSegment> Segments; 681 SegmentBuilder Builder(Segments); 682 683 sortNestedRegions(Regions); 684 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); 685 686 LLVM_DEBUG({ 687 dbgs() << "Combined regions:\n"; 688 for (const auto &CR : CombinedRegions) 689 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " 690 << CR.LineEnd << ":" << CR.ColumnEnd 691 << " (count=" << CR.ExecutionCount << ")\n"; 692 }); 693 694 Builder.buildSegmentsImpl(CombinedRegions); 695 696 #ifndef NDEBUG 697 for (unsigned I = 1, E = Segments.size(); I < E; ++I) { 698 const auto &L = Segments[I - 1]; 699 const auto &R = Segments[I]; 700 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { 701 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount) 702 continue; 703 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col 704 << " followed by " << R.Line << ":" << R.Col << "\n"); 705 assert(false && "Coverage segments not unique or sorted"); 706 } 707 } 708 #endif 709 710 return Segments; 711 } 712 }; 713 714 } // end anonymous namespace 715 716 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 717 std::vector<StringRef> Filenames; 718 for (const auto &Function : getCoveredFunctions()) 719 llvm::append_range(Filenames, Function.Filenames); 720 llvm::sort(Filenames); 721 auto Last = std::unique(Filenames.begin(), Filenames.end()); 722 Filenames.erase(Last, Filenames.end()); 723 return Filenames; 724 } 725 726 static SmallBitVector gatherFileIDs(StringRef SourceFile, 727 const FunctionRecord &Function) { 728 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 729 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 730 if (SourceFile == Function.Filenames[I]) 731 FilenameEquivalence[I] = true; 732 return FilenameEquivalence; 733 } 734 735 /// Return the ID of the file where the definition of the function is located. 736 static std::optional<unsigned> 737 findMainViewFileID(const FunctionRecord &Function) { 738 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 739 for (const auto &CR : Function.CountedRegions) 740 if (CR.Kind == CounterMappingRegion::ExpansionRegion) 741 IsNotExpandedFile[CR.ExpandedFileID] = false; 742 int I = IsNotExpandedFile.find_first(); 743 if (I == -1) 744 return std::nullopt; 745 return I; 746 } 747 748 /// Check if SourceFile is the file that contains the definition of 749 /// the Function. Return the ID of the file in that case or std::nullopt 750 /// otherwise. 751 static std::optional<unsigned> 752 findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) { 753 std::optional<unsigned> I = findMainViewFileID(Function); 754 if (I && SourceFile == Function.Filenames[*I]) 755 return I; 756 return std::nullopt; 757 } 758 759 static bool isExpansion(const CountedRegion &R, unsigned FileID) { 760 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 761 } 762 763 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { 764 CoverageData FileCoverage(Filename); 765 std::vector<CountedRegion> Regions; 766 767 // Look up the function records in the given file. Due to hash collisions on 768 // the filename, we may get back some records that are not in the file. 769 ArrayRef<unsigned> RecordIndices = 770 getImpreciseRecordIndicesForFilename(Filename); 771 for (unsigned RecordIndex : RecordIndices) { 772 const FunctionRecord &Function = Functions[RecordIndex]; 773 auto MainFileID = findMainViewFileID(Filename, Function); 774 auto FileIDs = gatherFileIDs(Filename, Function); 775 for (const auto &CR : Function.CountedRegions) 776 if (FileIDs.test(CR.FileID)) { 777 Regions.push_back(CR); 778 if (MainFileID && isExpansion(CR, *MainFileID)) 779 FileCoverage.Expansions.emplace_back(CR, Function); 780 } 781 // Capture branch regions specific to the function (excluding expansions). 782 for (const auto &CR : Function.CountedBranchRegions) 783 if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID)) 784 FileCoverage.BranchRegions.push_back(CR); 785 } 786 787 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 788 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); 789 790 return FileCoverage; 791 } 792 793 std::vector<InstantiationGroup> 794 CoverageMapping::getInstantiationGroups(StringRef Filename) const { 795 FunctionInstantiationSetCollector InstantiationSetCollector; 796 // Look up the function records in the given file. Due to hash collisions on 797 // the filename, we may get back some records that are not in the file. 798 ArrayRef<unsigned> RecordIndices = 799 getImpreciseRecordIndicesForFilename(Filename); 800 for (unsigned RecordIndex : RecordIndices) { 801 const FunctionRecord &Function = Functions[RecordIndex]; 802 auto MainFileID = findMainViewFileID(Filename, Function); 803 if (!MainFileID) 804 continue; 805 InstantiationSetCollector.insert(Function, *MainFileID); 806 } 807 808 std::vector<InstantiationGroup> Result; 809 for (auto &InstantiationSet : InstantiationSetCollector) { 810 InstantiationGroup IG{InstantiationSet.first.first, 811 InstantiationSet.first.second, 812 std::move(InstantiationSet.second)}; 813 Result.emplace_back(std::move(IG)); 814 } 815 return Result; 816 } 817 818 CoverageData 819 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { 820 auto MainFileID = findMainViewFileID(Function); 821 if (!MainFileID) 822 return CoverageData(); 823 824 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 825 std::vector<CountedRegion> Regions; 826 for (const auto &CR : Function.CountedRegions) 827 if (CR.FileID == *MainFileID) { 828 Regions.push_back(CR); 829 if (isExpansion(CR, *MainFileID)) 830 FunctionCoverage.Expansions.emplace_back(CR, Function); 831 } 832 // Capture branch regions specific to the function (excluding expansions). 833 for (const auto &CR : Function.CountedBranchRegions) 834 if (CR.FileID == *MainFileID) 835 FunctionCoverage.BranchRegions.push_back(CR); 836 837 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name 838 << "\n"); 839 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 840 841 return FunctionCoverage; 842 } 843 844 CoverageData CoverageMapping::getCoverageForExpansion( 845 const ExpansionRecord &Expansion) const { 846 CoverageData ExpansionCoverage( 847 Expansion.Function.Filenames[Expansion.FileID]); 848 std::vector<CountedRegion> Regions; 849 for (const auto &CR : Expansion.Function.CountedRegions) 850 if (CR.FileID == Expansion.FileID) { 851 Regions.push_back(CR); 852 if (isExpansion(CR, Expansion.FileID)) 853 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 854 } 855 for (const auto &CR : Expansion.Function.CountedBranchRegions) 856 // Capture branch regions that only pertain to the corresponding expansion. 857 if (CR.FileID == Expansion.FileID) 858 ExpansionCoverage.BranchRegions.push_back(CR); 859 860 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " 861 << Expansion.FileID << "\n"); 862 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 863 864 return ExpansionCoverage; 865 } 866 867 LineCoverageStats::LineCoverageStats( 868 ArrayRef<const CoverageSegment *> LineSegments, 869 const CoverageSegment *WrappedSegment, unsigned Line) 870 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), 871 LineSegments(LineSegments), WrappedSegment(WrappedSegment) { 872 // Find the minimum number of regions which start in this line. 873 unsigned MinRegionCount = 0; 874 auto isStartOfRegion = [](const CoverageSegment *S) { 875 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; 876 }; 877 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) 878 if (isStartOfRegion(LineSegments[I])) 879 ++MinRegionCount; 880 881 bool StartOfSkippedRegion = !LineSegments.empty() && 882 !LineSegments.front()->HasCount && 883 LineSegments.front()->IsRegionEntry; 884 885 HasMultipleRegions = MinRegionCount > 1; 886 Mapped = 887 !StartOfSkippedRegion && 888 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); 889 890 if (!Mapped) 891 return; 892 893 // Pick the max count from the non-gap, region entry segments and the 894 // wrapped count. 895 if (WrappedSegment) 896 ExecutionCount = WrappedSegment->Count; 897 if (!MinRegionCount) 898 return; 899 for (const auto *LS : LineSegments) 900 if (isStartOfRegion(LS)) 901 ExecutionCount = std::max(ExecutionCount, LS->Count); 902 } 903 904 LineCoverageIterator &LineCoverageIterator::operator++() { 905 if (Next == CD.end()) { 906 Stats = LineCoverageStats(); 907 Ended = true; 908 return *this; 909 } 910 if (Segments.size()) 911 WrappedSegment = Segments.back(); 912 Segments.clear(); 913 while (Next != CD.end() && Next->Line == Line) 914 Segments.push_back(&*Next++); 915 Stats = LineCoverageStats(Segments, WrappedSegment, Line); 916 ++Line; 917 return *this; 918 } 919 920 static std::string getCoverageMapErrString(coveragemap_error Err) { 921 switch (Err) { 922 case coveragemap_error::success: 923 return "Success"; 924 case coveragemap_error::eof: 925 return "End of File"; 926 case coveragemap_error::no_data_found: 927 return "No coverage data found"; 928 case coveragemap_error::unsupported_version: 929 return "Unsupported coverage format version"; 930 case coveragemap_error::truncated: 931 return "Truncated coverage data"; 932 case coveragemap_error::malformed: 933 return "Malformed coverage data"; 934 case coveragemap_error::decompression_failed: 935 return "Failed to decompress coverage data (zlib)"; 936 case coveragemap_error::invalid_or_missing_arch_specifier: 937 return "`-arch` specifier is invalid or missing for universal binary"; 938 } 939 llvm_unreachable("A value of coveragemap_error has no message."); 940 } 941 942 namespace { 943 944 // FIXME: This class is only here to support the transition to llvm::Error. It 945 // will be removed once this transition is complete. Clients should prefer to 946 // deal with the Error value directly, rather than converting to error_code. 947 class CoverageMappingErrorCategoryType : public std::error_category { 948 const char *name() const noexcept override { return "llvm.coveragemap"; } 949 std::string message(int IE) const override { 950 return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); 951 } 952 }; 953 954 } // end anonymous namespace 955 956 std::string CoverageMapError::message() const { 957 return getCoverageMapErrString(Err); 958 } 959 960 const std::error_category &llvm::coverage::coveragemap_category() { 961 static CoverageMappingErrorCategoryType ErrorCategory; 962 return ErrorCategory; 963 } 964 965 char CoverageMapError::ID = 0; 966