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