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 | |
45 | using namespace llvm; |
46 | using namespace coverage; |
47 | |
48 | #define DEBUG_TYPE "coverage-mapping" |
49 | |
50 | Counter 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 | |
60 | void CounterExpressionBuilder::(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 | |
77 | Counter 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 | |
129 | Counter 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 | |
134 | Counter 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 | |
140 | void 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 | |
170 | Expected<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 | |
226 | mcdc::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 | |
325 | namespace { |
326 | |
327 | /// Construct this->NextIDs with Branches for TVIdxBuilder to use it |
328 | /// before MCDCRecordProcessor(). |
329 | class NextIDsBuilder { |
330 | protected: |
331 | SmallVector<mcdc::ConditionIDs> NextIDs; |
332 | |
333 | public: |
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 | |
349 | class MCDCRecordProcessor : NextIDsBuilder, mcdc::TVIdxBuilder { |
350 | /// A bitmap representing the executed test vectors for a boolean expression. |
351 | /// Each index of the bitmap corresponds to a possible test vector. An index |
352 | /// with a bit value of '1' indicates that the corresponding Test Vector |
353 | /// identified by that index was executed. |
354 | const BitVector &Bitmap; |
355 | |
356 | /// Decision Region to which the ExecutedTestVectorBitmap applies. |
357 | const CounterMappingRegion &Region; |
358 | const mcdc::DecisionParameters &DecisionParams; |
359 | |
360 | /// Array of branch regions corresponding each conditions in the boolean |
361 | /// expression. |
362 | ArrayRef<const CounterMappingRegion *> Branches; |
363 | |
364 | /// Total number of conditions in the boolean expression. |
365 | unsigned NumConditions; |
366 | |
367 | /// Vector used to track whether a condition is constant folded. |
368 | MCDCRecord::BoolVector Folded; |
369 | |
370 | /// Mapping of calculated MC/DC Independence Pairs for each condition. |
371 | MCDCRecord::TVPairMap IndependencePairs; |
372 | |
373 | /// Storage for ExecVectors |
374 | /// ExecVectors is the alias of its 0th element. |
375 | std::array<MCDCRecord::TestVectors, 2> ExecVectorsByCond; |
376 | |
377 | /// Actual executed Test Vectors for the boolean expression, based on |
378 | /// ExecutedTestVectorBitmap. |
379 | MCDCRecord::TestVectors &ExecVectors; |
380 | |
381 | /// Number of False items in ExecVectors |
382 | unsigned NumExecVectorsF; |
383 | |
384 | #ifndef NDEBUG |
385 | DenseSet<unsigned> TVIdxs; |
386 | #endif |
387 | |
388 | public: |
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 | |
398 | private: |
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 | |
475 | public: |
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 | |
523 | Expected<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 | |
531 | unsigned 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 | |
587 | void 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 | |
595 | ArrayRef<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 | |
604 | static 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 |
614 | static 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 | |
634 | namespace { |
635 | |
636 | /// Collect Decisions, Branchs, and Expansions and associate them. |
637 | class MCDCDecisionRecorder { |
638 | private: |
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 | |
735 | private: |
736 | /// Decisions in progress |
737 | /// DecisionRecord is added for each MCDCDecisionRegion. |
738 | /// DecisionRecord is removed when Decision is completed. |
739 | SmallVector<DecisionRecord> Decisions; |
740 | |
741 | public: |
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 | |
790 | Error 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. |
925 | Error 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 | |
940 | Expected<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. |
950 | static 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 | |
959 | Error 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 | |
997 | Expected<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 | |
1067 | namespace { |
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. |
1073 | class FunctionInstantiationSetCollector { |
1074 | using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; |
1075 | MapT InstantiatedFunctions; |
1076 | |
1077 | public: |
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 | |
1091 | class 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 | |
1300 | public: |
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 | |
1340 | std::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 | |
1350 | static 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. |
1360 | static std::optional<unsigned> |
1361 | findMainViewFileID(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. |
1375 | static std::optional<unsigned> |
1376 | findMainViewFileID(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 | |
1383 | static bool isExpansion(const CountedRegion &R, unsigned FileID) { |
1384 | return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID; |
1385 | } |
1386 | |
1387 | CoverageData 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 | |
1421 | std::vector<InstantiationGroup> |
1422 | CoverageMapping::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 | |
1446 | CoverageData |
1447 | CoverageMapping::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 | |
1477 | CoverageData 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 | |
1500 | LineCoverageStats::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 | |
1544 | LineCoverageIterator &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 | |
1560 | static 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 | |
1599 | namespace { |
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. |
1604 | class 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 | |
1613 | std::string CoverageMapError::message() const { |
1614 | return getCoverageMapErrString(Err, ErrMsg: Msg); |
1615 | } |
1616 | |
1617 | const std::error_category &llvm::coverage::coveragemap_category() { |
1618 | static CoverageMappingErrorCategoryType ErrorCategory; |
1619 | return ErrorCategory; |
1620 | } |
1621 | |
1622 | char CoverageMapError::ID = 0; |
1623 | |