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