Home | History | Annotate | Download | only in ProfileData 
      1 //=-- CoverageMapping.cpp - Code coverage mapping support ---------*- C++ -*-=//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file contains support for clang's and llvm's instrumentation based
     11 // code coverage.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "llvm/ProfileData/CoverageMapping.h"
     16 #include "llvm/ADT/DenseMap.h"
     17 #include "llvm/ADT/Optional.h"
     18 #include "llvm/ADT/SmallBitVector.h"
     19 #include "llvm/ProfileData/CoverageMappingReader.h"
     20 #include "llvm/ProfileData/InstrProfReader.h"
     21 #include "llvm/Support/Debug.h"
     22 #include "llvm/Support/ErrorHandling.h"
     23 #include "llvm/Support/raw_ostream.h"
     24 
     25 using namespace llvm;
     26 using namespace coverage;
     27 
     28 #define DEBUG_TYPE "coverage-mapping"
     29 
     30 Counter CounterExpressionBuilder::get(const CounterExpression &E) {
     31   auto It = ExpressionIndices.find(E);
     32   if (It != ExpressionIndices.end())
     33     return Counter::getExpression(It->second);
     34   unsigned I = Expressions.size();
     35   Expressions.push_back(E);
     36   ExpressionIndices[E] = I;
     37   return Counter::getExpression(I);
     38 }
     39 
     40 void CounterExpressionBuilder::extractTerms(
     41     Counter C, int Sign, SmallVectorImpl<std::pair<unsigned, int>> &Terms) {
     42   switch (C.getKind()) {
     43   case Counter::Zero:
     44     break;
     45   case Counter::CounterValueReference:
     46     Terms.push_back(std::make_pair(C.getCounterID(), Sign));
     47     break;
     48   case Counter::Expression:
     49     const auto &E = Expressions[C.getExpressionID()];
     50     extractTerms(E.LHS, Sign, Terms);
     51     extractTerms(E.RHS, E.Kind == CounterExpression::Subtract ? -Sign : Sign,
     52                  Terms);
     53     break;
     54   }
     55 }
     56 
     57 Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
     58   // Gather constant terms.
     59   llvm::SmallVector<std::pair<unsigned, int>, 32> Terms;
     60   extractTerms(ExpressionTree, +1, Terms);
     61 
     62   // If there are no terms, this is just a zero. The algorithm below assumes at
     63   // least one term.
     64   if (Terms.size() == 0)
     65     return Counter::getZero();
     66 
     67   // Group the terms by counter ID.
     68   std::sort(Terms.begin(), Terms.end(),
     69             [](const std::pair<unsigned, int> &LHS,
     70                const std::pair<unsigned, int> &RHS) {
     71     return LHS.first < RHS.first;
     72   });
     73 
     74   // Combine terms by counter ID to eliminate counters that sum to zero.
     75   auto Prev = Terms.begin();
     76   for (auto I = Prev + 1, E = Terms.end(); I != E; ++I) {
     77     if (I->first == Prev->first) {
     78       Prev->second += I->second;
     79       continue;
     80     }
     81     ++Prev;
     82     *Prev = *I;
     83   }
     84   Terms.erase(++Prev, Terms.end());
     85 
     86   Counter C;
     87   // Create additions. We do this before subtractions to avoid constructs like
     88   // ((0 - X) + Y), as opposed to (Y - X).
     89   for (auto Term : Terms) {
     90     if (Term.second <= 0)
     91       continue;
     92     for (int I = 0; I < Term.second; ++I)
     93       if (C.isZero())
     94         C = Counter::getCounter(Term.first);
     95       else
     96         C = get(CounterExpression(CounterExpression::Add, C,
     97                                   Counter::getCounter(Term.first)));
     98   }
     99 
    100   // Create subtractions.
    101   for (auto Term : Terms) {
    102     if (Term.second >= 0)
    103       continue;
    104     for (int I = 0; I < -Term.second; ++I)
    105       C = get(CounterExpression(CounterExpression::Subtract, C,
    106                                 Counter::getCounter(Term.first)));
    107   }
    108   return C;
    109 }
    110 
    111 Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
    112   return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
    113 }
    114 
    115 Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
    116   return simplify(
    117       get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
    118 }
    119 
    120 void CounterMappingContext::dump(const Counter &C,
    121                                  llvm::raw_ostream &OS) const {
    122   switch (C.getKind()) {
    123   case Counter::Zero:
    124     OS << '0';
    125     return;
    126   case Counter::CounterValueReference:
    127     OS << '#' << C.getCounterID();
    128     break;
    129   case Counter::Expression: {
    130     if (C.getExpressionID() >= Expressions.size())
    131       return;
    132     const auto &E = Expressions[C.getExpressionID()];
    133     OS << '(';
    134     dump(E.LHS, OS);
    135     OS << (E.Kind == CounterExpression::Subtract ? " - " : " + ");
    136     dump(E.RHS, OS);
    137     OS << ')';
    138     break;
    139   }
    140   }
    141   if (CounterValues.empty())
    142     return;
    143   ErrorOr<int64_t> Value = evaluate(C);
    144   if (!Value)
    145     return;
    146   OS << '[' << *Value << ']';
    147 }
    148 
    149 ErrorOr<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
    150   switch (C.getKind()) {
    151   case Counter::Zero:
    152     return 0;
    153   case Counter::CounterValueReference:
    154     if (C.getCounterID() >= CounterValues.size())
    155       return std::make_error_code(std::errc::argument_out_of_domain);
    156     return CounterValues[C.getCounterID()];
    157   case Counter::Expression: {
    158     if (C.getExpressionID() >= Expressions.size())
    159       return std::make_error_code(std::errc::argument_out_of_domain);
    160     const auto &E = Expressions[C.getExpressionID()];
    161     ErrorOr<int64_t> LHS = evaluate(E.LHS);
    162     if (!LHS)
    163       return LHS;
    164     ErrorOr<int64_t> RHS = evaluate(E.RHS);
    165     if (!RHS)
    166       return RHS;
    167     return E.Kind == CounterExpression::Subtract ? *LHS - *RHS : *LHS + *RHS;
    168   }
    169   }
    170   llvm_unreachable("Unhandled CounterKind");
    171 }
    172 
    173 void FunctionRecordIterator::skipOtherFiles() {
    174   while (Current != Records.end() && !Filename.empty() &&
    175          Filename != Current->Filenames[0])
    176     ++Current;
    177   if (Current == Records.end())
    178     *this = FunctionRecordIterator();
    179 }
    180 
    181 ErrorOr<std::unique_ptr<CoverageMapping>>
    182 CoverageMapping::load(CoverageMappingReader &CoverageReader,
    183                       IndexedInstrProfReader &ProfileReader) {
    184   auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
    185 
    186   std::vector<uint64_t> Counts;
    187   for (const auto &Record : CoverageReader) {
    188     CounterMappingContext Ctx(Record.Expressions);
    189 
    190     Counts.clear();
    191     if (std::error_code EC = ProfileReader.getFunctionCounts(
    192             Record.FunctionName, Record.FunctionHash, Counts)) {
    193       if (EC == instrprof_error::hash_mismatch) {
    194         Coverage->MismatchedFunctionCount++;
    195         continue;
    196       } else if (EC != instrprof_error::unknown_function)
    197         return EC;
    198     } else
    199       Ctx.setCounts(Counts);
    200 
    201     assert(!Record.MappingRegions.empty() && "Function has no regions");
    202     FunctionRecord Function(Record.FunctionName, Record.Filenames);
    203     for (const auto &Region : Record.MappingRegions) {
    204       ErrorOr<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
    205       if (!ExecutionCount)
    206         break;
    207       Function.pushRegion(Region, *ExecutionCount);
    208     }
    209     if (Function.CountedRegions.size() != Record.MappingRegions.size()) {
    210       Coverage->MismatchedFunctionCount++;
    211       continue;
    212     }
    213 
    214     Coverage->Functions.push_back(std::move(Function));
    215   }
    216 
    217   return std::move(Coverage);
    218 }
    219 
    220 ErrorOr<std::unique_ptr<CoverageMapping>>
    221 CoverageMapping::load(StringRef ObjectFilename, StringRef ProfileFilename,
    222                       Triple::ArchType Arch) {
    223   auto CounterMappingBuff = MemoryBuffer::getFileOrSTDIN(ObjectFilename);
    224   if (std::error_code EC = CounterMappingBuff.getError())
    225     return EC;
    226   auto CoverageReaderOrErr =
    227       BinaryCoverageReader::create(CounterMappingBuff.get(), Arch);
    228   if (std::error_code EC = CoverageReaderOrErr.getError())
    229     return EC;
    230   auto CoverageReader = std::move(CoverageReaderOrErr.get());
    231   auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
    232   if (auto EC = ProfileReaderOrErr.getError())
    233     return EC;
    234   auto ProfileReader = std::move(ProfileReaderOrErr.get());
    235   return load(*CoverageReader, *ProfileReader);
    236 }
    237 
    238 namespace {
    239 /// \brief Distributes functions into instantiation sets.
    240 ///
    241 /// An instantiation set is a collection of functions that have the same source
    242 /// code, ie, template functions specializations.
    243 class FunctionInstantiationSetCollector {
    244   typedef DenseMap<std::pair<unsigned, unsigned>,
    245                    std::vector<const FunctionRecord *>> MapT;
    246   MapT InstantiatedFunctions;
    247 
    248 public:
    249   void insert(const FunctionRecord &Function, unsigned FileID) {
    250     auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
    251     while (I != E && I->FileID != FileID)
    252       ++I;
    253     assert(I != E && "function does not cover the given file");
    254     auto &Functions = InstantiatedFunctions[I->startLoc()];
    255     Functions.push_back(&Function);
    256   }
    257 
    258   MapT::iterator begin() { return InstantiatedFunctions.begin(); }
    259 
    260   MapT::iterator end() { return InstantiatedFunctions.end(); }
    261 };
    262 
    263 class SegmentBuilder {
    264   std::vector<CoverageSegment> Segments;
    265   SmallVector<const CountedRegion *, 8> ActiveRegions;
    266 
    267   /// Start a segment with no count specified.
    268   void startSegment(unsigned Line, unsigned Col) {
    269     DEBUG(dbgs() << "Top level segment at " << Line << ":" << Col << "\n");
    270     Segments.emplace_back(Line, Col, /*IsRegionEntry=*/false);
    271   }
    272 
    273   /// Start a segment with the given Region's count.
    274   void startSegment(unsigned Line, unsigned Col, bool IsRegionEntry,
    275                     const CountedRegion &Region) {
    276     if (Segments.empty())
    277       Segments.emplace_back(Line, Col, IsRegionEntry);
    278     CoverageSegment S = Segments.back();
    279     // Avoid creating empty regions.
    280     if (S.Line != Line || S.Col != Col) {
    281       Segments.emplace_back(Line, Col, IsRegionEntry);
    282       S = Segments.back();
    283     }
    284     DEBUG(dbgs() << "Segment at " << Line << ":" << Col);
    285     // Set this region's count.
    286     if (Region.Kind != coverage::CounterMappingRegion::SkippedRegion) {
    287       DEBUG(dbgs() << " with count " << Region.ExecutionCount);
    288       Segments.back().setCount(Region.ExecutionCount);
    289     }
    290     DEBUG(dbgs() << "\n");
    291   }
    292 
    293   /// Start a segment for the given region.
    294   void startSegment(const CountedRegion &Region) {
    295     startSegment(Region.LineStart, Region.ColumnStart, true, Region);
    296   }
    297 
    298   /// Pop the top region off of the active stack, starting a new segment with
    299   /// the containing Region's count.
    300   void popRegion() {
    301     const CountedRegion *Active = ActiveRegions.back();
    302     unsigned Line = Active->LineEnd, Col = Active->ColumnEnd;
    303     ActiveRegions.pop_back();
    304     if (ActiveRegions.empty())
    305       startSegment(Line, Col);
    306     else
    307       startSegment(Line, Col, false, *ActiveRegions.back());
    308   }
    309 
    310 public:
    311   /// Build a list of CoverageSegments from a sorted list of Regions.
    312   std::vector<CoverageSegment> buildSegments(ArrayRef<CountedRegion> Regions) {
    313     const CountedRegion *PrevRegion = nullptr;
    314     for (const auto &Region : Regions) {
    315       // Pop any regions that end before this one starts.
    316       while (!ActiveRegions.empty() &&
    317              ActiveRegions.back()->endLoc() <= Region.startLoc())
    318         popRegion();
    319       if (PrevRegion && PrevRegion->startLoc() == Region.startLoc() &&
    320           PrevRegion->endLoc() == Region.endLoc()) {
    321         if (Region.Kind == coverage::CounterMappingRegion::CodeRegion)
    322           Segments.back().addCount(Region.ExecutionCount);
    323       } else {
    324         // Add this region to the stack.
    325         ActiveRegions.push_back(&Region);
    326         startSegment(Region);
    327       }
    328       PrevRegion = &Region;
    329     }
    330     // Pop any regions that are left in the stack.
    331     while (!ActiveRegions.empty())
    332       popRegion();
    333     return Segments;
    334   }
    335 };
    336 }
    337 
    338 std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
    339   std::vector<StringRef> Filenames;
    340   for (const auto &Function : getCoveredFunctions())
    341     Filenames.insert(Filenames.end(), Function.Filenames.begin(),
    342                      Function.Filenames.end());
    343   std::sort(Filenames.begin(), Filenames.end());
    344   auto Last = std::unique(Filenames.begin(), Filenames.end());
    345   Filenames.erase(Last, Filenames.end());
    346   return Filenames;
    347 }
    348 
    349 static SmallBitVector gatherFileIDs(StringRef SourceFile,
    350                                     const FunctionRecord &Function) {
    351   SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
    352   for (unsigned I = 0, E = Function.Filenames.size(); I < E; ++I)
    353     if (SourceFile == Function.Filenames[I])
    354       FilenameEquivalence[I] = true;
    355   return FilenameEquivalence;
    356 }
    357 
    358 static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
    359                                              const FunctionRecord &Function) {
    360   SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
    361   SmallBitVector FilenameEquivalence = gatherFileIDs(SourceFile, Function);
    362   for (const auto &CR : Function.CountedRegions)
    363     if (CR.Kind == CounterMappingRegion::ExpansionRegion &&
    364         FilenameEquivalence[CR.FileID])
    365       IsNotExpandedFile[CR.ExpandedFileID] = false;
    366   IsNotExpandedFile &= FilenameEquivalence;
    367   int I = IsNotExpandedFile.find_first();
    368   if (I == -1)
    369     return None;
    370   return I;
    371 }
    372 
    373 static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
    374   SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
    375   for (const auto &CR : Function.CountedRegions)
    376     if (CR.Kind == CounterMappingRegion::ExpansionRegion)
    377       IsNotExpandedFile[CR.ExpandedFileID] = false;
    378   int I = IsNotExpandedFile.find_first();
    379   if (I == -1)
    380     return None;
    381   return I;
    382 }
    383 
    384 /// Sort a nested sequence of regions from a single file.
    385 template <class It> static void sortNestedRegions(It First, It Last) {
    386   std::sort(First, Last,
    387             [](const CountedRegion &LHS, const CountedRegion &RHS) {
    388     if (LHS.startLoc() == RHS.startLoc())
    389       // When LHS completely contains RHS, we sort LHS first.
    390       return RHS.endLoc() < LHS.endLoc();
    391     return LHS.startLoc() < RHS.startLoc();
    392   });
    393 }
    394 
    395 static bool isExpansion(const CountedRegion &R, unsigned FileID) {
    396   return R.Kind == CounterMappingRegion::ExpansionRegion && R.FileID == FileID;
    397 }
    398 
    399 CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) {
    400   CoverageData FileCoverage(Filename);
    401   std::vector<coverage::CountedRegion> Regions;
    402 
    403   for (const auto &Function : Functions) {
    404     auto MainFileID = findMainViewFileID(Filename, Function);
    405     if (!MainFileID)
    406       continue;
    407     auto FileIDs = gatherFileIDs(Filename, Function);
    408     for (const auto &CR : Function.CountedRegions)
    409       if (FileIDs.test(CR.FileID)) {
    410         Regions.push_back(CR);
    411         if (isExpansion(CR, *MainFileID))
    412           FileCoverage.Expansions.emplace_back(CR, Function);
    413       }
    414   }
    415 
    416   sortNestedRegions(Regions.begin(), Regions.end());
    417   DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
    418   FileCoverage.Segments = SegmentBuilder().buildSegments(Regions);
    419 
    420   return FileCoverage;
    421 }
    422 
    423 std::vector<const FunctionRecord *>
    424 CoverageMapping::getInstantiations(StringRef Filename) {
    425   FunctionInstantiationSetCollector InstantiationSetCollector;
    426   for (const auto &Function : Functions) {
    427     auto MainFileID = findMainViewFileID(Filename, Function);
    428     if (!MainFileID)
    429       continue;
    430     InstantiationSetCollector.insert(Function, *MainFileID);
    431   }
    432 
    433   std::vector<const FunctionRecord *> Result;
    434   for (const auto &InstantiationSet : InstantiationSetCollector) {
    435     if (InstantiationSet.second.size() < 2)
    436       continue;
    437     Result.insert(Result.end(), InstantiationSet.second.begin(),
    438                   InstantiationSet.second.end());
    439   }
    440   return Result;
    441 }
    442 
    443 CoverageData
    444 CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) {
    445   auto MainFileID = findMainViewFileID(Function);
    446   if (!MainFileID)
    447     return CoverageData();
    448 
    449   CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
    450   std::vector<coverage::CountedRegion> Regions;
    451   for (const auto &CR : Function.CountedRegions)
    452     if (CR.FileID == *MainFileID) {
    453       Regions.push_back(CR);
    454       if (isExpansion(CR, *MainFileID))
    455         FunctionCoverage.Expansions.emplace_back(CR, Function);
    456     }
    457 
    458   sortNestedRegions(Regions.begin(), Regions.end());
    459   DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n");
    460   FunctionCoverage.Segments = SegmentBuilder().buildSegments(Regions);
    461 
    462   return FunctionCoverage;
    463 }
    464 
    465 CoverageData
    466 CoverageMapping::getCoverageForExpansion(const ExpansionRecord &Expansion) {
    467   CoverageData ExpansionCoverage(
    468       Expansion.Function.Filenames[Expansion.FileID]);
    469   std::vector<coverage::CountedRegion> Regions;
    470   for (const auto &CR : Expansion.Function.CountedRegions)
    471     if (CR.FileID == Expansion.FileID) {
    472       Regions.push_back(CR);
    473       if (isExpansion(CR, Expansion.FileID))
    474         ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
    475     }
    476 
    477   sortNestedRegions(Regions.begin(), Regions.end());
    478   DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID
    479                << "\n");
    480   ExpansionCoverage.Segments = SegmentBuilder().buildSegments(Regions);
    481 
    482   return ExpansionCoverage;
    483 }
    484