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