Home | History | Annotate | Line # | Download | only in Coverage 
      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 ? StringRef(CompressedStr) : 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 }
    253