xref: /freebsd/contrib/llvm-project/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp (revision cb14a3fe5122c879eae1fb480ed7ce82a699ddb6)
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 <cmath>
34 #include <cstdint>
35 #include <iterator>
36 #include <map>
37 #include <memory>
38 #include <optional>
39 #include <string>
40 #include <system_error>
41 #include <utility>
42 #include <vector>
43 
44 using namespace llvm;
45 using namespace coverage;
46 
47 #define DEBUG_TYPE "coverage-mapping"
48 
49 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
50   auto It = ExpressionIndices.find(E);
51   if (It != ExpressionIndices.end())
52     return Counter::getExpression(It->second);
53   unsigned I = Expressions.size();
54   Expressions.push_back(E);
55   ExpressionIndices[E] = I;
56   return Counter::getExpression(I);
57 }
58 
59 void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
60                                             SmallVectorImpl<Term> &Terms) {
61   switch (C.getKind()) {
62   case Counter::Zero:
63     break;
64   case Counter::CounterValueReference:
65     Terms.emplace_back(C.getCounterID(), Factor);
66     break;
67   case Counter::Expression:
68     const auto &E = Expressions[C.getExpressionID()];
69     extractTerms(E.LHS, Factor, Terms);
70     extractTerms(
71         E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);
72     break;
73   }
74 }
75 
76 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
77   // Gather constant terms.
78   SmallVector<Term, 32> Terms;
79   extractTerms(ExpressionTree, +1, Terms);
80 
81   // If there are no terms, this is just a zero. The algorithm below assumes at
82   // least one term.
83   if (Terms.size() == 0)
84     return Counter::getZero();
85 
86   // Group the terms by counter ID.
87   llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {
88     return LHS.CounterID < RHS.CounterID;
89   });
90 
91   // Combine terms by counter ID to eliminate counters that sum to zero.
92   auto Prev = Terms.begin();
93   for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
94     if (I->CounterID == Prev->CounterID) {
95       Prev->Factor += I->Factor;
96       continue;
97     }
98     ++Prev;
99     *Prev = *I;
100   }
101   Terms.erase(++Prev, Terms.end());
102 
103   Counter C;
104   // Create additions. We do this before subtractions to avoid constructs like
105   // ((0 - X) + Y), as opposed to (Y - X).
106   for (auto T : Terms) {
107     if (T.Factor <= 0)
108       continue;
109     for (int I = 0; I < T.Factor; ++I)
110       if (C.isZero())
111         C = Counter::getCounter(T.CounterID);
112       else
113         C = get(CounterExpression(CounterExpression::Add, C,
114                                   Counter::getCounter(T.CounterID)));
115   }
116 
117   // Create subtractions.
118   for (auto T : Terms) {
119     if (T.Factor >= 0)
120       continue;
121     for (int I = 0; I < -T.Factor; ++I)
122       C = get(CounterExpression(CounterExpression::Subtract, C,
123                                 Counter::getCounter(T.CounterID)));
124   }
125   return C;
126 }
127 
128 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) {
129   auto Cnt = get(CounterExpression(CounterExpression::Add, LHS, RHS));
130   return Simplify ? simplify(Cnt) : Cnt;
131 }
132 
133 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,
134                                            bool Simplify) {
135   auto Cnt = get(CounterExpression(CounterExpression::Subtract, LHS, RHS));
136   return Simplify ? simplify(Cnt) : Cnt;
137 }
138 
139 void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
140   switch (C.getKind()) {
141   case Counter::Zero:
142     OS << '0';
143     return;
144   case Counter::CounterValueReference:
145     OS << '#' << C.getCounterID();
146     break;
147   case Counter::Expression: {
148     if (C.getExpressionID() >= Expressions.size())
149       return;
150     const auto &E = Expressions[C.getExpressionID()];
151     OS << '(';
152     dump(E.LHS, OS);
153     OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
154     dump(E.RHS, OS);
155     OS << ')';
156     break;
157   }
158   }
159   if (CounterValues.empty())
160     return;
161   Expected<int64_t> Value = evaluate(C);
162   if (auto E = Value.takeError()) {
163     consumeError(std::move(E));
164     return;
165   }
166   OS << '[' << *Value << ']';
167 }
168 
169 Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
170   struct StackElem {
171     Counter ICounter;
172     int64_t LHS = 0;
173     enum {
174       KNeverVisited = 0,
175       KVisitedOnce = 1,
176       KVisitedTwice = 2,
177     } VisitCount = KNeverVisited;
178   };
179 
180   std::stack<StackElem> CounterStack;
181   CounterStack.push({C});
182 
183   int64_t LastPoppedValue;
184 
185   while (!CounterStack.empty()) {
186     StackElem &Current = CounterStack.top();
187 
188     switch (Current.ICounter.getKind()) {
189     case Counter::Zero:
190       LastPoppedValue = 0;
191       CounterStack.pop();
192       break;
193     case Counter::CounterValueReference:
194       if (Current.ICounter.getCounterID() >= CounterValues.size())
195         return errorCodeToError(errc::argument_out_of_domain);
196       LastPoppedValue = CounterValues[Current.ICounter.getCounterID()];
197       CounterStack.pop();
198       break;
199     case Counter::Expression: {
200       if (Current.ICounter.getExpressionID() >= Expressions.size())
201         return errorCodeToError(errc::argument_out_of_domain);
202       const auto &E = Expressions[Current.ICounter.getExpressionID()];
203       if (Current.VisitCount == StackElem::KNeverVisited) {
204         CounterStack.push(StackElem{E.LHS});
205         Current.VisitCount = StackElem::KVisitedOnce;
206       } else if (Current.VisitCount == StackElem::KVisitedOnce) {
207         Current.LHS = LastPoppedValue;
208         CounterStack.push(StackElem{E.RHS});
209         Current.VisitCount = StackElem::KVisitedTwice;
210       } else {
211         int64_t LHS = Current.LHS;
212         int64_t RHS = LastPoppedValue;
213         LastPoppedValue =
214             E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS;
215         CounterStack.pop();
216       }
217       break;
218     }
219     }
220   }
221 
222   return LastPoppedValue;
223 }
224 
225 Expected<BitVector> CounterMappingContext::evaluateBitmap(
226     const CounterMappingRegion *MCDCDecision) const {
227   unsigned ID = MCDCDecision->MCDCParams.BitmapIdx;
228   unsigned NC = MCDCDecision->MCDCParams.NumConditions;
229   unsigned SizeInBits = llvm::alignTo(uint64_t(1) << NC, CHAR_BIT);
230   unsigned SizeInBytes = SizeInBits / CHAR_BIT;
231 
232   ArrayRef<uint8_t> Bytes(&BitmapBytes[ID], SizeInBytes);
233 
234   // Mask each bitmap byte into the BitVector. Go in reverse so that the
235   // bitvector can just be shifted over by one byte on each iteration.
236   BitVector Result(SizeInBits, false);
237   for (auto Byte = std::rbegin(Bytes); Byte != std::rend(Bytes); ++Byte) {
238     uint32_t Data = *Byte;
239     Result <<= CHAR_BIT;
240     Result.setBitsInMask(&Data, 1);
241   }
242   return Result;
243 }
244 
245 class MCDCRecordProcessor {
246   /// A bitmap representing the executed test vectors for a boolean expression.
247   /// Each index of the bitmap corresponds to a possible test vector. An index
248   /// with a bit value of '1' indicates that the corresponding Test Vector
249   /// identified by that index was executed.
250   BitVector &ExecutedTestVectorBitmap;
251 
252   /// Decision Region to which the ExecutedTestVectorBitmap applies.
253   CounterMappingRegion &Region;
254 
255   /// Array of branch regions corresponding each conditions in the boolean
256   /// expression.
257   ArrayRef<CounterMappingRegion> Branches;
258 
259   /// Total number of conditions in the boolean expression.
260   unsigned NumConditions;
261 
262   /// Mapping of a condition ID to its corresponding branch region.
263   llvm::DenseMap<unsigned, const CounterMappingRegion *> Map;
264 
265   /// Vector used to track whether a condition is constant folded.
266   MCDCRecord::BoolVector Folded;
267 
268   /// Mapping of calculated MC/DC Independence Pairs for each condition.
269   MCDCRecord::TVPairMap IndependencePairs;
270 
271   /// Total number of possible Test Vectors for the boolean expression.
272   MCDCRecord::TestVectors TestVectors;
273 
274   /// Actual executed Test Vectors for the boolean expression, based on
275   /// ExecutedTestVectorBitmap.
276   MCDCRecord::TestVectors ExecVectors;
277 
278 public:
279   MCDCRecordProcessor(BitVector &Bitmap, CounterMappingRegion &Region,
280                       ArrayRef<CounterMappingRegion> Branches)
281       : ExecutedTestVectorBitmap(Bitmap), Region(Region), Branches(Branches),
282         NumConditions(Region.MCDCParams.NumConditions),
283         Folded(NumConditions, false), IndependencePairs(NumConditions),
284         TestVectors((size_t)1 << NumConditions) {}
285 
286 private:
287   void recordTestVector(MCDCRecord::TestVector &TV,
288                         MCDCRecord::CondState Result) {
289     // Calculate an index that is used to identify the test vector in a vector
290     // of test vectors.  This index also corresponds to the index values of an
291     // MCDC Region's bitmap (see findExecutedTestVectors()).
292     unsigned Index = 0;
293     for (auto Cond = std::rbegin(TV); Cond != std::rend(TV); ++Cond) {
294       Index <<= 1;
295       Index |= (*Cond == MCDCRecord::MCDC_True) ? 0x1 : 0x0;
296     }
297 
298     // Copy the completed test vector to the vector of testvectors.
299     TestVectors[Index] = TV;
300 
301     // The final value (T,F) is equal to the last non-dontcare state on the
302     // path (in a short-circuiting system).
303     TestVectors[Index].push_back(Result);
304   }
305 
306   void shouldCopyOffTestVectorForTruePath(MCDCRecord::TestVector &TV,
307                                           unsigned ID) {
308     // Branch regions are hashed based on an ID.
309     const CounterMappingRegion *Branch = Map[ID];
310 
311     TV[ID - 1] = MCDCRecord::MCDC_True;
312     if (Branch->MCDCParams.TrueID > 0)
313       buildTestVector(TV, Branch->MCDCParams.TrueID);
314     else
315       recordTestVector(TV, MCDCRecord::MCDC_True);
316   }
317 
318   void shouldCopyOffTestVectorForFalsePath(MCDCRecord::TestVector &TV,
319                                            unsigned ID) {
320     // Branch regions are hashed based on an ID.
321     const CounterMappingRegion *Branch = Map[ID];
322 
323     TV[ID - 1] = MCDCRecord::MCDC_False;
324     if (Branch->MCDCParams.FalseID > 0)
325       buildTestVector(TV, Branch->MCDCParams.FalseID);
326     else
327       recordTestVector(TV, MCDCRecord::MCDC_False);
328   }
329 
330   /// Starting with the base test vector, build a comprehensive list of
331   /// possible test vectors by recursively walking the branch condition IDs
332   /// provided. Once an end node is reached, record the test vector in a vector
333   /// of test vectors that can be matched against during MC/DC analysis, and
334   /// then reset the positions to 'DontCare'.
335   void buildTestVector(MCDCRecord::TestVector &TV, unsigned ID = 1) {
336     shouldCopyOffTestVectorForTruePath(TV, ID);
337     shouldCopyOffTestVectorForFalsePath(TV, ID);
338 
339     // Reset back to DontCare.
340     TV[ID - 1] = MCDCRecord::MCDC_DontCare;
341   }
342 
343   /// Walk the bits in the bitmap.  A bit set to '1' indicates that the test
344   /// vector at the corresponding index was executed during a test run.
345   void findExecutedTestVectors(BitVector &ExecutedTestVectorBitmap) {
346     for (unsigned Idx = 0; Idx < ExecutedTestVectorBitmap.size(); ++Idx) {
347       if (ExecutedTestVectorBitmap[Idx] == 0)
348         continue;
349       assert(!TestVectors[Idx].empty() && "Test Vector doesn't exist.");
350       ExecVectors.push_back(TestVectors[Idx]);
351     }
352   }
353 
354   /// For a given condition and two executed Test Vectors, A and B, see if the
355   /// two test vectors match forming an Independence Pair for the condition.
356   /// For two test vectors to match, the following must be satisfied:
357   /// - The condition's value in each test vector must be opposite.
358   /// - The result's value in each test vector must be opposite.
359   /// - All other conditions' values must be equal or marked as "don't care".
360   bool matchTestVectors(unsigned Aidx, unsigned Bidx, unsigned ConditionIdx) {
361     const MCDCRecord::TestVector &A = ExecVectors[Aidx];
362     const MCDCRecord::TestVector &B = ExecVectors[Bidx];
363 
364     // If condition values in both A and B aren't opposites, no match.
365     // Because a value can be 0 (false), 1 (true), or -1 (DontCare), a check
366     // that "XOR != 1" will ensure that the values are opposites and that
367     // neither of them is a DontCare.
368     //  1 XOR  0 ==  1 | 0 XOR  0 ==  0 | -1 XOR  0 == -1
369     //  1 XOR  1 ==  0 | 0 XOR  1 ==  1 | -1 XOR  1 == -2
370     //  1 XOR -1 == -2 | 0 XOR -1 == -1 | -1 XOR -1 ==  0
371     if ((A[ConditionIdx] ^ B[ConditionIdx]) != 1)
372       return false;
373 
374     // If the results of both A and B aren't opposites, no match.
375     if ((A[NumConditions] ^ B[NumConditions]) != 1)
376       return false;
377 
378     for (unsigned Idx = 0; Idx < NumConditions; ++Idx) {
379       // Look for other conditions that don't match. Skip over the given
380       // Condition as well as any conditions marked as "don't care".
381       const auto ARecordTyForCond = A[Idx];
382       const auto BRecordTyForCond = B[Idx];
383       if (Idx == ConditionIdx ||
384           ARecordTyForCond == MCDCRecord::MCDC_DontCare ||
385           BRecordTyForCond == MCDCRecord::MCDC_DontCare)
386         continue;
387 
388       // If there is a condition mismatch with any of the other conditions,
389       // there is no match for the test vectors.
390       if (ARecordTyForCond != BRecordTyForCond)
391         return false;
392     }
393 
394     // Otherwise, match.
395     return true;
396   }
397 
398   /// Find all possible Independence Pairs for a boolean expression given its
399   /// executed Test Vectors.  This process involves looking at each condition
400   /// and attempting to find two Test Vectors that "match", giving us a pair.
401   void findIndependencePairs() {
402     unsigned NumTVs = ExecVectors.size();
403 
404     // For each condition.
405     for (unsigned C = 0; C < NumConditions; ++C) {
406       bool PairFound = false;
407 
408       // For each executed test vector.
409       for (unsigned I = 0; !PairFound && I < NumTVs; ++I) {
410         // Compared to every other executed test vector.
411         for (unsigned J = 0; !PairFound && J < NumTVs; ++J) {
412           if (I == J)
413             continue;
414 
415           // If a matching pair of vectors is found, record them.
416           if ((PairFound = matchTestVectors(I, J, C)))
417             IndependencePairs[C] = std::make_pair(I + 1, J + 1);
418         }
419       }
420     }
421   }
422 
423 public:
424   /// Process the MC/DC Record in order to produce a result for a boolean
425   /// expression. This process includes tracking the conditions that comprise
426   /// the decision region, calculating the list of all possible test vectors,
427   /// marking the executed test vectors, and then finding an Independence Pair
428   /// out of the executed test vectors for each condition in the boolean
429   /// expression. A condition is tracked to ensure that its ID can be mapped to
430   /// its ordinal position in the boolean expression. The condition's source
431   /// location is also tracked, as well as whether it is constant folded (in
432   /// which case it is excuded from the metric).
433   MCDCRecord processMCDCRecord() {
434     unsigned I = 0;
435     MCDCRecord::CondIDMap PosToID;
436     MCDCRecord::LineColPairMap CondLoc;
437 
438     // Walk the Record's BranchRegions (representing Conditions) in order to:
439     // - Hash the condition based on its corresponding ID. This will be used to
440     //   calculate the test vectors.
441     // - Keep a map of the condition's ordinal position (1, 2, 3, 4) to its
442     //   actual ID.  This will be used to visualize the conditions in the
443     //   correct order.
444     // - Keep track of the condition source location. This will be used to
445     //   visualize where the condition is.
446     // - Record whether the condition is constant folded so that we exclude it
447     //   from being measured.
448     for (const auto &B : Branches) {
449       Map[B.MCDCParams.ID] = &B;
450       PosToID[I] = B.MCDCParams.ID - 1;
451       CondLoc[I] = B.startLoc();
452       Folded[I++] = (B.Count.isZero() && B.FalseCount.isZero());
453     }
454 
455     // Initialize a base test vector as 'DontCare'.
456     MCDCRecord::TestVector TV(NumConditions, MCDCRecord::MCDC_DontCare);
457 
458     // Use the base test vector to build the list of all possible test vectors.
459     buildTestVector(TV);
460 
461     // Using Profile Bitmap from runtime, mark the executed test vectors.
462     findExecutedTestVectors(ExecutedTestVectorBitmap);
463 
464     // Compare executed test vectors against each other to find an independence
465     // pairs for each condition.  This processing takes the most time.
466     findIndependencePairs();
467 
468     // Record Test vectors, executed vectors, and independence pairs.
469     MCDCRecord Res(Region, ExecVectors, IndependencePairs, Folded, PosToID,
470                    CondLoc);
471     return Res;
472   }
473 };
474 
475 Expected<MCDCRecord> CounterMappingContext::evaluateMCDCRegion(
476     CounterMappingRegion Region, BitVector ExecutedTestVectorBitmap,
477     ArrayRef<CounterMappingRegion> Branches) {
478 
479   MCDCRecordProcessor MCDCProcessor(ExecutedTestVectorBitmap, Region, Branches);
480   return MCDCProcessor.processMCDCRecord();
481 }
482 
483 unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
484   struct StackElem {
485     Counter ICounter;
486     int64_t LHS = 0;
487     enum {
488       KNeverVisited = 0,
489       KVisitedOnce = 1,
490       KVisitedTwice = 2,
491     } VisitCount = KNeverVisited;
492   };
493 
494   std::stack<StackElem> CounterStack;
495   CounterStack.push({C});
496 
497   int64_t LastPoppedValue;
498 
499   while (!CounterStack.empty()) {
500     StackElem &Current = CounterStack.top();
501 
502     switch (Current.ICounter.getKind()) {
503     case Counter::Zero:
504       LastPoppedValue = 0;
505       CounterStack.pop();
506       break;
507     case Counter::CounterValueReference:
508       LastPoppedValue = Current.ICounter.getCounterID();
509       CounterStack.pop();
510       break;
511     case Counter::Expression: {
512       if (Current.ICounter.getExpressionID() >= Expressions.size()) {
513         LastPoppedValue = 0;
514         CounterStack.pop();
515       } else {
516         const auto &E = Expressions[Current.ICounter.getExpressionID()];
517         if (Current.VisitCount == StackElem::KNeverVisited) {
518           CounterStack.push(StackElem{E.LHS});
519           Current.VisitCount = StackElem::KVisitedOnce;
520         } else if (Current.VisitCount == StackElem::KVisitedOnce) {
521           Current.LHS = LastPoppedValue;
522           CounterStack.push(StackElem{E.RHS});
523           Current.VisitCount = StackElem::KVisitedTwice;
524         } else {
525           int64_t LHS = Current.LHS;
526           int64_t RHS = LastPoppedValue;
527           LastPoppedValue = std::max(LHS, RHS);
528           CounterStack.pop();
529         }
530       }
531       break;
532     }
533     }
534   }
535 
536   return LastPoppedValue;
537 }
538 
539 void FunctionRecordIterator::skipOtherFiles() {
540   while (Current != Records.end() && !Filename.empty() &&
541          Filename != Current->Filenames[0])
542     ++Current;
543   if (Current == Records.end())
544     *this = FunctionRecordIterator();
545 }
546 
547 ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(
548     StringRef Filename) const {
549   size_t FilenameHash = hash_value(Filename);
550   auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);
551   if (RecordIt == FilenameHash2RecordIndices.end())
552     return {};
553   return RecordIt->second;
554 }
555 
556 static unsigned getMaxCounterID(const CounterMappingContext &Ctx,
557                                 const CoverageMappingRecord &Record) {
558   unsigned MaxCounterID = 0;
559   for (const auto &Region : Record.MappingRegions) {
560     MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count));
561   }
562   return MaxCounterID;
563 }
564 
565 static unsigned getMaxBitmapSize(const CounterMappingContext &Ctx,
566                                  const CoverageMappingRecord &Record) {
567   unsigned MaxBitmapID = 0;
568   unsigned NumConditions = 0;
569   // The last DecisionRegion has the highest bitmap byte index used in the
570   // function, which when combined with its number of conditions, yields the
571   // full bitmap size.
572   for (const auto &Region : reverse(Record.MappingRegions)) {
573     if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {
574       MaxBitmapID = Region.MCDCParams.BitmapIdx;
575       NumConditions = Region.MCDCParams.NumConditions;
576       break;
577     }
578   }
579   unsigned SizeInBits = llvm::alignTo(uint64_t(1) << NumConditions, CHAR_BIT);
580   return MaxBitmapID + (SizeInBits / CHAR_BIT);
581 }
582 
583 Error CoverageMapping::loadFunctionRecord(
584     const CoverageMappingRecord &Record,
585     IndexedInstrProfReader &ProfileReader) {
586   StringRef OrigFuncName = Record.FunctionName;
587   if (OrigFuncName.empty())
588     return make_error<CoverageMapError>(coveragemap_error::malformed,
589                                         "record function name is empty");
590 
591   if (Record.Filenames.empty())
592     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
593   else
594     OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
595 
596   CounterMappingContext Ctx(Record.Expressions);
597 
598   std::vector<uint64_t> Counts;
599   if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
600                                                 Record.FunctionHash, Counts)) {
601     instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E)));
602     if (IPE == instrprof_error::hash_mismatch) {
603       FuncHashMismatches.emplace_back(std::string(Record.FunctionName),
604                                       Record.FunctionHash);
605       return Error::success();
606     }
607     if (IPE != instrprof_error::unknown_function)
608       return make_error<InstrProfError>(IPE);
609     Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);
610   }
611   Ctx.setCounts(Counts);
612 
613   std::vector<uint8_t> BitmapBytes;
614   if (Error E = ProfileReader.getFunctionBitmapBytes(
615           Record.FunctionName, Record.FunctionHash, BitmapBytes)) {
616     instrprof_error IPE = std::get<0>(InstrProfError::take(std::move(E)));
617     if (IPE == instrprof_error::hash_mismatch) {
618       FuncHashMismatches.emplace_back(std::string(Record.FunctionName),
619                                       Record.FunctionHash);
620       return Error::success();
621     }
622     if (IPE != instrprof_error::unknown_function)
623       return make_error<InstrProfError>(IPE);
624     BitmapBytes.assign(getMaxBitmapSize(Ctx, Record) + 1, 0);
625   }
626   Ctx.setBitmapBytes(BitmapBytes);
627 
628   assert(!Record.MappingRegions.empty() && "Function has no regions");
629 
630   // This coverage record is a zero region for a function that's unused in
631   // some TU, but used in a different TU. Ignore it. The coverage maps from the
632   // the other TU will either be loaded (providing full region counts) or they
633   // won't (in which case we don't unintuitively report functions as uncovered
634   // when they have non-zero counts in the profile).
635   if (Record.MappingRegions.size() == 1 &&
636       Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
637     return Error::success();
638 
639   unsigned NumConds = 0;
640   const CounterMappingRegion *MCDCDecision;
641   std::vector<CounterMappingRegion> MCDCBranches;
642 
643   FunctionRecord Function(OrigFuncName, Record.Filenames);
644   for (const auto &Region : Record.MappingRegions) {
645     // If an MCDCDecisionRegion is seen, track the BranchRegions that follow
646     // it according to Region.NumConditions.
647     if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {
648       assert(NumConds == 0);
649       MCDCDecision = &Region;
650       NumConds = Region.MCDCParams.NumConditions;
651       continue;
652     }
653     Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
654     if (auto E = ExecutionCount.takeError()) {
655       consumeError(std::move(E));
656       return Error::success();
657     }
658     Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount);
659     if (auto E = AltExecutionCount.takeError()) {
660       consumeError(std::move(E));
661       return Error::success();
662     }
663     Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);
664 
665     // If a MCDCDecisionRegion was seen, store the BranchRegions that
666     // correspond to it in a vector, according to the number of conditions
667     // recorded for the region (tracked by NumConds).
668     if (NumConds > 0 && Region.Kind == CounterMappingRegion::MCDCBranchRegion) {
669       MCDCBranches.push_back(Region);
670 
671       // As we move through all of the MCDCBranchRegions that follow the
672       // MCDCDecisionRegion, decrement NumConds to make sure we account for
673       // them all before we calculate the bitmap of executed test vectors.
674       if (--NumConds == 0) {
675         // Evaluating the test vector bitmap for the decision region entails
676         // calculating precisely what bits are pertinent to this region alone.
677         // This is calculated based on the recorded offset into the global
678         // profile bitmap; the length is calculated based on the recorded
679         // number of conditions.
680         Expected<BitVector> ExecutedTestVectorBitmap =
681             Ctx.evaluateBitmap(MCDCDecision);
682         if (auto E = ExecutedTestVectorBitmap.takeError()) {
683           consumeError(std::move(E));
684           return Error::success();
685         }
686 
687         // Since the bitmap identifies the executed test vectors for an MC/DC
688         // DecisionRegion, all of the information is now available to process.
689         // This is where the bulk of the MC/DC progressing takes place.
690         Expected<MCDCRecord> Record = Ctx.evaluateMCDCRegion(
691             *MCDCDecision, *ExecutedTestVectorBitmap, MCDCBranches);
692         if (auto E = Record.takeError()) {
693           consumeError(std::move(E));
694           return Error::success();
695         }
696 
697         // Save the MC/DC Record so that it can be visualized later.
698         Function.pushMCDCRecord(*Record);
699         MCDCBranches.clear();
700       }
701     }
702   }
703 
704   // Don't create records for (filenames, function) pairs we've already seen.
705   auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
706                                           Record.Filenames.end());
707   if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
708     return Error::success();
709 
710   Functions.push_back(std::move(Function));
711 
712   // Performance optimization: keep track of the indices of the function records
713   // which correspond to each filename. This can be used to substantially speed
714   // up queries for coverage info in a file.
715   unsigned RecordIndex = Functions.size() - 1;
716   for (StringRef Filename : Record.Filenames) {
717     auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];
718     // Note that there may be duplicates in the filename set for a function
719     // record, because of e.g. macro expansions in the function in which both
720     // the macro and the function are defined in the same file.
721     if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)
722       RecordIndices.push_back(RecordIndex);
723   }
724 
725   return Error::success();
726 }
727 
728 // This function is for memory optimization by shortening the lifetimes
729 // of CoverageMappingReader instances.
730 Error CoverageMapping::loadFromReaders(
731     ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
732     IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) {
733   for (const auto &CoverageReader : CoverageReaders) {
734     for (auto RecordOrErr : *CoverageReader) {
735       if (Error E = RecordOrErr.takeError())
736         return E;
737       const auto &Record = *RecordOrErr;
738       if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader))
739         return E;
740     }
741   }
742   return Error::success();
743 }
744 
745 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
746     ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
747     IndexedInstrProfReader &ProfileReader) {
748   auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
749   if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage))
750     return std::move(E);
751   return std::move(Coverage);
752 }
753 
754 // If E is a no_data_found error, returns success. Otherwise returns E.
755 static Error handleMaybeNoDataFoundError(Error E) {
756   return handleErrors(
757       std::move(E), [](const CoverageMapError &CME) {
758         if (CME.get() == coveragemap_error::no_data_found)
759           return static_cast<Error>(Error::success());
760         return make_error<CoverageMapError>(CME.get(), CME.getMessage());
761       });
762 }
763 
764 Error CoverageMapping::loadFromFile(
765     StringRef Filename, StringRef Arch, StringRef CompilationDir,
766     IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage,
767     bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) {
768   auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(
769       Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false);
770   if (std::error_code EC = CovMappingBufOrErr.getError())
771     return createFileError(Filename, errorCodeToError(EC));
772   MemoryBufferRef CovMappingBufRef =
773       CovMappingBufOrErr.get()->getMemBufferRef();
774   SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
775 
776   SmallVector<object::BuildIDRef> BinaryIDs;
777   auto CoverageReadersOrErr = BinaryCoverageReader::create(
778       CovMappingBufRef, Arch, Buffers, CompilationDir,
779       FoundBinaryIDs ? &BinaryIDs : nullptr);
780   if (Error E = CoverageReadersOrErr.takeError()) {
781     E = handleMaybeNoDataFoundError(std::move(E));
782     if (E)
783       return createFileError(Filename, std::move(E));
784     return E;
785   }
786 
787   SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
788   for (auto &Reader : CoverageReadersOrErr.get())
789     Readers.push_back(std::move(Reader));
790   if (FoundBinaryIDs && !Readers.empty()) {
791     llvm::append_range(*FoundBinaryIDs,
792                        llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) {
793                          return object::BuildID(BID);
794                        }));
795   }
796   DataFound |= !Readers.empty();
797   if (Error E = loadFromReaders(Readers, ProfileReader, Coverage))
798     return createFileError(Filename, std::move(E));
799   return Error::success();
800 }
801 
802 Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
803     ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
804     vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir,
805     const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) {
806   auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename, FS);
807   if (Error E = ProfileReaderOrErr.takeError())
808     return createFileError(ProfileFilename, std::move(E));
809   auto ProfileReader = std::move(ProfileReaderOrErr.get());
810   auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
811   bool DataFound = false;
812 
813   auto GetArch = [&](size_t Idx) {
814     if (Arches.empty())
815       return StringRef();
816     if (Arches.size() == 1)
817       return Arches.front();
818     return Arches[Idx];
819   };
820 
821   SmallVector<object::BuildID> FoundBinaryIDs;
822   for (const auto &File : llvm::enumerate(ObjectFilenames)) {
823     if (Error E =
824             loadFromFile(File.value(), GetArch(File.index()), CompilationDir,
825                          *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs))
826       return std::move(E);
827   }
828 
829   if (BIDFetcher) {
830     std::vector<object::BuildID> ProfileBinaryIDs;
831     if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs))
832       return createFileError(ProfileFilename, std::move(E));
833 
834     SmallVector<object::BuildIDRef> BinaryIDsToFetch;
835     if (!ProfileBinaryIDs.empty()) {
836       const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) {
837         return std::lexicographical_compare(A.begin(), A.end(), B.begin(),
838                                             B.end());
839       };
840       llvm::sort(FoundBinaryIDs, Compare);
841       std::set_difference(
842           ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(),
843           FoundBinaryIDs.begin(), FoundBinaryIDs.end(),
844           std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare);
845     }
846 
847     for (object::BuildIDRef BinaryID : BinaryIDsToFetch) {
848       std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID);
849       if (PathOpt) {
850         std::string Path = std::move(*PathOpt);
851         StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef();
852         if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader,
853                                   *Coverage, DataFound))
854           return std::move(E);
855       } else if (CheckBinaryIDs) {
856         return createFileError(
857             ProfileFilename,
858             createStringError(errc::no_such_file_or_directory,
859                               "Missing binary ID: " +
860                                   llvm::toHex(BinaryID, /*LowerCase=*/true)));
861       }
862     }
863   }
864 
865   if (!DataFound)
866     return createFileError(
867         join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "),
868         make_error<CoverageMapError>(coveragemap_error::no_data_found));
869   return std::move(Coverage);
870 }
871 
872 namespace {
873 
874 /// Distributes functions into instantiation sets.
875 ///
876 /// An instantiation set is a collection of functions that have the same source
877 /// code, ie, template functions specializations.
878 class FunctionInstantiationSetCollector {
879   using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
880   MapT InstantiatedFunctions;
881 
882 public:
883   void insert(const FunctionRecord &Function, unsigned FileID) {
884     auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
885     while (I != E && I->FileID != FileID)
886       ++I;
887     assert(I != E && "function does not cover the given file");
888     auto &Functions = InstantiatedFunctions[I->startLoc()];
889     Functions.push_back(&Function);
890   }
891 
892   MapT::iterator begin() { return InstantiatedFunctions.begin(); }
893   MapT::iterator end() { return InstantiatedFunctions.end(); }
894 };
895 
896 class SegmentBuilder {
897   std::vector<CoverageSegment> &Segments;
898   SmallVector<const CountedRegion *, 8> ActiveRegions;
899 
900   SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
901 
902   /// Emit a segment with the count from \p Region starting at \p StartLoc.
903   //
904   /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
905   /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
906   void startSegment(const CountedRegion &Region, LineColPair StartLoc,
907                     bool IsRegionEntry, bool EmitSkippedRegion = false) {
908     bool HasCount = !EmitSkippedRegion &&
909                     (Region.Kind != CounterMappingRegion::SkippedRegion);
910 
911     // If the new segment wouldn't affect coverage rendering, skip it.
912     if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
913       const auto &Last = Segments.back();
914       if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
915           !Last.IsRegionEntry)
916         return;
917     }
918 
919     if (HasCount)
920       Segments.emplace_back(StartLoc.first, StartLoc.second,
921                             Region.ExecutionCount, IsRegionEntry,
922                             Region.Kind == CounterMappingRegion::GapRegion);
923     else
924       Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
925 
926     LLVM_DEBUG({
927       const auto &Last = Segments.back();
928       dbgs() << "Segment at " << Last.Line << ":" << Last.Col
929              << " (count = " << Last.Count << ")"
930              << (Last.IsRegionEntry ? ", RegionEntry" : "")
931              << (!Last.HasCount ? ", Skipped" : "")
932              << (Last.IsGapRegion ? ", Gap" : "") << "\n";
933     });
934   }
935 
936   /// Emit segments for active regions which end before \p Loc.
937   ///
938   /// \p Loc: The start location of the next region. If std::nullopt, all active
939   /// regions are completed.
940   /// \p FirstCompletedRegion: Index of the first completed region.
941   void completeRegionsUntil(std::optional<LineColPair> Loc,
942                             unsigned FirstCompletedRegion) {
943     // Sort the completed regions by end location. This makes it simple to
944     // emit closing segments in sorted order.
945     auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
946     std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
947                       [](const CountedRegion *L, const CountedRegion *R) {
948                         return L->endLoc() < R->endLoc();
949                       });
950 
951     // Emit segments for all completed regions.
952     for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
953          ++I) {
954       const auto *CompletedRegion = ActiveRegions[I];
955       assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
956              "Completed region ends after start of new region");
957 
958       const auto *PrevCompletedRegion = ActiveRegions[I - 1];
959       auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
960 
961       // Don't emit any more segments if they start where the new region begins.
962       if (Loc && CompletedSegmentLoc == *Loc)
963         break;
964 
965       // Don't emit a segment if the next completed region ends at the same
966       // location as this one.
967       if (CompletedSegmentLoc == CompletedRegion->endLoc())
968         continue;
969 
970       // Use the count from the last completed region which ends at this loc.
971       for (unsigned J = I + 1; J < E; ++J)
972         if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
973           CompletedRegion = ActiveRegions[J];
974 
975       startSegment(*CompletedRegion, CompletedSegmentLoc, false);
976     }
977 
978     auto Last = ActiveRegions.back();
979     if (FirstCompletedRegion && Last->endLoc() != *Loc) {
980       // If there's a gap after the end of the last completed region and the
981       // start of the new region, use the last active region to fill the gap.
982       startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
983                    false);
984     } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
985       // Emit a skipped segment if there are no more active regions. This
986       // ensures that gaps between functions are marked correctly.
987       startSegment(*Last, Last->endLoc(), false, true);
988     }
989 
990     // Pop the completed regions.
991     ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
992   }
993 
994   void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
995     for (const auto &CR : enumerate(Regions)) {
996       auto CurStartLoc = CR.value().startLoc();
997 
998       // Active regions which end before the current region need to be popped.
999       auto CompletedRegions =
1000           std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
1001                                 [&](const CountedRegion *Region) {
1002                                   return !(Region->endLoc() <= CurStartLoc);
1003                                 });
1004       if (CompletedRegions != ActiveRegions.end()) {
1005         unsigned FirstCompletedRegion =
1006             std::distance(ActiveRegions.begin(), CompletedRegions);
1007         completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
1008       }
1009 
1010       bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
1011 
1012       // Try to emit a segment for the current region.
1013       if (CurStartLoc == CR.value().endLoc()) {
1014         // Avoid making zero-length regions active. If it's the last region,
1015         // emit a skipped segment. Otherwise use its predecessor's count.
1016         const bool Skipped =
1017             (CR.index() + 1) == Regions.size() ||
1018             CR.value().Kind == CounterMappingRegion::SkippedRegion;
1019         startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
1020                      CurStartLoc, !GapRegion, Skipped);
1021         // If it is skipped segment, create a segment with last pushed
1022         // regions's count at CurStartLoc.
1023         if (Skipped && !ActiveRegions.empty())
1024           startSegment(*ActiveRegions.back(), CurStartLoc, false);
1025         continue;
1026       }
1027       if (CR.index() + 1 == Regions.size() ||
1028           CurStartLoc != Regions[CR.index() + 1].startLoc()) {
1029         // Emit a segment if the next region doesn't start at the same location
1030         // as this one.
1031         startSegment(CR.value(), CurStartLoc, !GapRegion);
1032       }
1033 
1034       // This region is active (i.e not completed).
1035       ActiveRegions.push_back(&CR.value());
1036     }
1037 
1038     // Complete any remaining active regions.
1039     if (!ActiveRegions.empty())
1040       completeRegionsUntil(std::nullopt, 0);
1041   }
1042 
1043   /// Sort a nested sequence of regions from a single file.
1044   static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
1045     llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
1046       if (LHS.startLoc() != RHS.startLoc())
1047         return LHS.startLoc() < RHS.startLoc();
1048       if (LHS.endLoc() != RHS.endLoc())
1049         // When LHS completely contains RHS, we sort LHS first.
1050         return RHS.endLoc() < LHS.endLoc();
1051       // If LHS and RHS cover the same area, we need to sort them according
1052       // to their kinds so that the most suitable region will become "active"
1053       // in combineRegions(). Because we accumulate counter values only from
1054       // regions of the same kind as the first region of the area, prefer
1055       // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
1056       static_assert(CounterMappingRegion::CodeRegion <
1057                             CounterMappingRegion::ExpansionRegion &&
1058                         CounterMappingRegion::ExpansionRegion <
1059                             CounterMappingRegion::SkippedRegion,
1060                     "Unexpected order of region kind values");
1061       return LHS.Kind < RHS.Kind;
1062     });
1063   }
1064 
1065   /// Combine counts of regions which cover the same area.
1066   static ArrayRef<CountedRegion>
1067   combineRegions(MutableArrayRef<CountedRegion> Regions) {
1068     if (Regions.empty())
1069       return Regions;
1070     auto Active = Regions.begin();
1071     auto End = Regions.end();
1072     for (auto I = Regions.begin() + 1; I != End; ++I) {
1073       if (Active->startLoc() != I->startLoc() ||
1074           Active->endLoc() != I->endLoc()) {
1075         // Shift to the next region.
1076         ++Active;
1077         if (Active != I)
1078           *Active = *I;
1079         continue;
1080       }
1081       // Merge duplicate region.
1082       // If CodeRegions and ExpansionRegions cover the same area, it's probably
1083       // a macro which is fully expanded to another macro. In that case, we need
1084       // to accumulate counts only from CodeRegions, or else the area will be
1085       // counted twice.
1086       // On the other hand, a macro may have a nested macro in its body. If the
1087       // outer macro is used several times, the ExpansionRegion for the nested
1088       // macro will also be added several times. These ExpansionRegions cover
1089       // the same source locations and have to be combined to reach the correct
1090       // value for that area.
1091       // We add counts of the regions of the same kind as the active region
1092       // to handle the both situations.
1093       if (I->Kind == Active->Kind)
1094         Active->ExecutionCount += I->ExecutionCount;
1095     }
1096     return Regions.drop_back(std::distance(++Active, End));
1097   }
1098 
1099 public:
1100   /// Build a sorted list of CoverageSegments from a list of Regions.
1101   static std::vector<CoverageSegment>
1102   buildSegments(MutableArrayRef<CountedRegion> Regions) {
1103     std::vector<CoverageSegment> Segments;
1104     SegmentBuilder Builder(Segments);
1105 
1106     sortNestedRegions(Regions);
1107     ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
1108 
1109     LLVM_DEBUG({
1110       dbgs() << "Combined regions:\n";
1111       for (const auto &CR : CombinedRegions)
1112         dbgs() << "  " << CR.LineStart << ":" << CR.ColumnStart << " -> "
1113                << CR.LineEnd << ":" << CR.ColumnEnd
1114                << " (count=" << CR.ExecutionCount << ")\n";
1115     });
1116 
1117     Builder.buildSegmentsImpl(CombinedRegions);
1118 
1119 #ifndef NDEBUG
1120     for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
1121       const auto &L = Segments[I - 1];
1122       const auto &R = Segments[I];
1123       if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
1124         if (L.Line == R.Line && L.Col == R.Col && !L.HasCount)
1125           continue;
1126         LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
1127                           << " followed by " << R.Line << ":" << R.Col << "\n");
1128         assert(false && "Coverage segments not unique or sorted");
1129       }
1130     }
1131 #endif
1132 
1133     return Segments;
1134   }
1135 };
1136 
1137 } // end anonymous namespace
1138 
1139 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
1140   std::vector<StringRef> Filenames;
1141   for (const auto &Function : getCoveredFunctions())
1142     llvm::append_range(Filenames, Function.Filenames);
1143   llvm::sort(Filenames);
1144   auto Last = std::unique(Filenames.begin(), Filenames.end());
1145   Filenames.erase(Last, Filenames.end());
1146   return Filenames;
1147 }
1148 
1149 static SmallBitVector gatherFileIDs(StringRef SourceFile,
1150                                     const FunctionRecord &Function) {
1151   SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
1152   for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
1153     if (SourceFile == Function.Filenames[I])
1154       FilenameEquivalence[I] = true;
1155   return FilenameEquivalence;
1156 }
1157 
1158 /// Return the ID of the file where the definition of the function is located.
1159 static std::optional<unsigned>
1160 findMainViewFileID(const FunctionRecord &Function) {
1161   SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
1162   for (const auto &CR : Function.CountedRegions)
1163     if (CR.Kind == CounterMappingRegion::ExpansionRegion)
1164       IsNotExpandedFile[CR.ExpandedFileID] = false;
1165   int I = IsNotExpandedFile.find_first();
1166   if (I == -1)
1167     return std::nullopt;
1168   return I;
1169 }
1170 
1171 /// Check if SourceFile is the file that contains the definition of
1172 /// the Function. Return the ID of the file in that case or std::nullopt
1173 /// otherwise.
1174 static std::optional<unsigned>
1175 findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) {
1176   std::optional<unsigned> I = findMainViewFileID(Function);
1177   if (I && SourceFile == Function.Filenames[*I])
1178     return I;
1179   return std::nullopt;
1180 }
1181 
1182 static bool isExpansion(const CountedRegion &R, unsigned FileID) {
1183   return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
1184 }
1185 
1186 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
1187   CoverageData FileCoverage(Filename);
1188   std::vector<CountedRegion> Regions;
1189 
1190   // Look up the function records in the given file. Due to hash collisions on
1191   // the filename, we may get back some records that are not in the file.
1192   ArrayRef<unsigned> RecordIndices =
1193       getImpreciseRecordIndicesForFilename(Filename);
1194   for (unsigned RecordIndex : RecordIndices) {
1195     const FunctionRecord &Function = Functions[RecordIndex];
1196     auto MainFileID = findMainViewFileID(Filename, Function);
1197     auto FileIDs = gatherFileIDs(Filename, Function);
1198     for (const auto &CR : Function.CountedRegions)
1199       if (FileIDs.test(CR.FileID)) {
1200         Regions.push_back(CR);
1201         if (MainFileID && isExpansion(CR, *MainFileID))
1202           FileCoverage.Expansions.emplace_back(CR, Function);
1203       }
1204     // Capture branch regions specific to the function (excluding expansions).
1205     for (const auto &CR : Function.CountedBranchRegions)
1206       if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID))
1207         FileCoverage.BranchRegions.push_back(CR);
1208     // Capture MCDC records specific to the function.
1209     for (const auto &MR : Function.MCDCRecords)
1210       if (FileIDs.test(MR.getDecisionRegion().FileID))
1211         FileCoverage.MCDCRecords.push_back(MR);
1212   }
1213 
1214   LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
1215   FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1216 
1217   return FileCoverage;
1218 }
1219 
1220 std::vector<InstantiationGroup>
1221 CoverageMapping::getInstantiationGroups(StringRef Filename) const {
1222   FunctionInstantiationSetCollector InstantiationSetCollector;
1223   // Look up the function records in the given file. Due to hash collisions on
1224   // the filename, we may get back some records that are not in the file.
1225   ArrayRef<unsigned> RecordIndices =
1226       getImpreciseRecordIndicesForFilename(Filename);
1227   for (unsigned RecordIndex : RecordIndices) {
1228     const FunctionRecord &Function = Functions[RecordIndex];
1229     auto MainFileID = findMainViewFileID(Filename, Function);
1230     if (!MainFileID)
1231       continue;
1232     InstantiationSetCollector.insert(Function, *MainFileID);
1233   }
1234 
1235   std::vector<InstantiationGroup> Result;
1236   for (auto &InstantiationSet : InstantiationSetCollector) {
1237     InstantiationGroup IG{InstantiationSet.first.first,
1238                           InstantiationSet.first.second,
1239                           std::move(InstantiationSet.second)};
1240     Result.emplace_back(std::move(IG));
1241   }
1242   return Result;
1243 }
1244 
1245 CoverageData
1246 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
1247   auto MainFileID = findMainViewFileID(Function);
1248   if (!MainFileID)
1249     return CoverageData();
1250 
1251   CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
1252   std::vector<CountedRegion> Regions;
1253   for (const auto &CR : Function.CountedRegions)
1254     if (CR.FileID == *MainFileID) {
1255       Regions.push_back(CR);
1256       if (isExpansion(CR, *MainFileID))
1257         FunctionCoverage.Expansions.emplace_back(CR, Function);
1258     }
1259   // Capture branch regions specific to the function (excluding expansions).
1260   for (const auto &CR : Function.CountedBranchRegions)
1261     if (CR.FileID == *MainFileID)
1262       FunctionCoverage.BranchRegions.push_back(CR);
1263 
1264   // Capture MCDC records specific to the function.
1265   for (const auto &MR : Function.MCDCRecords)
1266     if (MR.getDecisionRegion().FileID == *MainFileID)
1267       FunctionCoverage.MCDCRecords.push_back(MR);
1268 
1269   LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
1270                     << "\n");
1271   FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1272 
1273   return FunctionCoverage;
1274 }
1275 
1276 CoverageData CoverageMapping::getCoverageForExpansion(
1277     const ExpansionRecord &Expansion) const {
1278   CoverageData ExpansionCoverage(
1279       Expansion.Function.Filenames[Expansion.FileID]);
1280   std::vector<CountedRegion> Regions;
1281   for (const auto &CR : Expansion.Function.CountedRegions)
1282     if (CR.FileID == Expansion.FileID) {
1283       Regions.push_back(CR);
1284       if (isExpansion(CR, Expansion.FileID))
1285         ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
1286     }
1287   for (const auto &CR : Expansion.Function.CountedBranchRegions)
1288     // Capture branch regions that only pertain to the corresponding expansion.
1289     if (CR.FileID == Expansion.FileID)
1290       ExpansionCoverage.BranchRegions.push_back(CR);
1291 
1292   LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
1293                     << Expansion.FileID << "\n");
1294   ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1295 
1296   return ExpansionCoverage;
1297 }
1298 
1299 LineCoverageStats::LineCoverageStats(
1300     ArrayRef<const CoverageSegment *> LineSegments,
1301     const CoverageSegment *WrappedSegment, unsigned Line)
1302     : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
1303       LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
1304   // Find the minimum number of regions which start in this line.
1305   unsigned MinRegionCount = 0;
1306   auto isStartOfRegion = [](const CoverageSegment *S) {
1307     return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
1308   };
1309   for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
1310     if (isStartOfRegion(LineSegments[I]))
1311       ++MinRegionCount;
1312 
1313   bool StartOfSkippedRegion = !LineSegments.empty() &&
1314                               !LineSegments.front()->HasCount &&
1315                               LineSegments.front()->IsRegionEntry;
1316 
1317   HasMultipleRegions = MinRegionCount > 1;
1318   Mapped =
1319       !StartOfSkippedRegion &&
1320       ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));
1321 
1322   if (!Mapped)
1323     return;
1324 
1325   // Pick the max count from the non-gap, region entry segments and the
1326   // wrapped count.
1327   if (WrappedSegment)
1328     ExecutionCount = WrappedSegment->Count;
1329   if (!MinRegionCount)
1330     return;
1331   for (const auto *LS : LineSegments)
1332     if (isStartOfRegion(LS))
1333       ExecutionCount = std::max(ExecutionCount, LS->Count);
1334 }
1335 
1336 LineCoverageIterator &LineCoverageIterator::operator++() {
1337   if (Next == CD.end()) {
1338     Stats = LineCoverageStats();
1339     Ended = true;
1340     return *this;
1341   }
1342   if (Segments.size())
1343     WrappedSegment = Segments.back();
1344   Segments.clear();
1345   while (Next != CD.end() && Next->Line == Line)
1346     Segments.push_back(&*Next++);
1347   Stats = LineCoverageStats(Segments, WrappedSegment, Line);
1348   ++Line;
1349   return *this;
1350 }
1351 
1352 static std::string getCoverageMapErrString(coveragemap_error Err,
1353                                            const std::string &ErrMsg = "") {
1354   std::string Msg;
1355   raw_string_ostream OS(Msg);
1356 
1357   switch (Err) {
1358   case coveragemap_error::success:
1359     OS << "success";
1360     break;
1361   case coveragemap_error::eof:
1362     OS << "end of File";
1363     break;
1364   case coveragemap_error::no_data_found:
1365     OS << "no coverage data found";
1366     break;
1367   case coveragemap_error::unsupported_version:
1368     OS << "unsupported coverage format version";
1369     break;
1370   case coveragemap_error::truncated:
1371     OS << "truncated coverage data";
1372     break;
1373   case coveragemap_error::malformed:
1374     OS << "malformed coverage data";
1375     break;
1376   case coveragemap_error::decompression_failed:
1377     OS << "failed to decompress coverage data (zlib)";
1378     break;
1379   case coveragemap_error::invalid_or_missing_arch_specifier:
1380     OS << "`-arch` specifier is invalid or missing for universal binary";
1381     break;
1382   }
1383 
1384   // If optional error message is not empty, append it to the message.
1385   if (!ErrMsg.empty())
1386     OS << ": " << ErrMsg;
1387 
1388   return Msg;
1389 }
1390 
1391 namespace {
1392 
1393 // FIXME: This class is only here to support the transition to llvm::Error. It
1394 // will be removed once this transition is complete. Clients should prefer to
1395 // deal with the Error value directly, rather than converting to error_code.
1396 class CoverageMappingErrorCategoryType : public std::error_category {
1397   const char *name() const noexcept override { return "llvm.coveragemap"; }
1398   std::string message(int IE) const override {
1399     return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
1400   }
1401 };
1402 
1403 } // end anonymous namespace
1404 
1405 std::string CoverageMapError::message() const {
1406   return getCoverageMapErrString(Err, Msg);
1407 }
1408 
1409 const std::error_category &llvm::coverage::coveragemap_category() {
1410   static CoverageMappingErrorCategoryType ErrorCategory;
1411   return ErrorCategory;
1412 }
1413 
1414 char CoverageMapError::ID = 0;
1415