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