Movatterモバイル変換

Go to the documentation of this file.

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-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// This file contains support for writing coverage mapping data for

10// instrumentation based coverage.

11//

12//===----------------------------------------------------------------------===//

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>

26using namespacellvm;

27using namespacecoverage;

29CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter(

30ArrayRef<std::string> Filenames)

31 : Filenames(Filenames) {

32#ifndef NDEBUG

33StringSet<> NameSet;

34for (StringRef Name : Filenames)

35assert(NameSet.insert(Name).second &&"Duplicate filename");

36#endif

37}

39voidCoverageFilenamesSectionWriter::write(raw_ostream &OS,bool Compress) {

40 std::string FilenamesStr;

41 {

42raw_string_ostream FilenamesOS{FilenamesStr};

43for (constauto &Filename : Filenames) {

44encodeULEB128(Filename.size(), FilenamesOS);

45 FilenamesOS << Filename;

46 }

47 }

49SmallVector<uint8_t, 128> CompressedStr;

50bool doCompression = Compress &&compression::zlib::isAvailable() &&

51DoInstrProfNameCompression;

52if (doCompression)

53compression::zlib::compress(arrayRefFromStringRef(FilenamesStr),

54 CompressedStr,

55compression::zlib::BestSizeCompression);

57// ::= <num-filenames>

58// <uncompressed-len>

59// <compressed-len-or-zero>

60// (<compressed-filenames> | <uncompressed-filenames>)

61encodeULEB128(Filenames.size(),OS);

62encodeULEB128(FilenamesStr.size(),OS);

63encodeULEB128(doCompression ? CompressedStr.size() : 0U,OS);

64OS << (doCompression ? toStringRef(CompressedStr) :StringRef(FilenamesStr));

65}

67namespace{

69/// Gather only the expressions that are used by the mapping

70/// regions in this function.

71classCounterExpressionsMinimizer {

72ArrayRef<CounterExpression> Expressions;

73SmallVector<CounterExpression, 16> UsedExpressions;

74 std::vector<unsigned> AdjustedExpressionIDs;

76public:

77 CounterExpressionsMinimizer(ArrayRef<CounterExpression> Expressions,

78ArrayRef<CounterMappingRegion> MappingRegions)

79 : Expressions(Expressions) {

80 AdjustedExpressionIDs.resize(Expressions.size(), 0);

81for (constauto &I : MappingRegions) {

82 mark(I.Count);

83 mark(I.FalseCount);

84 }

85for (constauto &I : MappingRegions) {

86 gatherUsed(I.Count);

87 gatherUsed(I.FalseCount);

88 }

89 }

91void mark(Counter C) {

92if (!C.isExpression())

93return;

94unsignedID =C.getExpressionID();

95 AdjustedExpressionIDs[ID] = 1;

96 mark(Expressions[ID].LHS);

97 mark(Expressions[ID].RHS);

98 }

100void gatherUsed(Counter C) {

101if (!C.isExpression() || !AdjustedExpressionIDs[C.getExpressionID()])

102return;

103 AdjustedExpressionIDs[C.getExpressionID()] = UsedExpressions.size();

104constauto &E = Expressions[C.getExpressionID()];

105 UsedExpressions.push_back(E);

106 gatherUsed(E.LHS);

107 gatherUsed(E.RHS);

108 }

109

110ArrayRef<CounterExpression> getExpressions() const{return UsedExpressions; }

111

112 /// Adjust the given counter to correctly transition from the old

113 /// expression ids to the new expression ids.

114Counter adjust(Counter C) const{

115if (C.isExpression())

116C =Counter::getExpression(AdjustedExpressionIDs[C.getExpressionID()]);

117returnC;

118 }

119};

120

121}// end anonymous namespace

122

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::Zero

128/// Counter::CounterValueReference(1) - A counter with kind

129/// Counter::CounterValueReference

130/// Counter::Expression(2) + CounterExpression::Subtract(0) -

131/// A counter with kind Counter::Expression and an expression

132/// with kind CounterExpression::Subtract

133/// Counter::Expression(2) + CounterExpression::Add(1) -

134/// A counter with kind Counter::Expression and an expression

135/// with kind CounterExpression::Add

136/// Remaining bits - Counter/Expression ID.

137staticunsignedencodeCounter(ArrayRef<CounterExpression> Expressions,

138Counter C) {

139unsignedTag =unsigned(C.getKind());

140if (C.isExpression())

141Tag += Expressions[C.getExpressionID()].Kind;

142unsignedID =C.getCounterID();

143assert(ID <=

144 (std::numeric_limits<unsigned>::max() >>Counter::EncodingTagBits));

145returnTag | (ID <<Counter::EncodingTagBits);

146}

147

148staticvoidwriteCounter(ArrayRef<CounterExpression> Expressions,Counter C,

149raw_ostream &OS) {

150encodeULEB128(encodeCounter(Expressions,C),OS);

151}

152

153voidCoverageMappingWriter::write(raw_ostream &OS) {

154// Check that we don't have any bogus regions.

155assert(all_of(MappingRegions,

156 [](constCounterMappingRegion &CMR) {

157return 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 starting

162// location. Sort by region kinds to ensure stable order for tests.

163llvm::stable_sort(MappingRegions, [](constCounterMappingRegion &LHS,

164constCounterMappingRegion &RHS) {

165if (LHS.FileID !=RHS.FileID)

166returnLHS.FileID <RHS.FileID;

167if (LHS.startLoc() !=RHS.startLoc())

168returnLHS.startLoc() <RHS.startLoc();

169

170// Put `Decision` before `Expansion`.

171auto getKindKey = [](CounterMappingRegion::RegionKind Kind) {

172 return (Kind == CounterMappingRegion::MCDCDecisionRegion

173 ? 2 * CounterMappingRegion::ExpansionRegion - 1

174 : 2 * Kind);

175 };

176

177return getKindKey(LHS.Kind) < getKindKey(RHS.Kind);

178 });

179

180// Write out the fileid -> filename mapping.

181encodeULEB128(VirtualFileMapping.size(),OS);

182for (constauto &FileID : VirtualFileMapping)

183encodeULEB128(FileID,OS);

184

185// Write out the expressions.

186 CounterExpressionsMinimizer Minimizer(Expressions, MappingRegions);

187auto MinExpressions = Minimizer.getExpressions();

188encodeULEB128(MinExpressions.size(),OS);

189for (constauto &E : MinExpressions) {

190writeCounter(MinExpressions, Minimizer.adjust(E.LHS),OS);

191writeCounter(MinExpressions, Minimizer.adjust(E.RHS),OS);

192 }

193

194// Write out the mapping regions.

195// Split the regions into subarrays where each region in a

196// subarray has a fileID which is the index of that subarray.

197unsigned PrevLineStart = 0;

198unsigned CurrentFileID = ~0U;

199for (autoI = MappingRegions.begin(), E = MappingRegions.end();I != E; ++I) {

200if (I->FileID != CurrentFileID) {

201// Ensure that all file ids have at least one mapping region.

202assert(I->FileID == (CurrentFileID + 1));

203// Find the number of regions with this file id.

204unsigned RegionCount = 1;

205for (auto J =I + 1; J != E &&I->FileID == J->FileID; ++J)

206 ++RegionCount;

207// Start a new region sub-array.

208encodeULEB128(RegionCount,OS);

209

210 CurrentFileID =I->FileID;

211 PrevLineStart = 0;

212 }

213Counter Count = Minimizer.adjust(I->Count);

214Counter FalseCount = Minimizer.adjust(I->FalseCount);

215bool ParamsShouldBeNull =true;

216switch (I->Kind) {

217caseCounterMappingRegion::CodeRegion:

218caseCounterMappingRegion::GapRegion:

219writeCounter(MinExpressions, Count,OS);

220break;

221caseCounterMappingRegion::ExpansionRegion: {

222assert(Count.isZero());

223assert(I->ExpandedFileID <=

224 (std::numeric_limits<unsigned>::max() >>

225Counter::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.

228unsigned EncodedTagExpandedFileID =

229 (1 <<Counter::EncodingTagBits) |

230 (I->ExpandedFileID

231 <<Counter::EncodingCounterTagAndExpansionRegionTagBits);

232encodeULEB128(EncodedTagExpandedFileID,OS);

233break;

234 }

235caseCounterMappingRegion::SkippedRegion:

236assert(Count.isZero());

237encodeULEB128(unsigned(I->Kind)

238 <<Counter::EncodingCounterTagAndExpansionRegionTagBits,

239OS);

240break;

241caseCounterMappingRegion::BranchRegion:

242encodeULEB128(unsigned(I->Kind)

243 <<Counter::EncodingCounterTagAndExpansionRegionTagBits,

244OS);

245writeCounter(MinExpressions, Count,OS);

246writeCounter(MinExpressions, FalseCount,OS);

247break;

248caseCounterMappingRegion::MCDCBranchRegion:

249encodeULEB128(unsigned(I->Kind)

250 <<Counter::EncodingCounterTagAndExpansionRegionTagBits,

251OS);

252writeCounter(MinExpressions, Count,OS);

253writeCounter(MinExpressions, FalseCount,OS);

254 {

255// They are written as internal values plus 1.

256constauto &BranchParams =I->getBranchParams();

257 ParamsShouldBeNull =false;

258unsigned ID1 = BranchParams.ID + 1;

259unsigned TID1 = BranchParams.Conds[true] + 1;

260unsigned FID1 = BranchParams.Conds[false] + 1;

261encodeULEB128(ID1,OS);

262encodeULEB128(TID1,OS);

263encodeULEB128(FID1,OS);

264 }

265break;

266caseCounterMappingRegion::MCDCDecisionRegion:

267encodeULEB128(unsigned(I->Kind)

268 <<Counter::EncodingCounterTagAndExpansionRegionTagBits,

269OS);

270 {

271constauto &DecisionParams =I->getDecisionParams();

272 ParamsShouldBeNull =false;

273encodeULEB128(static_cast<unsigned>(DecisionParams.BitmapIdx),OS);

274encodeULEB128(static_cast<unsigned>(DecisionParams.NumConditions),OS);

275 }

276break;

277 }

278assert(I->LineStart >= PrevLineStart);

279encodeULEB128(I->LineStart - PrevLineStart,OS);

280encodeULEB128(I->ColumnStart,OS);

281assert(I->LineEnd >=I->LineStart);

282encodeULEB128(I->LineEnd -I->LineStart,OS);

283encodeULEB128(I->ColumnEnd,OS);

284 PrevLineStart =I->LineStart;

285assert((!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.

290assert(CurrentFileID == (VirtualFileMapping.size() - 1));

291}

292

293voidTestingFormatWriter::write(raw_ostream &OS,TestingFormatVersion Version) {

294auto ByteSwap = [](uint64_t N) {

295return support::endian::byte_swap<uint64_t, llvm::endianness::little>(N);

296 };

297

298// Output a 64bit magic number.

299auto Magic = ByteSwap(TestingFormatMagic);

300OS.write(reinterpret_cast<char *>(&Magic),sizeof(Magic));

301

302// Output a 64bit version field.

303auto VersionLittle = ByteSwap(uint64_t(Version));

304OS.write(reinterpret_cast<char *>(&VersionLittle),sizeof(VersionLittle));

305

306// Output the ProfileNames data.

307encodeULEB128(ProfileNamesData.size(),OS);

308encodeULEB128(ProfileNamesAddr,OS);

309OS << ProfileNamesData;

310

311// Version2 adds an extra field to indicate the size of the

312// CoverageMappingData.

313if (Version ==TestingFormatVersion::Version2)

314encodeULEB128(CoverageMappingData.size(),OS);

315

316// Coverage mapping data is expected to have an alignment of 8.

317for (unsigned Pad =offsetToAlignment(OS.tell(),Align(8)); Pad; --Pad)

318OS.write(uint8_t(0));

319OS << CoverageMappingData;

320

321// Coverage records data is expected to have an alignment of 8.

322for (unsigned Pad =offsetToAlignment(OS.tell(),Align(8)); Pad; --Pad)

323OS.write(uint8_t(0));

324OS << CoverageRecordsData;

325}

ArrayRef.h

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

Compression.h

writeCounter

static void writeCounter(ArrayRef< CounterExpression > Expressions, Counter C, raw_ostream &OS)

Definition:CoverageMappingWriter.cpp:148

encodeCounter

static unsigned encodeCounter(ArrayRef< CounterExpression > Expressions, Counter C)

Encode the counter.

Definition:CoverageMappingWriter.cpp:137

CoverageMappingWriter.h

Name

std::string Name

Definition:ELFObjHandler.cpp:77

InstrProf.h

LEB128.h

#define I(x, y, z)

Definition:MD5.cpp:58

if(PassOpts->AAPipeline)

Definition:PassBuilderBindings.cpp:64

assert

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

raw_pwrite_stream & OS

Definition:SampleProfWriter.cpp:51

SmallVector.h

This file defines the SmallVector class.

StringExtras.h

This file contains some functions that are useful when dealing with strings.

RHS

Value * RHS

Definition:X86PartialReduction.cpp:74

LHS

Value * LHS

Definition:X86PartialReduction.cpp:73

llvm::ArrayRef

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

Definition:ArrayRef.h:41

llvm::ArrayRef::size

size_t size() const

size - Get the array size.

Definition:ArrayRef.h:168

llvm::SmallVectorBase::size

size_t size() const

Definition:SmallVector.h:78

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition:SmallVector.h:413

llvm::SmallVector

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

Definition:SmallVector.h:1196

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition:StringRef.h:51

llvm::StringRef::size

constexpr size_t size() const

size - Get the string size.

Definition:StringRef.h:150

llvm::StringSet

StringSet - A wrapper for StringMap that provides set-like functionality.

Definition:StringSet.h:23

llvm::StringSet::insert

std::pair< typename Base::iterator, bool > insert(StringRef key)

Definition:StringSet.h:38

llvm::coverage::CoverageFilenamesSectionWriter::write

void write(raw_ostream &OS, bool Compress=true)

Write encoded filenames to the given output stream.

Definition:CoverageMappingWriter.cpp:39

llvm::coverage::CoverageFilenamesSectionWriter::CoverageFilenamesSectionWriter

CoverageFilenamesSectionWriter(ArrayRef< std::string > Filenames)

Definition:CoverageMappingWriter.cpp:29

llvm::coverage::CoverageMappingWriter::write

void write(raw_ostream &OS)

Write encoded coverage mapping data to the given output stream.

Definition:CoverageMappingWriter.cpp:153

llvm::coverage::TestingFormatWriter::write

void write(raw_ostream &OS, TestingFormatVersion Version=TestingFormatVersion::CurrentVersion)

Encode to the given output stream.

Definition:CoverageMappingWriter.cpp:293

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition:raw_ostream.h:52

llvm::raw_ostream::tell

uint64_t tell() const

tell - Return the current offset with the file.

Definition:raw_ostream.h:147

llvm::raw_ostream::write

raw_ostream & write(unsigned char C)

Definition:raw_ostream.cpp:225

llvm::raw_string_ostream

A raw_ostream that writes to an std::string.

Definition:raw_ostream.h:661

Definition:AVRAsmBackend.cpp:30

llvm::CallingConv::C

@ C

The default llvm calling convention, compatible with C.

Definition:CallingConv.h:34

llvm::CallingConv::ID

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

Definition:CallingConv.h:24

llvm::compression::zlib::compress

void compress(ArrayRef< uint8_t > Input, SmallVectorImpl< uint8_t > &CompressedBuffer, int Level=DefaultCompression)

Definition:Compression.cpp:147

llvm::compression::zlib::isAvailable

bool isAvailable()

Definition:Compression.cpp:146

llvm::compression::zlib::BestSizeCompression

constexpr int BestSizeCompression

Definition:Compression.h:39

llvm::coverage::TestingFormatVersion

TestingFormatVersion

Definition:CoverageMapping.h:1442

llvm::coverage::TestingFormatVersion::Version2

@ Version2

llvm::coverage::TestingFormatMagic

constexpr uint64_t TestingFormatMagic

Definition:CoverageMapping.h:1440

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition:AddressRanges.h:18

llvm::stable_sort

void stable_sort(R &&Range)

Definition:STLExtras.h:2037

llvm::all_of

bool all_of(R &&range, UnaryPredicate P)

Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.

Definition:STLExtras.h:1739

llvm::DoInstrProfNameCompression

cl::opt< bool > DoInstrProfNameCompression

llvm::offsetToAlignment

uint64_t offsetToAlignment(uint64_t Value, Align Alignment)

Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...

Definition:Alignment.h:197

llvm::HighlightColor::Tag

@ Tag

llvm::encodeULEB128

unsigned encodeULEB128(uint64_t Value, raw_ostream &OS, unsigned PadTo=0)

Utility function to encode a ULEB128 value to an output stream.

Definition:LEB128.h:80

llvm::Version

@ Version

Definition:PGOCtxProfWriter.h:22

raw_ostream.h

#define N

llvm::Align

This struct is a compact representation of a valid (non-zero power of two) alignment.

Definition:Alignment.h:39

llvm::coverage::CounterMappingRegion

A Counter mapping region associates a source range with a specific counter.

Definition:CoverageMapping.h:231

llvm::coverage::CounterMappingRegion::endLoc

LineColPair endLoc() const

Definition:CoverageMapping.h:368

llvm::coverage::CounterMappingRegion::startLoc

LineColPair startLoc() const

Definition:CoverageMapping.h:364

llvm::coverage::CounterMappingRegion::RegionKind

RegionKind

Definition:CoverageMapping.h:232

llvm::coverage::CounterMappingRegion::ExpansionRegion

@ ExpansionRegion

An ExpansionRegion represents a file expansion region that associates a source range with the expansi...

Definition:CoverageMapping.h:239

llvm::coverage::CounterMappingRegion::MCDCDecisionRegion

@ MCDCDecisionRegion

A DecisionRegion represents a top-level boolean expression and is associated with a variable length b...

Definition:CoverageMapping.h:256

llvm::coverage::CounterMappingRegion::MCDCBranchRegion

@ MCDCBranchRegion

A Branch Region can be extended to include IDs to facilitate MC/DC.

Definition:CoverageMapping.h:259

llvm::coverage::CounterMappingRegion::SkippedRegion

@ SkippedRegion

A SkippedRegion represents a source range with code that was skipped by a preprocessor or similar mea...

Definition:CoverageMapping.h:243

llvm::coverage::CounterMappingRegion::GapRegion

@ GapRegion

A GapRegion is like a CodeRegion, but its count is only set as the line execution count when its the ...

Definition:CoverageMapping.h:247

llvm::coverage::CounterMappingRegion::BranchRegion

@ BranchRegion

A BranchRegion represents leaf-level boolean expressions and is associated with two counters,...

Definition:CoverageMapping.h:252

llvm::coverage::CounterMappingRegion::CodeRegion

@ CodeRegion

A CodeRegion associates some code with a counter.

Definition:CoverageMapping.h:234

llvm::coverage::Counter

A Counter is an abstract value that describes how to compute the execution count for a region of code...

Definition:CoverageMapping.h:107

llvm::coverage::Counter::EncodingTagBits

static const unsigned EncodingTagBits

Definition:CoverageMapping.h:111

llvm::coverage::Counter::isZero

bool isZero() const

Definition:CoverageMapping.h:127

llvm::coverage::Counter::EncodingCounterTagAndExpansionRegionTagBits

static const unsigned EncodingCounterTagAndExpansionRegionTagBits

Definition:CoverageMapping.h:113

llvm::coverage::Counter::getExpression

static Counter getExpression(unsigned ExpressionId)

Return the counter that corresponds to a specific addition counter expression.

Definition:CoverageMapping.h:157