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