1 | //===- CoverageMapping.h - Code coverage mapping support --------*- C++ -*-===// |
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 | // Code coverage mapping data is generated by clang and read by |
10 | // llvm-cov to show code coverage statistics for a file. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H |
15 | #define LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H |
16 | |
17 | #include "llvm/ADT/ArrayRef.h" |
18 | #include "llvm/ADT/BitVector.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/ADT/DenseSet.h" |
21 | #include "llvm/ADT/Hashing.h" |
22 | #include "llvm/ADT/StringRef.h" |
23 | #include "llvm/ADT/iterator.h" |
24 | #include "llvm/ADT/iterator_range.h" |
25 | #include "llvm/Object/BuildID.h" |
26 | #include "llvm/ProfileData/Coverage/MCDCTypes.h" |
27 | #include "llvm/ProfileData/InstrProf.h" |
28 | #include "llvm/Support/Alignment.h" |
29 | #include "llvm/Support/Compiler.h" |
30 | #include "llvm/Support/Debug.h" |
31 | #include "llvm/Support/Endian.h" |
32 | #include "llvm/Support/Error.h" |
33 | #include "llvm/Support/raw_ostream.h" |
34 | #include <cassert> |
35 | #include <cstdint> |
36 | #include <iterator> |
37 | #include <memory> |
38 | #include <sstream> |
39 | #include <string> |
40 | #include <system_error> |
41 | #include <utility> |
42 | #include <vector> |
43 | |
44 | namespace llvm { |
45 | |
46 | class IndexedInstrProfReader; |
47 | |
48 | namespace object { |
49 | class BuildIDFetcher; |
50 | } // namespace object |
51 | |
52 | namespace vfs { |
53 | class FileSystem; |
54 | } // namespace vfs |
55 | |
56 | namespace coverage { |
57 | |
58 | class CoverageMappingReader; |
59 | struct CoverageMappingRecord; |
60 | |
61 | enum class coveragemap_error { |
62 | success = 0, |
63 | eof, |
64 | no_data_found, |
65 | unsupported_version, |
66 | truncated, |
67 | malformed, |
68 | decompression_failed, |
69 | invalid_or_missing_arch_specifier |
70 | }; |
71 | |
72 | const std::error_category &coveragemap_category(); |
73 | |
74 | inline std::error_code make_error_code(coveragemap_error E) { |
75 | return std::error_code(static_cast<int>(E), coveragemap_category()); |
76 | } |
77 | |
78 | class CoverageMapError : public ErrorInfo<CoverageMapError> { |
79 | public: |
80 | CoverageMapError(coveragemap_error Err, const Twine &ErrStr = Twine()) |
81 | : Err(Err), Msg(ErrStr.str()) { |
82 | assert(Err != coveragemap_error::success && "Not an error" ); |
83 | } |
84 | |
85 | std::string message() const override; |
86 | |
87 | void log(raw_ostream &OS) const override { OS << message(); } |
88 | |
89 | std::error_code convertToErrorCode() const override { |
90 | return make_error_code(E: Err); |
91 | } |
92 | |
93 | coveragemap_error get() const { return Err; } |
94 | const std::string &getMessage() const { return Msg; } |
95 | |
96 | static char ID; |
97 | |
98 | private: |
99 | coveragemap_error Err; |
100 | std::string Msg; |
101 | }; |
102 | |
103 | /// A Counter is an abstract value that describes how to compute the |
104 | /// execution count for a region of code using the collected profile count data. |
105 | struct Counter { |
106 | /// The CounterExpression kind (Add or Subtract) is encoded in bit 0 next to |
107 | /// the CounterKind. This means CounterKind has to leave bit 0 free. |
108 | enum CounterKind { Zero, CounterValueReference, Expression }; |
109 | static const unsigned EncodingTagBits = 2; |
110 | static const unsigned EncodingTagMask = 0x3; |
111 | static const unsigned EncodingCounterTagAndExpansionRegionTagBits = |
112 | EncodingTagBits + 1; |
113 | |
114 | private: |
115 | CounterKind Kind = Zero; |
116 | unsigned ID = 0; |
117 | |
118 | Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {} |
119 | |
120 | public: |
121 | Counter() = default; |
122 | |
123 | CounterKind getKind() const { return Kind; } |
124 | |
125 | bool isZero() const { return Kind == Zero; } |
126 | |
127 | bool isExpression() const { return Kind == Expression; } |
128 | |
129 | unsigned getCounterID() const { return ID; } |
130 | |
131 | unsigned getExpressionID() const { return ID; } |
132 | |
133 | friend bool operator==(const Counter &LHS, const Counter &RHS) { |
134 | return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID; |
135 | } |
136 | |
137 | friend bool operator!=(const Counter &LHS, const Counter &RHS) { |
138 | return !(LHS == RHS); |
139 | } |
140 | |
141 | friend bool operator<(const Counter &LHS, const Counter &RHS) { |
142 | return std::tie(args: LHS.Kind, args: LHS.ID) < std::tie(args: RHS.Kind, args: RHS.ID); |
143 | } |
144 | |
145 | /// Return the counter that represents the number zero. |
146 | static Counter getZero() { return Counter(); } |
147 | |
148 | /// Return the counter that corresponds to a specific profile counter. |
149 | static Counter getCounter(unsigned CounterId) { |
150 | return Counter(CounterValueReference, CounterId); |
151 | } |
152 | |
153 | /// Return the counter that corresponds to a specific addition counter |
154 | /// expression. |
155 | static Counter getExpression(unsigned ExpressionId) { |
156 | return Counter(Expression, ExpressionId); |
157 | } |
158 | }; |
159 | |
160 | /// A Counter expression is a value that represents an arithmetic operation |
161 | /// with two counters. |
162 | struct CounterExpression { |
163 | enum ExprKind { Subtract, Add }; |
164 | ExprKind Kind; |
165 | Counter LHS, RHS; |
166 | |
167 | CounterExpression(ExprKind Kind, Counter LHS, Counter RHS) |
168 | : Kind(Kind), LHS(LHS), RHS(RHS) {} |
169 | }; |
170 | |
171 | /// A Counter expression builder is used to construct the counter expressions. |
172 | /// It avoids unnecessary duplication and simplifies algebraic expressions. |
173 | class CounterExpressionBuilder { |
174 | /// A list of all the counter expressions |
175 | std::vector<CounterExpression> Expressions; |
176 | |
177 | /// A lookup table for the index of a given expression. |
178 | DenseMap<CounterExpression, unsigned> ExpressionIndices; |
179 | |
180 | /// Return the counter which corresponds to the given expression. |
181 | /// |
182 | /// If the given expression is already stored in the builder, a counter |
183 | /// that references that expression is returned. Otherwise, the given |
184 | /// expression is added to the builder's collection of expressions. |
185 | Counter get(const CounterExpression &E); |
186 | |
187 | /// Represents a term in a counter expression tree. |
188 | struct Term { |
189 | unsigned CounterID; |
190 | int Factor; |
191 | |
192 | Term(unsigned CounterID, int Factor) |
193 | : CounterID(CounterID), Factor(Factor) {} |
194 | }; |
195 | |
196 | /// Gather the terms of the expression tree for processing. |
197 | /// |
198 | /// This collects each addition and subtraction referenced by the counter into |
199 | /// a sequence that can be sorted and combined to build a simplified counter |
200 | /// expression. |
201 | void (Counter C, int Sign, SmallVectorImpl<Term> &Terms); |
202 | |
203 | /// Simplifies the given expression tree |
204 | /// by getting rid of algebraically redundant operations. |
205 | Counter simplify(Counter ExpressionTree); |
206 | |
207 | public: |
208 | ArrayRef<CounterExpression> getExpressions() const { return Expressions; } |
209 | |
210 | /// Return a counter that represents the expression that adds LHS and RHS. |
211 | Counter add(Counter LHS, Counter RHS, bool Simplify = true); |
212 | |
213 | /// Return a counter that represents the expression that subtracts RHS from |
214 | /// LHS. |
215 | Counter subtract(Counter LHS, Counter RHS, bool Simplify = true); |
216 | }; |
217 | |
218 | using LineColPair = std::pair<unsigned, unsigned>; |
219 | |
220 | /// A Counter mapping region associates a source range with a specific counter. |
221 | struct CounterMappingRegion { |
222 | enum RegionKind { |
223 | /// A CodeRegion associates some code with a counter |
224 | CodeRegion, |
225 | |
226 | /// An ExpansionRegion represents a file expansion region that associates |
227 | /// a source range with the expansion of a virtual source file, such as |
228 | /// for a macro instantiation or #include file. |
229 | ExpansionRegion, |
230 | |
231 | /// A SkippedRegion represents a source range with code that was skipped |
232 | /// by a preprocessor or similar means. |
233 | SkippedRegion, |
234 | |
235 | /// A GapRegion is like a CodeRegion, but its count is only set as the |
236 | /// line execution count when its the only region in the line. |
237 | GapRegion, |
238 | |
239 | /// A BranchRegion represents leaf-level boolean expressions and is |
240 | /// associated with two counters, each representing the number of times the |
241 | /// expression evaluates to true or false. |
242 | BranchRegion, |
243 | |
244 | /// A DecisionRegion represents a top-level boolean expression and is |
245 | /// associated with a variable length bitmap index and condition number. |
246 | MCDCDecisionRegion, |
247 | |
248 | /// A Branch Region can be extended to include IDs to facilitate MC/DC. |
249 | MCDCBranchRegion |
250 | }; |
251 | |
252 | /// Primary Counter that is also used for Branch Regions (TrueCount). |
253 | Counter Count; |
254 | |
255 | /// Secondary Counter used for Branch Regions (FalseCount). |
256 | Counter FalseCount; |
257 | |
258 | /// Parameters used for Modified Condition/Decision Coverage |
259 | mcdc::Parameters MCDCParams; |
260 | |
261 | const auto &getDecisionParams() const { |
262 | return mcdc::getParams<const mcdc::DecisionParameters>(MCDCParams); |
263 | } |
264 | |
265 | const auto &getBranchParams() const { |
266 | return mcdc::getParams<const mcdc::BranchParameters>(MCDCParams); |
267 | } |
268 | |
269 | unsigned FileID = 0; |
270 | unsigned ExpandedFileID = 0; |
271 | unsigned LineStart, ColumnStart, LineEnd, ColumnEnd; |
272 | |
273 | RegionKind Kind; |
274 | |
275 | CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID, |
276 | unsigned LineStart, unsigned ColumnStart, |
277 | unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind) |
278 | : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID), |
279 | LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd), |
280 | ColumnEnd(ColumnEnd), Kind(Kind) {} |
281 | |
282 | CounterMappingRegion(Counter Count, Counter FalseCount, unsigned FileID, |
283 | unsigned ExpandedFileID, unsigned LineStart, |
284 | unsigned ColumnStart, unsigned LineEnd, |
285 | unsigned ColumnEnd, RegionKind Kind, |
286 | const mcdc::Parameters &MCDCParams = std::monostate()) |
287 | : Count(Count), FalseCount(FalseCount), MCDCParams(MCDCParams), |
288 | FileID(FileID), ExpandedFileID(ExpandedFileID), LineStart(LineStart), |
289 | ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd), |
290 | Kind(Kind) {} |
291 | |
292 | CounterMappingRegion(const mcdc::DecisionParameters &MCDCParams, |
293 | unsigned FileID, unsigned LineStart, |
294 | unsigned ColumnStart, unsigned LineEnd, |
295 | unsigned ColumnEnd, RegionKind Kind) |
296 | : MCDCParams(MCDCParams), FileID(FileID), LineStart(LineStart), |
297 | ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd), |
298 | Kind(Kind) {} |
299 | |
300 | static CounterMappingRegion |
301 | makeRegion(Counter Count, unsigned FileID, unsigned LineStart, |
302 | unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { |
303 | return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart, |
304 | LineEnd, ColumnEnd, CodeRegion); |
305 | } |
306 | |
307 | static CounterMappingRegion |
308 | makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart, |
309 | unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { |
310 | return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart, |
311 | ColumnStart, LineEnd, ColumnEnd, |
312 | ExpansionRegion); |
313 | } |
314 | |
315 | static CounterMappingRegion |
316 | makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart, |
317 | unsigned LineEnd, unsigned ColumnEnd) { |
318 | return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart, |
319 | LineEnd, ColumnEnd, SkippedRegion); |
320 | } |
321 | |
322 | static CounterMappingRegion |
323 | makeGapRegion(Counter Count, unsigned FileID, unsigned LineStart, |
324 | unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { |
325 | return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart, |
326 | LineEnd, (1U << 31) | ColumnEnd, GapRegion); |
327 | } |
328 | |
329 | static CounterMappingRegion |
330 | makeBranchRegion(Counter Count, Counter FalseCount, unsigned FileID, |
331 | unsigned LineStart, unsigned ColumnStart, unsigned LineEnd, |
332 | unsigned ColumnEnd, |
333 | const mcdc::Parameters &MCDCParams = std::monostate()) { |
334 | return CounterMappingRegion( |
335 | Count, FalseCount, FileID, 0, LineStart, ColumnStart, LineEnd, |
336 | ColumnEnd, |
337 | (std::get_if<mcdc::BranchParameters>(ptr: &MCDCParams) ? MCDCBranchRegion |
338 | : BranchRegion), |
339 | MCDCParams); |
340 | } |
341 | |
342 | static CounterMappingRegion |
343 | makeDecisionRegion(const mcdc::DecisionParameters &MCDCParams, |
344 | unsigned FileID, unsigned LineStart, unsigned ColumnStart, |
345 | unsigned LineEnd, unsigned ColumnEnd) { |
346 | return CounterMappingRegion(MCDCParams, FileID, LineStart, ColumnStart, |
347 | LineEnd, ColumnEnd, MCDCDecisionRegion); |
348 | } |
349 | |
350 | inline LineColPair startLoc() const { |
351 | return LineColPair(LineStart, ColumnStart); |
352 | } |
353 | |
354 | inline LineColPair endLoc() const { return LineColPair(LineEnd, ColumnEnd); } |
355 | }; |
356 | |
357 | /// Associates a source range with an execution count. |
358 | struct CountedRegion : public CounterMappingRegion { |
359 | uint64_t ExecutionCount; |
360 | uint64_t FalseExecutionCount; |
361 | bool Folded; |
362 | bool HasSingleByteCoverage; |
363 | |
364 | CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount, |
365 | bool HasSingleByteCoverage) |
366 | : CounterMappingRegion(R), ExecutionCount(ExecutionCount), |
367 | FalseExecutionCount(0), Folded(false), |
368 | HasSingleByteCoverage(HasSingleByteCoverage) {} |
369 | |
370 | CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount, |
371 | uint64_t FalseExecutionCount, bool HasSingleByteCoverage) |
372 | : CounterMappingRegion(R), ExecutionCount(ExecutionCount), |
373 | FalseExecutionCount(FalseExecutionCount), Folded(false), |
374 | HasSingleByteCoverage(HasSingleByteCoverage) {} |
375 | }; |
376 | |
377 | /// MCDC Record grouping all information together. |
378 | struct MCDCRecord { |
379 | /// CondState represents the evaluation of a condition in an executed test |
380 | /// vector, which can be True or False. A DontCare is used to mask an |
381 | /// unevaluatable condition resulting from short-circuit behavior of logical |
382 | /// operators in languages like C/C++. When comparing the evaluation of a |
383 | /// condition across executed test vectors, comparisons against a DontCare |
384 | /// are effectively ignored. |
385 | enum CondState { MCDC_DontCare = -1, MCDC_False = 0, MCDC_True = 1 }; |
386 | |
387 | /// Emulate SmallVector<CondState> with a pair of BitVector. |
388 | /// |
389 | /// True False DontCare (Impossible) |
390 | /// Values: True False False True |
391 | /// Visited: True True False False |
392 | class TestVector { |
393 | BitVector Values; /// True/False (False when DontCare) |
394 | BitVector Visited; /// ~DontCare |
395 | |
396 | public: |
397 | /// Default values are filled with DontCare. |
398 | TestVector(unsigned N) : Values(N), Visited(N) {} |
399 | |
400 | /// Emulate RHS SmallVector::operator[] |
401 | CondState operator[](int I) const { |
402 | return (Visited[I] ? (Values[I] ? MCDC_True : MCDC_False) |
403 | : MCDC_DontCare); |
404 | } |
405 | |
406 | /// Equivalent to buildTestVector's Index. |
407 | auto getIndex() const { return Values.getData()[0]; } |
408 | |
409 | /// Set the condition \p Val at position \p I. |
410 | /// This emulates LHS SmallVector::operator[]. |
411 | void set(int I, CondState Val) { |
412 | Visited[I] = (Val != MCDC_DontCare); |
413 | Values[I] = (Val == MCDC_True); |
414 | } |
415 | |
416 | /// Emulate SmallVector::push_back. |
417 | void push_back(CondState Val) { |
418 | Visited.push_back(Val: Val != MCDC_DontCare); |
419 | Values.push_back(Val: Val == MCDC_True); |
420 | assert(Values.size() == Visited.size()); |
421 | } |
422 | |
423 | /// For each element: |
424 | /// - False if either is DontCare |
425 | /// - False if both have the same value |
426 | /// - True if both have the opposite value |
427 | /// ((A.Values ^ B.Values) & A.Visited & B.Visited) |
428 | /// Dedicated to findIndependencePairs(). |
429 | auto getDifferences(const TestVector &B) const { |
430 | const auto &A = *this; |
431 | BitVector AB = A.Values; |
432 | AB ^= B.Values; |
433 | AB &= A.Visited; |
434 | AB &= B.Visited; |
435 | return AB; |
436 | } |
437 | }; |
438 | |
439 | using TestVectors = llvm::SmallVector<std::pair<TestVector, CondState>>; |
440 | using BoolVector = llvm::SmallVector<bool>; |
441 | using TVRowPair = std::pair<unsigned, unsigned>; |
442 | using TVPairMap = llvm::DenseMap<unsigned, TVRowPair>; |
443 | using CondIDMap = llvm::DenseMap<unsigned, unsigned>; |
444 | using LineColPairMap = llvm::DenseMap<unsigned, LineColPair>; |
445 | |
446 | private: |
447 | CounterMappingRegion Region; |
448 | TestVectors TV; |
449 | TVPairMap IndependencePairs; |
450 | BoolVector Folded; |
451 | CondIDMap PosToID; |
452 | LineColPairMap CondLoc; |
453 | |
454 | public: |
455 | MCDCRecord(const CounterMappingRegion &Region, TestVectors &&TV, |
456 | TVPairMap &&IndependencePairs, BoolVector &&Folded, |
457 | CondIDMap &&PosToID, LineColPairMap &&CondLoc) |
458 | : Region(Region), TV(std::move(TV)), |
459 | IndependencePairs(std::move(IndependencePairs)), |
460 | Folded(std::move(Folded)), PosToID(std::move(PosToID)), |
461 | CondLoc(std::move(CondLoc)){}; |
462 | |
463 | CounterMappingRegion getDecisionRegion() const { return Region; } |
464 | unsigned getNumConditions() const { |
465 | unsigned NumConditions = Region.getDecisionParams().NumConditions; |
466 | assert(NumConditions != 0 && |
467 | "In MC/DC, NumConditions should never be zero!" ); |
468 | return NumConditions; |
469 | } |
470 | unsigned getNumTestVectors() const { return TV.size(); } |
471 | bool isCondFolded(unsigned Condition) const { return Folded[Condition]; } |
472 | |
473 | /// Return the evaluation of a condition (indicated by Condition) in an |
474 | /// executed test vector (indicated by TestVectorIndex), which will be True, |
475 | /// False, or DontCare if the condition is unevaluatable. Because condition |
476 | /// IDs are not associated based on their position in the expression, |
477 | /// accessing conditions in the TestVectors requires a translation from a |
478 | /// ordinal position to actual condition ID. This is done via PosToID[]. |
479 | CondState getTVCondition(unsigned TestVectorIndex, unsigned Condition) { |
480 | return TV[TestVectorIndex].first[PosToID[Condition]]; |
481 | } |
482 | |
483 | /// Return the Result evaluation for an executed test vector. |
484 | /// See MCDCRecordProcessor::RecordTestVector(). |
485 | CondState getTVResult(unsigned TestVectorIndex) { |
486 | return TV[TestVectorIndex].second; |
487 | } |
488 | |
489 | /// Determine whether a given condition (indicated by Condition) is covered |
490 | /// by an Independence Pair. Because condition IDs are not associated based |
491 | /// on their position in the expression, accessing conditions in the |
492 | /// TestVectors requires a translation from a ordinal position to actual |
493 | /// condition ID. This is done via PosToID[]. |
494 | bool isConditionIndependencePairCovered(unsigned Condition) const { |
495 | auto It = PosToID.find(Val: Condition); |
496 | if (It != PosToID.end()) |
497 | return IndependencePairs.contains(Val: It->second); |
498 | llvm_unreachable("Condition ID without an Ordinal mapping" ); |
499 | } |
500 | |
501 | /// Return the Independence Pair that covers the given condition. Because |
502 | /// condition IDs are not associated based on their position in the |
503 | /// expression, accessing conditions in the TestVectors requires a |
504 | /// translation from a ordinal position to actual condition ID. This is done |
505 | /// via PosToID[]. |
506 | TVRowPair getConditionIndependencePair(unsigned Condition) { |
507 | assert(isConditionIndependencePairCovered(Condition)); |
508 | return IndependencePairs[PosToID[Condition]]; |
509 | } |
510 | |
511 | float getPercentCovered() const { |
512 | unsigned Folded = 0; |
513 | unsigned Covered = 0; |
514 | for (unsigned C = 0; C < getNumConditions(); C++) { |
515 | if (isCondFolded(Condition: C)) |
516 | Folded++; |
517 | else if (isConditionIndependencePairCovered(Condition: C)) |
518 | Covered++; |
519 | } |
520 | |
521 | unsigned Total = getNumConditions() - Folded; |
522 | if (Total == 0) |
523 | return 0.0; |
524 | return (static_cast<double>(Covered) / static_cast<double>(Total)) * 100.0; |
525 | } |
526 | |
527 | std::string (unsigned Condition) { |
528 | std::ostringstream OS; |
529 | OS << "Condition C" << Condition + 1 << " --> (" ; |
530 | OS << CondLoc[Condition].first << ":" << CondLoc[Condition].second; |
531 | OS << ")\n" ; |
532 | return OS.str(); |
533 | } |
534 | |
535 | std::string () const { |
536 | std::ostringstream OS; |
537 | if (getNumTestVectors() == 0) { |
538 | OS << "None.\n" ; |
539 | return OS.str(); |
540 | } |
541 | const auto NumConditions = getNumConditions(); |
542 | for (unsigned I = 0; I < NumConditions; I++) { |
543 | OS << "C" << I + 1; |
544 | if (I != NumConditions - 1) |
545 | OS << ", " ; |
546 | } |
547 | OS << " Result\n" ; |
548 | return OS.str(); |
549 | } |
550 | |
551 | std::string getTestVectorString(unsigned TestVectorIndex) { |
552 | assert(TestVectorIndex < getNumTestVectors() && |
553 | "TestVector index out of bounds!" ); |
554 | std::ostringstream OS; |
555 | const auto NumConditions = getNumConditions(); |
556 | // Add individual condition values to the string. |
557 | OS << " " << TestVectorIndex + 1 << " { " ; |
558 | for (unsigned Condition = 0; Condition < NumConditions; Condition++) { |
559 | if (isCondFolded(Condition)) |
560 | OS << "C" ; |
561 | else { |
562 | switch (getTVCondition(TestVectorIndex, Condition)) { |
563 | case MCDCRecord::MCDC_DontCare: |
564 | OS << "-" ; |
565 | break; |
566 | case MCDCRecord::MCDC_True: |
567 | OS << "T" ; |
568 | break; |
569 | case MCDCRecord::MCDC_False: |
570 | OS << "F" ; |
571 | break; |
572 | } |
573 | } |
574 | if (Condition != NumConditions - 1) |
575 | OS << ", " ; |
576 | } |
577 | |
578 | // Add result value to the string. |
579 | OS << " = " ; |
580 | if (getTVResult(TestVectorIndex) == MCDC_True) |
581 | OS << "T" ; |
582 | else |
583 | OS << "F" ; |
584 | OS << " }\n" ; |
585 | |
586 | return OS.str(); |
587 | } |
588 | |
589 | std::string getConditionCoverageString(unsigned Condition) { |
590 | assert(Condition < getNumConditions() && |
591 | "Condition index is out of bounds!" ); |
592 | std::ostringstream OS; |
593 | |
594 | OS << " C" << Condition + 1 << "-Pair: " ; |
595 | if (isCondFolded(Condition)) { |
596 | OS << "constant folded\n" ; |
597 | } else if (isConditionIndependencePairCovered(Condition)) { |
598 | TVRowPair rows = getConditionIndependencePair(Condition); |
599 | OS << "covered: (" << rows.first << "," ; |
600 | OS << rows.second << ")\n" ; |
601 | } else |
602 | OS << "not covered\n" ; |
603 | |
604 | return OS.str(); |
605 | } |
606 | }; |
607 | |
608 | namespace mcdc { |
609 | /// Compute TestVector Indices "TVIdx" from the Conds graph. |
610 | /// |
611 | /// Clang CodeGen handles the bitmap index based on TVIdx. |
612 | /// llvm-cov reconstructs conditions from TVIdx. |
613 | /// |
614 | /// For each leaf "The final decision", |
615 | /// - TVIdx should be unique. |
616 | /// - TVIdx has the Width. |
617 | /// - The width represents the number of possible paths. |
618 | /// - The minimum width is 1 "deterministic". |
619 | /// - The order of leaves are sorted by Width DESC. It expects |
620 | /// latter TVIdx(s) (with Width=1) could be pruned and altered to |
621 | /// other simple branch conditions. |
622 | /// |
623 | class TVIdxBuilder { |
624 | public: |
625 | struct MCDCNode { |
626 | int InCount = 0; /// Reference count; temporary use |
627 | int Width; /// Number of accumulated paths (>= 1) |
628 | ConditionIDs NextIDs; |
629 | }; |
630 | |
631 | #ifndef NDEBUG |
632 | /// This is no longer needed after the assignment. |
633 | /// It may be used in assert() for reconfirmation. |
634 | SmallVector<MCDCNode> SavedNodes; |
635 | #endif |
636 | |
637 | /// Output: Index for TestVectors bitmap (These are not CondIDs) |
638 | SmallVector<std::array<int, 2>> Indices; |
639 | |
640 | /// Output: The number of test vectors. |
641 | /// Error with HardMaxTVs if the number has exploded. |
642 | int NumTestVectors; |
643 | |
644 | /// Hard limit of test vectors |
645 | static constexpr auto HardMaxTVs = |
646 | std::numeric_limits<decltype(NumTestVectors)>::max(); |
647 | |
648 | public: |
649 | /// Calculate and assign Indices |
650 | /// \param NextIDs The list of {FalseID, TrueID} indexed by ID |
651 | /// The first element [0] should be the root node. |
652 | /// \param Offset Offset of index to final decisions. |
653 | TVIdxBuilder(const SmallVectorImpl<ConditionIDs> &NextIDs, int Offset = 0); |
654 | }; |
655 | } // namespace mcdc |
656 | |
657 | /// A Counter mapping context is used to connect the counters, expressions |
658 | /// and the obtained counter values. |
659 | class CounterMappingContext { |
660 | ArrayRef<CounterExpression> Expressions; |
661 | ArrayRef<uint64_t> CounterValues; |
662 | BitVector Bitmap; |
663 | |
664 | public: |
665 | CounterMappingContext(ArrayRef<CounterExpression> Expressions, |
666 | ArrayRef<uint64_t> CounterValues = std::nullopt) |
667 | : Expressions(Expressions), CounterValues(CounterValues) {} |
668 | |
669 | void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; } |
670 | void setBitmap(BitVector &&Bitmap_) { Bitmap = std::move(Bitmap_); } |
671 | |
672 | void dump(const Counter &C, raw_ostream &OS) const; |
673 | void dump(const Counter &C) const { dump(C, OS&: dbgs()); } |
674 | |
675 | /// Return the number of times that a region of code associated with this |
676 | /// counter was executed. |
677 | Expected<int64_t> evaluate(const Counter &C) const; |
678 | |
679 | /// Return an MCDC record that indicates executed test vectors and condition |
680 | /// pairs. |
681 | Expected<MCDCRecord> |
682 | evaluateMCDCRegion(const CounterMappingRegion &Region, |
683 | ArrayRef<const CounterMappingRegion *> Branches); |
684 | |
685 | unsigned getMaxCounterID(const Counter &C) const; |
686 | }; |
687 | |
688 | /// Code coverage information for a single function. |
689 | struct FunctionRecord { |
690 | /// Raw function name. |
691 | std::string Name; |
692 | /// Mapping from FileID (i.e. vector index) to filename. Used to support |
693 | /// macro expansions within a function in which the macro and function are |
694 | /// defined in separate files. |
695 | /// |
696 | /// TODO: Uniquing filenames across all function records may be a performance |
697 | /// optimization. |
698 | std::vector<std::string> Filenames; |
699 | /// Regions in the function along with their counts. |
700 | std::vector<CountedRegion> CountedRegions; |
701 | /// Branch Regions in the function along with their counts. |
702 | std::vector<CountedRegion> CountedBranchRegions; |
703 | /// MCDC Records record a DecisionRegion and associated BranchRegions. |
704 | std::vector<MCDCRecord> MCDCRecords; |
705 | /// The number of times this function was executed. |
706 | uint64_t ExecutionCount = 0; |
707 | |
708 | FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames) |
709 | : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {} |
710 | |
711 | FunctionRecord(FunctionRecord &&FR) = default; |
712 | FunctionRecord &operator=(FunctionRecord &&) = default; |
713 | |
714 | void pushMCDCRecord(MCDCRecord &&Record) { |
715 | MCDCRecords.push_back(x: std::move(Record)); |
716 | } |
717 | |
718 | void pushRegion(CounterMappingRegion Region, uint64_t Count, |
719 | uint64_t FalseCount, bool HasSingleByteCoverage) { |
720 | if (Region.Kind == CounterMappingRegion::BranchRegion || |
721 | Region.Kind == CounterMappingRegion::MCDCBranchRegion) { |
722 | CountedBranchRegions.emplace_back(args&: Region, args&: Count, args&: FalseCount, |
723 | args&: HasSingleByteCoverage); |
724 | // If both counters are hard-coded to zero, then this region represents a |
725 | // constant-folded branch. |
726 | if (Region.Count.isZero() && Region.FalseCount.isZero()) |
727 | CountedBranchRegions.back().Folded = true; |
728 | return; |
729 | } |
730 | if (CountedRegions.empty()) |
731 | ExecutionCount = Count; |
732 | CountedRegions.emplace_back(args&: Region, args&: Count, args&: FalseCount, |
733 | args&: HasSingleByteCoverage); |
734 | } |
735 | }; |
736 | |
737 | /// Iterator over Functions, optionally filtered to a single file. |
738 | class FunctionRecordIterator |
739 | : public iterator_facade_base<FunctionRecordIterator, |
740 | std::forward_iterator_tag, FunctionRecord> { |
741 | ArrayRef<FunctionRecord> Records; |
742 | ArrayRef<FunctionRecord>::iterator Current; |
743 | StringRef Filename; |
744 | |
745 | /// Skip records whose primary file is not \c Filename. |
746 | void skipOtherFiles(); |
747 | |
748 | public: |
749 | FunctionRecordIterator(ArrayRef<FunctionRecord> Records_, |
750 | StringRef Filename = "" ) |
751 | : Records(Records_), Current(Records.begin()), Filename(Filename) { |
752 | skipOtherFiles(); |
753 | } |
754 | |
755 | FunctionRecordIterator() : Current(Records.begin()) {} |
756 | |
757 | bool operator==(const FunctionRecordIterator &RHS) const { |
758 | return Current == RHS.Current && Filename == RHS.Filename; |
759 | } |
760 | |
761 | const FunctionRecord &operator*() const { return *Current; } |
762 | |
763 | FunctionRecordIterator &operator++() { |
764 | assert(Current != Records.end() && "incremented past end" ); |
765 | ++Current; |
766 | skipOtherFiles(); |
767 | return *this; |
768 | } |
769 | }; |
770 | |
771 | /// Coverage information for a macro expansion or #included file. |
772 | /// |
773 | /// When covered code has pieces that can be expanded for more detail, such as a |
774 | /// preprocessor macro use and its definition, these are represented as |
775 | /// expansions whose coverage can be looked up independently. |
776 | struct ExpansionRecord { |
777 | /// The abstract file this expansion covers. |
778 | unsigned FileID; |
779 | /// The region that expands to this record. |
780 | const CountedRegion &Region; |
781 | /// Coverage for the expansion. |
782 | const FunctionRecord &Function; |
783 | |
784 | ExpansionRecord(const CountedRegion &Region, |
785 | const FunctionRecord &Function) |
786 | : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {} |
787 | }; |
788 | |
789 | /// The execution count information starting at a point in a file. |
790 | /// |
791 | /// A sequence of CoverageSegments gives execution counts for a file in format |
792 | /// that's simple to iterate through for processing. |
793 | struct CoverageSegment { |
794 | /// The line where this segment begins. |
795 | unsigned Line; |
796 | /// The column where this segment begins. |
797 | unsigned Col; |
798 | /// The execution count, or zero if no count was recorded. |
799 | uint64_t Count; |
800 | /// When false, the segment was uninstrumented or skipped. |
801 | bool HasCount; |
802 | /// Whether this enters a new region or returns to a previous count. |
803 | bool IsRegionEntry; |
804 | /// Whether this enters a gap region. |
805 | bool IsGapRegion; |
806 | |
807 | CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry) |
808 | : Line(Line), Col(Col), Count(0), HasCount(false), |
809 | IsRegionEntry(IsRegionEntry), IsGapRegion(false) {} |
810 | |
811 | CoverageSegment(unsigned Line, unsigned Col, uint64_t Count, |
812 | bool IsRegionEntry, bool IsGapRegion = false, |
813 | bool IsBranchRegion = false) |
814 | : Line(Line), Col(Col), Count(Count), HasCount(true), |
815 | IsRegionEntry(IsRegionEntry), IsGapRegion(IsGapRegion) {} |
816 | |
817 | friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) { |
818 | return std::tie(args: L.Line, args: L.Col, args: L.Count, args: L.HasCount, args: L.IsRegionEntry, |
819 | args: L.IsGapRegion) == std::tie(args: R.Line, args: R.Col, args: R.Count, |
820 | args: R.HasCount, args: R.IsRegionEntry, |
821 | args: R.IsGapRegion); |
822 | } |
823 | }; |
824 | |
825 | /// An instantiation group contains a \c FunctionRecord list, such that each |
826 | /// record corresponds to a distinct instantiation of the same function. |
827 | /// |
828 | /// Note that it's possible for a function to have more than one instantiation |
829 | /// (consider C++ template specializations or static inline functions). |
830 | class InstantiationGroup { |
831 | friend class CoverageMapping; |
832 | |
833 | unsigned Line; |
834 | unsigned Col; |
835 | std::vector<const FunctionRecord *> Instantiations; |
836 | |
837 | InstantiationGroup(unsigned Line, unsigned Col, |
838 | std::vector<const FunctionRecord *> Instantiations) |
839 | : Line(Line), Col(Col), Instantiations(std::move(Instantiations)) {} |
840 | |
841 | public: |
842 | InstantiationGroup(const InstantiationGroup &) = delete; |
843 | InstantiationGroup(InstantiationGroup &&) = default; |
844 | |
845 | /// Get the number of instantiations in this group. |
846 | size_t size() const { return Instantiations.size(); } |
847 | |
848 | /// Get the line where the common function was defined. |
849 | unsigned getLine() const { return Line; } |
850 | |
851 | /// Get the column where the common function was defined. |
852 | unsigned getColumn() const { return Col; } |
853 | |
854 | /// Check if the instantiations in this group have a common mangled name. |
855 | bool hasName() const { |
856 | for (unsigned I = 1, E = Instantiations.size(); I < E; ++I) |
857 | if (Instantiations[I]->Name != Instantiations[0]->Name) |
858 | return false; |
859 | return true; |
860 | } |
861 | |
862 | /// Get the common mangled name for instantiations in this group. |
863 | StringRef getName() const { |
864 | assert(hasName() && "Instantiations don't have a shared name" ); |
865 | return Instantiations[0]->Name; |
866 | } |
867 | |
868 | /// Get the total execution count of all instantiations in this group. |
869 | uint64_t getTotalExecutionCount() const { |
870 | uint64_t Count = 0; |
871 | for (const FunctionRecord *F : Instantiations) |
872 | Count += F->ExecutionCount; |
873 | return Count; |
874 | } |
875 | |
876 | /// Get the instantiations in this group. |
877 | ArrayRef<const FunctionRecord *> getInstantiations() const { |
878 | return Instantiations; |
879 | } |
880 | }; |
881 | |
882 | /// Coverage information to be processed or displayed. |
883 | /// |
884 | /// This represents the coverage of an entire file, expansion, or function. It |
885 | /// provides a sequence of CoverageSegments to iterate through, as well as the |
886 | /// list of expansions that can be further processed. |
887 | class CoverageData { |
888 | friend class CoverageMapping; |
889 | |
890 | std::string Filename; |
891 | std::vector<CoverageSegment> Segments; |
892 | std::vector<ExpansionRecord> Expansions; |
893 | std::vector<CountedRegion> BranchRegions; |
894 | std::vector<MCDCRecord> MCDCRecords; |
895 | |
896 | public: |
897 | CoverageData() = default; |
898 | |
899 | CoverageData(StringRef Filename) : Filename(Filename) {} |
900 | |
901 | /// Get the name of the file this data covers. |
902 | StringRef getFilename() const { return Filename; } |
903 | |
904 | /// Get an iterator over the coverage segments for this object. The segments |
905 | /// are guaranteed to be uniqued and sorted by location. |
906 | std::vector<CoverageSegment>::const_iterator begin() const { |
907 | return Segments.begin(); |
908 | } |
909 | |
910 | std::vector<CoverageSegment>::const_iterator end() const { |
911 | return Segments.end(); |
912 | } |
913 | |
914 | bool empty() const { return Segments.empty(); } |
915 | |
916 | /// Expansions that can be further processed. |
917 | ArrayRef<ExpansionRecord> getExpansions() const { return Expansions; } |
918 | |
919 | /// Branches that can be further processed. |
920 | ArrayRef<CountedRegion> getBranches() const { return BranchRegions; } |
921 | |
922 | /// MCDC Records that can be further processed. |
923 | ArrayRef<MCDCRecord> getMCDCRecords() const { return MCDCRecords; } |
924 | }; |
925 | |
926 | /// The mapping of profile information to coverage data. |
927 | /// |
928 | /// This is the main interface to get coverage information, using a profile to |
929 | /// fill out execution counts. |
930 | class CoverageMapping { |
931 | DenseMap<size_t, DenseSet<size_t>> RecordProvenance; |
932 | std::vector<FunctionRecord> Functions; |
933 | DenseMap<size_t, SmallVector<unsigned, 0>> FilenameHash2RecordIndices; |
934 | std::vector<std::pair<std::string, uint64_t>> FuncHashMismatches; |
935 | |
936 | CoverageMapping() = default; |
937 | |
938 | // Load coverage records from readers. |
939 | static Error loadFromReaders( |
940 | ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, |
941 | IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage); |
942 | |
943 | // Load coverage records from file. |
944 | static Error |
945 | loadFromFile(StringRef Filename, StringRef Arch, StringRef CompilationDir, |
946 | IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage, |
947 | bool &DataFound, |
948 | SmallVectorImpl<object::BuildID> *FoundBinaryIDs = nullptr); |
949 | |
950 | /// Add a function record corresponding to \p Record. |
951 | Error loadFunctionRecord(const CoverageMappingRecord &Record, |
952 | IndexedInstrProfReader &ProfileReader); |
953 | |
954 | /// Look up the indices for function records which are at least partially |
955 | /// defined in the specified file. This is guaranteed to return a superset of |
956 | /// such records: extra records not in the file may be included if there is |
957 | /// a hash collision on the filename. Clients must be robust to collisions. |
958 | ArrayRef<unsigned> |
959 | getImpreciseRecordIndicesForFilename(StringRef Filename) const; |
960 | |
961 | public: |
962 | CoverageMapping(const CoverageMapping &) = delete; |
963 | CoverageMapping &operator=(const CoverageMapping &) = delete; |
964 | |
965 | /// Load the coverage mapping using the given readers. |
966 | static Expected<std::unique_ptr<CoverageMapping>> |
967 | load(ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, |
968 | IndexedInstrProfReader &ProfileReader); |
969 | |
970 | /// Load the coverage mapping from the given object files and profile. If |
971 | /// \p Arches is non-empty, it must specify an architecture for each object. |
972 | /// Ignores non-instrumented object files unless all are not instrumented. |
973 | static Expected<std::unique_ptr<CoverageMapping>> |
974 | load(ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename, |
975 | vfs::FileSystem &FS, ArrayRef<StringRef> Arches = std::nullopt, |
976 | StringRef CompilationDir = "" , |
977 | const object::BuildIDFetcher *BIDFetcher = nullptr, |
978 | bool CheckBinaryIDs = false); |
979 | |
980 | /// The number of functions that couldn't have their profiles mapped. |
981 | /// |
982 | /// This is a count of functions whose profile is out of date or otherwise |
983 | /// can't be associated with any coverage information. |
984 | unsigned getMismatchedCount() const { return FuncHashMismatches.size(); } |
985 | |
986 | /// A hash mismatch occurs when a profile record for a symbol does not have |
987 | /// the same hash as a coverage mapping record for the same symbol. This |
988 | /// returns a list of hash mismatches, where each mismatch is a pair of the |
989 | /// symbol name and its coverage mapping hash. |
990 | ArrayRef<std::pair<std::string, uint64_t>> getHashMismatches() const { |
991 | return FuncHashMismatches; |
992 | } |
993 | |
994 | /// Returns a lexicographically sorted, unique list of files that are |
995 | /// covered. |
996 | std::vector<StringRef> getUniqueSourceFiles() const; |
997 | |
998 | /// Get the coverage for a particular file. |
999 | /// |
1000 | /// The given filename must be the name as recorded in the coverage |
1001 | /// information. That is, only names returned from getUniqueSourceFiles will |
1002 | /// yield a result. |
1003 | CoverageData getCoverageForFile(StringRef Filename) const; |
1004 | |
1005 | /// Get the coverage for a particular function. |
1006 | CoverageData getCoverageForFunction(const FunctionRecord &Function) const; |
1007 | |
1008 | /// Get the coverage for an expansion within a coverage set. |
1009 | CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const; |
1010 | |
1011 | /// Gets all of the functions covered by this profile. |
1012 | iterator_range<FunctionRecordIterator> getCoveredFunctions() const { |
1013 | return make_range(x: FunctionRecordIterator(Functions), |
1014 | y: FunctionRecordIterator()); |
1015 | } |
1016 | |
1017 | /// Gets all of the functions in a particular file. |
1018 | iterator_range<FunctionRecordIterator> |
1019 | getCoveredFunctions(StringRef Filename) const { |
1020 | return make_range(x: FunctionRecordIterator(Functions, Filename), |
1021 | y: FunctionRecordIterator()); |
1022 | } |
1023 | |
1024 | /// Get the list of function instantiation groups in a particular file. |
1025 | /// |
1026 | /// Every instantiation group in a program is attributed to exactly one file: |
1027 | /// the file in which the definition for the common function begins. |
1028 | std::vector<InstantiationGroup> |
1029 | getInstantiationGroups(StringRef Filename) const; |
1030 | }; |
1031 | |
1032 | /// Coverage statistics for a single line. |
1033 | class LineCoverageStats { |
1034 | uint64_t ExecutionCount; |
1035 | bool HasMultipleRegions; |
1036 | bool Mapped; |
1037 | unsigned Line; |
1038 | ArrayRef<const CoverageSegment *> LineSegments; |
1039 | const CoverageSegment *WrappedSegment; |
1040 | |
1041 | friend class LineCoverageIterator; |
1042 | LineCoverageStats() = default; |
1043 | |
1044 | public: |
1045 | LineCoverageStats(ArrayRef<const CoverageSegment *> LineSegments, |
1046 | const CoverageSegment *WrappedSegment, unsigned Line); |
1047 | |
1048 | uint64_t getExecutionCount() const { return ExecutionCount; } |
1049 | |
1050 | bool hasMultipleRegions() const { return HasMultipleRegions; } |
1051 | |
1052 | bool isMapped() const { return Mapped; } |
1053 | |
1054 | unsigned getLine() const { return Line; } |
1055 | |
1056 | ArrayRef<const CoverageSegment *> getLineSegments() const { |
1057 | return LineSegments; |
1058 | } |
1059 | |
1060 | const CoverageSegment *getWrappedSegment() const { return WrappedSegment; } |
1061 | }; |
1062 | |
1063 | /// An iterator over the \c LineCoverageStats objects for lines described by |
1064 | /// a \c CoverageData instance. |
1065 | class LineCoverageIterator |
1066 | : public iterator_facade_base<LineCoverageIterator, |
1067 | std::forward_iterator_tag, |
1068 | const LineCoverageStats> { |
1069 | public: |
1070 | LineCoverageIterator(const CoverageData &CD) |
1071 | : LineCoverageIterator(CD, CD.begin()->Line) {} |
1072 | |
1073 | LineCoverageIterator(const CoverageData &CD, unsigned Line) |
1074 | : CD(CD), WrappedSegment(nullptr), Next(CD.begin()), Ended(false), |
1075 | Line(Line) { |
1076 | this->operator++(); |
1077 | } |
1078 | |
1079 | bool operator==(const LineCoverageIterator &R) const { |
1080 | return &CD == &R.CD && Next == R.Next && Ended == R.Ended; |
1081 | } |
1082 | |
1083 | const LineCoverageStats &operator*() const { return Stats; } |
1084 | |
1085 | LineCoverageIterator &operator++(); |
1086 | |
1087 | LineCoverageIterator getEnd() const { |
1088 | auto EndIt = *this; |
1089 | EndIt.Next = CD.end(); |
1090 | EndIt.Ended = true; |
1091 | return EndIt; |
1092 | } |
1093 | |
1094 | private: |
1095 | const CoverageData &CD; |
1096 | const CoverageSegment *WrappedSegment; |
1097 | std::vector<CoverageSegment>::const_iterator Next; |
1098 | bool Ended; |
1099 | unsigned Line; |
1100 | SmallVector<const CoverageSegment *, 4> Segments; |
1101 | LineCoverageStats Stats; |
1102 | }; |
1103 | |
1104 | /// Get a \c LineCoverageIterator range for the lines described by \p CD. |
1105 | static inline iterator_range<LineCoverageIterator> |
1106 | getLineCoverageStats(const coverage::CoverageData &CD) { |
1107 | auto Begin = LineCoverageIterator(CD); |
1108 | auto End = Begin.getEnd(); |
1109 | return make_range(x: Begin, y: End); |
1110 | } |
1111 | |
1112 | // Coverage mappping data (V2) has the following layout: |
1113 | // IPSK_covmap: |
1114 | // [CoverageMapFileHeader] |
1115 | // [ArrayStart] |
1116 | // [CovMapFunctionRecordV2] |
1117 | // [CovMapFunctionRecordV2] |
1118 | // ... |
1119 | // [ArrayEnd] |
1120 | // [Encoded Filenames and Region Mapping Data] |
1121 | // |
1122 | // Coverage mappping data (V3) has the following layout: |
1123 | // IPSK_covmap: |
1124 | // [CoverageMapFileHeader] |
1125 | // [Encoded Filenames] |
1126 | // IPSK_covfun: |
1127 | // [ArrayStart] |
1128 | // odr_name_1: [CovMapFunctionRecordV3] |
1129 | // odr_name_2: [CovMapFunctionRecordV3] |
1130 | // ... |
1131 | // [ArrayEnd] |
1132 | // |
1133 | // Both versions of the coverage mapping format encode the same information, |
1134 | // but the V3 format does so more compactly by taking advantage of linkonce_odr |
1135 | // semantics (it allows exactly 1 function record per name reference). |
1136 | |
1137 | /// This namespace defines accessors shared by different versions of coverage |
1138 | /// mapping records. |
1139 | namespace accessors { |
1140 | |
1141 | /// Return the structural hash associated with the function. |
1142 | template <class FuncRecordTy, llvm::endianness Endian> |
1143 | uint64_t getFuncHash(const FuncRecordTy *Record) { |
1144 | return support::endian::byte_swap<uint64_t, Endian>(Record->FuncHash); |
1145 | } |
1146 | |
1147 | /// Return the coverage map data size for the function. |
1148 | template <class FuncRecordTy, llvm::endianness Endian> |
1149 | uint64_t getDataSize(const FuncRecordTy *Record) { |
1150 | return support::endian::byte_swap<uint32_t, Endian>(Record->DataSize); |
1151 | } |
1152 | |
1153 | /// Return the function lookup key. The value is considered opaque. |
1154 | template <class FuncRecordTy, llvm::endianness Endian> |
1155 | uint64_t getFuncNameRef(const FuncRecordTy *Record) { |
1156 | return support::endian::byte_swap<uint64_t, Endian>(Record->NameRef); |
1157 | } |
1158 | |
1159 | /// Return the PGO name of the function. Used for formats in which the name is |
1160 | /// a hash. |
1161 | template <class FuncRecordTy, llvm::endianness Endian> |
1162 | Error getFuncNameViaRef(const FuncRecordTy *Record, |
1163 | InstrProfSymtab &ProfileNames, StringRef &FuncName) { |
1164 | uint64_t NameRef = getFuncNameRef<FuncRecordTy, Endian>(Record); |
1165 | FuncName = ProfileNames.getFuncOrVarName(MD5Hash: NameRef); |
1166 | return Error::success(); |
1167 | } |
1168 | |
1169 | /// Read coverage mapping out-of-line, from \p MappingBuf. This is used when the |
1170 | /// coverage mapping is attached to the file header, instead of to the function |
1171 | /// record. |
1172 | template <class FuncRecordTy, llvm::endianness Endian> |
1173 | StringRef getCoverageMappingOutOfLine(const FuncRecordTy *Record, |
1174 | const char *MappingBuf) { |
1175 | return {MappingBuf, size_t(getDataSize<FuncRecordTy, Endian>(Record))}; |
1176 | } |
1177 | |
1178 | /// Advance to the next out-of-line coverage mapping and its associated |
1179 | /// function record. |
1180 | template <class FuncRecordTy, llvm::endianness Endian> |
1181 | std::pair<const char *, const FuncRecordTy *> |
1182 | advanceByOneOutOfLine(const FuncRecordTy *Record, const char *MappingBuf) { |
1183 | return {MappingBuf + getDataSize<FuncRecordTy, Endian>(Record), Record + 1}; |
1184 | } |
1185 | |
1186 | } // end namespace accessors |
1187 | |
1188 | LLVM_PACKED_START |
1189 | template <class IntPtrT> |
1190 | struct CovMapFunctionRecordV1 { |
1191 | using ThisT = CovMapFunctionRecordV1<IntPtrT>; |
1192 | |
1193 | #define COVMAP_V1 |
1194 | #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; |
1195 | #include "llvm/ProfileData/InstrProfData.inc" |
1196 | #undef COVMAP_V1 |
1197 | CovMapFunctionRecordV1() = delete; |
1198 | |
1199 | template <llvm::endianness Endian> uint64_t getFuncHash() const { |
1200 | return accessors::getFuncHash<ThisT, Endian>(this); |
1201 | } |
1202 | |
1203 | template <llvm::endianness Endian> uint64_t getDataSize() const { |
1204 | return accessors::getDataSize<ThisT, Endian>(this); |
1205 | } |
1206 | |
1207 | /// Return function lookup key. The value is consider opaque. |
1208 | template <llvm::endianness Endian> IntPtrT getFuncNameRef() const { |
1209 | return support::endian::byte_swap<IntPtrT, Endian>(NamePtr); |
1210 | } |
1211 | |
1212 | /// Return the PGO name of the function. |
1213 | template <llvm::endianness Endian> |
1214 | Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { |
1215 | IntPtrT NameRef = getFuncNameRef<Endian>(); |
1216 | uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize); |
1217 | FuncName = ProfileNames.getFuncName(FuncNameAddress: NameRef, NameSize: NameS); |
1218 | if (NameS && FuncName.empty()) |
1219 | return make_error<CoverageMapError>(Args: coveragemap_error::malformed, |
1220 | Args: "function name is empty" ); |
1221 | return Error::success(); |
1222 | } |
1223 | |
1224 | template <llvm::endianness Endian> |
1225 | std::pair<const char *, const ThisT *> |
1226 | advanceByOne(const char *MappingBuf) const { |
1227 | return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf); |
1228 | } |
1229 | |
1230 | template <llvm::endianness Endian> uint64_t getFilenamesRef() const { |
1231 | llvm_unreachable("V1 function format does not contain a filenames ref" ); |
1232 | } |
1233 | |
1234 | template <llvm::endianness Endian> |
1235 | StringRef getCoverageMapping(const char *MappingBuf) const { |
1236 | return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this, |
1237 | MappingBuf); |
1238 | } |
1239 | }; |
1240 | |
1241 | struct CovMapFunctionRecordV2 { |
1242 | using ThisT = CovMapFunctionRecordV2; |
1243 | |
1244 | #define COVMAP_V2 |
1245 | #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; |
1246 | #include "llvm/ProfileData/InstrProfData.inc" |
1247 | #undef COVMAP_V2 |
1248 | CovMapFunctionRecordV2() = delete; |
1249 | |
1250 | template <llvm::endianness Endian> uint64_t getFuncHash() const { |
1251 | return accessors::getFuncHash<ThisT, Endian>(this); |
1252 | } |
1253 | |
1254 | template <llvm::endianness Endian> uint64_t getDataSize() const { |
1255 | return accessors::getDataSize<ThisT, Endian>(this); |
1256 | } |
1257 | |
1258 | template <llvm::endianness Endian> uint64_t getFuncNameRef() const { |
1259 | return accessors::getFuncNameRef<ThisT, Endian>(this); |
1260 | } |
1261 | |
1262 | template <llvm::endianness Endian> |
1263 | Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { |
1264 | return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames, |
1265 | FuncName); |
1266 | } |
1267 | |
1268 | template <llvm::endianness Endian> |
1269 | std::pair<const char *, const ThisT *> |
1270 | advanceByOne(const char *MappingBuf) const { |
1271 | return accessors::advanceByOneOutOfLine<ThisT, Endian>(this, MappingBuf); |
1272 | } |
1273 | |
1274 | template <llvm::endianness Endian> uint64_t getFilenamesRef() const { |
1275 | llvm_unreachable("V2 function format does not contain a filenames ref" ); |
1276 | } |
1277 | |
1278 | template <llvm::endianness Endian> |
1279 | StringRef getCoverageMapping(const char *MappingBuf) const { |
1280 | return accessors::getCoverageMappingOutOfLine<ThisT, Endian>(this, |
1281 | MappingBuf); |
1282 | } |
1283 | }; |
1284 | |
1285 | struct CovMapFunctionRecordV3 { |
1286 | using ThisT = CovMapFunctionRecordV3; |
1287 | |
1288 | #define COVMAP_V3 |
1289 | #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; |
1290 | #include "llvm/ProfileData/InstrProfData.inc" |
1291 | #undef COVMAP_V3 |
1292 | CovMapFunctionRecordV3() = delete; |
1293 | |
1294 | template <llvm::endianness Endian> uint64_t getFuncHash() const { |
1295 | return accessors::getFuncHash<ThisT, Endian>(this); |
1296 | } |
1297 | |
1298 | template <llvm::endianness Endian> uint64_t getDataSize() const { |
1299 | return accessors::getDataSize<ThisT, Endian>(this); |
1300 | } |
1301 | |
1302 | template <llvm::endianness Endian> uint64_t getFuncNameRef() const { |
1303 | return accessors::getFuncNameRef<ThisT, Endian>(this); |
1304 | } |
1305 | |
1306 | template <llvm::endianness Endian> |
1307 | Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { |
1308 | return accessors::getFuncNameViaRef<ThisT, Endian>(this, ProfileNames, |
1309 | FuncName); |
1310 | } |
1311 | |
1312 | /// Get the filename set reference. |
1313 | template <llvm::endianness Endian> uint64_t getFilenamesRef() const { |
1314 | return support::endian::byte_swap<uint64_t, Endian>(FilenamesRef); |
1315 | } |
1316 | |
1317 | /// Read the inline coverage mapping. Ignore the buffer parameter, it is for |
1318 | /// out-of-line coverage mapping data only. |
1319 | template <llvm::endianness Endian> |
1320 | StringRef getCoverageMapping(const char *) const { |
1321 | return StringRef(&CoverageMapping, getDataSize<Endian>()); |
1322 | } |
1323 | |
1324 | // Advance to the next inline coverage mapping and its associated function |
1325 | // record. Ignore the out-of-line coverage mapping buffer. |
1326 | template <llvm::endianness Endian> |
1327 | std::pair<const char *, const CovMapFunctionRecordV3 *> |
1328 | advanceByOne(const char *) const { |
1329 | assert(isAddrAligned(Align(8), this) && "Function record not aligned" ); |
1330 | const char *Next = ((const char *)this) + sizeof(CovMapFunctionRecordV3) - |
1331 | sizeof(char) + getDataSize<Endian>(); |
1332 | // Each function record has an alignment of 8, so we need to adjust |
1333 | // alignment before reading the next record. |
1334 | Next += offsetToAlignedAddr(Addr: Next, Alignment: Align(8)); |
1335 | return {nullptr, reinterpret_cast<const CovMapFunctionRecordV3 *>(Next)}; |
1336 | } |
1337 | }; |
1338 | |
1339 | // Per module coverage mapping data header, i.e. CoverageMapFileHeader |
1340 | // documented above. |
1341 | struct { |
1342 | #define (Type, LLVMType, Name, Init) Type Name; |
1343 | #include "llvm/ProfileData/InstrProfData.inc" |
1344 | template <llvm::endianness Endian> uint32_t () const { |
1345 | return support::endian::byte_swap<uint32_t, Endian>(NRecords); |
1346 | } |
1347 | |
1348 | template <llvm::endianness Endian> uint32_t () const { |
1349 | return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize); |
1350 | } |
1351 | |
1352 | template <llvm::endianness Endian> uint32_t () const { |
1353 | return support::endian::byte_swap<uint32_t, Endian>(CoverageSize); |
1354 | } |
1355 | |
1356 | template <llvm::endianness Endian> uint32_t () const { |
1357 | return support::endian::byte_swap<uint32_t, Endian>(Version); |
1358 | } |
1359 | }; |
1360 | |
1361 | LLVM_PACKED_END |
1362 | |
1363 | enum CovMapVersion { |
1364 | Version1 = 0, |
1365 | // Function's name reference from CovMapFuncRecord is changed from raw |
1366 | // name string pointer to MD5 to support name section compression. Name |
1367 | // section is also compressed. |
1368 | Version2 = 1, |
1369 | // A new interpretation of the columnEnd field is added in order to mark |
1370 | // regions as gap areas. |
1371 | Version3 = 2, |
1372 | // Function records are named, uniqued, and moved to a dedicated section. |
1373 | Version4 = 3, |
1374 | // Branch regions referring to two counters are added |
1375 | Version5 = 4, |
1376 | // Compilation directory is stored separately and combined with relative |
1377 | // filenames to produce an absolute file path. |
1378 | Version6 = 5, |
1379 | // Branch regions extended and Decision Regions added for MC/DC. |
1380 | Version7 = 6, |
1381 | // The current version is Version7. |
1382 | CurrentVersion = INSTR_PROF_COVMAP_VERSION |
1383 | }; |
1384 | |
1385 | // Correspond to "llvmcovm", in little-endian. |
1386 | constexpr uint64_t TestingFormatMagic = 0x6d766f636d766c6c; |
1387 | |
1388 | enum class TestingFormatVersion : uint64_t { |
1389 | // The first version's number corresponds to the string "testdata" in |
1390 | // little-endian. This is for a historical reason. |
1391 | Version1 = 0x6174616474736574, |
1392 | // Version1 has a defect that it can't store multiple file records. Version2 |
1393 | // fix this problem by adding a new field before the file records section. |
1394 | Version2 = 1, |
1395 | // The current testing format version is Version2. |
1396 | CurrentVersion = Version2 |
1397 | }; |
1398 | |
1399 | template <int CovMapVersion, class IntPtrT> struct CovMapTraits { |
1400 | using CovMapFuncRecordType = CovMapFunctionRecordV3; |
1401 | using NameRefType = uint64_t; |
1402 | }; |
1403 | |
1404 | template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version3, IntPtrT> { |
1405 | using CovMapFuncRecordType = CovMapFunctionRecordV2; |
1406 | using NameRefType = uint64_t; |
1407 | }; |
1408 | |
1409 | template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version2, IntPtrT> { |
1410 | using CovMapFuncRecordType = CovMapFunctionRecordV2; |
1411 | using NameRefType = uint64_t; |
1412 | }; |
1413 | |
1414 | template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> { |
1415 | using CovMapFuncRecordType = CovMapFunctionRecordV1<IntPtrT>; |
1416 | using NameRefType = IntPtrT; |
1417 | }; |
1418 | |
1419 | } // end namespace coverage |
1420 | |
1421 | /// Provide DenseMapInfo for CounterExpression |
1422 | template<> struct DenseMapInfo<coverage::CounterExpression> { |
1423 | static inline coverage::CounterExpression getEmptyKey() { |
1424 | using namespace coverage; |
1425 | |
1426 | return CounterExpression(CounterExpression::ExprKind::Subtract, |
1427 | Counter::getCounter(CounterId: ~0U), |
1428 | Counter::getCounter(CounterId: ~0U)); |
1429 | } |
1430 | |
1431 | static inline coverage::CounterExpression getTombstoneKey() { |
1432 | using namespace coverage; |
1433 | |
1434 | return CounterExpression(CounterExpression::ExprKind::Add, |
1435 | Counter::getCounter(CounterId: ~0U), |
1436 | Counter::getCounter(CounterId: ~0U)); |
1437 | } |
1438 | |
1439 | static unsigned getHashValue(const coverage::CounterExpression &V) { |
1440 | return static_cast<unsigned>( |
1441 | hash_combine(args: V.Kind, args: V.LHS.getKind(), args: V.LHS.getCounterID(), |
1442 | args: V.RHS.getKind(), args: V.RHS.getCounterID())); |
1443 | } |
1444 | |
1445 | static bool isEqual(const coverage::CounterExpression &LHS, |
1446 | const coverage::CounterExpression &RHS) { |
1447 | return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS; |
1448 | } |
1449 | }; |
1450 | |
1451 | } // end namespace llvm |
1452 | |
1453 | #endif // LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H |
1454 | |