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