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