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