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/STLExtras.h"
18#include "llvm/ADT/SmallBitVector.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/StringExtras.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Object/BuildID.h"
23#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
24#include "llvm/ProfileData/InstrProfReader.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/Errc.h"
27#include "llvm/Support/Error.h"
28#include "llvm/Support/ErrorHandling.h"
29#include "llvm/Support/MemoryBuffer.h"
30#include "llvm/Support/VirtualFileSystem.h"
31#include "llvm/Support/raw_ostream.h"
32#include <algorithm>
33#include <cassert>
34#include <cmath>
35#include <cstdint>
36#include <iterator>
37#include <map>
38#include <memory>
39#include <optional>
40#include <stack>
41#include <string>
42#include <system_error>
43#include <utility>
44#include <vector>
45
46using namespace llvm;
47using namespace coverage;
48
49#define DEBUG_TYPE "coverage-mapping"
50
51Counter CounterExpressionBuilder::get(const CounterExpression &E) {
52 auto It = ExpressionIndices.find(Val: E);
53 if (It != ExpressionIndices.end())
54 return Counter::getExpression(ExpressionId: It->second);
55 unsigned I = Expressions.size();
56 Expressions.push_back(x: E);
57 ExpressionIndices[E] = I;
58 return Counter::getExpression(ExpressionId: I);
59}
60
61void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
62 SmallVectorImpl<Term> &Terms) {
63 switch (C.getKind()) {
64 case Counter::Zero:
65 break;
66 case Counter::CounterValueReference:
67 Terms.emplace_back(Args: C.getCounterID(), Args&: Factor);
68 break;
69 case Counter::Expression:
70 const auto &E = Expressions[C.getExpressionID()];
71 extractTerms(C: E.LHS, Factor, Terms);
72 extractTerms(
73 C: E.RHS, Factor: E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);
74 break;
75 }
76}
77
78Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
79 // Gather constant terms.
80 SmallVector<Term, 32> Terms;
81 extractTerms(C: ExpressionTree, Factor: +1, Terms);
82
83 // If there are no terms, this is just a zero. The algorithm below assumes at
84 // least one term.
85 if (Terms.size() == 0)
86 return Counter::getZero();
87
88 // Group the terms by counter ID.
89 llvm::sort(C&: Terms, Comp: [](const Term &LHS, const Term &RHS) {
90 return LHS.CounterID < RHS.CounterID;
91 });
92
93 // Combine terms by counter ID to eliminate counters that sum to zero.
94 auto Prev = Terms.begin();
95 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
96 if (I->CounterID == Prev->CounterID) {
97 Prev->Factor += I->Factor;
98 continue;
99 }
100 ++Prev;
101 *Prev = *I;
102 }
103 Terms.erase(CS: ++Prev, CE: Terms.end());
104
105 Counter C;
106 // Create additions. We do this before subtractions to avoid constructs like
107 // ((0 - X) + Y), as opposed to (Y - X).
108 for (auto T : Terms) {
109 if (T.Factor <= 0)
110 continue;
111 for (int I = 0; I < T.Factor; ++I)
112 if (C.isZero())
113 C = Counter::getCounter(CounterId: T.CounterID);
114 else
115 C = get(E: CounterExpression(CounterExpression::Add, C,
116 Counter::getCounter(CounterId: T.CounterID)));
117 }
118
119 // Create subtractions.
120 for (auto T : Terms) {
121 if (T.Factor >= 0)
122 continue;
123 for (int I = 0; I < -T.Factor; ++I)
124 C = get(E: CounterExpression(CounterExpression::Subtract, C,
125 Counter::getCounter(CounterId: T.CounterID)));
126 }
127 return C;
128}
129
130Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS, bool Simplify) {
131 auto Cnt = get(E: CounterExpression(CounterExpression::Add, LHS, RHS));
132 return Simplify ? simplify(ExpressionTree: Cnt) : Cnt;
133}
134
135Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS,
136 bool Simplify) {
137 auto Cnt = get(E: CounterExpression(CounterExpression::Subtract, LHS, RHS));
138 return Simplify ? simplify(ExpressionTree: Cnt) : Cnt;
139}
140
141void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
142 switch (C.getKind()) {
143 case Counter::Zero:
144 OS << '0';
145 return;
146 case Counter::CounterValueReference:
147 OS << '#' << C.getCounterID();
148 break;
149 case Counter::Expression: {
150 if (C.getExpressionID() >= Expressions.size())
151 return;
152 const auto &E = Expressions[C.getExpressionID()];
153 OS << '(';
154 dump(C: E.LHS, OS);
155 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
156 dump(C: E.RHS, OS);
157 OS << ')';
158 break;
159 }
160 }
161 if (CounterValues.empty())
162 return;
163 Expected<int64_t> Value = evaluate(C);
164 if (auto E = Value.takeError()) {
165 consumeError(Err: std::move(E));
166 return;
167 }
168 OS << '[' << *Value << ']';
169}
170
171Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
172 struct StackElem {
173 Counter ICounter;
174 int64_t LHS = 0;
175 enum {
176 KNeverVisited = 0,
177 KVisitedOnce = 1,
178 KVisitedTwice = 2,
179 } VisitCount = KNeverVisited;
180 };
181
182 std::stack<StackElem> CounterStack;
183 CounterStack.push(x: {.ICounter: C});
184
185 int64_t LastPoppedValue;
186
187 while (!CounterStack.empty()) {
188 StackElem &Current = CounterStack.top();
189
190 switch (Current.ICounter.getKind()) {
191 case Counter::Zero:
192 LastPoppedValue = 0;
193 CounterStack.pop();
194 break;
195 case Counter::CounterValueReference:
196 if (Current.ICounter.getCounterID() >= CounterValues.size())
197 return errorCodeToError(EC: errc::argument_out_of_domain);
198 LastPoppedValue = CounterValues[Current.ICounter.getCounterID()];
199 CounterStack.pop();
200 break;
201 case Counter::Expression: {
202 if (Current.ICounter.getExpressionID() >= Expressions.size())
203 return errorCodeToError(EC: errc::argument_out_of_domain);
204 const auto &E = Expressions[Current.ICounter.getExpressionID()];
205 if (Current.VisitCount == StackElem::KNeverVisited) {
206 CounterStack.push(x: StackElem{.ICounter: E.LHS});
207 Current.VisitCount = StackElem::KVisitedOnce;
208 } else if (Current.VisitCount == StackElem::KVisitedOnce) {
209 Current.LHS = LastPoppedValue;
210 CounterStack.push(x: StackElem{.ICounter: E.RHS});
211 Current.VisitCount = StackElem::KVisitedTwice;
212 } else {
213 int64_t LHS = Current.LHS;
214 int64_t RHS = LastPoppedValue;
215 LastPoppedValue =
216 E.Kind == CounterExpression::Subtract ? LHS - RHS : LHS + RHS;
217 CounterStack.pop();
218 }
219 break;
220 }
221 }
222 }
223
224 return LastPoppedValue;
225}
226
227mcdc::TVIdxBuilder::TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs,
228 int Offset)
229 : Indices(NextIDs.size()) {
230 // Construct Nodes and set up each InCount
231 auto N = NextIDs.size();
232 SmallVector<MCDCNode> Nodes(N);
233 for (unsigned ID = 0; ID < N; ++ID) {
234 for (unsigned C = 0; C < 2; ++C) {
235#ifndef NDEBUG
236 Indices[ID][C] = INT_MIN;
237#endif
238 auto NextID = NextIDs[ID][C];
239 Nodes[ID].NextIDs[C] = NextID;
240 if (NextID >= 0)
241 ++Nodes[NextID].InCount;
242 }
243 }
244
245 // Sort key ordered by <-Width, Ord>
246 SmallVector<std::tuple<int, /// -Width
247 unsigned, /// Ord
248 int, /// ID
249 unsigned /// Cond (0 or 1)
250 >>
251 Decisions;
252
253 // Traverse Nodes to assign Idx
254 SmallVector<int> Q;
255 assert(Nodes[0].InCount == 0);
256 Nodes[0].Width = 1;
257 Q.push_back(Elt: 0);
258
259 unsigned Ord = 0;
260 while (!Q.empty()) {
261 auto IID = Q.begin();
262 int ID = *IID;
263 Q.erase(CI: IID);
264 auto &Node = Nodes[ID];
265 assert(Node.Width > 0);
266
267 for (unsigned I = 0; I < 2; ++I) {
268 auto NextID = Node.NextIDs[I];
269 assert(NextID != 0 && "NextID should not point to the top");
270 if (NextID < 0) {
271 // Decision
272 Decisions.emplace_back(Args: -Node.Width, Args: Ord++, Args&: ID, Args&: I);
273 assert(Ord == Decisions.size());
274 continue;
275 }
276
277 // Inter Node
278 auto &NextNode = Nodes[NextID];
279 assert(NextNode.InCount > 0);
280
281 // Assign Idx
282 assert(Indices[ID][I] == INT_MIN);
283 Indices[ID][I] = NextNode.Width;
284 auto NextWidth = int64_t(NextNode.Width) + Node.Width;
285 if (NextWidth > HardMaxTVs) {
286 NumTestVectors = HardMaxTVs; // Overflow
287 return;
288 }
289 NextNode.Width = NextWidth;
290
291 // Ready if all incomings are processed.
292 // Or NextNode.Width hasn't been confirmed yet.
293 if (--NextNode.InCount == 0)
294 Q.push_back(Elt: NextID);
295 }
296 }
297
298 llvm::sort(C&: Decisions);
299
300 // Assign TestVector Indices in Decision Nodes
301 int64_t CurIdx = 0;
302 for (auto [NegWidth, Ord, ID, C] : Decisions) {
303 int Width = -NegWidth;
304 assert(Nodes[ID].Width == Width);
305 assert(Nodes[ID].NextIDs[C] < 0);
306 assert(Indices[ID][C] == INT_MIN);
307 Indices[ID][C] = Offset + CurIdx;
308 CurIdx += Width;
309 if (CurIdx > HardMaxTVs) {
310 NumTestVectors = HardMaxTVs; // Overflow
311 return;
312 }
313 }
314
315 assert(CurIdx < HardMaxTVs);
316 NumTestVectors = CurIdx;
317
318#ifndef NDEBUG
319 for (const auto &Idxs : Indices)
320 for (auto Idx : Idxs)
321 assert(Idx != INT_MIN);
322 SavedNodes = std::move(Nodes);
323#endif
324}
325
326namespace {
327
328/// Construct this->NextIDs with Branches for TVIdxBuilder to use it
329/// before MCDCRecordProcessor().
330class NextIDsBuilder {
331protected:
332 SmallVector<mcdc::ConditionIDs> NextIDs;
333
334public:
335 NextIDsBuilder(const ArrayRef<const CounterMappingRegion *> Branches)
336 : NextIDs(Branches.size()) {
337#ifndef NDEBUG
338 DenseSet<mcdc::ConditionID> SeenIDs;
339#endif
340 for (const auto *Branch : Branches) {
341 const auto &BranchParams = Branch->getBranchParams();
342 assert(SeenIDs.insert(BranchParams.ID).second && "Duplicate CondID");
343 NextIDs[BranchParams.ID] = BranchParams.Conds;
344 }
345 assert(SeenIDs.size() == Branches.size());
346 }
347};
348
349class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder {
350 /// A bitmap representing the executed test vectors for a boolean expression.
351 /// Each index of the bitmap corresponds to a possible test vector. An index
352 /// with a bit value of '1' indicates that the corresponding Test Vector
353 /// identified by that index was executed.
354 const BitVector &Bitmap;
355
356 /// Decision Region to which the ExecutedTestVectorBitmap applies.
357 const CounterMappingRegion &Region;
358 const mcdc::DecisionParameters &DecisionParams;
359
360 /// Array of branch regions corresponding each conditions in the boolean
361 /// expression.
362 ArrayRef<const CounterMappingRegion *> Branches;
363
364 /// Total number of conditions in the boolean expression.
365 unsigned NumConditions;
366
367 /// Vector used to track whether a condition is constant folded.
368 MCDCRecord::BoolVector Folded;
369
370 /// Mapping of calculated MC/DC Independence Pairs for each condition.
371 MCDCRecord::TVPairMap IndependencePairs;
372
373 /// Storage for ExecVectors
374 /// ExecVectors is the alias of its 0th element.
375 std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond;
376
377 /// Actual executed Test Vectors for the boolean expression, based on
378 /// ExecutedTestVectorBitmap.
379 MCDCRecord::TestVectors &ExecVectors;
380
381 /// Number of False items in ExecVectors
382 unsigned NumExecVectorsF;
383
384#ifndef NDEBUG
385 DenseSet<unsigned> TVIdxs;
386#endif
387
388 bool IsVersion11;
389
390public:
391 MCDCRecordProcessor(const BitVector &Bitmap,
392 const CounterMappingRegion &Region,
393 ArrayRef<const CounterMappingRegion *> Branches,
394 bool IsVersion11)
395 : NextIDsBuilder(Branches), TVIdxBuilder(this->NextIDs), Bitmap(Bitmap),
396 Region(Region), DecisionParams(Region.getDecisionParams()),
397 Branches(Branches), NumConditions(DecisionParams.NumConditions),
398 Folded(NumConditions, false), IndependencePairs(NumConditions),
399 ExecVectors(ExecVectorsByCond[false]), IsVersion11(IsVersion11) {}
400
401private:
402 // Walk the binary decision diagram and try assigning both false and true to
403 // each node. When a terminal node (ID == 0) is reached, fill in the value in
404 // the truth table.
405 void buildTestVector(MCDCRecord::TestVector &TV, mcdc::ConditionID ID,
406 int TVIdx) {
407 for (auto MCDCCond : {MCDCRecord::MCDC_False, MCDCRecord::MCDC_True}) {
408 static_assert(MCDCRecord::MCDC_False == 0);
409 static_assert(MCDCRecord::MCDC_True == 1);
410 TV.set(I: ID, Val: MCDCCond);
411 auto NextID = NextIDs[ID][MCDCCond];
412 auto NextTVIdx = TVIdx + Indices[ID][MCDCCond];
413 assert(NextID == SavedNodes[ID].NextIDs[MCDCCond]);
414 if (NextID >= 0) {
415 buildTestVector(TV, ID: NextID, TVIdx: NextTVIdx);
416 continue;
417 }
418
419 assert(TVIdx < SavedNodes[ID].Width);
420 assert(TVIdxs.insert(NextTVIdx).second && "Duplicate TVIdx");
421
422 if (!Bitmap[IsVersion11
423 ? DecisionParams.BitmapIdx * CHAR_BIT + TV.getIndex()
424 : DecisionParams.BitmapIdx - NumTestVectors + NextTVIdx])
425 continue;
426
427 // Copy the completed test vector to the vector of testvectors.
428 // The final value (T,F) is equal to the last non-dontcare state on the
429 // path (in a short-circuiting system).
430 ExecVectorsByCond[MCDCCond].push_back(Elt: {TV, MCDCCond});
431 }
432
433 // Reset back to DontCare.
434 TV.set(I: ID, Val: MCDCRecord::MCDC_DontCare);
435 }
436
437 /// Walk the bits in the bitmap. A bit set to '1' indicates that the test
438 /// vector at the corresponding index was executed during a test run.
439 void findExecutedTestVectors() {
440 // Walk the binary decision diagram to enumerate all possible test vectors.
441 // We start at the root node (ID == 0) with all values being DontCare.
442 // `TVIdx` starts with 0 and is in the traversal.
443 // `Index` encodes the bitmask of true values and is initially 0.
444 MCDCRecord::TestVector TV(NumConditions);
445 buildTestVector(TV, ID: 0, TVIdx: 0);
446 assert(TVIdxs.size() == unsigned(NumTestVectors) &&
447 "TVIdxs wasn't fulfilled");
448
449 // Fill ExecVectors order by False items and True items.
450 // ExecVectors is the alias of ExecVectorsByCond[false], so
451 // Append ExecVectorsByCond[true] on it.
452 NumExecVectorsF = ExecVectors.size();
453 auto &ExecVectorsT = ExecVectorsByCond[true];
454 ExecVectors.append(in_start: std::make_move_iterator(i: ExecVectorsT.begin()),
455 in_end: std::make_move_iterator(i: ExecVectorsT.end()));
456 }
457
458 // Find an independence pair for each condition:
459 // - The condition is true in one test and false in the other.
460 // - The decision outcome is true one test and false in the other.
461 // - All other conditions' values must be equal or marked as "don't care".
462 void findIndependencePairs() {
463 unsigned NumTVs = ExecVectors.size();
464 for (unsigned I = NumExecVectorsF; I < NumTVs; ++I) {
465 const auto &[A, ACond] = ExecVectors[I];
466 assert(ACond == MCDCRecord::MCDC_True);
467 for (unsigned J = 0; J < NumExecVectorsF; ++J) {
468 const auto &[B, BCond] = ExecVectors[J];
469 assert(BCond == MCDCRecord::MCDC_False);
470 // If the two vectors differ in exactly one condition, ignoring DontCare
471 // conditions, we have found an independence pair.
472 auto AB = A.getDifferences(B);
473 if (AB.count() == 1)
474 IndependencePairs.insert(
475 KV: {AB.find_first(), std::make_pair(x: J + 1, y: I + 1)});
476 }
477 }
478 }
479
480public:
481 /// Process the MC/DC Record in order to produce a result for a boolean
482 /// expression. This process includes tracking the conditions that comprise
483 /// the decision region, calculating the list of all possible test vectors,
484 /// marking the executed test vectors, and then finding an Independence Pair
485 /// out of the executed test vectors for each condition in the boolean
486 /// expression. A condition is tracked to ensure that its ID can be mapped to
487 /// its ordinal position in the boolean expression. The condition's source
488 /// location is also tracked, as well as whether it is constant folded (in
489 /// which case it is excuded from the metric).
490 MCDCRecord processMCDCRecord() {
491 unsigned I = 0;
492 MCDCRecord::CondIDMap PosToID;
493 MCDCRecord::LineColPairMap CondLoc;
494
495 // Walk the Record's BranchRegions (representing Conditions) in order to:
496 // - Hash the condition based on its corresponding ID. This will be used to
497 // calculate the test vectors.
498 // - Keep a map of the condition's ordinal position (1, 2, 3, 4) to its
499 // actual ID. This will be used to visualize the conditions in the
500 // correct order.
501 // - Keep track of the condition source location. This will be used to
502 // visualize where the condition is.
503 // - Record whether the condition is constant folded so that we exclude it
504 // from being measured.
505 for (const auto *B : Branches) {
506 const auto &BranchParams = B->getBranchParams();
507 PosToID[I] = BranchParams.ID;
508 CondLoc[I] = B->startLoc();
509 Folded[I++] = (B->Count.isZero() && B->FalseCount.isZero());
510 }
511
512 // Using Profile Bitmap from runtime, mark the executed test vectors.
513 findExecutedTestVectors();
514
515 // Compare executed test vectors against each other to find an independence
516 // pairs for each condition. This processing takes the most time.
517 findIndependencePairs();
518
519 // Record Test vectors, executed vectors, and independence pairs.
520 return MCDCRecord(Region, std::move(ExecVectors),
521 std::move(IndependencePairs), std::move(Folded),
522 std::move(PosToID), std::move(CondLoc));
523 }
524};
525
526} // namespace
527
528Expected<MCDCRecord> CounterMappingContext::evaluateMCDCRegion(
529 const CounterMappingRegion &Region,
530 ArrayRef<const CounterMappingRegion *> Branches, bool IsVersion11) {
531
532 MCDCRecordProcessor MCDCProcessor(Bitmap, Region, Branches, IsVersion11);
533 return MCDCProcessor.processMCDCRecord();
534}
535
536unsigned CounterMappingContext::getMaxCounterID(const Counter &C) const {
537 struct StackElem {
538 Counter ICounter;
539 int64_t LHS = 0;
540 enum {
541 KNeverVisited = 0,
542 KVisitedOnce = 1,
543 KVisitedTwice = 2,
544 } VisitCount = KNeverVisited;
545 };
546
547 std::stack<StackElem> CounterStack;
548 CounterStack.push(x: {.ICounter: C});
549
550 int64_t LastPoppedValue;
551
552 while (!CounterStack.empty()) {
553 StackElem &Current = CounterStack.top();
554
555 switch (Current.ICounter.getKind()) {
556 case Counter::Zero:
557 LastPoppedValue = 0;
558 CounterStack.pop();
559 break;
560 case Counter::CounterValueReference:
561 LastPoppedValue = Current.ICounter.getCounterID();
562 CounterStack.pop();
563 break;
564 case Counter::Expression: {
565 if (Current.ICounter.getExpressionID() >= Expressions.size()) {
566 LastPoppedValue = 0;
567 CounterStack.pop();
568 } else {
569 const auto &E = Expressions[Current.ICounter.getExpressionID()];
570 if (Current.VisitCount == StackElem::KNeverVisited) {
571 CounterStack.push(x: StackElem{.ICounter: E.LHS});
572 Current.VisitCount = StackElem::KVisitedOnce;
573 } else if (Current.VisitCount == StackElem::KVisitedOnce) {
574 Current.LHS = LastPoppedValue;
575 CounterStack.push(x: StackElem{.ICounter: E.RHS});
576 Current.VisitCount = StackElem::KVisitedTwice;
577 } else {
578 int64_t LHS = Current.LHS;
579 int64_t RHS = LastPoppedValue;
580 LastPoppedValue = std::max(a: LHS, b: RHS);
581 CounterStack.pop();
582 }
583 }
584 break;
585 }
586 }
587 }
588
589 return LastPoppedValue;
590}
591
592void FunctionRecordIterator::skipOtherFiles() {
593 while (Current != Records.end() && !Filename.empty() &&
594 Filename != Current->Filenames[0])
595 ++Current;
596 if (Current == Records.end())
597 *this = FunctionRecordIterator();
598}
599
600ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(
601 StringRef Filename) const {
602 size_t FilenameHash = hash_value(S: Filename);
603 auto RecordIt = FilenameHash2RecordIndices.find(Val: FilenameHash);
604 if (RecordIt == FilenameHash2RecordIndices.end())
605 return {};
606 return RecordIt->second;
607}
608
609static unsigned getMaxCounterID(const CounterMappingContext &Ctx,
610 const CoverageMappingRecord &Record) {
611 unsigned MaxCounterID = 0;
612 for (const auto &Region : Record.MappingRegions) {
613 MaxCounterID = std::max(a: MaxCounterID, b: Ctx.getMaxCounterID(C: Region.Count));
614 }
615 return MaxCounterID;
616}
617
618/// Returns the bit count
619static unsigned getMaxBitmapSize(const CoverageMappingRecord &Record,
620 bool IsVersion11) {
621 unsigned MaxBitmapIdx = 0;
622 unsigned NumConditions = 0;
623 // Scan max(BitmapIdx).
624 // Note that `<=` is used insted of `<`, because `BitmapIdx == 0` is valid
625 // and `MaxBitmapIdx is `unsigned`. `BitmapIdx` is unique in the record.
626 for (const auto &Region : reverse(C: Record.MappingRegions)) {
627 if (Region.Kind != CounterMappingRegion::MCDCDecisionRegion)
628 continue;
629 const auto &DecisionParams = Region.getDecisionParams();
630 if (MaxBitmapIdx <= DecisionParams.BitmapIdx) {
631 MaxBitmapIdx = DecisionParams.BitmapIdx;
632 NumConditions = DecisionParams.NumConditions;
633 }
634 }
635
636 if (IsVersion11)
637 MaxBitmapIdx = MaxBitmapIdx * CHAR_BIT +
638 llvm::alignTo(Value: uint64_t(1) << NumConditions, CHAR_BIT);
639
640 return MaxBitmapIdx;
641}
642
643namespace {
644
645/// Collect Decisions, Branchs, and Expansions and associate them.
646class MCDCDecisionRecorder {
647private:
648 /// This holds the DecisionRegion and MCDCBranches under it.
649 /// Also traverses Expansion(s).
650 /// The Decision has the number of MCDCBranches and will complete
651 /// when it is filled with unique ConditionID of MCDCBranches.
652 struct DecisionRecord {
653 const CounterMappingRegion *DecisionRegion;
654
655 /// They are reflected from DecisionRegion for convenience.
656 mcdc::DecisionParameters DecisionParams;
657 LineColPair DecisionStartLoc;
658 LineColPair DecisionEndLoc;
659
660 /// This is passed to `MCDCRecordProcessor`, so this should be compatible
661 /// to`ArrayRef<const CounterMappingRegion *>`.
662 SmallVector<const CounterMappingRegion *> MCDCBranches;
663
664 /// IDs that are stored in MCDCBranches
665 /// Complete when all IDs (1 to NumConditions) are met.
666 DenseSet<mcdc::ConditionID> ConditionIDs;
667
668 /// Set of IDs of Expansion(s) that are relevant to DecisionRegion
669 /// and its children (via expansions).
670 /// FileID pointed by ExpandedFileID is dedicated to the expansion, so
671 /// the location in the expansion doesn't matter.
672 DenseSet<unsigned> ExpandedFileIDs;
673
674 DecisionRecord(const CounterMappingRegion &Decision)
675 : DecisionRegion(&Decision),
676 DecisionParams(Decision.getDecisionParams()),
677 DecisionStartLoc(Decision.startLoc()),
678 DecisionEndLoc(Decision.endLoc()) {
679 assert(Decision.Kind == CounterMappingRegion::MCDCDecisionRegion);
680 }
681
682 /// Determine whether DecisionRecord dominates `R`.
683 bool dominates(const CounterMappingRegion &R) const {
684 // Determine whether `R` is included in `DecisionRegion`.
685 if (R.FileID == DecisionRegion->FileID &&
686 R.startLoc() >= DecisionStartLoc && R.endLoc() <= DecisionEndLoc)
687 return true;
688
689 // Determine whether `R` is pointed by any of Expansions.
690 return ExpandedFileIDs.contains(V: R.FileID);
691 }
692
693 enum Result {
694 NotProcessed = 0, /// Irrelevant to this Decision
695 Processed, /// Added to this Decision
696 Completed, /// Added and filled this Decision
697 };
698
699 /// Add Branch into the Decision
700 /// \param Branch expects MCDCBranchRegion
701 /// \returns NotProcessed/Processed/Completed
702 Result addBranch(const CounterMappingRegion &Branch) {
703 assert(Branch.Kind == CounterMappingRegion::MCDCBranchRegion);
704
705 auto ConditionID = Branch.getBranchParams().ID;
706
707 if (ConditionIDs.contains(V: ConditionID) ||
708 ConditionID >= DecisionParams.NumConditions)
709 return NotProcessed;
710
711 if (!this->dominates(R: Branch))
712 return NotProcessed;
713
714 assert(MCDCBranches.size() < DecisionParams.NumConditions);
715
716 // Put `ID=0` in front of `MCDCBranches` for convenience
717 // even if `MCDCBranches` is not topological.
718 if (ConditionID == 0)
719 MCDCBranches.insert(I: MCDCBranches.begin(), Elt: &Branch);
720 else
721 MCDCBranches.push_back(Elt: &Branch);
722
723 // Mark `ID` as `assigned`.
724 ConditionIDs.insert(V: ConditionID);
725
726 // `Completed` when `MCDCBranches` is full
727 return (MCDCBranches.size() == DecisionParams.NumConditions ? Completed
728 : Processed);
729 }
730
731 /// Record Expansion if it is relevant to this Decision.
732 /// Each `Expansion` may nest.
733 /// \returns true if recorded.
734 bool recordExpansion(const CounterMappingRegion &Expansion) {
735 if (!this->dominates(R: Expansion))
736 return false;
737
738 ExpandedFileIDs.insert(V: Expansion.ExpandedFileID);
739 return true;
740 }
741 };
742
743private:
744 /// Decisions in progress
745 /// DecisionRecord is added for each MCDCDecisionRegion.
746 /// DecisionRecord is removed when Decision is completed.
747 SmallVector<DecisionRecord> Decisions;
748
749public:
750 ~MCDCDecisionRecorder() {
751 assert(Decisions.empty() && "All Decisions have not been resolved");
752 }
753
754 /// Register Region and start recording.
755 void registerDecision(const CounterMappingRegion &Decision) {
756 Decisions.emplace_back(Args: Decision);
757 }
758
759 void recordExpansion(const CounterMappingRegion &Expansion) {
760 any_of(Range&: Decisions, P: [&Expansion](auto &Decision) {
761 return Decision.recordExpansion(Expansion);
762 });
763 }
764
765 using DecisionAndBranches =
766 std::pair<const CounterMappingRegion *, /// Decision
767 SmallVector<const CounterMappingRegion *> /// Branches
768 >;
769
770 /// Add MCDCBranchRegion to DecisionRecord.
771 /// \param Branch to be processed
772 /// \returns DecisionsAndBranches if DecisionRecord completed.
773 /// Or returns nullopt.
774 std::optional<DecisionAndBranches>
775 processBranch(const CounterMappingRegion &Branch) {
776 // Seek each Decision and apply Region to it.
777 for (auto DecisionIter = Decisions.begin(), DecisionEnd = Decisions.end();
778 DecisionIter != DecisionEnd; ++DecisionIter)
779 switch (DecisionIter->addBranch(Branch)) {
780 case DecisionRecord::NotProcessed:
781 continue;
782 case DecisionRecord::Processed:
783 return std::nullopt;
784 case DecisionRecord::Completed:
785 DecisionAndBranches Result =
786 std::make_pair(x&: DecisionIter->DecisionRegion,
787 y: std::move(DecisionIter->MCDCBranches));
788 Decisions.erase(CI: DecisionIter); // No longer used.
789 return Result;
790 }
791
792 llvm_unreachable("Branch not found in Decisions");
793 }
794};
795
796} // namespace
797
798Error CoverageMapping::loadFunctionRecord(
799 const CoverageMappingRecord &Record,
800 IndexedInstrProfReader &ProfileReader) {
801 StringRef OrigFuncName = Record.FunctionName;
802 if (OrigFuncName.empty())
803 return make_error<CoverageMapError>(Args: coveragemap_error::malformed,
804 Args: "record function name is empty");
805
806 if (Record.Filenames.empty())
807 OrigFuncName = getFuncNameWithoutPrefix(PGOFuncName: OrigFuncName);
808 else
809 OrigFuncName = getFuncNameWithoutPrefix(PGOFuncName: OrigFuncName, FileName: Record.Filenames[0]);
810
811 CounterMappingContext Ctx(Record.Expressions);
812
813 std::vector<uint64_t> Counts;
814 if (Error E = ProfileReader.getFunctionCounts(FuncName: Record.FunctionName,
815 FuncHash: Record.FunctionHash, Counts)) {
816 instrprof_error IPE = std::get<0>(in: InstrProfError::take(E: std::move(E)));
817 if (IPE == instrprof_error::hash_mismatch) {
818 FuncHashMismatches.emplace_back(args: std::string(Record.FunctionName),
819 args: Record.FunctionHash);
820 return Error::success();
821 }
822 if (IPE != instrprof_error::unknown_function)
823 return make_error<InstrProfError>(Args&: IPE);
824 Counts.assign(n: getMaxCounterID(Ctx, Record) + 1, val: 0);
825 }
826 Ctx.setCounts(Counts);
827
828 bool IsVersion11 =
829 ProfileReader.getVersion() < IndexedInstrProf::ProfVersion::Version12;
830
831 BitVector Bitmap;
832 if (Error E = ProfileReader.getFunctionBitmap(FuncName: Record.FunctionName,
833 FuncHash: Record.FunctionHash, Bitmap)) {
834 instrprof_error IPE = std::get<0>(in: InstrProfError::take(E: std::move(E)));
835 if (IPE == instrprof_error::hash_mismatch) {
836 FuncHashMismatches.emplace_back(args: std::string(Record.FunctionName),
837 args: Record.FunctionHash);
838 return Error::success();
839 }
840 if (IPE != instrprof_error::unknown_function)
841 return make_error<InstrProfError>(Args&: IPE);
842 Bitmap = BitVector(getMaxBitmapSize(Record, IsVersion11));
843 }
844 Ctx.setBitmap(std::move(Bitmap));
845
846 assert(!Record.MappingRegions.empty() && "Function has no regions");
847
848 // This coverage record is a zero region for a function that's unused in
849 // some TU, but used in a different TU. Ignore it. The coverage maps from the
850 // the other TU will either be loaded (providing full region counts) or they
851 // won't (in which case we don't unintuitively report functions as uncovered
852 // when they have non-zero counts in the profile).
853 if (Record.MappingRegions.size() == 1 &&
854 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
855 return Error::success();
856
857 MCDCDecisionRecorder MCDCDecisions;
858 FunctionRecord Function(OrigFuncName, Record.Filenames);
859 for (const auto &Region : Record.MappingRegions) {
860 // MCDCDecisionRegion should be handled first since it overlaps with
861 // others inside.
862 if (Region.Kind == CounterMappingRegion::MCDCDecisionRegion) {
863 MCDCDecisions.registerDecision(Decision: Region);
864 continue;
865 }
866 Expected<int64_t> ExecutionCount = Ctx.evaluate(C: Region.Count);
867 if (auto E = ExecutionCount.takeError()) {
868 consumeError(Err: std::move(E));
869 return Error::success();
870 }
871 Expected<int64_t> AltExecutionCount = Ctx.evaluate(C: Region.FalseCount);
872 if (auto E = AltExecutionCount.takeError()) {
873 consumeError(Err: std::move(E));
874 return Error::success();
875 }
876 Function.pushRegion(Region, Count: *ExecutionCount, FalseCount: *AltExecutionCount,
877 HasSingleByteCoverage: ProfileReader.hasSingleByteCoverage());
878
879 // Record ExpansionRegion.
880 if (Region.Kind == CounterMappingRegion::ExpansionRegion) {
881 MCDCDecisions.recordExpansion(Expansion: Region);
882 continue;
883 }
884
885 // Do nothing unless MCDCBranchRegion.
886 if (Region.Kind != CounterMappingRegion::MCDCBranchRegion)
887 continue;
888
889 auto Result = MCDCDecisions.processBranch(Branch: Region);
890 if (!Result) // Any Decision doesn't complete.
891 continue;
892
893 auto MCDCDecision = Result->first;
894 auto &MCDCBranches = Result->second;
895
896 // Since the bitmap identifies the executed test vectors for an MC/DC
897 // DecisionRegion, all of the information is now available to process.
898 // This is where the bulk of the MC/DC progressing takes place.
899 Expected<MCDCRecord> Record =
900 Ctx.evaluateMCDCRegion(Region: *MCDCDecision, Branches: MCDCBranches, IsVersion11);
901 if (auto E = Record.takeError()) {
902 consumeError(Err: std::move(E));
903 return Error::success();
904 }
905
906 // Save the MC/DC Record so that it can be visualized later.
907 Function.pushMCDCRecord(Record: std::move(*Record));
908 }
909
910 // Don't create records for (filenames, function) pairs we've already seen.
911 auto FilenamesHash = hash_combine_range(first: Record.Filenames.begin(),
912 last: Record.Filenames.end());
913 if (!RecordProvenance[FilenamesHash].insert(V: hash_value(S: OrigFuncName)).second)
914 return Error::success();
915
916 Functions.push_back(x: std::move(Function));
917
918 // Performance optimization: keep track of the indices of the function records
919 // which correspond to each filename. This can be used to substantially speed
920 // up queries for coverage info in a file.
921 unsigned RecordIndex = Functions.size() - 1;
922 for (StringRef Filename : Record.Filenames) {
923 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(S: Filename)];
924 // Note that there may be duplicates in the filename set for a function
925 // record, because of e.g. macro expansions in the function in which both
926 // the macro and the function are defined in the same file.
927 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)
928 RecordIndices.push_back(Elt: RecordIndex);
929 }
930
931 return Error::success();
932}
933
934// This function is for memory optimization by shortening the lifetimes
935// of CoverageMappingReader instances.
936Error CoverageMapping::loadFromReaders(
937 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
938 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) {
939 for (const auto &CoverageReader : CoverageReaders) {
940 for (auto RecordOrErr : *CoverageReader) {
941 if (Error E = RecordOrErr.takeError())
942 return E;
943 const auto &Record = *RecordOrErr;
944 if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader))
945 return E;
946 }
947 }
948 return Error::success();
949}
950
951Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
952 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
953 IndexedInstrProfReader &ProfileReader) {
954 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
955 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, Coverage&: *Coverage))
956 return std::move(E);
957 return std::move(Coverage);
958}
959
960// If E is a no_data_found error, returns success. Otherwise returns E.
961static Error handleMaybeNoDataFoundError(Error E) {
962 return handleErrors(
963 E: std::move(E), Hs: [](const CoverageMapError &CME) {
964 if (CME.get() == coveragemap_error::no_data_found)
965 return static_cast<Error>(Error::success());
966 return make_error<CoverageMapError>(Args: CME.get(), Args: CME.getMessage());
967 });
968}
969
970Error CoverageMapping::loadFromFile(
971 StringRef Filename, StringRef Arch, StringRef CompilationDir,
972 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage,
973 bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) {
974 auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(
975 Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false);
976 if (std::error_code EC = CovMappingBufOrErr.getError())
977 return createFileError(F: Filename, E: errorCodeToError(EC));
978 MemoryBufferRef CovMappingBufRef =
979 CovMappingBufOrErr.get()->getMemBufferRef();
980 SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
981
982 SmallVector<object::BuildIDRef> BinaryIDs;
983 auto CoverageReadersOrErr = BinaryCoverageReader::create(
984 ObjectBuffer: CovMappingBufRef, Arch, ObjectFileBuffers&: Buffers, CompilationDir,
985 BinaryIDs: FoundBinaryIDs ? &BinaryIDs : nullptr);
986 if (Error E = CoverageReadersOrErr.takeError()) {
987 E = handleMaybeNoDataFoundError(E: std::move(E));
988 if (E)
989 return createFileError(F: Filename, E: std::move(E));
990 return E;
991 }
992
993 SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
994 for (auto &Reader : CoverageReadersOrErr.get())
995 Readers.push_back(Elt: std::move(Reader));
996 if (FoundBinaryIDs && !Readers.empty()) {
997 llvm::append_range(C&: *FoundBinaryIDs,
998 R: llvm::map_range(C&: BinaryIDs, F: [](object::BuildIDRef BID) {
999 return object::BuildID(BID);
1000 }));
1001 }
1002 DataFound |= !Readers.empty();
1003 if (Error E = loadFromReaders(CoverageReaders: Readers, ProfileReader, Coverage))
1004 return createFileError(F: Filename, E: std::move(E));
1005 return Error::success();
1006}
1007
1008Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
1009 ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
1010 vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir,
1011 const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) {
1012 auto ProfileReaderOrErr = IndexedInstrProfReader::create(Path: ProfileFilename, FS);
1013 if (Error E = ProfileReaderOrErr.takeError())
1014 return createFileError(F: ProfileFilename, E: std::move(E));
1015 auto ProfileReader = std::move(ProfileReaderOrErr.get());
1016 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
1017 bool DataFound = false;
1018
1019 auto GetArch = [&](size_t Idx) {
1020 if (Arches.empty())
1021 return StringRef();
1022 if (Arches.size() == 1)
1023 return Arches.front();
1024 return Arches[Idx];
1025 };
1026
1027 SmallVector<object::BuildID> FoundBinaryIDs;
1028 for (const auto &File : llvm::enumerate(First&: ObjectFilenames)) {
1029 if (Error E =
1030 loadFromFile(Filename: File.value(), Arch: GetArch(File.index()), CompilationDir,
1031 ProfileReader&: *ProfileReader, Coverage&: *Coverage, DataFound, FoundBinaryIDs: &FoundBinaryIDs))
1032 return std::move(E);
1033 }
1034
1035 if (BIDFetcher) {
1036 std::vector<object::BuildID> ProfileBinaryIDs;
1037 if (Error E = ProfileReader->readBinaryIds(BinaryIds&: ProfileBinaryIDs))
1038 return createFileError(F: ProfileFilename, E: std::move(E));
1039
1040 SmallVector<object::BuildIDRef> BinaryIDsToFetch;
1041 if (!ProfileBinaryIDs.empty()) {
1042 const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) {
1043 return std::lexicographical_compare(A.begin(), A.end(), B.begin(),
1044 B.end());
1045 };
1046 llvm::sort(C&: FoundBinaryIDs, Comp: Compare);
1047 std::set_difference(
1048 first1: ProfileBinaryIDs.begin(), last1: ProfileBinaryIDs.end(),
1049 first2: FoundBinaryIDs.begin(), last2: FoundBinaryIDs.end(),
1050 result: std::inserter(x&: BinaryIDsToFetch, i: BinaryIDsToFetch.end()), comp: Compare);
1051 }
1052
1053 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) {
1054 std::optional<std::string> PathOpt = BIDFetcher->fetch(BuildID: BinaryID);
1055 if (PathOpt) {
1056 std::string Path = std::move(*PathOpt);
1057 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef();
1058 if (Error E = loadFromFile(Filename: Path, Arch, CompilationDir, ProfileReader&: *ProfileReader,
1059 Coverage&: *Coverage, DataFound))
1060 return std::move(E);
1061 } else if (CheckBinaryIDs) {
1062 return createFileError(
1063 F: ProfileFilename,
1064 E: createStringError(EC: errc::no_such_file_or_directory,
1065 S: "Missing binary ID: " +
1066 llvm::toHex(Input: BinaryID, /*LowerCase=*/true)));
1067 }
1068 }
1069 }
1070
1071 if (!DataFound)
1072 return createFileError(
1073 F: join(Begin: ObjectFilenames.begin(), End: ObjectFilenames.end(), Separator: ", "),
1074 E: make_error<CoverageMapError>(Args: coveragemap_error::no_data_found));
1075 return std::move(Coverage);
1076}
1077
1078namespace {
1079
1080/// Distributes functions into instantiation sets.
1081///
1082/// An instantiation set is a collection of functions that have the same source
1083/// code, ie, template functions specializations.
1084class FunctionInstantiationSetCollector {
1085 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
1086 MapT InstantiatedFunctions;
1087
1088public:
1089 void insert(const FunctionRecord &Function, unsigned FileID) {
1090 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
1091 while (I != E && I->FileID != FileID)
1092 ++I;
1093 assert(I != E && "function does not cover the given file");
1094 auto &Functions = InstantiatedFunctions[I->startLoc()];
1095 Functions.push_back(x: &Function);
1096 }
1097
1098 MapT::iterator begin() { return InstantiatedFunctions.begin(); }
1099 MapT::iterator end() { return InstantiatedFunctions.end(); }
1100};
1101
1102class SegmentBuilder {
1103 std::vector<CoverageSegment> &Segments;
1104 SmallVector<const CountedRegion *, 8> ActiveRegions;
1105
1106 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
1107
1108 /// Emit a segment with the count from \p Region starting at \p StartLoc.
1109 //
1110 /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
1111 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
1112 void startSegment(const CountedRegion &Region, LineColPair StartLoc,
1113 bool IsRegionEntry, bool EmitSkippedRegion = false) {
1114 bool HasCount = !EmitSkippedRegion &&
1115 (Region.Kind != CounterMappingRegion::SkippedRegion);
1116
1117 // If the new segment wouldn't affect coverage rendering, skip it.
1118 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
1119 const auto &Last = Segments.back();
1120 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
1121 !Last.IsRegionEntry)
1122 return;
1123 }
1124
1125 if (HasCount)
1126 Segments.emplace_back(args&: StartLoc.first, args&: StartLoc.second,
1127 args: Region.ExecutionCount, args&: IsRegionEntry,
1128 args: Region.Kind == CounterMappingRegion::GapRegion);
1129 else
1130 Segments.emplace_back(args&: StartLoc.first, args&: StartLoc.second, args&: IsRegionEntry);
1131
1132 LLVM_DEBUG({
1133 const auto &Last = Segments.back();
1134 dbgs() << "Segment at " << Last.Line << ":" << Last.Col
1135 << " (count = " << Last.Count << ")"
1136 << (Last.IsRegionEntry ? ", RegionEntry" : "")
1137 << (!Last.HasCount ? ", Skipped" : "")
1138 << (Last.IsGapRegion ? ", Gap" : "") << "\n";
1139 });
1140 }
1141
1142 /// Emit segments for active regions which end before \p Loc.
1143 ///
1144 /// \p Loc: The start location of the next region. If std::nullopt, all active
1145 /// regions are completed.
1146 /// \p FirstCompletedRegion: Index of the first completed region.
1147 void completeRegionsUntil(std::optional<LineColPair> Loc,
1148 unsigned FirstCompletedRegion) {
1149 // Sort the completed regions by end location. This makes it simple to
1150 // emit closing segments in sorted order.
1151 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
1152 std::stable_sort(first: CompletedRegionsIt, last: ActiveRegions.end(),
1153 comp: [](const CountedRegion *L, const CountedRegion *R) {
1154 return L->endLoc() < R->endLoc();
1155 });
1156
1157 // Emit segments for all completed regions.
1158 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
1159 ++I) {
1160 const auto *CompletedRegion = ActiveRegions[I];
1161 assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
1162 "Completed region ends after start of new region");
1163
1164 const auto *PrevCompletedRegion = ActiveRegions[I - 1];
1165 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
1166
1167 // Don't emit any more segments if they start where the new region begins.
1168 if (Loc && CompletedSegmentLoc == *Loc)
1169 break;
1170
1171 // Don't emit a segment if the next completed region ends at the same
1172 // location as this one.
1173 if (CompletedSegmentLoc == CompletedRegion->endLoc())
1174 continue;
1175
1176 // Use the count from the last completed region which ends at this loc.
1177 for (unsigned J = I + 1; J < E; ++J)
1178 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
1179 CompletedRegion = ActiveRegions[J];
1180
1181 startSegment(Region: *CompletedRegion, StartLoc: CompletedSegmentLoc, IsRegionEntry: false);
1182 }
1183
1184 auto Last = ActiveRegions.back();
1185 if (FirstCompletedRegion && Last->endLoc() != *Loc) {
1186 // If there's a gap after the end of the last completed region and the
1187 // start of the new region, use the last active region to fill the gap.
1188 startSegment(Region: *ActiveRegions[FirstCompletedRegion - 1], StartLoc: Last->endLoc(),
1189 IsRegionEntry: false);
1190 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
1191 // Emit a skipped segment if there are no more active regions. This
1192 // ensures that gaps between functions are marked correctly.
1193 startSegment(Region: *Last, StartLoc: Last->endLoc(), IsRegionEntry: false, EmitSkippedRegion: true);
1194 }
1195
1196 // Pop the completed regions.
1197 ActiveRegions.erase(CS: CompletedRegionsIt, CE: ActiveRegions.end());
1198 }
1199
1200 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
1201 for (const auto &CR : enumerate(First&: Regions)) {
1202 auto CurStartLoc = CR.value().startLoc();
1203
1204 // Active regions which end before the current region need to be popped.
1205 auto CompletedRegions =
1206 std::stable_partition(first: ActiveRegions.begin(), last: ActiveRegions.end(),
1207 pred: [&](const CountedRegion *Region) {
1208 return !(Region->endLoc() <= CurStartLoc);
1209 });
1210 if (CompletedRegions != ActiveRegions.end()) {
1211 unsigned FirstCompletedRegion =
1212 std::distance(first: ActiveRegions.begin(), last: CompletedRegions);
1213 completeRegionsUntil(Loc: CurStartLoc, FirstCompletedRegion);
1214 }
1215
1216 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
1217
1218 // Try to emit a segment for the current region.
1219 if (CurStartLoc == CR.value().endLoc()) {
1220 // Avoid making zero-length regions active. If it's the last region,
1221 // emit a skipped segment. Otherwise use its predecessor's count.
1222 const bool Skipped =
1223 (CR.index() + 1) == Regions.size() ||
1224 CR.value().Kind == CounterMappingRegion::SkippedRegion;
1225 startSegment(Region: ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
1226 StartLoc: CurStartLoc, IsRegionEntry: !GapRegion, EmitSkippedRegion: Skipped);
1227 // If it is skipped segment, create a segment with last pushed
1228 // regions's count at CurStartLoc.
1229 if (Skipped && !ActiveRegions.empty())
1230 startSegment(Region: *ActiveRegions.back(), StartLoc: CurStartLoc, IsRegionEntry: false);
1231 continue;
1232 }
1233 if (CR.index() + 1 == Regions.size() ||
1234 CurStartLoc != Regions[CR.index() + 1].startLoc()) {
1235 // Emit a segment if the next region doesn't start at the same location
1236 // as this one.
1237 startSegment(Region: CR.value(), StartLoc: CurStartLoc, IsRegionEntry: !GapRegion);
1238 }
1239
1240 // This region is active (i.e not completed).
1241 ActiveRegions.push_back(Elt: &CR.value());
1242 }
1243
1244 // Complete any remaining active regions.
1245 if (!ActiveRegions.empty())
1246 completeRegionsUntil(Loc: std::nullopt, FirstCompletedRegion: 0);
1247 }
1248
1249 /// Sort a nested sequence of regions from a single file.
1250 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
1251 llvm::sort(C&: Regions, Comp: [](const CountedRegion &LHS, const CountedRegion &RHS) {
1252 if (LHS.startLoc() != RHS.startLoc())
1253 return LHS.startLoc() < RHS.startLoc();
1254 if (LHS.endLoc() != RHS.endLoc())
1255 // When LHS completely contains RHS, we sort LHS first.
1256 return RHS.endLoc() < LHS.endLoc();
1257 // If LHS and RHS cover the same area, we need to sort them according
1258 // to their kinds so that the most suitable region will become "active"
1259 // in combineRegions(). Because we accumulate counter values only from
1260 // regions of the same kind as the first region of the area, prefer
1261 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
1262 static_assert(CounterMappingRegion::CodeRegion <
1263 CounterMappingRegion::ExpansionRegion &&
1264 CounterMappingRegion::ExpansionRegion <
1265 CounterMappingRegion::SkippedRegion,
1266 "Unexpected order of region kind values");
1267 return LHS.Kind < RHS.Kind;
1268 });
1269 }
1270
1271 /// Combine counts of regions which cover the same area.
1272 static ArrayRef<CountedRegion>
1273 combineRegions(MutableArrayRef<CountedRegion> Regions) {
1274 if (Regions.empty())
1275 return Regions;
1276 auto Active = Regions.begin();
1277 auto End = Regions.end();
1278 for (auto I = Regions.begin() + 1; I != End; ++I) {
1279 if (Active->startLoc() != I->startLoc() ||
1280 Active->endLoc() != I->endLoc()) {
1281 // Shift to the next region.
1282 ++Active;
1283 if (Active != I)
1284 *Active = *I;
1285 continue;
1286 }
1287 // Merge duplicate region.
1288 // If CodeRegions and ExpansionRegions cover the same area, it's probably
1289 // a macro which is fully expanded to another macro. In that case, we need
1290 // to accumulate counts only from CodeRegions, or else the area will be
1291 // counted twice.
1292 // On the other hand, a macro may have a nested macro in its body. If the
1293 // outer macro is used several times, the ExpansionRegion for the nested
1294 // macro will also be added several times. These ExpansionRegions cover
1295 // the same source locations and have to be combined to reach the correct
1296 // value for that area.
1297 // We add counts of the regions of the same kind as the active region
1298 // to handle the both situations.
1299 if (I->Kind == Active->Kind) {
1300 assert(I->HasSingleByteCoverage == Active->HasSingleByteCoverage &&
1301 "Regions are generated in different coverage modes");
1302 if (I->HasSingleByteCoverage)
1303 Active->ExecutionCount = Active->ExecutionCount || I->ExecutionCount;
1304 else
1305 Active->ExecutionCount += I->ExecutionCount;
1306 }
1307 }
1308 return Regions.drop_back(N: std::distance(first: ++Active, last: End));
1309 }
1310
1311public:
1312 /// Build a sorted list of CoverageSegments from a list of Regions.
1313 static std::vector<CoverageSegment>
1314 buildSegments(MutableArrayRef<CountedRegion> Regions) {
1315 std::vector<CoverageSegment> Segments;
1316 SegmentBuilder Builder(Segments);
1317
1318 sortNestedRegions(Regions);
1319 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
1320
1321 LLVM_DEBUG({
1322 dbgs() << "Combined regions:\n";
1323 for (const auto &CR : CombinedRegions)
1324 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> "
1325 << CR.LineEnd << ":" << CR.ColumnEnd
1326 << " (count=" << CR.ExecutionCount << ")\n";
1327 });
1328
1329 Builder.buildSegmentsImpl(Regions: CombinedRegions);
1330
1331#ifndef NDEBUG
1332 for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
1333 const auto &L = Segments[I - 1];
1334 const auto &R = Segments[I];
1335 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
1336 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount)
1337 continue;
1338 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
1339 << " followed by " << R.Line << ":" << R.Col << "\n");
1340 assert(false && "Coverage segments not unique or sorted");
1341 }
1342 }
1343#endif
1344
1345 return Segments;
1346 }
1347};
1348
1349} // end anonymous namespace
1350
1351std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
1352 std::vector<StringRef> Filenames;
1353 for (const auto &Function : getCoveredFunctions())
1354 llvm::append_range(C&: Filenames, R: Function.Filenames);
1355 llvm::sort(C&: Filenames);
1356 auto Last = llvm::unique(R&: Filenames);
1357 Filenames.erase(first: Last, last: Filenames.end());
1358 return Filenames;
1359}
1360
1361static SmallBitVector gatherFileIDs(StringRef SourceFile,
1362 const FunctionRecord &Function) {
1363 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
1364 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
1365 if (SourceFile == Function.Filenames[I])
1366 FilenameEquivalence[I] = true;
1367 return FilenameEquivalence;
1368}
1369
1370/// Return the ID of the file where the definition of the function is located.
1371static std::optional<unsigned>
1372findMainViewFileID(const FunctionRecord &Function) {
1373 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
1374 for (const auto &CR : Function.CountedRegions)
1375 if (CR.Kind == CounterMappingRegion::ExpansionRegion)
1376 IsNotExpandedFile[CR.ExpandedFileID] = false;
1377 int I = IsNotExpandedFile.find_first();
1378 if (I == -1)
1379 return std::nullopt;
1380 return I;
1381}
1382
1383/// Check if SourceFile is the file that contains the definition of
1384/// the Function. Return the ID of the file in that case or std::nullopt
1385/// otherwise.
1386static std::optional<unsigned>
1387findMainViewFileID(StringRef SourceFile, const FunctionRecord &Function) {
1388 std::optional<unsigned> I = findMainViewFileID(Function);
1389 if (I && SourceFile == Function.Filenames[*I])
1390 return I;
1391 return std::nullopt;
1392}
1393
1394static bool isExpansion(const CountedRegion &R, unsigned FileID) {
1395 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
1396}
1397
1398CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
1399 CoverageData FileCoverage(Filename);
1400 std::vector<CountedRegion> Regions;
1401
1402 // Look up the function records in the given file. Due to hash collisions on
1403 // the filename, we may get back some records that are not in the file.
1404 ArrayRef<unsigned> RecordIndices =
1405 getImpreciseRecordIndicesForFilename(Filename);
1406 for (unsigned RecordIndex : RecordIndices) {
1407 const FunctionRecord &Function = Functions[RecordIndex];
1408 auto MainFileID = findMainViewFileID(SourceFile: Filename, Function);
1409 auto FileIDs = gatherFileIDs(SourceFile: Filename, Function);
1410 for (const auto &CR : Function.CountedRegions)
1411 if (FileIDs.test(Idx: CR.FileID)) {
1412 Regions.push_back(x: CR);
1413 if (MainFileID && isExpansion(R: CR, FileID: *MainFileID))
1414 FileCoverage.Expansions.emplace_back(args: CR, args: Function);
1415 }
1416 // Capture branch regions specific to the function (excluding expansions).
1417 for (const auto &CR : Function.CountedBranchRegions)
1418 if (FileIDs.test(Idx: CR.FileID) && (CR.FileID == CR.ExpandedFileID))
1419 FileCoverage.BranchRegions.push_back(x: CR);
1420 // Capture MCDC records specific to the function.
1421 for (const auto &MR : Function.MCDCRecords)
1422 if (FileIDs.test(Idx: MR.getDecisionRegion().FileID))
1423 FileCoverage.MCDCRecords.push_back(x: MR);
1424 }
1425
1426 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
1427 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1428
1429 return FileCoverage;
1430}
1431
1432std::vector<InstantiationGroup>
1433CoverageMapping::getInstantiationGroups(StringRef Filename) const {
1434 FunctionInstantiationSetCollector InstantiationSetCollector;
1435 // Look up the function records in the given file. Due to hash collisions on
1436 // the filename, we may get back some records that are not in the file.
1437 ArrayRef<unsigned> RecordIndices =
1438 getImpreciseRecordIndicesForFilename(Filename);
1439 for (unsigned RecordIndex : RecordIndices) {
1440 const FunctionRecord &Function = Functions[RecordIndex];
1441 auto MainFileID = findMainViewFileID(SourceFile: Filename, Function);
1442 if (!MainFileID)
1443 continue;
1444 InstantiationSetCollector.insert(Function, FileID: *MainFileID);
1445 }
1446
1447 std::vector<InstantiationGroup> Result;
1448 for (auto &InstantiationSet : InstantiationSetCollector) {
1449 InstantiationGroup IG{InstantiationSet.first.first,
1450 InstantiationSet.first.second,
1451 std::move(InstantiationSet.second)};
1452 Result.emplace_back(args: std::move(IG));
1453 }
1454 return Result;
1455}
1456
1457CoverageData
1458CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
1459 auto MainFileID = findMainViewFileID(Function);
1460 if (!MainFileID)
1461 return CoverageData();
1462
1463 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
1464 std::vector<CountedRegion> Regions;
1465 for (const auto &CR : Function.CountedRegions)
1466 if (CR.FileID == *MainFileID) {
1467 Regions.push_back(x: CR);
1468 if (isExpansion(R: CR, FileID: *MainFileID))
1469 FunctionCoverage.Expansions.emplace_back(args: CR, args: Function);
1470 }
1471 // Capture branch regions specific to the function (excluding expansions).
1472 for (const auto &CR : Function.CountedBranchRegions)
1473 if (CR.FileID == *MainFileID)
1474 FunctionCoverage.BranchRegions.push_back(x: CR);
1475
1476 // Capture MCDC records specific to the function.
1477 for (const auto &MR : Function.MCDCRecords)
1478 if (MR.getDecisionRegion().FileID == *MainFileID)
1479 FunctionCoverage.MCDCRecords.push_back(x: MR);
1480
1481 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
1482 << "\n");
1483 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1484
1485 return FunctionCoverage;
1486}
1487
1488CoverageData CoverageMapping::getCoverageForExpansion(
1489 const ExpansionRecord &Expansion) const {
1490 CoverageData ExpansionCoverage(
1491 Expansion.Function.Filenames[Expansion.FileID]);
1492 std::vector<CountedRegion> Regions;
1493 for (const auto &CR : Expansion.Function.CountedRegions)
1494 if (CR.FileID == Expansion.FileID) {
1495 Regions.push_back(x: CR);
1496 if (isExpansion(R: CR, FileID: Expansion.FileID))
1497 ExpansionCoverage.Expansions.emplace_back(args: CR, args: Expansion.Function);
1498 }
1499 for (const auto &CR : Expansion.Function.CountedBranchRegions)
1500 // Capture branch regions that only pertain to the corresponding expansion.
1501 if (CR.FileID == Expansion.FileID)
1502 ExpansionCoverage.BranchRegions.push_back(x: CR);
1503
1504 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
1505 << Expansion.FileID << "\n");
1506 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
1507
1508 return ExpansionCoverage;
1509}
1510
1511LineCoverageStats::LineCoverageStats(
1512 ArrayRef<const CoverageSegment *> LineSegments,
1513 const CoverageSegment *WrappedSegment, unsigned Line)
1514 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
1515 LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
1516 // Find the minimum number of regions which start in this line.
1517 unsigned MinRegionCount = 0;
1518 auto isStartOfRegion = [](const CoverageSegment *S) {
1519 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
1520 };
1521 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
1522 if (isStartOfRegion(LineSegments[I]))
1523 ++MinRegionCount;
1524
1525 bool StartOfSkippedRegion = !LineSegments.empty() &&
1526 !LineSegments.front()->HasCount &&
1527 LineSegments.front()->IsRegionEntry;
1528
1529 HasMultipleRegions = MinRegionCount > 1;
1530 Mapped =
1531 !StartOfSkippedRegion &&
1532 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));
1533
1534 // if there is any starting segment at this line with a counter, it must be
1535 // mapped
1536 Mapped |= std::any_of(
1537 first: LineSegments.begin(), last: LineSegments.end(),
1538 pred: [](const auto *Seq) { return Seq->IsRegionEntry && Seq->HasCount; });
1539
1540 if (!Mapped) {
1541 return;
1542 }
1543
1544 // Pick the max count from the non-gap, region entry segments and the
1545 // wrapped count.
1546 if (WrappedSegment)
1547 ExecutionCount = WrappedSegment->Count;
1548 if (!MinRegionCount)
1549 return;
1550 for (const auto *LS : LineSegments)
1551 if (isStartOfRegion(LS))
1552 ExecutionCount = std::max(a: ExecutionCount, b: LS->Count);
1553}
1554
1555LineCoverageIterator &LineCoverageIterator::operator++() {
1556 if (Next == CD.end()) {
1557 Stats = LineCoverageStats();
1558 Ended = true;
1559 return *this;
1560 }
1561 if (Segments.size())
1562 WrappedSegment = Segments.back();
1563 Segments.clear();
1564 while (Next != CD.end() && Next->Line == Line)
1565 Segments.push_back(Elt: &*Next++);
1566 Stats = LineCoverageStats(Segments, WrappedSegment, Line);
1567 ++Line;
1568 return *this;
1569}
1570
1571static std::string getCoverageMapErrString(coveragemap_error Err,
1572 const std::string &ErrMsg = "") {
1573 std::string Msg;
1574 raw_string_ostream OS(Msg);
1575
1576 switch (Err) {
1577 case coveragemap_error::success:
1578 OS << "success";
1579 break;
1580 case coveragemap_error::eof:
1581 OS << "end of File";
1582 break;
1583 case coveragemap_error::no_data_found:
1584 OS << "no coverage data found";
1585 break;
1586 case coveragemap_error::unsupported_version:
1587 OS << "unsupported coverage format version";
1588 break;
1589 case coveragemap_error::truncated:
1590 OS << "truncated coverage data";
1591 break;
1592 case coveragemap_error::malformed:
1593 OS << "malformed coverage data";
1594 break;
1595 case coveragemap_error::decompression_failed:
1596 OS << "failed to decompress coverage data (zlib)";
1597 break;
1598 case coveragemap_error::invalid_or_missing_arch_specifier:
1599 OS << "`-arch` specifier is invalid or missing for universal binary";
1600 break;
1601 }
1602
1603 // If optional error message is not empty, append it to the message.
1604 if (!ErrMsg.empty())
1605 OS << ": " << ErrMsg;
1606
1607 return Msg;
1608}
1609
1610namespace {
1611
1612// FIXME: This class is only here to support the transition to llvm::Error. It
1613// will be removed once this transition is complete. Clients should prefer to
1614// deal with the Error value directly, rather than converting to error_code.
1615class CoverageMappingErrorCategoryType : public std::error_category {
1616 const char *name() const noexcept override { return "llvm.coveragemap"; }
1617 std::string message(int IE) const override {
1618 return getCoverageMapErrString(Err: static_cast<coveragemap_error>(IE));
1619 }
1620};
1621
1622} // end anonymous namespace
1623
1624std::string CoverageMapError::message() const {
1625 return getCoverageMapErrString(Err, ErrMsg: Msg);
1626}
1627
1628const std::error_category &llvm::coverage::coveragemap_category() {
1629 static CoverageMappingErrorCategoryType ErrorCategory;
1630 return ErrorCategory;
1631}
1632
1633char CoverageMapError::ID = 0;
1634