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 <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   SmallVector<uint8_t, 128> CompressedStr;
  50   bool doCompression = Compress && compression::zlib::isAvailable() &&
  51                        DoInstrProfNameCompression;
  52   if (doCompression)
  53     compression::zlib::compress(arrayRefFromStringRef(FilenamesStr),
  54                                 CompressedStr,
  55                                 compression::zlib::BestSizeCompression);
  56
  57   // ::= <num-filenames>
  58   //     <uncompressed-len>
  59   //     <compressed-len-or-zero>
  60   //     (<compressed-filenames> | <uncompressed-filenames>)
  61   encodeULEB128(Filenames.size(), OS);
  62   encodeULEB128(FilenamesStr.size(), OS);
  63   encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);
  64   OS << (doCompression ? toStringRef(CompressedStr) : StringRef(FilenamesStr));
  65 }
  66
  67 namespace {
  68
  69 /// Gather only the expressions that are used by the mapping
  70 /// regions in this function.
  71 class CounterExpressionsMinimizer {
  72   ArrayRef<CounterExpression> Expressions;
  73   SmallVector<CounterExpression, 16> UsedExpressions;
  74   std::vector<unsigned> AdjustedExpressionIDs;
  75
  76 public:
  77   CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
  78                               ArrayRef<CounterMappingRegion> MappingRegions)
  79       : Expressions(Expressions) {
  80     AdjustedExpressionIDs.resize(Expressions.size(), 0);
  81     for (const auto &I : MappingRegions) {
  82       mark(I.Count);
  83       mark(I.FalseCount);
  84     }
  85     for (const auto &I : MappingRegions) {
  86       gatherUsed(I.Count);
  87       gatherUsed(I.FalseCount);
  88     }
  89   }
  90
  91   void mark(Counter C) {
  92     if (!C.isExpression())
  93       return;
  94     unsigned ID = C.getExpressionID();
  95     AdjustedExpressionIDs[ID] = 1;
  96     mark(Expressions[ID].LHS);
  97     mark(Expressions[ID].RHS);
  98   }
  99
 100   void gatherUsed(Counter C) {
 101     if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
 102       return;
 103     AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
 104     const auto &E = Expressions[C.getExpressionID()];
 105     UsedExpressions.push_back(E);
 106     gatherUsed(E.LHS);
 107     gatherUsed(E.RHS);
 108   }
 109
 110   ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
 111
 112   /// Adjust the given counter to correctly transition from the old
 113   /// expression ids to the new expression ids.
 114   Counter adjust(Counter C) const {
 115     if (C.isExpression())
 116       C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
 117     return C;
 118   }
 119 };
 120
 121 } // end anonymous namespace
 122
 123 /// Encode the counter.
 124 ///
 125 /// The encoding uses the following format:
 126 /// Low 2 bits - Tag:
 127 ///   Counter::Zero(0) - A Counter with kind Counter::Zero
 128 ///   Counter::CounterValueReference(1) - A counter with kind
 129 ///     Counter::CounterValueReference
 130 ///   Counter::Expression(2) + CounterExpression::Subtract(0) -
 131 ///     A counter with kind Counter::Expression and an expression
 132 ///     with kind CounterExpression::Subtract
 133 ///   Counter::Expression(2) + CounterExpression::Add(1) -
 134 ///     A counter with kind Counter::Expression and an expression
 135 ///     with kind CounterExpression::Add
 136 /// Remaining bits - Counter/Expression ID.
 137 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
 138                               Counter C) {
 139   unsigned Tag = unsigned(C.getKind());
 140   if (C.isExpression())
 141     Tag += Expressions[C.getExpressionID()].Kind;
 142   unsigned ID = C.getCounterID();
 143   assert(ID <=
 144          (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
 145   return Tag | (ID << Counter::EncodingTagBits);
 146 }
 147
 148 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
 149                          raw_ostream &OS) {
 150   encodeULEB128(encodeCounter(Expressions, C), OS);
 151 }
 152
 153 void CoverageMappingWriter::write(raw_ostream &OS) {
 154   // Check that we don't have any bogus regions.
 155   assert(all_of(MappingRegions,
 156                 [](const CounterMappingRegion &CMR) {
 157                   return CMR.startLoc() <= CMR.endLoc();
 158                 }) &&
 159          "Source region does not begin before it ends");
 160
 161   // Sort the regions in an ascending order by the file id and the starting
 162   // location. Sort by region kinds to ensure stable order for tests.
 163   llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,
 164                                        const CounterMappingRegion &RHS) {
 165     if (LHS.FileID != RHS.FileID)
 166       return LHS.FileID < RHS.FileID;
 167     if (LHS.startLoc() != RHS.startLoc())
 168       return LHS.startLoc() < RHS.startLoc();
 169
 170     // Put `Decision` before `Expansion`.
 171     auto getKindKey = [](CounterMappingRegion::RegionKind Kind) {
 172       return (Kind == CounterMappingRegion::MCDCDecisionRegion
 173                   ? 2 * CounterMappingRegion::ExpansionRegion - 1
 174                   : 2 * Kind);
 175     };
 176
 177     return getKindKey(LHS.Kind) < getKindKey(RHS.Kind);
 178   });
 179
 180   // Write out the fileid -> filename mapping.
 181   encodeULEB128(VirtualFileMapping.size(), OS);
 182   for (const auto &FileID : VirtualFileMapping)
 183     encodeULEB128(FileID, OS);
 184
 185   // Write out the expressions.
 186   CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
 187   auto MinExpressions = Minimizer.getExpressions();
 188   encodeULEB128(MinExpressions.size(), OS);
 189   for (const auto &E : MinExpressions) {
 190     writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
 191     writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
 192   }
 193
 194   // Write out the mapping regions.
 195   // Split the regions into subarrays where each region in a
 196   // subarray has a fileID which is the index of that subarray.
 197   unsigned PrevLineStart = 0;
 198   unsigned CurrentFileID = ~0U;
 199   for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
 200     if (I->FileID != CurrentFileID) {
 201       // Ensure that all file ids have at least one mapping region.
 202       assert(I->FileID == (CurrentFileID + 1));
 203       // Find the number of regions with this file id.
 204       unsigned RegionCount = 1;
 205       for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
 206         ++RegionCount;
 207       // Start a new region sub-array.
 208       encodeULEB128(RegionCount, OS);
 209
 210       CurrentFileID = I->FileID;
 211       PrevLineStart = 0;
 212     }
 213     Counter Count = Minimizer.adjust(I->Count);
 214     Counter FalseCount = Minimizer.adjust(I->FalseCount);
 215     bool ParamsShouldBeNull = true;
 216     switch (I->Kind) {
 217     case CounterMappingRegion::CodeRegion:
 218     case CounterMappingRegion::GapRegion:
 219       writeCounter(MinExpressions, Count, OS);
 220       break;
 221     case CounterMappingRegion::ExpansionRegion: {
 222       assert(Count.isZero());
 223       assert(I->ExpandedFileID <=
 224              (std::numeric_limits<unsigned>::max() >>
 225               Counter::EncodingCounterTagAndExpansionRegionTagBits));
 226       // Mark an expansion region with a set bit that follows the counter tag,
 227       // and pack the expanded file id into the remaining bits.
 228       unsigned EncodedTagExpandedFileID =
 229           (1 << Counter::EncodingTagBits) |
 230           (I->ExpandedFileID
 231            << Counter::EncodingCounterTagAndExpansionRegionTagBits);
 232       encodeULEB128(EncodedTagExpandedFileID, OS);
 233       break;
 234     }
 235     case CounterMappingRegion::SkippedRegion:
 236       assert(Count.isZero());
 237       encodeULEB128(unsigned(I->Kind)
 238                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 239                     OS);
 240       break;
 241     case CounterMappingRegion::BranchRegion:
 242       encodeULEB128(unsigned(I->Kind)
 243                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 244                     OS);
 245       writeCounter(MinExpressions, Count, OS);
 246       writeCounter(MinExpressions, FalseCount, OS);
 247       break;
 248     case CounterMappingRegion::MCDCBranchRegion:
 249       encodeULEB128(unsigned(I->Kind)
 250                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 251                     OS);
 252       writeCounter(MinExpressions, Count, OS);
 253       writeCounter(MinExpressions, FalseCount, OS);
 254       {
 255         // They are written as internal values plus 1.
 256         const auto &BranchParams = I->getBranchParams();
 257         ParamsShouldBeNull = false;
 258         unsigned ID1 = BranchParams.ID + 1;
 259         unsigned TID1 = BranchParams.Conds[true] + 1;
 260         unsigned FID1 = BranchParams.Conds[false] + 1;
 261         encodeULEB128(ID1, OS);
 262         encodeULEB128(TID1, OS);
 263         encodeULEB128(FID1, OS);
 264       }
 265       break;
 266     case CounterMappingRegion::MCDCDecisionRegion:
 267       encodeULEB128(unsigned(I->Kind)
 268                         << Counter::EncodingCounterTagAndExpansionRegionTagBits,
 269                     OS);
 270       {
 271         const auto &DecisionParams = I->getDecisionParams();
 272         ParamsShouldBeNull = false;
 273         encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx), OS);
 274         encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions), OS);
 275       }
 276       break;
 277     }
 278     assert(I->LineStart >= PrevLineStart);
 279     encodeULEB128(I->LineStart - PrevLineStart, OS);
 280     encodeULEB128(I->ColumnStart, OS);
 281     assert(I->LineEnd >= I->LineStart);
 282     encodeULEB128(I->LineEnd - I->LineStart, OS);
 283     encodeULEB128(I->ColumnEnd, OS);
 284     PrevLineStart = I->LineStart;
 285     assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) &&
 286            "MCDCParams should be empty");
 287     (void)ParamsShouldBeNull;
 288   }
 289   // Ensure that all file ids have at least one mapping region.
 290   assert(CurrentFileID == (VirtualFileMapping.size() - 1));
 291 }
 292
 293 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {
 294   auto ByteSwap = [](uint64_t N) {
 295     return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N);
 296   };
 297
 298   // Output a 64bit magic number.
 299   auto Magic = ByteSwap(TestingFormatMagic);
 300   OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic));
 301
 302   // Output a 64bit version field.
 303   auto VersionLittle = ByteSwap(uint64_t(Version));
 304   OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle));
 305
 306   // Output the ProfileNames data.
 307   encodeULEB128(ProfileNamesData.size(), OS);
 308   encodeULEB128(ProfileNamesAddr, OS);
 309   OS << ProfileNamesData;
 310
 311   // Version2 adds an extra field to indicate the size of the
 312   // CoverageMappingData.
 313   if (Version == TestingFormatVersion::Version2)
 314     encodeULEB128(CoverageMappingData.size(), OS);
 315
 316   // Coverage mapping data is expected to have an alignment of 8.
 317   for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
 318     OS.write(uint8_t(0));
 319   OS << CoverageMappingData;
 320
 321   // Coverage records data is expected to have an alignment of 8.
 322   for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)
 323     OS.write(uint8_t(0));
 324   OS << CoverageRecordsData;
 325 }