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