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 bool ParamsShouldBeNull = true; 217 switch (I->Kind) { 218 case CounterMappingRegion::CodeRegion: 219 case CounterMappingRegion::GapRegion: 220 writeCounter(MinExpressions, Count, OS); 221 break; 222 case CounterMappingRegion::ExpansionRegion: { 223 assert(Count.isZero()); 224 assert(I->ExpandedFileID <= 225 (std::numeric_limits<unsigned>::max() >> 226 Counter::EncodingCounterTagAndExpansionRegionTagBits)); 227 // Mark an expansion region with a set bit that follows the counter tag, 228 // and pack the expanded file id into the remaining bits. 229 unsigned EncodedTagExpandedFileID = 230 (1 << Counter::EncodingTagBits) | 231 (I->ExpandedFileID 232 << Counter::EncodingCounterTagAndExpansionRegionTagBits); 233 encodeULEB128(EncodedTagExpandedFileID, OS); 234 break; 235 } 236 case CounterMappingRegion::SkippedRegion: 237 assert(Count.isZero()); 238 encodeULEB128(unsigned(I->Kind) 239 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 240 OS); 241 break; 242 case CounterMappingRegion::BranchRegion: 243 encodeULEB128(unsigned(I->Kind) 244 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 245 OS); 246 writeCounter(MinExpressions, Count, OS); 247 writeCounter(MinExpressions, FalseCount, OS); 248 break; 249 case CounterMappingRegion::MCDCBranchRegion: 250 encodeULEB128(unsigned(I->Kind) 251 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 252 OS); 253 writeCounter(MinExpressions, Count, OS); 254 writeCounter(MinExpressions, FalseCount, OS); 255 { 256 // They are written as internal values plus 1. 257 const auto &BranchParams = I->getBranchParams(); 258 ParamsShouldBeNull = false; 259 unsigned ID1 = BranchParams.ID + 1; 260 unsigned TID1 = BranchParams.Conds[true] + 1; 261 unsigned FID1 = BranchParams.Conds[false] + 1; 262 encodeULEB128(ID1, OS); 263 encodeULEB128(TID1, OS); 264 encodeULEB128(FID1, OS); 265 } 266 break; 267 case CounterMappingRegion::MCDCDecisionRegion: 268 encodeULEB128(unsigned(I->Kind) 269 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 270 OS); 271 { 272 const auto &DecisionParams = I->getDecisionParams(); 273 ParamsShouldBeNull = false; 274 encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx), OS); 275 encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions), OS); 276 } 277 break; 278 } 279 assert(I->LineStart >= PrevLineStart); 280 encodeULEB128(I->LineStart - PrevLineStart, OS); 281 encodeULEB128(I->ColumnStart, OS); 282 assert(I->LineEnd >= I->LineStart); 283 encodeULEB128(I->LineEnd - I->LineStart, OS); 284 encodeULEB128(I->ColumnEnd, OS); 285 PrevLineStart = I->LineStart; 286 assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) && 287 "MCDCParams should be empty"); 288 (void)ParamsShouldBeNull; 289 } 290 // Ensure that all file ids have at least one mapping region. 291 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 292 } 293 294 void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) { 295 auto ByteSwap = [](uint64_t N) { 296 return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N); 297 }; 298 299 // Output a 64bit magic number. 300 auto Magic = ByteSwap(TestingFormatMagic); 301 OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic)); 302 303 // Output a 64bit version field. 304 auto VersionLittle = ByteSwap(uint64_t(Version)); 305 OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle)); 306 307 // Output the ProfileNames data. 308 encodeULEB128(ProfileNamesData.size(), OS); 309 encodeULEB128(ProfileNamesAddr, OS); 310 OS << ProfileNamesData; 311 312 // Version2 adds an extra field to indicate the size of the 313 // CoverageMappingData. 314 if (Version == TestingFormatVersion::Version2) 315 encodeULEB128(CoverageMappingData.size(), OS); 316 317 // Coverage mapping data is expected to have an alignment of 8. 318 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 319 OS.write(uint8_t(0)); 320 OS << CoverageMappingData; 321 322 // Coverage records data is expected to have an alignment of 8. 323 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad) 324 OS.write(uint8_t(0)); 325 OS << CoverageRecordsData; 326 } 327