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 unsigned encodeCounter(ArrayRef<CounterExpression> Expressions, Counter C) {
107 unsigned Tag = unsigned(C.getKind());
108 if (C.isExpression())
109 Tag += Expressions[C.getExpressionID()].Kind;
110 unsigned ID = C.getCounterID();
112 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
113 return Tag | (ID << Counter::EncodingTagBits);
116 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
118 encodeULEB128(encodeCounter(Expressions, C), OS);
121 void CoverageMappingWriter::write(raw_ostream &OS) {
122 // Sort the regions in an ascending order by the file id and the starting
124 std::sort(MappingRegions.begin(), MappingRegions.end());
126 // Write out the fileid -> filename mapping.
127 encodeULEB128(VirtualFileMapping.size(), OS);
128 for (const auto &FileID : VirtualFileMapping)
129 encodeULEB128(FileID, OS);
131 // Write out the expressions.
132 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
133 auto MinExpressions = Minimizer.getExpressions();
134 encodeULEB128(MinExpressions.size(), OS);
135 for (const auto &E : MinExpressions) {
136 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
137 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
140 // Write out the mapping regions.
141 // Split the regions into subarrays where each region in a
142 // subarray has a fileID which is the index of that subarray.
143 unsigned PrevLineStart = 0;
144 unsigned CurrentFileID = MappingRegions.front().FileID;
145 assert(CurrentFileID == 0);
146 encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
147 for (const auto &I : MappingRegions) {
148 if (I.FileID != CurrentFileID) {
149 // Ensure that all file ids have at least one mapping region.
150 assert(I.FileID == (CurrentFileID + 1));
151 // Start a new region sub-array.
152 CurrentFileID = I.FileID;
153 encodeULEB128(countFileIDs(MappingRegions, CurrentFileID), OS);
156 Counter Count = Minimizer.adjust(I.Count);
158 case CounterMappingRegion::CodeRegion:
159 writeCounter(MinExpressions, Count, OS);
161 case CounterMappingRegion::ExpansionRegion: {
162 assert(Count.isZero());
163 assert(I.ExpandedFileID <=
164 (std::numeric_limits<unsigned>::max() >>
165 Counter::EncodingCounterTagAndExpansionRegionTagBits));
166 // Mark an expansion region with a set bit that follows the counter tag,
167 // and pack the expanded file id into the remaining bits.
168 unsigned EncodedTagExpandedFileID =
169 (1 << Counter::EncodingTagBits) |
171 << Counter::EncodingCounterTagAndExpansionRegionTagBits);
172 encodeULEB128(EncodedTagExpandedFileID, OS);
175 case CounterMappingRegion::SkippedRegion:
176 assert(Count.isZero());
177 encodeULEB128(unsigned(I.Kind)
178 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
182 assert(I.LineStart >= PrevLineStart);
183 encodeULEB128(I.LineStart - PrevLineStart, OS);
184 uint64_t CodeBeforeColumnStart =
185 uint64_t(I.HasCodeBefore) |
186 (uint64_t(I.ColumnStart)
187 << CounterMappingRegion::EncodingHasCodeBeforeBits);
188 encodeULEB128(CodeBeforeColumnStart, OS);
189 assert(I.LineEnd >= I.LineStart);
190 encodeULEB128(I.LineEnd - I.LineStart, OS);
191 encodeULEB128(I.ColumnEnd, OS);
192 PrevLineStart = I.LineStart;
194 // Ensure that all file ids have at least one mapping region.
195 assert(CurrentFileID == (VirtualFileMapping.size() - 1));