137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//=-- CoverageMappingWriter.cpp - Code coverage mapping writer -------------=// 237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// The LLVM Compiler Infrastructure 437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// This file is distributed under the University of Illinois Open Source 637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// License. See LICENSE.TXT for details. 737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 1037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// This file contains support for writing coverage mapping data for 1137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// instrumentation based coverage. 1237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines// 1337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines//===----------------------------------------------------------------------===// 1437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/ProfileData/CoverageMappingWriter.h" 1637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#include "llvm/Support/LEB128.h" 1737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 1837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesusing namespace llvm; 1937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesusing namespace coverage; 2037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid CoverageFilenamesSectionWriter::write(raw_ostream &OS) { 2237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(Filenames.size(), OS); 2337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &Filename : Filenames) { 2437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(Filename.size(), OS); 2537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS << Filename; 2637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 2737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 2837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 2937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesnamespace { 3037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \brief Gather only the expressions that are used by the mapping 3137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// regions in this function. 3237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesclass CounterExpressionsMinimizer { 3337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ArrayRef<CounterExpression> Expressions; 3437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines llvm::SmallVector<CounterExpression, 16> UsedExpressions; 3537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines std::vector<unsigned> AdjustedExpressionIDs; 3637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 3737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinespublic: 3837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void mark(Counter C) { 3937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!C.isExpression()) 4037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 4137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned ID = C.getExpressionID(); 4237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AdjustedExpressionIDs[ID] = 1; 4337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines mark(Expressions[ID].LHS); 4437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines mark(Expressions[ID].RHS); 4537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 4637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 4737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines void gatherUsed(Counter C) { 4837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()]) 4937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return; 5037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size(); 5137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines const auto &E = Expressions[C.getExpressionID()]; 5237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines UsedExpressions.push_back(E); 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines gatherUsed(E.LHS); 5437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines gatherUsed(E.RHS); 5537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 5637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 5737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions, 5837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ArrayRef<CounterMappingRegion> MappingRegions) 5937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines : Expressions(Expressions) { 6037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines AdjustedExpressionIDs.resize(Expressions.size(), 0); 6137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &I : MappingRegions) 6237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines mark(I.Count); 6337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &I : MappingRegions) 6437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines gatherUsed(I.Count); 6537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 6637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; } 6837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 6937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// \brief Adjust the given counter to correctly transition from the old 7037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines /// expression ids to the new expression ids. 7137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Counter adjust(Counter C) const { 7237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (C.isExpression()) 7337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]); 7437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return C; 7537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 7637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines}; 7737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 7837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 7937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// \brief Encode the counter. 8037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// 8137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// The encoding uses the following format: 8237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Low 2 bits - Tag: 8337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Counter::Zero(0) - A Counter with kind Counter::Zero 8437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Counter::CounterValueReference(1) - A counter with kind 8537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Counter::CounterValueReference 8637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Counter::Expression(2) + CounterExpression::Subtract(0) - 8737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// A counter with kind Counter::Expression and an expression 8837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// with kind CounterExpression::Subtract 8937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Counter::Expression(2) + CounterExpression::Add(1) - 9037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// A counter with kind Counter::Expression and an expression 9137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// with kind CounterExpression::Add 9237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines/// Remaining bits - Counter/Expression ID. 9337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic unsigned encodeCounter(ArrayRef<CounterExpression> Expressions, 9437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Counter C) { 9537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned Tag = unsigned(C.getKind()); 9637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (C.isExpression()) 9737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Tag += Expressions[C.getExpressionID()].Kind; 9837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned ID = C.getCounterID(); 9937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(ID <= 10037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits)); 10137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines return Tag | (ID << Counter::EncodingTagBits); 10237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 10337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 10437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesstatic void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C, 10537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines raw_ostream &OS) { 10637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(encodeCounter(Expressions, C), OS); 10737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 10837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 10937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hinesvoid CoverageMappingWriter::write(raw_ostream &OS) { 11037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Sort the regions in an ascending order by the file id and the starting 11137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // location. 112ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines std::stable_sort(MappingRegions.begin(), MappingRegions.end()); 11337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Write out the fileid -> filename mapping. 11537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(VirtualFileMapping.size(), OS); 11637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &FileID : VirtualFileMapping) 11737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(FileID, OS); 11837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 11937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Write out the expressions. 12037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions); 12137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines auto MinExpressions = Minimizer.getExpressions(); 12237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(MinExpressions.size(), OS); 12337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (const auto &E : MinExpressions) { 12437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS); 12537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS); 12637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 12737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 12837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Write out the mapping regions. 12937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Split the regions into subarrays where each region in a 13037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // subarray has a fileID which is the index of that subarray. 13137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned PrevLineStart = 0; 13237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned CurrentFileID = ~0U; 13337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) { 13437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (I->FileID != CurrentFileID) { 13537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Ensure that all file ids have at least one mapping region. 13637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(I->FileID == (CurrentFileID + 1)); 13737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Find the number of regions with this file id. 13837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned RegionCount = 1; 13937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J) 14037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines ++RegionCount; 14137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Start a new region sub-array. 14237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(RegionCount, OS); 14337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines 14437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines CurrentFileID = I->FileID; 14537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PrevLineStart = 0; 14637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 14737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Counter Count = Minimizer.adjust(I->Count); 14837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines switch (I->Kind) { 14937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines case CounterMappingRegion::CodeRegion: 15037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines writeCounter(MinExpressions, Count, OS); 15137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 15237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines case CounterMappingRegion::ExpansionRegion: { 15337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Count.isZero()); 15437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(I->ExpandedFileID <= 15537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (std::numeric_limits<unsigned>::max() >> 15637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines Counter::EncodingCounterTagAndExpansionRegionTagBits)); 15737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Mark an expansion region with a set bit that follows the counter tag, 15837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // and pack the expanded file id into the remaining bits. 15937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines unsigned EncodedTagExpandedFileID = 16037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (1 << Counter::EncodingTagBits) | 16137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines (I->ExpandedFileID 16237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines << Counter::EncodingCounterTagAndExpansionRegionTagBits); 16337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(EncodedTagExpandedFileID, OS); 16437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 16537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 16637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines case CounterMappingRegion::SkippedRegion: 16737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(Count.isZero()); 16837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(unsigned(I->Kind) 16937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines << Counter::EncodingCounterTagAndExpansionRegionTagBits, 17037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines OS); 17137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines break; 17237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 17337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(I->LineStart >= PrevLineStart); 17437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(I->LineStart - PrevLineStart, OS); 175ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines encodeULEB128(I->ColumnStart, OS); 17637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(I->LineEnd >= I->LineStart); 17737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(I->LineEnd - I->LineStart, OS); 17837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines encodeULEB128(I->ColumnEnd, OS); 17937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines PrevLineStart = I->LineStart; 18037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines } 18137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines // Ensure that all file ids have at least one mapping region. 18237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines assert(CurrentFileID == (VirtualFileMapping.size() - 1)); 18337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines} 184