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