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