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 const auto &CompareLT = [](object::BuildIDRef A, object::BuildIDRef B) { 414 return StringRef(reinterpret_cast<const char *>(A.data()), A.size()) < 415 StringRef(reinterpret_cast<const char *>(B.data()), B.size()); 416 }; 417 const auto &CompareEQ = [](object::BuildIDRef A, object::BuildIDRef B) { 418 return StringRef(reinterpret_cast<const char *>(A.data()), A.size()) == 419 StringRef(reinterpret_cast<const char *>(B.data()), B.size()); 420 }; 421 std::vector<object::BuildID> ProfileBinaryIDs; 422 if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs)) 423 return createFileError(ProfileFilename, std::move(E)); 424 llvm::sort(ProfileBinaryIDs, CompareLT); 425 ProfileBinaryIDs.erase(llvm::unique(ProfileBinaryIDs, CompareEQ), 426 ProfileBinaryIDs.end()); 427 428 SmallVector<object::BuildIDRef> BinaryIDsToFetch; 429 if (!ProfileBinaryIDs.empty()) { 430 llvm::sort(FoundBinaryIDs, CompareLT); 431 FoundBinaryIDs.erase(llvm::unique(FoundBinaryIDs, CompareEQ), 432 FoundBinaryIDs.end()); 433 std::set_difference( 434 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(), 435 FoundBinaryIDs.begin(), FoundBinaryIDs.end(), 436 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), CompareLT); 437 } 438 439 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) { 440 std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID); 441 if (!PathOpt) 442 continue; 443 std::string Path = std::move(*PathOpt); 444 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef(); 445 if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader, 446 *Coverage, DataFound)) 447 return std::move(E); 448 } 449 } 450 451 if (!DataFound) 452 return createFileError( 453 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "), 454 make_error<CoverageMapError>(coveragemap_error::no_data_found)); 455 return std::move(Coverage); 456 } 457 458 namespace { 459 460 /// Distributes functions into instantiation sets. 461 /// 462 /// An instantiation set is a collection of functions that have the same source 463 /// code, ie, template functions specializations. 464 class FunctionInstantiationSetCollector { 465 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; 466 MapT InstantiatedFunctions; 467 468 public: 469 void insert(const FunctionRecord &Function, unsigned FileID) { 470 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); 471 while (I != E && I->FileID != FileID) 472 ++I; 473 assert(I != E && "function does not cover the given file"); 474 auto &Functions = InstantiatedFunctions[I->startLoc()]; 475 Functions.push_back(&Function); 476 } 477 478 MapT::iterator begin() { return InstantiatedFunctions.begin(); } 479 MapT::iterator end() { return InstantiatedFunctions.end(); } 480 }; 481 482 class SegmentBuilder { 483 std::vector<CoverageSegment> &Segments; 484 SmallVector<const CountedRegion *, 8> ActiveRegions; 485 486 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} 487 488 /// Emit a segment with the count from \p Region starting at \p StartLoc. 489 // 490 /// \p IsRegionEntry: The segment is at the start of a new non-gap region. 491 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. 492 void startSegment(const CountedRegion &Region, LineColPair StartLoc, 493 bool IsRegionEntry, bool EmitSkippedRegion = false) { 494 bool HasCount = !EmitSkippedRegion && 495 (Region.Kind != CounterMappingRegion::SkippedRegion); 496 497 // If the new segment wouldn't affect coverage rendering, skip it. 498 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) { 499 const auto &Last = Segments.back(); 500 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount && 501 !Last.IsRegionEntry) 502 return; 503 } 504 505 if (HasCount) 506 Segments.emplace_back(StartLoc.first, StartLoc.second, 507 Region.ExecutionCount, IsRegionEntry, 508 Region.Kind == CounterMappingRegion::GapRegion); 509 else 510 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); 511 512 LLVM_DEBUG({ 513 const auto &Last = Segments.back(); 514 dbgs() << "Segment at " << Last.Line << ":" << Last.Col 515 << " (count = " << Last.Count << ")" 516 << (Last.IsRegionEntry ? ", RegionEntry" : "") 517 << (!Last.HasCount ? ", Skipped" : "") 518 << (Last.IsGapRegion ? ", Gap" : "") << "\n"; 519 }); 520 } 521 522 /// Emit segments for active regions which end before \p Loc. 523 /// 524 /// \p Loc: The start location of the next region. If std::nullopt, all active 525 /// regions are completed. 526 /// \p FirstCompletedRegion: Index of the first completed region. 527 void completeRegionsUntil(std::optional<LineColPair> Loc, 528 unsigned FirstCompletedRegion) { 529 // Sort the completed regions by end location. This makes it simple to 530 // emit closing segments in sorted order. 531 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; 532 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), 533 [](const CountedRegion *L, const CountedRegion *R) { 534 return L->endLoc() < R->endLoc(); 535 }); 536 537 // Emit segments for all completed regions. 538 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; 539 ++I) { 540 const auto *CompletedRegion = ActiveRegions[I]; 541 assert((!Loc || CompletedRegion->endLoc() <= *Loc) && 542 "Completed region ends after start of new region"); 543 544 const auto *PrevCompletedRegion = ActiveRegions[I - 1]; 545 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); 546 547 // Don't emit any more segments if they start where the new region begins. 548 if (Loc && CompletedSegmentLoc == *Loc) 549 break; 550 551 // Don't emit a segment if the next completed region ends at the same 552 // location as this one. 553 if (CompletedSegmentLoc == CompletedRegion->endLoc()) 554 continue; 555 556 // Use the count from the last completed region which ends at this loc. 557 for (unsigned J = I + 1; J < E; ++J) 558 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) 559 CompletedRegion = ActiveRegions[J]; 560 561 startSegment(*CompletedRegion, CompletedSegmentLoc, false); 562 } 563 564 auto Last = ActiveRegions.back(); 565 if (FirstCompletedRegion && Last->endLoc() != *Loc) { 566 // If there's a gap after the end of the last completed region and the 567 // start of the new region, use the last active region to fill the gap. 568 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), 569 false); 570 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) { 571 // Emit a skipped segment if there are no more active regions. This 572 // ensures that gaps between functions are marked correctly. 573 startSegment(*Last, Last->endLoc(), false, true); 574 } 575 576 // Pop the completed regions. 577 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); 578 } 579 580 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { 581 for (const auto &CR : enumerate(Regions)) { 582 auto CurStartLoc = CR.value().startLoc(); 583 584 // Active regions which end before the current region need to be popped. 585 auto CompletedRegions = 586 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), 587 [&](const CountedRegion *Region) { 588 return !(Region->endLoc() <= CurStartLoc); 589 }); 590 if (CompletedRegions != ActiveRegions.end()) { 591 unsigned FirstCompletedRegion = 592 std::distance(ActiveRegions.begin(), CompletedRegions); 593 completeRegionsUntil(CurStartLoc, FirstCompletedRegion); 594 } 595 596 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; 597 598 // Try to emit a segment for the current region. 599 if (CurStartLoc == CR.value().endLoc()) { 600 // Avoid making zero-length regions active. If it's the last region, 601 // emit a skipped segment. Otherwise use its predecessor's count. 602 const bool Skipped = 603 (CR.index() + 1) == Regions.size() || 604 CR.value().Kind == CounterMappingRegion::SkippedRegion; 605 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(), 606 CurStartLoc, !GapRegion, Skipped); 607 // If it is skipped segment, create a segment with last pushed 608 // regions's count at CurStartLoc. 609 if (Skipped && !ActiveRegions.empty()) 610 startSegment(*ActiveRegions.back(), CurStartLoc, false); 611 continue; 612 } 613 if (CR.index() + 1 == Regions.size() || 614 CurStartLoc != Regions[CR.index() + 1].startLoc()) { 615 // Emit a segment if the next region doesn't start at the same location 616 // as this one. 617 startSegment(CR.value(), CurStartLoc, !GapRegion); 618 } 619 620 // This region is active (i.e not completed). 621 ActiveRegions.push_back(&CR.value()); 622 } 623 624 // Complete any remaining active regions. 625 if (!ActiveRegions.empty()) 626 completeRegionsUntil(std::nullopt, 0); 627 } 628 629 /// Sort a nested sequence of regions from a single file. 630 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { 631 llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { 632 if (LHS.startLoc() != RHS.startLoc()) 633 return LHS.startLoc() < RHS.startLoc(); 634 if (LHS.endLoc() != RHS.endLoc()) 635 // When LHS completely contains RHS, we sort LHS first. 636 return RHS.endLoc() < LHS.endLoc(); 637 // If LHS and RHS cover the same area, we need to sort them according 638 // to their kinds so that the most suitable region will become "active" 639 // in combineRegions(). Because we accumulate counter values only from 640 // regions of the same kind as the first region of the area, prefer 641 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. 642 static_assert(CounterMappingRegion::CodeRegion < 643 CounterMappingRegion::ExpansionRegion && 644 CounterMappingRegion::ExpansionRegion < 645 CounterMappingRegion::SkippedRegion, 646 "Unexpected order of region kind values"); 647 return LHS.Kind < RHS.Kind; 648 }); 649 } 650 651 /// Combine counts of regions which cover the same area. 652 static ArrayRef<CountedRegion> 653 combineRegions(MutableArrayRef<CountedRegion> Regions) { 654 if (Regions.empty()) 655 return Regions; 656 auto Active = Regions.begin(); 657 auto End = Regions.end(); 658 for (auto I = Regions.begin() + 1; I != End; ++I) { 659 if (Active->startLoc() != I->startLoc() || 660 Active->endLoc() != I->endLoc()) { 661 // Shift to the next region. 662 ++Active; 663 if (Active != I) 664 *Active = *I; 665 continue; 666 } 667 // Merge duplicate region. 668 // If CodeRegions and ExpansionRegions cover the same area, it's probably 669 // a macro which is fully expanded to another macro. In that case, we need 670 // to accumulate counts only from CodeRegions, or else the area will be 671 // counted twice. 672 // On the other hand, a macro may have a nested macro in its body. If the 673 // outer macro is used several times, the ExpansionRegion for the nested 674 // macro will also be added several times. These ExpansionRegions cover 675 // the same source locations and have to be combined to reach the correct 676 // value for that area. 677 // We add counts of the regions of the same kind as the active region 678 // to handle the both situations. 679 if (I->Kind == Active->Kind) 680 Active->ExecutionCount += I->ExecutionCount; 681 } 682 return Regions.drop_back(std::distance(++Active, End)); 683 } 684 685 public: 686 /// Build a sorted list of CoverageSegments from a list of Regions. 687 static std::vector<CoverageSegment> 688 buildSegments(MutableArrayRef<CountedRegion> Regions) { 689 std::vector<CoverageSegment> Segments; 690 SegmentBuilder Builder(Segments); 691 692 sortNestedRegions(Regions); 693 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); 694 695 LLVM_DEBUG({ 696 dbgs() << "Combined regions:\n"; 697 for (const auto &CR : CombinedRegions) 698 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " 699 << CR.LineEnd << ":" << CR.ColumnEnd 700 << " (count=" << CR.ExecutionCount << ")\n"; 701 }); 702 703 Builder.buildSegmentsImpl(CombinedRegions); 704 705 #ifndef NDEBUG 706 for (unsigned I = 1, E = Segments.size(); I < E; ++I) { 707 const auto &L = Segments[I - 1]; 708 const auto &R = Segments[I]; 709 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { 710 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount) 711 continue; 712 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col 713 << " followed by " << R.Line << ":" << R.Col << "\n"); 714 assert(false && "Coverage segments not unique or sorted"); 715 } 716 } 717 #endif 718 719 return Segments; 720 } 721 }; 722 723 } // end anonymous namespace 724 725 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { 726 std::vector<StringRef> Filenames; 727 for (const auto &Function : getCoveredFunctions()) 728 llvm::append_range(Filenames, Function.Filenames); 729 llvm::sort(Filenames); 730 auto Last = std::unique(Filenames.begin(), Filenames.end()); 731 Filenames.erase(Last, Filenames.end()); 732 return Filenames; 733 } 734 735 static SmallBitVector gatherFileIDs(StringRef SourceFile, 736 const FunctionRecord &Function) { 737 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); 738 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I) 739 if (SourceFile == Function.Filenames[I]) 740 FilenameEquivalence[I] = true; 741 return FilenameEquivalence; 742 } 743 744 /// Return the ID of the file where the definition of the function is located. 745 static std::optional<unsigned> 746 findMainViewFileID(const FunctionRecord &Function) { 747 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); 748 for (const auto &CR : Function.CountedRegions) 749 if (CR.Kind == CounterMappingRegion::ExpansionRegion) 750 IsNotExpandedFile[CR.ExpandedFileID] = false; 751 int I = IsNotExpandedFile.find_first(); 752 if (I == -1) 753 return std::nullopt; 754 return I; 755 } 756 757 /// Check if SourceFile is the file that contains the definition of 758 /// the Function. Return the ID of the file in that case or std::nullopt 759 /// otherwise. 760 static std::optional<unsigned> 761 findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) { 762 std::optional<unsigned> I = findMainViewFileID(Function); 763 if (I && SourceFile == Function.Filenames[*I]) 764 return I; 765 return std::nullopt; 766 } 767 768 static bool isExpansion(const CountedRegion &R, unsigned FileID) { 769 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; 770 } 771 772 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { 773 CoverageData FileCoverage(Filename); 774 std::vector<CountedRegion> Regions; 775 776 // Look up the function records in the given file. Due to hash collisions on 777 // the filename, we may get back some records that are not in the file. 778 ArrayRef<unsigned> RecordIndices = 779 getImpreciseRecordIndicesForFilename(Filename); 780 for (unsigned RecordIndex : RecordIndices) { 781 const FunctionRecord &Function = Functions[RecordIndex]; 782 auto MainFileID = findMainViewFileID(Filename, Function); 783 auto FileIDs = gatherFileIDs(Filename, Function); 784 for (const auto &CR : Function.CountedRegions) 785 if (FileIDs.test(CR.FileID)) { 786 Regions.push_back(CR); 787 if (MainFileID && isExpansion(CR, *MainFileID)) 788 FileCoverage.Expansions.emplace_back(CR, Function); 789 } 790 // Capture branch regions specific to the function (excluding expansions). 791 for (const auto &CR : Function.CountedBranchRegions) 792 if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID)) 793 FileCoverage.BranchRegions.push_back(CR); 794 } 795 796 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); 797 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); 798 799 return FileCoverage; 800 } 801 802 std::vector<InstantiationGroup> 803 CoverageMapping::getInstantiationGroups(StringRef Filename) const { 804 FunctionInstantiationSetCollector InstantiationSetCollector; 805 // Look up the function records in the given file. Due to hash collisions on 806 // the filename, we may get back some records that are not in the file. 807 ArrayRef<unsigned> RecordIndices = 808 getImpreciseRecordIndicesForFilename(Filename); 809 for (unsigned RecordIndex : RecordIndices) { 810 const FunctionRecord &Function = Functions[RecordIndex]; 811 auto MainFileID = findMainViewFileID(Filename, Function); 812 if (!MainFileID) 813 continue; 814 InstantiationSetCollector.insert(Function, *MainFileID); 815 } 816 817 std::vector<InstantiationGroup> Result; 818 for (auto &InstantiationSet : InstantiationSetCollector) { 819 InstantiationGroup IG{InstantiationSet.first.first, 820 InstantiationSet.first.second, 821 std::move(InstantiationSet.second)}; 822 Result.emplace_back(std::move(IG)); 823 } 824 return Result; 825 } 826 827 CoverageData 828 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { 829 auto MainFileID = findMainViewFileID(Function); 830 if (!MainFileID) 831 return CoverageData(); 832 833 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); 834 std::vector<CountedRegion> Regions; 835 for (const auto &CR : Function.CountedRegions) 836 if (CR.FileID == *MainFileID) { 837 Regions.push_back(CR); 838 if (isExpansion(CR, *MainFileID)) 839 FunctionCoverage.Expansions.emplace_back(CR, Function); 840 } 841 // Capture branch regions specific to the function (excluding expansions). 842 for (const auto &CR : Function.CountedBranchRegions) 843 if (CR.FileID == *MainFileID) 844 FunctionCoverage.BranchRegions.push_back(CR); 845 846 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name 847 << "\n"); 848 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 849 850 return FunctionCoverage; 851 } 852 853 CoverageData CoverageMapping::getCoverageForExpansion( 854 const ExpansionRecord &Expansion) const { 855 CoverageData ExpansionCoverage( 856 Expansion.Function.Filenames[Expansion.FileID]); 857 std::vector<CountedRegion> Regions; 858 for (const auto &CR : Expansion.Function.CountedRegions) 859 if (CR.FileID == Expansion.FileID) { 860 Regions.push_back(CR); 861 if (isExpansion(CR, Expansion.FileID)) 862 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); 863 } 864 for (const auto &CR : Expansion.Function.CountedBranchRegions) 865 // Capture branch regions that only pertain to the corresponding expansion. 866 if (CR.FileID == Expansion.FileID) 867 ExpansionCoverage.BranchRegions.push_back(CR); 868 869 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " 870 << Expansion.FileID << "\n"); 871 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); 872 873 return ExpansionCoverage; 874 } 875 876 LineCoverageStats::LineCoverageStats( 877 ArrayRef<const CoverageSegment *> LineSegments, 878 const CoverageSegment *WrappedSegment, unsigned Line) 879 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), 880 LineSegments(LineSegments), WrappedSegment(WrappedSegment) { 881 // Find the minimum number of regions which start in this line. 882 unsigned MinRegionCount = 0; 883 auto isStartOfRegion = [](const CoverageSegment *S) { 884 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry; 885 }; 886 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I) 887 if (isStartOfRegion(LineSegments[I])) 888 ++MinRegionCount; 889 890 bool StartOfSkippedRegion = !LineSegments.empty() && 891 !LineSegments.front()->HasCount && 892 LineSegments.front()->IsRegionEntry; 893 894 HasMultipleRegions = MinRegionCount > 1; 895 Mapped = 896 !StartOfSkippedRegion && 897 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0)); 898 899 if (!Mapped) 900 return; 901 902 // Pick the max count from the non-gap, region entry segments and the 903 // wrapped count. 904 if (WrappedSegment) 905 ExecutionCount = WrappedSegment->Count; 906 if (!MinRegionCount) 907 return; 908 for (const auto *LS : LineSegments) 909 if (isStartOfRegion(LS)) 910 ExecutionCount = std::max(ExecutionCount, LS->Count); 911 } 912 913 LineCoverageIterator &LineCoverageIterator::operator++() { 914 if (Next == CD.end()) { 915 Stats = LineCoverageStats(); 916 Ended = true; 917 return *this; 918 } 919 if (Segments.size()) 920 WrappedSegment = Segments.back(); 921 Segments.clear(); 922 while (Next != CD.end() && Next->Line == Line) 923 Segments.push_back(&*Next++); 924 Stats = LineCoverageStats(Segments, WrappedSegment, Line); 925 ++Line; 926 return *this; 927 } 928 929 static std::string getCoverageMapErrString(coveragemap_error Err) { 930 switch (Err) { 931 case coveragemap_error::success: 932 return "Success"; 933 case coveragemap_error::eof: 934 return "End of File"; 935 case coveragemap_error::no_data_found: 936 return "No coverage data found"; 937 case coveragemap_error::unsupported_version: 938 return "Unsupported coverage format version"; 939 case coveragemap_error::truncated: 940 return "Truncated coverage data"; 941 case coveragemap_error::malformed: 942 return "Malformed coverage data"; 943 case coveragemap_error::decompression_failed: 944 return "Failed to decompress coverage data (zlib)"; 945 case coveragemap_error::invalid_or_missing_arch_specifier: 946 return "`-arch` specifier is invalid or missing for universal binary"; 947 } 948 llvm_unreachable("A value of coveragemap_error has no message."); 949 } 950 951 namespace { 952 953 // FIXME: This class is only here to support the transition to llvm::Error. It 954 // will be removed once this transition is complete. Clients should prefer to 955 // deal with the Error value directly, rather than converting to error_code. 956 class CoverageMappingErrorCategoryType : public std::error_category { 957 const char *name() const noexcept override { return "llvm.coveragemap"; } 958 std::string message(int IE) const override { 959 return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); 960 } 961 }; 962 963 } // end anonymous namespace 964 965 std::string CoverageMapError::message() const { 966 return getCoverageMapErrString(Err); 967 } 968 969 const std::error_category &llvm::coverage::coveragemap_category() { 970 static CoverageMappingErrorCategoryType ErrorCategory; 971 return ErrorCategory; 972 } 973 974 char CoverageMapError::ID = 0; 975