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