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 Return the number of regions that have the given FileID.
  80 static unsigned countFileIDs(ArrayRef<CounterMappingRegion> Regions,
  81                              unsigned FileID) {
  82   unsigned Result = 0;
  83   for (const auto &I : Regions) {
  84     if (I.FileID == FileID)
  85       ++Result;
  86     if (I.FileID > FileID)
  87       break;
  88   }
  89   return Result;
  90 }
  91
  92 /// \brief Encode the counter.
  93 ///
  94 /// The encoding uses the following format:
  95 /// Low 2 bits - Tag:
  96 ///   Counter::Zero(0) - A Counter with kind Counter::Zero
  97 ///   Counter::CounterValueReference(1) - A counter with kind
  98 ///     Counter::CounterValueReference
  99 ///   Counter::Expression(2) + CounterExpression::Subtract(0) -
 100 ///     A counter with kind Counter::Expression and an expression
 101 ///     with kind CounterExpression::Subtract
 102 ///   Counter::Expression(2) + CounterExpression::Add(1) -
 103 ///     A counter with kind Counter::Expression and an expression
 104 ///     with kind CounterExpression::Add
 105 /// Remaining bits - Counter/Expression ID.
 106 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
 107                               Counter C) {
 108   unsigned Tag = unsigned(C.getKind());
 109   if (C.isExpression())
 110     Tag += Expressions[C.getExpressionID()].Kind;
 111   unsigned ID = C.getCounterID();
 112   assert(ID <=
 113          (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
 114   return Tag | (ID << Counter::EncodingTagBits);
 115 }
 116
 117 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
 118                          raw_ostream &OS) {
 119   encodeULEB128(encodeCounter(Expressions, C), OS);
 120 }
 121
 122 void CoverageMappingWriter::write(raw_ostream &OS) {
 123   // Sort the regions in an ascending order by the file id and the starting
 124   // location.
 125   std::sort(MappingRegions.begin(), MappingRegions.end());
 126
 127   // Write out the fileid -> filename mapping.
 128   encodeULEB128(VirtualFileMapping.size(), OS);
 129   for (const auto &FileID : VirtualFileMapping)
 130     encodeULEB128(FileID, OS);
 131
 132   // Write out the expressions.
 133   CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
 134   auto MinExpressions = Minimizer.getExpressions();
 135   encodeULEB128(MinExpressions.size(), OS);
 136   for (const auto &E : MinExpressions) {
 137     writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
 138     writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
 139   }
 140
 141   // Write out the mapping regions.
 142   // Split the regions into subarrays where each region in a
 143   // subarray has a fileID which is the index of that subarray.
 144   unsigned PrevLineStart = 0;
 145   unsigned CurrentFileID = MappingRegions.front().FileID;
 146   assert(CurrentFileID == 0);
 147   encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
 148   for (const auto &I : MappingRegions) {
 149     if (I.FileID != CurrentFileID) {
 150       // Ensure that all file ids have at least one mapping region.
 151       assert(I.FileID == (CurrentFileID + 1));
 152       // Start a new region sub-array.
 153       CurrentFileID = I.FileID;
 154       encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
 155       PrevLineStart = 0;
 156     }
 157     Counter Count = Minimizer.adjust(I.Count);
 158     switch (I.Kind) {
 159     case CounterMappingRegion::CodeRegion:
 160       writeCounter(MinExpressions, Count, OS);
 161       break;
 162     case CounterMappingRegion::ExpansionRegion: {
 163       assert(Count.isZero());
 164       assert(I.ExpandedFileID <=
 165              (std::numeric_limits<unsigned>::max() >>
 166               Counter::EncodingCounterTagAndExpansionRegionTagBits));
 167       // Mark an expansion region with a set bit that follows the counter tag,
 168       // and pack the expanded file id into the remaining bits.
 169       unsigned EncodedTagExpandedFileID =
 170           (1 << Counter::EncodingTagBits) |
 171           (I.ExpandedFileID
 172            << Counter::EncodingCounterTagAndExpansionRegionTagBits);
 173       encodeULEB128(EncodedTagExpandedFileID, OS);
 174       break;
 175     }
 176     case CounterMappingRegion::SkippedRegion:
 177       assert(Count.isZero());
 178       encodeULEB128(unsigned(I.Kind)
 179                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 180                     OS);
 181       break;
 182     }
 183     assert(I.LineStart >= PrevLineStart);
 184     encodeULEB128(I.LineStart - PrevLineStart, OS);
 185     uint64_t CodeBeforeColumnStart =
 186         uint64_t(I.HasCodeBefore) |
 187         (uint64_t(I.ColumnStart)
 188          << CounterMappingRegion::EncodingHasCodeBeforeBits);
 189     encodeULEB128(CodeBeforeColumnStart, OS);
 190     assert(I.LineEnd >= I.LineStart);
 191     encodeULEB128(I.LineEnd - I.LineStart, OS);
 192     encodeULEB128(I.ColumnEnd, OS);
 193     PrevLineStart = I.LineStart;
 194   }
 195   // Ensure that all file ids have at least one mapping region.
 196   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
 197 }