CoverageMappingGen.cpp source code [clang_source_code/lib/CodeGen/CoverageMappingGen.cpp]

1	//===--- CoverageMappingGen.cpp - Coverage mapping generation ---- C++ --===//
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	// Instrumentation-based code coverage mapping generator
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "CoverageMappingGen.h"
14	#include "CodeGenFunction.h"
15	#include "clang/AST/StmtVisitor.h"
16	#include "clang/Lex/Lexer.h"
17	#include "llvm/ADT/SmallSet.h"
18	#include "llvm/ADT/StringExtras.h"
19	#include "llvm/ADT/Optional.h"
20	#include "llvm/ProfileData/Coverage/CoverageMapping.h"
21	#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
22	#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
23	#include "llvm/ProfileData/InstrProfReader.h"
24	#include "llvm/Support/FileSystem.h"
25	#include "llvm/Support/Path.h"
26
27	using namespace clang;
28	using namespace CodeGen;
29	using namespace llvm::coverage;
30
31	void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) {
32	SkippedRanges.push_back(Range);
33	}
34
35	namespace {
36
37	/// A region of source code that can be mapped to a counter.
38	class SourceMappingRegion {
39	Counter Count;
40
41	/// The region's starting location.
42	Optional<SourceLocation> LocStart;
43
44	/// The region's ending location.
45	Optional<SourceLocation> LocEnd;
46
47	/// Whether this region should be emitted after its parent is emitted.
48	bool DeferRegion;
49
50	/// Whether this region is a gap region. The count from a gap region is set
51	/// as the line execution count if there are no other regions on the line.
52	bool GapRegion;
53
54	public:
55	SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart,
56	Optional<SourceLocation> LocEnd, bool DeferRegion = false,
57	bool GapRegion = false)
58	: Count(Count), LocStart(LocStart), LocEnd(LocEnd),
59	DeferRegion(DeferRegion), GapRegion(GapRegion) {}
60
61	const Counter &getCounter() const { return Count; }
62
63	void setCounter(Counter C) { Count = C; }
64
65	bool hasStartLoc() const { return LocStart.hasValue(); }
66
67	void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
68
69	SourceLocation getBeginLoc() const {
70	(0) . __assert_fail ("LocStart && \"Region has no start location\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 70, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(LocStart && "Region has no start location");
71	return *LocStart;
72	}
73
74	bool hasEndLoc() const { return LocEnd.hasValue(); }
75
76	void setEndLoc(SourceLocation Loc) {
77	(0) . __assert_fail ("Loc.isValid() && \"Setting an invalid end location\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 77, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Loc.isValid() && "Setting an invalid end location");
78	LocEnd = Loc;
79	}
80
81	SourceLocation getEndLoc() const {
82	(0) . __assert_fail ("LocEnd && \"Region has no end location\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 82, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(LocEnd && "Region has no end location");
83	return *LocEnd;
84	}
85
86	bool isDeferred() const { return DeferRegion; }
87
88	void setDeferred(bool Deferred) { DeferRegion = Deferred; }
89
90	bool isGap() const { return GapRegion; }
91
92	void setGap(bool Gap) { GapRegion = Gap; }
93	};
94
95	/// Spelling locations for the start and end of a source region.
96	struct SpellingRegion {
97	/// The line where the region starts.
98	unsigned LineStart;
99
100	/// The column where the region starts.
101	unsigned ColumnStart;
102
103	/// The line where the region ends.
104	unsigned LineEnd;
105
106	/// The column where the region ends.
107	unsigned ColumnEnd;
108
109	SpellingRegion(SourceManager &SM, SourceLocation LocStart,
110	SourceLocation LocEnd) {
111	LineStart = SM.getSpellingLineNumber(LocStart);
112	ColumnStart = SM.getSpellingColumnNumber(LocStart);
113	LineEnd = SM.getSpellingLineNumber(LocEnd);
114	ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
115	}
116
117	SpellingRegion(SourceManager &SM, SourceMappingRegion &R)
118	: SpellingRegion(SM, R.getBeginLoc(), R.getEndLoc()) {}
119
120	/// Check if the start and end locations appear in source order, i.e
121	/// top->bottom, left->right.
122	bool isInSourceOrder() const {
123	return (LineStart < LineEnd) \|\|
124	(LineStart == LineEnd && ColumnStart <= ColumnEnd);
125	}
126	};
127
128	/// Provides the common functionality for the different
129	/// coverage mapping region builders.
130	class CoverageMappingBuilder {
131	public:
132	CoverageMappingModuleGen &CVM;
133	SourceManager &SM;
134	const LangOptions &LangOpts;
135
136	private:
137	/// Map of clang's FileIDs to IDs used for coverage mapping.
138	llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
139	FileIDMapping;
140
141	public:
142	/// The coverage mapping regions for this function
143	llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
144	/// The source mapping regions for this function.
145	std::vector<SourceMappingRegion> SourceRegions;
146
147	/// A set of regions which can be used as a filter.
148	///
149	/// It is produced by emitExpansionRegions() and is used in
150	/// emitSourceRegions() to suppress producing code regions if
151	/// the same area is covered by expansion regions.
152	typedef llvm::SmallSet<std::pair<SourceLocation, SourceLocation>, 8>
153	SourceRegionFilter;
154
155	CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
156	const LangOptions &LangOpts)
157	: CVM(CVM), SM(SM), LangOpts(LangOpts) {}
158
159	/// Return the precise end location for the given token.
160	SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
161	// We avoid getLocForEndOfToken here, because it doesn't do what we want for
162	// macro locations, which we just treat as expanded files.
163	unsigned TokLen =
164	Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts);
165	return Loc.getLocWithOffset(TokLen);
166	}
167
168	/// Return the start location of an included file or expanded macro.
169	SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
170	if (Loc.isMacroID())
171	return Loc.getLocWithOffset(-SM.getFileOffset(Loc));
172	return SM.getLocForStartOfFile(SM.getFileID(Loc));
173	}
174
175	/// Return the end location of an included file or expanded macro.
176	SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
177	if (Loc.isMacroID())
178	return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) -
179	SM.getFileOffset(Loc));
180	return SM.getLocForEndOfFile(SM.getFileID(Loc));
181	}
182
183	/// Find out where the current file is included or macro is expanded.
184	SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
185	return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getBegin()
186	: SM.getIncludeLoc(SM.getFileID(Loc));
187	}
188
189	/// Return true if \c Loc is a location in a built-in macro.
190	bool isInBuiltin(SourceLocation Loc) {
191	return SM.getBufferName(SM.getSpellingLoc(Loc)) == "<built-in>";
192	}
193
194	/// Check whether \c Loc is included or expanded from \c Parent.
195	bool isNestedIn(SourceLocation Loc, FileID Parent) {
196	do {
197	Loc = getIncludeOrExpansionLoc(Loc);
198	if (Loc.isInvalid())
199	return false;
200	} while (!SM.isInFileID(Loc, Parent));
201	return true;
202	}
203
204	/// Get the start of \c S ignoring macro arguments and builtin macros.
205	SourceLocation getStart(const Stmt *S) {
206	SourceLocation Loc = S->getBeginLoc();
207	while (SM.isMacroArgExpansion(Loc) \|\| isInBuiltin(Loc))
208	Loc = SM.getImmediateExpansionRange(Loc).getBegin();
209	return Loc;
210	}
211
212	/// Get the end of \c S ignoring macro arguments and builtin macros.
213	SourceLocation getEnd(const Stmt *S) {
214	SourceLocation Loc = S->getEndLoc();
215	while (SM.isMacroArgExpansion(Loc) \|\| isInBuiltin(Loc))
216	Loc = SM.getImmediateExpansionRange(Loc).getBegin();
217	return getPreciseTokenLocEnd(Loc);
218	}
219
220	/// Find the set of files we have regions for and assign IDs
221	///
222	/// Fills \c Mapping with the virtual file mapping needed to write out
223	/// coverage and collects the necessary file information to emit source and
224	/// expansion regions.
225	void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) {
226	FileIDMapping.clear();
227
228	llvm::SmallSet<FileID, 8> Visited;
229	SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
230	for (const auto &Region : SourceRegions) {
231	SourceLocation Loc = Region.getBeginLoc();
232	FileID File = SM.getFileID(Loc);
233	if (!Visited.insert(File).second)
234	continue;
235
236	// Do not map FileID's associated with system headers.
237	if (SM.isInSystemHeader(SM.getSpellingLoc(Loc)))
238	continue;
239
240	unsigned Depth = 0;
241	for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
242	Parent.isValid(); Parent = getIncludeOrExpansionLoc(Parent))
243	++Depth;
244	FileLocs.push_back(std::make_pair(Loc, Depth));
245	}
246	std::stable_sort(FileLocs.begin(), FileLocs.end(), llvm::less_second());
247
248	for (const auto &FL : FileLocs) {
249	SourceLocation Loc = FL.first;
250	FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
251	auto Entry = SM.getFileEntryForID(SpellingFile);
252	if (!Entry)
253	continue;
254
255	FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc);
256	Mapping.push_back(CVM.getFileID(Entry));
257	}
258	}
259
260	/// Get the coverage mapping file ID for \c Loc.
261	///
262	/// If such file id doesn't exist, return None.
263	Optional<unsigned> getCoverageFileID(SourceLocation Loc) {
264	auto Mapping = FileIDMapping.find(SM.getFileID(Loc));
265	if (Mapping != FileIDMapping.end())
266	return Mapping->second.first;
267	return None;
268	}
269
270	/// Gather all the regions that were skipped by the preprocessor
271	/// using the constructs like #if.
272	void gatherSkippedRegions() {
273	/// An array of the minimum lineStarts and the maximum lineEnds
274	/// for mapping regions from the appropriate source files.
275	llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
276	FileLineRanges.resize(
277	FileIDMapping.size(),
278	std::make_pair(std::numeric_limits<unsigned>::max(), 0));
279	for (const auto &R : MappingRegions) {
280	FileLineRanges[R.FileID].first =
281	std::min(FileLineRanges[R.FileID].first, R.LineStart);
282	FileLineRanges[R.FileID].second =
283	std::max(FileLineRanges[R.FileID].second, R.LineEnd);
284	}
285
286	auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
287	for (const auto &I : SkippedRanges) {
288	auto LocStart = I.getBegin();
289	auto LocEnd = I.getEnd();
290	(0) . __assert_fail ("SM.isWrittenInSameFile(LocStart, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 291, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
291	(0) . __assert_fail ("SM.isWrittenInSameFile(LocStart, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 291, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "region spans multiple files");
292
293	auto CovFileID = getCoverageFileID(LocStart);
294	if (!CovFileID)
295	continue;
296	SpellingRegion SR{SM, LocStart, LocEnd};
297	auto Region = CounterMappingRegion::makeSkipped(
298	*CovFileID, SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd);
299	// Make sure that we only collect the regions that are inside
300	// the source code of this function.
301	if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
302	Region.LineEnd <= FileLineRanges[*CovFileID].second)
303	MappingRegions.push_back(Region);
304	}
305	}
306
307	/// Generate the coverage counter mapping regions from collected
308	/// source regions.
309	void emitSourceRegions(const SourceRegionFilter &Filter) {
310	for (const auto &Region : SourceRegions) {
311	(0) . __assert_fail ("Region.hasEndLoc() && \"incomplete region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 311, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Region.hasEndLoc() && "incomplete region");
312
313	SourceLocation LocStart = Region.getBeginLoc();
314	(0) . __assert_fail ("SM.getFileID(LocStart).isValid() && \"region in invalid file\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 314, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
315
316	// Ignore regions from system headers.
317	if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart)))
318	continue;
319
320	auto CovFileID = getCoverageFileID(LocStart);
321	// Ignore regions that don't have a file, such as builtin macros.
322	if (!CovFileID)
323	continue;
324
325	SourceLocation LocEnd = Region.getEndLoc();
326	(0) . __assert_fail ("SM.isWrittenInSameFile(LocStart, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 327, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
327	(0) . __assert_fail ("SM.isWrittenInSameFile(LocStart, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 327, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "region spans multiple files");
328
329	// Don't add code regions for the area covered by expansion regions.
330	// This not only suppresses redundant regions, but sometimes prevents
331	// creating regions with wrong counters if, for example, a statement's
332	// body ends at the end of a nested macro.
333	if (Filter.count(std::make_pair(LocStart, LocEnd)))
334	continue;
335
336	// Find the spelling locations for the mapping region.
337	SpellingRegion SR{SM, LocStart, LocEnd};
338	(0) . __assert_fail ("SR.isInSourceOrder() && \"region start and end out of order\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 338, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SR.isInSourceOrder() && "region start and end out of order");
339
340	if (Region.isGap()) {
341	MappingRegions.push_back(CounterMappingRegion::makeGapRegion(
342	Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
343	SR.LineEnd, SR.ColumnEnd));
344	} else {
345	MappingRegions.push_back(CounterMappingRegion::makeRegion(
346	Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
347	SR.LineEnd, SR.ColumnEnd));
348	}
349	}
350	}
351
352	/// Generate expansion regions for each virtual file we've seen.
353	SourceRegionFilter emitExpansionRegions() {
354	SourceRegionFilter Filter;
355	for (const auto &FM : FileIDMapping) {
356	SourceLocation ExpandedLoc = FM.second.second;
357	SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc);
358	if (ParentLoc.isInvalid())
359	continue;
360
361	auto ParentFileID = getCoverageFileID(ParentLoc);
362	if (!ParentFileID)
363	continue;
364	auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
365	(0) . __assert_fail ("ExpandedFileID && \"expansion in uncovered file\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 365, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(ExpandedFileID && "expansion in uncovered file");
366
367	SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
368	(0) . __assert_fail ("SM.isWrittenInSameFile(ParentLoc, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 369, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
369	(0) . __assert_fail ("SM.isWrittenInSameFile(ParentLoc, LocEnd) && \"region spans multiple files\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 369, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "region spans multiple files");
370	Filter.insert(std::make_pair(ParentLoc, LocEnd));
371
372	SpellingRegion SR{SM, ParentLoc, LocEnd};
373	(0) . __assert_fail ("SR.isInSourceOrder() && \"region start and end out of order\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 373, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(SR.isInSourceOrder() && "region start and end out of order");
374	MappingRegions.push_back(CounterMappingRegion::makeExpansion(
375	ParentFileID, ExpandedFileID, SR.LineStart, SR.ColumnStart,
376	SR.LineEnd, SR.ColumnEnd));
377	}
378	return Filter;
379	}
380	};
381
382	/// Creates unreachable coverage regions for the functions that
383	/// are not emitted.
384	struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
385	EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
386	const LangOptions &LangOpts)
387	: CoverageMappingBuilder(CVM, SM, LangOpts) {}
388
389	void VisitDecl(const Decl *D) {
390	if (!D->hasBody())
391	return;
392	auto Body = D->getBody();
393	SourceLocation Start = getStart(Body);
394	SourceLocation End = getEnd(Body);
395	if (!SM.isWrittenInSameFile(Start, End)) {
396	// Walk up to find the common ancestor.
397	// Correct the locations accordingly.
398	FileID StartFileID = SM.getFileID(Start);
399	FileID EndFileID = SM.getFileID(End);
400	while (StartFileID != EndFileID && !isNestedIn(End, StartFileID)) {
401	Start = getIncludeOrExpansionLoc(Start);
402	(0) . __assert_fail ("Start.isValid() && \"Declaration start location not nested within a known region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 403, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(Start.isValid() &&
403	(0) . __assert_fail ("Start.isValid() && \"Declaration start location not nested within a known region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 403, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "Declaration start location not nested within a known region");
404	StartFileID = SM.getFileID(Start);
405	}
406	while (StartFileID != EndFileID) {
407	End = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(End));
408	(0) . __assert_fail ("End.isValid() && \"Declaration end location not nested within a known region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 409, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(End.isValid() &&
409	(0) . __assert_fail ("End.isValid() && \"Declaration end location not nested within a known region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 409, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true"> "Declaration end location not nested within a known region");
410	EndFileID = SM.getFileID(End);
411	}
412	}
413	SourceRegions.emplace_back(Counter(), Start, End);
414	}
415
416	/// Write the mapping data to the output stream
417	void write(llvm::raw_ostream &OS) {
418	SmallVector<unsigned, 16> FileIDMapping;
419	gatherFileIDs(FileIDMapping);
420	emitSourceRegions(SourceRegionFilter());
421
422	if (MappingRegions.empty())
423	return;
424
425	CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions);
426	Writer.write(OS);
427	}
428	};
429
430	/// A StmtVisitor that creates coverage mapping regions which map
431	/// from the source code locations to the PGO counters.
432	struct CounterCoverageMappingBuilder
433	: public CoverageMappingBuilder,
434	public ConstStmtVisitor<CounterCoverageMappingBuilder> {
435	/// The map of statements to count values.
436	llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
437
438	/// A stack of currently live regions.
439	std::vector<SourceMappingRegion> RegionStack;
440
441	/// The currently deferred region: its end location and count can be set once
442	/// its parent has been popped from the region stack.
443	Optional<SourceMappingRegion> DeferredRegion;
444
445	CounterExpressionBuilder Builder;
446
447	/// A location in the most recently visited file or macro.
448	///
449	/// This is used to adjust the active source regions appropriately when
450	/// expressions cross file or macro boundaries.
451	SourceLocation MostRecentLocation;
452
453	/// Location of the last terminated region.
454	Optional<std::pair<SourceLocation, size_t>> LastTerminatedRegion;
455
456	/// Return a counter for the subtraction of \c RHS from \c LHS
457	Counter subtractCounters(Counter LHS, Counter RHS) {
458	return Builder.subtract(LHS, RHS);
459	}
460
461	/// Return a counter for the sum of \c LHS and \c RHS.
462	Counter addCounters(Counter LHS, Counter RHS) {
463	return Builder.add(LHS, RHS);
464	}
465
466	Counter addCounters(Counter C1, Counter C2, Counter C3) {
467	return addCounters(addCounters(C1, C2), C3);
468	}
469
470	/// Return the region counter for the given statement.
471	///
472	/// This should only be called on statements that have a dedicated counter.
473	Counter getRegionCounter(const Stmt *S) {
474	return Counter::getCounter(CounterMap[S]);
475	}
476
477	/// Push a region onto the stack.
478	///
479	/// Returns the index on the stack where the region was pushed. This can be
480	/// used with popRegions to exit a "scope", ending the region that was pushed.
481	size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None,
482	Optional<SourceLocation> EndLoc = None) {
483	if (StartLoc) {
484	MostRecentLocation = *StartLoc;
485	completeDeferred(Count, MostRecentLocation);
486	}
487	RegionStack.emplace_back(Count, StartLoc, EndLoc);
488
489	return RegionStack.size() - 1;
490	}
491
492	/// Complete any pending deferred region by setting its end location and
493	/// count, and then pushing it onto the region stack.
494	size_t completeDeferred(Counter Count, SourceLocation DeferredEndLoc) {
495	size_t Index = RegionStack.size();
496	if (!DeferredRegion)
497	return Index;
498
499	// Consume the pending region.
500	SourceMappingRegion DR = DeferredRegion.getValue();
501	DeferredRegion = None;
502
503	// If the region ends in an expansion, find the expansion site.
504	FileID StartFile = SM.getFileID(DR.getBeginLoc());
505	if (SM.getFileID(DeferredEndLoc) != StartFile) {
506	if (isNestedIn(DeferredEndLoc, StartFile)) {
507	do {
508	DeferredEndLoc = getIncludeOrExpansionLoc(DeferredEndLoc);
509	} while (StartFile != SM.getFileID(DeferredEndLoc));
510	} else {
511	return Index;
512	}
513	}
514
515	// The parent of this deferred region ends where the containing decl ends,
516	// so the region isn't useful.
517	if (DR.getBeginLoc() == DeferredEndLoc)
518	return Index;
519
520	// If we're visiting statements in non-source order (e.g switch cases or
521	// a loop condition) we can't construct a sensible deferred region.
522	if (!SpellingRegion(SM, DR.getBeginLoc(), DeferredEndLoc).isInSourceOrder())
523	return Index;
524
525	DR.setGap(true);
526	DR.setCounter(Count);
527	DR.setEndLoc(DeferredEndLoc);
528	handleFileExit(DeferredEndLoc);
529	RegionStack.push_back(DR);
530	return Index;
531	}
532
533	/// Complete a deferred region created after a terminated region at the
534	/// top-level.
535	void completeTopLevelDeferredRegion(Counter Count,
536	SourceLocation DeferredEndLoc) {
537	if (DeferredRegion \|\| !LastTerminatedRegion)
538	return;
539
540	if (LastTerminatedRegion->second != RegionStack.size())
541	return;
542
543	SourceLocation Start = LastTerminatedRegion->first;
544	if (SM.getFileID(Start) != SM.getMainFileID())
545	return;
546
547	SourceMappingRegion DR = RegionStack.back();
548	DR.setStartLoc(Start);
549	DR.setDeferred(false);
550	DeferredRegion = DR;
551	completeDeferred(Count, DeferredEndLoc);
552	}
553
554	size_t locationDepth(SourceLocation Loc) {
555	size_t Depth = 0;
556	while (Loc.isValid()) {
557	Loc = getIncludeOrExpansionLoc(Loc);
558	Depth++;
559	}
560	return Depth;
561	}
562
563	/// Pop regions from the stack into the function's list of regions.
564	///
565	/// Adds all regions from \c ParentIndex to the top of the stack to the
566	/// function's \c SourceRegions.
567	void popRegions(size_t ParentIndex) {
568	(0) . __assert_fail ("RegionStack.size() >= ParentIndex && \"parent not in stack\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 568, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(RegionStack.size() >= ParentIndex && "parent not in stack");
569	bool ParentOfDeferredRegion = false;
570	while (RegionStack.size() > ParentIndex) {
571	SourceMappingRegion &Region = RegionStack.back();
572	if (Region.hasStartLoc()) {
573	SourceLocation StartLoc = Region.getBeginLoc();
574	SourceLocation EndLoc = Region.hasEndLoc()
575	? Region.getEndLoc()
576	: RegionStack[ParentIndex].getEndLoc();
577	size_t StartDepth = locationDepth(StartLoc);
578	size_t EndDepth = locationDepth(EndLoc);
579	while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) {
580	bool UnnestStart = StartDepth >= EndDepth;
581	bool UnnestEnd = EndDepth >= StartDepth;
582	if (UnnestEnd) {
583	// The region ends in a nested file or macro expansion. Create a
584	// separate region for each expansion.
585	SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc);
586	assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
587
588	if (!isRegionAlreadyAdded(NestedLoc, EndLoc))
589	SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
590
591	EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
592	if (EndLoc.isInvalid())
593	llvm::report_fatal_error("File exit not handled before popRegions");
594	EndDepth--;
595	}
596	if (UnnestStart) {
597	// The region begins in a nested file or macro expansion. Create a
598	// separate region for each expansion.
599	SourceLocation NestedLoc = getEndOfFileOrMacro(StartLoc);
600	assert(SM.isWrittenInSameFile(StartLoc, NestedLoc));
601
602	if (!isRegionAlreadyAdded(StartLoc, NestedLoc))
603	SourceRegions.emplace_back(Region.getCounter(), StartLoc, NestedLoc);
604
605	StartLoc = getIncludeOrExpansionLoc(StartLoc);
606	if (StartLoc.isInvalid())
607	llvm::report_fatal_error("File exit not handled before popRegions");
608	StartDepth--;
609	}
610	}
611	Region.setStartLoc(StartLoc);
612	Region.setEndLoc(EndLoc);
613
614	MostRecentLocation = EndLoc;
615	// If this region happens to span an entire expansion, we need to make
616	// sure we don't overlap the parent region with it.
617	if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
618	EndLoc == getEndOfFileOrMacro(EndLoc))
619	MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
620
621	assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc));
622	assert(SpellingRegion(SM, Region).isInSourceOrder());
623	SourceRegions.push_back(Region);
624
625	if (ParentOfDeferredRegion) {
626	ParentOfDeferredRegion = false;
627
628	// If there's an existing deferred region, keep the old one, because
629	// it means there are two consecutive returns (or a similar pattern).
630	if (!DeferredRegion.hasValue() &&
631	// File IDs aren't gathered within macro expansions, so it isn't
632	// useful to try and create a deferred region inside of one.
633	!EndLoc.isMacroID())
634	DeferredRegion =
635	SourceMappingRegion(Counter::getZero(), EndLoc, None);
636	}
637	} else if (Region.isDeferred()) {
638	(0) . __assert_fail ("!ParentOfDeferredRegion && \"Consecutive deferred regions\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 638, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!ParentOfDeferredRegion && "Consecutive deferred regions");
639	ParentOfDeferredRegion = true;
640	}
641	RegionStack.pop_back();
642
643	// If the zero region pushed after the last terminated region no longer
644	// exists, clear its cached information.
645	if (LastTerminatedRegion &&
646	RegionStack.size() < LastTerminatedRegion->second)
647	LastTerminatedRegion = None;
648	}
649	(0) . __assert_fail ("!ParentOfDeferredRegion && \"Deferred region with no parent\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 649, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!ParentOfDeferredRegion && "Deferred region with no parent");
650	}
651
652	/// Return the currently active region.
653	SourceMappingRegion &getRegion() {
654	(0) . __assert_fail ("!RegionStack.empty() && \"statement has no region\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 654, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!RegionStack.empty() && "statement has no region");
655	return RegionStack.back();
656	}
657
658	/// Propagate counts through the children of \p S if \p VisitChildren is true.
659	/// Otherwise, only emit a count for \p S itself.
660	Counter propagateCounts(Counter TopCount, const Stmt *S,
661	bool VisitChildren = true) {
662	SourceLocation StartLoc = getStart(S);
663	SourceLocation EndLoc = getEnd(S);
664	size_t Index = pushRegion(TopCount, StartLoc, EndLoc);
665	if (VisitChildren)
666	Visit(S);
667	Counter ExitCount = getRegion().getCounter();
668	popRegions(Index);
669
670	// The statement may be spanned by an expansion. Make sure we handle a file
671	// exit out of this expansion before moving to the next statement.
672	if (SM.isBeforeInTranslationUnit(StartLoc, S->getBeginLoc()))
673	MostRecentLocation = EndLoc;
674
675	return ExitCount;
676	}
677
678	/// Check whether a region with bounds \c StartLoc and \c EndLoc
679	/// is already added to \c SourceRegions.
680	bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc) {
681	return SourceRegions.rend() !=
682	std::find_if(SourceRegions.rbegin(), SourceRegions.rend(),
683	[&](const SourceMappingRegion &Region) {
684	return Region.getBeginLoc() == StartLoc &&
685	Region.getEndLoc() == EndLoc;
686	});
687	}
688
689	/// Adjust the most recently visited location to \c EndLoc.
690	///
691	/// This should be used after visiting any statements in non-source order.
692	void adjustForOutOfOrderTraversal(SourceLocation EndLoc) {
693	MostRecentLocation = EndLoc;
694	// The code region for a whole macro is created in handleFileExit() when
695	// it detects exiting of the virtual file of that macro. If we visited
696	// statements in non-source order, we might already have such a region
697	// added, for example, if a body of a loop is divided among multiple
698	// macros. Avoid adding duplicate regions in such case.
699	if (getRegion().hasEndLoc() &&
700	MostRecentLocation == getEndOfFileOrMacro(MostRecentLocation) &&
701	isRegionAlreadyAdded(getStartOfFileOrMacro(MostRecentLocation),
702	MostRecentLocation))
703	MostRecentLocation = getIncludeOrExpansionLoc(MostRecentLocation);
704	}
705
706	/// Adjust regions and state when \c NewLoc exits a file.
707	///
708	/// If moving from our most recently tracked location to \c NewLoc exits any
709	/// files, this adjusts our current region stack and creates the file regions
710	/// for the exited file.
711	void handleFileExit(SourceLocation NewLoc) {
712	if (NewLoc.isInvalid() \|\|
713	SM.isWrittenInSameFile(MostRecentLocation, NewLoc))
714	return;
715
716	// If NewLoc is not in a file that contains MostRecentLocation, walk up to
717	// find the common ancestor.
718	SourceLocation LCA = NewLoc;
719	FileID ParentFile = SM.getFileID(LCA);
720	while (!isNestedIn(MostRecentLocation, ParentFile)) {
721	LCA = getIncludeOrExpansionLoc(LCA);
722	if (LCA.isInvalid() \|\| SM.isWrittenInSameFile(LCA, MostRecentLocation)) {
723	// Since there isn't a common ancestor, no file was exited. We just need
724	// to adjust our location to the new file.
725	MostRecentLocation = NewLoc;
726	return;
727	}
728	ParentFile = SM.getFileID(LCA);
729	}
730
731	llvm::SmallSet<SourceLocation, 8> StartLocs;
732	Optional<Counter> ParentCounter;
733	for (SourceMappingRegion &I : llvm::reverse(RegionStack)) {
734	if (!I.hasStartLoc())
735	continue;
736	SourceLocation Loc = I.getBeginLoc();
737	if (!isNestedIn(Loc, ParentFile)) {
738	ParentCounter = I.getCounter();
739	break;
740	}
741
742	while (!SM.isInFileID(Loc, ParentFile)) {
743	// The most nested region for each start location is the one with the
744	// correct count. We avoid creating redundant regions by stopping once
745	// we've seen this region.
746	if (StartLocs.insert(Loc).second)
747	SourceRegions.emplace_back(I.getCounter(), Loc,
748	getEndOfFileOrMacro(Loc));
749	Loc = getIncludeOrExpansionLoc(Loc);
750	}
751	I.setStartLoc(getPreciseTokenLocEnd(Loc));
752	}
753
754	if (ParentCounter) {
755	// If the file is contained completely by another region and doesn't
756	// immediately start its own region, the whole file gets a region
757	// corresponding to the parent.
758	SourceLocation Loc = MostRecentLocation;
759	while (isNestedIn(Loc, ParentFile)) {
760	SourceLocation FileStart = getStartOfFileOrMacro(Loc);
761	if (StartLocs.insert(FileStart).second) {
762	SourceRegions.emplace_back(*ParentCounter, FileStart,
763	getEndOfFileOrMacro(Loc));
764	assert(SpellingRegion(SM, SourceRegions.back()).isInSourceOrder());
765	}
766	Loc = getIncludeOrExpansionLoc(Loc);
767	}
768	}
769
770	MostRecentLocation = NewLoc;
771	}
772
773	/// Ensure that \c S is included in the current region.
774	void extendRegion(const Stmt *S) {
775	SourceMappingRegion &Region = getRegion();
776	SourceLocation StartLoc = getStart(S);
777
778	handleFileExit(StartLoc);
779	if (!Region.hasStartLoc())
780	Region.setStartLoc(StartLoc);
781
782	completeDeferred(Region.getCounter(), StartLoc);
783	}
784
785	/// Mark \c S as a terminator, starting a zero region.
786	void terminateRegion(const Stmt *S) {
787	extendRegion(S);
788	SourceMappingRegion &Region = getRegion();
789	SourceLocation EndLoc = getEnd(S);
790	if (!Region.hasEndLoc())
791	Region.setEndLoc(EndLoc);
792	pushRegion(Counter::getZero());
793	auto &ZeroRegion = getRegion();
794	ZeroRegion.setDeferred(true);
795	LastTerminatedRegion = {EndLoc, RegionStack.size()};
796	}
797
798	/// Find a valid gap range between \p AfterLoc and \p BeforeLoc.
799	Optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc,
800	SourceLocation BeforeLoc) {
801	// If the start and end locations of the gap are both within the same macro
802	// file, the range may not be in source order.
803	if (AfterLoc.isMacroID() \|\| BeforeLoc.isMacroID())
804	return None;
805	if (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc))
806	return None;
807	return {{AfterLoc, BeforeLoc}};
808	}
809
810	/// Find the source range after \p AfterStmt and before \p BeforeStmt.
811	Optional<SourceRange> findGapAreaBetween(const Stmt *AfterStmt,
812	const Stmt *BeforeStmt) {
813	return findGapAreaBetween(getPreciseTokenLocEnd(getEnd(AfterStmt)),
814	getStart(BeforeStmt));
815	}
816
817	/// Emit a gap region between \p StartLoc and \p EndLoc with the given count.
818	void fillGapAreaWithCount(SourceLocation StartLoc, SourceLocation EndLoc,
819	Counter Count) {
820	if (StartLoc == EndLoc)
821	return;
822	assert(SpellingRegion(SM, StartLoc, EndLoc).isInSourceOrder());
823	handleFileExit(StartLoc);
824	size_t Index = pushRegion(Count, StartLoc, EndLoc);
825	getRegion().setGap(true);
826	handleFileExit(EndLoc);
827	popRegions(Index);
828	}
829
830	/// Keep counts of breaks and continues inside loops.
831	struct BreakContinue {
832	Counter BreakCount;
833	Counter ContinueCount;
834	};
835	SmallVector<BreakContinue, 8> BreakContinueStack;
836
837	CounterCoverageMappingBuilder(
838	CoverageMappingModuleGen &CVM,
839	llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
840	const LangOptions &LangOpts)
841	: CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap),
842	DeferredRegion(None) {}
843
844	/// Write the mapping data to the output stream
845	void write(llvm::raw_ostream &OS) {
846	llvm::SmallVector<unsigned, 8> VirtualFileMapping;
847	gatherFileIDs(VirtualFileMapping);
848	SourceRegionFilter Filter = emitExpansionRegions();
849	(0) . __assert_fail ("!DeferredRegion && \"Deferred region never completed\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 849, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!DeferredRegion && "Deferred region never completed");
850	emitSourceRegions(Filter);
851	gatherSkippedRegions();
852
853	if (MappingRegions.empty())
854	return;
855
856	CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
857	MappingRegions);
858	Writer.write(OS);
859	}
860
861	void VisitStmt(const Stmt *S) {
862	if (S->getBeginLoc().isValid())
863	extendRegion(S);
864	for (const Stmt *Child : S->children())
865	if (Child)
866	this->Visit(Child);
867	handleFileExit(getEnd(S));
868	}
869
870	void VisitDecl(const Decl *D) {
871	(0) . __assert_fail ("!DeferredRegion && \"Deferred region never completed\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 871, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!DeferredRegion && "Deferred region never completed");
872
873	Stmt *Body = D->getBody();
874
875	// Do not propagate region counts into system headers.
876	if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body))))
877	return;
878
879	// Do not visit the artificial children nodes of defaulted methods. The
880	// lexer may not be able to report back precise token end locations for
881	// these children nodes (llvm.org/PR39822), and moreover users will not be
882	// able to see coverage for them.
883	bool Defaulted = false;
884	if (auto *Method = dyn_cast<CXXMethodDecl>(D))
885	Defaulted = Method->isDefaulted();
886
887	propagateCounts(getRegionCounter(Body), Body,
888	/VisitChildren=/!Defaulted);
889	(0) . __assert_fail ("RegionStack.empty() && \"Regions entered but never exited\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 889, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(RegionStack.empty() && "Regions entered but never exited");
890
891	// Discard the last uncompleted deferred region in a decl, if one exists.
892	// This prevents lines at the end of a function containing only whitespace
893	// or closing braces from being marked as uncovered.
894	DeferredRegion = None;
895	}
896
897	void VisitReturnStmt(const ReturnStmt *S) {
898	extendRegion(S);
899	if (S->getRetValue())
900	Visit(S->getRetValue());
901	terminateRegion(S);
902	}
903
904	void VisitCXXThrowExpr(const CXXThrowExpr *E) {
905	extendRegion(E);
906	if (E->getSubExpr())
907	Visit(E->getSubExpr());
908	terminateRegion(E);
909	}
910
911	void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
912
913	void VisitLabelStmt(const LabelStmt *S) {
914	Counter LabelCount = getRegionCounter(S);
915	SourceLocation Start = getStart(S);
916	completeTopLevelDeferredRegion(LabelCount, Start);
917	completeDeferred(LabelCount, Start);
918	// We can't extendRegion here or we risk overlapping with our new region.
919	handleFileExit(Start);
920	pushRegion(LabelCount, Start);
921	Visit(S->getSubStmt());
922	}
923
924	void VisitBreakStmt(const BreakStmt *S) {
925	(0) . __assert_fail ("!BreakContinueStack.empty() && \"break not in a loop or switch!\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 925, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
926	BreakContinueStack.back().BreakCount = addCounters(
927	BreakContinueStack.back().BreakCount, getRegion().getCounter());
928	// FIXME: a break in a switch should terminate regions for all preceding
929	// case statements, not just the most recent one.
930	terminateRegion(S);
931	}
932
933	void VisitContinueStmt(const ContinueStmt *S) {
934	(0) . __assert_fail ("!BreakContinueStack.empty() && \"continue stmt not in a loop!\"", "/home/seafit/code_projects/clang_source/clang/lib/CodeGen/CoverageMappingGen.cpp", 934, __PRETTY_FUNCTION__))" file_link="../../../include/assert.h.html#88" macro="true">assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
935	BreakContinueStack.back().ContinueCount = addCounters(
936	BreakContinueStack.back().ContinueCount, getRegion().getCounter());
937	terminateRegion(S);
938	}
939
940	void VisitCallExpr(const CallExpr *E) {
941	VisitStmt(E);
942
943	// Terminate the region when we hit a noreturn function.
944	// (This is helpful dealing with switch statements.)
945	QualType CalleeType = E->getCallee()->getType();
946	if (getFunctionExtInfo(*CalleeType).getNoReturn())
947	terminateRegion(E);
948	}
949
950	void VisitWhileStmt(const WhileStmt *S) {
951	extendRegion(S);
952
953	Counter ParentCount = getRegion().getCounter();
954	Counter BodyCount = getRegionCounter(S);
955
956	// Handle the body first so that we can get the backedge count.
957	BreakContinueStack.push_back(BreakContinue());
958	extendRegion(S->getBody());
959	Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
960	BreakContinue BC = BreakContinueStack.pop_back_val();
961
962	// Go back to handle the condition.
963	Counter CondCount =
964	addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
965	propagateCounts(CondCount, S->getCond());
966	adjustForOutOfOrderTraversal(getEnd(S));
967
968	// The body count applies to the area immediately after the increment.
969	auto Gap = findGapAreaBetween(S->getCond(), S->getBody());
970	if (Gap)
971	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
972
973	Counter OutCount =
974	addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
975	if (OutCount != ParentCount)
976	pushRegion(OutCount);
977	}
978
979	void VisitDoStmt(const DoStmt *S) {
980	extendRegion(S);
981
982	Counter ParentCount = getRegion().getCounter();
983	Counter BodyCount = getRegionCounter(S);
984
985	BreakContinueStack.push_back(BreakContinue());
986	extendRegion(S->getBody());
987	Counter BackedgeCount =
988	propagateCounts(addCounters(ParentCount, BodyCount), S->getBody());
989	BreakContinue BC = BreakContinueStack.pop_back_val();
990
991	Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
992	propagateCounts(CondCount, S->getCond());
993
994	Counter OutCount =
995	addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
996	if (OutCount != ParentCount)
997	pushRegion(OutCount);
998	}
999
1000	void VisitForStmt(const ForStmt *S) {
1001	extendRegion(S);
1002	if (S->getInit())
1003	Visit(S->getInit());
1004
1005	Counter ParentCount = getRegion().getCounter();
1006	Counter BodyCount = getRegionCounter(S);
1007
1008	// The loop increment may contain a break or continue.
1009	if (S->getInc())
1010	BreakContinueStack.emplace_back();
1011
1012	// Handle the body first so that we can get the backedge count.
1013	BreakContinueStack.emplace_back();
1014	extendRegion(S->getBody());
1015	Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1016	BreakContinue BodyBC = BreakContinueStack.pop_back_val();
1017
1018	// The increment is essentially part of the body but it needs to include
1019	// the count for all the continue statements.
1020	BreakContinue IncrementBC;
1021	if (const Stmt *Inc = S->getInc()) {
1022	propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
1023	IncrementBC = BreakContinueStack.pop_back_val();
1024	}
1025
1026	// Go back to handle the condition.
1027	Counter CondCount = addCounters(
1028	addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
1029	IncrementBC.ContinueCount);
1030	if (const Expr *Cond = S->getCond()) {
1031	propagateCounts(CondCount, Cond);
1032	adjustForOutOfOrderTraversal(getEnd(S));
1033	}
1034
1035	// The body count applies to the area immediately after the increment.
1036	auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1037	getStart(S->getBody()));
1038	if (Gap)
1039	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1040
1041	Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
1042	subtractCounters(CondCount, BodyCount));
1043	if (OutCount != ParentCount)
1044	pushRegion(OutCount);
1045	}
1046
1047	void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1048	extendRegion(S);
1049	if (S->getInit())
1050	Visit(S->getInit());
1051	Visit(S->getLoopVarStmt());
1052	Visit(S->getRangeStmt());
1053
1054	Counter ParentCount = getRegion().getCounter();
1055	Counter BodyCount = getRegionCounter(S);
1056
1057	BreakContinueStack.push_back(BreakContinue());
1058	extendRegion(S->getBody());
1059	Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1060	BreakContinue BC = BreakContinueStack.pop_back_val();
1061
1062	// The body count applies to the area immediately after the range.
1063	auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1064	getStart(S->getBody()));
1065	if (Gap)
1066	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1067
1068	Counter LoopCount =
1069	addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1070	Counter OutCount =
1071	addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1072	if (OutCount != ParentCount)
1073	pushRegion(OutCount);
1074	}
1075
1076	void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1077	extendRegion(S);
1078	Visit(S->getElement());
1079
1080	Counter ParentCount = getRegion().getCounter();
1081	Counter BodyCount = getRegionCounter(S);
1082
1083	BreakContinueStack.push_back(BreakContinue());
1084	extendRegion(S->getBody());
1085	Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1086	BreakContinue BC = BreakContinueStack.pop_back_val();
1087
1088	// The body count applies to the area immediately after the collection.
1089	auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1090	getStart(S->getBody()));
1091	if (Gap)
1092	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1093
1094	Counter LoopCount =
1095	addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1096	Counter OutCount =
1097	addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1098	if (OutCount != ParentCount)
1099	pushRegion(OutCount);
1100	}
1101
1102	void VisitSwitchStmt(const SwitchStmt *S) {
1103	extendRegion(S);
1104	if (S->getInit())
1105	Visit(S->getInit());
1106	Visit(S->getCond());
1107
1108	BreakContinueStack.push_back(BreakContinue());
1109
1110	const Stmt *Body = S->getBody();
1111	extendRegion(Body);
1112	if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1113	if (!CS->body_empty()) {
1114	// Make a region for the body of the switch. If the body starts with
1115	// a case, that case will reuse this region; otherwise, this covers
1116	// the unreachable code at the beginning of the switch body.
1117	size_t Index =
1118	pushRegion(Counter::getZero(), getStart(CS->body_front()));
1119	for (const auto *Child : CS->children())
1120	Visit(Child);
1121
1122	// Set the end for the body of the switch, if it isn't already set.
1123	for (size_t i = RegionStack.size(); i != Index; --i) {
1124	if (!RegionStack[i - 1].hasEndLoc())
1125	RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1126	}
1127
1128	popRegions(Index);
1129	}
1130	} else
1131	propagateCounts(Counter::getZero(), Body);
1132	BreakContinue BC = BreakContinueStack.pop_back_val();
1133
1134	if (!BreakContinueStack.empty())
1135	BreakContinueStack.back().ContinueCount = addCounters(
1136	BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1137
1138	Counter ExitCount = getRegionCounter(S);
1139	SourceLocation ExitLoc = getEnd(S);
1140	pushRegion(ExitCount);
1141
1142	// Ensure that handleFileExit recognizes when the end location is located
1143	// in a different file.
1144	MostRecentLocation = getStart(S);
1145	handleFileExit(ExitLoc);
1146	}
1147
1148	void VisitSwitchCase(const SwitchCase *S) {
1149	extendRegion(S);
1150
1151	SourceMappingRegion &Parent = getRegion();
1152
1153	Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1154	// Reuse the existing region if it starts at our label. This is typical of
1155	// the first case in a switch.
1156	if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1157	Parent.setCounter(Count);
1158	else
1159	pushRegion(Count, getStart(S));
1160
1161	if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1162	Visit(CS->getLHS());
1163	if (const Expr *RHS = CS->getRHS())
1164	Visit(RHS);
1165	}
1166	Visit(S->getSubStmt());
1167	}
1168
1169	void VisitIfStmt(const IfStmt *S) {
1170	extendRegion(S);
1171	if (S->getInit())
1172	Visit(S->getInit());
1173
1174	// Extend into the condition before we propagate through it below - this is
1175	// needed to handle macros that generate the "if" but not the condition.
1176	extendRegion(S->getCond());
1177
1178	Counter ParentCount = getRegion().getCounter();
1179	Counter ThenCount = getRegionCounter(S);
1180
1181	// Emitting a counter for the condition makes it easier to interpret the
1182	// counter for the body when looking at the coverage.
1183	propagateCounts(ParentCount, S->getCond());
1184
1185	// The 'then' count applies to the area immediately after the condition.
1186	auto Gap = findGapAreaBetween(S->getCond(), S->getThen());
1187	if (Gap)
1188	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
1189
1190	extendRegion(S->getThen());
1191	Counter OutCount = propagateCounts(ThenCount, S->getThen());
1192
1193	Counter ElseCount = subtractCounters(ParentCount, ThenCount);
1194	if (const Stmt *Else = S->getElse()) {
1195	// The 'else' count applies to the area immediately after the 'then'.
1196	Gap = findGapAreaBetween(S->getThen(), Else);
1197	if (Gap)
1198	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
1199	extendRegion(Else);
1200	OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
1201	} else
1202	OutCount = addCounters(OutCount, ElseCount);
1203
1204	if (OutCount != ParentCount)
1205	pushRegion(OutCount);
1206	}
1207
1208	void VisitCXXTryStmt(const CXXTryStmt *S) {
1209	extendRegion(S);
1210	// Handle macros that generate the "try" but not the rest.
1211	extendRegion(S->getTryBlock());
1212
1213	Counter ParentCount = getRegion().getCounter();
1214	propagateCounts(ParentCount, S->getTryBlock());
1215
1216	for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
1217	Visit(S->getHandler(I));
1218
1219	Counter ExitCount = getRegionCounter(S);
1220	pushRegion(ExitCount);
1221	}
1222
1223	void VisitCXXCatchStmt(const CXXCatchStmt *S) {
1224	propagateCounts(getRegionCounter(S), S->getHandlerBlock());
1225	}
1226
1227	void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1228	extendRegion(E);
1229
1230	Counter ParentCount = getRegion().getCounter();
1231	Counter TrueCount = getRegionCounter(E);
1232
1233	Visit(E->getCond());
1234
1235	if (!isa<BinaryConditionalOperator>(E)) {
1236	// The 'then' count applies to the area immediately after the condition.
1237	auto Gap =
1238	findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1239	if (Gap)
1240	fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1241
1242	extendRegion(E->getTrueExpr());
1243	propagateCounts(TrueCount, E->getTrueExpr());
1244	}
1245
1246	extendRegion(E->getFalseExpr());
1247	propagateCounts(subtractCounters(ParentCount, TrueCount),
1248	E->getFalseExpr());
1249	}
1250
1251	void VisitBinLAnd(const BinaryOperator *E) {
1252	extendRegion(E->getLHS());
1253	propagateCounts(getRegion().getCounter(), E->getLHS());
1254	handleFileExit(getEnd(E->getLHS()));
1255
1256	extendRegion(E->getRHS());
1257	propagateCounts(getRegionCounter(E), E->getRHS());
1258	}
1259
1260	void VisitBinLOr(const BinaryOperator *E) {
1261	extendRegion(E->getLHS());
1262	propagateCounts(getRegion().getCounter(), E->getLHS());
1263	handleFileExit(getEnd(E->getLHS()));
1264
1265	extendRegion(E->getRHS());
1266	propagateCounts(getRegionCounter(E), E->getRHS());
1267	}
1268
1269	void VisitLambdaExpr(const LambdaExpr *LE) {
1270	// Lambdas are treated as their own functions for now, so we shouldn't
1271	// propagate counts into them.
1272	}
1273	};
1274
1275	std::string getCoverageSection(const CodeGenModule &CGM) {
1276	return llvm::getInstrProfSectionName(
1277	llvm::IPSK_covmap,
1278	CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1279	}
1280
1281	std::string normalizeFilename(StringRef Filename) {
1282	llvm::SmallString<256> Path(Filename);
1283	llvm::sys::fs::make_absolute(Path);
1284	llvm::sys::path::remove_dots(Path, /remove_dot_dots=/true);
1285	return Path.str().str();
1286	}
1287
1288	} // end anonymous namespace
1289
1290	static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1291	ArrayRef<CounterExpression> Expressions,
1292	ArrayRef<CounterMappingRegion> Regions) {
1293	OS << FunctionName << ":\n";
1294	CounterMappingContext Ctx(Expressions);
1295	for (const auto &R : Regions) {
1296	OS.indent(2);
1297	switch (R.Kind) {
1298	case CounterMappingRegion::CodeRegion:
1299	break;
1300	case CounterMappingRegion::ExpansionRegion:
1301	OS << "Expansion,";
1302	break;
1303	case CounterMappingRegion::SkippedRegion:
1304	OS << "Skipped,";
1305	break;
1306	case CounterMappingRegion::GapRegion:
1307	OS << "Gap,";
1308	break;
1309	}
1310
1311	OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1312	<< " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1313	Ctx.dump(R.Count, OS);
1314	if (R.Kind == CounterMappingRegion::ExpansionRegion)
1315	OS << " (Expanded file = " << R.ExpandedFileID << ")";
1316	OS << "\n";
1317	}
1318	}
1319
1320	void CoverageMappingModuleGen::addFunctionMappingRecord(
1321	llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1322	const std::string &CoverageMapping, bool IsUsed) {
1323	llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1324	if (!FunctionRecordTy) {
1325	#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1326	llvm::Type *FunctionRecordTypes[] = {
1327	#include "llvm/ProfileData/InstrProfData.inc"
1328	};
1329	FunctionRecordTy =
1330	llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1331	/isPacked=/true);
1332	}
1333
1334	#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1335	llvm::Constant *FunctionRecordVals[] = {
1336	#include "llvm/ProfileData/InstrProfData.inc"
1337	};
1338	FunctionRecords.push_back(llvm::ConstantStruct::get(
1339	FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1340	if (!IsUsed)
1341	FunctionNames.push_back(
1342	llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1343	CoverageMappings.push_back(CoverageMapping);
1344
1345	if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1346	// Dump the coverage mapping data for this function by decoding the
1347	// encoded data. This allows us to dump the mapping regions which were
1348	// also processed by the CoverageMappingWriter which performs
1349	// additional minimization operations such as reducing the number of
1350	// expressions.
1351	std::vector<StringRef> Filenames;
1352	std::vector<CounterExpression> Expressions;
1353	std::vector<CounterMappingRegion> Regions;
1354	llvm::SmallVector<std::string, 16> FilenameStrs;
1355	llvm::SmallVector<StringRef, 16> FilenameRefs;
1356	FilenameStrs.resize(FileEntries.size());
1357	FilenameRefs.resize(FileEntries.size());
1358	for (const auto &Entry : FileEntries) {
1359	auto I = Entry.second;
1360	FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1361	FilenameRefs[I] = FilenameStrs[I];
1362	}
1363	RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1364	Expressions, Regions);
1365	if (Reader.read())
1366	return;
1367	dump(llvm::outs(), NameValue, Expressions, Regions);
1368	}
1369	}
1370
1371	void CoverageMappingModuleGen::emit() {
1372	if (FunctionRecords.empty())
1373	return;
1374	llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1375	auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1376
1377	// Create the filenames and merge them with coverage mappings
1378	llvm::SmallVector<std::string, 16> FilenameStrs;
1379	llvm::SmallVector<StringRef, 16> FilenameRefs;
1380	FilenameStrs.resize(FileEntries.size());
1381	FilenameRefs.resize(FileEntries.size());
1382	for (const auto &Entry : FileEntries) {
1383	auto I = Entry.second;
1384	FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1385	FilenameRefs[I] = FilenameStrs[I];
1386	}
1387
1388	std::string FilenamesAndCoverageMappings;
1389	llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1390	CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1391	std::string RawCoverageMappings =
1392	llvm::join(CoverageMappings.begin(), CoverageMappings.end(), "");
1393	OS << RawCoverageMappings;
1394	size_t CoverageMappingSize = RawCoverageMappings.size();
1395	size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1396	// Append extra zeroes if necessary to ensure that the size of the filenames
1397	// and coverage mappings is a multiple of 8.
1398	if (size_t Rem = OS.str().size() % 8) {
1399	CoverageMappingSize += 8 - Rem;
1400	OS.write_zeros(8 - Rem);
1401	}
1402	auto *FilenamesAndMappingsVal =
1403	llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1404
1405	// Create the deferred function records array
1406	auto RecordsTy =
1407	llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1408	auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1409
1410	llvm::Type *CovDataHeaderTypes[] = {
1411	#define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1412	#include "llvm/ProfileData/InstrProfData.inc"
1413	};
1414	auto CovDataHeaderTy =
1415	llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1416	llvm::Constant *CovDataHeaderVals[] = {
1417	#define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1418	#include "llvm/ProfileData/InstrProfData.inc"
1419	};
1420	auto CovDataHeaderVal = llvm::ConstantStruct::get(
1421	CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1422
1423	// Create the coverage data record
1424	llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1425	FilenamesAndMappingsVal->getType()};
1426	auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1427	llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1428	FilenamesAndMappingsVal};
1429	auto CovDataVal =
1430	llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1431	auto CovData = new llvm::GlobalVariable(
1432	CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1433	CovDataVal, llvm::getCoverageMappingVarName());
1434
1435	CovData->setSection(getCoverageSection(CGM));
1436	CovData->setAlignment(8);
1437
1438	// Make sure the data doesn't get deleted.
1439	CGM.addUsedGlobal(CovData);
1440	// Create the deferred function records array
1441	if (!FunctionNames.empty()) {
1442	auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1443	FunctionNames.size());
1444	auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1445	// This variable will NOT be emitted to the object file. It is used
1446	// to pass the list of names referenced to codegen.
1447	new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1448	llvm::GlobalValue::InternalLinkage, NamesArrVal,
1449	llvm::getCoverageUnusedNamesVarName());
1450	}
1451	}
1452
1453	unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1454	auto It = FileEntries.find(File);
1455	if (It != FileEntries.end())
1456	return It->second;
1457	unsigned FileID = FileEntries.size();
1458	FileEntries.insert(std::make_pair(File, FileID));
1459	return FileID;
1460	}
1461
1462	void CoverageMappingGen::emitCounterMapping(const Decl *D,
1463	llvm::raw_ostream &OS) {
1464	assert(CounterMap);
1465	CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1466	Walker.VisitDecl(D);
1467	Walker.write(OS);
1468	}
1469
1470	void CoverageMappingGen::emitEmptyMapping(const Decl *D,
1471	llvm::raw_ostream &OS) {
1472	EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1473	Walker.VisitDecl(D);
1474	Walker.write(OS);
1475	}
1476

clang::CoverageSourceInfo::SourceRangeSkipped

clang::CodeGen::CoverageMappingModuleGen::addFunctionMappingRecord

clang::CodeGen::CoverageMappingModuleGen::emit

clang::CodeGen::CoverageMappingModuleGen::getFileID

clang::CodeGen::CoverageMappingGen::emitCounterMapping

clang::CodeGen::CoverageMappingGen::emitEmptyMapping

Clang Project