/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
Line | Count | Source (jump to first uncovered line) |
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/None.h" |
18 | | #include "llvm/ADT/Optional.h" |
19 | | #include "llvm/ADT/SmallBitVector.h" |
20 | | #include "llvm/ADT/SmallVector.h" |
21 | | #include "llvm/ADT/StringRef.h" |
22 | | #include "llvm/ProfileData/Coverage/CoverageMappingReader.h" |
23 | | #include "llvm/ProfileData/InstrProfReader.h" |
24 | | #include "llvm/Support/Debug.h" |
25 | | #include "llvm/Support/Errc.h" |
26 | | #include "llvm/Support/Error.h" |
27 | | #include "llvm/Support/ErrorHandling.h" |
28 | | #include "llvm/Support/ManagedStatic.h" |
29 | | #include "llvm/Support/MemoryBuffer.h" |
30 | | #include "llvm/Support/raw_ostream.h" |
31 | | #include <algorithm> |
32 | | #include <cassert> |
33 | | #include <cstdint> |
34 | | #include <iterator> |
35 | | #include <map> |
36 | | #include <memory> |
37 | | #include <string> |
38 | | #include <system_error> |
39 | | #include <utility> |
40 | | #include <vector> |
41 | | |
42 | | using namespace llvm; |
43 | | using namespace coverage; |
44 | | |
45 | | #define DEBUG_TYPE "coverage-mapping" |
46 | | |
47 | 1.17k | Counter CounterExpressionBuilder::get(const CounterExpression &E) { |
48 | 1.17k | auto It = ExpressionIndices.find(E); |
49 | 1.17k | if (It != ExpressionIndices.end()) |
50 | 559 | return Counter::getExpression(It->second); |
51 | 614 | unsigned I = Expressions.size(); |
52 | 614 | Expressions.push_back(E); |
53 | 614 | ExpressionIndices[E] = I; |
54 | 614 | return Counter::getExpression(I); |
55 | 614 | } |
56 | | |
57 | | void CounterExpressionBuilder::extractTerms(Counter C, int Factor, |
58 | 2.83k | SmallVectorImpl<Term> &Terms) { |
59 | 2.83k | switch (C.getKind()) { |
60 | 2.83k | case Counter::Zero: |
61 | 342 | break; |
62 | 2.83k | case Counter::CounterValueReference: |
63 | 1.40k | Terms.emplace_back(C.getCounterID(), Factor); |
64 | 1.40k | break; |
65 | 2.83k | case Counter::Expression: |
66 | 1.09k | const auto &E = Expressions[C.getExpressionID()]; |
67 | 1.09k | extractTerms(E.LHS, Factor, Terms); |
68 | 1.09k | extractTerms( |
69 | 1.09k | E.RHS, E.Kind == CounterExpression::Subtract ? -Factor440 : Factor653 , Terms); |
70 | 1.09k | break; |
71 | 2.83k | } |
72 | 2.83k | } |
73 | | |
74 | 653 | Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) { |
75 | 653 | // Gather constant terms. |
76 | 653 | SmallVector<Term, 32> Terms; |
77 | 653 | extractTerms(ExpressionTree, +1, Terms); |
78 | 653 | |
79 | 653 | // If there are no terms, this is just a zero. The algorithm below assumes at |
80 | 653 | // least one term. |
81 | 653 | if (Terms.size() == 0) |
82 | 36 | return Counter::getZero(); |
83 | 617 | |
84 | 617 | // Group the terms by counter ID. |
85 | 906 | llvm::sort(Terms, [](const Term &LHS, const Term &RHS) 617 { |
86 | 906 | return LHS.CounterID < RHS.CounterID; |
87 | 906 | }); |
88 | 617 | |
89 | 617 | // Combine terms by counter ID to eliminate counters that sum to zero. |
90 | 617 | auto Prev = Terms.begin(); |
91 | 1.40k | for (auto I = Prev + 1, E = Terms.end(); I != E; ++I787 ) { |
92 | 787 | if (I->CounterID == Prev->CounterID) { |
93 | 140 | Prev->Factor += I->Factor; |
94 | 140 | continue; |
95 | 140 | } |
96 | 647 | ++Prev; |
97 | 647 | *Prev = *I; |
98 | 647 | } |
99 | 617 | Terms.erase(++Prev, Terms.end()); |
100 | 617 | |
101 | 617 | Counter C; |
102 | 617 | // Create additions. We do this before subtractions to avoid constructs like |
103 | 617 | // ((0 - X) + Y), as opposed to (Y - X). |
104 | 1.26k | for (auto T : Terms) { |
105 | 1.26k | if (T.Factor <= 0) |
106 | 438 | continue; |
107 | 1.65k | for (int I = 0; 826 I < T.Factor; ++I830 ) |
108 | 830 | if (C.isZero()) |
109 | 616 | C = Counter::getCounter(T.CounterID); |
110 | 214 | else |
111 | 214 | C = get(CounterExpression(CounterExpression::Add, C, |
112 | 214 | Counter::getCounter(T.CounterID))); |
113 | 826 | } |
114 | 617 | |
115 | 617 | // Create subtractions. |
116 | 1.26k | for (auto T : Terms) { |
117 | 1.26k | if (T.Factor >= 0) |
118 | 958 | continue; |
119 | 612 | for (int I = 0; 306 I < -T.Factor; ++I306 ) |
120 | 306 | C = get(CounterExpression(CounterExpression::Subtract, C, |
121 | 306 | Counter::getCounter(T.CounterID))); |
122 | 306 | } |
123 | 617 | return C; |
124 | 617 | } |
125 | | |
126 | 459 | Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) { |
127 | 459 | return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS))); |
128 | 459 | } |
129 | | |
130 | 194 | Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) { |
131 | 194 | return simplify( |
132 | 194 | get(CounterExpression(CounterExpression::Subtract, LHS, RHS))); |
133 | 194 | } |
134 | | |
135 | 1.82k | void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const { |
136 | 1.82k | switch (C.getKind()) { |
137 | 1.82k | case Counter::Zero: |
138 | 56 | OS << '0'; |
139 | 56 | return; |
140 | 1.82k | case Counter::CounterValueReference: |
141 | 1.44k | OS << '#' << C.getCounterID(); |
142 | 1.44k | break; |
143 | 1.82k | case Counter::Expression: { |
144 | 318 | if (C.getExpressionID() >= Expressions.size()) |
145 | 0 | return; |
146 | 318 | const auto &E = Expressions[C.getExpressionID()]; |
147 | 318 | OS << '('; |
148 | 318 | dump(E.LHS, OS); |
149 | 318 | OS << (E.Kind == CounterExpression::Subtract ? " - "216 : " + "102 ); |
150 | 318 | dump(E.RHS, OS); |
151 | 318 | OS << ')'; |
152 | 318 | break; |
153 | 318 | } |
154 | 1.76k | } |
155 | 1.76k | if (CounterValues.empty()) |
156 | 1.76k | return; |
157 | 0 | Expected<int64_t> Value = evaluate(C); |
158 | 0 | if (auto E = Value.takeError()) { |
159 | 0 | consumeError(std::move(E)); |
160 | 0 | return; |
161 | 0 | } |
162 | 0 | OS << '[' << *Value << ']'; |
163 | 0 | } |
164 | | |
165 | 3.20k | Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { |
166 | 3.20k | switch (C.getKind()) { |
167 | 3.20k | case Counter::Zero: |
168 | 92 | return 0; |
169 | 3.20k | case Counter::CounterValueReference: |
170 | 2.58k | if (C.getCounterID() >= CounterValues.size()) |
171 | 0 | return errorCodeToError(errc::argument_out_of_domain); |
172 | 2.58k | return CounterValues[C.getCounterID()]; |
173 | 2.58k | case Counter::Expression: { |
174 | 524 | if (C.getExpressionID() >= Expressions.size()) |
175 | 0 | return errorCodeToError(errc::argument_out_of_domain); |
176 | 524 | const auto &E = Expressions[C.getExpressionID()]; |
177 | 524 | Expected<int64_t> LHS = evaluate(E.LHS); |
178 | 524 | if (!LHS) |
179 | 0 | return LHS; |
180 | 524 | Expected<int64_t> RHS = evaluate(E.RHS); |
181 | 524 | if (!RHS) |
182 | 0 | return RHS; |
183 | 524 | return E.Kind == CounterExpression::Subtract ? *LHS - *RHS385 : *LHS + *RHS139 ; |
184 | 524 | } |
185 | 0 | } |
186 | 0 | llvm_unreachable("Unhandled CounterKind"); |
187 | 0 | } |
188 | | |
189 | 1.24k | void FunctionRecordIterator::skipOtherFiles() { |
190 | 1.30k | while (Current != Records.end() && !Filename.empty()1.01k && |
191 | 1.30k | Filename != Current->Filenames[0]140 ) |
192 | 58 | ++Current; |
193 | 1.24k | if (Current == Records.end()) |
194 | 293 | *this = FunctionRecordIterator(); |
195 | 1.24k | } |
196 | | |
197 | | Error CoverageMapping::loadFunctionRecord( |
198 | | const CoverageMappingRecord &Record, |
199 | 525 | IndexedInstrProfReader &ProfileReader) { |
200 | 525 | StringRef OrigFuncName = Record.FunctionName; |
201 | 525 | if (OrigFuncName.empty()) |
202 | 4 | return make_error<CoverageMapError>(coveragemap_error::malformed); |
203 | 521 | |
204 | 521 | if (Record.Filenames.empty()) |
205 | 4 | OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName); |
206 | 517 | else |
207 | 517 | OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]); |
208 | 521 | |
209 | 521 | CounterMappingContext Ctx(Record.Expressions); |
210 | 521 | |
211 | 521 | std::vector<uint64_t> Counts; |
212 | 521 | if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName, |
213 | 45 | Record.FunctionHash, Counts)) { |
214 | 45 | instrprof_error IPE = InstrProfError::take(std::move(E)); |
215 | 45 | if (IPE == instrprof_error::hash_mismatch) { |
216 | 1 | FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash); |
217 | 1 | return Error::success(); |
218 | 44 | } else if (IPE != instrprof_error::unknown_function) |
219 | 0 | return make_error<InstrProfError>(IPE); |
220 | 44 | Counts.assign(Record.MappingRegions.size(), 0); |
221 | 44 | } |
222 | 521 | Ctx.setCounts(Counts); |
223 | 520 | |
224 | 520 | assert(!Record.MappingRegions.empty() && "Function has no regions"); |
225 | 520 | |
226 | 520 | // This coverage record is a zero region for a function that's unused in |
227 | 520 | // some TU, but used in a different TU. Ignore it. The coverage maps from the |
228 | 520 | // the other TU will either be loaded (providing full region counts) or they |
229 | 520 | // won't (in which case we don't unintuitively report functions as uncovered |
230 | 520 | // when they have non-zero counts in the profile). |
231 | 520 | if (Record.MappingRegions.size() == 1 && |
232 | 520 | Record.MappingRegions[0].Count.isZero()220 && Counts[0] > 017 ) |
233 | 0 | return Error::success(); |
234 | 520 | |
235 | 520 | FunctionRecord Function(OrigFuncName, Record.Filenames); |
236 | 2.15k | for (const auto &Region : Record.MappingRegions) { |
237 | 2.15k | Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count); |
238 | 2.15k | if (auto E = ExecutionCount.takeError()) { |
239 | 0 | consumeError(std::move(E)); |
240 | 0 | return Error::success(); |
241 | 0 | } |
242 | 2.15k | Function.pushRegion(Region, *ExecutionCount); |
243 | 2.15k | } |
244 | 520 | |
245 | 520 | // Don't create records for (filenames, function) pairs we've already seen. |
246 | 520 | auto FilenamesHash = hash_combine_range(Record.Filenames.begin(), |
247 | 520 | Record.Filenames.end()); |
248 | 520 | if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second) |
249 | 8 | return Error::success(); |
250 | 512 | |
251 | 512 | Functions.push_back(std::move(Function)); |
252 | 512 | return Error::success(); |
253 | 512 | } |
254 | | |
255 | | Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load( |
256 | | ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, |
257 | 215 | IndexedInstrProfReader &ProfileReader) { |
258 | 215 | auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping()); |
259 | 215 | |
260 | 235 | for (const auto &CoverageReader : CoverageReaders) { |
261 | 526 | for (auto RecordOrErr : *CoverageReader) { |
262 | 526 | if (Error E = RecordOrErr.takeError()) |
263 | 1 | return std::move(E); |
264 | 525 | const auto &Record = *RecordOrErr; |
265 | 525 | if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader)) |
266 | 4 | return std::move(E); |
267 | 525 | } |
268 | 235 | } |
269 | 215 | |
270 | 215 | return std::move(Coverage)210 ; |
271 | 215 | } |
272 | | |
273 | | Expected<std::unique_ptr<CoverageMapping>> |
274 | | CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames, |
275 | 116 | StringRef ProfileFilename, ArrayRef<StringRef> Arches) { |
276 | 116 | auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename); |
277 | 116 | if (Error E = ProfileReaderOrErr.takeError()) |
278 | 0 | return std::move(E); |
279 | 116 | auto ProfileReader = std::move(ProfileReaderOrErr.get()); |
280 | 116 | |
281 | 116 | SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers; |
282 | 116 | SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers; |
283 | 119 | for (const auto &File : llvm::enumerate(ObjectFilenames)) { |
284 | 119 | auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value()); |
285 | 119 | if (std::error_code EC = CovMappingBufOrErr.getError()) |
286 | 0 | return errorCodeToError(EC); |
287 | 119 | StringRef Arch = Arches.empty() ? StringRef()111 : Arches[File.index()]8 ; |
288 | 119 | MemoryBufferRef CovMappingBufRef = |
289 | 119 | CovMappingBufOrErr.get()->getMemBufferRef(); |
290 | 119 | auto CoverageReadersOrErr = |
291 | 119 | BinaryCoverageReader::create(CovMappingBufRef, Arch, Buffers); |
292 | 119 | if (Error E = CoverageReadersOrErr.takeError()) |
293 | 1 | return std::move(E); |
294 | 118 | for (auto &Reader : CoverageReadersOrErr.get()) |
295 | 123 | Readers.push_back(std::move(Reader)); |
296 | 118 | Buffers.push_back(std::move(CovMappingBufOrErr.get())); |
297 | 118 | } |
298 | 116 | return load(Readers, *ProfileReader)115 ; |
299 | 116 | } |
300 | | |
301 | | namespace { |
302 | | |
303 | | /// Distributes functions into instantiation sets. |
304 | | /// |
305 | | /// An instantiation set is a collection of functions that have the same source |
306 | | /// code, ie, template functions specializations. |
307 | | class FunctionInstantiationSetCollector { |
308 | | using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>; |
309 | | MapT InstantiatedFunctions; |
310 | | |
311 | | public: |
312 | 380 | void insert(const FunctionRecord &Function, unsigned FileID) { |
313 | 380 | auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end(); |
314 | 380 | while (I != E && I->FileID != FileID) |
315 | 0 | ++I; |
316 | 380 | assert(I != E && "function does not cover the given file"); |
317 | 380 | auto &Functions = InstantiatedFunctions[I->startLoc()]; |
318 | 380 | Functions.push_back(&Function); |
319 | 380 | } |
320 | | |
321 | 255 | MapT::iterator begin() { return InstantiatedFunctions.begin(); } |
322 | 255 | MapT::iterator end() { return InstantiatedFunctions.end(); } |
323 | | }; |
324 | | |
325 | | class SegmentBuilder { |
326 | | std::vector<CoverageSegment> &Segments; |
327 | | SmallVector<const CountedRegion *, 8> ActiveRegions; |
328 | | |
329 | 524 | SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {} |
330 | | |
331 | | /// Emit a segment with the count from \p Region starting at \p StartLoc. |
332 | | // |
333 | | /// \p IsRegionEntry: The segment is at the start of a new non-gap region. |
334 | | /// \p EmitSkippedRegion: The segment must be emitted as a skipped region. |
335 | | void startSegment(const CountedRegion &Region, LineColPair StartLoc, |
336 | 4.13k | bool IsRegionEntry, bool EmitSkippedRegion = false) { |
337 | 4.13k | bool HasCount = !EmitSkippedRegion && |
338 | 4.13k | (Region.Kind != CounterMappingRegion::SkippedRegion)3.55k ; |
339 | 4.13k | |
340 | 4.13k | // If the new segment wouldn't affect coverage rendering, skip it. |
341 | 4.13k | if (!Segments.empty() && !IsRegionEntry3.61k && !EmitSkippedRegion2.15k ) { |
342 | 1.59k | const auto &Last = Segments.back(); |
343 | 1.59k | if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount1.59k && |
344 | 1.59k | !Last.IsRegionEntry544 ) |
345 | 101 | return; |
346 | 4.03k | } |
347 | 4.03k | |
348 | 4.03k | if (HasCount) |
349 | 3.45k | Segments.emplace_back(StartLoc.first, StartLoc.second, |
350 | 3.45k | Region.ExecutionCount, IsRegionEntry, |
351 | 3.45k | Region.Kind == CounterMappingRegion::GapRegion); |
352 | 580 | else |
353 | 580 | Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry); |
354 | 4.03k | |
355 | 4.03k | LLVM_DEBUG({ |
356 | 4.03k | const auto &Last = Segments.back(); |
357 | 4.03k | dbgs() << "Segment at " << Last.Line << ":" << Last.Col |
358 | 4.03k | << " (count = " << Last.Count << ")" |
359 | 4.03k | << (Last.IsRegionEntry ? ", RegionEntry" : "") |
360 | 4.03k | << (!Last.HasCount ? ", Skipped" : "") |
361 | 4.03k | << (Last.IsGapRegion ? ", Gap" : "") << "\n"; |
362 | 4.03k | }); |
363 | 4.03k | } |
364 | | |
365 | | /// Emit segments for active regions which end before \p Loc. |
366 | | /// |
367 | | /// \p Loc: The start location of the next region. If None, all active |
368 | | /// regions are completed. |
369 | | /// \p FirstCompletedRegion: Index of the first completed region. |
370 | | void completeRegionsUntil(Optional<LineColPair> Loc, |
371 | 2.12k | unsigned FirstCompletedRegion) { |
372 | 2.12k | // Sort the completed regions by end location. This makes it simple to |
373 | 2.12k | // emit closing segments in sorted order. |
374 | 2.12k | auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion; |
375 | 2.12k | std::stable_sort(CompletedRegionsIt, ActiveRegions.end(), |
376 | 2.12k | [](const CountedRegion *L, const CountedRegion *R) { |
377 | 551 | return L->endLoc() < R->endLoc(); |
378 | 551 | }); |
379 | 2.12k | |
380 | 2.12k | // Emit segments for all completed regions. |
381 | 2.57k | for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E; |
382 | 2.12k | ++I447 ) { |
383 | 451 | const auto *CompletedRegion = ActiveRegions[I]; |
384 | 451 | assert((!Loc || CompletedRegion->endLoc() <= *Loc) && |
385 | 451 | "Completed region ends after start of new region"); |
386 | 451 | |
387 | 451 | const auto *PrevCompletedRegion = ActiveRegions[I - 1]; |
388 | 451 | auto CompletedSegmentLoc = PrevCompletedRegion->endLoc(); |
389 | 451 | |
390 | 451 | // Don't emit any more segments if they start where the new region begins. |
391 | 451 | if (Loc && CompletedSegmentLoc == *Loc86 ) |
392 | 4 | break; |
393 | 447 | |
394 | 447 | // Don't emit a segment if the next completed region ends at the same |
395 | 447 | // location as this one. |
396 | 447 | if (CompletedSegmentLoc == CompletedRegion->endLoc()) |
397 | 197 | continue; |
398 | 250 | |
399 | 250 | // Use the count from the last completed region which ends at this loc. |
400 | 331 | for (unsigned J = I + 1; 250 J < E; ++J81 ) |
401 | 81 | if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc()) |
402 | 57 | CompletedRegion = ActiveRegions[J]; |
403 | 250 | |
404 | 250 | startSegment(*CompletedRegion, CompletedSegmentLoc, false); |
405 | 250 | } |
406 | 2.12k | |
407 | 2.12k | auto Last = ActiveRegions.back(); |
408 | 2.12k | if (FirstCompletedRegion && Last->endLoc() != *Loc1.55k ) { |
409 | 747 | // If there's a gap after the end of the last completed region and the |
410 | 747 | // start of the new region, use the last active region to fill the gap. |
411 | 747 | startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(), |
412 | 747 | false); |
413 | 1.37k | } else if (!FirstCompletedRegion && (566 !Loc566 || *Loc != Last->endLoc()58 )) { |
414 | 561 | // Emit a skipped segment if there are no more active regions. This |
415 | 561 | // ensures that gaps between functions are marked correctly. |
416 | 561 | startSegment(*Last, Last->endLoc(), false, true); |
417 | 561 | } |
418 | 2.12k | |
419 | 2.12k | // Pop the completed regions. |
420 | 2.12k | ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end()); |
421 | 2.12k | } |
422 | | |
423 | 522 | void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) { |
424 | 2.59k | for (const auto &CR : enumerate(Regions)) { |
425 | 2.59k | auto CurStartLoc = CR.value().startLoc(); |
426 | 2.59k | |
427 | 2.59k | // Active regions which end before the current region need to be popped. |
428 | 2.59k | auto CompletedRegions = |
429 | 2.59k | std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(), |
430 | 4.07k | [&](const CountedRegion *Region) { |
431 | 4.07k | return !(Region->endLoc() <= CurStartLoc); |
432 | 4.07k | }); |
433 | 2.59k | if (CompletedRegions != ActiveRegions.end()) { |
434 | 1.61k | unsigned FirstCompletedRegion = |
435 | 1.61k | std::distance(ActiveRegions.begin(), CompletedRegions); |
436 | 1.61k | completeRegionsUntil(CurStartLoc, FirstCompletedRegion); |
437 | 1.61k | } |
438 | 2.59k | |
439 | 2.59k | bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion; |
440 | 2.59k | |
441 | 2.59k | // Try to emit a segment for the current region. |
442 | 2.59k | if (CurStartLoc == CR.value().endLoc()) { |
443 | 20 | // Avoid making zero-length regions active. If it's the last region, |
444 | 20 | // emit a skipped segment. Otherwise use its predecessor's count. |
445 | 20 | const bool Skipped = (CR.index() + 1) == Regions.size(); |
446 | 20 | startSegment(ActiveRegions.empty() ? CR.value()16 : *ActiveRegions.back()4 , |
447 | 20 | CurStartLoc, !GapRegion, Skipped); |
448 | 20 | continue; |
449 | 20 | } |
450 | 2.57k | if (CR.index() + 1 == Regions.size() || |
451 | 2.57k | CurStartLoc != Regions[CR.index() + 1].startLoc()2.07k ) { |
452 | 2.55k | // Emit a segment if the next region doesn't start at the same location |
453 | 2.55k | // as this one. |
454 | 2.55k | startSegment(CR.value(), CurStartLoc, !GapRegion); |
455 | 2.55k | } |
456 | 2.57k | |
457 | 2.57k | // This region is active (i.e not completed). |
458 | 2.57k | ActiveRegions.push_back(&CR.value()); |
459 | 2.57k | } |
460 | 522 | |
461 | 522 | // Complete any remaining active regions. |
462 | 522 | if (!ActiveRegions.empty()) |
463 | 509 | completeRegionsUntil(None, 0); |
464 | 522 | } |
465 | | |
466 | | /// Sort a nested sequence of regions from a single file. |
467 | 524 | static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) { |
468 | 4.07k | llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) { |
469 | 4.07k | if (LHS.startLoc() != RHS.startLoc()) |
470 | 3.70k | return LHS.startLoc() < RHS.startLoc(); |
471 | 363 | if (LHS.endLoc() != RHS.endLoc()) |
472 | 20 | // When LHS completely contains RHS, we sort LHS first. |
473 | 20 | return RHS.endLoc() < LHS.endLoc(); |
474 | 343 | // If LHS and RHS cover the same area, we need to sort them according |
475 | 343 | // to their kinds so that the most suitable region will become "active" |
476 | 343 | // in combineRegions(). Because we accumulate counter values only from |
477 | 343 | // regions of the same kind as the first region of the area, prefer |
478 | 343 | // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion. |
479 | 343 | static_assert(CounterMappingRegion::CodeRegion < |
480 | 343 | CounterMappingRegion::ExpansionRegion && |
481 | 343 | CounterMappingRegion::ExpansionRegion < |
482 | 343 | CounterMappingRegion::SkippedRegion, |
483 | 343 | "Unexpected order of region kind values"); |
484 | 343 | return LHS.Kind < RHS.Kind; |
485 | 343 | }); |
486 | 524 | } |
487 | | |
488 | | /// Combine counts of regions which cover the same area. |
489 | | static ArrayRef<CountedRegion> |
490 | 523 | combineRegions(MutableArrayRef<CountedRegion> Regions) { |
491 | 523 | if (Regions.empty()) |
492 | 0 | return Regions; |
493 | 523 | auto Active = Regions.begin(); |
494 | 523 | auto End = Regions.end(); |
495 | 2.93k | for (auto I = Regions.begin() + 1; I != End; ++I2.41k ) { |
496 | 2.41k | if (Active->startLoc() != I->startLoc() || |
497 | 2.41k | Active->endLoc() != I->endLoc()364 ) { |
498 | 2.07k | // Shift to the next region. |
499 | 2.07k | ++Active; |
500 | 2.07k | if (Active != I) |
501 | 228 | *Active = *I; |
502 | 2.07k | continue; |
503 | 2.07k | } |
504 | 345 | // Merge duplicate region. |
505 | 345 | // If CodeRegions and ExpansionRegions cover the same area, it's probably |
506 | 345 | // a macro which is fully expanded to another macro. In that case, we need |
507 | 345 | // to accumulate counts only from CodeRegions, or else the area will be |
508 | 345 | // counted twice. |
509 | 345 | // On the other hand, a macro may have a nested macro in its body. If the |
510 | 345 | // outer macro is used several times, the ExpansionRegion for the nested |
511 | 345 | // macro will also be added several times. These ExpansionRegions cover |
512 | 345 | // the same source locations and have to be combined to reach the correct |
513 | 345 | // value for that area. |
514 | 345 | // We add counts of the regions of the same kind as the active region |
515 | 345 | // to handle the both situations. |
516 | 345 | if (I->Kind == Active->Kind) |
517 | 340 | Active->ExecutionCount += I->ExecutionCount; |
518 | 345 | } |
519 | 523 | return Regions.drop_back(std::distance(++Active, End)); |
520 | 523 | } |
521 | | |
522 | | public: |
523 | | /// Build a sorted list of CoverageSegments from a list of Regions. |
524 | | static std::vector<CoverageSegment> |
525 | 523 | buildSegments(MutableArrayRef<CountedRegion> Regions) { |
526 | 523 | std::vector<CoverageSegment> Segments; |
527 | 523 | SegmentBuilder Builder(Segments); |
528 | 523 | |
529 | 523 | sortNestedRegions(Regions); |
530 | 523 | ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); |
531 | 523 | |
532 | 523 | LLVM_DEBUG({ |
533 | 523 | dbgs() << "Combined regions:\n"; |
534 | 523 | for (const auto &CR : CombinedRegions) |
535 | 523 | dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> " |
536 | 523 | << CR.LineEnd << ":" << CR.ColumnEnd |
537 | 523 | << " (count=" << CR.ExecutionCount << ")\n"; |
538 | 523 | }); |
539 | 523 | |
540 | 523 | Builder.buildSegmentsImpl(CombinedRegions); |
541 | 523 | |
542 | | #ifndef NDEBUG |
543 | | for (unsigned I = 1, E = Segments.size(); I < E; ++I) { |
544 | | const auto &L = Segments[I - 1]; |
545 | | const auto &R = Segments[I]; |
546 | | if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) { |
547 | | LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col |
548 | | << " followed by " << R.Line << ":" << R.Col << "\n"); |
549 | | assert(false && "Coverage segments not unique or sorted"); |
550 | | } |
551 | | } |
552 | | #endif |
553 | | |
554 | 523 | return Segments; |
555 | 523 | } |
556 | | }; |
557 | | |
558 | | } // end anonymous namespace |
559 | | |
560 | 215 | std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const { |
561 | 215 | std::vector<StringRef> Filenames; |
562 | 215 | for (const auto &Function : getCoveredFunctions()) |
563 | 751 | Filenames.insert(Filenames.end(), Function.Filenames.begin(), |
564 | 751 | Function.Filenames.end()); |
565 | 215 | llvm::sort(Filenames); |
566 | 215 | auto Last = std::unique(Filenames.begin(), Filenames.end()); |
567 | 215 | Filenames.erase(Last, Filenames.end()); |
568 | 215 | return Filenames; |
569 | 215 | } |
570 | | |
571 | | static SmallBitVector gatherFileIDs(StringRef SourceFile, |
572 | 915 | const FunctionRecord &Function) { |
573 | 915 | SmallBitVector FilenameEquivalence(Function.Filenames.size(), false); |
574 | 1.88k | for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I970 ) |
575 | 970 | if (SourceFile == Function.Filenames[I]) |
576 | 269 | FilenameEquivalence[I] = true; |
577 | 915 | return FilenameEquivalence; |
578 | 915 | } |
579 | | |
580 | | /// Return the ID of the file where the definition of the function is located. |
581 | 2.82k | static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) { |
582 | 2.82k | SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true); |
583 | 2.82k | for (const auto &CR : Function.CountedRegions) |
584 | 14.9k | if (CR.Kind == CounterMappingRegion::ExpansionRegion) |
585 | 74 | IsNotExpandedFile[CR.ExpandedFileID] = false; |
586 | 2.82k | int I = IsNotExpandedFile.find_first(); |
587 | 2.82k | if (I == -1) |
588 | 0 | return None; |
589 | 2.82k | return I; |
590 | 2.82k | } |
591 | | |
592 | | /// Check if SourceFile is the file that contains the definition of |
593 | | /// the Function. Return the ID of the file in that case or None otherwise. |
594 | | static Optional<unsigned> findMainViewFileID(StringRef SourceFile, |
595 | 2.49k | const FunctionRecord &Function) { |
596 | 2.49k | Optional<unsigned> I = findMainViewFileID(Function); |
597 | 2.49k | if (I && SourceFile == Function.Filenames[*I]2.48k ) |
598 | 622 | return I; |
599 | 1.86k | return None; |
600 | 1.86k | } |
601 | | |
602 | 2.92k | static bool isExpansion(const CountedRegion &R, unsigned FileID) { |
603 | 2.92k | return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID35 ; |
604 | 2.92k | } |
605 | | |
606 | 183 | CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const { |
607 | 183 | CoverageData FileCoverage(Filename); |
608 | 183 | std::vector<CountedRegion> Regions; |
609 | 183 | |
610 | 915 | for (const auto &Function : Functions) { |
611 | 915 | auto MainFileID = findMainViewFileID(Filename, Function); |
612 | 915 | auto FileIDs = gatherFileIDs(Filename, Function); |
613 | 915 | for (const auto &CR : Function.CountedRegions) |
614 | 5.03k | if (FileIDs.test(CR.FileID)) { |
615 | 1.30k | Regions.push_back(CR); |
616 | 1.30k | if (MainFileID && isExpansion(CR, *MainFileID)1.28k ) |
617 | 17 | FileCoverage.Expansions.emplace_back(CR, Function); |
618 | 1.30k | } |
619 | 915 | } |
620 | 183 | |
621 | 183 | LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); |
622 | 183 | FileCoverage.Segments = SegmentBuilder::buildSegments(Regions); |
623 | 183 | |
624 | 183 | return FileCoverage; |
625 | 183 | } |
626 | | |
627 | | std::vector<InstantiationGroup> |
628 | 254 | CoverageMapping::getInstantiationGroups(StringRef Filename) const { |
629 | 254 | FunctionInstantiationSetCollector InstantiationSetCollector; |
630 | 1.57k | for (const auto &Function : Functions) { |
631 | 1.57k | auto MainFileID = findMainViewFileID(Filename, Function); |
632 | 1.57k | if (!MainFileID) |
633 | 1.19k | continue; |
634 | 379 | InstantiationSetCollector.insert(Function, *MainFileID); |
635 | 379 | } |
636 | 254 | |
637 | 254 | std::vector<InstantiationGroup> Result; |
638 | 310 | for (auto &InstantiationSet : InstantiationSetCollector) { |
639 | 310 | InstantiationGroup IG{InstantiationSet.first.first, |
640 | 310 | InstantiationSet.first.second, |
641 | 310 | std::move(InstantiationSet.second)}; |
642 | 310 | Result.emplace_back(std::move(IG)); |
643 | 310 | } |
644 | 254 | return Result; |
645 | 254 | } |
646 | | |
647 | | CoverageData |
648 | 336 | CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { |
649 | 336 | auto MainFileID = findMainViewFileID(Function); |
650 | 336 | if (!MainFileID) |
651 | 0 | return CoverageData(); |
652 | 336 | |
653 | 336 | CoverageData FunctionCoverage(Function.Filenames[*MainFileID]); |
654 | 336 | std::vector<CountedRegion> Regions; |
655 | 336 | for (const auto &CR : Function.CountedRegions) |
656 | 1.66k | if (CR.FileID == *MainFileID) { |
657 | 1.62k | Regions.push_back(CR); |
658 | 1.62k | if (isExpansion(CR, *MainFileID)) |
659 | 8 | FunctionCoverage.Expansions.emplace_back(CR, Function); |
660 | 1.62k | } |
661 | 336 | |
662 | 336 | LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name |
663 | 336 | << "\n"); |
664 | 336 | FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions); |
665 | 336 | |
666 | 336 | return FunctionCoverage; |
667 | 336 | } |
668 | | |
669 | | CoverageData CoverageMapping::getCoverageForExpansion( |
670 | 3 | const ExpansionRecord &Expansion) const { |
671 | 3 | CoverageData ExpansionCoverage( |
672 | 3 | Expansion.Function.Filenames[Expansion.FileID]); |
673 | 3 | std::vector<CountedRegion> Regions; |
674 | 3 | for (const auto &CR : Expansion.Function.CountedRegions) |
675 | 48 | if (CR.FileID == Expansion.FileID) { |
676 | 12 | Regions.push_back(CR); |
677 | 12 | if (isExpansion(CR, Expansion.FileID)) |
678 | 2 | ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function); |
679 | 12 | } |
680 | 3 | |
681 | 3 | LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " |
682 | 3 | << Expansion.FileID << "\n"); |
683 | 3 | ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); |
684 | 3 | |
685 | 3 | return ExpansionCoverage; |
686 | 3 | } |
687 | | |
688 | | LineCoverageStats::LineCoverageStats( |
689 | | ArrayRef<const CoverageSegment *> LineSegments, |
690 | | const CoverageSegment *WrappedSegment, unsigned Line) |
691 | | : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line), |
692 | 3.93k | LineSegments(LineSegments), WrappedSegment(WrappedSegment) { |
693 | 3.93k | // Find the minimum number of regions which start in this line. |
694 | 3.93k | unsigned MinRegionCount = 0; |
695 | 5.93k | auto isStartOfRegion = [](const CoverageSegment *S) { |
696 | 5.93k | return !S->IsGapRegion && S->HasCount5.10k && S->IsRegionEntry4.60k ; |
697 | 5.93k | }; |
698 | 7.05k | for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 23.26k ; ++I3.11k ) |
699 | 3.11k | if (isStartOfRegion(LineSegments[I])) |
700 | 1.55k | ++MinRegionCount; |
701 | 3.93k | |
702 | 3.93k | bool StartOfSkippedRegion = !LineSegments.empty() && |
703 | 3.93k | !LineSegments.front()->HasCount1.92k && |
704 | 3.93k | LineSegments.front()->IsRegionEntry382 ; |
705 | 3.93k | |
706 | 3.93k | HasMultipleRegions = MinRegionCount > 1; |
707 | 3.93k | Mapped = |
708 | 3.93k | !StartOfSkippedRegion && |
709 | 3.93k | (3.92k (3.92k WrappedSegment3.92k && WrappedSegment->HasCount2.86k ) || (MinRegionCount > 0)1.36k ); |
710 | 3.93k | |
711 | 3.93k | if (!Mapped) |
712 | 932 | return; |
713 | 3.00k | |
714 | 3.00k | // Pick the max count from the non-gap, region entry segments and the |
715 | 3.00k | // wrapped count. |
716 | 3.00k | if (WrappedSegment) |
717 | 2.59k | ExecutionCount = WrappedSegment->Count; |
718 | 3.00k | if (!MinRegionCount) |
719 | 1.70k | return; |
720 | 1.29k | for (const auto *LS : LineSegments) |
721 | 2.82k | if (isStartOfRegion(LS)) |
722 | 1.66k | ExecutionCount = std::max(ExecutionCount, LS->Count); |
723 | 1.29k | } |
724 | | |
725 | 5.13k | LineCoverageIterator &LineCoverageIterator::operator++() { |
726 | 5.13k | if (Next == CD.end()) { |
727 | 1.19k | Stats = LineCoverageStats(); |
728 | 1.19k | Ended = true; |
729 | 1.19k | return *this; |
730 | 1.19k | } |
731 | 3.93k | if (Segments.size()) |
732 | 1.51k | WrappedSegment = Segments.back(); |
733 | 3.93k | Segments.clear(); |
734 | 7.39k | while (Next != CD.end() && Next->Line == Line6.96k ) |
735 | 3.45k | Segments.push_back(&*Next++); |
736 | 3.93k | Stats = LineCoverageStats(Segments, WrappedSegment, Line); |
737 | 3.93k | ++Line; |
738 | 3.93k | return *this; |
739 | 3.93k | } |
740 | | |
741 | 5 | static std::string getCoverageMapErrString(coveragemap_error Err) { |
742 | 5 | switch (Err) { |
743 | 5 | case coveragemap_error::success: |
744 | 0 | return "Success"; |
745 | 5 | case coveragemap_error::eof: |
746 | 0 | return "End of File"; |
747 | 5 | case coveragemap_error::no_data_found: |
748 | 0 | return "No coverage data found"; |
749 | 5 | case coveragemap_error::unsupported_version: |
750 | 0 | return "Unsupported coverage format version"; |
751 | 5 | case coveragemap_error::truncated: |
752 | 0 | return "Truncated coverage data"; |
753 | 5 | case coveragemap_error::malformed: |
754 | 5 | return "Malformed coverage data"; |
755 | 0 | } |
756 | 0 | llvm_unreachable("A value of coveragemap_error has no message."); |
757 | 0 | } |
758 | | |
759 | | namespace { |
760 | | |
761 | | // FIXME: This class is only here to support the transition to llvm::Error. It |
762 | | // will be removed once this transition is complete. Clients should prefer to |
763 | | // deal with the Error value directly, rather than converting to error_code. |
764 | | class CoverageMappingErrorCategoryType : public std::error_category { |
765 | 0 | const char *name() const noexcept override { return "llvm.coveragemap"; } |
766 | 0 | std::string message(int IE) const override { |
767 | 0 | return getCoverageMapErrString(static_cast<coveragemap_error>(IE)); |
768 | 0 | } |
769 | | }; |
770 | | |
771 | | } // end anonymous namespace |
772 | | |
773 | 5 | std::string CoverageMapError::message() const { |
774 | 5 | return getCoverageMapErrString(Err); |
775 | 5 | } |
776 | | |
777 | | static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory; |
778 | | |
779 | 0 | const std::error_category &llvm::coverage::coveragemap_category() { |
780 | 0 | return *ErrorCategory; |
781 | 0 | } |
782 | | |
783 | | char CoverageMapError::ID = 0; |