lib/ProfileData/CoverageMappingWriter.cpp

   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/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 }