LLVM 17.0.0git
CoverageMapping.cpp
Go to the documentation of this file.
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
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
21#include "llvm/ADT/StringRef.h"
22#include "llvm/Object/BuildID.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/Errc.h"
27#include "llvm/Support/Error.h"
32#include <algorithm>
33#include <cassert>
34#include <cstdint>
35#include <iterator>
36#include <map>
37#include <memory>
38#include <optional>
39#include <string>
40#include <system_error>
41#include <utility>
42#include <vector>
43
44using namespace llvm;
45using namespace coverage;
46
47#define DEBUG_TYPE "coverage-mapping"
48
49Counter CounterExpressionBuilder::get(const CounterExpression &E) {
50 auto It = ExpressionIndices.find(E);
51 if (It != ExpressionIndices.end())
52 return Counter::getExpression(It->second);
53 unsigned I = Expressions.size();
54 Expressions.push_back(E);
55 ExpressionIndices[E] = I;
57}
58
59void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
60 SmallVectorImpl<Term> &Terms) {
61 switch (C.getKind()) {
62 case Counter::Zero:
63 break;
65 Terms.emplace_back(C.getCounterID(), Factor);
66 break;
68 const auto &E = Expressions[C.getExpressionID()];
69 extractTerms(E.LHS, Factor, Terms);
70 extractTerms(
71 E.RHS, E.Kind == CounterExpression::Subtract ? -Factor : Factor, Terms);
72 break;
73 }
74}
75
76Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
77 // Gather constant terms.
79 extractTerms(ExpressionTree, +1, Terms);
80
81 // If there are no terms, this is just a zero. The algorithm below assumes at
82 // least one term.
83 if (Terms.size() == 0)
84 return Counter::getZero();
85
86 // Group the terms by counter ID.
87 llvm::sort(Terms, [](const Term &LHS, const Term &RHS) {
88 return LHS.CounterID < RHS.CounterID;
89 });
90
91 // Combine terms by counter ID to eliminate counters that sum to zero.
92 auto Prev = Terms.begin();
93 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
94 if (I->CounterID == Prev->CounterID) {
95 Prev->Factor += I->Factor;
96 continue;
97 }
98 ++Prev;
99 *Prev = *I;
100 }
101 Terms.erase(++Prev, Terms.end());
102
103 Counter C;
104 // Create additions. We do this before subtractions to avoid constructs like
105 // ((0 - X) + Y), as opposed to (Y - X).
106 for (auto T : Terms) {
107 if (T.Factor <= 0)
108 continue;
109 for (int I = 0; I < T.Factor; ++I)
110 if (C.isZero())
111 C = Counter::getCounter(T.CounterID);
112 else
114 Counter::getCounter(T.CounterID)));
115 }
116
117 // Create subtractions.
118 for (auto T : Terms) {
119 if (T.Factor >= 0)
120 continue;
121 for (int I = 0; I < -T.Factor; ++I)
123 Counter::getCounter(T.CounterID)));
124 }
125 return C;
126}
127
130 return Simplify ? simplify(Cnt) : Cnt;
131}
132
134 bool Simplify) {
136 return Simplify ? simplify(Cnt) : Cnt;
137}
138
140 switch (C.getKind()) {
141 case Counter::Zero:
142 OS << '0';
143 return;
145 OS << '#' << C.getCounterID();
146 break;
147 case Counter::Expression: {
148 if (C.getExpressionID() >= Expressions.size())
149 return;
150 const auto &E = Expressions[C.getExpressionID()];
151 OS << '(';
152 dump(E.LHS, OS);
153 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
154 dump(E.RHS, OS);
155 OS << ')';
156 break;
157 }
158 }
159 if (CounterValues.empty())
160 return;
162 if (auto E = Value.takeError()) {
163 consumeError(std::move(E));
164 return;
165 }
166 OS << '[' << *Value << ']';
167}
168
170 switch (C.getKind()) {
171 case Counter::Zero:
172 return 0;
174 if (C.getCounterID() >= CounterValues.size())
176 return CounterValues[C.getCounterID()];
177 case Counter::Expression: {
178 if (C.getExpressionID() >= Expressions.size())
180 const auto &E = Expressions[C.getExpressionID()];
182 if (!LHS)
183 return LHS;
185 if (!RHS)
186 return RHS;
187 return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
188 }
189 }
190 llvm_unreachable("Unhandled CounterKind");
191}
192
194 switch (C.getKind()) {
195 case Counter::Zero:
196 return 0;
198 return C.getCounterID();
199 case Counter::Expression: {
200 if (C.getExpressionID() >= Expressions.size())
201 return 0;
202 const auto &E = Expressions[C.getExpressionID()];
203 return std::max(getMaxCounterID(E.LHS), getMaxCounterID(E.RHS));
204 }
205 }
206 llvm_unreachable("Unhandled CounterKind");
207}
208
209void FunctionRecordIterator::skipOtherFiles() {
210 while (Current != Records.end() && !Filename.empty() &&
211 Filename != Current->Filenames[0])
212 ++Current;
213 if (Current == Records.end())
214 *this = FunctionRecordIterator();
215}
216
217ArrayRef<unsigned> CoverageMapping::getImpreciseRecordIndicesForFilename(
218 StringRef Filename) const {
219 size_t FilenameHash = hash_value(Filename);
220 auto RecordIt = FilenameHash2RecordIndices.find(FilenameHash);
221 if (RecordIt == FilenameHash2RecordIndices.end())
222 return {};
223 return RecordIt->second;
224}
225
226static unsigned getMaxCounterID(const CounterMappingContext &Ctx,
228 unsigned MaxCounterID = 0;
229 for (const auto &Region : Record.MappingRegions) {
230 MaxCounterID = std::max(MaxCounterID, Ctx.getMaxCounterID(Region.Count));
231 }
232 return MaxCounterID;
233}
234
235Error CoverageMapping::loadFunctionRecord(
237 IndexedInstrProfReader &ProfileReader) {
238 StringRef OrigFuncName = Record.FunctionName;
239 if (OrigFuncName.empty())
240 return make_error<CoverageMapError>(coveragemap_error::malformed);
241
242 if (Record.Filenames.empty())
243 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
244 else
245 OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
246
247 CounterMappingContext Ctx(Record.Expressions);
248
249 std::vector<uint64_t> Counts;
250 if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
251 Record.FunctionHash, Counts)) {
252 instrprof_error IPE = InstrProfError::take(std::move(E));
254 FuncHashMismatches.emplace_back(std::string(Record.FunctionName),
255 Record.FunctionHash);
256 return Error::success();
257 } else if (IPE != instrprof_error::unknown_function)
258 return make_error<InstrProfError>(IPE);
259 Counts.assign(getMaxCounterID(Ctx, Record) + 1, 0);
260 }
261 Ctx.setCounts(Counts);
262
263 assert(!Record.MappingRegions.empty() && "Function has no regions");
264
265 // This coverage record is a zero region for a function that's unused in
266 // some TU, but used in a different TU. Ignore it. The coverage maps from the
267 // the other TU will either be loaded (providing full region counts) or they
268 // won't (in which case we don't unintuitively report functions as uncovered
269 // when they have non-zero counts in the profile).
270 if (Record.MappingRegions.size() == 1 &&
271 Record.MappingRegions[0].Count.isZero() && Counts[0] > 0)
272 return Error::success();
273
274 FunctionRecord Function(OrigFuncName, Record.Filenames);
275 for (const auto &Region : Record.MappingRegions) {
276 Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
277 if (auto E = ExecutionCount.takeError()) {
278 consumeError(std::move(E));
279 return Error::success();
280 }
281 Expected<int64_t> AltExecutionCount = Ctx.evaluate(Region.FalseCount);
282 if (auto E = AltExecutionCount.takeError()) {
283 consumeError(std::move(E));
284 return Error::success();
285 }
286 Function.pushRegion(Region, *ExecutionCount, *AltExecutionCount);
287 }
288
289 // Don't create records for (filenames, function) pairs we've already seen.
290 auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
291 Record.Filenames.end());
292 if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
293 return Error::success();
294
295 Functions.push_back(std::move(Function));
296
297 // Performance optimization: keep track of the indices of the function records
298 // which correspond to each filename. This can be used to substantially speed
299 // up queries for coverage info in a file.
300 unsigned RecordIndex = Functions.size() - 1;
301 for (StringRef Filename : Record.Filenames) {
302 auto &RecordIndices = FilenameHash2RecordIndices[hash_value(Filename)];
303 // Note that there may be duplicates in the filename set for a function
304 // record, because of e.g. macro expansions in the function in which both
305 // the macro and the function are defined in the same file.
306 if (RecordIndices.empty() || RecordIndices.back() != RecordIndex)
307 RecordIndices.push_back(RecordIndex);
308 }
309
310 return Error::success();
311}
312
313// This function is for memory optimization by shortening the lifetimes
314// of CoverageMappingReader instances.
315Error CoverageMapping::loadFromReaders(
316 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
317 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage) {
318 for (const auto &CoverageReader : CoverageReaders) {
319 for (auto RecordOrErr : *CoverageReader) {
320 if (Error E = RecordOrErr.takeError())
321 return E;
322 const auto &Record = *RecordOrErr;
323 if (Error E = Coverage.loadFunctionRecord(Record, ProfileReader))
324 return E;
325 }
326 }
327 return Error::success();
328}
329
331 ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
332 IndexedInstrProfReader &ProfileReader) {
333 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
334 if (Error E = loadFromReaders(CoverageReaders, ProfileReader, *Coverage))
335 return std::move(E);
336 return std::move(Coverage);
337}
338
339// If E is a no_data_found error, returns success. Otherwise returns E.
341 return handleErrors(
342 std::move(E), [](const CoverageMapError &CME) {
344 return static_cast<Error>(Error::success());
345 return make_error<CoverageMapError>(CME.get());
346 });
347}
348
349Error CoverageMapping::loadFromFile(
350 StringRef Filename, StringRef Arch, StringRef CompilationDir,
351 IndexedInstrProfReader &ProfileReader, CoverageMapping &Coverage,
352 bool &DataFound, SmallVectorImpl<object::BuildID> *FoundBinaryIDs) {
353 auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(
354 Filename, /*IsText=*/false, /*RequiresNullTerminator=*/false);
355 if (std::error_code EC = CovMappingBufOrErr.getError())
356 return createFileError(Filename, errorCodeToError(EC));
357 MemoryBufferRef CovMappingBufRef =
358 CovMappingBufOrErr.get()->getMemBufferRef();
360
362 auto CoverageReadersOrErr = BinaryCoverageReader::create(
363 CovMappingBufRef, Arch, Buffers, CompilationDir,
364 FoundBinaryIDs ? &BinaryIDs : nullptr);
365 if (Error E = CoverageReadersOrErr.takeError()) {
366 E = handleMaybeNoDataFoundError(std::move(E));
367 if (E)
368 return createFileError(Filename, std::move(E));
369 return E;
370 }
371
373 for (auto &Reader : CoverageReadersOrErr.get())
374 Readers.push_back(std::move(Reader));
375 if (FoundBinaryIDs && !Readers.empty()) {
376 llvm::append_range(*FoundBinaryIDs,
377 llvm::map_range(BinaryIDs, [](object::BuildIDRef BID) {
378 return object::BuildID(BID);
379 }));
380 }
381 DataFound |= !Readers.empty();
382 if (Error E = loadFromReaders(Readers, ProfileReader, Coverage))
383 return createFileError(Filename, std::move(E));
384 return Error::success();
385}
386
388 ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename,
389 vfs::FileSystem &FS, ArrayRef<StringRef> Arches, StringRef CompilationDir,
390 const object::BuildIDFetcher *BIDFetcher, bool CheckBinaryIDs) {
391 auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename, FS);
392 if (Error E = ProfileReaderOrErr.takeError())
393 return createFileError(ProfileFilename, std::move(E));
394 auto ProfileReader = std::move(ProfileReaderOrErr.get());
395 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
396 bool DataFound = false;
397
398 auto GetArch = [&](size_t Idx) {
399 if (Arches.empty())
400 return StringRef();
401 if (Arches.size() == 1)
402 return Arches.front();
403 return Arches[Idx];
404 };
405
406 SmallVector<object::BuildID> FoundBinaryIDs;
407 for (const auto &File : llvm::enumerate(ObjectFilenames)) {
408 if (Error E =
409 loadFromFile(File.value(), GetArch(File.index()), CompilationDir,
410 *ProfileReader, *Coverage, DataFound, &FoundBinaryIDs))
411 return std::move(E);
412 }
413
414 if (BIDFetcher) {
415 std::vector<object::BuildID> ProfileBinaryIDs;
416 if (Error E = ProfileReader->readBinaryIds(ProfileBinaryIDs))
417 return createFileError(ProfileFilename, std::move(E));
418
419 SmallVector<object::BuildIDRef> BinaryIDsToFetch;
420 if (!ProfileBinaryIDs.empty()) {
421 const auto &Compare = [](object::BuildIDRef A, object::BuildIDRef B) {
422 return std::lexicographical_compare(A.begin(), A.end(), B.begin(),
423 B.end());
424 };
425 llvm::sort(FoundBinaryIDs, Compare);
426 std::set_difference(
427 ProfileBinaryIDs.begin(), ProfileBinaryIDs.end(),
428 FoundBinaryIDs.begin(), FoundBinaryIDs.end(),
429 std::inserter(BinaryIDsToFetch, BinaryIDsToFetch.end()), Compare);
430 }
431
432 for (object::BuildIDRef BinaryID : BinaryIDsToFetch) {
433 std::optional<std::string> PathOpt = BIDFetcher->fetch(BinaryID);
434 if (PathOpt) {
435 std::string Path = std::move(*PathOpt);
436 StringRef Arch = Arches.size() == 1 ? Arches.front() : StringRef();
437 if (Error E = loadFromFile(Path, Arch, CompilationDir, *ProfileReader,
438 *Coverage, DataFound))
439 return std::move(E);
440 } else if (CheckBinaryIDs) {
441 return createFileError(
442 ProfileFilename,
444 "Missing binary ID: " +
445 llvm::toHex(BinaryID, /*LowerCase=*/true)));
446 }
447 }
448 }
449
450 if (!DataFound)
451 return createFileError(
452 join(ObjectFilenames.begin(), ObjectFilenames.end(), ", "),
453 make_error<CoverageMapError>(coveragemap_error::no_data_found));
454 return std::move(Coverage);
455}
456
457namespace {
458
459/// Distributes functions into instantiation sets.
460///
461/// An instantiation set is a collection of functions that have the same source
462/// code, ie, template functions specializations.
463class FunctionInstantiationSetCollector {
464 using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
465 MapT InstantiatedFunctions;
466
467public:
468 void insert(const FunctionRecord &Function, unsigned FileID) {
469 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
470 while (I != E && I->FileID != FileID)
471 ++I;
472 assert(I != E && "function does not cover the given file");
473 auto &Functions = InstantiatedFunctions[I->startLoc()];
474 Functions.push_back(&Function);
475 }
476
477 MapT::iterator begin() { return InstantiatedFunctions.begin(); }
478 MapT::iterator end() { return InstantiatedFunctions.end(); }
479};
480
481class SegmentBuilder {
482 std::vector<CoverageSegment> &Segments;
484
485 SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
486
487 /// Emit a segment with the count from \p Region starting at \p StartLoc.
488 //
489 /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
490 /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
491 void startSegment(const CountedRegion &Region, LineColPair StartLoc,
492 bool IsRegionEntry, bool EmitSkippedRegion = false) {
493 bool HasCount = !EmitSkippedRegion &&
495
496 // If the new segment wouldn't affect coverage rendering, skip it.
497 if (!Segments.empty() && !IsRegionEntry && !EmitSkippedRegion) {
498 const auto &Last = Segments.back();
499 if (Last.HasCount == HasCount && Last.Count == Region.ExecutionCount &&
500 !Last.IsRegionEntry)
501 return;
502 }
503
504 if (HasCount)
505 Segments.emplace_back(StartLoc.first, StartLoc.second,
506 Region.ExecutionCount, IsRegionEntry,
508 else
509 Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
510
511 LLVM_DEBUG({
512 const auto &Last = Segments.back();
513 dbgs() << "Segment at " << Last.Line << ":" << Last.Col
514 << " (count = " << Last.Count << ")"
515 << (Last.IsRegionEntry ? ", RegionEntry" : "")
516 << (!Last.HasCount ? ", Skipped" : "")
517 << (Last.IsGapRegion ? ", Gap" : "") << "\n";
518 });
519 }
520
521 /// Emit segments for active regions which end before \p Loc.
522 ///
523 /// \p Loc: The start location of the next region. If std::nullopt, all active
524 /// regions are completed.
525 /// \p FirstCompletedRegion: Index of the first completed region.
526 void completeRegionsUntil(std::optional<LineColPair> Loc,
527 unsigned FirstCompletedRegion) {
528 // Sort the completed regions by end location. This makes it simple to
529 // emit closing segments in sorted order.
530 auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
531 std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
532 [](const CountedRegion *L, const CountedRegion *R) {
533 return L->endLoc() < R->endLoc();
534 });
535
536 // Emit segments for all completed regions.
537 for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
538 ++I) {
539 const auto *CompletedRegion = ActiveRegions[I];
540 assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
541 "Completed region ends after start of new region");
542
543 const auto *PrevCompletedRegion = ActiveRegions[I - 1];
544 auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
545
546 // Don't emit any more segments if they start where the new region begins.
547 if (Loc && CompletedSegmentLoc == *Loc)
548 break;
549
550 // Don't emit a segment if the next completed region ends at the same
551 // location as this one.
552 if (CompletedSegmentLoc == CompletedRegion->endLoc())
553 continue;
554
555 // Use the count from the last completed region which ends at this loc.
556 for (unsigned J = I + 1; J < E; ++J)
557 if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
558 CompletedRegion = ActiveRegions[J];
559
560 startSegment(*CompletedRegion, CompletedSegmentLoc, false);
561 }
562
563 auto Last = ActiveRegions.back();
564 if (FirstCompletedRegion && Last->endLoc() != *Loc) {
565 // If there's a gap after the end of the last completed region and the
566 // start of the new region, use the last active region to fill the gap.
567 startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
568 false);
569 } else if (!FirstCompletedRegion && (!Loc || *Loc != Last->endLoc())) {
570 // Emit a skipped segment if there are no more active regions. This
571 // ensures that gaps between functions are marked correctly.
572 startSegment(*Last, Last->endLoc(), false, true);
573 }
574
575 // Pop the completed regions.
576 ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
577 }
578
579 void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
580 for (const auto &CR : enumerate(Regions)) {
581 auto CurStartLoc = CR.value().startLoc();
582
583 // Active regions which end before the current region need to be popped.
584 auto CompletedRegions =
585 std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
586 [&](const CountedRegion *Region) {
587 return !(Region->endLoc() <= CurStartLoc);
588 });
589 if (CompletedRegions != ActiveRegions.end()) {
590 unsigned FirstCompletedRegion =
591 std::distance(ActiveRegions.begin(), CompletedRegions);
592 completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
593 }
594
595 bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
596
597 // Try to emit a segment for the current region.
598 if (CurStartLoc == CR.value().endLoc()) {
599 // Avoid making zero-length regions active. If it's the last region,
600 // emit a skipped segment. Otherwise use its predecessor's count.
601 const bool Skipped =
602 (CR.index() + 1) == Regions.size() ||
603 CR.value().Kind == CounterMappingRegion::SkippedRegion;
604 startSegment(ActiveRegions.empty() ? CR.value() : *ActiveRegions.back(),
605 CurStartLoc, !GapRegion, Skipped);
606 // If it is skipped segment, create a segment with last pushed
607 // regions's count at CurStartLoc.
608 if (Skipped && !ActiveRegions.empty())
609 startSegment(*ActiveRegions.back(), CurStartLoc, false);
610 continue;
611 }
612 if (CR.index() + 1 == Regions.size() ||
613 CurStartLoc != Regions[CR.index() + 1].startLoc()) {
614 // Emit a segment if the next region doesn't start at the same location
615 // as this one.
616 startSegment(CR.value(), CurStartLoc, !GapRegion);
617 }
618
619 // This region is active (i.e not completed).
620 ActiveRegions.push_back(&CR.value());
621 }
622
623 // Complete any remaining active regions.
624 if (!ActiveRegions.empty())
625 completeRegionsUntil(std::nullopt, 0);
626 }
627
628 /// Sort a nested sequence of regions from a single file.
629 static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
630 llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
631 if (LHS.startLoc() != RHS.startLoc())
632 return LHS.startLoc() < RHS.startLoc();
633 if (LHS.endLoc() != RHS.endLoc())
634 // When LHS completely contains RHS, we sort LHS first.
635 return RHS.endLoc() < LHS.endLoc();
636 // If LHS and RHS cover the same area, we need to sort them according
637 // to their kinds so that the most suitable region will become "active"
638 // in combineRegions(). Because we accumulate counter values only from
639 // regions of the same kind as the first region of the area, prefer
640 // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
645 "Unexpected order of region kind values");
646 return LHS.Kind < RHS.Kind;
647 });
648 }
649
650 /// Combine counts of regions which cover the same area.
652 combineRegions(MutableArrayRef<CountedRegion> Regions) {
653 if (Regions.empty())
654 return Regions;
655 auto Active = Regions.begin();
656 auto End = Regions.end();
657 for (auto I = Regions.begin() + 1; I != End; ++I) {
658 if (Active->startLoc() != I->startLoc() ||
659 Active->endLoc() != I->endLoc()) {
660 // Shift to the next region.
661 ++Active;
662 if (Active != I)
663 *Active = *I;
664 continue;
665 }
666 // Merge duplicate region.
667 // If CodeRegions and ExpansionRegions cover the same area, it's probably
668 // a macro which is fully expanded to another macro. In that case, we need
669 // to accumulate counts only from CodeRegions, or else the area will be
670 // counted twice.
671 // On the other hand, a macro may have a nested macro in its body. If the
672 // outer macro is used several times, the ExpansionRegion for the nested
673 // macro will also be added several times. These ExpansionRegions cover
674 // the same source locations and have to be combined to reach the correct
675 // value for that area.
676 // We add counts of the regions of the same kind as the active region
677 // to handle the both situations.
678 if (I->Kind == Active->Kind)
679 Active->ExecutionCount += I->ExecutionCount;
680 }
681 return Regions.drop_back(std::distance(++Active, End));
682 }
683
684public:
685 /// Build a sorted list of CoverageSegments from a list of Regions.
686 static std::vector<CoverageSegment>
687 buildSegments(MutableArrayRef<CountedRegion> Regions) {
688 std::vector<CoverageSegment> Segments;
689 SegmentBuilder Builder(Segments);
690
691 sortNestedRegions(Regions);
692 ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
693
694 LLVM_DEBUG({
695 dbgs() << "Combined regions:\n";
696 for (const auto &CR : CombinedRegions)
697 dbgs() << " " << CR.LineStart << ":" << CR.ColumnStart << " -> "
698 << CR.LineEnd << ":" << CR.ColumnEnd
699 << " (count=" << CR.ExecutionCount << ")\n";
700 });
701
702 Builder.buildSegmentsImpl(CombinedRegions);
703
704#ifndef NDEBUG
705 for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
706 const auto &L = Segments[I - 1];
707 const auto &R = Segments[I];
708 if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
709 if (L.Line == R.Line && L.Col == R.Col && !L.HasCount)
710 continue;
711 LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
712 << " followed by " << R.Line << ":" << R.Col << "\n");
713 assert(false && "Coverage segments not unique or sorted");
714 }
715 }
716#endif
717
718 return Segments;
719 }
720};
721
722} // end anonymous namespace
723
724std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
725 std::vector<StringRef> Filenames;
726 for (const auto &Function : getCoveredFunctions())
727 llvm::append_range(Filenames, Function.Filenames);
728 llvm::sort(Filenames);
729 auto Last = std::unique(Filenames.begin(), Filenames.end());
730 Filenames.erase(Last, Filenames.end());
731 return Filenames;
732}
733
735 const FunctionRecord &Function) {
736 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
737 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
738 if (SourceFile == Function.Filenames[I])
739 FilenameEquivalence[I] = true;
740 return FilenameEquivalence;
741}
742
743/// Return the ID of the file where the definition of the function is located.
744static std::optional<unsigned>
746 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
747 for (const auto &CR : Function.CountedRegions)
749 IsNotExpandedFile[CR.ExpandedFileID] = false;
750 int I = IsNotExpandedFile.find_first();
751 if (I == -1)
752 return std::nullopt;
753 return I;
754}
755
756/// Check if SourceFile is the file that contains the definition of
757/// the Function. Return the ID of the file in that case or std::nullopt
758/// otherwise.
759static std::optional<unsigned>
761 std::optional<unsigned> I = findMainViewFileID(Function);
762 if (I && SourceFile == Function.Filenames[*I])
763 return I;
764 return std::nullopt;
765}
766
767static bool isExpansion(const CountedRegion &R, unsigned FileID) {
768 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
769}
770
772 CoverageData FileCoverage(Filename);
773 std::vector<CountedRegion> Regions;
774
775 // Look up the function records in the given file. Due to hash collisions on
776 // the filename, we may get back some records that are not in the file.
777 ArrayRef<unsigned> RecordIndices =
778 getImpreciseRecordIndicesForFilename(Filename);
779 for (unsigned RecordIndex : RecordIndices) {
780 const FunctionRecord &Function = Functions[RecordIndex];
781 auto MainFileID = findMainViewFileID(Filename, Function);
782 auto FileIDs = gatherFileIDs(Filename, Function);
783 for (const auto &CR : Function.CountedRegions)
784 if (FileIDs.test(CR.FileID)) {
785 Regions.push_back(CR);
786 if (MainFileID && isExpansion(CR, *MainFileID))
787 FileCoverage.Expansions.emplace_back(CR, Function);
788 }
789 // Capture branch regions specific to the function (excluding expansions).
790 for (const auto &CR : Function.CountedBranchRegions)
791 if (FileIDs.test(CR.FileID) && (CR.FileID == CR.ExpandedFileID))
792 FileCoverage.BranchRegions.push_back(CR);
793 }
794
795 LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
796 FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
797
798 return FileCoverage;
799}
800
801std::vector<InstantiationGroup>
803 FunctionInstantiationSetCollector InstantiationSetCollector;
804 // Look up the function records in the given file. Due to hash collisions on
805 // the filename, we may get back some records that are not in the file.
806 ArrayRef<unsigned> RecordIndices =
807 getImpreciseRecordIndicesForFilename(Filename);
808 for (unsigned RecordIndex : RecordIndices) {
809 const FunctionRecord &Function = Functions[RecordIndex];
810 auto MainFileID = findMainViewFileID(Filename, Function);
811 if (!MainFileID)
812 continue;
813 InstantiationSetCollector.insert(Function, *MainFileID);
814 }
815
816 std::vector<InstantiationGroup> Result;
817 for (auto &InstantiationSet : InstantiationSetCollector) {
818 InstantiationGroup IG{InstantiationSet.first.first,
819 InstantiationSet.first.second,
820 std::move(InstantiationSet.second)};
821 Result.emplace_back(std::move(IG));
822 }
823 return Result;
824}
825
828 auto MainFileID = findMainViewFileID(Function);
829 if (!MainFileID)
830 return CoverageData();
831
832 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
833 std::vector<CountedRegion> Regions;
834 for (const auto &CR : Function.CountedRegions)
835 if (CR.FileID == *MainFileID) {
836 Regions.push_back(CR);
837 if (isExpansion(CR, *MainFileID))
838 FunctionCoverage.Expansions.emplace_back(CR, Function);
839 }
840 // Capture branch regions specific to the function (excluding expansions).
841 for (const auto &CR : Function.CountedBranchRegions)
842 if (CR.FileID == *MainFileID)
843 FunctionCoverage.BranchRegions.push_back(CR);
844
845 LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
846 << "\n");
847 FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
848
849 return FunctionCoverage;
850}
851
853 const ExpansionRecord &Expansion) const {
854 CoverageData ExpansionCoverage(
855 Expansion.Function.Filenames[Expansion.FileID]);
856 std::vector<CountedRegion> Regions;
857 for (const auto &CR : Expansion.Function.CountedRegions)
858 if (CR.FileID == Expansion.FileID) {
859 Regions.push_back(CR);
860 if (isExpansion(CR, Expansion.FileID))
861 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
862 }
863 for (const auto &CR : Expansion.Function.CountedBranchRegions)
864 // Capture branch regions that only pertain to the corresponding expansion.
865 if (CR.FileID == Expansion.FileID)
866 ExpansionCoverage.BranchRegions.push_back(CR);
867
868 LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
869 << Expansion.FileID << "\n");
870 ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
871
872 return ExpansionCoverage;
873}
874
875LineCoverageStats::LineCoverageStats(
877 const CoverageSegment *WrappedSegment, unsigned Line)
878 : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
879 LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
880 // Find the minimum number of regions which start in this line.
881 unsigned MinRegionCount = 0;
882 auto isStartOfRegion = [](const CoverageSegment *S) {
883 return !S->IsGapRegion && S->HasCount && S->IsRegionEntry;
884 };
885 for (unsigned I = 0; I < LineSegments.size() && MinRegionCount < 2; ++I)
886 if (isStartOfRegion(LineSegments[I]))
887 ++MinRegionCount;
888
889 bool StartOfSkippedRegion = !LineSegments.empty() &&
890 !LineSegments.front()->HasCount &&
891 LineSegments.front()->IsRegionEntry;
892
893 HasMultipleRegions = MinRegionCount > 1;
894 Mapped =
895 !StartOfSkippedRegion &&
896 ((WrappedSegment && WrappedSegment->HasCount) || (MinRegionCount > 0));
897
898 if (!Mapped)
899 return;
900
901 // Pick the max count from the non-gap, region entry segments and the
902 // wrapped count.
903 if (WrappedSegment)
904 ExecutionCount = WrappedSegment->Count;
905 if (!MinRegionCount)
906 return;
907 for (const auto *LS : LineSegments)
908 if (isStartOfRegion(LS))
909 ExecutionCount = std::max(ExecutionCount, LS->Count);
910}
911
913 if (Next == CD.end()) {
914 Stats = LineCoverageStats();
915 Ended = true;
916 return *this;
917 }
918 if (Segments.size())
919 WrappedSegment = Segments.back();
920 Segments.clear();
921 while (Next != CD.end() && Next->Line == Line)
922 Segments.push_back(&*Next++);
923 Stats = LineCoverageStats(Segments, WrappedSegment, Line);
924 ++Line;
925 return *this;
926}
927
929 switch (Err) {
931 return "Success";
933 return "End of File";
935 return "No coverage data found";
937 return "Unsupported coverage format version";
939 return "Truncated coverage data";
941 return "Malformed coverage data";
943 return "Failed to decompress coverage data (zlib)";
945 return "`-arch` specifier is invalid or missing for universal binary";
946 }
947 llvm_unreachable("A value of coveragemap_error has no message.");
948}
949
950namespace {
951
952// FIXME: This class is only here to support the transition to llvm::Error. It
953// will be removed once this transition is complete. Clients should prefer to
954// deal with the Error value directly, rather than converting to error_code.
955class CoverageMappingErrorCategoryType : public std::error_category {
956 const char *name() const noexcept override { return "llvm.coveragemap"; }
957 std::string message(int IE) const override {
958 return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
959 }
960};
961
962} // end anonymous namespace
963
964std::string CoverageMapError::message() const {
965 return getCoverageMapErrString(Err);
966}
967
968const std::error_category &llvm::coverage::coveragemap_category() {
969 static CoverageMappingErrorCategoryType ErrorCategory;
970 return ErrorCategory;
971}
972
973char CoverageMapError::ID = 0;
aarch64 promote const
assume Assume Simplify
assume Assume Builder
This file declares a library for handling Build IDs and using them to find debug info.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static SmallBitVector gatherFileIDs(StringRef SourceFile, const FunctionRecord &Function)
static std::optional< unsigned > findMainViewFileID(const FunctionRecord &Function)
Return the ID of the file where the definition of the function is located.
static bool isExpansion(const CountedRegion &R, unsigned FileID)
static std::string getCoverageMapErrString(coveragemap_error Err)
static Error handleMaybeNoDataFoundError(Error E)
static unsigned getMaxCounterID(const CounterMappingContext &Ctx, const CoverageMappingRecord &Record)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
hexagon bit simplify
#define I(x, y, z)
Definition: MD5.cpp:58
if(VerifyEach)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const char * name
Definition: SMEABIPass.cpp:49
raw_pwrite_stream & OS
This file implements the SmallBitVector class.
This file defines the SmallString class.
This file defines the SmallVector class.
This file contains some functions that are useful when dealing with strings.
Defines the virtual file system interface vfs::FileSystem.
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:166
iterator end() const
Definition: ArrayRef.h:152
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:163
iterator begin() const
Definition: ArrayRef.h:151
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
static ErrorSuccess success()
Create a success value.
Definition: Error.h:330
Tagged union holding either a T or a Error.
Definition: Error.h:470
Error takeError()
Take ownership of the stored error.
Definition: Error.h:597
iterator begin()
Definition: Function.h:756
size_t size() const
Definition: Function.h:761
iterator end()
Definition: Function.h:758
Reader for the indexed binary instrprof format.
static Expected< std::unique_ptr< IndexedInstrProfReader > > create(const Twine &Path, vfs::FileSystem &FS, const Twine &RemappingPath="")
Factory method to create an indexed reader.
Error getFunctionCounts(StringRef FuncName, uint64_t FuncHash, std::vector< uint64_t > &Counts)
Fill Counts with the profile data for the given function name.
Error readBinaryIds(std::vector< llvm::object::BuildID > &BinaryIds) override
Read a list of binary ids.
static instrprof_error take(Error E)
Consume an Error and return the raw enum value contained within it.
Definition: InstrProf.h:358
static ErrorOr< std::unique_ptr< MemoryBuffer > > getFileOrSTDIN(const Twine &Filename, bool IsText=false, bool RequiresNullTerminator=true, std::optional< Align > Alignment=std::nullopt)
Open the specified file as a MemoryBuffer, or open stdin if the Filename is "-".
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:305
iterator end() const
Definition: ArrayRef.h:355
iterator begin() const
Definition: ArrayRef.h:354
MutableArrayRef< T > drop_back(size_t N=1) const
Definition: ArrayRef.h:390
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
constexpr bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:134
LLVM Value Representation.
Definition: Value.h:74
static Expected< std::vector< std::unique_ptr< BinaryCoverageReader > > > create(MemoryBufferRef ObjectBuffer, StringRef Arch, SmallVectorImpl< std::unique_ptr< MemoryBuffer > > &ObjectFileBuffers, StringRef CompilationDir="", SmallVectorImpl< object::BuildIDRef > *BinaryIDs=nullptr)
Counter subtract(Counter LHS, Counter RHS, bool Simplify=true)
Return a counter that represents the expression that subtracts RHS from LHS.
Counter add(Counter LHS, Counter RHS, bool Simplify=true)
Return a counter that represents the expression that adds LHS and RHS.
A Counter mapping context is used to connect the counters, expressions and the obtained counter value...
Expected< int64_t > evaluate(const Counter &C) const
Return the number of times that a region of code associated with this counter was executed.
unsigned getMaxCounterID(const Counter &C) const
void dump(const Counter &C, raw_ostream &OS) const
Coverage information to be processed or displayed.
std::vector< CoverageSegment >::const_iterator end() const
std::string message() const override
Return the error message as a string.
coveragemap_error get() const
The mapping of profile information to coverage data.
std::vector< StringRef > getUniqueSourceFiles() const
Returns a lexicographically sorted, unique list of files that are covered.
CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const
Get the coverage for an expansion within a coverage set.
iterator_range< FunctionRecordIterator > getCoveredFunctions() const
Gets all of the functions covered by this profile.
CoverageData getCoverageForFunction(const FunctionRecord &Function) const
Get the coverage for a particular function.
std::vector< InstantiationGroup > getInstantiationGroups(StringRef Filename) const
Get the list of function instantiation groups in a particular file.
CoverageData getCoverageForFile(StringRef Filename) const
Get the coverage for a particular file.
static Expected< std::unique_ptr< CoverageMapping > > load(ArrayRef< std::unique_ptr< CoverageMappingReader > > CoverageReaders, IndexedInstrProfReader &ProfileReader)
Load the coverage mapping using the given readers.
An instantiation group contains a FunctionRecord list, such that each record corresponds to a distinc...
An iterator over the LineCoverageStats objects for lines described by a CoverageData instance.
Coverage statistics for a single line.
BuildIDFetcher searches local cache directories for debug info.
Definition: BuildID.h:36
virtual std::optional< std::string > fetch(BuildIDRef BuildID) const
Returns the path to the debug file with the given build ID.
Definition: BuildID.cpp:60
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:226
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
The virtual file system interface.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
const std::error_category & coveragemap_category()
std::pair< unsigned, unsigned > LineColPair
SmallVector< uint8_t, 10 > BuildID
A build ID in binary form.
Definition: BuildID.h:25
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
hash_code hash_value(const FixedPointSemantics &Val)
Definition: APFixedPoint.h:128
Error createFileError(const Twine &F, Error E)
Concatenate a source file path and/or name with an Error.
Definition: Error.h:1327
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2424
StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName="<unknown>")
Given a PGO function name, remove the filename prefix and return the original (static) function name.
Definition: InstrProf.cpp:324
Error handleErrors(Error E, HandlerTs &&... Hs)
Pass the ErrorInfo(s) contained in E to their respective handlers.
Definition: Error.h:943
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1246
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:461
@ no_such_file_or_directory
@ argument_out_of_domain
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1744
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
instrprof_error
Definition: InstrProf.h:308
Error errorCodeToError(std::error_code EC)
Helper for converting an std::error_code to a Error.
Definition: Error.cpp:92
void consumeError(Error Err)
Consume a Error without doing anything.
Definition: Error.h:1043
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
Associates a source range with an execution count.
A Counter expression is a value that represents an arithmetic operation with two counters.
@ ExpansionRegion
An ExpansionRegion represents a file expansion region that associates a source range with the expansi...
@ SkippedRegion
A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...
@ GapRegion
A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...
@ CodeRegion
A CodeRegion associates some code with a counter.
A Counter is an abstract value that describes how to compute the execution count for a region of code...
static Counter getZero()
Return the counter that represents the number zero.
static Counter getCounter(unsigned CounterId)
Return the counter that corresponds to a specific profile counter.
static Counter getExpression(unsigned ExpressionId)
Return the counter that corresponds to a specific addition counter expression.
Coverage mapping information for a single function.
The execution count information starting at a point in a file.
bool HasCount
When false, the segment was uninstrumented or skipped.
uint64_t Count
The execution count, or zero if no count was recorded.
bool IsGapRegion
Whether this enters a gap region.
Coverage information for a macro expansion or #included file.
unsigned FileID
The abstract file this expansion covers.
const FunctionRecord & Function
Coverage for the expansion.
Code coverage information for a single function.
std::vector< CountedRegion > CountedBranchRegions
Branch Regions in the function along with their counts.
std::vector< CountedRegion > CountedRegions
Regions in the function along with their counts.
std::vector< std::string > Filenames
Mapping from FileID (i.e.