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

Generated by: LCOV version 1.13