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/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"
26 using namespace coverage;
28 void CoverageFilenamesSectionWriter::write(raw_ostream &OS) {
29 encodeULEB128(Filenames.size(), OS);
30 for (const auto &Filename : Filenames) {
31 encodeULEB128(Filename.size(), OS);
38 /// \brief 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;
46 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,
47 ArrayRef<CounterMappingRegion> MappingRegions)
48 : Expressions(Expressions) {
49 AdjustedExpressionIDs.resize(Expressions.size(), 0);
50 for (const auto &I : MappingRegions)
52 for (const auto &I : MappingRegions)
56 void mark(Counter C) {
57 if (!C.isExpression())
59 unsigned ID = C.getExpressionID();
60 AdjustedExpressionIDs[ID] = 1;
61 mark(Expressions[ID].LHS);
62 mark(Expressions[ID].RHS);
65 void gatherUsed(Counter C) {
66 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])
68 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();
69 const auto &E = Expressions[C.getExpressionID()];
70 UsedExpressions.push_back(E);
75 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }
77 /// \brief Adjust the given counter to correctly transition from the old
78 /// expression ids to the new expression ids.
79 Counter adjust(Counter C) const {
81 C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);
86 } // end anonymous namespace
88 /// \brief Encode the counter.
90 /// The encoding uses the following format:
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 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,
104 unsigned Tag = unsigned(C.getKind());
105 if (C.isExpression())
106 Tag += Expressions[C.getExpressionID()].Kind;
107 unsigned ID = C.getCounterID();
109 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));
110 return Tag | (ID << Counter::EncodingTagBits);
113 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,
115 encodeULEB128(encodeCounter(Expressions, C), OS);
118 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();
124 "Source region does not begin before it ends");
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.
129 MappingRegions.begin(), MappingRegions.end(),
130 [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) {
131 if (LHS.FileID != RHS.FileID)
132 return LHS.FileID < RHS.FileID;
133 if (LHS.startLoc() != RHS.startLoc())
134 return LHS.startLoc() < RHS.startLoc();
135 return LHS.Kind < RHS.Kind;
138 // Write out the fileid -> filename mapping.
139 encodeULEB128(VirtualFileMapping.size(), OS);
140 for (const auto &FileID : VirtualFileMapping)
141 encodeULEB128(FileID, OS);
143 // Write out the expressions.
144 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);
145 auto MinExpressions = Minimizer.getExpressions();
146 encodeULEB128(MinExpressions.size(), OS);
147 for (const auto &E : MinExpressions) {
148 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);
149 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);
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 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {
158 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 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)
165 // Start a new region sub-array.
166 encodeULEB128(RegionCount, OS);
168 CurrentFileID = I->FileID;
171 Counter Count = Minimizer.adjust(I->Count);
173 case CounterMappingRegion::CodeRegion:
174 case CounterMappingRegion::GapRegion:
175 writeCounter(MinExpressions, Count, OS);
177 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 unsigned EncodedTagExpandedFileID =
185 (1 << Counter::EncodingTagBits) |
187 << Counter::EncodingCounterTagAndExpansionRegionTagBits);
188 encodeULEB128(EncodedTagExpandedFileID, OS);
191 case CounterMappingRegion::SkippedRegion:
192 assert(Count.isZero());
193 encodeULEB128(unsigned(I->Kind)
194 << Counter::EncodingCounterTagAndExpansionRegionTagBits,
198 assert(I->LineStart >= PrevLineStart);
199 encodeULEB128(I->LineStart - PrevLineStart, OS);
200 encodeULEB128(I->ColumnStart, OS);
201 assert(I->LineEnd >= I->LineStart);
202 encodeULEB128(I->LineEnd - I->LineStart, OS);
203 encodeULEB128(I->ColumnEnd, OS);
204 PrevLineStart = I->LineStart;
206 // Ensure that all file ids have at least one mapping region.
207 assert(CurrentFileID == (VirtualFileMapping.size() - 1));