1 //=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains support for writing coverage mapping data for
11 // instrumentation based coverage.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/ProfileData/CoverageMappingWriter.h"
16 #include "llvm/Support/LEB128.h"
19 using namespace coverage;
21 void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
22 encodeULEB128(Filenames.size(), OS);
23 for (const auto &Filename : Filenames) {
24 encodeULEB128(Filename.size(), OS);
30 /// \brief Gather only the expressions that are used by the mapping
31 /// regions in this function.
32 class CounterExpressionsMinimizer {
33 ArrayRef<CounterExpression> Expressions;
34 llvm::SmallVector<CounterExpression, 16> UsedExpressions;
35 std::vector<unsigned> AdjustedExpressionIDs;
38 void mark(Counter C) {
39 if (!C.isExpression())
41 unsigned ID = C.getExpressionID();
42 AdjustedExpressionIDs[ID] = 1;
43 mark(Expressions[ID].LHS);
44 mark(Expressions[ID].RHS);
47 void gatherUsed(Counter C) {
48 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
50 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
51 const auto &E = Expressions[C.getExpressionID()];
52 UsedExpressions.push_back(E);
57 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
58 ArrayRef<CounterMappingRegion> MappingRegions)
59 : Expressions(Expressions) {
60 AdjustedExpressionIDs.resize(Expressions.size(), 0);
61 for (const auto &I : MappingRegions)
63 for (const auto &I : MappingRegions)
67 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
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 {
73 C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
79 /// \brief Return the number of regions that have the given FileID.
80 static unsigned countFileIDs(ArrayRef<CounterMappingRegion> Regions,
83 for (const auto &I : Regions) {
84 if (I.FileID == FileID)
86 if (I.FileID > FileID)
92 /// \brief Encode the counter.
94 /// The encoding uses the following format:
96 /// Counter::Zero(0) - A Counter with kind Counter::Zero
97 /// Counter::CounterValueReference(1) - A counter with kind
98 /// Counter::CounterValueReference
99 /// Counter::Expression(2) + CounterExpression::Subtract(0) -
100 /// A counter with kind Counter::Expression and an expression
101 /// with kind CounterExpression::Subtract
102 /// Counter::Expression(2) + CounterExpression::Add(1) -
103 /// A counter with kind Counter::Expression and an expression
104 /// with kind CounterExpression::Add
105 /// Remaining bits - Counter/Expression ID.
106 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
108 unsigned Tag = unsigned(C.getKind());
109 if (C.isExpression())
110 Tag += Expressions[C.getExpressionID()].Kind;
111 unsigned ID = C.getCounterID();
113 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
114 return Tag | (ID << Counter::EncodingTagBits);
117 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
119 encodeULEB128(encodeCounter(Expressions, C), OS);
122 void CoverageMappingWriter::write(raw_ostream &OS) {
123 // Sort the regions in an ascending order by the file id and the starting
125 std::sort(MappingRegions.begin(), MappingRegions.end());
127 // Write out the fileid -> filename mapping.
128 encodeULEB128(VirtualFileMapping.size(), OS);
129 for (const auto &FileID : VirtualFileMapping)
130 encodeULEB128(FileID, OS);
132 // Write out the expressions.
133 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
134 auto MinExpressions = Minimizer.getExpressions();
135 encodeULEB128(MinExpressions.size(), OS);
136 for (const auto &E : MinExpressions) {
137 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
138 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
141 // Write out the mapping regions.
142 // Split the regions into subarrays where each region in a
143 // subarray has a fileID which is the index of that subarray.
144 unsigned PrevLineStart = 0;
145 unsigned CurrentFileID = MappingRegions.front().FileID;
146 assert(CurrentFileID == 0);
147 encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
148 for (const auto &I : MappingRegions) {
149 if (I.FileID != CurrentFileID) {
150 // Ensure that all file ids have at least one mapping region.
151 assert(I.FileID == (CurrentFileID + 1));
152 // Start a new region sub-array.
153 CurrentFileID = I.FileID;
154 encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
157 Counter Count = Minimizer.adjust(I.Count);
159 case CounterMappingRegion::CodeRegion:
160 writeCounter(MinExpressions, Count, OS);
162 case CounterMappingRegion::ExpansionRegion: {
163 assert(Count.isZero());
164 assert(I.ExpandedFileID <=
165 (std::numeric_limits<unsigned>::max() >>
166 Counter::EncodingCounterTagAndExpansionRegionTagBits));
167 // Mark an expansion region with a set bit that follows the counter tag,
168 // and pack the expanded file id into the remaining bits.
169 unsigned EncodedTagExpandedFileID =
170 (1 << Counter::EncodingTagBits) |
172 << Counter::EncodingCounterTagAndExpansionRegionTagBits);
173 encodeULEB128(EncodedTagExpandedFileID, OS);
176 case CounterMappingRegion::SkippedRegion:
177 assert(Count.isZero());
178 encodeULEB128(unsigned(I.Kind)
179 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
183 assert(I.LineStart >= PrevLineStart);
184 encodeULEB128(I.LineStart - PrevLineStart, OS);
185 uint64_t CodeBeforeColumnStart =
186 uint64_t(I.HasCodeBefore) |
187 (uint64_t(I.ColumnStart)
188 << CounterMappingRegion::EncodingHasCodeBeforeBits);
189 encodeULEB128(CodeBeforeColumnStart, OS);
190 assert(I.LineEnd >= I.LineStart);
191 encodeULEB128(I.LineEnd - I.LineStart, OS);
192 encodeULEB128(I.ColumnEnd, OS);
193 PrevLineStart = I.LineStart;
195 // Ensure that all file ids have at least one mapping region.
196 assert(CurrentFileID == (VirtualFileMapping.size() - 1));