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