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
26using namespace llvm;
27using namespace coverage;
28
29CoverageFilenamesSectionWriter::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
39void 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
67namespace {
68
69/// Gather only the expressions that are used by the mapping
70/// regions in this function.
71class CounterExpressionsMinimizer {
72  ArrayRef<CounterExpression> Expressions;
73  SmallVector<CounterExpression, 16> UsedExpressions;
74  std::vector<unsigned> AdjustedExpressionIDs;
75
76public:
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.
137static 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
148static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
149                         raw_ostream &OS) {
150  encodeULEB128(encodeCounter(Expressions, C), OS);
151}
152
153void 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    return LHS.Kind < RHS.Kind;
170  });
171
172  // Write out the fileid -> filename mapping.
173  encodeULEB128(VirtualFileMapping.size(), OS);
174  for (const auto &FileID : VirtualFileMapping)
175    encodeULEB128(FileID, OS);
176
177  // Write out the expressions.
178  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
179  auto MinExpressions = Minimizer.getExpressions();
180  encodeULEB128(MinExpressions.size(), OS);
181  for (const auto &E : MinExpressions) {
182    writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
183    writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
184  }
185
186  // Write out the mapping regions.
187  // Split the regions into subarrays where each region in a
188  // subarray has a fileID which is the index of that subarray.
189  unsigned PrevLineStart = 0;
190  unsigned CurrentFileID = ~0U;
191  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
192    if (I->FileID != CurrentFileID) {
193      // Ensure that all file ids have at least one mapping region.
194      assert(I->FileID == (CurrentFileID + 1));
195      // Find the number of regions with this file id.
196      unsigned RegionCount = 1;
197      for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
198        ++RegionCount;
199      // Start a new region sub-array.
200      encodeULEB128(RegionCount, OS);
201
202      CurrentFileID = I->FileID;
203      PrevLineStart = 0;
204    }
205    Counter Count = Minimizer.adjust(I->Count);
206    Counter FalseCount = Minimizer.adjust(I->FalseCount);
207    switch (I->Kind) {
208    case CounterMappingRegion::CodeRegion:
209    case CounterMappingRegion::GapRegion:
210      writeCounter(MinExpressions, Count, OS);
211      break;
212    case CounterMappingRegion::ExpansionRegion: {
213      assert(Count.isZero());
214      assert(I->ExpandedFileID <=
215             (std::numeric_limits<unsigned>::max() >>
216              Counter::EncodingCounterTagAndExpansionRegionTagBits));
217      // Mark an expansion region with a set bit that follows the counter tag,
218      // and pack the expanded file id into the remaining bits.
219      unsigned EncodedTagExpandedFileID =
220          (1 << Counter::EncodingTagBits) |
221          (I->ExpandedFileID
222           << Counter::EncodingCounterTagAndExpansionRegionTagBits);
223      encodeULEB128(EncodedTagExpandedFileID, OS);
224      break;
225    }
226    case CounterMappingRegion::SkippedRegion:
227      assert(Count.isZero());
228      encodeULEB128(unsigned(I->Kind)
229                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
230                    OS);
231      break;
232    case CounterMappingRegion::BranchRegion:
233      encodeULEB128(unsigned(I->Kind)
234                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
235                    OS);
236      writeCounter(MinExpressions, Count, OS);
237      writeCounter(MinExpressions, FalseCount, OS);
238      break;
239    }
240    assert(I->LineStart >= PrevLineStart);
241    encodeULEB128(I->LineStart - PrevLineStart, OS);
242    encodeULEB128(I->ColumnStart, OS);
243    assert(I->LineEnd >= I->LineStart);
244    encodeULEB128(I->LineEnd - I->LineStart, OS);
245    encodeULEB128(I->ColumnEnd, OS);
246    PrevLineStart = I->LineStart;
247  }
248  // Ensure that all file ids have at least one mapping region.
249  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
250}
251