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 171 // Put `Decision` before `Expansion`. 172 auto getKindKey = [](CounterMappingRegion::RegionKind Kind) { 173 return (Kind == CounterMappingRegion::MCDCDecisionRegion 174 ? 2 * CounterMappingRegion::ExpansionRegion - 1 175 : 2 * Kind); 176 }; 177 178 return getKindKey(LHS.Kind) < getKindKey(RHS.Kind); 179 }); 180 181 // Write out the fileid -> filename mapping. 182 encodeULEB128(VirtualFileMapping.size(), OS); 183 for (const auto &FileID : VirtualFileMapping) 184 encodeULEB128(FileID, OS); 185 186 // Write out the expressions. 187 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 188 auto MinExpressions = Minimizer.getExpressions(); 189 encodeULEB128(MinExpressions.size(), OS); 190 for (const auto &E : MinExpressions) { 191 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 192 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 193 } 194 195 // Write out the mapping regions. 196 // Split the regions into subarrays where each region in a 197 // subarray has a fileID which is the index of that subarray. 198 unsigned PrevLineStart = 0; 199 unsigned CurrentFileID = ~0U; 200 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 201 if (I->FileID != CurrentFileID) { 202 // Ensure that all file ids have at least one mapping region. 203 assert(I->FileID == (CurrentFileID + 1)); 204 // Find the number of regions with this file id. 205 unsigned RegionCount = 1; 206 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 207 ++RegionCount; 208 // Start a new region sub-array. 209 encodeULEB128(RegionCount, OS); 210 211 CurrentFileID = I->FileID; 212 PrevLineStart = 0; 213 } 214 Counter Count = Minimizer.adjust(I->Count); 215 Counter FalseCount = Minimizer.adjust(I->FalseCount); 216 switch (I->Kind) { 217 case CounterMappingRegion::CodeRegion: 218 case CounterMappingRegion::GapRegion: 219 writeCounter(MinExpressions, Count, OS); 220 break; 221 case CounterMappingRegion::ExpansionRegion: { 222 assert(Count.isZero()); 223 assert(I->ExpandedFileID <= 224 (std::numeric_limits<unsigned>::max() >> 225 Counter::EncodingCounterTagAndExpansionRegionTagBits)); 226 // Mark an expansion region with a set bit that follows the counter tag, 227 // and pack the expanded file id into the remaining bits. 228 unsigned EncodedTagExpandedFileID = 229 (1 << Counter::EncodingTagBits) | 230 (I->ExpandedFileID 231 << Counter::EncodingCounterTagAndExpansionRegionTagBits); 232 encodeULEB128(EncodedTagExpandedFileID, OS); 233 break; 234 } 235 case CounterMappingRegion::SkippedRegion: 236 assert(Count.isZero()); 237 encodeULEB128(unsigned(I->Kind) 238 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 239 OS); 240 break; 241 case CounterMappingRegion::BranchRegion: 242 encodeULEB128(unsigned(I->Kind) 243 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 244 OS); 245 writeCounter(MinExpressions, Count, OS); 246 writeCounter(MinExpressions, FalseCount, OS); 247 break; 248 case CounterMappingRegion::MCDCBranchRegion: 249 encodeULEB128(unsigned(I->Kind) 250 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 251 OS); 252 writeCounter(MinExpressions, Count, OS); 253 writeCounter(MinExpressions, FalseCount, OS); 254 encodeULEB128(unsigned(I->MCDCParams.ID), OS); 255 encodeULEB128(unsigned(I->MCDCParams.TrueID), OS); 256 encodeULEB128(unsigned(I->MCDCParams.FalseID), OS); 257 break; 258 case CounterMappingRegion::MCDCDecisionRegion: 259 encodeULEB128(unsigned(I->Kind) 260 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 261 OS); 262 encodeULEB128(unsigned(I->MCDCParams.BitmapIdx), OS); 263 encodeULEB128(unsigned(I->MCDCParams.NumConditions), OS); 264 break; 265 } 266 assert(I->LineStart >= PrevLineStart); 267 encodeULEB128(I->LineStart - PrevLineStart, OS); 268 encodeULEB128(I->ColumnStart, OS); 269 assert(I->LineEnd >= I->LineStart); 270 encodeULEB128(I->LineEnd - I->LineStart, OS); 271 encodeULEB128(I->ColumnEnd, OS); 272 PrevLineStart = I->LineStart; 273 } 274 // Ensure that all file ids have at least one mapping region. 275 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 276 } 277 278 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) { 279 auto ByteSwap = [](uint64_t N) { 280 return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N); 281 }; 282 283 // Output a 64bit magic number. 284 auto Magic = ByteSwap(TestingFormatMagic); 285 OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic)); 286 287 // Output a 64bit version field. 288 auto VersionLittle = ByteSwap(uint64_t(Version)); 289 OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle)); 290 291 // Output the ProfileNames data. 292 encodeULEB128(ProfileNamesData.size(), OS); 293 encodeULEB128(ProfileNamesAddr, OS); 294 OS << ProfileNamesData; 295 296 // Version2 adds an extra field to indicate the size of the 297 // CoverageMappingData. 298 if (Version == TestingFormatVersion::Version2) 299 encodeULEB128(CoverageMappingData.size(), OS); 300 301 // Coverage mapping data is expected to have an alignment of 8. 302 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 303 OS.write(uint8_t(0)); 304 OS << CoverageMappingData; 305 306 // Coverage records data is expected to have an alignment of 8. 307 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 308 OS.write(uint8_t(0)); 309 OS << CoverageRecordsData; 310 } 311