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