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/ADT/ArrayRef.h" 16 #include "llvm/ADT/SmallVector.h" 17 #include "llvm/ProfileData/Coverage/CoverageMappingWriter.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 // Sort the regions in an ascending order by the file id and the starting 120 // location. Sort by region kinds to ensure stable order for tests. 121 std::stable_sort( 122 MappingRegions.begin(), MappingRegions.end(), 123 [](const CounterMappingRegion &LHS, const CounterMappingRegion &RHS) { 124 if (LHS.FileID != RHS.FileID) 125 return LHS.FileID < RHS.FileID; 126 if (LHS.startLoc() != RHS.startLoc()) 127 return LHS.startLoc() < RHS.startLoc(); 128 return LHS.Kind < RHS.Kind; 129 }); 130 131 // Write out the fileid -> filename mapping. 132 encodeULEB128(VirtualFileMapping.size(), OS); 133 for (const auto &FileID : VirtualFileMapping) 134 encodeULEB128(FileID, OS); 135 136 // Write out the expressions. 137 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 138 auto MinExpressions = Minimizer.getExpressions(); 139 encodeULEB128(MinExpressions.size(), OS); 140 for (const auto &E : MinExpressions) { 141 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 142 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 143 } 144 145 // Write out the mapping regions. 146 // Split the regions into subarrays where each region in a 147 // subarray has a fileID which is the index of that subarray. 148 unsigned PrevLineStart = 0; 149 unsigned CurrentFileID = ~0U; 150 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 151 if (I->FileID != CurrentFileID) { 152 // Ensure that all file ids have at least one mapping region. 153 assert(I->FileID == (CurrentFileID + 1)); 154 // Find the number of regions with this file id. 155 unsigned RegionCount = 1; 156 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 157 ++RegionCount; 158 // Start a new region sub-array. 159 encodeULEB128(RegionCount, OS); 160 161 CurrentFileID = I->FileID; 162 PrevLineStart = 0; 163 } 164 Counter Count = Minimizer.adjust(I->Count); 165 switch (I->Kind) { 166 case CounterMappingRegion::CodeRegion: 167 writeCounter(MinExpressions, Count, OS); 168 break; 169 case CounterMappingRegion::ExpansionRegion: { 170 assert(Count.isZero()); 171 assert(I->ExpandedFileID <= 172 (std::numeric_limits<unsigned>::max() >> 173 Counter::EncodingCounterTagAndExpansionRegionTagBits)); 174 // Mark an expansion region with a set bit that follows the counter tag, 175 // and pack the expanded file id into the remaining bits. 176 unsigned EncodedTagExpandedFileID = 177 (1 << Counter::EncodingTagBits) | 178 (I->ExpandedFileID 179 << Counter::EncodingCounterTagAndExpansionRegionTagBits); 180 encodeULEB128(EncodedTagExpandedFileID, OS); 181 break; 182 } 183 case CounterMappingRegion::SkippedRegion: 184 assert(Count.isZero()); 185 encodeULEB128(unsigned(I->Kind) 186 << Counter::EncodingCounterTagAndExpansionRegionTagBits, 187 OS); 188 break; 189 } 190 assert(I->LineStart >= PrevLineStart); 191 encodeULEB128(I->LineStart - PrevLineStart, OS); 192 encodeULEB128(I->ColumnStart, OS); 193 assert(I->LineEnd >= I->LineStart); 194 encodeULEB128(I->LineEnd - I->LineStart, OS); 195 encodeULEB128(I->ColumnEnd, OS); 196 PrevLineStart = I->LineStart; 197 } 198 // Ensure that all file ids have at least one mapping region. 199 assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 200 } 201