326 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains support for writing coverage mapping data for10// 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/ADT/StringExtras.h"18#include "llvm/ProfileData/InstrProf.h"19#include "llvm/Support/Compression.h"20#include "llvm/Support/LEB128.h"21#include "llvm/Support/raw_ostream.h"22#include <cassert>23#include <limits>24#include <vector>25 26using namespace llvm;27using namespace coverage;28 29CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter(30 ArrayRef<std::string> Filenames)31 : Filenames(Filenames) {32#ifndef NDEBUG33 StringSet<> NameSet;34 for (StringRef Name : Filenames)35 assert(NameSet.insert(Name).second && "Duplicate filename");36#endif37}38 39void CoverageFilenamesSectionWriter::write(raw_ostream &OS, bool Compress) {40 std::string FilenamesStr;41 {42 raw_string_ostream FilenamesOS{FilenamesStr};43 for (const auto &Filename : Filenames) {44 encodeULEB128(Filename.size(), FilenamesOS);45 FilenamesOS << Filename;46 }47 }48 49 SmallVector<uint8_t, 128> CompressedStr;50 bool doCompression = Compress && compression::zlib::isAvailable() &&51 DoInstrProfNameCompression;52 if (doCompression)53 compression::zlib::compress(arrayRefFromStringRef(FilenamesStr),54 CompressedStr,55 compression::zlib::BestSizeCompression);56 57 // ::= <num-filenames>58 // <uncompressed-len>59 // <compressed-len-or-zero>60 // (<compressed-filenames> | <uncompressed-filenames>)61 encodeULEB128(Filenames.size(), OS);62 encodeULEB128(FilenamesStr.size(), OS);63 encodeULEB128(doCompression ? CompressedStr.size() : 0U, OS);64 OS << (doCompression ? toStringRef(CompressedStr) : StringRef(FilenamesStr));65}66 67namespace {68 69/// Gather only the expressions that are used by the mapping70/// regions in this function.71class CounterExpressionsMinimizer {72 ArrayRef<CounterExpression> Expressions;73 SmallVector<CounterExpression, 16> UsedExpressions;74 std::vector<unsigned> AdjustedExpressionIDs;75 76public:77 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,78 ArrayRef<CounterMappingRegion> MappingRegions)79 : Expressions(Expressions) {80 AdjustedExpressionIDs.resize(Expressions.size(), 0);81 for (const auto &I : MappingRegions) {82 mark(I.Count);83 mark(I.FalseCount);84 }85 for (const auto &I : MappingRegions) {86 gatherUsed(I.Count);87 gatherUsed(I.FalseCount);88 }89 }90 91 void mark(Counter C) {92 if (!C.isExpression())93 return;94 unsigned ID = C.getExpressionID();95 AdjustedExpressionIDs[ID] = 1;96 mark(Expressions[ID].LHS);97 mark(Expressions[ID].RHS);98 }99 100 void gatherUsed(Counter C) {101 if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])102 return;103 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();104 const auto &E = Expressions[C.getExpressionID()];105 UsedExpressions.push_back(E);106 gatherUsed(E.LHS);107 gatherUsed(E.RHS);108 }109 110 ArrayRef<CounterExpression> getExpressions() const { return UsedExpressions; }111 112 /// Adjust the given counter to correctly transition from the old113 /// expression ids to the new expression ids.114 Counter adjust(Counter C) const {115 if (C.isExpression())116 C = Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);117 return C;118 }119};120 121} // end anonymous namespace122 123/// Encode the counter.124///125/// The encoding uses the following format:126/// Low 2 bits - Tag:127/// Counter::Zero(0) - A Counter with kind Counter::Zero128/// Counter::CounterValueReference(1) - A counter with kind129/// Counter::CounterValueReference130/// Counter::Expression(2) + CounterExpression::Subtract(0) -131/// A counter with kind Counter::Expression and an expression132/// with kind CounterExpression::Subtract133/// Counter::Expression(2) + CounterExpression::Add(1) -134/// A counter with kind Counter::Expression and an expression135/// with kind CounterExpression::Add136/// Remaining bits - Counter/Expression ID.137static unsigned encodeCounter(ArrayRef<CounterExpression> Expressions,138 Counter C) {139 unsigned Tag = unsigned(C.getKind());140 if (C.isExpression())141 Tag += Expressions[C.getExpressionID()].Kind;142 unsigned ID = C.getCounterID();143 assert(ID <=144 (std::numeric_limits<unsigned>::max() >> Counter::EncodingTagBits));145 return Tag | (ID << Counter::EncodingTagBits);146}147 148static void writeCounter(ArrayRef<CounterExpression> Expressions, Counter C,149 raw_ostream &OS) {150 encodeULEB128(encodeCounter(Expressions, C), OS);151}152 153void CoverageMappingWriter::write(raw_ostream &OS) {154 // Check that we don't have any bogus regions.155 assert(all_of(MappingRegions,156 [](const CounterMappingRegion &CMR) {157 return CMR.startLoc() <= CMR.endLoc();158 }) &&159 "Source region does not begin before it ends");160 161 // Sort the regions in an ascending order by the file id and the starting162 // location. Sort by region kinds to ensure stable order for tests.163 llvm::stable_sort(MappingRegions, [](const CounterMappingRegion &LHS,164 const CounterMappingRegion &RHS) {165 if (LHS.FileID != RHS.FileID)166 return LHS.FileID < RHS.FileID;167 if (LHS.startLoc() != RHS.startLoc())168 return LHS.startLoc() < RHS.startLoc();169 170 // Put `Decision` before `Expansion`.171 auto getKindKey = [](CounterMappingRegion::RegionKind Kind) {172 return (Kind == CounterMappingRegion::MCDCDecisionRegion173 ? 2 * CounterMappingRegion::ExpansionRegion - 1174 : 2 * Kind);175 };176 177 return getKindKey(LHS.Kind) < getKindKey(RHS.Kind);178 });179 180 // Write out the fileid -> filename mapping.181 encodeULEB128(VirtualFileMapping.size(), OS);182 for (const auto &FileID : VirtualFileMapping)183 encodeULEB128(FileID, OS);184 185 // Write out the expressions.186 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);187 auto MinExpressions = Minimizer.getExpressions();188 encodeULEB128(MinExpressions.size(), OS);189 for (const auto &E : MinExpressions) {190 writeCounter(MinExpressions, Minimizer.adjust(E.LHS), OS);191 writeCounter(MinExpressions, Minimizer.adjust(E.RHS), OS);192 }193 194 // Write out the mapping regions.195 // Split the regions into subarrays where each region in a196 // subarray has a fileID which is the index of that subarray.197 unsigned PrevLineStart = 0;198 unsigned CurrentFileID = ~0U;199 for (auto I = MappingRegions.begin(), E = MappingRegions.end(); I != E; ++I) {200 if (I->FileID != CurrentFileID) {201 // Ensure that all file ids have at least one mapping region.202 assert(I->FileID == (CurrentFileID + 1));203 // Find the number of regions with this file id.204 unsigned RegionCount = 1;205 for (auto J = I + 1; J != E && I->FileID == J->FileID; ++J)206 ++RegionCount;207 // Start a new region sub-array.208 encodeULEB128(RegionCount, OS);209 210 CurrentFileID = I->FileID;211 PrevLineStart = 0;212 }213 Counter Count = Minimizer.adjust(I->Count);214 Counter FalseCount = Minimizer.adjust(I->FalseCount);215 bool ParamsShouldBeNull = true;216 switch (I->Kind) {217 case CounterMappingRegion::CodeRegion:218 case CounterMappingRegion::GapRegion:219 writeCounter(MinExpressions, Count, OS);220 break;221 case CounterMappingRegion::ExpansionRegion: {222 assert(Count.isZero());223 assert(I->ExpandedFileID <=224 (std::numeric_limits<unsigned>::max() >>225 Counter::EncodingCounterTagAndExpansionRegionTagBits));226 // Mark an expansion region with a set bit that follows the counter tag,227 // and pack the expanded file id into the remaining bits.228 unsigned EncodedTagExpandedFileID =229 (1 << Counter::EncodingTagBits) |230 (I->ExpandedFileID231 << Counter::EncodingCounterTagAndExpansionRegionTagBits);232 encodeULEB128(EncodedTagExpandedFileID, OS);233 break;234 }235 case CounterMappingRegion::SkippedRegion:236 assert(Count.isZero());237 encodeULEB128(unsigned(I->Kind)238 << Counter::EncodingCounterTagAndExpansionRegionTagBits,239 OS);240 break;241 case CounterMappingRegion::BranchRegion:242 encodeULEB128(unsigned(I->Kind)243 << Counter::EncodingCounterTagAndExpansionRegionTagBits,244 OS);245 writeCounter(MinExpressions, Count, OS);246 writeCounter(MinExpressions, FalseCount, OS);247 break;248 case CounterMappingRegion::MCDCBranchRegion:249 encodeULEB128(unsigned(I->Kind)250 << Counter::EncodingCounterTagAndExpansionRegionTagBits,251 OS);252 writeCounter(MinExpressions, Count, OS);253 writeCounter(MinExpressions, FalseCount, OS);254 {255 // They are written as internal values plus 1.256 const auto &BranchParams = I->getBranchParams();257 ParamsShouldBeNull = false;258 unsigned ID1 = BranchParams.ID + 1;259 unsigned TID1 = BranchParams.Conds[true] + 1;260 unsigned FID1 = BranchParams.Conds[false] + 1;261 encodeULEB128(ID1, OS);262 encodeULEB128(TID1, OS);263 encodeULEB128(FID1, OS);264 }265 break;266 case CounterMappingRegion::MCDCDecisionRegion:267 encodeULEB128(unsigned(I->Kind)268 << Counter::EncodingCounterTagAndExpansionRegionTagBits,269 OS);270 {271 const auto &DecisionParams = I->getDecisionParams();272 ParamsShouldBeNull = false;273 encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx), OS);274 encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions), OS);275 }276 break;277 }278 assert(I->LineStart >= PrevLineStart);279 encodeULEB128(I->LineStart - PrevLineStart, OS);280 encodeULEB128(I->ColumnStart, OS);281 assert(I->LineEnd >= I->LineStart);282 encodeULEB128(I->LineEnd - I->LineStart, OS);283 encodeULEB128(I->ColumnEnd, OS);284 PrevLineStart = I->LineStart;285 assert((!ParamsShouldBeNull || std::get_if<0>(&I->MCDCParams)) &&286 "MCDCParams should be empty");287 (void)ParamsShouldBeNull;288 }289 // Ensure that all file ids have at least one mapping region.290 assert(CurrentFileID == (VirtualFileMapping.size() - 1));291}292 293void TestingFormatWriter::write(raw_ostream &OS, TestingFormatVersion Version) {294 auto ByteSwap = [](uint64_t N) {295 return support::endian::byte_swap<uint64_t>(N, llvm::endianness::little);296 };297 298 // Output a 64bit magic number.299 auto Magic = ByteSwap(TestingFormatMagic);300 OS.write(reinterpret_cast<char *>(&Magic), sizeof(Magic));301 302 // Output a 64bit version field.303 auto VersionLittle = ByteSwap(uint64_t(Version));304 OS.write(reinterpret_cast<char *>(&VersionLittle), sizeof(VersionLittle));305 306 // Output the ProfileNames data.307 encodeULEB128(ProfileNamesData.size(), OS);308 encodeULEB128(ProfileNamesAddr, OS);309 OS << ProfileNamesData;310 311 // Version2 adds an extra field to indicate the size of the312 // CoverageMappingData.313 if (Version == TestingFormatVersion::Version2)314 encodeULEB128(CoverageMappingData.size(), OS);315 316 // Coverage mapping data is expected to have an alignment of 8.317 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)318 OS.write(uint8_t(0));319 OS << CoverageMappingData;320 321 // Coverage records data is expected to have an alignment of 8.322 for (unsigned Pad = offsetToAlignment(OS.tell(), Align(8)); Pad; --Pad)323 OS.write(uint8_t(0));324 OS << CoverageRecordsData;325}326