1//=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file contains support for writing coverage mapping data for
11// instrumentation based coverage.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
16#include "llvm/Support/LEB128.h"
17
18using namespace llvm;
19using namespace coverage;
20
21void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
22  encodeULEB128(Filenames.size(), OS);
23  for (const auto &Filename : Filenames) {
24    encodeULEB128(Filename.size(), OS);
25    OS << Filename;
26  }
27}
28
29namespace {
30/// \brief Gather only the expressions that are used by the mapping
31/// regions in this function.
32class CounterExpressionsMinimizer {
33  ArrayRef<CounterExpression> Expressions;
34  llvm::SmallVector<CounterExpression, 16> UsedExpressions;
35  std::vector<unsigned> AdjustedExpressionIDs;
36
37public:
38  void mark(Counter C) {
39    if (!C.isExpression())
40      return;
41    unsigned ID = C.getExpressionID();
42    AdjustedExpressionIDs[ID] = 1;
43    mark(Expressions[ID].LHS);
44    mark(Expressions[ID].RHS);
45  }
46
47  void gatherUsed(Counter C) {
48    if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
49      return;
50    AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
51    const auto &E = Expressions[C.getExpressionID()];
52    UsedExpressions.push_back(E);
53    gatherUsed(E.LHS);
54    gatherUsed(E.RHS);
55  }
56
57  CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
58                              ArrayRef<CounterMappingRegion> MappingRegions)
59      : Expressions(Expressions) {
60    AdjustedExpressionIDs.resize(Expressions.size(), 0);
61    for (const auto &I : MappingRegions)
62      mark(I.Count);
63    for (const auto &I : MappingRegions)
64      gatherUsed(I.Count);
65  }
66
67  ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
68
69  /// \brief Adjust the given counter to correctly transition from the old
70  /// expression ids to the new expression ids.
71  Counter adjust(Counter C) const {
72    if (C.isExpression())
73      C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
74    return C;
75  }
76};
77}
78
79/// \brief Encode the counter.
80///
81/// The encoding uses the following format:
82/// Low 2 bits - Tag:
83///   Counter::Zero(0) - A Counter with kind Counter::Zero
84///   Counter::CounterValueReference(1) - A counter with kind
85///     Counter::CounterValueReference
86///   Counter::Expression(2) + CounterExpression::Subtract(0) -
87///     A counter with kind Counter::Expression and an expression
88///     with kind CounterExpression::Subtract
89///   Counter::Expression(2) + CounterExpression::Add(1) -
90///     A counter with kind Counter::Expression and an expression
91///     with kind CounterExpression::Add
92/// Remaining bits - Counter/Expression ID.
93static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
94                              Counter C) {
95  unsigned Tag = unsigned(C.getKind());
96  if (C.isExpression())
97    Tag += Expressions[C.getExpressionID()].Kind;
98  unsigned ID = C.getCounterID();
99  assert(ID <=
100         (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
101  return Tag | (ID << Counter::EncodingTagBits);
102}
103
104static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
105                         raw_ostream &OS) {
106  encodeULEB128(encodeCounter(Expressions, C), OS);
107}
108
109void CoverageMappingWriter::write(raw_ostream &OS) {
110  // Sort the regions in an ascending order by the file id and the starting
111  // location.
112  std::stable_sort(MappingRegions.begin(), MappingRegions.end());
113
114  // Write out the fileid -> filename mapping.
115  encodeULEB128(VirtualFileMapping.size(), OS);
116  for (const auto &FileID : VirtualFileMapping)
117    encodeULEB128(FileID, OS);
118
119  // Write out the expressions.
120  CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
121  auto MinExpressions = Minimizer.getExpressions();
122  encodeULEB128(MinExpressions.size(), OS);
123  for (const auto &E : MinExpressions) {
124    writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
125    writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
126  }
127
128  // Write out the mapping regions.
129  // Split the regions into subarrays where each region in a
130  // subarray has a fileID which is the index of that subarray.
131  unsigned PrevLineStart = 0;
132  unsigned CurrentFileID = ~0U;
133  for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
134    if (I->FileID != CurrentFileID) {
135      // Ensure that all file ids have at least one mapping region.
136      assert(I->FileID == (CurrentFileID + 1));
137      // Find the number of regions with this file id.
138      unsigned RegionCount = 1;
139      for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
140        ++RegionCount;
141      // Start a new region sub-array.
142      encodeULEB128(RegionCount, OS);
143
144      CurrentFileID = I->FileID;
145      PrevLineStart = 0;
146    }
147    Counter Count = Minimizer.adjust(I->Count);
148    switch (I->Kind) {
149    case CounterMappingRegion::CodeRegion:
150      writeCounter(MinExpressions, Count, OS);
151      break;
152    case CounterMappingRegion::ExpansionRegion: {
153      assert(Count.isZero());
154      assert(I->ExpandedFileID <=
155             (std::numeric_limits<unsigned>::max() >>
156              Counter::EncodingCounterTagAndExpansionRegionTagBits));
157      // Mark an expansion region with a set bit that follows the counter tag,
158      // and pack the expanded file id into the remaining bits.
159      unsigned EncodedTagExpandedFileID =
160          (1 << Counter::EncodingTagBits) |
161          (I->ExpandedFileID
162           << Counter::EncodingCounterTagAndExpansionRegionTagBits);
163      encodeULEB128(EncodedTagExpandedFileID, OS);
164      break;
165    }
166    case CounterMappingRegion::SkippedRegion:
167      assert(Count.isZero());
168      encodeULEB128(unsigned(I->Kind)
169                        << Counter::EncodingCounterTagAndExpansionRegionTagBits,
170                    OS);
171      break;
172    }
173    assert(I->LineStart >= PrevLineStart);
174    encodeULEB128(I->LineStart - PrevLineStart, OS);
175    encodeULEB128(I->ColumnStart, OS);
176    assert(I->LineEnd >= I->LineStart);
177    encodeULEB128(I->LineEnd - I->LineStart, OS);
178    encodeULEB128(I->ColumnEnd, OS);
179    PrevLineStart = I->LineStart;
180  }
181  // Ensure that all file ids have at least one mapping region.
182  assert(CurrentFileID == (VirtualFileMapping.size() - 1));
183}
184