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 <cassert> 23 #include <limits> 24 #include <vector> 25 26 using namespace llvm; 27 using namespace coverage; 28 29 CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter( 30 ArrayRef<std::string> Filenames) 31 : Filenames(Filenames) { 32 #ifndef NDEBUG 33 StringSet<> NameSet; 34 for (StringRef Name : Filenames) 35 assert(NameSet.insert(Name).second && "Duplicate filename"); 36 #endif 37 } 38 39 void CoverageFilenamesSectionWriter::write(raw_ostream &OS, bool Compress) { 40 std::string FilenamesStr; 41 { 42 raw_string_ostream FilenamesOS{FilenamesStr}; 43 for (const auto &Filename : Filenames) { 44 encodeULEB128(Filename.size(), FilenamesOS); 45 FilenamesOS << Filename; 46 } 47 } 48 49 SmallVector<uint8_t, 128> CompressedStr; 50 bool doCompression = Compress && compression::zlib::isAvailable() && 51 DoInstrProfNameCompression; 52 if (doCompression) 53 compression::zlib::compress(arrayRefFromStringRef(FilenamesStr), 54 CompressedStr, 55 compression::zlib::BestSizeCompression); 56 57 // ::= <num-filenames> 58 // <uncompressed-len> 59 // <compressed-len-or-zero> 60 // (<compressed-filenames> | <uncompressed-filenames>) 61 encodeULEB128(Filenames.size(), OS); 62 encodeULEB128(FilenamesStr.size(), OS); 63 encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS); 64 OS << (doCompression ? toStringRef(CompressedStr) : StringRef(FilenamesStr)); 65 } 66 67 namespace { 68 69 /// Gather only the expressions that are used by the mapping 70 /// regions in this function. 71 class CounterExpressionsMinimizer { 72 ArrayRef<CounterExpression> Expressions; 73 SmallVector<CounterExpression, 16> UsedExpressions; 74 std::vector<unsigned> AdjustedExpressionIDs; 75 76 public: 77 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions, 78 ArrayRef<CounterMappingRegion> MappingRegions) 79 : Expressions(Expressions) { 80 AdjustedExpressionIDs.resize(Expressions.size(), 0); 81 for (const auto &I : MappingRegions) { 82 mark(I.Count); 83 mark(I.FalseCount); 84 } 85 for (const auto &I : MappingRegions) { 86 gatherUsed(I.Count); 87 gatherUsed(I.FalseCount); 88 } 89 } 90 91 void mark(Counter C) { 92 if (!C.isExpression()) 93 return; 94 unsigned ID = C.getExpressionID(); 95 AdjustedExpressionIDs[ID] = 1; 96 mark(Expressions[ID].LHS); 97 mark(Expressions[ID].RHS); 98 } 99 100 void gatherUsed(Counter C) { 101 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()]) 102 return; 103 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size(); 104 const auto &E = Expressions[C.getExpressionID()]; 105 UsedExpressions.push_back(E); 106 gatherUsed(E.LHS); 107 gatherUsed(E.RHS); 108 } 109 110 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; } 111 112 /// Adjust the given counter to correctly transition from the old 113 /// expression ids to the new expression ids. 114 Counter adjust(Counter C) const { 115 if (C.isExpression()) 116 C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]); 117 return C; 118 } 119 }; 120 121 } // end anonymous namespace 122 123 /// Encode the counter. 124 /// 125 /// The encoding uses the following format: 126 /// Low 2 bits - Tag: 127 /// Counter::Zero(0) - A Counter with kind Counter::Zero 128 /// Counter::CounterValueReference(1) - A counter with kind 129 /// Counter::CounterValueReference 130 /// Counter::Expression(2) + CounterExpression::Subtract(0) - 131 /// A counter with kind Counter::Expression and an expression 132 /// with kind CounterExpression::Subtract 133 /// Counter::Expression(2) + CounterExpression::Add(1) - 134 /// A counter with kind Counter::Expression and an expression 135 /// with kind CounterExpression::Add 136 /// Remaining bits - Counter/Expression ID. 137 static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions, 138 Counter C) { 139 unsigned Tag = unsigned(C.getKind()); 140 if (C.isExpression()) 141 Tag += Expressions[C.getExpressionID()].Kind; 142 unsigned ID = C.getCounterID(); 143 assert(ID <= 144 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits)); 145 return Tag | (ID << Counter::EncodingTagBits); 146 } 147 148 static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C, 149 raw_ostream &OS) { 150 encodeULEB128(encodeCounter(Expressions, C), OS); 151 } 152 153 void CoverageMappingWriter::write(raw_ostream &OS) { 154 // Check that we don't have any bogus regions. 155 assert(all_of(MappingRegions, 156 [](const CounterMappingRegion &CMR) { 157 return CMR.startLoc() <= CMR.endLoc(); 158 }) && 159 "Source region does not begin before it ends"); 160 161 // Sort the regions in an ascending order by the file id and the starting 162 // location. Sort by region kinds to ensure stable order for tests. 163 llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS, 164 const CounterMappingRegion &RHS) { 165 if (LHS.FileID != RHS.FileID) 166 return LHS.FileID < RHS.FileID; 167 if (LHS.startLoc() != RHS.startLoc()) 168 return LHS.startLoc() < RHS.startLoc(); 169 170 // Put `Decision` before `Expansion`. 171 auto getKindKey = [](CounterMappingRegion::RegionKind Kind) { 172 return (Kind == CounterMappingRegion::MCDCDecisionRegion 173 ? 2 * CounterMappingRegion::ExpansionRegion - 1 174 : 2 * Kind); 175 }; 176 177 return getKindKey(LHS.Kind) < getKindKey(RHS.Kind); 178 }); 179 180 // Write out the fileid -> filename mapping. 181 encodeULEB128(VirtualFileMapping.size(), OS); 182 for (const auto &FileID : VirtualFileMapping) 183 encodeULEB128(FileID, OS); 184 185 // Write out the expressions. 186 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 187 auto MinExpressions = Minimizer.getExpressions(); 188 encodeULEB128(MinExpressions.size(), OS); 189 for (const auto &E : MinExpressions) { 190 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 191 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 192 } 193 194 // Write out the mapping regions. 195 // Split the regions into subarrays where each region in a 196 // subarray has a fileID which is the index of that subarray. 197 unsigned PrevLineStart = 0; 198 unsigned CurrentFileID = ~0U; 199 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 200 if (I->FileID != CurrentFileID) { 201 // Ensure that all file ids have at least one mapping region. 202 assert(I->FileID == (CurrentFileID + 1)); 203 // Find the number of regions with this file id. 204 unsigned RegionCount = 1; 205 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 206 ++RegionCount; 207 // Start a new region sub-array. 208 encodeULEB128(RegionCount, OS); 209 210 CurrentFileID = I->FileID; 211 PrevLineStart = 0; 212 } 213 Counter Count = Minimizer.adjust(I->Count); 214 Counter FalseCount = Minimizer.adjust(I->FalseCount); 215 bool ParamsShouldBeNull = true; 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 { 255 // They are written as internal values plus 1. 256 const auto &BranchParams = I->getBranchParams(); 257 ParamsShouldBeNull = false; 258 unsigned ID1 = BranchParams.ID + 1; 259 unsigned TID1 = BranchParams.Conds[true] + 1; 260 unsigned FID1 = BranchParams.Conds[false] + 1; 261 encodeULEB128(ID1, OS); 262 encodeULEB128(TID1, OS); 263 encodeULEB128(FID1, OS); 264 } 265 break; 266 case CounterMappingRegion::MCDCDecisionRegion: 267 encodeULEB128(unsigned(I->Kind) 268 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 269 OS); 270 { 271 const auto &DecisionParams = I->getDecisionParams(); 272 ParamsShouldBeNull = false; 273 encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx), OS); 274 encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions), OS); 275 } 276 break; 277 } 278 assert(I->LineStart >= PrevLineStart); 279 encodeULEB128(I->LineStart - PrevLineStart, OS); 280 encodeULEB128(I->ColumnStart, OS); 281 assert(I->LineEnd >= I->LineStart); 282 encodeULEB128(I->LineEnd - I->LineStart, OS); 283 encodeULEB128(I->ColumnEnd, OS); 284 PrevLineStart = I->LineStart; 285 assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) && 286 "MCDCParams should be empty"); 287 (void)ParamsShouldBeNull; 288 } 289 // Ensure that all file ids have at least one mapping region. 290 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 291 } 292 293 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) { 294 auto ByteSwap = [](uint64_t N) { 295 return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N); 296 }; 297 298 // Output a 64bit magic number. 299 auto Magic = ByteSwap(TestingFormatMagic); 300 OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic)); 301 302 // Output a 64bit version field. 303 auto VersionLittle = ByteSwap(uint64_t(Version)); 304 OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle)); 305 306 // Output the ProfileNames data. 307 encodeULEB128(ProfileNamesData.size(), OS); 308 encodeULEB128(ProfileNamesAddr, OS); 309 OS << ProfileNamesData; 310 311 // Version2 adds an extra field to indicate the size of the 312 // CoverageMappingData. 313 if (Version == TestingFormatVersion::Version2) 314 encodeULEB128(CoverageMappingData.size(), OS); 315 316 // Coverage mapping data is expected to have an alignment of 8. 317 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 318 OS.write(uint8_t(0)); 319 OS << CoverageMappingData; 320 321 // Coverage records data is expected to have an alignment of 8. 322 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 323 OS.write(uint8_t(0)); 324 OS << CoverageRecordsData; 325 } 326