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/ADT/StringExtras.h" 18 #include "llvm/ProfileData/InstrProf.h" 19 #include "llvm/Support/Compression.h" 20 #include "llvm/Support/LEB128.h" 21 #include "llvm/Support/raw_ostream.h" 22 #include <algorithm> 23 #include <cassert> 24 #include <limits> 25 #include <vector> 26 27 using namespace llvm; 28 using namespace coverage; 29 30 CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter( 31 ArrayRef<std::string> Filenames) 32 : Filenames(Filenames) { 33 #ifndef NDEBUG 34 StringSet<> NameSet; 35 for (StringRef Name : Filenames) 36 assert(NameSet.insert(Name).second && "Duplicate filename"); 37 #endif 38 } 39 40 void CoverageFilenamesSectionWriter::write(raw_ostream &OS, bool Compress) { 41 std::string FilenamesStr; 42 { 43 raw_string_ostream FilenamesOS{FilenamesStr}; 44 for (const auto &Filename : Filenames) { 45 encodeULEB128(Filename.size(), FilenamesOS); 46 FilenamesOS << Filename; 47 } 48 } 49 50 SmallVector<uint8_t, 128> CompressedStr; 51 bool doCompression = Compress && compression::zlib::isAvailable() && 52 DoInstrProfNameCompression; 53 if (doCompression) 54 compression::zlib::compress(arrayRefFromStringRef(FilenamesStr), 55 CompressedStr, 56 compression::zlib::BestSizeCompression); 57 58 // ::= <num-filenames> 59 // <uncompressed-len> 60 // <compressed-len-or-zero> 61 // (<compressed-filenames> | <uncompressed-filenames>) 62 encodeULEB128(Filenames.size(), OS); 63 encodeULEB128(FilenamesStr.size(), OS); 64 encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS); 65 OS << (doCompression ? toStringRef(CompressedStr) : StringRef(FilenamesStr)); 66 } 67 68 namespace { 69 70 /// Gather only the expressions that are used by the mapping 71 /// regions in this function. 72 class CounterExpressionsMinimizer { 73 ArrayRef<CounterExpression> Expressions; 74 SmallVector<CounterExpression, 16> UsedExpressions; 75 std::vector<unsigned> AdjustedExpressionIDs; 76 77 public: 78 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions, 79 ArrayRef<CounterMappingRegion> MappingRegions) 80 : Expressions(Expressions) { 81 AdjustedExpressionIDs.resize(Expressions.size(), 0); 82 for (const auto &I : MappingRegions) { 83 mark(I.Count); 84 mark(I.FalseCount); 85 } 86 for (const auto &I : MappingRegions) { 87 gatherUsed(I.Count); 88 gatherUsed(I.FalseCount); 89 } 90 } 91 92 void mark(Counter C) { 93 if (!C.isExpression()) 94 return; 95 unsigned ID = C.getExpressionID(); 96 AdjustedExpressionIDs[ID] = 1; 97 mark(Expressions[ID].LHS); 98 mark(Expressions[ID].RHS); 99 } 100 101 void gatherUsed(Counter C) { 102 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()]) 103 return; 104 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size(); 105 const auto &E = Expressions[C.getExpressionID()]; 106 UsedExpressions.push_back(E); 107 gatherUsed(E.LHS); 108 gatherUsed(E.RHS); 109 } 110 111 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; } 112 113 /// Adjust the given counter to correctly transition from the old 114 /// expression ids to the new expression ids. 115 Counter adjust(Counter C) const { 116 if (C.isExpression()) 117 C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]); 118 return C; 119 } 120 }; 121 122 } // end anonymous namespace 123 124 /// Encode the counter. 125 /// 126 /// The encoding uses the following format: 127 /// Low 2 bits - Tag: 128 /// Counter::Zero(0) - A Counter with kind Counter::Zero 129 /// Counter::CounterValueReference(1) - A counter with kind 130 /// Counter::CounterValueReference 131 /// Counter::Expression(2) + CounterExpression::Subtract(0) - 132 /// A counter with kind Counter::Expression and an expression 133 /// with kind CounterExpression::Subtract 134 /// Counter::Expression(2) + CounterExpression::Add(1) - 135 /// A counter with kind Counter::Expression and an expression 136 /// with kind CounterExpression::Add 137 /// Remaining bits - Counter/Expression ID. 138 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions, 139 Counter C) { 140 unsigned Tag = unsigned(C.getKind()); 141 if (C.isExpression()) 142 Tag += Expressions[C.getExpressionID()].Kind; 143 unsigned ID = C.getCounterID(); 144 assert(ID <= 145 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits)); 146 return Tag | (ID << Counter::EncodingTagBits); 147 } 148 149 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C, 150 raw_ostream &OS) { 151 encodeULEB128(encodeCounter(Expressions, C), OS); 152 } 153 154 void CoverageMappingWriter::write(raw_ostream &OS) { 155 // Check that we don't have any bogus regions. 156 assert(all_of(MappingRegions, 157 [](const CounterMappingRegion &CMR) { 158 return CMR.startLoc() <= CMR.endLoc(); 159 }) && 160 "Source region does not begin before it ends"); 161 162 // Sort the regions in an ascending order by the file id and the starting 163 // location. Sort by region kinds to ensure stable order for tests. 164 llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS, 165 const CounterMappingRegion &RHS) { 166 if (LHS.FileID != RHS.FileID) 167 return LHS.FileID < RHS.FileID; 168 if (LHS.startLoc() != RHS.startLoc()) 169 return LHS.startLoc() < RHS.startLoc(); 170 return LHS.Kind < RHS.Kind; 171 }); 172 173 // Write out the fileid -> filename mapping. 174 encodeULEB128(VirtualFileMapping.size(), OS); 175 for (const auto &FileID : VirtualFileMapping) 176 encodeULEB128(FileID, OS); 177 178 // Write out the expressions. 179 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 180 auto MinExpressions = Minimizer.getExpressions(); 181 encodeULEB128(MinExpressions.size(), OS); 182 for (const auto &E : MinExpressions) { 183 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 184 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 185 } 186 187 // Write out the mapping regions. 188 // Split the regions into subarrays where each region in a 189 // subarray has a fileID which is the index of that subarray. 190 unsigned PrevLineStart = 0; 191 unsigned CurrentFileID = ~0U; 192 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 193 if (I->FileID != CurrentFileID) { 194 // Ensure that all file ids have at least one mapping region. 195 assert(I->FileID == (CurrentFileID + 1)); 196 // Find the number of regions with this file id. 197 unsigned RegionCount = 1; 198 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 199 ++RegionCount; 200 // Start a new region sub-array. 201 encodeULEB128(RegionCount, OS); 202 203 CurrentFileID = I->FileID; 204 PrevLineStart = 0; 205 } 206 Counter Count = Minimizer.adjust(I->Count); 207 Counter FalseCount = Minimizer.adjust(I->FalseCount); 208 switch (I->Kind) { 209 case CounterMappingRegion::CodeRegion: 210 case CounterMappingRegion::GapRegion: 211 writeCounter(MinExpressions, Count, OS); 212 break; 213 case CounterMappingRegion::ExpansionRegion: { 214 assert(Count.isZero()); 215 assert(I->ExpandedFileID <= 216 (std::numeric_limits<unsigned>::max() >> 217 Counter::EncodingCounterTagAndExpansionRegionTagBits)); 218 // Mark an expansion region with a set bit that follows the counter tag, 219 // and pack the expanded file id into the remaining bits. 220 unsigned EncodedTagExpandedFileID = 221 (1 << Counter::EncodingTagBits) | 222 (I->ExpandedFileID 223 << Counter::EncodingCounterTagAndExpansionRegionTagBits); 224 encodeULEB128(EncodedTagExpandedFileID, OS); 225 break; 226 } 227 case CounterMappingRegion::SkippedRegion: 228 assert(Count.isZero()); 229 encodeULEB128(unsigned(I->Kind) 230 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 231 OS); 232 break; 233 case CounterMappingRegion::BranchRegion: 234 encodeULEB128(unsigned(I->Kind) 235 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 236 OS); 237 writeCounter(MinExpressions, Count, OS); 238 writeCounter(MinExpressions, FalseCount, OS); 239 break; 240 } 241 assert(I->LineStart >= PrevLineStart); 242 encodeULEB128(I->LineStart - PrevLineStart, OS); 243 encodeULEB128(I->ColumnStart, OS); 244 assert(I->LineEnd >= I->LineStart); 245 encodeULEB128(I->LineEnd - I->LineStart, OS); 246 encodeULEB128(I->ColumnEnd, OS); 247 PrevLineStart = I->LineStart; 248 } 249 // Ensure that all file ids have at least one mapping region. 250 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 251 } 252