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