contrib/llvm/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 /// \brief 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   /// \brief 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 /// \brief 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   // Sort the regions in an ascending order by the file id and the starting
 120   // location. Sort by region kinds to ensure stable order for tests.
 121   std::stable_sort(
 122       MappingRegions.begin(), MappingRegions.end(),
 123       [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) {
 124         if (LHS.FileID != RHS.FileID)
 125           return LHS.FileID < RHS.FileID;
 126         if (LHS.startLoc() != RHS.startLoc())
 127           return LHS.startLoc() < RHS.startLoc();
 128         return LHS.Kind < RHS.Kind;
 129       });
 130
 131   // Write out the fileid -> filename mapping.
 132   encodeULEB128(VirtualFileMapping.size(), OS);
 133   for (const auto &FileID : VirtualFileMapping)
 134     encodeULEB128(FileID, OS);
 135
 136   // Write out the expressions.
 137   CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
 138   auto MinExpressions = Minimizer.getExpressions();
 139   encodeULEB128(MinExpressions.size(), OS);
 140   for (const auto &E : MinExpressions) {
 141     writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
 142     writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
 143   }
 144
 145   // Write out the mapping regions.
 146   // Split the regions into subarrays where each region in a
 147   // subarray has a fileID which is the index of that subarray.
 148   unsigned PrevLineStart = 0;
 149   unsigned CurrentFileID = ~0U;
 150   for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
 151     if (I->FileID != CurrentFileID) {
 152       // Ensure that all file ids have at least one mapping region.
 153       assert(I->FileID == (CurrentFileID + 1));
 154       // Find the number of regions with this file id.
 155       unsigned RegionCount = 1;
 156       for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
 157         ++RegionCount;
 158       // Start a new region sub-array.
 159       encodeULEB128(RegionCount, OS);
 160
 161       CurrentFileID = I->FileID;
 162       PrevLineStart = 0;
 163     }
 164     Counter Count = Minimizer.adjust(I->Count);
 165     switch (I->Kind) {
 166     case CounterMappingRegion::CodeRegion:
 167       writeCounter(MinExpressions, Count, OS);
 168       break;
 169     case CounterMappingRegion::ExpansionRegion: {
 170       assert(Count.isZero());
 171       assert(I->ExpandedFileID <=
 172              (std::numeric_limits<unsigned>::max() >>
 173               Counter::EncodingCounterTagAndExpansionRegionTagBits));
 174       // Mark an expansion region with a set bit that follows the counter tag,
 175       // and pack the expanded file id into the remaining bits.
 176       unsigned EncodedTagExpandedFileID =
 177           (1 << Counter::EncodingTagBits) |
 178           (I->ExpandedFileID
 179            << Counter::EncodingCounterTagAndExpansionRegionTagBits);
 180       encodeULEB128(EncodedTagExpandedFileID, OS);
 181       break;
 182     }
 183     case CounterMappingRegion::SkippedRegion:
 184       assert(Count.isZero());
 185       encodeULEB128(unsigned(I->Kind)
 186                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 187                     OS);
 188       break;
 189     }
 190     assert(I->LineStart >= PrevLineStart);
 191     encodeULEB128(I->LineStart - PrevLineStart, OS);
 192     encodeULEB128(I->ColumnStart, OS);
 193     assert(I->LineEnd >= I->LineStart);
 194     encodeULEB128(I->LineEnd - I->LineStart, OS);
 195     encodeULEB128(I->ColumnEnd, OS);
 196     PrevLineStart = I->LineStart;
 197   }
 198   // Ensure that all file ids have at least one mapping region.
 199   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
 200 }