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/Basic/Diagnostic.h"
17	#include "clang/Basic/FileManager.h"
18	#include "clang/Frontend/FrontendDiagnostic.h"
19	#include "clang/Lex/Lexer.h"
20	#include "llvm/ADT/SmallSet.h"
21	#include "llvm/ADT/StringExtras.h"
22	#include "llvm/ProfileData/Coverage/CoverageMapping.h"
23	#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
24	#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
25	#include "llvm/ProfileData/InstrProfReader.h"
26	#include "llvm/Support/FileSystem.h"
27	#include "llvm/Support/Path.h"
28	#include <optional>
29
30	// This selects the coverage mapping format defined when `InstrProfData.inc`
31	// is textually included.
32	#define COVMAP_V3
33
34	namespace llvm {
35	cl::opt<bool>
36	EnableSingleByteCoverage("enable-single-byte-coverage",
37	llvm::cl::ZeroOrMore,
38	llvm::cl::desc("Enable single byte coverage"),
39	llvm::cl::Hidden, llvm::cl::init(Val: false));
40	} // namespace llvm
41
42	static llvm::cl::opt<bool> EmptyLineCommentCoverage(
43	"emptyline-comment-coverage",
44	llvm::cl::desc("Emit emptylines and comment lines as skipped regions (only "
45	"disable it on test)"),
46	llvm::cl::init(Val: true), llvm::cl::Hidden);
47
48	llvm::cl::opt<bool> SystemHeadersCoverage(
49	"system-headers-coverage",
50	llvm::cl::desc("Enable collecting coverage from system headers"),
51	llvm::cl::init(Val: false), llvm::cl::Hidden);
52
53	using namespace clang;
54	using namespace CodeGen;
55	using namespace llvm::coverage;
56
57	CoverageSourceInfo *
58	CoverageMappingModuleGen::setUpCoverageCallbacks(Preprocessor &PP) {
59	CoverageSourceInfo *CoverageInfo =
60	new CoverageSourceInfo(PP.getSourceManager());
61	PP.addPPCallbacks(C: std::unique_ptr<PPCallbacks>(CoverageInfo));
62	if (EmptyLineCommentCoverage) {
63	PP.addCommentHandler(Handler: CoverageInfo);
64	PP.setEmptylineHandler(CoverageInfo);
65	PP.setPreprocessToken(true);
66	PP.setTokenWatcher([CoverageInfo](clang::Token Tok) {
67	// Update previous token location.
68	CoverageInfo->PrevTokLoc = Tok.getLocation();
69	if (Tok.getKind() != clang::tok::eod)
70	CoverageInfo->updateNextTokLoc(Loc: Tok.getLocation());
71	});
72	}
73	return CoverageInfo;
74	}
75
76	void CoverageSourceInfo::AddSkippedRange(SourceRange Range,
77	SkippedRange::Kind RangeKind) {
78	if (EmptyLineCommentCoverage && !SkippedRanges.empty() &&
79	PrevTokLoc == SkippedRanges.back().PrevTokLoc &&
80	SourceMgr.isWrittenInSameFile(Loc1: SkippedRanges.back().Range.getEnd(),
81	Loc2: Range.getBegin()))
82	SkippedRanges.back().Range.setEnd(Range.getEnd());
83	else
84	SkippedRanges.push_back(x: {Range, RangeKind, PrevTokLoc});
85	}
86
87	void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) {
88	AddSkippedRange(Range, RangeKind: SkippedRange::PPIfElse);
89	}
90
91	void CoverageSourceInfo::HandleEmptyline(SourceRange Range) {
92	AddSkippedRange(Range, RangeKind: SkippedRange::EmptyLine);
93	}
94
95	bool CoverageSourceInfo::HandleComment(Preprocessor &PP, SourceRange Range) {
96	AddSkippedRange(Range, RangeKind: SkippedRange::Comment);
97	return false;
98	}
99
100	void CoverageSourceInfo::updateNextTokLoc(SourceLocation Loc) {
101	if (!SkippedRanges.empty() && SkippedRanges.back().NextTokLoc.isInvalid())
102	SkippedRanges.back().NextTokLoc = Loc;
103	}
104
105	namespace {
106	/// A region of source code that can be mapped to a counter.
107	class SourceMappingRegion {
108	/// Primary Counter that is also used for Branch Regions for "True" branches.
109	Counter Count;
110
111	/// Secondary Counter used for Branch Regions for "False" branches.
112	std::optional<Counter> FalseCount;
113
114	/// Parameters used for Modified Condition/Decision Coverage
115	mcdc::Parameters MCDCParams;
116
117	/// The region's starting location.
118	std::optional<SourceLocation> LocStart;
119
120	/// The region's ending location.
121	std::optional<SourceLocation> LocEnd;
122
123	/// Whether this region is a gap region. The count from a gap region is set
124	/// as the line execution count if there are no other regions on the line.
125	bool GapRegion;
126
127	/// Whetever this region is skipped ('if constexpr' or 'if consteval' untaken
128	/// branch, or anything skipped but not empty line / comments)
129	bool SkippedRegion;
130
131	public:
132	SourceMappingRegion(Counter Count, std::optional<SourceLocation> LocStart,
133	std::optional<SourceLocation> LocEnd,
134	bool GapRegion = false)
135	: Count(Count), LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion),
136	SkippedRegion(false) {}
137
138	SourceMappingRegion(Counter Count, std::optional<Counter> FalseCount,
139	mcdc::Parameters MCDCParams,
140	std::optional<SourceLocation> LocStart,
141	std::optional<SourceLocation> LocEnd,
142	bool GapRegion = false)
143	: Count(Count), FalseCount(FalseCount), MCDCParams(MCDCParams),
144	LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion),
145	SkippedRegion(false) {}
146
147	SourceMappingRegion(mcdc::Parameters MCDCParams,
148	std::optional<SourceLocation> LocStart,
149	std::optional<SourceLocation> LocEnd)
150	: MCDCParams(MCDCParams), LocStart(LocStart), LocEnd(LocEnd),
151	GapRegion(false), SkippedRegion(false) {}
152
153	const Counter &getCounter() const { return Count; }
154
155	const Counter &getFalseCounter() const {
156	assert(FalseCount && "Region has no alternate counter");
157	return *FalseCount;
158	}
159
160	void setCounter(Counter C) { Count = C; }
161
162	bool hasStartLoc() const { return LocStart.has_value(); }
163
164	void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
165
166	SourceLocation getBeginLoc() const {
167	assert(LocStart && "Region has no start location");
168	return *LocStart;
169	}
170
171	bool hasEndLoc() const { return LocEnd.has_value(); }
172
173	void setEndLoc(SourceLocation Loc) {
174	assert(Loc.isValid() && "Setting an invalid end location");
175	LocEnd = Loc;
176	}
177
178	SourceLocation getEndLoc() const {
179	assert(LocEnd && "Region has no end location");
180	return *LocEnd;
181	}
182
183	bool isGap() const { return GapRegion; }
184
185	void setGap(bool Gap) { GapRegion = Gap; }
186
187	bool isSkipped() const { return SkippedRegion; }
188
189	void setSkipped(bool Skipped) { SkippedRegion = Skipped; }
190
191	bool isBranch() const { return FalseCount.has_value(); }
192
193	bool isMCDCDecision() const {
194	const auto *DecisionParams =
195	std::get_if<mcdc::DecisionParameters>(ptr: &MCDCParams);
196	assert(!DecisionParams || DecisionParams->NumConditions > 0);
197	return DecisionParams;
198	}
199
200	const auto &getMCDCDecisionParams() const {
201	return mcdc::getParams<const mcdc::DecisionParameters>(MCDCParams);
202	}
203
204	const mcdc::Parameters &getMCDCParams() const { return MCDCParams; }
205	};
206
207	/// Spelling locations for the start and end of a source region.
208	struct SpellingRegion {
209	/// The line where the region starts.
210	unsigned LineStart;
211
212	/// The column where the region starts.
213	unsigned ColumnStart;
214
215	/// The line where the region ends.
216	unsigned LineEnd;
217
218	/// The column where the region ends.
219	unsigned ColumnEnd;
220
221	SpellingRegion(SourceManager &SM, SourceLocation LocStart,
222	SourceLocation LocEnd) {
223	LineStart = SM.getSpellingLineNumber(Loc: LocStart);
224	ColumnStart = SM.getSpellingColumnNumber(Loc: LocStart);
225	LineEnd = SM.getSpellingLineNumber(Loc: LocEnd);
226	ColumnEnd = SM.getSpellingColumnNumber(Loc: LocEnd);
227	}
228
229	SpellingRegion(SourceManager &SM, SourceMappingRegion &R)
230	: SpellingRegion(SM, R.getBeginLoc(), R.getEndLoc()) {}
231
232	/// Check if the start and end locations appear in source order, i.e
233	/// top->bottom, left->right.
234	bool isInSourceOrder() const {
235	return (LineStart < LineEnd) ||
236	(LineStart == LineEnd && ColumnStart <= ColumnEnd);
237	}
238	};
239
240	/// Provides the common functionality for the different
241	/// coverage mapping region builders.
242	class CoverageMappingBuilder {
243	public:
244	CoverageMappingModuleGen &CVM;
245	SourceManager &SM;
246	const LangOptions &LangOpts;
247
248	private:
249	/// Map of clang's FileIDs to IDs used for coverage mapping.
250	llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
251	FileIDMapping;
252
253	public:
254	/// The coverage mapping regions for this function
255	llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
256	/// The source mapping regions for this function.
257	std::vector<SourceMappingRegion> SourceRegions;
258
259	/// A set of regions which can be used as a filter.
260	///
261	/// It is produced by emitExpansionRegions() and is used in
262	/// emitSourceRegions() to suppress producing code regions if
263	/// the same area is covered by expansion regions.
264	typedef llvm::SmallSet<std::pair<SourceLocation, SourceLocation>, 8>
265	SourceRegionFilter;
266
267	CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
268	const LangOptions &LangOpts)
269	: CVM(CVM), SM(SM), LangOpts(LangOpts) {}
270
271	/// Return the precise end location for the given token.
272	SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
273	// We avoid getLocForEndOfToken here, because it doesn't do what we want for
274	// macro locations, which we just treat as expanded files.
275	unsigned TokLen =
276	Lexer::MeasureTokenLength(Loc: SM.getSpellingLoc(Loc), SM, LangOpts);
277	return Loc.getLocWithOffset(Offset: TokLen);
278	}
279
280	/// Return the start location of an included file or expanded macro.
281	SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
282	if (Loc.isMacroID())
283	return Loc.getLocWithOffset(Offset: -SM.getFileOffset(SpellingLoc: Loc));
284	return SM.getLocForStartOfFile(FID: SM.getFileID(SpellingLoc: Loc));
285	}
286
287	/// Return the end location of an included file or expanded macro.
288	SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
289	if (Loc.isMacroID())
290	return Loc.getLocWithOffset(Offset: SM.getFileIDSize(FID: SM.getFileID(SpellingLoc: Loc)) -
291	SM.getFileOffset(SpellingLoc: Loc));
292	return SM.getLocForEndOfFile(FID: SM.getFileID(SpellingLoc: Loc));
293	}
294
295	/// Find out where the current file is included or macro is expanded.
296	SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
297	return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getBegin()
298	: SM.getIncludeLoc(FID: SM.getFileID(SpellingLoc: Loc));
299	}
300
301	/// Return true if \c Loc is a location in a built-in macro.
302	bool isInBuiltin(SourceLocation Loc) {
303	return SM.getBufferName(Loc: SM.getSpellingLoc(Loc)) == "<built-in>";
304	}
305
306	/// Check whether \c Loc is included or expanded from \c Parent.
307	bool isNestedIn(SourceLocation Loc, FileID Parent) {
308	do {
309	Loc = getIncludeOrExpansionLoc(Loc);
310	if (Loc.isInvalid())
311	return false;
312	} while (!SM.isInFileID(Loc, FID: Parent));
313	return true;
314	}
315
316	/// Get the start of \c S ignoring macro arguments and builtin macros.
317	SourceLocation getStart(const Stmt *S) {
318	SourceLocation Loc = S->getBeginLoc();
319	while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
320	Loc = SM.getImmediateExpansionRange(Loc).getBegin();
321	return Loc;
322	}
323
324	/// Get the end of \c S ignoring macro arguments and builtin macros.
325	SourceLocation getEnd(const Stmt *S) {
326	SourceLocation Loc = S->getEndLoc();
327	while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
328	Loc = SM.getImmediateExpansionRange(Loc).getBegin();
329	return getPreciseTokenLocEnd(Loc);
330	}
331
332	/// Find the set of files we have regions for and assign IDs
333	///
334	/// Fills \c Mapping with the virtual file mapping needed to write out
335	/// coverage and collects the necessary file information to emit source and
336	/// expansion regions.
337	void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) {
338	FileIDMapping.clear();
339
340	llvm::SmallSet<FileID, 8> Visited;
341	SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
342	for (const auto &Region : SourceRegions) {
343	SourceLocation Loc = Region.getBeginLoc();
344	FileID File = SM.getFileID(SpellingLoc: Loc);
345	if (!Visited.insert(V: File).second)
346	continue;
347
348	// Do not map FileID's associated with system headers unless collecting
349	// coverage from system headers is explicitly enabled.
350	if (!SystemHeadersCoverage && SM.isInSystemHeader(Loc: SM.getSpellingLoc(Loc)))
351	continue;
352
353	unsigned Depth = 0;
354	for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
355	Parent.isValid(); Parent = getIncludeOrExpansionLoc(Loc: Parent))
356	++Depth;
357	FileLocs.push_back(Elt: std::make_pair(x&: Loc, y&: Depth));
358	}
359	llvm::stable_sort(Range&: FileLocs, C: llvm::less_second());
360
361	for (const auto &FL : FileLocs) {
362	SourceLocation Loc = FL.first;
363	FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
364	auto Entry = SM.getFileEntryRefForID(FID: SpellingFile);
365	if (!Entry)
366	continue;
367
368	FileIDMapping[SM.getFileID(SpellingLoc: Loc)] = std::make_pair(x: Mapping.size(), y&: Loc);
369	Mapping.push_back(Elt: CVM.getFileID(File: *Entry));
370	}
371	}
372
373	/// Get the coverage mapping file ID for \c Loc.
374	///
375	/// If such file id doesn't exist, return std::nullopt.
376	std::optional<unsigned> getCoverageFileID(SourceLocation Loc) {
377	auto Mapping = FileIDMapping.find(Val: SM.getFileID(SpellingLoc: Loc));
378	if (Mapping != FileIDMapping.end())
379	return Mapping->second.first;
380	return std::nullopt;
381	}
382
383	/// This shrinks the skipped range if it spans a line that contains a
384	/// non-comment token. If shrinking the skipped range would make it empty,
385	/// this returns std::nullopt.
386	/// Note this function can potentially be expensive because
387	/// getSpellingLineNumber uses getLineNumber, which is expensive.
388	std::optional<SpellingRegion> adjustSkippedRange(SourceManager &SM,
389	SourceLocation LocStart,
390	SourceLocation LocEnd,
391	SourceLocation PrevTokLoc,
392	SourceLocation NextTokLoc) {
393	SpellingRegion SR{SM, LocStart, LocEnd};
394	SR.ColumnStart = 1;
395	if (PrevTokLoc.isValid() && SM.isWrittenInSameFile(Loc1: LocStart, Loc2: PrevTokLoc) &&
396	SR.LineStart == SM.getSpellingLineNumber(Loc: PrevTokLoc))
397	SR.LineStart++;
398	if (NextTokLoc.isValid() && SM.isWrittenInSameFile(Loc1: LocEnd, Loc2: NextTokLoc) &&
399	SR.LineEnd == SM.getSpellingLineNumber(Loc: NextTokLoc)) {
400	SR.LineEnd--;
401	SR.ColumnEnd++;
402	}
403	if (SR.isInSourceOrder())
404	return SR;
405	return std::nullopt;
406	}
407
408	/// Gather all the regions that were skipped by the preprocessor
409	/// using the constructs like #if or comments.
410	void gatherSkippedRegions() {
411	/// An array of the minimum lineStarts and the maximum lineEnds
412	/// for mapping regions from the appropriate source files.
413	llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
414	FileLineRanges.resize(
415	N: FileIDMapping.size(),
416	NV: std::make_pair(x: std::numeric_limits<unsigned>::max(), y: 0));
417	for (const auto &R : MappingRegions) {
418	FileLineRanges[R.FileID].first =
419	std::min(a: FileLineRanges[R.FileID].first, b: R.LineStart);
420	FileLineRanges[R.FileID].second =
421	std::max(a: FileLineRanges[R.FileID].second, b: R.LineEnd);
422	}
423
424	auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
425	for (auto &I : SkippedRanges) {
426	SourceRange Range = I.Range;
427	auto LocStart = Range.getBegin();
428	auto LocEnd = Range.getEnd();
429	assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
430	"region spans multiple files");
431
432	auto CovFileID = getCoverageFileID(Loc: LocStart);
433	if (!CovFileID)
434	continue;
435	std::optional<SpellingRegion> SR;
436	if (I.isComment())
437	SR = adjustSkippedRange(SM, LocStart, LocEnd, PrevTokLoc: I.PrevTokLoc,
438	NextTokLoc: I.NextTokLoc);
439	else if (I.isPPIfElse() || I.isEmptyLine())
440	SR = {SM, LocStart, LocEnd};
441
442	if (!SR)
443	continue;
444	auto Region = CounterMappingRegion::makeSkipped(
445	FileID: *CovFileID, LineStart: SR->LineStart, ColumnStart: SR->ColumnStart, LineEnd: SR->LineEnd,
446	ColumnEnd: SR->ColumnEnd);
447	// Make sure that we only collect the regions that are inside
448	// the source code of this function.
449	if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
450	Region.LineEnd <= FileLineRanges[*CovFileID].second)
451	MappingRegions.push_back(Elt: Region);
452	}
453	}
454
455	/// Generate the coverage counter mapping regions from collected
456	/// source regions.
457	void emitSourceRegions(const SourceRegionFilter &Filter) {
458	for (const auto &Region : SourceRegions) {
459	assert(Region.hasEndLoc() && "incomplete region");
460
461	SourceLocation LocStart = Region.getBeginLoc();
462	assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
463
464	// Ignore regions from system headers unless collecting coverage from
465	// system headers is explicitly enabled.
466	if (!SystemHeadersCoverage &&
467	SM.isInSystemHeader(Loc: SM.getSpellingLoc(Loc: LocStart)))
468	continue;
469
470	auto CovFileID = getCoverageFileID(Loc: LocStart);
471	// Ignore regions that don't have a file, such as builtin macros.
472	if (!CovFileID)
473	continue;
474
475	SourceLocation LocEnd = Region.getEndLoc();
476	assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
477	"region spans multiple files");
478
479	// Don't add code regions for the area covered by expansion regions.
480	// This not only suppresses redundant regions, but sometimes prevents
481	// creating regions with wrong counters if, for example, a statement's
482	// body ends at the end of a nested macro.
483	if (Filter.count(V: std::make_pair(x&: LocStart, y&: LocEnd)))
484	continue;
485
486	// Find the spelling locations for the mapping region.
487	SpellingRegion SR{SM, LocStart, LocEnd};
488	assert(SR.isInSourceOrder() && "region start and end out of order");
489
490	if (Region.isGap()) {
491	MappingRegions.push_back(Elt: CounterMappingRegion::makeGapRegion(
492	Count: Region.getCounter(), FileID: *CovFileID, LineStart: SR.LineStart, ColumnStart: SR.ColumnStart,
493	LineEnd: SR.LineEnd, ColumnEnd: SR.ColumnEnd));
494	} else if (Region.isSkipped()) {
495	MappingRegions.push_back(Elt: CounterMappingRegion::makeSkipped(
496	FileID: *CovFileID, LineStart: SR.LineStart, ColumnStart: SR.ColumnStart, LineEnd: SR.LineEnd,
497	ColumnEnd: SR.ColumnEnd));
498	} else if (Region.isBranch()) {
499	MappingRegions.push_back(Elt: CounterMappingRegion::makeBranchRegion(
500	Count: Region.getCounter(), FalseCount: Region.getFalseCounter(), FileID: *CovFileID,
501	LineStart: SR.LineStart, ColumnStart: SR.ColumnStart, LineEnd: SR.LineEnd, ColumnEnd: SR.ColumnEnd,
502	MCDCParams: Region.getMCDCParams()));
503	} else if (Region.isMCDCDecision()) {
504	MappingRegions.push_back(Elt: CounterMappingRegion::makeDecisionRegion(
505	MCDCParams: Region.getMCDCDecisionParams(), FileID: *CovFileID, LineStart: SR.LineStart,
506	ColumnStart: SR.ColumnStart, LineEnd: SR.LineEnd, ColumnEnd: SR.ColumnEnd));
507	} else {
508	MappingRegions.push_back(Elt: CounterMappingRegion::makeRegion(
509	Count: Region.getCounter(), FileID: *CovFileID, LineStart: SR.LineStart, ColumnStart: SR.ColumnStart,
510	LineEnd: SR.LineEnd, ColumnEnd: SR.ColumnEnd));
511	}
512	}
513	}
514
515	/// Generate expansion regions for each virtual file we've seen.
516	SourceRegionFilter emitExpansionRegions() {
517	SourceRegionFilter Filter;
518	for (const auto &FM : FileIDMapping) {
519	SourceLocation ExpandedLoc = FM.second.second;
520	SourceLocation ParentLoc = getIncludeOrExpansionLoc(Loc: ExpandedLoc);
521	if (ParentLoc.isInvalid())
522	continue;
523
524	auto ParentFileID = getCoverageFileID(Loc: ParentLoc);
525	if (!ParentFileID)
526	continue;
527	auto ExpandedFileID = getCoverageFileID(Loc: ExpandedLoc);
528	assert(ExpandedFileID && "expansion in uncovered file");
529
530	SourceLocation LocEnd = getPreciseTokenLocEnd(Loc: ParentLoc);
531	assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
532	"region spans multiple files");
533	Filter.insert(V: std::make_pair(x&: ParentLoc, y&: LocEnd));
534
535	SpellingRegion SR{SM, ParentLoc, LocEnd};
536	assert(SR.isInSourceOrder() && "region start and end out of order");
537	MappingRegions.push_back(Elt: CounterMappingRegion::makeExpansion(
538	FileID: *ParentFileID, ExpandedFileID: *ExpandedFileID, LineStart: SR.LineStart, ColumnStart: SR.ColumnStart,
539	LineEnd: SR.LineEnd, ColumnEnd: SR.ColumnEnd));
540	}
541	return Filter;
542	}
543	};
544
545	/// Creates unreachable coverage regions for the functions that
546	/// are not emitted.
547	struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
548	EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
549	const LangOptions &LangOpts)
550	: CoverageMappingBuilder(CVM, SM, LangOpts) {}
551
552	void VisitDecl(const Decl *D) {
553	if (!D->hasBody())
554	return;
555	auto Body = D->getBody();
556	SourceLocation Start = getStart(S: Body);
557	SourceLocation End = getEnd(S: Body);
558	if (!SM.isWrittenInSameFile(Loc1: Start, Loc2: End)) {
559	// Walk up to find the common ancestor.
560	// Correct the locations accordingly.
561	FileID StartFileID = SM.getFileID(SpellingLoc: Start);
562	FileID EndFileID = SM.getFileID(SpellingLoc: End);
563	while (StartFileID != EndFileID && !isNestedIn(Loc: End, Parent: StartFileID)) {
564	Start = getIncludeOrExpansionLoc(Loc: Start);
565	assert(Start.isValid() &&
566	"Declaration start location not nested within a known region");
567	StartFileID = SM.getFileID(SpellingLoc: Start);
568	}
569	while (StartFileID != EndFileID) {
570	End = getPreciseTokenLocEnd(Loc: getIncludeOrExpansionLoc(Loc: End));
571	assert(End.isValid() &&
572	"Declaration end location not nested within a known region");
573	EndFileID = SM.getFileID(SpellingLoc: End);
574	}
575	}
576	SourceRegions.emplace_back(args: Counter(), args&: Start, args&: End);
577	}
578
579	/// Write the mapping data to the output stream
580	void write(llvm::raw_ostream &OS) {
581	SmallVector<unsigned, 16> FileIDMapping;
582	gatherFileIDs(Mapping&: FileIDMapping);
583	emitSourceRegions(Filter: SourceRegionFilter());
584
585	if (MappingRegions.empty())
586	return;
587
588	CoverageMappingWriter Writer(FileIDMapping, std::nullopt, MappingRegions);
589	Writer.write(OS);
590	}
591	};
592
593	/// A wrapper object for maintaining stacks to track the resursive AST visitor
594	/// walks for the purpose of assigning IDs to leaf-level conditions measured by
595	/// MC/DC. The object is created with a reference to the MCDCBitmapMap that was
596	/// created during the initial AST walk. The presence of a bitmap associated
597	/// with a boolean expression (top-level logical operator nest) indicates that
598	/// the boolean expression qualified for MC/DC. The resulting condition IDs
599	/// are preserved in a map reference that is also provided during object
600	/// creation.
601	struct MCDCCoverageBuilder {
602
603	/// The AST walk recursively visits nested logical-AND or logical-OR binary
604	/// operator nodes and then visits their LHS and RHS children nodes. As this
605	/// happens, the algorithm will assign IDs to each operator's LHS and RHS side
606	/// as the walk moves deeper into the nest. At each level of the recursive
607	/// nest, the LHS and RHS may actually correspond to larger subtrees (not
608	/// leaf-conditions). If this is the case, when that node is visited, the ID
609	/// assigned to the subtree is re-assigned to its LHS, and a new ID is given
610	/// to its RHS. At the end of the walk, all leaf-level conditions will have a
611	/// unique ID -- keep in mind that the final set of IDs may not be in
612	/// numerical order from left to right.
613	///
614	/// Example: "x = (A && B) || (C && D) || (D && F)"
615	///
616	/// Visit Depth1:
617	/// (A && B) || (C && D) || (D && F)
618	/// ^-------LHS--------^ ^-RHS--^
619	/// ID=1 ID=2
620	///
621	/// Visit LHS-Depth2:
622	/// (A && B) || (C && D)
623	/// ^-LHS--^ ^-RHS--^
624	/// ID=1 ID=3
625	///
626	/// Visit LHS-Depth3:
627	/// (A && B)
628	/// LHS RHS
629	/// ID=1 ID=4
630	///
631	/// Visit RHS-Depth3:
632	/// (C && D)
633	/// LHS RHS
634	/// ID=3 ID=5
635	///
636	/// Visit RHS-Depth2: (D && F)
637	/// LHS RHS
638	/// ID=2 ID=6
639	///
640	/// Visit Depth1:
641	/// (A && B) || (C && D) || (D && F)
642	/// ID=1 ID=4 ID=3 ID=5 ID=2 ID=6
643	///
644	/// A node ID of '0' always means MC/DC isn't being tracked.
645	///
646	/// As the AST walk proceeds recursively, the algorithm will also use a stack
647	/// to track the IDs of logical-AND and logical-OR operations on the RHS so
648	/// that it can be determined which nodes are executed next, depending on how
649	/// a LHS or RHS of a logical-AND or logical-OR is evaluated. This
650	/// information relies on the assigned IDs and are embedded within the
651	/// coverage region IDs of each branch region associated with a leaf-level
652	/// condition. This information helps the visualization tool reconstruct all
653	/// possible test vectors for the purposes of MC/DC analysis. If a "next" node
654	/// ID is '0', it means it's the end of the test vector. The following rules
655	/// are used:
656	///
657	/// For logical-AND ("LHS && RHS"):
658	/// - If LHS is TRUE, execution goes to the RHS node.
659	/// - If LHS is FALSE, execution goes to the LHS node of the next logical-OR.
660	/// If that does not exist, execution exits (ID == 0).
661	///
662	/// - If RHS is TRUE, execution goes to LHS node of the next logical-AND.
663	/// If that does not exist, execution exits (ID == 0).
664	/// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR.
665	/// If that does not exist, execution exits (ID == 0).
666	///
667	/// For logical-OR ("LHS || RHS"):
668	/// - If LHS is TRUE, execution goes to the LHS node of the next logical-AND.
669	/// If that does not exist, execution exits (ID == 0).
670	/// - If LHS is FALSE, execution goes to the RHS node.
671	///
672	/// - If RHS is TRUE, execution goes to LHS node of the next logical-AND.
673	/// If that does not exist, execution exits (ID == 0).
674	/// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR.
675	/// If that does not exist, execution exits (ID == 0).
676	///
677	/// Finally, the condition IDs are also used when instrumenting the code to
678	/// indicate a unique offset into a temporary bitmap that represents the true
679	/// or false evaluation of that particular condition.
680	///
681	/// NOTE regarding the use of CodeGenFunction::stripCond(). Even though, for
682	/// simplicity, parentheses and unary logical-NOT operators are considered
683	/// part of their underlying condition for both MC/DC and branch coverage, the
684	/// condition IDs themselves are assigned and tracked using the underlying
685	/// condition itself. This is done solely for consistency since parentheses
686	/// and logical-NOTs are ignored when checking whether the condition is
687	/// actually an instrumentable condition. This can also make debugging a bit
688	/// easier.
689
690	private:
691	CodeGenModule &CGM;
692
693	llvm::SmallVector<mcdc::ConditionIDs> DecisionStack;
694	MCDC::State &MCDCState;
695	mcdc::ConditionID NextID = 0;
696	bool NotMapped = false;
697
698	/// Represent a sentinel value as a pair of final decisions for the bottom
699	// of DecisionStack.
700	static constexpr mcdc::ConditionIDs DecisionStackSentinel{-1, -1};
701
702	/// Is this a logical-AND operation?
703	bool isLAnd(const BinaryOperator *E) const {
704	return E->getOpcode() == BO_LAnd;
705	}
706
707	public:
708	MCDCCoverageBuilder(CodeGenModule &CGM, MCDC::State &MCDCState)
709	: CGM(CGM), DecisionStack(1, DecisionStackSentinel),
710	MCDCState(MCDCState) {}
711
712	/// Return whether the build of the control flow map is at the top-level
713	/// (root) of a logical operator nest in a boolean expression prior to the
714	/// assignment of condition IDs.
715	bool isIdle() const { return (NextID == 0 && !NotMapped); }
716
717	/// Return whether any IDs have been assigned in the build of the control
718	/// flow map, indicating that the map is being generated for this boolean
719	/// expression.
720	bool isBuilding() const { return (NextID > 0); }
721
722	/// Set the given condition's ID.
723	void setCondID(const Expr *Cond, mcdc::ConditionID ID) {
724	MCDCState.BranchByStmt[CodeGenFunction::stripCond(Cond)].ID = ID;
725	}
726
727	/// Return the ID of a given condition.
728	mcdc::ConditionID getCondID(const Expr *Cond) const {
729	auto I = MCDCState.BranchByStmt.find(CodeGenFunction::stripCond(C: Cond));
730	if (I == MCDCState.BranchByStmt.end())
731	return -1;
732	else
733	return I->second.ID;
734	}
735
736	/// Return the LHS Decision ([0,0] if not set).
737	const mcdc::ConditionIDs &back() const { return DecisionStack.back(); }
738
739	/// Push the binary operator statement to track the nest level and assign IDs
740	/// to the operator's LHS and RHS. The RHS may be a larger subtree that is
741	/// broken up on successive levels.
742	void pushAndAssignIDs(const BinaryOperator *E) {
743	if (!CGM.getCodeGenOpts().MCDCCoverage)
744	return;
745
746	// If binary expression is disqualified, don't do mapping.
747	if (!isBuilding() &&
748	!MCDCState.DecisionByStmt.contains(Val: CodeGenFunction::stripCond(E)))
749	NotMapped = true;
750
751	// Don't go any further if we don't need to map condition IDs.
752	if (NotMapped)
753	return;
754
755	const mcdc::ConditionIDs &ParentDecision = DecisionStack.back();
756
757	// If the operator itself has an assigned ID, this means it represents a
758	// larger subtree. In this case, assign that ID to its LHS node. Its RHS
759	// will receive a new ID below. Otherwise, assign ID+1 to LHS.
760	if (MCDCState.BranchByStmt.contains(Val: CodeGenFunction::stripCond(E)))
761	setCondID(Cond: E->getLHS(), ID: getCondID(E));
762	else
763	setCondID(Cond: E->getLHS(), ID: NextID++);
764
765	// Assign a ID+1 for the RHS.
766	mcdc::ConditionID RHSid = NextID++;
767	setCondID(Cond: E->getRHS(), ID: RHSid);
768
769	// Push the LHS decision IDs onto the DecisionStack.
770	if (isLAnd(E))
771	DecisionStack.push_back(Elt: {ParentDecision[false], RHSid});
772	else
773	DecisionStack.push_back(Elt: {RHSid, ParentDecision[true]});
774	}
775
776	/// Pop and return the LHS Decision ([0,0] if not set).
777	mcdc::ConditionIDs pop() {
778	if (!CGM.getCodeGenOpts().MCDCCoverage || NotMapped)
779	return DecisionStackSentinel;
780
781	assert(DecisionStack.size() > 1);
782	return DecisionStack.pop_back_val();
783	}
784
785	/// Return the total number of conditions and reset the state. The number of
786	/// conditions is zero if the expression isn't mapped.
787	unsigned getTotalConditionsAndReset(const BinaryOperator *E) {
788	if (!CGM.getCodeGenOpts().MCDCCoverage)
789	return 0;
790
791	assert(!isIdle());
792	assert(DecisionStack.size() == 1);
793
794	// Reset state if not doing mapping.
795	if (NotMapped) {
796	NotMapped = false;
797	assert(NextID == 0);
798	return 0;
799	}
800
801	// Set number of conditions and reset.
802	unsigned TotalConds = NextID;
803
804	// Reset ID back to beginning.
805	NextID = 0;
806
807	return TotalConds;
808	}
809	};
810
811	/// A StmtVisitor that creates coverage mapping regions which map
812	/// from the source code locations to the PGO counters.
813	struct CounterCoverageMappingBuilder
814	: public CoverageMappingBuilder,
815	public ConstStmtVisitor<CounterCoverageMappingBuilder> {
816	/// The map of statements to count values.
817	llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
818
819	MCDC::State &MCDCState;
820
821	/// A stack of currently live regions.
822	llvm::SmallVector<SourceMappingRegion> RegionStack;
823
824	/// An object to manage MCDC regions.
825	MCDCCoverageBuilder MCDCBuilder;
826
827	CounterExpressionBuilder Builder;
828
829	/// A location in the most recently visited file or macro.
830	///
831	/// This is used to adjust the active source regions appropriately when
832	/// expressions cross file or macro boundaries.
833	SourceLocation MostRecentLocation;
834
835	/// Whether the visitor at a terminate statement.
836	bool HasTerminateStmt = false;
837
838	/// Gap region counter after terminate statement.
839	Counter GapRegionCounter;
840
841	/// Return a counter for the subtraction of \c RHS from \c LHS
842	Counter subtractCounters(Counter LHS, Counter RHS, bool Simplify = true) {
843	assert(!llvm::EnableSingleByteCoverage &&
844	"cannot add counters when single byte coverage mode is enabled");
845	return Builder.subtract(LHS, RHS, Simplify);
846	}
847
848	/// Return a counter for the sum of \c LHS and \c RHS.
849	Counter addCounters(Counter LHS, Counter RHS, bool Simplify = true) {
850	assert(!llvm::EnableSingleByteCoverage &&
851	"cannot add counters when single byte coverage mode is enabled");
852	return Builder.add(LHS, RHS, Simplify);
853	}
854
855	Counter addCounters(Counter C1, Counter C2, Counter C3,
856	bool Simplify = true) {
857	assert(!llvm::EnableSingleByteCoverage &&
858	"cannot add counters when single byte coverage mode is enabled");
859	return addCounters(LHS: addCounters(LHS: C1, RHS: C2, Simplify), RHS: C3, Simplify);
860	}
861
862	/// Return the region counter for the given statement.
863	///
864	/// This should only be called on statements that have a dedicated counter.
865	Counter getRegionCounter(const Stmt *S) {
866	return Counter::getCounter(CounterId: CounterMap[S]);
867	}
868
869	/// Push a region onto the stack.
870	///
871	/// Returns the index on the stack where the region was pushed. This can be
872	/// used with popRegions to exit a "scope", ending the region that was pushed.
873	size_t pushRegion(Counter Count,
874	std::optional<SourceLocation> StartLoc = std::nullopt,
875	std::optional<SourceLocation> EndLoc = std::nullopt,
876	std::optional<Counter> FalseCount = std::nullopt,
877	const mcdc::Parameters &BranchParams = std::monostate()) {
878
879	if (StartLoc && !FalseCount) {
880	MostRecentLocation = *StartLoc;
881	}
882
883	// If either of these locations is invalid, something elsewhere in the
884	// compiler has broken.
885	assert((!StartLoc || StartLoc->isValid()) && "Start location is not valid");
886	assert((!EndLoc || EndLoc->isValid()) && "End location is not valid");
887
888	// However, we can still recover without crashing.
889	// If either location is invalid, set it to std::nullopt to avoid
890	// letting users of RegionStack think that region has a valid start/end
891	// location.
892	if (StartLoc && StartLoc->isInvalid())
893	StartLoc = std::nullopt;
894	if (EndLoc && EndLoc->isInvalid())
895	EndLoc = std::nullopt;
896	RegionStack.emplace_back(Args&: Count, Args&: FalseCount, Args: BranchParams, Args&: StartLoc, Args&: EndLoc);
897
898	return RegionStack.size() - 1;
899	}
900
901	size_t pushRegion(const mcdc::DecisionParameters &DecisionParams,
902	std::optional<SourceLocation> StartLoc = std::nullopt,
903	std::optional<SourceLocation> EndLoc = std::nullopt) {
904
905	RegionStack.emplace_back(Args: DecisionParams, Args&: StartLoc, Args&: EndLoc);
906
907	return RegionStack.size() - 1;
908	}
909
910	size_t locationDepth(SourceLocation Loc) {
911	size_t Depth = 0;
912	while (Loc.isValid()) {
913	Loc = getIncludeOrExpansionLoc(Loc);
914	Depth++;
915	}
916	return Depth;
917	}
918
919	/// Pop regions from the stack into the function's list of regions.
920	///
921	/// Adds all regions from \c ParentIndex to the top of the stack to the
922	/// function's \c SourceRegions.
923	void popRegions(size_t ParentIndex) {
924	assert(RegionStack.size() >= ParentIndex && "parent not in stack");
925	while (RegionStack.size() > ParentIndex) {
926	SourceMappingRegion &Region = RegionStack.back();
927	if (Region.hasStartLoc() &&
928	(Region.hasEndLoc() || RegionStack[ParentIndex].hasEndLoc())) {
929	SourceLocation StartLoc = Region.getBeginLoc();
930	SourceLocation EndLoc = Region.hasEndLoc()
931	? Region.getEndLoc()
932	: RegionStack[ParentIndex].getEndLoc();
933	bool isBranch = Region.isBranch();
934	size_t StartDepth = locationDepth(Loc: StartLoc);
935	size_t EndDepth = locationDepth(Loc: EndLoc);
936	while (!SM.isWrittenInSameFile(Loc1: StartLoc, Loc2: EndLoc)) {
937	bool UnnestStart = StartDepth >= EndDepth;
938	bool UnnestEnd = EndDepth >= StartDepth;
939	if (UnnestEnd) {
940	// The region ends in a nested file or macro expansion. If the
941	// region is not a branch region, create a separate region for each
942	// expansion, and for all regions, update the EndLoc. Branch
943	// regions should not be split in order to keep a straightforward
944	// correspondance between the region and its associated branch
945	// condition, even if the condition spans multiple depths.
946	SourceLocation NestedLoc = getStartOfFileOrMacro(Loc: EndLoc);
947	assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
948
949	if (!isBranch && !isRegionAlreadyAdded(StartLoc: NestedLoc, EndLoc))
950	SourceRegions.emplace_back(args: Region.getCounter(), args&: NestedLoc,
951	args&: EndLoc);
952
953	EndLoc = getPreciseTokenLocEnd(Loc: getIncludeOrExpansionLoc(Loc: EndLoc));
954	if (EndLoc.isInvalid())
955	llvm::report_fatal_error(
956	reason: "File exit not handled before popRegions");
957	EndDepth--;
958	}
959	if (UnnestStart) {
960	// The region ends in a nested file or macro expansion. If the
961	// region is not a branch region, create a separate region for each
962	// expansion, and for all regions, update the StartLoc. Branch
963	// regions should not be split in order to keep a straightforward
964	// correspondance between the region and its associated branch
965	// condition, even if the condition spans multiple depths.
966	SourceLocation NestedLoc = getEndOfFileOrMacro(Loc: StartLoc);
967	assert(SM.isWrittenInSameFile(StartLoc, NestedLoc));
968
969	if (!isBranch && !isRegionAlreadyAdded(StartLoc, EndLoc: NestedLoc))
970	SourceRegions.emplace_back(args: Region.getCounter(), args&: StartLoc,
971	args&: NestedLoc);
972
973	StartLoc = getIncludeOrExpansionLoc(Loc: StartLoc);
974	if (StartLoc.isInvalid())
975	llvm::report_fatal_error(
976	reason: "File exit not handled before popRegions");
977	StartDepth--;
978	}
979	}
980	Region.setStartLoc(StartLoc);
981	Region.setEndLoc(EndLoc);
982
983	if (!isBranch) {
984	MostRecentLocation = EndLoc;
985	// If this region happens to span an entire expansion, we need to
986	// make sure we don't overlap the parent region with it.
987	if (StartLoc == getStartOfFileOrMacro(Loc: StartLoc) &&
988	EndLoc == getEndOfFileOrMacro(Loc: EndLoc))
989	MostRecentLocation = getIncludeOrExpansionLoc(Loc: EndLoc);
990	}
991
992	assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc));
993	assert(SpellingRegion(SM, Region).isInSourceOrder());
994	SourceRegions.push_back(x: Region);
995	}
996	RegionStack.pop_back();
997	}
998	}
999
1000	/// Return the currently active region.
1001	SourceMappingRegion &getRegion() {
1002	assert(!RegionStack.empty() && "statement has no region");
1003	return RegionStack.back();
1004	}
1005
1006	/// Propagate counts through the children of \p S if \p VisitChildren is true.
1007	/// Otherwise, only emit a count for \p S itself.
1008	Counter propagateCounts(Counter TopCount, const Stmt *S,
1009	bool VisitChildren = true) {
1010	SourceLocation StartLoc = getStart(S);
1011	SourceLocation EndLoc = getEnd(S);
1012	size_t Index = pushRegion(Count: TopCount, StartLoc, EndLoc);
1013	if (VisitChildren)
1014	Visit(S);
1015	Counter ExitCount = getRegion().getCounter();
1016	popRegions(ParentIndex: Index);
1017
1018	// The statement may be spanned by an expansion. Make sure we handle a file
1019	// exit out of this expansion before moving to the next statement.
1020	if (SM.isBeforeInTranslationUnit(LHS: StartLoc, RHS: S->getBeginLoc()))
1021	MostRecentLocation = EndLoc;
1022
1023	return ExitCount;
1024	}
1025
1026	/// Determine whether the given condition can be constant folded.
1027	bool ConditionFoldsToBool(const Expr *Cond) {
1028	Expr::EvalResult Result;
1029	return (Cond->EvaluateAsInt(Result, Ctx: CVM.getCodeGenModule().getContext()));
1030	}
1031
1032	/// Create a Branch Region around an instrumentable condition for coverage
1033	/// and add it to the function's SourceRegions. A branch region tracks a
1034	/// "True" counter and a "False" counter for boolean expressions that
1035	/// result in the generation of a branch.
1036	void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt,
1037	const mcdc::ConditionIDs &Conds = {}) {
1038	// Check for NULL conditions.
1039	if (!C)
1040	return;
1041
1042	// Ensure we are an instrumentable condition (i.e. no "&&" or "||"). Push
1043	// region onto RegionStack but immediately pop it (which adds it to the
1044	// function's SourceRegions) because it doesn't apply to any other source
1045	// code other than the Condition.
1046	if (CodeGenFunction::isInstrumentedCondition(C)) {
1047	mcdc::Parameters BranchParams;
1048	mcdc::ConditionID ID = MCDCBuilder.getCondID(Cond: C);
1049	if (ID >= 0)
1050	BranchParams = mcdc::BranchParameters{ID, Conds};
1051
1052	// If a condition can fold to true or false, the corresponding branch
1053	// will be removed. Create a region with both counters hard-coded to
1054	// zero. This allows us to visualize them in a special way.
1055	// Alternatively, we can prevent any optimization done via
1056	// constant-folding by ensuring that ConstantFoldsToSimpleInteger() in
1057	// CodeGenFunction.c always returns false, but that is very heavy-handed.
1058	if (ConditionFoldsToBool(Cond: C))
1059	popRegions(ParentIndex: pushRegion(Count: Counter::getZero(), StartLoc: getStart(C), EndLoc: getEnd(C),
1060	FalseCount: Counter::getZero(), BranchParams));
1061	else
1062	// Otherwise, create a region with the True counter and False counter.
1063	popRegions(ParentIndex: pushRegion(Count: TrueCnt, StartLoc: getStart(C), EndLoc: getEnd(C), FalseCount: FalseCnt,
1064	BranchParams));
1065	}
1066	}
1067
1068	/// Create a Decision Region with a BitmapIdx and number of Conditions. This
1069	/// type of region "contains" branch regions, one for each of the conditions.
1070	/// The visualization tool will group everything together.
1071	void createDecisionRegion(const Expr *C,
1072	const mcdc::DecisionParameters &DecisionParams) {
1073	popRegions(ParentIndex: pushRegion(DecisionParams, StartLoc: getStart(C), EndLoc: getEnd(C)));
1074	}
1075
1076	/// Create a Branch Region around a SwitchCase for code coverage
1077	/// and add it to the function's SourceRegions.
1078	void createSwitchCaseRegion(const SwitchCase *SC, Counter TrueCnt,
1079	Counter FalseCnt) {
1080	// Push region onto RegionStack but immediately pop it (which adds it to
1081	// the function's SourceRegions) because it doesn't apply to any other
1082	// source other than the SwitchCase.
1083	popRegions(ParentIndex: pushRegion(Count: TrueCnt, StartLoc: getStart(S: SC), EndLoc: SC->getColonLoc(), FalseCount: FalseCnt));
1084	}
1085
1086	/// Check whether a region with bounds \c StartLoc and \c EndLoc
1087	/// is already added to \c SourceRegions.
1088	bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc,
1089	bool isBranch = false) {
1090	return llvm::any_of(
1091	Range: llvm::reverse(C&: SourceRegions), P: [&](const SourceMappingRegion &Region) {
1092	return Region.getBeginLoc() == StartLoc &&
1093	Region.getEndLoc() == EndLoc && Region.isBranch() == isBranch;
1094	});
1095	}
1096
1097	/// Adjust the most recently visited location to \c EndLoc.
1098	///
1099	/// This should be used after visiting any statements in non-source order.
1100	void adjustForOutOfOrderTraversal(SourceLocation EndLoc) {
1101	MostRecentLocation = EndLoc;
1102	// The code region for a whole macro is created in handleFileExit() when
1103	// it detects exiting of the virtual file of that macro. If we visited
1104	// statements in non-source order, we might already have such a region
1105	// added, for example, if a body of a loop is divided among multiple
1106	// macros. Avoid adding duplicate regions in such case.
1107	if (getRegion().hasEndLoc() &&
1108	MostRecentLocation == getEndOfFileOrMacro(Loc: MostRecentLocation) &&
1109	isRegionAlreadyAdded(StartLoc: getStartOfFileOrMacro(Loc: MostRecentLocation),
1110	EndLoc: MostRecentLocation, isBranch: getRegion().isBranch()))
1111	MostRecentLocation = getIncludeOrExpansionLoc(Loc: MostRecentLocation);
1112	}
1113
1114	/// Adjust regions and state when \c NewLoc exits a file.
1115	///
1116	/// If moving from our most recently tracked location to \c NewLoc exits any
1117	/// files, this adjusts our current region stack and creates the file regions
1118	/// for the exited file.
1119	void handleFileExit(SourceLocation NewLoc) {
1120	if (NewLoc.isInvalid() ||
1121	SM.isWrittenInSameFile(Loc1: MostRecentLocation, Loc2: NewLoc))
1122	return;
1123
1124	// If NewLoc is not in a file that contains MostRecentLocation, walk up to
1125	// find the common ancestor.
1126	SourceLocation LCA = NewLoc;
1127	FileID ParentFile = SM.getFileID(SpellingLoc: LCA);
1128	while (!isNestedIn(Loc: MostRecentLocation, Parent: ParentFile)) {
1129	LCA = getIncludeOrExpansionLoc(Loc: LCA);
1130	if (LCA.isInvalid() || SM.isWrittenInSameFile(Loc1: LCA, Loc2: MostRecentLocation)) {
1131	// Since there isn't a common ancestor, no file was exited. We just need
1132	// to adjust our location to the new file.
1133	MostRecentLocation = NewLoc;
1134	return;
1135	}
1136	ParentFile = SM.getFileID(SpellingLoc: LCA);
1137	}
1138
1139	llvm::SmallSet<SourceLocation, 8> StartLocs;
1140	std::optional<Counter> ParentCounter;
1141	for (SourceMappingRegion &I : llvm::reverse(C&: RegionStack)) {
1142	if (!I.hasStartLoc())
1143	continue;
1144	SourceLocation Loc = I.getBeginLoc();
1145	if (!isNestedIn(Loc, Parent: ParentFile)) {
1146	ParentCounter = I.getCounter();
1147	break;
1148	}
1149
1150	while (!SM.isInFileID(Loc, FID: ParentFile)) {
1151	// The most nested region for each start location is the one with the
1152	// correct count. We avoid creating redundant regions by stopping once
1153	// we've seen this region.
1154	if (StartLocs.insert(V: Loc).second) {
1155	if (I.isBranch())
1156	SourceRegions.emplace_back(args: I.getCounter(), args: I.getFalseCounter(),
1157	args: I.getMCDCParams(), args&: Loc,
1158	args: getEndOfFileOrMacro(Loc), args: I.isBranch());
1159	else
1160	SourceRegions.emplace_back(args: I.getCounter(), args&: Loc,
1161	args: getEndOfFileOrMacro(Loc));
1162	}
1163	Loc = getIncludeOrExpansionLoc(Loc);
1164	}
1165	I.setStartLoc(getPreciseTokenLocEnd(Loc));
1166	}
1167
1168	if (ParentCounter) {
1169	// If the file is contained completely by another region and doesn't
1170	// immediately start its own region, the whole file gets a region
1171	// corresponding to the parent.
1172	SourceLocation Loc = MostRecentLocation;
1173	while (isNestedIn(Loc, Parent: ParentFile)) {
1174	SourceLocation FileStart = getStartOfFileOrMacro(Loc);
1175	if (StartLocs.insert(V: FileStart).second) {
1176	SourceRegions.emplace_back(args&: *ParentCounter, args&: FileStart,
1177	args: getEndOfFileOrMacro(Loc));
1178	assert(SpellingRegion(SM, SourceRegions.back()).isInSourceOrder());
1179	}
1180	Loc = getIncludeOrExpansionLoc(Loc);
1181	}
1182	}
1183
1184	MostRecentLocation = NewLoc;
1185	}
1186
1187	/// Ensure that \c S is included in the current region.
1188	void extendRegion(const Stmt *S) {
1189	SourceMappingRegion &Region = getRegion();
1190	SourceLocation StartLoc = getStart(S);
1191
1192	handleFileExit(NewLoc: StartLoc);
1193	if (!Region.hasStartLoc())
1194	Region.setStartLoc(StartLoc);
1195	}
1196
1197	/// Mark \c S as a terminator, starting a zero region.
1198	void terminateRegion(const Stmt *S) {
1199	extendRegion(S);
1200	SourceMappingRegion &Region = getRegion();
1201	SourceLocation EndLoc = getEnd(S);
1202	if (!Region.hasEndLoc())
1203	Region.setEndLoc(EndLoc);
1204	pushRegion(Count: Counter::getZero());
1205	HasTerminateStmt = true;
1206	}
1207
1208	/// Find a valid gap range between \p AfterLoc and \p BeforeLoc.
1209	std::optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc,
1210	SourceLocation BeforeLoc) {
1211	// Some statements (like AttributedStmt and ImplicitValueInitExpr) don't
1212	// have valid source locations. Do not emit a gap region if this is the case
1213	// in either AfterLoc end or BeforeLoc end.
1214	if (AfterLoc.isInvalid() || BeforeLoc.isInvalid())
1215	return std::nullopt;
1216
1217	// If AfterLoc is in function-like macro, use the right parenthesis
1218	// location.
1219	if (AfterLoc.isMacroID()) {
1220	FileID FID = SM.getFileID(SpellingLoc: AfterLoc);
1221	const SrcMgr::ExpansionInfo *EI = &SM.getSLocEntry(FID).getExpansion();
1222	if (EI->isFunctionMacroExpansion())
1223	AfterLoc = EI->getExpansionLocEnd();
1224	}
1225
1226	size_t StartDepth = locationDepth(Loc: AfterLoc);
1227	size_t EndDepth = locationDepth(Loc: BeforeLoc);
1228	while (!SM.isWrittenInSameFile(Loc1: AfterLoc, Loc2: BeforeLoc)) {
1229	bool UnnestStart = StartDepth >= EndDepth;
1230	bool UnnestEnd = EndDepth >= StartDepth;
1231	if (UnnestEnd) {
1232	assert(SM.isWrittenInSameFile(getStartOfFileOrMacro(BeforeLoc),
1233	BeforeLoc));
1234
1235	BeforeLoc = getIncludeOrExpansionLoc(Loc: BeforeLoc);
1236	assert(BeforeLoc.isValid());
1237	EndDepth--;
1238	}
1239	if (UnnestStart) {
1240	assert(SM.isWrittenInSameFile(AfterLoc,
1241	getEndOfFileOrMacro(AfterLoc)));
1242
1243	AfterLoc = getIncludeOrExpansionLoc(Loc: AfterLoc);
1244	assert(AfterLoc.isValid());
1245	AfterLoc = getPreciseTokenLocEnd(Loc: AfterLoc);
1246	assert(AfterLoc.isValid());
1247	StartDepth--;
1248	}
1249	}
1250	AfterLoc = getPreciseTokenLocEnd(Loc: AfterLoc);
1251	// If the start and end locations of the gap are both within the same macro
1252	// file, the range may not be in source order.
1253	if (AfterLoc.isMacroID() || BeforeLoc.isMacroID())
1254	return std::nullopt;
1255	if (!SM.isWrittenInSameFile(Loc1: AfterLoc, Loc2: BeforeLoc) ||
1256	!SpellingRegion(SM, AfterLoc, BeforeLoc).isInSourceOrder())
1257	return std::nullopt;
1258	return {{AfterLoc, BeforeLoc}};
1259	}
1260
1261	/// Emit a gap region between \p StartLoc and \p EndLoc with the given count.
1262	void fillGapAreaWithCount(SourceLocation StartLoc, SourceLocation EndLoc,
1263	Counter Count) {
1264	if (StartLoc == EndLoc)
1265	return;
1266	assert(SpellingRegion(SM, StartLoc, EndLoc).isInSourceOrder());
1267	handleFileExit(NewLoc: StartLoc);
1268	size_t Index = pushRegion(Count, StartLoc, EndLoc);
1269	getRegion().setGap(true);
1270	handleFileExit(NewLoc: EndLoc);
1271	popRegions(ParentIndex: Index);
1272	}
1273
1274	/// Find a valid range starting with \p StartingLoc and ending before \p
1275	/// BeforeLoc.
1276	std::optional<SourceRange> findAreaStartingFromTo(SourceLocation StartingLoc,
1277	SourceLocation BeforeLoc) {
1278	// If StartingLoc is in function-like macro, use its start location.
1279	if (StartingLoc.isMacroID()) {
1280	FileID FID = SM.getFileID(SpellingLoc: StartingLoc);
1281	const SrcMgr::ExpansionInfo *EI = &SM.getSLocEntry(FID).getExpansion();
1282	if (EI->isFunctionMacroExpansion())
1283	StartingLoc = EI->getExpansionLocStart();
1284	}
1285
1286	size_t StartDepth = locationDepth(Loc: StartingLoc);
1287	size_t EndDepth = locationDepth(Loc: BeforeLoc);
1288	while (!SM.isWrittenInSameFile(Loc1: StartingLoc, Loc2: BeforeLoc)) {
1289	bool UnnestStart = StartDepth >= EndDepth;
1290	bool UnnestEnd = EndDepth >= StartDepth;
1291	if (UnnestEnd) {
1292	assert(SM.isWrittenInSameFile(getStartOfFileOrMacro(BeforeLoc),
1293	BeforeLoc));
1294
1295	BeforeLoc = getIncludeOrExpansionLoc(Loc: BeforeLoc);
1296	assert(BeforeLoc.isValid());
1297	EndDepth--;
1298	}
1299	if (UnnestStart) {
1300	assert(SM.isWrittenInSameFile(StartingLoc,
1301	getStartOfFileOrMacro(StartingLoc)));
1302
1303	StartingLoc = getIncludeOrExpansionLoc(Loc: StartingLoc);
1304	assert(StartingLoc.isValid());
1305	StartDepth--;
1306	}
1307	}
1308	// If the start and end locations of the gap are both within the same macro
1309	// file, the range may not be in source order.
1310	if (StartingLoc.isMacroID() || BeforeLoc.isMacroID())
1311	return std::nullopt;
1312	if (!SM.isWrittenInSameFile(Loc1: StartingLoc, Loc2: BeforeLoc) ||
1313	!SpellingRegion(SM, StartingLoc, BeforeLoc).isInSourceOrder())
1314	return std::nullopt;
1315	return {{StartingLoc, BeforeLoc}};
1316	}
1317
1318	void markSkipped(SourceLocation StartLoc, SourceLocation BeforeLoc) {
1319	const auto Skipped = findAreaStartingFromTo(StartingLoc: StartLoc, BeforeLoc);
1320
1321	if (!Skipped)
1322	return;
1323
1324	const auto NewStartLoc = Skipped->getBegin();
1325	const auto EndLoc = Skipped->getEnd();
1326
1327	if (NewStartLoc == EndLoc)
1328	return;
1329	assert(SpellingRegion(SM, NewStartLoc, EndLoc).isInSourceOrder());
1330	handleFileExit(NewLoc: NewStartLoc);
1331	size_t Index = pushRegion(Count: Counter{}, StartLoc: NewStartLoc, EndLoc);
1332	getRegion().setSkipped(true);
1333	handleFileExit(NewLoc: EndLoc);
1334	popRegions(ParentIndex: Index);
1335	}
1336
1337	/// Keep counts of breaks and continues inside loops.
1338	struct BreakContinue {
1339	Counter BreakCount;
1340	Counter ContinueCount;
1341	};
1342	SmallVector<BreakContinue, 8> BreakContinueStack;
1343
1344	CounterCoverageMappingBuilder(
1345	CoverageMappingModuleGen &CVM,
1346	llvm::DenseMap<const Stmt *, unsigned> &CounterMap,
1347	MCDC::State &MCDCState, SourceManager &SM, const LangOptions &LangOpts)
1348	: CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap),
1349	MCDCState(MCDCState), MCDCBuilder(CVM.getCodeGenModule(), MCDCState) {}
1350
1351	/// Write the mapping data to the output stream
1352	void write(llvm::raw_ostream &OS) {
1353	llvm::SmallVector<unsigned, 8> VirtualFileMapping;
1354	gatherFileIDs(Mapping&: VirtualFileMapping);
1355	SourceRegionFilter Filter = emitExpansionRegions();
1356	emitSourceRegions(Filter);
1357	gatherSkippedRegions();
1358
1359	if (MappingRegions.empty())
1360	return;
1361
1362	CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
1363	MappingRegions);
1364	Writer.write(OS);
1365	}
1366
1367	void VisitStmt(const Stmt *S) {
1368	if (S->getBeginLoc().isValid())
1369	extendRegion(S);
1370	const Stmt *LastStmt = nullptr;
1371	bool SaveTerminateStmt = HasTerminateStmt;
1372	HasTerminateStmt = false;
1373	GapRegionCounter = Counter::getZero();
1374	for (const Stmt *Child : S->children())
1375	if (Child) {
1376	// If last statement contains terminate statements, add a gap area
1377	// between the two statements.
1378	if (LastStmt && HasTerminateStmt) {
1379	auto Gap = findGapAreaBetween(AfterLoc: getEnd(S: LastStmt), BeforeLoc: getStart(S: Child));
1380	if (Gap)
1381	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(),
1382	Count: GapRegionCounter);
1383	SaveTerminateStmt = true;
1384	HasTerminateStmt = false;
1385	}
1386	this->Visit(Child);
1387	LastStmt = Child;
1388	}
1389	if (SaveTerminateStmt)
1390	HasTerminateStmt = true;
1391	handleFileExit(NewLoc: getEnd(S));
1392	}
1393
1394	void VisitDecl(const Decl *D) {
1395	Stmt *Body = D->getBody();
1396
1397	// Do not propagate region counts into system headers unless collecting
1398	// coverage from system headers is explicitly enabled.
1399	if (!SystemHeadersCoverage && Body &&
1400	SM.isInSystemHeader(Loc: SM.getSpellingLoc(Loc: getStart(S: Body))))
1401	return;
1402
1403	// Do not visit the artificial children nodes of defaulted methods. The
1404	// lexer may not be able to report back precise token end locations for
1405	// these children nodes (llvm.org/PR39822), and moreover users will not be
1406	// able to see coverage for them.
1407	Counter BodyCounter = getRegionCounter(S: Body);
1408	bool Defaulted = false;
1409	if (auto *Method = dyn_cast<CXXMethodDecl>(Val: D))
1410	Defaulted = Method->isDefaulted();
1411	if (auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: D)) {
1412	for (auto *Initializer : Ctor->inits()) {
1413	if (Initializer->isWritten()) {
1414	auto *Init = Initializer->getInit();
1415	if (getStart(Init).isValid() && getEnd(Init).isValid())
1416	propagateCounts(BodyCounter, Init);
1417	}
1418	}
1419	}
1420
1421	propagateCounts(TopCount: BodyCounter, S: Body,
1422	/*VisitChildren=*/!Defaulted);
1423	assert(RegionStack.empty() && "Regions entered but never exited");
1424	}
1425
1426	void VisitReturnStmt(const ReturnStmt *S) {
1427	extendRegion(S);
1428	if (S->getRetValue())
1429	Visit(S->getRetValue());
1430	terminateRegion(S);
1431	}
1432
1433	void VisitCoroutineBodyStmt(const CoroutineBodyStmt *S) {
1434	extendRegion(S);
1435	Visit(S->getBody());
1436	}
1437
1438	void VisitCoreturnStmt(const CoreturnStmt *S) {
1439	extendRegion(S);
1440	if (S->getOperand())
1441	Visit(S->getOperand());
1442	terminateRegion(S);
1443	}
1444
1445	void VisitCXXThrowExpr(const CXXThrowExpr *E) {
1446	extendRegion(E);
1447	if (E->getSubExpr())
1448	Visit(E->getSubExpr());
1449	terminateRegion(E);
1450	}
1451
1452	void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
1453
1454	void VisitLabelStmt(const LabelStmt *S) {
1455	Counter LabelCount = getRegionCounter(S);
1456	SourceLocation Start = getStart(S);
1457	// We can't extendRegion here or we risk overlapping with our new region.
1458	handleFileExit(NewLoc: Start);
1459	pushRegion(Count: LabelCount, StartLoc: Start);
1460	Visit(S->getSubStmt());
1461	}
1462
1463	void VisitBreakStmt(const BreakStmt *S) {
1464	assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
1465	if (!llvm::EnableSingleByteCoverage)
1466	BreakContinueStack.back().BreakCount = addCounters(
1467	LHS: BreakContinueStack.back().BreakCount, RHS: getRegion().getCounter());
1468	// FIXME: a break in a switch should terminate regions for all preceding
1469	// case statements, not just the most recent one.
1470	terminateRegion(S);
1471	}
1472
1473	void VisitContinueStmt(const ContinueStmt *S) {
1474	assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
1475	if (!llvm::EnableSingleByteCoverage)
1476	BreakContinueStack.back().ContinueCount = addCounters(
1477	LHS: BreakContinueStack.back().ContinueCount, RHS: getRegion().getCounter());
1478	terminateRegion(S);
1479	}
1480
1481	void VisitCallExpr(const CallExpr *E) {
1482	VisitStmt(E);
1483
1484	// Terminate the region when we hit a noreturn function.
1485	// (This is helpful dealing with switch statements.)
1486	QualType CalleeType = E->getCallee()->getType();
1487	if (getFunctionExtInfo(t: *CalleeType).getNoReturn())
1488	terminateRegion(E);
1489	}
1490
1491	void VisitWhileStmt(const WhileStmt *S) {
1492	extendRegion(S);
1493
1494	Counter ParentCount = getRegion().getCounter();
1495	Counter BodyCount = llvm::EnableSingleByteCoverage
1496	? getRegionCounter(S: S->getBody())
1497	: getRegionCounter(S);
1498
1499	// Handle the body first so that we can get the backedge count.
1500	BreakContinueStack.push_back(Elt: BreakContinue());
1501	extendRegion(S: S->getBody());
1502	Counter BackedgeCount = propagateCounts(TopCount: BodyCount, S: S->getBody());
1503	BreakContinue BC = BreakContinueStack.pop_back_val();
1504
1505	bool BodyHasTerminateStmt = HasTerminateStmt;
1506	HasTerminateStmt = false;
1507
1508	// Go back to handle the condition.
1509	Counter CondCount =
1510	llvm::EnableSingleByteCoverage
1511	? getRegionCounter(S->getCond())
1512	: addCounters(C1: ParentCount, C2: BackedgeCount, C3: BC.ContinueCount);
1513	propagateCounts(CondCount, S->getCond());
1514	adjustForOutOfOrderTraversal(EndLoc: getEnd(S));
1515
1516	// The body count applies to the area immediately after the increment.
1517	auto Gap = findGapAreaBetween(AfterLoc: S->getRParenLoc(), BeforeLoc: getStart(S: S->getBody()));
1518	if (Gap)
1519	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: BodyCount);
1520
1521	Counter OutCount =
1522	llvm::EnableSingleByteCoverage
1523	? getRegionCounter(S)
1524	: addCounters(LHS: BC.BreakCount,
1525	RHS: subtractCounters(LHS: CondCount, RHS: BodyCount));
1526
1527	if (OutCount != ParentCount) {
1528	pushRegion(Count: OutCount);
1529	GapRegionCounter = OutCount;
1530	if (BodyHasTerminateStmt)
1531	HasTerminateStmt = true;
1532	}
1533
1534	// Create Branch Region around condition.
1535	if (!llvm::EnableSingleByteCoverage)
1536	createBranchRegion(C: S->getCond(), TrueCnt: BodyCount,
1537	FalseCnt: subtractCounters(LHS: CondCount, RHS: BodyCount));
1538	}
1539
1540	void VisitDoStmt(const DoStmt *S) {
1541	extendRegion(S);
1542
1543	Counter ParentCount = getRegion().getCounter();
1544	Counter BodyCount = llvm::EnableSingleByteCoverage
1545	? getRegionCounter(S: S->getBody())
1546	: getRegionCounter(S);
1547
1548	BreakContinueStack.push_back(Elt: BreakContinue());
1549	extendRegion(S: S->getBody());
1550
1551	Counter BackedgeCount;
1552	if (llvm::EnableSingleByteCoverage)
1553	propagateCounts(TopCount: BodyCount, S: S->getBody());
1554	else
1555	BackedgeCount =
1556	propagateCounts(TopCount: addCounters(LHS: ParentCount, RHS: BodyCount), S: S->getBody());
1557
1558	BreakContinue BC = BreakContinueStack.pop_back_val();
1559
1560	bool BodyHasTerminateStmt = HasTerminateStmt;
1561	HasTerminateStmt = false;
1562
1563	Counter CondCount = llvm::EnableSingleByteCoverage
1564	? getRegionCounter(S->getCond())
1565	: addCounters(LHS: BackedgeCount, RHS: BC.ContinueCount);
1566	propagateCounts(CondCount, S->getCond());
1567
1568	Counter OutCount =
1569	llvm::EnableSingleByteCoverage
1570	? getRegionCounter(S)
1571	: addCounters(LHS: BC.BreakCount,
1572	RHS: subtractCounters(LHS: CondCount, RHS: BodyCount));
1573	if (OutCount != ParentCount) {
1574	pushRegion(Count: OutCount);
1575	GapRegionCounter = OutCount;
1576	}
1577
1578	// Create Branch Region around condition.
1579	if (!llvm::EnableSingleByteCoverage)
1580	createBranchRegion(C: S->getCond(), TrueCnt: BodyCount,
1581	FalseCnt: subtractCounters(LHS: CondCount, RHS: BodyCount));
1582
1583	if (BodyHasTerminateStmt)
1584	HasTerminateStmt = true;
1585	}
1586
1587	void VisitForStmt(const ForStmt *S) {
1588	extendRegion(S);
1589	if (S->getInit())
1590	Visit(S->getInit());
1591
1592	Counter ParentCount = getRegion().getCounter();
1593	Counter BodyCount = llvm::EnableSingleByteCoverage
1594	? getRegionCounter(S: S->getBody())
1595	: getRegionCounter(S);
1596
1597	// The loop increment may contain a break or continue.
1598	if (S->getInc())
1599	BreakContinueStack.emplace_back();
1600
1601	// Handle the body first so that we can get the backedge count.
1602	BreakContinueStack.emplace_back();
1603	extendRegion(S: S->getBody());
1604	Counter BackedgeCount = propagateCounts(TopCount: BodyCount, S: S->getBody());
1605	BreakContinue BodyBC = BreakContinueStack.pop_back_val();
1606
1607	bool BodyHasTerminateStmt = HasTerminateStmt;
1608	HasTerminateStmt = false;
1609
1610	// The increment is essentially part of the body but it needs to include
1611	// the count for all the continue statements.
1612	BreakContinue IncrementBC;
1613	if (const Stmt *Inc = S->getInc()) {
1614	Counter IncCount;
1615	if (llvm::EnableSingleByteCoverage)
1616	IncCount = getRegionCounter(S->getInc());
1617	else
1618	IncCount = addCounters(LHS: BackedgeCount, RHS: BodyBC.ContinueCount);
1619	propagateCounts(TopCount: IncCount, S: Inc);
1620	IncrementBC = BreakContinueStack.pop_back_val();
1621	}
1622
1623	// Go back to handle the condition.
1624	Counter CondCount =
1625	llvm::EnableSingleByteCoverage
1626	? getRegionCounter(S->getCond())
1627	: addCounters(
1628	LHS: addCounters(C1: ParentCount, C2: BackedgeCount, C3: BodyBC.ContinueCount),
1629	RHS: IncrementBC.ContinueCount);
1630
1631	if (const Expr *Cond = S->getCond()) {
1632	propagateCounts(CondCount, Cond);
1633	adjustForOutOfOrderTraversal(EndLoc: getEnd(S));
1634	}
1635
1636	// The body count applies to the area immediately after the increment.
1637	auto Gap = findGapAreaBetween(AfterLoc: S->getRParenLoc(), BeforeLoc: getStart(S: S->getBody()));
1638	if (Gap)
1639	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: BodyCount);
1640
1641	Counter OutCount =
1642	llvm::EnableSingleByteCoverage
1643	? getRegionCounter(S)
1644	: addCounters(C1: BodyBC.BreakCount, C2: IncrementBC.BreakCount,
1645	C3: subtractCounters(LHS: CondCount, RHS: BodyCount));
1646	if (OutCount != ParentCount) {
1647	pushRegion(Count: OutCount);
1648	GapRegionCounter = OutCount;
1649	if (BodyHasTerminateStmt)
1650	HasTerminateStmt = true;
1651	}
1652
1653	// Create Branch Region around condition.
1654	if (!llvm::EnableSingleByteCoverage)
1655	createBranchRegion(C: S->getCond(), TrueCnt: BodyCount,
1656	FalseCnt: subtractCounters(LHS: CondCount, RHS: BodyCount));
1657	}
1658
1659	void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1660	extendRegion(S);
1661	if (S->getInit())
1662	Visit(S->getInit());
1663	Visit(S->getLoopVarStmt());
1664	Visit(S->getRangeStmt());
1665
1666	Counter ParentCount = getRegion().getCounter();
1667	Counter BodyCount = llvm::EnableSingleByteCoverage
1668	? getRegionCounter(S: S->getBody())
1669	: getRegionCounter(S);
1670
1671	BreakContinueStack.push_back(Elt: BreakContinue());
1672	extendRegion(S: S->getBody());
1673	Counter BackedgeCount = propagateCounts(TopCount: BodyCount, S: S->getBody());
1674	BreakContinue BC = BreakContinueStack.pop_back_val();
1675
1676	bool BodyHasTerminateStmt = HasTerminateStmt;
1677	HasTerminateStmt = false;
1678
1679	// The body count applies to the area immediately after the range.
1680	auto Gap = findGapAreaBetween(AfterLoc: S->getRParenLoc(), BeforeLoc: getStart(S: S->getBody()));
1681	if (Gap)
1682	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: BodyCount);
1683
1684	Counter OutCount;
1685	Counter LoopCount;
1686	if (llvm::EnableSingleByteCoverage)
1687	OutCount = getRegionCounter(S);
1688	else {
1689	LoopCount = addCounters(C1: ParentCount, C2: BackedgeCount, C3: BC.ContinueCount);
1690	OutCount =
1691	addCounters(LHS: BC.BreakCount, RHS: subtractCounters(LHS: LoopCount, RHS: BodyCount));
1692	}
1693	if (OutCount != ParentCount) {
1694	pushRegion(Count: OutCount);
1695	GapRegionCounter = OutCount;
1696	if (BodyHasTerminateStmt)
1697	HasTerminateStmt = true;
1698	}
1699
1700	// Create Branch Region around condition.
1701	if (!llvm::EnableSingleByteCoverage)
1702	createBranchRegion(C: S->getCond(), TrueCnt: BodyCount,
1703	FalseCnt: subtractCounters(LHS: LoopCount, RHS: BodyCount));
1704	}
1705
1706	void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1707	extendRegion(S);
1708	Visit(S->getElement());
1709
1710	Counter ParentCount = getRegion().getCounter();
1711	Counter BodyCount = getRegionCounter(S);
1712
1713	BreakContinueStack.push_back(Elt: BreakContinue());
1714	extendRegion(S: S->getBody());
1715	Counter BackedgeCount = propagateCounts(TopCount: BodyCount, S: S->getBody());
1716	BreakContinue BC = BreakContinueStack.pop_back_val();
1717
1718	// The body count applies to the area immediately after the collection.
1719	auto Gap = findGapAreaBetween(AfterLoc: S->getRParenLoc(), BeforeLoc: getStart(S: S->getBody()));
1720	if (Gap)
1721	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: BodyCount);
1722
1723	Counter LoopCount =
1724	addCounters(C1: ParentCount, C2: BackedgeCount, C3: BC.ContinueCount);
1725	Counter OutCount =
1726	addCounters(LHS: BC.BreakCount, RHS: subtractCounters(LHS: LoopCount, RHS: BodyCount));
1727	if (OutCount != ParentCount) {
1728	pushRegion(Count: OutCount);
1729	GapRegionCounter = OutCount;
1730	}
1731	}
1732
1733	void VisitSwitchStmt(const SwitchStmt *S) {
1734	extendRegion(S);
1735	if (S->getInit())
1736	Visit(S->getInit());
1737	Visit(S->getCond());
1738
1739	BreakContinueStack.push_back(Elt: BreakContinue());
1740
1741	const Stmt *Body = S->getBody();
1742	extendRegion(S: Body);
1743	if (const auto *CS = dyn_cast<CompoundStmt>(Val: Body)) {
1744	if (!CS->body_empty()) {
1745	// Make a region for the body of the switch. If the body starts with
1746	// a case, that case will reuse this region; otherwise, this covers
1747	// the unreachable code at the beginning of the switch body.
1748	size_t Index = pushRegion(Count: Counter::getZero(), StartLoc: getStart(CS));
1749	getRegion().setGap(true);
1750	Visit(Body);
1751
1752	// Set the end for the body of the switch, if it isn't already set.
1753	for (size_t i = RegionStack.size(); i != Index; --i) {
1754	if (!RegionStack[i - 1].hasEndLoc())
1755	RegionStack[i - 1].setEndLoc(getEnd(S: CS->body_back()));
1756	}
1757
1758	popRegions(ParentIndex: Index);
1759	}
1760	} else
1761	propagateCounts(TopCount: Counter::getZero(), S: Body);
1762	BreakContinue BC = BreakContinueStack.pop_back_val();
1763
1764	if (!BreakContinueStack.empty() && !llvm::EnableSingleByteCoverage)
1765	BreakContinueStack.back().ContinueCount = addCounters(
1766	LHS: BreakContinueStack.back().ContinueCount, RHS: BC.ContinueCount);
1767
1768	Counter ParentCount = getRegion().getCounter();
1769	Counter ExitCount = getRegionCounter(S);
1770	SourceLocation ExitLoc = getEnd(S);
1771	pushRegion(Count: ExitCount);
1772	GapRegionCounter = ExitCount;
1773
1774	// Ensure that handleFileExit recognizes when the end location is located
1775	// in a different file.
1776	MostRecentLocation = getStart(S);
1777	handleFileExit(NewLoc: ExitLoc);
1778
1779	// When single byte coverage mode is enabled, do not create branch region by
1780	// early returning.
1781	if (llvm::EnableSingleByteCoverage)
1782	return;
1783
1784	// Create a Branch Region around each Case. Subtract the case's
1785	// counter from the Parent counter to track the "False" branch count.
1786	Counter CaseCountSum;
1787	bool HasDefaultCase = false;
1788	const SwitchCase *Case = S->getSwitchCaseList();
1789	for (; Case; Case = Case->getNextSwitchCase()) {
1790	HasDefaultCase = HasDefaultCase || isa<DefaultStmt>(Val: Case);
1791	CaseCountSum =
1792	addCounters(LHS: CaseCountSum, RHS: getRegionCounter(S: Case), /*Simplify=*/false);
1793	createSwitchCaseRegion(
1794	SC: Case, TrueCnt: getRegionCounter(S: Case),
1795	FalseCnt: subtractCounters(LHS: ParentCount, RHS: getRegionCounter(S: Case)));
1796	}
1797	// Simplify is skipped while building the counters above: it can get really
1798	// slow on top of switches with thousands of cases. Instead, trigger
1799	// simplification by adding zero to the last counter.
1800	CaseCountSum = addCounters(LHS: CaseCountSum, RHS: Counter::getZero());
1801
1802	// If no explicit default case exists, create a branch region to represent
1803	// the hidden branch, which will be added later by the CodeGen. This region
1804	// will be associated with the switch statement's condition.
1805	if (!HasDefaultCase) {
1806	Counter DefaultTrue = subtractCounters(LHS: ParentCount, RHS: CaseCountSum);
1807	Counter DefaultFalse = subtractCounters(LHS: ParentCount, RHS: DefaultTrue);
1808	createBranchRegion(C: S->getCond(), TrueCnt: DefaultTrue, FalseCnt: DefaultFalse);
1809	}
1810	}
1811
1812	void VisitSwitchCase(const SwitchCase *S) {
1813	extendRegion(S);
1814
1815	SourceMappingRegion &Parent = getRegion();
1816	Counter Count = llvm::EnableSingleByteCoverage
1817	? getRegionCounter(S)
1818	: addCounters(LHS: Parent.getCounter(), RHS: getRegionCounter(S));
1819
1820	// Reuse the existing region if it starts at our label. This is typical of
1821	// the first case in a switch.
1822	if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1823	Parent.setCounter(Count);
1824	else
1825	pushRegion(Count, StartLoc: getStart(S));
1826
1827	GapRegionCounter = Count;
1828
1829	if (const auto *CS = dyn_cast<CaseStmt>(Val: S)) {
1830	Visit(CS->getLHS());
1831	if (const Expr *RHS = CS->getRHS())
1832	Visit(RHS);
1833	}
1834	Visit(S->getSubStmt());
1835	}
1836
1837	void coverIfConsteval(const IfStmt *S) {
1838	assert(S->isConsteval());
1839
1840	const auto *Then = S->getThen();
1841	const auto *Else = S->getElse();
1842
1843	// It's better for llvm-cov to create a new region with same counter
1844	// so line-coverage can be properly calculated for lines containing
1845	// a skipped region (without it the line is marked uncovered)
1846	const Counter ParentCount = getRegion().getCounter();
1847
1848	extendRegion(S);
1849
1850	if (S->isNegatedConsteval()) {
1851	// ignore 'if consteval'
1852	markSkipped(StartLoc: S->getIfLoc(), BeforeLoc: getStart(S: Then));
1853	propagateCounts(TopCount: ParentCount, S: Then);
1854
1855	if (Else) {
1856	// ignore 'else <else>'
1857	markSkipped(StartLoc: getEnd(S: Then), BeforeLoc: getEnd(S: Else));
1858	}
1859	} else {
1860	assert(S->isNonNegatedConsteval());
1861	// ignore 'if consteval <then> [else]'
1862	markSkipped(StartLoc: S->getIfLoc(), BeforeLoc: Else ? getStart(S: Else) : getEnd(S: Then));
1863
1864	if (Else)
1865	propagateCounts(TopCount: ParentCount, S: Else);
1866	}
1867	}
1868
1869	void coverIfConstexpr(const IfStmt *S) {
1870	assert(S->isConstexpr());
1871
1872	// evaluate constant condition...
1873	const bool isTrue =
1874	S->getCond()
1875	->EvaluateKnownConstInt(Ctx: CVM.getCodeGenModule().getContext())
1876	.getBoolValue();
1877
1878	extendRegion(S);
1879
1880	// I'm using 'propagateCounts' later as new region is better and allows me
1881	// to properly calculate line coverage in llvm-cov utility
1882	const Counter ParentCount = getRegion().getCounter();
1883
1884	// ignore 'if constexpr ('
1885	SourceLocation startOfSkipped = S->getIfLoc();
1886
1887	if (const auto *Init = S->getInit()) {
1888	const auto start = getStart(S: Init);
1889	const auto end = getEnd(S: Init);
1890
1891	// this check is to make sure typedef here which doesn't have valid source
1892	// location won't crash it
1893	if (start.isValid() && end.isValid()) {
1894	markSkipped(StartLoc: startOfSkipped, BeforeLoc: start);
1895	propagateCounts(TopCount: ParentCount, S: Init);
1896	startOfSkipped = getEnd(S: Init);
1897	}
1898	}
1899
1900	const auto *Then = S->getThen();
1901	const auto *Else = S->getElse();
1902
1903	if (isTrue) {
1904	// ignore '<condition>)'
1905	markSkipped(StartLoc: startOfSkipped, BeforeLoc: getStart(S: Then));
1906	propagateCounts(TopCount: ParentCount, S: Then);
1907
1908	if (Else)
1909	// ignore 'else <else>'
1910	markSkipped(StartLoc: getEnd(S: Then), BeforeLoc: getEnd(S: Else));
1911	} else {
1912	// ignore '<condition>) <then> [else]'
1913	markSkipped(StartLoc: startOfSkipped, BeforeLoc: Else ? getStart(S: Else) : getEnd(S: Then));
1914
1915	if (Else)
1916	propagateCounts(TopCount: ParentCount, S: Else);
1917	}
1918	}
1919
1920	void VisitIfStmt(const IfStmt *S) {
1921	// "if constexpr" and "if consteval" are not normal conditional statements,
1922	// their discarded statement should be skipped
1923	if (S->isConsteval())
1924	return coverIfConsteval(S);
1925	else if (S->isConstexpr())
1926	return coverIfConstexpr(S);
1927
1928	extendRegion(S);
1929	if (S->getInit())
1930	Visit(S->getInit());
1931
1932	// Extend into the condition before we propagate through it below - this is
1933	// needed to handle macros that generate the "if" but not the condition.
1934	extendRegion(S->getCond());
1935
1936	Counter ParentCount = getRegion().getCounter();
1937	Counter ThenCount = llvm::EnableSingleByteCoverage
1938	? getRegionCounter(S: S->getThen())
1939	: getRegionCounter(S);
1940
1941	// Emitting a counter for the condition makes it easier to interpret the
1942	// counter for the body when looking at the coverage.
1943	propagateCounts(ParentCount, S->getCond());
1944
1945	// The 'then' count applies to the area immediately after the condition.
1946	std::optional<SourceRange> Gap =
1947	findGapAreaBetween(AfterLoc: S->getRParenLoc(), BeforeLoc: getStart(S: S->getThen()));
1948	if (Gap)
1949	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: ThenCount);
1950
1951	extendRegion(S: S->getThen());
1952	Counter OutCount = propagateCounts(TopCount: ThenCount, S: S->getThen());
1953
1954	Counter ElseCount;
1955	if (!llvm::EnableSingleByteCoverage)
1956	ElseCount = subtractCounters(LHS: ParentCount, RHS: ThenCount);
1957	else if (S->getElse())
1958	ElseCount = getRegionCounter(S: S->getElse());
1959
1960	if (const Stmt *Else = S->getElse()) {
1961	bool ThenHasTerminateStmt = HasTerminateStmt;
1962	HasTerminateStmt = false;
1963	// The 'else' count applies to the area immediately after the 'then'.
1964	std::optional<SourceRange> Gap =
1965	findGapAreaBetween(AfterLoc: getEnd(S: S->getThen()), BeforeLoc: getStart(S: Else));
1966	if (Gap)
1967	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: ElseCount);
1968	extendRegion(S: Else);
1969
1970	Counter ElseOutCount = propagateCounts(TopCount: ElseCount, S: Else);
1971	if (!llvm::EnableSingleByteCoverage)
1972	OutCount = addCounters(LHS: OutCount, RHS: ElseOutCount);
1973
1974	if (ThenHasTerminateStmt)
1975	HasTerminateStmt = true;
1976	} else if (!llvm::EnableSingleByteCoverage)
1977	OutCount = addCounters(LHS: OutCount, RHS: ElseCount);
1978
1979	if (llvm::EnableSingleByteCoverage)
1980	OutCount = getRegionCounter(S);
1981
1982	if (OutCount != ParentCount) {
1983	pushRegion(Count: OutCount);
1984	GapRegionCounter = OutCount;
1985	}
1986
1987	if (!S->isConsteval() && !llvm::EnableSingleByteCoverage)
1988	// Create Branch Region around condition.
1989	createBranchRegion(C: S->getCond(), TrueCnt: ThenCount,
1990	FalseCnt: subtractCounters(LHS: ParentCount, RHS: ThenCount));
1991	}
1992
1993	void VisitCXXTryStmt(const CXXTryStmt *S) {
1994	extendRegion(S);
1995	// Handle macros that generate the "try" but not the rest.
1996	extendRegion(S->getTryBlock());
1997
1998	Counter ParentCount = getRegion().getCounter();
1999	propagateCounts(ParentCount, S->getTryBlock());
2000
2001	for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
2002	Visit(S->getHandler(i: I));
2003
2004	Counter ExitCount = getRegionCounter(S);
2005	pushRegion(Count: ExitCount);
2006	}
2007
2008	void VisitCXXCatchStmt(const CXXCatchStmt *S) {
2009	propagateCounts(TopCount: getRegionCounter(S), S: S->getHandlerBlock());
2010	}
2011
2012	void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
2013	extendRegion(E);
2014
2015	Counter ParentCount = getRegion().getCounter();
2016	Counter TrueCount = llvm::EnableSingleByteCoverage
2017	? getRegionCounter(E->getTrueExpr())
2018	: getRegionCounter(E);
2019	Counter OutCount;
2020
2021	if (const auto *BCO = dyn_cast<BinaryConditionalOperator>(Val: E)) {
2022	propagateCounts(ParentCount, BCO->getCommon());
2023	OutCount = TrueCount;
2024	} else {
2025	propagateCounts(ParentCount, E->getCond());
2026	// The 'then' count applies to the area immediately after the condition.
2027	auto Gap =
2028	findGapAreaBetween(AfterLoc: E->getQuestionLoc(), BeforeLoc: getStart(E->getTrueExpr()));
2029	if (Gap)
2030	fillGapAreaWithCount(StartLoc: Gap->getBegin(), EndLoc: Gap->getEnd(), Count: TrueCount);
2031
2032	extendRegion(E->getTrueExpr());
2033	OutCount = propagateCounts(TrueCount, E->getTrueExpr());
2034	}
2035
2036	extendRegion(E->getFalseExpr());
2037	Counter FalseCount = llvm::EnableSingleByteCoverage
2038	? getRegionCounter(E->getFalseExpr())
2039	: subtractCounters(LHS: ParentCount, RHS: TrueCount);
2040
2041	Counter FalseOutCount = propagateCounts(FalseCount, E->getFalseExpr());
2042	if (llvm::EnableSingleByteCoverage)
2043	OutCount = getRegionCounter(E);
2044	else
2045	OutCount = addCounters(LHS: OutCount, RHS: FalseOutCount);
2046
2047	if (OutCount != ParentCount) {
2048	pushRegion(Count: OutCount);
2049	GapRegionCounter = OutCount;
2050	}
2051
2052	// Create Branch Region around condition.
2053	if (!llvm::EnableSingleByteCoverage)
2054	createBranchRegion(C: E->getCond(), TrueCnt: TrueCount,
2055	FalseCnt: subtractCounters(LHS: ParentCount, RHS: TrueCount));
2056	}
2057
2058	void createDecision(const BinaryOperator *E) {
2059	unsigned NumConds = MCDCBuilder.getTotalConditionsAndReset(E);
2060	if (NumConds == 0)
2061	return;
2062
2063	auto DecisionParams = mcdc::DecisionParameters{
2064	MCDCState.DecisionByStmt[E].BitmapIdx,
2065	NumConds,
2066	};
2067
2068	// Create MCDC Decision Region.
2069	createDecisionRegion(C: E, DecisionParams: DecisionParams);
2070	}
2071
2072	void VisitBinLAnd(const BinaryOperator *E) {
2073	bool IsRootNode = MCDCBuilder.isIdle();
2074
2075	// Keep track of Binary Operator and assign MCDC condition IDs.
2076	MCDCBuilder.pushAndAssignIDs(E);
2077
2078	extendRegion(E->getLHS());
2079	propagateCounts(getRegion().getCounter(), E->getLHS());
2080	handleFileExit(NewLoc: getEnd(E->getLHS()));
2081
2082	// Track LHS True/False Decision.
2083	const auto DecisionLHS = MCDCBuilder.pop();
2084
2085	// Counter tracks the right hand side of a logical and operator.
2086	extendRegion(E->getRHS());
2087	propagateCounts(getRegionCounter(E), E->getRHS());
2088
2089	// Track RHS True/False Decision.
2090	const auto DecisionRHS = MCDCBuilder.back();
2091
2092	// Extract the RHS's Execution Counter.
2093	Counter RHSExecCnt = getRegionCounter(E);
2094
2095	// Extract the RHS's "True" Instance Counter.
2096	Counter RHSTrueCnt = getRegionCounter(E->getRHS());
2097
2098	// Extract the Parent Region Counter.
2099	Counter ParentCnt = getRegion().getCounter();
2100
2101	// Create Branch Region around LHS condition.
2102	if (!llvm::EnableSingleByteCoverage)
2103	createBranchRegion(C: E->getLHS(), TrueCnt: RHSExecCnt,
2104	FalseCnt: subtractCounters(LHS: ParentCnt, RHS: RHSExecCnt), Conds: DecisionLHS);
2105
2106	// Create Branch Region around RHS condition.
2107	if (!llvm::EnableSingleByteCoverage)
2108	createBranchRegion(C: E->getRHS(), TrueCnt: RHSTrueCnt,
2109	FalseCnt: subtractCounters(LHS: RHSExecCnt, RHS: RHSTrueCnt), Conds: DecisionRHS);
2110
2111	// Create MCDC Decision Region if at top-level (root).
2112	if (IsRootNode)
2113	createDecision(E);
2114	}
2115
2116	// Determine whether the right side of OR operation need to be visited.
2117	bool shouldVisitRHS(const Expr *LHS) {
2118	bool LHSIsTrue = false;
2119	bool LHSIsConst = false;
2120	if (!LHS->isValueDependent())
2121	LHSIsConst = LHS->EvaluateAsBooleanCondition(
2122	Result&: LHSIsTrue, Ctx: CVM.getCodeGenModule().getContext());
2123	return !LHSIsConst || (LHSIsConst && !LHSIsTrue);
2124	}
2125
2126	void VisitBinLOr(const BinaryOperator *E) {
2127	bool IsRootNode = MCDCBuilder.isIdle();
2128
2129	// Keep track of Binary Operator and assign MCDC condition IDs.
2130	MCDCBuilder.pushAndAssignIDs(E);
2131
2132	extendRegion(E->getLHS());
2133	Counter OutCount = propagateCounts(getRegion().getCounter(), E->getLHS());
2134	handleFileExit(NewLoc: getEnd(E->getLHS()));
2135
2136	// Track LHS True/False Decision.
2137	const auto DecisionLHS = MCDCBuilder.pop();
2138
2139	// Counter tracks the right hand side of a logical or operator.
2140	extendRegion(E->getRHS());
2141	propagateCounts(getRegionCounter(E), E->getRHS());
2142
2143	// Track RHS True/False Decision.
2144	const auto DecisionRHS = MCDCBuilder.back();
2145
2146	// Extract the RHS's Execution Counter.
2147	Counter RHSExecCnt = getRegionCounter(E);
2148
2149	// Extract the RHS's "False" Instance Counter.
2150	Counter RHSFalseCnt = getRegionCounter(E->getRHS());
2151
2152	if (!shouldVisitRHS(LHS: E->getLHS())) {
2153	GapRegionCounter = OutCount;
2154	}
2155
2156	// Extract the Parent Region Counter.
2157	Counter ParentCnt = getRegion().getCounter();
2158
2159	// Create Branch Region around LHS condition.
2160	if (!llvm::EnableSingleByteCoverage)
2161	createBranchRegion(C: E->getLHS(), TrueCnt: subtractCounters(LHS: ParentCnt, RHS: RHSExecCnt),
2162	FalseCnt: RHSExecCnt, Conds: DecisionLHS);
2163
2164	// Create Branch Region around RHS condition.
2165	if (!llvm::EnableSingleByteCoverage)
2166	createBranchRegion(C: E->getRHS(), TrueCnt: subtractCounters(LHS: RHSExecCnt, RHS: RHSFalseCnt),
2167	FalseCnt: RHSFalseCnt, Conds: DecisionRHS);
2168
2169	// Create MCDC Decision Region if at top-level (root).
2170	if (IsRootNode)
2171	createDecision(E);
2172	}
2173
2174	void VisitLambdaExpr(const LambdaExpr *LE) {
2175	// Lambdas are treated as their own functions for now, so we shouldn't
2176	// propagate counts into them.
2177	}
2178
2179	void VisitPseudoObjectExpr(const PseudoObjectExpr *POE) {
2180	// Just visit syntatic expression as this is what users actually write.
2181	VisitStmt(POE->getSyntacticForm());
2182	}
2183
2184	void VisitOpaqueValueExpr(const OpaqueValueExpr* OVE) {
2185	Visit(OVE->getSourceExpr());
2186	}
2187	};
2188
2189	} // end anonymous namespace
2190
2191	static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
2192	ArrayRef<CounterExpression> Expressions,
2193	ArrayRef<CounterMappingRegion> Regions) {
2194	OS << FunctionName << ":\n";
2195	CounterMappingContext Ctx(Expressions);
2196	for (const auto &R : Regions) {
2197	OS.indent(NumSpaces: 2);
2198	switch (R.Kind) {
2199	case CounterMappingRegion::CodeRegion:
2200	break;
2201	case CounterMappingRegion::ExpansionRegion:
2202	OS << "Expansion,";
2203	break;
2204	case CounterMappingRegion::SkippedRegion:
2205	OS << "Skipped,";
2206	break;
2207	case CounterMappingRegion::GapRegion:
2208	OS << "Gap,";
2209	break;
2210	case CounterMappingRegion::BranchRegion:
2211	case CounterMappingRegion::MCDCBranchRegion:
2212	OS << "Branch,";
2213	break;
2214	case CounterMappingRegion::MCDCDecisionRegion:
2215	OS << "Decision,";
2216	break;
2217	}
2218
2219	OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
2220	<< " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
2221
2222	if (const auto *DecisionParams =
2223	std::get_if<mcdc::DecisionParameters>(ptr: &R.MCDCParams)) {
2224	OS << "M:" << DecisionParams->BitmapIdx;
2225	OS << ", C:" << DecisionParams->NumConditions;
2226	} else {
2227	Ctx.dump(C: R.Count, OS);
2228
2229	if (R.Kind == CounterMappingRegion::BranchRegion ||
2230	R.Kind == CounterMappingRegion::MCDCBranchRegion) {
2231	OS << ", ";
2232	Ctx.dump(C: R.FalseCount, OS);
2233	}
2234	}
2235
2236	if (const auto *BranchParams =
2237	std::get_if<mcdc::BranchParameters>(ptr: &R.MCDCParams)) {
2238	OS << " [" << BranchParams->ID + 1 << ","
2239	<< BranchParams->Conds[true] + 1;
2240	OS << "," << BranchParams->Conds[false] + 1 << "] ";
2241	}
2242
2243	if (R.Kind == CounterMappingRegion::ExpansionRegion)
2244	OS << " (Expanded file = " << R.ExpandedFileID << ")";
2245	OS << "\n";
2246	}
2247	}
2248
2249	CoverageMappingModuleGen::CoverageMappingModuleGen(
2250	CodeGenModule &CGM, CoverageSourceInfo &SourceInfo)
2251	: CGM(CGM), SourceInfo(SourceInfo) {}
2252
2253	std::string CoverageMappingModuleGen::getCurrentDirname() {
2254	if (!CGM.getCodeGenOpts().CoverageCompilationDir.empty())
2255	return CGM.getCodeGenOpts().CoverageCompilationDir;
2256
2257	SmallString<256> CWD;
2258	llvm::sys::fs::current_path(result&: CWD);
2259	return CWD.str().str();
2260	}
2261
2262	std::string CoverageMappingModuleGen::normalizeFilename(StringRef Filename) {
2263	llvm::SmallString<256> Path(Filename);
2264	llvm::sys::path::remove_dots(path&: Path, /*remove_dot_dot=*/true);
2265
2266	/// Traverse coverage prefix map in reverse order because prefix replacements
2267	/// are applied in reverse order starting from the last one when multiple
2268	/// prefix replacement options are provided.
2269	for (const auto &[From, To] :
2270	llvm::reverse(C: CGM.getCodeGenOpts().CoveragePrefixMap)) {
2271	if (llvm::sys::path::replace_path_prefix(Path, OldPrefix: From, NewPrefix: To))
2272	break;
2273	}
2274	return Path.str().str();
2275	}
2276
2277	static std::string getInstrProfSection(const CodeGenModule &CGM,
2278	llvm::InstrProfSectKind SK) {
2279	return llvm::getInstrProfSectionName(
2280	IPSK: SK, OF: CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
2281	}
2282
2283	void CoverageMappingModuleGen::emitFunctionMappingRecord(
2284	const FunctionInfo &Info, uint64_t FilenamesRef) {
2285	llvm::LLVMContext &Ctx = CGM.getLLVMContext();
2286
2287	// Assign a name to the function record. This is used to merge duplicates.
2288	std::string FuncRecordName = "__covrec_" + llvm::utohexstr(X: Info.NameHash);
2289
2290	// A dummy description for a function included-but-not-used in a TU can be
2291	// replaced by full description provided by a different TU. The two kinds of
2292	// descriptions play distinct roles: therefore, assign them different names
2293	// to prevent `linkonce_odr` merging.
2294	if (Info.IsUsed)
2295	FuncRecordName += "u";
2296
2297	// Create the function record type.
2298	const uint64_t NameHash = Info.NameHash;
2299	const uint64_t FuncHash = Info.FuncHash;
2300	const std::string &CoverageMapping = Info.CoverageMapping;
2301	#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
2302	llvm::Type *FunctionRecordTypes[] = {
2303	#include "llvm/ProfileData/InstrProfData.inc"
2304	};
2305	auto *FunctionRecordTy =
2306	llvm::StructType::get(Context&: Ctx, Elements: ArrayRef(FunctionRecordTypes),
2307	/*isPacked=*/true);
2308
2309	// Create the function record constant.
2310	#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
2311	llvm::Constant *FunctionRecordVals[] = {
2312	#include "llvm/ProfileData/InstrProfData.inc"
2313	};
2314	auto *FuncRecordConstant =
2315	llvm::ConstantStruct::get(T: FunctionRecordTy, V: ArrayRef(FunctionRecordVals));
2316
2317	// Create the function record global.
2318	auto *FuncRecord = new llvm::GlobalVariable(
2319	CGM.getModule(), FunctionRecordTy, /*isConstant=*/true,
2320	llvm::GlobalValue::LinkOnceODRLinkage, FuncRecordConstant,
2321	FuncRecordName);
2322	FuncRecord->setVisibility(llvm::GlobalValue::HiddenVisibility);
2323	FuncRecord->setSection(getInstrProfSection(CGM, SK: llvm::IPSK_covfun));
2324	FuncRecord->setAlignment(llvm::Align(8));
2325	if (CGM.supportsCOMDAT())
2326	FuncRecord->setComdat(CGM.getModule().getOrInsertComdat(Name: FuncRecordName));
2327
2328	// Make sure the data doesn't get deleted.
2329	CGM.addUsedGlobal(GV: FuncRecord);
2330	}
2331
2332	void CoverageMappingModuleGen::addFunctionMappingRecord(
2333	llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
2334	const std::string &CoverageMapping, bool IsUsed) {
2335	const uint64_t NameHash = llvm::IndexedInstrProf::ComputeHash(K: NameValue);
2336	FunctionRecords.push_back(x: {.NameHash: NameHash, .FuncHash: FuncHash, .CoverageMapping: CoverageMapping, .IsUsed: IsUsed});
2337
2338	if (!IsUsed)
2339	FunctionNames.push_back(x: NamePtr);
2340
2341	if (CGM.getCodeGenOpts().DumpCoverageMapping) {
2342	// Dump the coverage mapping data for this function by decoding the
2343	// encoded data. This allows us to dump the mapping regions which were
2344	// also processed by the CoverageMappingWriter which performs
2345	// additional minimization operations such as reducing the number of
2346	// expressions.
2347	llvm::SmallVector<std::string, 16> FilenameStrs;
2348	std::vector<StringRef> Filenames;
2349	std::vector<CounterExpression> Expressions;
2350	std::vector<CounterMappingRegion> Regions;
2351	FilenameStrs.resize(N: FileEntries.size() + 1);
2352	FilenameStrs[0] = normalizeFilename(Filename: getCurrentDirname());
2353	for (const auto &Entry : FileEntries) {
2354	auto I = Entry.second;
2355	FilenameStrs[I] = normalizeFilename(Filename: Entry.first.getName());
2356	}
2357	ArrayRef<std::string> FilenameRefs = llvm::ArrayRef(FilenameStrs);
2358	RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
2359	Expressions, Regions);
2360	if (Reader.read())
2361	return;
2362	dump(OS&: llvm::outs(), FunctionName: NameValue, Expressions, Regions);
2363	}
2364	}
2365
2366	void CoverageMappingModuleGen::emit() {
2367	if (FunctionRecords.empty())
2368	return;
2369	llvm::LLVMContext &Ctx = CGM.getLLVMContext();
2370	auto *Int32Ty = llvm::Type::getInt32Ty(C&: Ctx);
2371
2372	// Create the filenames and merge them with coverage mappings
2373	llvm::SmallVector<std::string, 16> FilenameStrs;
2374	FilenameStrs.resize(N: FileEntries.size() + 1);
2375	// The first filename is the current working directory.
2376	FilenameStrs[0] = normalizeFilename(Filename: getCurrentDirname());
2377	for (const auto &Entry : FileEntries) {
2378	auto I = Entry.second;
2379	FilenameStrs[I] = normalizeFilename(Filename: Entry.first.getName());
2380	}
2381
2382	std::string Filenames;
2383	{
2384	llvm::raw_string_ostream OS(Filenames);
2385	CoverageFilenamesSectionWriter(FilenameStrs).write(OS);
2386	}
2387	auto *FilenamesVal =
2388	llvm::ConstantDataArray::getString(Context&: Ctx, Initializer: Filenames, AddNull: false);
2389	const int64_t FilenamesRef = llvm::IndexedInstrProf::ComputeHash(K: Filenames);
2390
2391	// Emit the function records.
2392	for (const FunctionInfo &Info : FunctionRecords)
2393	emitFunctionMappingRecord(Info, FilenamesRef);
2394
2395	const unsigned NRecords = 0;
2396	const size_t FilenamesSize = Filenames.size();
2397	const unsigned CoverageMappingSize = 0;
2398	llvm::Type *CovDataHeaderTypes[] = {
2399	#define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
2400	#include "llvm/ProfileData/InstrProfData.inc"
2401	};
2402	auto CovDataHeaderTy =
2403	llvm::StructType::get(Context&: Ctx, Elements: ArrayRef(CovDataHeaderTypes));
2404	llvm::Constant *CovDataHeaderVals[] = {
2405	#define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
2406	#include "llvm/ProfileData/InstrProfData.inc"
2407	};
2408	auto CovDataHeaderVal =
2409	llvm::ConstantStruct::get(T: CovDataHeaderTy, V: ArrayRef(CovDataHeaderVals));
2410
2411	// Create the coverage data record
2412	llvm::Type *CovDataTypes[] = {CovDataHeaderTy, FilenamesVal->getType()};
2413	auto CovDataTy = llvm::StructType::get(Context&: Ctx, Elements: ArrayRef(CovDataTypes));
2414	llvm::Constant *TUDataVals[] = {CovDataHeaderVal, FilenamesVal};
2415	auto CovDataVal = llvm::ConstantStruct::get(T: CovDataTy, V: ArrayRef(TUDataVals));
2416	auto CovData = new llvm::GlobalVariable(
2417	CGM.getModule(), CovDataTy, true, llvm::GlobalValue::PrivateLinkage,
2418	CovDataVal, llvm::getCoverageMappingVarName());
2419
2420	CovData->setSection(getInstrProfSection(CGM, SK: llvm::IPSK_covmap));
2421	CovData->setAlignment(llvm::Align(8));
2422
2423	// Make sure the data doesn't get deleted.
2424	CGM.addUsedGlobal(GV: CovData);
2425	// Create the deferred function records array
2426	if (!FunctionNames.empty()) {
2427	auto NamesArrTy = llvm::ArrayType::get(ElementType: llvm::PointerType::getUnqual(C&: Ctx),
2428	NumElements: FunctionNames.size());
2429	auto NamesArrVal = llvm::ConstantArray::get(T: NamesArrTy, V: FunctionNames);
2430	// This variable will *NOT* be emitted to the object file. It is used
2431	// to pass the list of names referenced to codegen.
2432	new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
2433	llvm::GlobalValue::InternalLinkage, NamesArrVal,
2434	llvm::getCoverageUnusedNamesVarName());
2435	}
2436	}
2437
2438	unsigned CoverageMappingModuleGen::getFileID(FileEntryRef File) {
2439	auto It = FileEntries.find(Val: File);
2440	if (It != FileEntries.end())
2441	return It->second;
2442	unsigned FileID = FileEntries.size() + 1;
2443	FileEntries.insert(KV: std::make_pair(x&: File, y&: FileID));
2444	return FileID;
2445	}
2446
2447	void CoverageMappingGen::emitCounterMapping(const Decl *D,
2448	llvm::raw_ostream &OS) {
2449	assert(CounterMap && MCDCState);
2450	CounterCoverageMappingBuilder Walker(CVM, *CounterMap, *MCDCState, SM,
2451	LangOpts);
2452	Walker.VisitDecl(D);
2453	Walker.write(OS);
2454	}
2455
2456	void CoverageMappingGen::emitEmptyMapping(const Decl *D,
2457	llvm::raw_ostream &OS) {
2458	EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
2459	Walker.VisitDecl(D);
2460	Walker.write(OS);
2461	}
2462