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