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