1 //=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains support for clang's and llvm's instrumentation based
13 //===----------------------------------------------------------------------===//
15 #include "llvm/ProfileData/CoverageMapping.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/Optional.h"
18 #include "llvm/ADT/SmallBitVector.h"
19 #include "llvm/ProfileData/CoverageMappingReader.h"
20 #include "llvm/ProfileData/InstrProfReader.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/Path.h"
24 #include "llvm/Support/raw_ostream.h"
27 using namespace coverage;
29 #define DEBUG_TYPE "coverage-mapping"
31 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
32 auto It = ExpressionIndices.find(E);
33 if (It != ExpressionIndices.end())
34 return Counter::getExpression(It->second);
35 unsigned I = Expressions.size();
36 Expressions.push_back(E);
37 ExpressionIndices[E] = I;
38 return Counter::getExpression(I);
41 void CounterExpressionBuilder::extractTerms(
42 Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
43 switch (C.getKind()) {
46 case Counter::CounterValueReference:
47 Terms.push_back(std::make_pair(C.getCounterID(), Sign));
49 case Counter::Expression:
50 const auto &E = Expressions[C.getExpressionID()];
51 extractTerms(E.LHS, Sign, Terms);
52 extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
58 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
59 // Gather constant terms.
60 llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
61 extractTerms(ExpressionTree, +1, Terms);
63 // If there are no terms, this is just a zero. The algorithm below assumes at
65 if (Terms.size() == 0)
66 return Counter::getZero();
68 // Group the terms by counter ID.
69 std::sort(Terms.begin(), Terms.end(),
70 [](const std::pair<unsigned, int> &LHS,
71 const std::pair<unsigned, int> &RHS) {
72 return LHS.first < RHS.first;
75 // Combine terms by counter ID to eliminate counters that sum to zero.
76 auto Prev = Terms.begin();
77 for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
78 if (I->first == Prev->first) {
79 Prev->second += I->second;
85 Terms.erase(++Prev, Terms.end());
88 // Create additions. We do this before subtractions to avoid constructs like
89 // ((0 - X) + Y), as opposed to (Y - X).
90 for (auto Term : Terms) {
93 for (int I = 0; I < Term.second; ++I)
95 C = Counter::getCounter(Term.first);
97 C = get(CounterExpression(CounterExpression::Add, C,
98 Counter::getCounter(Term.first)));
101 // Create subtractions.
102 for (auto Term : Terms) {
103 if (Term.second >= 0)
105 for (int I = 0; I < -Term.second; ++I)
106 C = get(CounterExpression(CounterExpression::Subtract, C,
107 Counter::getCounter(Term.first)));
112 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
113 return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
116 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
118 get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
121 void CounterMappingContext::dump(const Counter &C,
122 llvm::raw_ostream &OS) const {
123 switch (C.getKind()) {
127 case Counter::CounterValueReference:
128 OS << '#' << C.getCounterID();
130 case Counter::Expression: {
131 if (C.getExpressionID() >= Expressions.size())
133 const auto &E = Expressions[C.getExpressionID()];
136 OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
142 if (CounterValues.empty())
144 ErrorOr<int64_t> Value = evaluate(C);
147 OS << '[' << *Value << ']';
150 ErrorOr<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
151 switch (C.getKind()) {
154 case Counter::CounterValueReference:
155 if (C.getCounterID() >= CounterValues.size())
156 return std::make_error_code(std::errc::argument_out_of_domain);
157 return CounterValues[C.getCounterID()];
158 case Counter::Expression: {
159 if (C.getExpressionID() >= Expressions.size())
160 return std::make_error_code(std::errc::argument_out_of_domain);
161 const auto &E = Expressions[C.getExpressionID()];
162 ErrorOr<int64_t> LHS = evaluate(E.LHS);
165 ErrorOr<int64_t> RHS = evaluate(E.RHS);
168 return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
171 llvm_unreachable("Unhandled CounterKind");
174 void FunctionRecordIterator::skipOtherFiles() {
175 while (Current != Records.end() && !Filename.empty() &&
176 Filename != Current->Filenames[0])
178 if (Current == Records.end())
179 *this = FunctionRecordIterator();
182 /// Get the function name from the record, removing the filename prefix if
184 static StringRef getFuncNameWithoutPrefix(const CoverageMappingRecord &Record) {
185 StringRef FunctionName = Record.FunctionName;
186 if (Record.Filenames.empty())
188 StringRef Filename = sys::path::filename(Record.Filenames[0]);
189 if (FunctionName.startswith(Filename))
190 FunctionName = FunctionName.drop_front(Filename.size() + 1);
194 ErrorOr<std::unique_ptr<CoverageMapping>>
195 CoverageMapping::load(CoverageMappingReader &CoverageReader,
196 IndexedInstrProfReader &ProfileReader) {
197 auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
199 std::vector<uint64_t> Counts;
200 for (const auto &Record : CoverageReader) {
201 CounterMappingContext Ctx(Record.Expressions);
204 if (std::error_code EC = ProfileReader.getFunctionCounts(
205 Record.FunctionName, Record.FunctionHash, Counts)) {
206 if (EC == instrprof_error::hash_mismatch) {
207 Coverage->MismatchedFunctionCount++;
209 } else if (EC != instrprof_error::unknown_function)
212 Ctx.setCounts(Counts);
214 assert(!Record.MappingRegions.empty() && "Function has no regions");
216 FunctionRecord Function(getFuncNameWithoutPrefix(Record), Record.Filenames);
217 for (const auto &Region : Record.MappingRegions) {
218 ErrorOr<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
221 Function.pushRegion(Region, *ExecutionCount);
223 if (Function.CountedRegions.size() != Record.MappingRegions.size()) {
224 Coverage->MismatchedFunctionCount++;
228 Coverage->Functions.push_back(std::move(Function));
231 return std::move(Coverage);
234 ErrorOr<std::unique_ptr<CoverageMapping>>
235 CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename,
236 Triple::ArchType Arch) {
237 auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename);
238 if (std::error_code EC = CounterMappingBuff.getError())
240 auto CoverageReaderOrErr =
241 BinaryCoverageReader::create(CounterMappingBuff.get(), Arch);
242 if (std::error_code EC = CoverageReaderOrErr.getError())
244 auto CoverageReader = std::move(CoverageReaderOrErr.get());
245 auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
246 if (auto EC = ProfileReaderOrErr.getError())
248 auto ProfileReader = std::move(ProfileReaderOrErr.get());
249 return load(*CoverageReader, *ProfileReader);
253 /// \brief Distributes functions into instantiation sets.
255 /// An instantiation set is a collection of functions that have the same source
256 /// code, ie, template functions specializations.
257 class FunctionInstantiationSetCollector {
258 typedef DenseMap<std::pair<unsigned, unsigned>,
259 std::vector<const FunctionRecord *>> MapT;
260 MapT InstantiatedFunctions;
263 void insert(const FunctionRecord &Function, unsigned FileID) {
264 auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
265 while (I != E && I->FileID != FileID)
267 assert(I != E && "function does not cover the given file");
268 auto &Functions = InstantiatedFunctions[I->startLoc()];
269 Functions.push_back(&Function);
272 MapT::iterator begin() { return InstantiatedFunctions.begin(); }
274 MapT::iterator end() { return InstantiatedFunctions.end(); }
277 class SegmentBuilder {
278 std::vector<CoverageSegment> Segments;
279 SmallVector<const CountedRegion *, 8> ActiveRegions;
281 /// Start a segment with no count specified.
282 void startSegment(unsigned Line, unsigned Col) {
283 DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
284 Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
287 /// Start a segment with the given Region's count.
288 void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
289 const CountedRegion &Region) {
290 if (Segments.empty())
291 Segments.emplace_back(Line, Col, IsRegionEntry);
292 CoverageSegment S = Segments.back();
293 // Avoid creating empty regions.
294 if (S.Line != Line || S.Col != Col) {
295 Segments.emplace_back(Line, Col, IsRegionEntry);
298 DEBUG(dbgs() << "Segment at " << Line << ":" << Col);
299 // Set this region's count.
300 if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) {
301 DEBUG(dbgs() << " with count " << Region.ExecutionCount);
302 Segments.back().setCount(Region.ExecutionCount);
304 DEBUG(dbgs() << "\n");
307 /// Start a segment for the given region.
308 void startSegment(const CountedRegion &Region) {
309 startSegment(Region.LineStart, Region.ColumnStart, true, Region);
312 /// Pop the top region off of the active stack, starting a new segment with
313 /// the containing Region's count.
315 const CountedRegion *Active = ActiveRegions.back();
316 unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
317 ActiveRegions.pop_back();
318 if (ActiveRegions.empty())
319 startSegment(Line, Col);
321 startSegment(Line, Col, false, *ActiveRegions.back());
325 /// Build a list of CoverageSegments from a sorted list of Regions.
326 std::vector<CoverageSegment> buildSegments(ArrayRef<CountedRegion> Regions) {
327 const CountedRegion *PrevRegion = nullptr;
328 for (const auto &Region : Regions) {
329 // Pop any regions that end before this one starts.
330 while (!ActiveRegions.empty() &&
331 ActiveRegions.back()->endLoc() <= Region.startLoc())
333 if (PrevRegion && PrevRegion->startLoc() == Region.startLoc() &&
334 PrevRegion->endLoc() == Region.endLoc()) {
335 if (Region.Kind == coverage::CounterMappingRegion::CodeRegion)
336 Segments.back().addCount(Region.ExecutionCount);
338 // Add this region to the stack.
339 ActiveRegions.push_back(&Region);
340 startSegment(Region);
342 PrevRegion = &Region;
344 // Pop any regions that are left in the stack.
345 while (!ActiveRegions.empty())
352 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
353 std::vector<StringRef> Filenames;
354 for (const auto &Function : getCoveredFunctions())
355 Filenames.insert(Filenames.end(), Function.Filenames.begin(),
356 Function.Filenames.end());
357 std::sort(Filenames.begin(), Filenames.end());
358 auto Last = std::unique(Filenames.begin(), Filenames.end());
359 Filenames.erase(Last, Filenames.end());
363 static SmallBitVector gatherFileIDs(StringRef SourceFile,
364 const FunctionRecord &Function) {
365 SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
366 for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
367 if (SourceFile == Function.Filenames[I])
368 FilenameEquivalence[I] = true;
369 return FilenameEquivalence;
372 static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
373 const FunctionRecord &Function) {
374 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
375 SmallBitVector FilenameEquivalence = gatherFileIDs(SourceFile, Function);
376 for (const auto &CR : Function.CountedRegions)
377 if (CR.Kind == CounterMappingRegion::ExpansionRegion &&
378 FilenameEquivalence[CR.FileID])
379 IsNotExpandedFile[CR.ExpandedFileID] = false;
380 IsNotExpandedFile &= FilenameEquivalence;
381 int I = IsNotExpandedFile.find_first();
387 static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
388 SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
389 for (const auto &CR : Function.CountedRegions)
390 if (CR.Kind == CounterMappingRegion::ExpansionRegion)
391 IsNotExpandedFile[CR.ExpandedFileID] = false;
392 int I = IsNotExpandedFile.find_first();
398 /// Sort a nested sequence of regions from a single file.
399 template <class It> static void sortNestedRegions(It First, It Last) {
400 std::sort(First, Last,
401 [](const CountedRegion &LHS, const CountedRegion &RHS) {
402 if (LHS.startLoc() == RHS.startLoc())
403 // When LHS completely contains RHS, we sort LHS first.
404 return RHS.endLoc() < LHS.endLoc();
405 return LHS.startLoc() < RHS.startLoc();
409 static bool isExpansion(const CountedRegion &R, unsigned FileID) {
410 return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
413 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) {
414 CoverageData FileCoverage(Filename);
415 std::vector<coverage::CountedRegion> Regions;
417 for (const auto &Function : Functions) {
418 auto MainFileID = findMainViewFileID(Filename, Function);
421 auto FileIDs = gatherFileIDs(Filename, Function);
422 for (const auto &CR : Function.CountedRegions)
423 if (FileIDs.test(CR.FileID)) {
424 Regions.push_back(CR);
425 if (isExpansion(CR, *MainFileID))
426 FileCoverage.Expansions.emplace_back(CR, Function);
430 sortNestedRegions(Regions.begin(), Regions.end());
431 DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
432 FileCoverage.Segments = SegmentBuilder().buildSegments(Regions);
437 std::vector<const FunctionRecord *>
438 CoverageMapping::getInstantiations(StringRef Filename) {
439 FunctionInstantiationSetCollector InstantiationSetCollector;
440 for (const auto &Function : Functions) {
441 auto MainFileID = findMainViewFileID(Filename, Function);
444 InstantiationSetCollector.insert(Function, *MainFileID);
447 std::vector<const FunctionRecord *> Result;
448 for (const auto &InstantiationSet : InstantiationSetCollector) {
449 if (InstantiationSet.second.size() < 2)
451 Result.insert(Result.end(), InstantiationSet.second.begin(),
452 InstantiationSet.second.end());
458 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
459 auto MainFileID = findMainViewFileID(Function);
461 return CoverageData();
463 CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
464 std::vector<coverage::CountedRegion> Regions;
465 for (const auto &CR : Function.CountedRegions)
466 if (CR.FileID == *MainFileID) {
467 Regions.push_back(CR);
468 if (isExpansion(CR, *MainFileID))
469 FunctionCoverage.Expansions.emplace_back(CR, Function);
472 sortNestedRegions(Regions.begin(), Regions.end());
473 DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
474 FunctionCoverage.Segments = SegmentBuilder().buildSegments(Regions);
476 return FunctionCoverage;
480 CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) {
481 CoverageData ExpansionCoverage(
482 Expansion.Function.Filenames[Expansion.FileID]);
483 std::vector<coverage::CountedRegion> Regions;
484 for (const auto &CR : Expansion.Function.CountedRegions)
485 if (CR.FileID == Expansion.FileID) {
486 Regions.push_back(CR);
487 if (isExpansion(CR, Expansion.FileID))
488 ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
491 sortNestedRegions(Regions.begin(), Regions.end());
492 DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
494 ExpansionCoverage.Segments = SegmentBuilder().buildSegments(Regions);
496 return ExpansionCoverage;