CoverageMapping.cpp revision 304240 
1//=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains support for clang's and llvm's instrumentation based
11// code coverage.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ProfileData/Coverage/CoverageMapping.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/Optional.h"
18#include "llvm/ADT/SmallBitVector.h"
19#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
20#include "llvm/ProfileData/InstrProfReader.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/Errc.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/ManagedStatic.h"
25#include "llvm/Support/Path.h"
26#include "llvm/Support/raw_ostream.h"
27
28using namespace llvm;
29using namespace coverage;
30
31#define DEBUG_TYPE "coverage-mapping"
32
33Counter CounterExpressionBuilder::get(const CounterExpression &E) {
34  auto It = ExpressionIndices.find(E);
35  if (It != ExpressionIndices.end())
36    return Counter::getExpression(It->second);
37  unsigned I = Expressions.size();
38  Expressions.push_back(E);
39  ExpressionIndices[E] = I;
40  return Counter::getExpression(I);
41}
42
43void CounterExpressionBuilder::extractTerms(
44    Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
45  switch (C.getKind()) {
46  case Counter::Zero:
47    break;
48  case Counter::CounterValueReference:
49    Terms.push_back(std::make_pair(C.getCounterID(), Sign));
50    break;
51  case Counter::Expression:
52    const auto &E = Expressions[C.getExpressionID()];
53    extractTerms(E.LHS, Sign, Terms);
54    extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
55                 Terms);
56    break;
57  }
58}
59
60Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
61  // Gather constant terms.
62  llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
63  extractTerms(ExpressionTree, +1, Terms);
64
65  // If there are no terms, this is just a zero. The algorithm below assumes at
66  // least one term.
67  if (Terms.size() == 0)
68    return Counter::getZero();
69
70  // Group the terms by counter ID.
71  std::sort(Terms.begin(), Terms.end(),
72            [](const std::pair<unsigned, int> &LHS,
73               const std::pair<unsigned, int> &RHS) {
74    return LHS.first < RHS.first;
75  });
76
77  // Combine terms by counter ID to eliminate counters that sum to zero.
78  auto Prev = Terms.begin();
79  for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
80    if (I->first == Prev->first) {
81      Prev->second += I->second;
82      continue;
83    }
84    ++Prev;
85    *Prev = *I;
86  }
87  Terms.erase(++Prev, Terms.end());
88
89  Counter C;
90  // Create additions. We do this before subtractions to avoid constructs like
91  // ((0 - X) + Y), as opposed to (Y - X).
92  for (auto Term : Terms) {
93    if (Term.second <= 0)
94      continue;
95    for (int I = 0; I < Term.second; ++I)
96      if (C.isZero())
97        C = Counter::getCounter(Term.first);
98      else
99        C = get(CounterExpression(CounterExpression::Add, C,
100                                  Counter::getCounter(Term.first)));
101  }
102
103  // Create subtractions.
104  for (auto Term : Terms) {
105    if (Term.second >= 0)
106      continue;
107    for (int I = 0; I < -Term.second; ++I)
108      C = get(CounterExpression(CounterExpression::Subtract, C,
109                                Counter::getCounter(Term.first)));
110  }
111  return C;
112}
113
114Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
115  return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
116}
117
118Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
119  return simplify(
120      get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
121}
122
123void CounterMappingContext::dump(const Counter &C,
124                                 llvm::raw_ostream &OS) const {
125  switch (C.getKind()) {
126  case Counter::Zero:
127    OS << '0';
128    return;
129  case Counter::CounterValueReference:
130    OS << '#' << C.getCounterID();
131    break;
132  case Counter::Expression: {
133    if (C.getExpressionID() >= Expressions.size())
134      return;
135    const auto &E = Expressions[C.getExpressionID()];
136    OS << '(';
137    dump(E.LHS, OS);
138    OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
139    dump(E.RHS, OS);
140    OS << ')';
141    break;
142  }
143  }
144  if (CounterValues.empty())
145    return;
146  Expected<int64_t> Value = evaluate(C);
147  if (auto E = Value.takeError()) {
148    llvm::consumeError(std::move(E));
149    return;
150  }
151  OS << '[' << *Value << ']';
152}
153
154Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
155  switch (C.getKind()) {
156  case Counter::Zero:
157    return 0;
158  case Counter::CounterValueReference:
159    if (C.getCounterID() >= CounterValues.size())
160      return errorCodeToError(errc::argument_out_of_domain);
161    return CounterValues[C.getCounterID()];
162  case Counter::Expression: {
163    if (C.getExpressionID() >= Expressions.size())
164      return errorCodeToError(errc::argument_out_of_domain);
165    const auto &E = Expressions[C.getExpressionID()];
166    Expected<int64_t> LHS = evaluate(E.LHS);
167    if (!LHS)
168      return LHS;
169    Expected<int64_t> RHS = evaluate(E.RHS);
170    if (!RHS)
171      return RHS;
172    return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
173  }
174  }
175  llvm_unreachable("Unhandled CounterKind");
176}
177
178void FunctionRecordIterator::skipOtherFiles() {
179  while (Current != Records.end() && !Filename.empty() &&
180         Filename != Current->Filenames[0])
181    ++Current;
182  if (Current == Records.end())
183    *this = FunctionRecordIterator();
184}
185
186Expected<std::unique_ptr<CoverageMapping>>
187CoverageMapping::load(CoverageMappingReader &CoverageReader,
188                      IndexedInstrProfReader &ProfileReader) {
189  auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
190
191  std::vector<uint64_t> Counts;
192  for (const auto &Record : CoverageReader) {
193    CounterMappingContext Ctx(Record.Expressions);
194
195    Counts.clear();
196    if (Error E = ProfileReader.getFunctionCounts(
197            Record.FunctionName, Record.FunctionHash, Counts)) {
198      instrprof_error IPE = InstrProfError::take(std::move(E));
199      if (IPE == instrprof_error::hash_mismatch) {
200        Coverage->MismatchedFunctionCount++;
201        continue;
202      } else if (IPE != instrprof_error::unknown_function)
203        return make_error<InstrProfError>(IPE);
204      Counts.assign(Record.MappingRegions.size(), 0);
205    }
206    Ctx.setCounts(Counts);
207
208    assert(!Record.MappingRegions.empty() && "Function has no regions");
209
210    StringRef OrigFuncName = Record.FunctionName;
211    if (Record.Filenames.empty())
212      OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
213    else
214      OrigFuncName =
215          getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
216    FunctionRecord Function(OrigFuncName, Record.Filenames);
217    for (const auto &Region : Record.MappingRegions) {
218      Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
219      if (auto E = ExecutionCount.takeError()) {
220        llvm::consumeError(std::move(E));
221        break;
222      }
223      Function.pushRegion(Region, *ExecutionCount);
224    }
225    if (Function.CountedRegions.size() != Record.MappingRegions.size()) {
226      Coverage->MismatchedFunctionCount++;
227      continue;
228    }
229
230    Coverage->Functions.push_back(std::move(Function));
231  }
232
233  return std::move(Coverage);
234}
235
236Expected<std::unique_ptr<CoverageMapping>>
237CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename,
238                      StringRef Arch) {
239  auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename);
240  if (std::error_code EC = CounterMappingBuff.getError())
241    return errorCodeToError(EC);
242  auto CoverageReaderOrErr =
243      BinaryCoverageReader::create(CounterMappingBuff.get(), Arch);
244  if (Error E = CoverageReaderOrErr.takeError())
245    return std::move(E);
246  auto CoverageReader = std::move(CoverageReaderOrErr.get());
247  auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
248  if (Error E = ProfileReaderOrErr.takeError())
249    return std::move(E);
250  auto ProfileReader = std::move(ProfileReaderOrErr.get());
251  return load(*CoverageReader, *ProfileReader);
252}
253
254namespace {
255/// \brief Distributes functions into instantiation sets.
256///
257/// An instantiation set is a collection of functions that have the same source
258/// code, ie, template functions specializations.
259class FunctionInstantiationSetCollector {
260  typedef DenseMap<std::pair<unsigned, unsigned>,
261                   std::vector<const FunctionRecord *>> MapT;
262  MapT InstantiatedFunctions;
263
264public:
265  void insert(const FunctionRecord &Function, unsigned FileID) {
266    auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
267    while (I != E && I->FileID != FileID)
268      ++I;
269    assert(I != E && "function does not cover the given file");
270    auto &Functions = InstantiatedFunctions[I->startLoc()];
271    Functions.push_back(&Function);
272  }
273
274  MapT::iterator begin() { return InstantiatedFunctions.begin(); }
275
276  MapT::iterator end() { return InstantiatedFunctions.end(); }
277};
278
279class SegmentBuilder {
280  std::vector<CoverageSegment> &Segments;
281  SmallVector<const CountedRegion *, 8> ActiveRegions;
282
283  SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
284
285  /// Start a segment with no count specified.
286  void startSegment(unsigned Line, unsigned Col) {
287    DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
288    Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
289  }
290
291  /// Start a segment with the given Region's count.
292  void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
293                    const CountedRegion &Region) {
294    // Avoid creating empty regions.
295    if (!Segments.empty() && Segments.back().Line == Line &&
296        Segments.back().Col == Col)
297      Segments.pop_back();
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.emplace_back(Line, Col, Region.ExecutionCount, IsRegionEntry);
303    } else
304      Segments.emplace_back(Line, Col, IsRegionEntry);
305    DEBUG(dbgs() << "\n");
306  }
307
308  /// Start a segment for the given region.
309  void startSegment(const CountedRegion &Region) {
310    startSegment(Region.LineStart, Region.ColumnStart, true, Region);
311  }
312
313  /// Pop the top region off of the active stack, starting a new segment with
314  /// the containing Region's count.
315  void popRegion() {
316    const CountedRegion *Active = ActiveRegions.back();
317    unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
318    ActiveRegions.pop_back();
319    if (ActiveRegions.empty())
320      startSegment(Line, Col);
321    else
322      startSegment(Line, Col, false, *ActiveRegions.back());
323  }
324
325  void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
326    for (const auto &Region : Regions) {
327      // Pop any regions that end before this one starts.
328      while (!ActiveRegions.empty() &&
329             ActiveRegions.back()->endLoc() <= Region.startLoc())
330        popRegion();
331      // Add this region to the stack.
332      ActiveRegions.push_back(&Region);
333      startSegment(Region);
334    }
335    // Pop any regions that are left in the stack.
336    while (!ActiveRegions.empty())
337      popRegion();
338  }
339
340  /// Sort a nested sequence of regions from a single file.
341  static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
342    std::sort(Regions.begin(), Regions.end(), [](const CountedRegion &LHS,
343                                                 const CountedRegion &RHS) {
344      if (LHS.startLoc() != RHS.startLoc())
345        return LHS.startLoc() < RHS.startLoc();
346      if (LHS.endLoc() != RHS.endLoc())
347        // When LHS completely contains RHS, we sort LHS first.
348        return RHS.endLoc() < LHS.endLoc();
349      // If LHS and RHS cover the same area, we need to sort them according
350      // to their kinds so that the most suitable region will become "active"
351      // in combineRegions(). Because we accumulate counter values only from
352      // regions of the same kind as the first region of the area, prefer
353      // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
354      static_assert(coverage::CounterMappingRegion::CodeRegion <
355                            coverage::CounterMappingRegion::ExpansionRegion &&
356                        coverage::CounterMappingRegion::ExpansionRegion <
357                            coverage::CounterMappingRegion::SkippedRegion,
358                    "Unexpected order of region kind values");
359      return LHS.Kind < RHS.Kind;
360    });
361  }
362
363  /// Combine counts of regions which cover the same area.
364  static ArrayRef<CountedRegion>
365  combineRegions(MutableArrayRef<CountedRegion> Regions) {
366    if (Regions.empty())
367      return Regions;
368    auto Active = Regions.begin();
369    auto End = Regions.end();
370    for (auto I = Regions.begin() + 1; I != End; ++I) {
371      if (Active->startLoc() != I->startLoc() ||
372          Active->endLoc() != I->endLoc()) {
373        // Shift to the next region.
374        ++Active;
375        if (Active != I)
376          *Active = *I;
377        continue;
378      }
379      // Merge duplicate region.
380      // If CodeRegions and ExpansionRegions cover the same area, it's probably
381      // a macro which is fully expanded to another macro. In that case, we need
382      // to accumulate counts only from CodeRegions, or else the area will be
383      // counted twice.
384      // On the other hand, a macro may have a nested macro in its body. If the
385      // outer macro is used several times, the ExpansionRegion for the nested
386      // macro will also be added several times. These ExpansionRegions cover
387      // the same source locations and have to be combined to reach the correct
388      // value for that area.
389      // We add counts of the regions of the same kind as the active region
390      // to handle the both situations.
391      if (I->Kind == Active->Kind)
392        Active->ExecutionCount += I->ExecutionCount;
393    }
394    return Regions.drop_back(std::distance(++Active, End));
395  }
396
397public:
398  /// Build a list of CoverageSegments from a list of Regions.
399  static std::vector<CoverageSegment>
400  buildSegments(MutableArrayRef<CountedRegion> Regions) {
401    std::vector<CoverageSegment> Segments;
402    SegmentBuilder Builder(Segments);
403
404    sortNestedRegions(Regions);
405    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
406
407    Builder.buildSegmentsImpl(CombinedRegions);
408    return Segments;
409  }
410};
411}
412
413std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
414  std::vector<StringRef> Filenames;
415  for (const auto &Function : getCoveredFunctions())
416    Filenames.insert(Filenames.end(), Function.Filenames.begin(),
417                     Function.Filenames.end());
418  std::sort(Filenames.begin(), Filenames.end());
419  auto Last = std::unique(Filenames.begin(), Filenames.end());
420  Filenames.erase(Last, Filenames.end());
421  return Filenames;
422}
423
424static SmallBitVector gatherFileIDs(StringRef SourceFile,
425                                    const FunctionRecord &Function) {
426  SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
427  for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
428    if (SourceFile == Function.Filenames[I])
429      FilenameEquivalence[I] = true;
430  return FilenameEquivalence;
431}
432
433/// Return the ID of the file where the definition of the function is located.
434static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
435  SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
436  for (const auto &CR : Function.CountedRegions)
437    if (CR.Kind == CounterMappingRegion::ExpansionRegion)
438      IsNotExpandedFile[CR.ExpandedFileID] = false;
439  int I = IsNotExpandedFile.find_first();
440  if (I == -1)
441    return None;
442  return I;
443}
444
445/// Check if SourceFile is the file that contains the definition of
446/// the Function. Return the ID of the file in that case or None otherwise.
447static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
448                                             const FunctionRecord &Function) {
449  Optional<unsigned> I = findMainViewFileID(Function);
450  if (I && SourceFile == Function.Filenames[*I])
451    return I;
452  return None;
453}
454
455static bool isExpansion(const CountedRegion &R, unsigned FileID) {
456  return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
457}
458
459CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
460  CoverageData FileCoverage(Filename);
461  std::vector<coverage::CountedRegion> Regions;
462
463  for (const auto &Function : Functions) {
464    auto MainFileID = findMainViewFileID(Filename, Function);
465    auto FileIDs = gatherFileIDs(Filename, Function);
466    for (const auto &CR : Function.CountedRegions)
467      if (FileIDs.test(CR.FileID)) {
468        Regions.push_back(CR);
469        if (MainFileID && isExpansion(CR, *MainFileID))
470          FileCoverage.Expansions.emplace_back(CR, Function);
471      }
472  }
473
474  DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
475  FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
476
477  return FileCoverage;
478}
479
480std::vector<const FunctionRecord *>
481CoverageMapping::getInstantiations(StringRef Filename) const {
482  FunctionInstantiationSetCollector InstantiationSetCollector;
483  for (const auto &Function : Functions) {
484    auto MainFileID = findMainViewFileID(Filename, Function);
485    if (!MainFileID)
486      continue;
487    InstantiationSetCollector.insert(Function, *MainFileID);
488  }
489
490  std::vector<const FunctionRecord *> Result;
491  for (const auto &InstantiationSet : InstantiationSetCollector) {
492    if (InstantiationSet.second.size() < 2)
493      continue;
494    Result.insert(Result.end(), InstantiationSet.second.begin(),
495                  InstantiationSet.second.end());
496  }
497  return Result;
498}
499
500CoverageData
501CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
502  auto MainFileID = findMainViewFileID(Function);
503  if (!MainFileID)
504    return CoverageData();
505
506  CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
507  std::vector<coverage::CountedRegion> Regions;
508  for (const auto &CR : Function.CountedRegions)
509    if (CR.FileID == *MainFileID) {
510      Regions.push_back(CR);
511      if (isExpansion(CR, *MainFileID))
512        FunctionCoverage.Expansions.emplace_back(CR, Function);
513    }
514
515  DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
516  FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
517
518  return FunctionCoverage;
519}
520
521CoverageData CoverageMapping::getCoverageForExpansion(
522    const ExpansionRecord &Expansion) const {
523  CoverageData ExpansionCoverage(
524      Expansion.Function.Filenames[Expansion.FileID]);
525  std::vector<coverage::CountedRegion> Regions;
526  for (const auto &CR : Expansion.Function.CountedRegions)
527    if (CR.FileID == Expansion.FileID) {
528      Regions.push_back(CR);
529      if (isExpansion(CR, Expansion.FileID))
530        ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
531    }
532
533  DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
534               << "\n");
535  ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
536
537  return ExpansionCoverage;
538}
539
540namespace {
541std::string getCoverageMapErrString(coveragemap_error Err) {
542  switch (Err) {
543  case coveragemap_error::success:
544    return "Success";
545  case coveragemap_error::eof:
546    return "End of File";
547  case coveragemap_error::no_data_found:
548    return "No coverage data found";
549  case coveragemap_error::unsupported_version:
550    return "Unsupported coverage format version";
551  case coveragemap_error::truncated:
552    return "Truncated coverage data";
553  case coveragemap_error::malformed:
554    return "Malformed coverage data";
555  }
556  llvm_unreachable("A value of coveragemap_error has no message.");
557}
558
559// FIXME: This class is only here to support the transition to llvm::Error. It
560// will be removed once this transition is complete. Clients should prefer to
561// deal with the Error value directly, rather than converting to error_code.
562class CoverageMappingErrorCategoryType : public std::error_category {
563  const char *name() const LLVM_NOEXCEPT override { return "llvm.coveragemap"; }
564  std::string message(int IE) const override {
565    return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
566  }
567};
568} // end anonymous namespace
569
570std::string CoverageMapError::message() const {
571  return getCoverageMapErrString(Err);
572}
573
574static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;
575
576const std::error_category &llvm::coverage::coveragemap_category() {
577  return *ErrorCategory;
578}
579
580char CoverageMapError::ID = 0;
581