LCOV - code coverage report
Current view: top level - lib/ProfileData/Coverage - CoverageMapping.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 290 315 92.1 %
Date: 2018-02-21 17:27:13 Functions: 30 35 85.7 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13