llvm/lib/ProfileData/Coverage/CoverageMapping.cpp

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