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