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