Line data Source code
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/ADT/ArrayRef.h"
17 : #include "llvm/ADT/SmallVector.h"
18 : #include "llvm/Support/LEB128.h"
19 : #include "llvm/Support/raw_ostream.h"
20 : #include <algorithm>
21 : #include <cassert>
22 : #include <limits>
23 : #include <vector>
24 :
25 : using namespace llvm;
26 : using namespace coverage;
27 :
28 55 : void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
29 55 : encodeULEB128(Filenames.size(), OS);
30 118 : for (const auto &Filename : Filenames) {
31 63 : encodeULEB128(Filename.size(), OS);
32 63 : OS << Filename;
33 : }
34 55 : }
35 :
36 : namespace {
37 :
38 : /// Gather only the expressions that are used by the mapping
39 : /// regions in this function.
40 : class CounterExpressionsMinimizer {
41 : ArrayRef<CounterExpression> Expressions;
42 : SmallVector<CounterExpression, 16> UsedExpressions;
43 : std::vector<unsigned> AdjustedExpressionIDs;
44 :
45 : public:
46 304 : CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
47 : ArrayRef<CounterMappingRegion> MappingRegions)
48 608 : : Expressions(Expressions) {
49 304 : AdjustedExpressionIDs.resize(Expressions.size(), 0);
50 1895 : for (const auto &I : MappingRegions)
51 1591 : mark(I.Count);
52 1895 : for (const auto &I : MappingRegions)
53 1591 : gatherUsed(I.Count);
54 304 : }
55 :
56 2185 : void mark(Counter C) {
57 2185 : if (!C.isExpression())
58 : return;
59 297 : unsigned ID = C.getExpressionID();
60 297 : AdjustedExpressionIDs[ID] = 1;
61 594 : mark(Expressions[ID].LHS);
62 594 : mark(Expressions[ID].RHS);
63 : }
64 :
65 2021 : void gatherUsed(Counter C) {
66 2021 : if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
67 : return;
68 215 : AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
69 215 : const auto &E = Expressions[C.getExpressionID()];
70 215 : UsedExpressions.push_back(E);
71 215 : gatherUsed(E.LHS);
72 215 : gatherUsed(E.RHS);
73 : }
74 :
75 : ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
76 :
77 : /// Adjust the given counter to correctly transition from the old
78 : /// expression ids to the new expression ids.
79 : Counter adjust(Counter C) const {
80 2021 : if (C.isExpression())
81 594 : C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
82 : return C;
83 : }
84 : };
85 :
86 : } // end anonymous namespace
87 :
88 : /// Encode the counter.
89 : ///
90 : /// The encoding uses the following format:
91 : /// Low 2 bits - Tag:
92 : /// Counter::Zero(0) - A Counter with kind Counter::Zero
93 : /// Counter::CounterValueReference(1) - A counter with kind
94 : /// Counter::CounterValueReference
95 : /// Counter::Expression(2) + CounterExpression::Subtract(0) -
96 : /// A counter with kind Counter::Expression and an expression
97 : /// with kind CounterExpression::Subtract
98 : /// Counter::Expression(2) + CounterExpression::Add(1) -
99 : /// A counter with kind Counter::Expression and an expression
100 : /// with kind CounterExpression::Add
101 : /// Remaining bits - Counter/Expression ID.
102 0 : static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
103 : Counter C) {
104 : unsigned Tag = unsigned(C.getKind());
105 0 : if (C.isExpression())
106 0 : Tag += Expressions[C.getExpressionID()].Kind;
107 : unsigned ID = C.getCounterID();
108 : assert(ID <=
109 : (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
110 0 : return Tag | (ID << Counter::EncodingTagBits);
111 : }
112 :
113 0 : static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
114 : raw_ostream &OS) {
115 0 : encodeULEB128(encodeCounter(Expressions, C), OS);
116 0 : }
117 :
118 304 : void CoverageMappingWriter::write(raw_ostream &OS) {
119 : // Check that we don't have any bogus regions.
120 : assert(all_of(MappingRegions,
121 : [](const CounterMappingRegion &CMR) {
122 : return CMR.startLoc() <= CMR.endLoc();
123 : }) &&
124 : "Source region does not begin before it ends");
125 :
126 : // Sort the regions in an ascending order by the file id and the starting
127 : // location. Sort by region kinds to ensure stable order for tests.
128 : std::stable_sort(
129 : MappingRegions.begin(), MappingRegions.end(),
130 : [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) {
131 0 : if (LHS.FileID != RHS.FileID)
132 0 : return LHS.FileID < RHS.FileID;
133 : if (LHS.startLoc() != RHS.startLoc())
134 : return LHS.startLoc() < RHS.startLoc();
135 0 : return LHS.Kind < RHS.Kind;
136 : });
137 :
138 : // Write out the fileid -> filename mapping.
139 304 : encodeULEB128(VirtualFileMapping.size(), OS);
140 806 : for (const auto &FileID : VirtualFileMapping)
141 502 : encodeULEB128(FileID, OS);
142 :
143 : // Write out the expressions.
144 608 : CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
145 : auto MinExpressions = Minimizer.getExpressions();
146 304 : encodeULEB128(MinExpressions.size(), OS);
147 519 : for (const auto &E : MinExpressions) {
148 215 : writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
149 215 : writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
150 : }
151 :
152 : // Write out the mapping regions.
153 : // Split the regions into subarrays where each region in a
154 : // subarray has a fileID which is the index of that subarray.
155 : unsigned PrevLineStart = 0;
156 : unsigned CurrentFileID = ~0U;
157 1895 : for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
158 1591 : if (I->FileID != CurrentFileID) {
159 : // Ensure that all file ids have at least one mapping region.
160 : assert(I->FileID == (CurrentFileID + 1));
161 : // Find the number of regions with this file id.
162 : unsigned RegionCount = 1;
163 1591 : for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
164 1089 : ++RegionCount;
165 : // Start a new region sub-array.
166 502 : encodeULEB128(RegionCount, OS);
167 :
168 502 : CurrentFileID = I->FileID;
169 : PrevLineStart = 0;
170 : }
171 1591 : Counter Count = Minimizer.adjust(I->Count);
172 1591 : switch (I->Kind) {
173 1412 : case CounterMappingRegion::CodeRegion:
174 : case CounterMappingRegion::GapRegion:
175 1412 : writeCounter(MinExpressions, Count, OS);
176 1412 : break;
177 166 : case CounterMappingRegion::ExpansionRegion: {
178 : assert(Count.isZero());
179 : assert(I->ExpandedFileID <=
180 : (std::numeric_limits<unsigned>::max() >>
181 : Counter::EncodingCounterTagAndExpansionRegionTagBits));
182 : // Mark an expansion region with a set bit that follows the counter tag,
183 : // and pack the expanded file id into the remaining bits.
184 166 : unsigned EncodedTagExpandedFileID =
185 : (1 << Counter::EncodingTagBits) |
186 166 : (I->ExpandedFileID
187 166 : << Counter::EncodingCounterTagAndExpansionRegionTagBits);
188 166 : encodeULEB128(EncodedTagExpandedFileID, OS);
189 166 : break;
190 : }
191 13 : case CounterMappingRegion::SkippedRegion:
192 : assert(Count.isZero());
193 13 : encodeULEB128(unsigned(I->Kind)
194 13 : << Counter::EncodingCounterTagAndExpansionRegionTagBits,
195 : OS);
196 13 : break;
197 : }
198 : assert(I->LineStart >= PrevLineStart);
199 1591 : encodeULEB128(I->LineStart - PrevLineStart, OS);
200 1591 : encodeULEB128(I->ColumnStart, OS);
201 : assert(I->LineEnd >= I->LineStart);
202 1591 : encodeULEB128(I->LineEnd - I->LineStart, OS);
203 1591 : encodeULEB128(I->ColumnEnd, OS);
204 1591 : PrevLineStart = I->LineStart;
205 : }
206 : // Ensure that all file ids have at least one mapping region.
207 : assert(CurrentFileID == (VirtualFileMapping.size() - 1));
208 304 : }
|
