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