lib/ProfileData/Coverage/CoverageMappingWriter.cpp

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