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

source code of llvm/lib/ProfileData/Coverage/CoverageMapping.cpp