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