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 std::stable_sort( 128 MappingRegions.begin(), MappingRegions.end(), 129 [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) { 130 if (LHS.FileID != RHS.FileID) 131 return LHS.FileID < RHS.FileID; 132 if (LHS.startLoc() != RHS.startLoc()) 133 return LHS.startLoc() < RHS.startLoc(); 134 return LHS.Kind < RHS.Kind; 135 }); 136 137 // Write out the fileid -> filename mapping. 138 encodeULEB128(VirtualFileMapping.size(), OS); 139 for (const auto &FileID : VirtualFileMapping) 140 encodeULEB128(FileID, OS); 141 142 // Write out the expressions. 143 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 144 auto MinExpressions = Minimizer.getExpressions(); 145 encodeULEB128(MinExpressions.size(), OS); 146 for (const auto &E : MinExpressions) { 147 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 148 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 149 } 150 151 // Write out the mapping regions. 152 // Split the regions into subarrays where each region in a 153 // subarray has a fileID which is the index of that subarray. 154 unsigned PrevLineStart = 0; 155 unsigned CurrentFileID = ~0U; 156 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 157 if (I->FileID != CurrentFileID) { 158 // Ensure that all file ids have at least one mapping region. 159 assert(I->FileID == (CurrentFileID + 1)); 160 // Find the number of regions with this file id. 161 unsigned RegionCount = 1; 162 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 163 ++RegionCount; 164 // Start a new region sub-array. 165 encodeULEB128(RegionCount, OS); 166 167 CurrentFileID = I->FileID; 168 PrevLineStart = 0; 169 } 170 Counter Count = Minimizer.adjust(I->Count); 171 switch (I->Kind) { 172 case CounterMappingRegion::CodeRegion: 173 case CounterMappingRegion::GapRegion: 174 writeCounter(MinExpressions, Count, OS); 175 break; 176 case CounterMappingRegion::ExpansionRegion: { 177 assert(Count.isZero()); 178 assert(I->ExpandedFileID <= 179 (std::numeric_limits<unsigned>::max() >> 180 Counter::EncodingCounterTagAndExpansionRegionTagBits)); 181 // Mark an expansion region with a set bit that follows the counter tag, 182 // and pack the expanded file id into the remaining bits. 183 unsigned EncodedTagExpandedFileID = 184 (1 << Counter::EncodingTagBits) | 185 (I->ExpandedFileID 186 << Counter::EncodingCounterTagAndExpansionRegionTagBits); 187 encodeULEB128(EncodedTagExpandedFileID, OS); 188 break; 189 } 190 case CounterMappingRegion::SkippedRegion: 191 assert(Count.isZero()); 192 encodeULEB128(unsigned(I->Kind) 193 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 194 OS); 195 break; 196 } 197 assert(I->LineStart >= PrevLineStart); 198 encodeULEB128(I->LineStart - PrevLineStart, OS); 199 encodeULEB128(I->ColumnStart, OS); 200 assert(I->LineEnd >= I->LineStart); 201 encodeULEB128(I->LineEnd - I->LineStart, OS); 202 encodeULEB128(I->ColumnEnd, OS); 203 PrevLineStart = I->LineStart; 204 } 205 // Ensure that all file ids have at least one mapping region. 206 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 207 } 208