Home | History | Annotate | Download | only in Coverage 
      1 //=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=//
      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 writing coverage mapping data for
     11 // instrumentation based coverage.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
     16 #include "llvm/Support/LEB128.h"
     17 
     18 using namespace llvm;
     19 using namespace coverage;
     20 
     21 void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
     22   encodeULEB128(Filenames.size(), OS);
     23   for (const auto &Filename : Filenames) {
     24     encodeULEB128(Filename.size(), OS);
     25     OS << Filename;
     26   }
     27 }
     28 
     29 namespace {
     30 /// \brief Gather only the expressions that are used by the mapping
     31 /// regions in this function.
     32 class CounterExpressionsMinimizer {
     33   ArrayRef<CounterExpression> Expressions;
     34   llvm::SmallVector<CounterExpression, 16> UsedExpressions;
     35   std::vector<unsigned> AdjustedExpressionIDs;
     36 
     37 public:
     38   void mark(Counter C) {
     39     if (!C.isExpression())
     40       return;
     41     unsigned ID = C.getExpressionID();
     42     AdjustedExpressionIDs[ID] = 1;
     43     mark(Expressions[ID].LHS);
     44     mark(Expressions[ID].RHS);
     45   }
     46 
     47   void gatherUsed(Counter C) {
     48     if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
     49       return;
     50     AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
     51     const auto &E = Expressions[C.getExpressionID()];
     52     UsedExpressions.push_back(E);
     53     gatherUsed(E.LHS);
     54     gatherUsed(E.RHS);
     55   }
     56 
     57   CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
     58                               ArrayRef<CounterMappingRegion> MappingRegions)
     59       : Expressions(Expressions) {
     60     AdjustedExpressionIDs.resize(Expressions.size(), 0);
     61     for (const auto &I : MappingRegions)
     62       mark(I.Count);
     63     for (const auto &I : MappingRegions)
     64       gatherUsed(I.Count);
     65   }
     66 
     67   ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
     68 
     69   /// \brief Adjust the given counter to correctly transition from the old
     70   /// expression ids to the new expression ids.
     71   Counter adjust(Counter C) const {
     72     if (C.isExpression())
     73       C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
     74     return C;
     75   }
     76 };
     77 }
     78 
     79 /// \brief Encode the counter.
     80 ///
     81 /// The encoding uses the following format:
     82 /// Low 2 bits - Tag:
     83 ///   Counter::Zero(0) - A Counter with kind Counter::Zero
     84 ///   Counter::CounterValueReference(1) - A counter with kind
     85 ///     Counter::CounterValueReference
     86 ///   Counter::Expression(2) + CounterExpression::Subtract(0) -
     87 ///     A counter with kind Counter::Expression and an expression
     88 ///     with kind CounterExpression::Subtract
     89 ///   Counter::Expression(2) + CounterExpression::Add(1) -
     90 ///     A counter with kind Counter::Expression and an expression
     91 ///     with kind CounterExpression::Add
     92 /// Remaining bits - Counter/Expression ID.
     93 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
     94                               Counter C) {
     95   unsigned Tag = unsigned(C.getKind());
     96   if (C.isExpression())
     97     Tag += Expressions[C.getExpressionID()].Kind;
     98   unsigned ID = C.getCounterID();
     99   assert(ID <=
    100          (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
    101   return Tag | (ID << Counter::EncodingTagBits);
    102 }
    103 
    104 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
    105                          raw_ostream &OS) {
    106   encodeULEB128(encodeCounter(Expressions, C), OS);
    107 }
    108 
    109 void CoverageMappingWriter::write(raw_ostream &OS) {
    110   // Sort the regions in an ascending order by the file id and the starting
    111   // location.
    112   std::stable_sort(MappingRegions.begin(), MappingRegions.end());
    113 
    114   // Write out the fileid -> filename mapping.
    115   encodeULEB128(VirtualFileMapping.size(), OS);
    116   for (const auto &FileID : VirtualFileMapping)
    117     encodeULEB128(FileID, OS);
    118 
    119   // Write out the expressions.
    120   CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
    121   auto MinExpressions = Minimizer.getExpressions();
    122   encodeULEB128(MinExpressions.size(), OS);
    123   for (const auto &E : MinExpressions) {
    124     writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
    125     writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
    126   }
    127 
    128   // Write out the mapping regions.
    129   // Split the regions into subarrays where each region in a
    130   // subarray has a fileID which is the index of that subarray.
    131   unsigned PrevLineStart = 0;
    132   unsigned CurrentFileID = ~0U;
    133   for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
    134     if (I->FileID != CurrentFileID) {
    135       // Ensure that all file ids have at least one mapping region.
    136       assert(I->FileID == (CurrentFileID + 1));
    137       // Find the number of regions with this file id.
    138       unsigned RegionCount = 1;
    139       for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
    140         ++RegionCount;
    141       // Start a new region sub-array.
    142       encodeULEB128(RegionCount, OS);
    143 
    144       CurrentFileID = I->FileID;
    145       PrevLineStart = 0;
    146     }
    147     Counter Count = Minimizer.adjust(I->Count);
    148     switch (I->Kind) {
    149     case CounterMappingRegion::CodeRegion:
    150       writeCounter(MinExpressions, Count, OS);
    151       break;
    152     case CounterMappingRegion::ExpansionRegion: {
    153       assert(Count.isZero());
    154       assert(I->ExpandedFileID <=
    155              (std::numeric_limits<unsigned>::max() >>
    156               Counter::EncodingCounterTagAndExpansionRegionTagBits));
    157       // Mark an expansion region with a set bit that follows the counter tag,
    158       // and pack the expanded file id into the remaining bits.
    159       unsigned EncodedTagExpandedFileID =
    160           (1 << Counter::EncodingTagBits) |
    161           (I->ExpandedFileID
    162            << Counter::EncodingCounterTagAndExpansionRegionTagBits);
    163       encodeULEB128(EncodedTagExpandedFileID, OS);
    164       break;
    165     }
    166     case CounterMappingRegion::SkippedRegion:
    167       assert(Count.isZero());
    168       encodeULEB128(unsigned(I->Kind)
    169                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
    170                     OS);
    171       break;
    172     }
    173     assert(I->LineStart >= PrevLineStart);
    174     encodeULEB128(I->LineStart - PrevLineStart, OS);
    175     encodeULEB128(I->ColumnStart, OS);
    176     assert(I->LineEnd >= I->LineStart);
    177     encodeULEB128(I->LineEnd - I->LineStart, OS);
    178     encodeULEB128(I->ColumnEnd, OS);
    179     PrevLineStart = I->LineStart;
    180   }
    181   // Ensure that all file ids have at least one mapping region.
    182   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
    183 }
    184