diff options
Diffstat (limited to 'contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp')
| -rw-r--r-- | contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp | 1475 |
1 files changed, 1151 insertions, 324 deletions
diff --git a/contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp b/contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp index 5c25c204cc0b..67a9caf8b4ec 100644 --- a/contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp +++ b/contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp @@ -17,7 +17,7 @@ #include "clang/Basic/FileManager.h" #include "clang/Frontend/FrontendDiagnostic.h" #include "clang/Lex/Lexer.h" -#include "llvm/ADT/Optional.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ProfileData/Coverage/CoverageMapping.h" @@ -26,17 +26,33 @@ #include "llvm/ProfileData/InstrProfReader.h" #include "llvm/Support/FileSystem.h" #include "llvm/Support/Path.h" +#include <optional> // This selects the coverage mapping format defined when `InstrProfData.inc` // is textually included. #define COVMAP_V3 +namespace llvm { +cl::opt<bool> + EnableSingleByteCoverage("enable-single-byte-coverage", + llvm::cl::ZeroOrMore, + llvm::cl::desc("Enable single byte coverage"), + llvm::cl::Hidden, llvm::cl::init(false)); +} // namespace llvm + static llvm::cl::opt<bool> EmptyLineCommentCoverage( "emptyline-comment-coverage", llvm::cl::desc("Emit emptylines and comment lines as skipped regions (only " "disable it on test)"), llvm::cl::init(true), llvm::cl::Hidden); +namespace llvm::coverage { +cl::opt<bool> SystemHeadersCoverage( + "system-headers-coverage", + cl::desc("Enable collecting coverage from system headers"), cl::init(false), + cl::Hidden); +} + using namespace clang; using namespace CodeGen; using namespace llvm::coverage; @@ -60,26 +76,27 @@ CoverageMappingModuleGen::setUpCoverageCallbacks(Preprocessor &PP) { return CoverageInfo; } -void CoverageSourceInfo::AddSkippedRange(SourceRange Range) { +void CoverageSourceInfo::AddSkippedRange(SourceRange Range, + SkippedRange::Kind RangeKind) { if (EmptyLineCommentCoverage && !SkippedRanges.empty() && PrevTokLoc == SkippedRanges.back().PrevTokLoc && SourceMgr.isWrittenInSameFile(SkippedRanges.back().Range.getEnd(), Range.getBegin())) SkippedRanges.back().Range.setEnd(Range.getEnd()); else - SkippedRanges.push_back({Range, PrevTokLoc}); + SkippedRanges.push_back({Range, RangeKind, PrevTokLoc}); } void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) { - AddSkippedRange(Range); + AddSkippedRange(Range, SkippedRange::PPIfElse); } void CoverageSourceInfo::HandleEmptyline(SourceRange Range) { - AddSkippedRange(Range); + AddSkippedRange(Range, SkippedRange::EmptyLine); } bool CoverageSourceInfo::HandleComment(Preprocessor &PP, SourceRange Range) { - AddSkippedRange(Range); + AddSkippedRange(Range, SkippedRange::Comment); return false; } @@ -89,41 +106,52 @@ void CoverageSourceInfo::updateNextTokLoc(SourceLocation Loc) { } namespace { - /// A region of source code that can be mapped to a counter. class SourceMappingRegion { /// Primary Counter that is also used for Branch Regions for "True" branches. Counter Count; /// Secondary Counter used for Branch Regions for "False" branches. - Optional<Counter> FalseCount; + std::optional<Counter> FalseCount; + + /// Parameters used for Modified Condition/Decision Coverage + mcdc::Parameters MCDCParams; /// The region's starting location. - Optional<SourceLocation> LocStart; + std::optional<SourceLocation> LocStart; /// The region's ending location. - Optional<SourceLocation> LocEnd; - - /// Whether this region should be emitted after its parent is emitted. - bool DeferRegion; + std::optional<SourceLocation> LocEnd; /// Whether this region is a gap region. The count from a gap region is set /// as the line execution count if there are no other regions on the line. bool GapRegion; + /// Whetever this region is skipped ('if constexpr' or 'if consteval' untaken + /// branch, or anything skipped but not empty line / comments) + bool SkippedRegion; + public: - SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart, - Optional<SourceLocation> LocEnd, bool DeferRegion = false, + SourceMappingRegion(Counter Count, std::optional<SourceLocation> LocStart, + std::optional<SourceLocation> LocEnd, bool GapRegion = false) - : Count(Count), LocStart(LocStart), LocEnd(LocEnd), - DeferRegion(DeferRegion), GapRegion(GapRegion) {} + : Count(Count), LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion), + SkippedRegion(false) {} - SourceMappingRegion(Counter Count, Optional<Counter> FalseCount, - Optional<SourceLocation> LocStart, - Optional<SourceLocation> LocEnd, bool DeferRegion = false, + SourceMappingRegion(Counter Count, std::optional<Counter> FalseCount, + mcdc::Parameters MCDCParams, + std::optional<SourceLocation> LocStart, + std::optional<SourceLocation> LocEnd, bool GapRegion = false) - : Count(Count), FalseCount(FalseCount), LocStart(LocStart), - LocEnd(LocEnd), DeferRegion(DeferRegion), GapRegion(GapRegion) {} + : Count(Count), FalseCount(FalseCount), MCDCParams(MCDCParams), + LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion), + SkippedRegion(false) {} + + SourceMappingRegion(mcdc::Parameters MCDCParams, + std::optional<SourceLocation> LocStart, + std::optional<SourceLocation> LocEnd) + : MCDCParams(MCDCParams), LocStart(LocStart), LocEnd(LocEnd), + GapRegion(false), SkippedRegion(false) {} const Counter &getCounter() const { return Count; } @@ -134,7 +162,7 @@ public: void setCounter(Counter C) { Count = C; } - bool hasStartLoc() const { return LocStart.hasValue(); } + bool hasStartLoc() const { return LocStart.has_value(); } void setStartLoc(SourceLocation Loc) { LocStart = Loc; } @@ -143,7 +171,7 @@ public: return *LocStart; } - bool hasEndLoc() const { return LocEnd.hasValue(); } + bool hasEndLoc() const { return LocEnd.has_value(); } void setEndLoc(SourceLocation Loc) { assert(Loc.isValid() && "Setting an invalid end location"); @@ -155,15 +183,35 @@ public: return *LocEnd; } - bool isDeferred() const { return DeferRegion; } - - void setDeferred(bool Deferred) { DeferRegion = Deferred; } - bool isGap() const { return GapRegion; } void setGap(bool Gap) { GapRegion = Gap; } - bool isBranch() const { return FalseCount.hasValue(); } + bool isSkipped() const { return SkippedRegion; } + + void setSkipped(bool Skipped) { SkippedRegion = Skipped; } + + bool isBranch() const { return FalseCount.has_value(); } + + bool isMCDCBranch() const { + return std::holds_alternative<mcdc::BranchParameters>(MCDCParams); + } + + const auto &getMCDCBranchParams() const { + return mcdc::getParams<const mcdc::BranchParameters>(MCDCParams); + } + + bool isMCDCDecision() const { + return std::holds_alternative<mcdc::DecisionParameters>(MCDCParams); + } + + const auto &getMCDCDecisionParams() const { + return mcdc::getParams<const mcdc::DecisionParameters>(MCDCParams); + } + + const mcdc::Parameters &getMCDCParams() const { return MCDCParams; } + + void resetMCDCParams() { MCDCParams = mcdc::Parameters(); } }; /// Spelling locations for the start and end of a source region. @@ -254,10 +302,36 @@ public: return SM.getLocForEndOfFile(SM.getFileID(Loc)); } - /// Find out where the current file is included or macro is expanded. - SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) { - return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getBegin() - : SM.getIncludeLoc(SM.getFileID(Loc)); + /// Find out where a macro is expanded. If the immediate result is a + /// <scratch space>, keep looking until the result isn't. Return a pair of + /// \c SourceLocation. The first object is always the begin sloc of found + /// result. The second should be checked by the caller: if it has value, it's + /// the end sloc of the found result. Otherwise the while loop didn't get + /// executed, which means the location wasn't changed and the caller has to + /// learn the end sloc from somewhere else. + std::pair<SourceLocation, std::optional<SourceLocation>> + getNonScratchExpansionLoc(SourceLocation Loc) { + std::optional<SourceLocation> EndLoc = std::nullopt; + while (Loc.isMacroID() && + SM.isWrittenInScratchSpace(SM.getSpellingLoc(Loc))) { + auto ExpansionRange = SM.getImmediateExpansionRange(Loc); + Loc = ExpansionRange.getBegin(); + EndLoc = ExpansionRange.getEnd(); + } + return std::make_pair(Loc, EndLoc); + } + + /// Find out where the current file is included or macro is expanded. If + /// \c AcceptScratch is set to false, keep looking for expansions until the + /// found sloc is not a <scratch space>. + SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc, + bool AcceptScratch = true) { + if (!Loc.isMacroID()) + return SM.getIncludeLoc(SM.getFileID(Loc)); + Loc = SM.getImmediateExpansionRange(Loc).getBegin(); + if (AcceptScratch) + return Loc; + return getNonScratchExpansionLoc(Loc).first; } /// Return true if \c Loc is a location in a built-in macro. @@ -301,15 +375,35 @@ public: llvm::SmallSet<FileID, 8> Visited; SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs; - for (const auto &Region : SourceRegions) { + for (auto &Region : SourceRegions) { SourceLocation Loc = Region.getBeginLoc(); + + // Replace Region with its definition if it is in <scratch space>. + auto NonScratchExpansionLoc = getNonScratchExpansionLoc(Loc); + auto EndLoc = NonScratchExpansionLoc.second; + if (EndLoc.has_value()) { + Loc = NonScratchExpansionLoc.first; + Region.setStartLoc(Loc); + Region.setEndLoc(EndLoc.value()); + } + + // Replace Loc with FileLoc if it is expanded with system headers. + if (!SystemHeadersCoverage && SM.isInSystemMacro(Loc)) { + auto BeginLoc = SM.getSpellingLoc(Loc); + auto EndLoc = SM.getSpellingLoc(Region.getEndLoc()); + if (SM.isWrittenInSameFile(BeginLoc, EndLoc)) { + Loc = SM.getFileLoc(Loc); + Region.setStartLoc(Loc); + Region.setEndLoc(SM.getFileLoc(Region.getEndLoc())); + } + } + FileID File = SM.getFileID(Loc); if (!Visited.insert(File).second) continue; - // Do not map FileID's associated with system headers. - if (SM.isInSystemHeader(SM.getSpellingLoc(Loc))) - continue; + assert(SystemHeadersCoverage || + !SM.isInSystemHeader(SM.getSpellingLoc(Loc))); unsigned Depth = 0; for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc); @@ -322,33 +416,35 @@ public: for (const auto &FL : FileLocs) { SourceLocation Loc = FL.first; FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first; - auto Entry = SM.getFileEntryForID(SpellingFile); + auto Entry = SM.getFileEntryRefForID(SpellingFile); if (!Entry) continue; FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc); - Mapping.push_back(CVM.getFileID(Entry)); + Mapping.push_back(CVM.getFileID(*Entry)); } } /// Get the coverage mapping file ID for \c Loc. /// - /// If such file id doesn't exist, return None. - Optional<unsigned> getCoverageFileID(SourceLocation Loc) { + /// If such file id doesn't exist, return std::nullopt. + std::optional<unsigned> getCoverageFileID(SourceLocation Loc) { auto Mapping = FileIDMapping.find(SM.getFileID(Loc)); if (Mapping != FileIDMapping.end()) return Mapping->second.first; - return None; + return std::nullopt; } /// This shrinks the skipped range if it spans a line that contains a /// non-comment token. If shrinking the skipped range would make it empty, - /// this returns None. - Optional<SpellingRegion> adjustSkippedRange(SourceManager &SM, - SourceLocation LocStart, - SourceLocation LocEnd, - SourceLocation PrevTokLoc, - SourceLocation NextTokLoc) { + /// this returns std::nullopt. + /// Note this function can potentially be expensive because + /// getSpellingLineNumber uses getLineNumber, which is expensive. + std::optional<SpellingRegion> adjustSkippedRange(SourceManager &SM, + SourceLocation LocStart, + SourceLocation LocEnd, + SourceLocation PrevTokLoc, + SourceLocation NextTokLoc) { SpellingRegion SR{SM, LocStart, LocEnd}; SR.ColumnStart = 1; if (PrevTokLoc.isValid() && SM.isWrittenInSameFile(LocStart, PrevTokLoc) && @@ -361,7 +457,7 @@ public: } if (SR.isInSourceOrder()) return SR; - return None; + return std::nullopt; } /// Gather all the regions that were skipped by the preprocessor @@ -391,9 +487,14 @@ public: auto CovFileID = getCoverageFileID(LocStart); if (!CovFileID) continue; - Optional<SpellingRegion> SR = - adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc, I.NextTokLoc); - if (!SR.hasValue()) + std::optional<SpellingRegion> SR; + if (I.isComment()) + SR = adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc, + I.NextTokLoc); + else if (I.isPPIfElse() || I.isEmptyLine()) + SR = {SM, LocStart, LocEnd}; + + if (!SR) continue; auto Region = CounterMappingRegion::makeSkipped( *CovFileID, SR->LineStart, SR->ColumnStart, SR->LineEnd, @@ -415,14 +516,22 @@ public: SourceLocation LocStart = Region.getBeginLoc(); assert(SM.getFileID(LocStart).isValid() && "region in invalid file"); - // Ignore regions from system headers. - if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart))) + // Ignore regions from system headers unless collecting coverage from + // system headers is explicitly enabled. + if (!SystemHeadersCoverage && + SM.isInSystemHeader(SM.getSpellingLoc(LocStart))) { + assert(!Region.isMCDCBranch() && !Region.isMCDCDecision() && + "Don't suppress the condition in system headers"); continue; + } auto CovFileID = getCoverageFileID(LocStart); // Ignore regions that don't have a file, such as builtin macros. - if (!CovFileID) + if (!CovFileID) { + assert(!Region.isMCDCBranch() && !Region.isMCDCDecision() && + "Don't suppress the condition in non-file regions"); continue; + } SourceLocation LocEnd = Region.getEndLoc(); assert(SM.isWrittenInSameFile(LocStart, LocEnd) && @@ -432,8 +541,11 @@ public: // This not only suppresses redundant regions, but sometimes prevents // creating regions with wrong counters if, for example, a statement's // body ends at the end of a nested macro. - if (Filter.count(std::make_pair(LocStart, LocEnd))) + if (Filter.count(std::make_pair(LocStart, LocEnd))) { + assert(!Region.isMCDCBranch() && !Region.isMCDCDecision() && + "Don't suppress the condition"); continue; + } // Find the spelling locations for the mapping region. SpellingRegion SR{SM, LocStart, LocEnd}; @@ -443,10 +555,19 @@ public: MappingRegions.push_back(CounterMappingRegion::makeGapRegion( Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd)); + } else if (Region.isSkipped()) { + MappingRegions.push_back(CounterMappingRegion::makeSkipped( + *CovFileID, SR.LineStart, SR.ColumnStart, SR.LineEnd, + SR.ColumnEnd)); } else if (Region.isBranch()) { MappingRegions.push_back(CounterMappingRegion::makeBranchRegion( Region.getCounter(), Region.getFalseCounter(), *CovFileID, - SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd)); + SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd, + Region.getMCDCParams())); + } else if (Region.isMCDCDecision()) { + MappingRegions.push_back(CounterMappingRegion::makeDecisionRegion( + Region.getMCDCDecisionParams(), *CovFileID, SR.LineStart, + SR.ColumnStart, SR.LineEnd, SR.ColumnEnd)); } else { MappingRegions.push_back(CounterMappingRegion::makeRegion( Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart, @@ -460,7 +581,7 @@ public: SourceRegionFilter Filter; for (const auto &FM : FileIDMapping) { SourceLocation ExpandedLoc = FM.second.second; - SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc); + SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc, false); if (ParentLoc.isInvalid()) continue; @@ -528,11 +649,236 @@ struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder { if (MappingRegions.empty()) return; - CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions); + CoverageMappingWriter Writer(FileIDMapping, std::nullopt, MappingRegions); Writer.write(OS); } }; +/// A wrapper object for maintaining stacks to track the resursive AST visitor +/// walks for the purpose of assigning IDs to leaf-level conditions measured by +/// MC/DC. The object is created with a reference to the MCDCBitmapMap that was +/// created during the initial AST walk. The presence of a bitmap associated +/// with a boolean expression (top-level logical operator nest) indicates that +/// the boolean expression qualified for MC/DC. The resulting condition IDs +/// are preserved in a map reference that is also provided during object +/// creation. +struct MCDCCoverageBuilder { + + /// The AST walk recursively visits nested logical-AND or logical-OR binary + /// operator nodes and then visits their LHS and RHS children nodes. As this + /// happens, the algorithm will assign IDs to each operator's LHS and RHS side + /// as the walk moves deeper into the nest. At each level of the recursive + /// nest, the LHS and RHS may actually correspond to larger subtrees (not + /// leaf-conditions). If this is the case, when that node is visited, the ID + /// assigned to the subtree is re-assigned to its LHS, and a new ID is given + /// to its RHS. At the end of the walk, all leaf-level conditions will have a + /// unique ID -- keep in mind that the final set of IDs may not be in + /// numerical order from left to right. + /// + /// Example: "x = (A && B) || (C && D) || (D && F)" + /// + /// Visit Depth1: + /// (A && B) || (C && D) || (D && F) + /// ^-------LHS--------^ ^-RHS--^ + /// ID=1 ID=2 + /// + /// Visit LHS-Depth2: + /// (A && B) || (C && D) + /// ^-LHS--^ ^-RHS--^ + /// ID=1 ID=3 + /// + /// Visit LHS-Depth3: + /// (A && B) + /// LHS RHS + /// ID=1 ID=4 + /// + /// Visit RHS-Depth3: + /// (C && D) + /// LHS RHS + /// ID=3 ID=5 + /// + /// Visit RHS-Depth2: (D && F) + /// LHS RHS + /// ID=2 ID=6 + /// + /// Visit Depth1: + /// (A && B) || (C && D) || (D && F) + /// ID=1 ID=4 ID=3 ID=5 ID=2 ID=6 + /// + /// A node ID of '0' always means MC/DC isn't being tracked. + /// + /// As the AST walk proceeds recursively, the algorithm will also use a stack + /// to track the IDs of logical-AND and logical-OR operations on the RHS so + /// that it can be determined which nodes are executed next, depending on how + /// a LHS or RHS of a logical-AND or logical-OR is evaluated. This + /// information relies on the assigned IDs and are embedded within the + /// coverage region IDs of each branch region associated with a leaf-level + /// condition. This information helps the visualization tool reconstruct all + /// possible test vectors for the purposes of MC/DC analysis. If a "next" node + /// ID is '0', it means it's the end of the test vector. The following rules + /// are used: + /// + /// For logical-AND ("LHS && RHS"): + /// - If LHS is TRUE, execution goes to the RHS node. + /// - If LHS is FALSE, execution goes to the LHS node of the next logical-OR. + /// If that does not exist, execution exits (ID == 0). + /// + /// - If RHS is TRUE, execution goes to LHS node of the next logical-AND. + /// If that does not exist, execution exits (ID == 0). + /// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR. + /// If that does not exist, execution exits (ID == 0). + /// + /// For logical-OR ("LHS || RHS"): + /// - If LHS is TRUE, execution goes to the LHS node of the next logical-AND. + /// If that does not exist, execution exits (ID == 0). + /// - If LHS is FALSE, execution goes to the RHS node. + /// + /// - If RHS is TRUE, execution goes to LHS node of the next logical-AND. + /// If that does not exist, execution exits (ID == 0). + /// - If RHS is FALSE, execution goes to the LHS node of the next logical-OR. + /// If that does not exist, execution exits (ID == 0). + /// + /// Finally, the condition IDs are also used when instrumenting the code to + /// indicate a unique offset into a temporary bitmap that represents the true + /// or false evaluation of that particular condition. + /// + /// NOTE regarding the use of CodeGenFunction::stripCond(). Even though, for + /// simplicity, parentheses and unary logical-NOT operators are considered + /// part of their underlying condition for both MC/DC and branch coverage, the + /// condition IDs themselves are assigned and tracked using the underlying + /// condition itself. This is done solely for consistency since parentheses + /// and logical-NOTs are ignored when checking whether the condition is + /// actually an instrumentable condition. This can also make debugging a bit + /// easier. + +private: + CodeGenModule &CGM; + + llvm::SmallVector<mcdc::ConditionIDs> DecisionStack; + MCDC::State &MCDCState; + const Stmt *DecisionStmt = nullptr; + mcdc::ConditionID NextID = 0; + bool NotMapped = false; + + /// Represent a sentinel value as a pair of final decisions for the bottom + // of DecisionStack. + static constexpr mcdc::ConditionIDs DecisionStackSentinel{-1, -1}; + + /// Is this a logical-AND operation? + bool isLAnd(const BinaryOperator *E) const { + return E->getOpcode() == BO_LAnd; + } + +public: + MCDCCoverageBuilder(CodeGenModule &CGM, MCDC::State &MCDCState) + : CGM(CGM), DecisionStack(1, DecisionStackSentinel), + MCDCState(MCDCState) {} + + /// Return whether the build of the control flow map is at the top-level + /// (root) of a logical operator nest in a boolean expression prior to the + /// assignment of condition IDs. + bool isIdle() const { return (NextID == 0 && !NotMapped); } + + /// Return whether any IDs have been assigned in the build of the control + /// flow map, indicating that the map is being generated for this boolean + /// expression. + bool isBuilding() const { return (NextID > 0); } + + /// Set the given condition's ID. + void setCondID(const Expr *Cond, mcdc::ConditionID ID) { + MCDCState.BranchByStmt[CodeGenFunction::stripCond(Cond)] = {ID, + DecisionStmt}; + } + + /// Return the ID of a given condition. + mcdc::ConditionID getCondID(const Expr *Cond) const { + auto I = MCDCState.BranchByStmt.find(CodeGenFunction::stripCond(Cond)); + if (I == MCDCState.BranchByStmt.end()) + return -1; + else + return I->second.ID; + } + + /// Return the LHS Decision ([0,0] if not set). + const mcdc::ConditionIDs &back() const { return DecisionStack.back(); } + + /// Push the binary operator statement to track the nest level and assign IDs + /// to the operator's LHS and RHS. The RHS may be a larger subtree that is + /// broken up on successive levels. + void pushAndAssignIDs(const BinaryOperator *E) { + if (!CGM.getCodeGenOpts().MCDCCoverage) + return; + + // If binary expression is disqualified, don't do mapping. + if (!isBuilding() && + !MCDCState.DecisionByStmt.contains(CodeGenFunction::stripCond(E))) + NotMapped = true; + + // Don't go any further if we don't need to map condition IDs. + if (NotMapped) + return; + + if (NextID == 0) { + DecisionStmt = E; + assert(MCDCState.DecisionByStmt.contains(E)); + } + + const mcdc::ConditionIDs &ParentDecision = DecisionStack.back(); + + // If the operator itself has an assigned ID, this means it represents a + // larger subtree. In this case, assign that ID to its LHS node. Its RHS + // will receive a new ID below. Otherwise, assign ID+1 to LHS. + if (MCDCState.BranchByStmt.contains(CodeGenFunction::stripCond(E))) + setCondID(E->getLHS(), getCondID(E)); + else + setCondID(E->getLHS(), NextID++); + + // Assign a ID+1 for the RHS. + mcdc::ConditionID RHSid = NextID++; + setCondID(E->getRHS(), RHSid); + + // Push the LHS decision IDs onto the DecisionStack. + if (isLAnd(E)) + DecisionStack.push_back({ParentDecision[false], RHSid}); + else + DecisionStack.push_back({RHSid, ParentDecision[true]}); + } + + /// Pop and return the LHS Decision ([0,0] if not set). + mcdc::ConditionIDs pop() { + if (!CGM.getCodeGenOpts().MCDCCoverage || NotMapped) + return DecisionStackSentinel; + + assert(DecisionStack.size() > 1); + return DecisionStack.pop_back_val(); + } + + /// Return the total number of conditions and reset the state. The number of + /// conditions is zero if the expression isn't mapped. + unsigned getTotalConditionsAndReset(const BinaryOperator *E) { + if (!CGM.getCodeGenOpts().MCDCCoverage) + return 0; + + assert(!isIdle()); + assert(DecisionStack.size() == 1); + + // Reset state if not doing mapping. + if (NotMapped) { + NotMapped = false; + assert(NextID == 0); + return 0; + } + + // Set number of conditions and reset. + unsigned TotalConds = NextID; + + // Reset ID back to beginning. + NextID = 0; + + return TotalConds; + } +}; + /// A StmtVisitor that creates coverage mapping regions which map /// from the source code locations to the PGO counters. struct CounterCoverageMappingBuilder @@ -541,12 +887,17 @@ struct CounterCoverageMappingBuilder /// The map of statements to count values. llvm::DenseMap<const Stmt *, unsigned> &CounterMap; + MCDC::State &MCDCState; + /// A stack of currently live regions. - std::vector<SourceMappingRegion> RegionStack; + llvm::SmallVector<SourceMappingRegion> RegionStack; + + /// Set if the Expr should be handled as a leaf even if it is kind of binary + /// logical ops (&&, ||). + llvm::DenseSet<const Stmt *> LeafExprSet; - /// The currently deferred region: its end location and count can be set once - /// its parent has been popped from the region stack. - Optional<SourceMappingRegion> DeferredRegion; + /// An object to manage MCDC regions. + MCDCCoverageBuilder MCDCBuilder; CounterExpressionBuilder Builder; @@ -556,21 +907,31 @@ struct CounterCoverageMappingBuilder /// expressions cross file or macro boundaries. SourceLocation MostRecentLocation; - /// Location of the last terminated region. - Optional<std::pair<SourceLocation, size_t>> LastTerminatedRegion; + /// Whether the visitor at a terminate statement. + bool HasTerminateStmt = false; + + /// Gap region counter after terminate statement. + Counter GapRegionCounter; /// Return a counter for the subtraction of \c RHS from \c LHS - Counter subtractCounters(Counter LHS, Counter RHS) { - return Builder.subtract(LHS, RHS); + Counter subtractCounters(Counter LHS, Counter RHS, bool Simplify = true) { + assert(!llvm::EnableSingleByteCoverage && + "cannot add counters when single byte coverage mode is enabled"); + return Builder.subtract(LHS, RHS, Simplify); } /// Return a counter for the sum of \c LHS and \c RHS. - Counter addCounters(Counter LHS, Counter RHS) { - return Builder.add(LHS, RHS); + Counter addCounters(Counter LHS, Counter RHS, bool Simplify = true) { + assert(!llvm::EnableSingleByteCoverage && + "cannot add counters when single byte coverage mode is enabled"); + return Builder.add(LHS, RHS, Simplify); } - Counter addCounters(Counter C1, Counter C2, Counter C3) { - return addCounters(addCounters(C1, C2), C3); + Counter addCounters(Counter C1, Counter C2, Counter C3, + bool Simplify = true) { + assert(!llvm::EnableSingleByteCoverage && + "cannot add counters when single byte coverage mode is enabled"); + return addCounters(addCounters(C1, C2, Simplify), C3, Simplify); } /// Return the region counter for the given statement. @@ -584,81 +945,41 @@ struct CounterCoverageMappingBuilder /// /// Returns the index on the stack where the region was pushed. This can be /// used with popRegions to exit a "scope", ending the region that was pushed. - size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None, - Optional<SourceLocation> EndLoc = None, - Optional<Counter> FalseCount = None) { + size_t pushRegion(Counter Count, + std::optional<SourceLocation> StartLoc = std::nullopt, + std::optional<SourceLocation> EndLoc = std::nullopt, + std::optional<Counter> FalseCount = std::nullopt, + const mcdc::Parameters &BranchParams = std::monostate()) { - if (StartLoc && !FalseCount.hasValue()) { + if (StartLoc && !FalseCount) { MostRecentLocation = *StartLoc; - completeDeferred(Count, MostRecentLocation); } - RegionStack.emplace_back(Count, FalseCount, StartLoc, EndLoc, - FalseCount.hasValue()); + // If either of these locations is invalid, something elsewhere in the + // compiler has broken. + assert((!StartLoc || StartLoc->isValid()) && "Start location is not valid"); + assert((!EndLoc || EndLoc->isValid()) && "End location is not valid"); + + // However, we can still recover without crashing. + // If either location is invalid, set it to std::nullopt to avoid + // letting users of RegionStack think that region has a valid start/end + // location. + if (StartLoc && StartLoc->isInvalid()) + StartLoc = std::nullopt; + if (EndLoc && EndLoc->isInvalid()) + EndLoc = std::nullopt; + RegionStack.emplace_back(Count, FalseCount, BranchParams, StartLoc, EndLoc); return RegionStack.size() - 1; } - /// Complete any pending deferred region by setting its end location and - /// count, and then pushing it onto the region stack. - size_t completeDeferred(Counter Count, SourceLocation DeferredEndLoc) { - size_t Index = RegionStack.size(); - if (!DeferredRegion) - return Index; - - // Consume the pending region. - SourceMappingRegion DR = DeferredRegion.getValue(); - DeferredRegion = None; - - // If the region ends in an expansion, find the expansion site. - FileID StartFile = SM.getFileID(DR.getBeginLoc()); - if (SM.getFileID(DeferredEndLoc) != StartFile) { - if (isNestedIn(DeferredEndLoc, StartFile)) { - do { - DeferredEndLoc = getIncludeOrExpansionLoc(DeferredEndLoc); - } while (StartFile != SM.getFileID(DeferredEndLoc)); - } else { - return Index; - } - } - - // The parent of this deferred region ends where the containing decl ends, - // so the region isn't useful. - if (DR.getBeginLoc() == DeferredEndLoc) - return Index; - - // If we're visiting statements in non-source order (e.g switch cases or - // a loop condition) we can't construct a sensible deferred region. - if (!SpellingRegion(SM, DR.getBeginLoc(), DeferredEndLoc).isInSourceOrder()) - return Index; - - DR.setGap(true); - DR.setCounter(Count); - DR.setEndLoc(DeferredEndLoc); - handleFileExit(DeferredEndLoc); - RegionStack.push_back(DR); - return Index; - } - - /// Complete a deferred region created after a terminated region at the - /// top-level. - void completeTopLevelDeferredRegion(Counter Count, - SourceLocation DeferredEndLoc) { - if (DeferredRegion || !LastTerminatedRegion) - return; + size_t pushRegion(const mcdc::DecisionParameters &DecisionParams, + std::optional<SourceLocation> StartLoc = std::nullopt, + std::optional<SourceLocation> EndLoc = std::nullopt) { - if (LastTerminatedRegion->second != RegionStack.size()) - return; - - SourceLocation Start = LastTerminatedRegion->first; - if (SM.getFileID(Start) != SM.getMainFileID()) - return; + RegionStack.emplace_back(DecisionParams, StartLoc, EndLoc); - SourceMappingRegion DR = RegionStack.back(); - DR.setStartLoc(Start); - DR.setDeferred(false); - DeferredRegion = DR; - completeDeferred(Count, DeferredEndLoc); + return RegionStack.size() - 1; } size_t locationDepth(SourceLocation Loc) { @@ -676,10 +997,10 @@ struct CounterCoverageMappingBuilder /// function's \c SourceRegions. void popRegions(size_t ParentIndex) { assert(RegionStack.size() >= ParentIndex && "parent not in stack"); - bool ParentOfDeferredRegion = false; while (RegionStack.size() > ParentIndex) { SourceMappingRegion &Region = RegionStack.back(); - if (Region.hasStartLoc()) { + if (Region.hasStartLoc() && + (Region.hasEndLoc() || RegionStack[ParentIndex].hasEndLoc())) { SourceLocation StartLoc = Region.getBeginLoc(); SourceLocation EndLoc = Region.hasEndLoc() ? Region.getEndLoc() @@ -746,32 +1067,9 @@ struct CounterCoverageMappingBuilder assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc)); assert(SpellingRegion(SM, Region).isInSourceOrder()); SourceRegions.push_back(Region); - - if (ParentOfDeferredRegion) { - ParentOfDeferredRegion = false; - - // If there's an existing deferred region, keep the old one, because - // it means there are two consecutive returns (or a similar pattern). - if (!DeferredRegion.hasValue() && - // File IDs aren't gathered within macro expansions, so it isn't - // useful to try and create a deferred region inside of one. - !EndLoc.isMacroID()) - DeferredRegion = - SourceMappingRegion(Counter::getZero(), EndLoc, None); - } - } else if (Region.isDeferred()) { - assert(!ParentOfDeferredRegion && "Consecutive deferred regions"); - ParentOfDeferredRegion = true; } RegionStack.pop_back(); - - // If the zero region pushed after the last terminated region no longer - // exists, clear its cached information. - if (LastTerminatedRegion && - RegionStack.size() < LastTerminatedRegion->second) - LastTerminatedRegion = None; } - assert(!ParentOfDeferredRegion && "Deferred region with no parent"); } /// Return the currently active region. @@ -810,7 +1108,8 @@ struct CounterCoverageMappingBuilder /// and add it to the function's SourceRegions. A branch region tracks a /// "True" counter and a "False" counter for boolean expressions that /// result in the generation of a branch. - void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt) { + void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt, + const mcdc::ConditionIDs &Conds = {}) { // Check for NULL conditions. if (!C) return; @@ -819,7 +1118,15 @@ struct CounterCoverageMappingBuilder // region onto RegionStack but immediately pop it (which adds it to the // function's SourceRegions) because it doesn't apply to any other source // code other than the Condition. - if (CodeGenFunction::isInstrumentedCondition(C)) { + // With !SystemHeadersCoverage, binary logical ops in system headers may be + // treated as instrumentable conditions. + if (CodeGenFunction::isInstrumentedCondition(C) || + LeafExprSet.count(CodeGenFunction::stripCond(C))) { + mcdc::Parameters BranchParams; + mcdc::ConditionID ID = MCDCBuilder.getCondID(C); + if (ID >= 0) + BranchParams = mcdc::BranchParameters{ID, Conds}; + // If a condition can fold to true or false, the corresponding branch // will be removed. Create a region with both counters hard-coded to // zero. This allows us to visualize them in a special way. @@ -828,13 +1135,22 @@ struct CounterCoverageMappingBuilder // CodeGenFunction.c always returns false, but that is very heavy-handed. if (ConditionFoldsToBool(C)) popRegions(pushRegion(Counter::getZero(), getStart(C), getEnd(C), - Counter::getZero())); + Counter::getZero(), BranchParams)); else // Otherwise, create a region with the True counter and False counter. - popRegions(pushRegion(TrueCnt, getStart(C), getEnd(C), FalseCnt)); + popRegions(pushRegion(TrueCnt, getStart(C), getEnd(C), FalseCnt, + BranchParams)); } } + /// Create a Decision Region with a BitmapIdx and number of Conditions. This + /// type of region "contains" branch regions, one for each of the conditions. + /// The visualization tool will group everything together. + void createDecisionRegion(const Expr *C, + const mcdc::DecisionParameters &DecisionParams) { + popRegions(pushRegion(DecisionParams, getStart(C), getEnd(C))); + } + /// Create a Branch Region around a SwitchCase for code coverage /// and add it to the function's SourceRegions. void createSwitchCaseRegion(const SwitchCase *SC, Counter TrueCnt, @@ -849,13 +1165,11 @@ struct CounterCoverageMappingBuilder /// is already added to \c SourceRegions. bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc, bool isBranch = false) { - return SourceRegions.rend() != - std::find_if(SourceRegions.rbegin(), SourceRegions.rend(), - [&](const SourceMappingRegion &Region) { - return Region.getBeginLoc() == StartLoc && - Region.getEndLoc() == EndLoc && - Region.isBranch() == isBranch; - }); + return llvm::any_of( + llvm::reverse(SourceRegions), [&](const SourceMappingRegion &Region) { + return Region.getBeginLoc() == StartLoc && + Region.getEndLoc() == EndLoc && Region.isBranch() == isBranch; + }); } /// Adjust the most recently visited location to \c EndLoc. @@ -901,7 +1215,7 @@ struct CounterCoverageMappingBuilder } llvm::SmallSet<SourceLocation, 8> StartLocs; - Optional<Counter> ParentCounter; + std::optional<Counter> ParentCounter; for (SourceMappingRegion &I : llvm::reverse(RegionStack)) { if (!I.hasStartLoc()) continue; @@ -917,7 +1231,8 @@ struct CounterCoverageMappingBuilder // we've seen this region. if (StartLocs.insert(Loc).second) { if (I.isBranch()) - SourceRegions.emplace_back(I.getCounter(), I.getFalseCounter(), Loc, + SourceRegions.emplace_back(I.getCounter(), I.getFalseCounter(), + I.getMCDCParams(), Loc, getEndOfFileOrMacro(Loc), I.isBranch()); else SourceRegions.emplace_back(I.getCounter(), Loc, @@ -955,8 +1270,6 @@ struct CounterCoverageMappingBuilder handleFileExit(StartLoc); if (!Region.hasStartLoc()) Region.setStartLoc(StartLoc); - - completeDeferred(Region.getCounter(), StartLoc); } /// Mark \c S as a terminator, starting a zero region. @@ -967,30 +1280,62 @@ struct CounterCoverageMappingBuilder if (!Region.hasEndLoc()) Region.setEndLoc(EndLoc); pushRegion(Counter::getZero()); - auto &ZeroRegion = getRegion(); - ZeroRegion.setDeferred(true); - LastTerminatedRegion = {EndLoc, RegionStack.size()}; + HasTerminateStmt = true; } /// Find a valid gap range between \p AfterLoc and \p BeforeLoc. - Optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc, - SourceLocation BeforeLoc) { + std::optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc, + SourceLocation BeforeLoc) { + // Some statements (like AttributedStmt and ImplicitValueInitExpr) don't + // have valid source locations. Do not emit a gap region if this is the case + // in either AfterLoc end or BeforeLoc end. + if (AfterLoc.isInvalid() || BeforeLoc.isInvalid()) + return std::nullopt; + + // If AfterLoc is in function-like macro, use the right parenthesis + // location. + if (AfterLoc.isMacroID()) { + FileID FID = SM.getFileID(AfterLoc); + const SrcMgr::ExpansionInfo *EI = &SM.getSLocEntry(FID).getExpansion(); + if (EI->isFunctionMacroExpansion()) + AfterLoc = EI->getExpansionLocEnd(); + } + + size_t StartDepth = locationDepth(AfterLoc); + size_t EndDepth = locationDepth(BeforeLoc); + while (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc)) { + bool UnnestStart = StartDepth >= EndDepth; + bool UnnestEnd = EndDepth >= StartDepth; + if (UnnestEnd) { + assert(SM.isWrittenInSameFile(getStartOfFileOrMacro(BeforeLoc), + BeforeLoc)); + + BeforeLoc = getIncludeOrExpansionLoc(BeforeLoc); + assert(BeforeLoc.isValid()); + EndDepth--; + } + if (UnnestStart) { + assert(SM.isWrittenInSameFile(AfterLoc, + getEndOfFileOrMacro(AfterLoc))); + + AfterLoc = getIncludeOrExpansionLoc(AfterLoc); + assert(AfterLoc.isValid()); + AfterLoc = getPreciseTokenLocEnd(AfterLoc); + assert(AfterLoc.isValid()); + StartDepth--; + } + } + AfterLoc = getPreciseTokenLocEnd(AfterLoc); // If the start and end locations of the gap are both within the same macro // file, the range may not be in source order. if (AfterLoc.isMacroID() || BeforeLoc.isMacroID()) - return None; - if (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc)) - return None; + return std::nullopt; + if (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc) || + !SpellingRegion(SM, AfterLoc, BeforeLoc).isInSourceOrder()) + return std::nullopt; return {{AfterLoc, BeforeLoc}}; } - /// Find the source range after \p AfterStmt and before \p BeforeStmt. - Optional<SourceRange> findGapAreaBetween(const Stmt *AfterStmt, - const Stmt *BeforeStmt) { - return findGapAreaBetween(getPreciseTokenLocEnd(getEnd(AfterStmt)), - getStart(BeforeStmt)); - } - /// Emit a gap region between \p StartLoc and \p EndLoc with the given count. void fillGapAreaWithCount(SourceLocation StartLoc, SourceLocation EndLoc, Counter Count) { @@ -1004,6 +1349,69 @@ struct CounterCoverageMappingBuilder popRegions(Index); } + /// Find a valid range starting with \p StartingLoc and ending before \p + /// BeforeLoc. + std::optional<SourceRange> findAreaStartingFromTo(SourceLocation StartingLoc, + SourceLocation BeforeLoc) { + // If StartingLoc is in function-like macro, use its start location. + if (StartingLoc.isMacroID()) { + FileID FID = SM.getFileID(StartingLoc); + const SrcMgr::ExpansionInfo *EI = &SM.getSLocEntry(FID).getExpansion(); + if (EI->isFunctionMacroExpansion()) + StartingLoc = EI->getExpansionLocStart(); + } + + size_t StartDepth = locationDepth(StartingLoc); + size_t EndDepth = locationDepth(BeforeLoc); + while (!SM.isWrittenInSameFile(StartingLoc, BeforeLoc)) { + bool UnnestStart = StartDepth >= EndDepth; + bool UnnestEnd = EndDepth >= StartDepth; + if (UnnestEnd) { + assert(SM.isWrittenInSameFile(getStartOfFileOrMacro(BeforeLoc), + BeforeLoc)); + + BeforeLoc = getIncludeOrExpansionLoc(BeforeLoc); + assert(BeforeLoc.isValid()); + EndDepth--; + } + if (UnnestStart) { + assert(SM.isWrittenInSameFile(StartingLoc, + getStartOfFileOrMacro(StartingLoc))); + + StartingLoc = getIncludeOrExpansionLoc(StartingLoc); + assert(StartingLoc.isValid()); + StartDepth--; + } + } + // If the start and end locations of the gap are both within the same macro + // file, the range may not be in source order. + if (StartingLoc.isMacroID() || BeforeLoc.isMacroID()) + return std::nullopt; + if (!SM.isWrittenInSameFile(StartingLoc, BeforeLoc) || + !SpellingRegion(SM, StartingLoc, BeforeLoc).isInSourceOrder()) + return std::nullopt; + return {{StartingLoc, BeforeLoc}}; + } + + void markSkipped(SourceLocation StartLoc, SourceLocation BeforeLoc) { + const auto Skipped = findAreaStartingFromTo(StartLoc, BeforeLoc); + + if (!Skipped) + return; + + const auto NewStartLoc = Skipped->getBegin(); + const auto EndLoc = Skipped->getEnd(); + + if (NewStartLoc == EndLoc) + return; + assert(SpellingRegion(SM, NewStartLoc, EndLoc).isInSourceOrder()); + handleFileExit(NewStartLoc); + size_t Index = pushRegion(Counter{}, NewStartLoc, EndLoc); + getRegion().setSkipped(true); + handleFileExit(EndLoc); + popRegions(Index); + } + /// Keep counts of breaks and continues inside loops. struct BreakContinue { Counter BreakCount; @@ -1013,17 +1421,16 @@ struct CounterCoverageMappingBuilder CounterCoverageMappingBuilder( CoverageMappingModuleGen &CVM, - llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM, - const LangOptions &LangOpts) + llvm::DenseMap<const Stmt *, unsigned> &CounterMap, + MCDC::State &MCDCState, SourceManager &SM, const LangOptions &LangOpts) : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap), - DeferredRegion(None) {} + MCDCState(MCDCState), MCDCBuilder(CVM.getCodeGenModule(), MCDCState) {} /// Write the mapping data to the output stream void write(llvm::raw_ostream &OS) { llvm::SmallVector<unsigned, 8> VirtualFileMapping; gatherFileIDs(VirtualFileMapping); SourceRegionFilter Filter = emitExpansionRegions(); - assert(!DeferredRegion && "Deferred region never completed"); emitSourceRegions(Filter); gatherSkippedRegions(); @@ -1038,37 +1445,60 @@ struct CounterCoverageMappingBuilder void VisitStmt(const Stmt *S) { if (S->getBeginLoc().isValid()) extendRegion(S); + const Stmt *LastStmt = nullptr; + bool SaveTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; + GapRegionCounter = Counter::getZero(); for (const Stmt *Child : S->children()) - if (Child) + if (Child) { + // If last statement contains terminate statements, add a gap area + // between the two statements. + if (LastStmt && HasTerminateStmt) { + auto Gap = findGapAreaBetween(getEnd(LastStmt), getStart(Child)); + if (Gap) + fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), + GapRegionCounter); + SaveTerminateStmt = true; + HasTerminateStmt = false; + } this->Visit(Child); + LastStmt = Child; + } + if (SaveTerminateStmt) + HasTerminateStmt = true; handleFileExit(getEnd(S)); } void VisitDecl(const Decl *D) { - assert(!DeferredRegion && "Deferred region never completed"); - Stmt *Body = D->getBody(); - // Do not propagate region counts into system headers. - if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body)))) + // Do not propagate region counts into system headers unless collecting + // coverage from system headers is explicitly enabled. + if (!SystemHeadersCoverage && Body && + SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body)))) return; // Do not visit the artificial children nodes of defaulted methods. The // lexer may not be able to report back precise token end locations for // these children nodes (llvm.org/PR39822), and moreover users will not be // able to see coverage for them. + Counter BodyCounter = getRegionCounter(Body); bool Defaulted = false; if (auto *Method = dyn_cast<CXXMethodDecl>(D)) Defaulted = Method->isDefaulted(); + if (auto *Ctor = dyn_cast<CXXConstructorDecl>(D)) { + for (auto *Initializer : Ctor->inits()) { + if (Initializer->isWritten()) { + auto *Init = Initializer->getInit(); + if (getStart(Init).isValid() && getEnd(Init).isValid()) + propagateCounts(BodyCounter, Init); + } + } + } - propagateCounts(getRegionCounter(Body), Body, + propagateCounts(BodyCounter, Body, /*VisitChildren=*/!Defaulted); assert(RegionStack.empty() && "Regions entered but never exited"); - - // Discard the last uncompleted deferred region in a decl, if one exists. - // This prevents lines at the end of a function containing only whitespace - // or closing braces from being marked as uncovered. - DeferredRegion = None; } void VisitReturnStmt(const ReturnStmt *S) { @@ -1090,6 +1520,10 @@ struct CounterCoverageMappingBuilder terminateRegion(S); } + void VisitCoroutineSuspendExpr(const CoroutineSuspendExpr *E) { + Visit(E->getOperand()); + } + void VisitCXXThrowExpr(const CXXThrowExpr *E) { extendRegion(E); if (E->getSubExpr()) @@ -1102,8 +1536,6 @@ struct CounterCoverageMappingBuilder void VisitLabelStmt(const LabelStmt *S) { Counter LabelCount = getRegionCounter(S); SourceLocation Start = getStart(S); - completeTopLevelDeferredRegion(LabelCount, Start); - completeDeferred(LabelCount, Start); // We can't extendRegion here or we risk overlapping with our new region. handleFileExit(Start); pushRegion(LabelCount, Start); @@ -1112,8 +1544,9 @@ struct CounterCoverageMappingBuilder void VisitBreakStmt(const BreakStmt *S) { assert(!BreakContinueStack.empty() && "break not in a loop or switch!"); - BreakContinueStack.back().BreakCount = addCounters( - BreakContinueStack.back().BreakCount, getRegion().getCounter()); + if (!llvm::EnableSingleByteCoverage) + BreakContinueStack.back().BreakCount = addCounters( + BreakContinueStack.back().BreakCount, getRegion().getCounter()); // FIXME: a break in a switch should terminate regions for all preceding // case statements, not just the most recent one. terminateRegion(S); @@ -1121,8 +1554,9 @@ struct CounterCoverageMappingBuilder void VisitContinueStmt(const ContinueStmt *S) { assert(!BreakContinueStack.empty() && "continue stmt not in a loop!"); - BreakContinueStack.back().ContinueCount = addCounters( - BreakContinueStack.back().ContinueCount, getRegion().getCounter()); + if (!llvm::EnableSingleByteCoverage) + BreakContinueStack.back().ContinueCount = addCounters( + BreakContinueStack.back().ContinueCount, getRegion().getCounter()); terminateRegion(S); } @@ -1140,7 +1574,9 @@ struct CounterCoverageMappingBuilder extendRegion(S); Counter ParentCount = getRegion().getCounter(); - Counter BodyCount = getRegionCounter(S); + Counter BodyCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getBody()) + : getRegionCounter(S); // Handle the body first so that we can get the backedge count. BreakContinueStack.push_back(BreakContinue()); @@ -1148,50 +1584,86 @@ struct CounterCoverageMappingBuilder Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); BreakContinue BC = BreakContinueStack.pop_back_val(); + bool BodyHasTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; + // Go back to handle the condition. Counter CondCount = - addCounters(ParentCount, BackedgeCount, BC.ContinueCount); + llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getCond()) + : addCounters(ParentCount, BackedgeCount, BC.ContinueCount); propagateCounts(CondCount, S->getCond()); adjustForOutOfOrderTraversal(getEnd(S)); // The body count applies to the area immediately after the increment. - auto Gap = findGapAreaBetween(S->getCond(), S->getBody()); + auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody())); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); Counter OutCount = - addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount)); - if (OutCount != ParentCount) + llvm::EnableSingleByteCoverage + ? getRegionCounter(S) + : addCounters(BC.BreakCount, + subtractCounters(CondCount, BodyCount)); + + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + if (BodyHasTerminateStmt) + HasTerminateStmt = true; + } // Create Branch Region around condition. - createBranchRegion(S->getCond(), BodyCount, - subtractCounters(CondCount, BodyCount)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(S->getCond(), BodyCount, + subtractCounters(CondCount, BodyCount)); } void VisitDoStmt(const DoStmt *S) { extendRegion(S); Counter ParentCount = getRegion().getCounter(); - Counter BodyCount = getRegionCounter(S); + Counter BodyCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getBody()) + : getRegionCounter(S); BreakContinueStack.push_back(BreakContinue()); extendRegion(S->getBody()); - Counter BackedgeCount = - propagateCounts(addCounters(ParentCount, BodyCount), S->getBody()); + + Counter BackedgeCount; + if (llvm::EnableSingleByteCoverage) + propagateCounts(BodyCount, S->getBody()); + else + BackedgeCount = + propagateCounts(addCounters(ParentCount, BodyCount), S->getBody()); + BreakContinue BC = BreakContinueStack.pop_back_val(); - Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount); + bool BodyHasTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; + + Counter CondCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getCond()) + : addCounters(BackedgeCount, BC.ContinueCount); propagateCounts(CondCount, S->getCond()); Counter OutCount = - addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount)); - if (OutCount != ParentCount) + llvm::EnableSingleByteCoverage + ? getRegionCounter(S) + : addCounters(BC.BreakCount, + subtractCounters(CondCount, BodyCount)); + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + } // Create Branch Region around condition. - createBranchRegion(S->getCond(), BodyCount, - subtractCounters(CondCount, BodyCount)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(S->getCond(), BodyCount, + subtractCounters(CondCount, BodyCount)); + + if (BodyHasTerminateStmt) + HasTerminateStmt = true; } void VisitForStmt(const ForStmt *S) { @@ -1200,7 +1672,9 @@ struct CounterCoverageMappingBuilder Visit(S->getInit()); Counter ParentCount = getRegion().getCounter(); - Counter BodyCount = getRegionCounter(S); + Counter BodyCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getBody()) + : getRegionCounter(S); // The loop increment may contain a break or continue. if (S->getInc()) @@ -1212,37 +1686,56 @@ struct CounterCoverageMappingBuilder Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); BreakContinue BodyBC = BreakContinueStack.pop_back_val(); + bool BodyHasTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; + // The increment is essentially part of the body but it needs to include // the count for all the continue statements. BreakContinue IncrementBC; if (const Stmt *Inc = S->getInc()) { - propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc); + Counter IncCount; + if (llvm::EnableSingleByteCoverage) + IncCount = getRegionCounter(S->getInc()); + else + IncCount = addCounters(BackedgeCount, BodyBC.ContinueCount); + propagateCounts(IncCount, Inc); IncrementBC = BreakContinueStack.pop_back_val(); } // Go back to handle the condition. - Counter CondCount = addCounters( - addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount), - IncrementBC.ContinueCount); + Counter CondCount = + llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getCond()) + : addCounters( + addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount), + IncrementBC.ContinueCount); + if (const Expr *Cond = S->getCond()) { propagateCounts(CondCount, Cond); adjustForOutOfOrderTraversal(getEnd(S)); } // The body count applies to the area immediately after the increment. - auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), - getStart(S->getBody())); + auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody())); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); - Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount, - subtractCounters(CondCount, BodyCount)); - if (OutCount != ParentCount) + Counter OutCount = + llvm::EnableSingleByteCoverage + ? getRegionCounter(S) + : addCounters(BodyBC.BreakCount, IncrementBC.BreakCount, + subtractCounters(CondCount, BodyCount)); + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + if (BodyHasTerminateStmt) + HasTerminateStmt = true; + } // Create Branch Region around condition. - createBranchRegion(S->getCond(), BodyCount, - subtractCounters(CondCount, BodyCount)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(S->getCond(), BodyCount, + subtractCounters(CondCount, BodyCount)); } void VisitCXXForRangeStmt(const CXXForRangeStmt *S) { @@ -1253,29 +1746,43 @@ struct CounterCoverageMappingBuilder Visit(S->getRangeStmt()); Counter ParentCount = getRegion().getCounter(); - Counter BodyCount = getRegionCounter(S); + Counter BodyCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getBody()) + : getRegionCounter(S); BreakContinueStack.push_back(BreakContinue()); extendRegion(S->getBody()); Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); BreakContinue BC = BreakContinueStack.pop_back_val(); + bool BodyHasTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; + // The body count applies to the area immediately after the range. - auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), - getStart(S->getBody())); + auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody())); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); - Counter LoopCount = - addCounters(ParentCount, BackedgeCount, BC.ContinueCount); - Counter OutCount = - addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount)); - if (OutCount != ParentCount) + Counter OutCount; + Counter LoopCount; + if (llvm::EnableSingleByteCoverage) + OutCount = getRegionCounter(S); + else { + LoopCount = addCounters(ParentCount, BackedgeCount, BC.ContinueCount); + OutCount = + addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount)); + } + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + if (BodyHasTerminateStmt) + HasTerminateStmt = true; + } // Create Branch Region around condition. - createBranchRegion(S->getCond(), BodyCount, - subtractCounters(LoopCount, BodyCount)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(S->getCond(), BodyCount, + subtractCounters(LoopCount, BodyCount)); } void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) { @@ -1291,8 +1798,7 @@ struct CounterCoverageMappingBuilder BreakContinue BC = BreakContinueStack.pop_back_val(); // The body count applies to the area immediately after the collection. - auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), - getStart(S->getBody())); + auto Gap = findGapAreaBetween(S->getRParenLoc(), getStart(S->getBody())); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); @@ -1300,8 +1806,10 @@ struct CounterCoverageMappingBuilder addCounters(ParentCount, BackedgeCount, BC.ContinueCount); Counter OutCount = addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount)); - if (OutCount != ParentCount) + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + } } void VisitSwitchStmt(const SwitchStmt *S) { @@ -1321,8 +1829,7 @@ struct CounterCoverageMappingBuilder // the unreachable code at the beginning of the switch body. size_t Index = pushRegion(Counter::getZero(), getStart(CS)); getRegion().setGap(true); - for (const auto *Child : CS->children()) - Visit(Child); + Visit(Body); // Set the end for the body of the switch, if it isn't already set. for (size_t i = RegionStack.size(); i != Index; --i) { @@ -1336,7 +1843,7 @@ struct CounterCoverageMappingBuilder propagateCounts(Counter::getZero(), Body); BreakContinue BC = BreakContinueStack.pop_back_val(); - if (!BreakContinueStack.empty()) + if (!BreakContinueStack.empty() && !llvm::EnableSingleByteCoverage) BreakContinueStack.back().ContinueCount = addCounters( BreakContinueStack.back().ContinueCount, BC.ContinueCount); @@ -1344,12 +1851,18 @@ struct CounterCoverageMappingBuilder Counter ExitCount = getRegionCounter(S); SourceLocation ExitLoc = getEnd(S); pushRegion(ExitCount); + GapRegionCounter = ExitCount; // Ensure that handleFileExit recognizes when the end location is located // in a different file. MostRecentLocation = getStart(S); handleFileExit(ExitLoc); + // When single byte coverage mode is enabled, do not create branch region by + // early returning. + if (llvm::EnableSingleByteCoverage) + return; + // Create a Branch Region around each Case. Subtract the case's // counter from the Parent counter to track the "False" branch count. Counter CaseCountSum; @@ -1357,11 +1870,16 @@ struct CounterCoverageMappingBuilder const SwitchCase *Case = S->getSwitchCaseList(); for (; Case; Case = Case->getNextSwitchCase()) { HasDefaultCase = HasDefaultCase || isa<DefaultStmt>(Case); - CaseCountSum = addCounters(CaseCountSum, getRegionCounter(Case)); + CaseCountSum = + addCounters(CaseCountSum, getRegionCounter(Case), /*Simplify=*/false); createSwitchCaseRegion( Case, getRegionCounter(Case), subtractCounters(ParentCount, getRegionCounter(Case))); } + // Simplify is skipped while building the counters above: it can get really + // slow on top of switches with thousands of cases. Instead, trigger + // simplification by adding zero to the last counter. + CaseCountSum = addCounters(CaseCountSum, Counter::getZero()); // If no explicit default case exists, create a branch region to represent // the hidden branch, which will be added later by the CodeGen. This region @@ -1377,8 +1895,10 @@ struct CounterCoverageMappingBuilder extendRegion(S); SourceMappingRegion &Parent = getRegion(); + Counter Count = llvm::EnableSingleByteCoverage + ? getRegionCounter(S) + : addCounters(Parent.getCounter(), getRegionCounter(S)); - Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S)); // Reuse the existing region if it starts at our label. This is typical of // the first case in a switch. if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S)) @@ -1386,6 +1906,8 @@ struct CounterCoverageMappingBuilder else pushRegion(Count, getStart(S)); + GapRegionCounter = Count; + if (const auto *CS = dyn_cast<CaseStmt>(S)) { Visit(CS->getLHS()); if (const Expr *RHS = CS->getRHS()) @@ -1394,7 +1916,97 @@ struct CounterCoverageMappingBuilder Visit(S->getSubStmt()); } + void coverIfConsteval(const IfStmt *S) { + assert(S->isConsteval()); + + const auto *Then = S->getThen(); + const auto *Else = S->getElse(); + + // It's better for llvm-cov to create a new region with same counter + // so line-coverage can be properly calculated for lines containing + // a skipped region (without it the line is marked uncovered) + const Counter ParentCount = getRegion().getCounter(); + + extendRegion(S); + + if (S->isNegatedConsteval()) { + // ignore 'if consteval' + markSkipped(S->getIfLoc(), getStart(Then)); + propagateCounts(ParentCount, Then); + + if (Else) { + // ignore 'else <else>' + markSkipped(getEnd(Then), getEnd(Else)); + } + } else { + assert(S->isNonNegatedConsteval()); + // ignore 'if consteval <then> [else]' + markSkipped(S->getIfLoc(), Else ? getStart(Else) : getEnd(Then)); + + if (Else) + propagateCounts(ParentCount, Else); + } + } + + void coverIfConstexpr(const IfStmt *S) { + assert(S->isConstexpr()); + + // evaluate constant condition... + const bool isTrue = + S->getCond() + ->EvaluateKnownConstInt(CVM.getCodeGenModule().getContext()) + .getBoolValue(); + + extendRegion(S); + + // I'm using 'propagateCounts' later as new region is better and allows me + // to properly calculate line coverage in llvm-cov utility + const Counter ParentCount = getRegion().getCounter(); + + // ignore 'if constexpr (' + SourceLocation startOfSkipped = S->getIfLoc(); + + if (const auto *Init = S->getInit()) { + const auto start = getStart(Init); + const auto end = getEnd(Init); + + // this check is to make sure typedef here which doesn't have valid source + // location won't crash it + if (start.isValid() && end.isValid()) { + markSkipped(startOfSkipped, start); + propagateCounts(ParentCount, Init); + startOfSkipped = getEnd(Init); + } + } + + const auto *Then = S->getThen(); + const auto *Else = S->getElse(); + + if (isTrue) { + // ignore '<condition>)' + markSkipped(startOfSkipped, getStart(Then)); + propagateCounts(ParentCount, Then); + + if (Else) + // ignore 'else <else>' + markSkipped(getEnd(Then), getEnd(Else)); + } else { + // ignore '<condition>) <then> [else]' + markSkipped(startOfSkipped, Else ? getStart(Else) : getEnd(Then)); + + if (Else) + propagateCounts(ParentCount, Else); + } + } + void VisitIfStmt(const IfStmt *S) { + // "if constexpr" and "if consteval" are not normal conditional statements, + // their discarded statement should be skipped + if (S->isConsteval()) + return coverIfConsteval(S); + else if (S->isConstexpr()) + return coverIfConstexpr(S); + extendRegion(S); if (S->getInit()) Visit(S->getInit()); @@ -1404,37 +2016,60 @@ struct CounterCoverageMappingBuilder extendRegion(S->getCond()); Counter ParentCount = getRegion().getCounter(); - Counter ThenCount = getRegionCounter(S); + Counter ThenCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(S->getThen()) + : getRegionCounter(S); // Emitting a counter for the condition makes it easier to interpret the // counter for the body when looking at the coverage. propagateCounts(ParentCount, S->getCond()); // The 'then' count applies to the area immediately after the condition. - auto Gap = findGapAreaBetween(S->getCond(), S->getThen()); + std::optional<SourceRange> Gap = + findGapAreaBetween(S->getRParenLoc(), getStart(S->getThen())); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount); extendRegion(S->getThen()); Counter OutCount = propagateCounts(ThenCount, S->getThen()); - Counter ElseCount = subtractCounters(ParentCount, ThenCount); + Counter ElseCount; + if (!llvm::EnableSingleByteCoverage) + ElseCount = subtractCounters(ParentCount, ThenCount); + else if (S->getElse()) + ElseCount = getRegionCounter(S->getElse()); + if (const Stmt *Else = S->getElse()) { + bool ThenHasTerminateStmt = HasTerminateStmt; + HasTerminateStmt = false; // The 'else' count applies to the area immediately after the 'then'. - Gap = findGapAreaBetween(S->getThen(), Else); + std::optional<SourceRange> Gap = + findGapAreaBetween(getEnd(S->getThen()), getStart(Else)); if (Gap) fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount); extendRegion(Else); - OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else)); - } else + + Counter ElseOutCount = propagateCounts(ElseCount, Else); + if (!llvm::EnableSingleByteCoverage) + OutCount = addCounters(OutCount, ElseOutCount); + + if (ThenHasTerminateStmt) + HasTerminateStmt = true; + } else if (!llvm::EnableSingleByteCoverage) OutCount = addCounters(OutCount, ElseCount); - if (OutCount != ParentCount) + if (llvm::EnableSingleByteCoverage) + OutCount = getRegionCounter(S); + + if (OutCount != ParentCount) { pushRegion(OutCount); + GapRegionCounter = OutCount; + } - // Create Branch Region around condition. - createBranchRegion(S->getCond(), ThenCount, - subtractCounters(ParentCount, ThenCount)); + if (!S->isConsteval() && !llvm::EnableSingleByteCoverage) + // Create Branch Region around condition. + createBranchRegion(S->getCond(), ThenCount, + subtractCounters(ParentCount, ThenCount)); } void VisitCXXTryStmt(const CXXTryStmt *S) { @@ -1460,11 +2095,16 @@ struct CounterCoverageMappingBuilder extendRegion(E); Counter ParentCount = getRegion().getCounter(); - Counter TrueCount = getRegionCounter(E); - - Visit(E->getCond()); - - if (!isa<BinaryConditionalOperator>(E)) { + Counter TrueCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(E->getTrueExpr()) + : getRegionCounter(E); + Counter OutCount; + + if (const auto *BCO = dyn_cast<BinaryConditionalOperator>(E)) { + propagateCounts(ParentCount, BCO->getCommon()); + OutCount = TrueCount; + } else { + propagateCounts(ParentCount, E->getCond()); // The 'then' count applies to the area immediately after the condition. auto Gap = findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr())); @@ -1472,27 +2112,130 @@ struct CounterCoverageMappingBuilder fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount); extendRegion(E->getTrueExpr()); - propagateCounts(TrueCount, E->getTrueExpr()); + OutCount = propagateCounts(TrueCount, E->getTrueExpr()); } extendRegion(E->getFalseExpr()); - propagateCounts(subtractCounters(ParentCount, TrueCount), - E->getFalseExpr()); + Counter FalseCount = llvm::EnableSingleByteCoverage + ? getRegionCounter(E->getFalseExpr()) + : subtractCounters(ParentCount, TrueCount); + + Counter FalseOutCount = propagateCounts(FalseCount, E->getFalseExpr()); + if (llvm::EnableSingleByteCoverage) + OutCount = getRegionCounter(E); + else + OutCount = addCounters(OutCount, FalseOutCount); + + if (OutCount != ParentCount) { + pushRegion(OutCount); + GapRegionCounter = OutCount; + } // Create Branch Region around condition. - createBranchRegion(E->getCond(), TrueCount, - subtractCounters(ParentCount, TrueCount)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(E->getCond(), TrueCount, + subtractCounters(ParentCount, TrueCount)); + } + + void createOrCancelDecision(const BinaryOperator *E, unsigned Since) { + unsigned NumConds = MCDCBuilder.getTotalConditionsAndReset(E); + if (NumConds == 0) + return; + + // Extract [ID, Conds] to construct the graph. + llvm::SmallVector<mcdc::ConditionIDs> CondIDs(NumConds); + for (const auto &SR : ArrayRef(SourceRegions).slice(Since)) { + if (SR.isMCDCBranch()) { + auto [ID, Conds] = SR.getMCDCBranchParams(); + CondIDs[ID] = Conds; + } + } + + // Construct the graph and calculate `Indices`. + mcdc::TVIdxBuilder Builder(CondIDs); + unsigned NumTVs = Builder.NumTestVectors; + unsigned MaxTVs = CVM.getCodeGenModule().getCodeGenOpts().MCDCMaxTVs; + assert(MaxTVs < mcdc::TVIdxBuilder::HardMaxTVs); + + if (NumTVs > MaxTVs) { + // NumTVs exceeds MaxTVs -- warn and cancel the Decision. + cancelDecision(E, Since, NumTVs, MaxTVs); + return; + } + + // Update the state for CodeGenPGO + assert(MCDCState.DecisionByStmt.contains(E)); + MCDCState.DecisionByStmt[E] = { + MCDCState.BitmapBits, // Top + std::move(Builder.Indices), + }; + + auto DecisionParams = mcdc::DecisionParameters{ + MCDCState.BitmapBits += NumTVs, // Tail + NumConds, + }; + + // Create MCDC Decision Region. + createDecisionRegion(E, DecisionParams); + } + + // Warn and cancel the Decision. + void cancelDecision(const BinaryOperator *E, unsigned Since, int NumTVs, + int MaxTVs) { + auto &Diag = CVM.getCodeGenModule().getDiags(); + unsigned DiagID = + Diag.getCustomDiagID(DiagnosticsEngine::Warning, + "unsupported MC/DC boolean expression; " + "number of test vectors (%0) exceeds max (%1). " + "Expression will not be covered"); + Diag.Report(E->getBeginLoc(), DiagID) << NumTVs << MaxTVs; + + // Restore MCDCBranch to Branch. + for (auto &SR : MutableArrayRef(SourceRegions).slice(Since)) { + assert(!SR.isMCDCDecision() && "Decision shouldn't be seen here"); + if (SR.isMCDCBranch()) + SR.resetMCDCParams(); + } + + // Tell CodeGenPGO not to instrument. + MCDCState.DecisionByStmt.erase(E); + } + + /// Check if E belongs to system headers. + bool isExprInSystemHeader(const BinaryOperator *E) const { + return (!SystemHeadersCoverage && + SM.isInSystemHeader(SM.getSpellingLoc(E->getOperatorLoc())) && + SM.isInSystemHeader(SM.getSpellingLoc(E->getBeginLoc())) && + SM.isInSystemHeader(SM.getSpellingLoc(E->getEndLoc()))); } void VisitBinLAnd(const BinaryOperator *E) { + if (isExprInSystemHeader(E)) { + LeafExprSet.insert(E); + return; + } + + bool IsRootNode = MCDCBuilder.isIdle(); + + unsigned SourceRegionsSince = SourceRegions.size(); + + // Keep track of Binary Operator and assign MCDC condition IDs. + MCDCBuilder.pushAndAssignIDs(E); + extendRegion(E->getLHS()); propagateCounts(getRegion().getCounter(), E->getLHS()); handleFileExit(getEnd(E->getLHS())); + // Track LHS True/False Decision. + const auto DecisionLHS = MCDCBuilder.pop(); + // Counter tracks the right hand side of a logical and operator. extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); + // Track RHS True/False Decision. + const auto DecisionRHS = MCDCBuilder.back(); + // Extract the RHS's Execution Counter. Counter RHSExecCnt = getRegionCounter(E); @@ -1503,45 +2246,103 @@ struct CounterCoverageMappingBuilder Counter ParentCnt = getRegion().getCounter(); // Create Branch Region around LHS condition. - createBranchRegion(E->getLHS(), RHSExecCnt, - subtractCounters(ParentCnt, RHSExecCnt)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(E->getLHS(), RHSExecCnt, + subtractCounters(ParentCnt, RHSExecCnt), DecisionLHS); // Create Branch Region around RHS condition. - createBranchRegion(E->getRHS(), RHSTrueCnt, - subtractCounters(RHSExecCnt, RHSTrueCnt)); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(E->getRHS(), RHSTrueCnt, + subtractCounters(RHSExecCnt, RHSTrueCnt), DecisionRHS); + + // Create MCDC Decision Region if at top-level (root). + if (IsRootNode) + createOrCancelDecision(E, SourceRegionsSince); + } + + // Determine whether the right side of OR operation need to be visited. + bool shouldVisitRHS(const Expr *LHS) { + bool LHSIsTrue = false; + bool LHSIsConst = false; + if (!LHS->isValueDependent()) + LHSIsConst = LHS->EvaluateAsBooleanCondition( + LHSIsTrue, CVM.getCodeGenModule().getContext()); + return !LHSIsConst || (LHSIsConst && !LHSIsTrue); } void VisitBinLOr(const BinaryOperator *E) { + if (isExprInSystemHeader(E)) { + LeafExprSet.insert(E); + return; + } + + bool IsRootNode = MCDCBuilder.isIdle(); + + unsigned SourceRegionsSince = SourceRegions.size(); + + // Keep track of Binary Operator and assign MCDC condition IDs. + MCDCBuilder.pushAndAssignIDs(E); + extendRegion(E->getLHS()); - propagateCounts(getRegion().getCounter(), E->getLHS()); + Counter OutCount = propagateCounts(getRegion().getCounter(), E->getLHS()); handleFileExit(getEnd(E->getLHS())); + // Track LHS True/False Decision. + const auto DecisionLHS = MCDCBuilder.pop(); + // Counter tracks the right hand side of a logical or operator. extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); + // Track RHS True/False Decision. + const auto DecisionRHS = MCDCBuilder.back(); + // Extract the RHS's Execution Counter. Counter RHSExecCnt = getRegionCounter(E); // Extract the RHS's "False" Instance Counter. Counter RHSFalseCnt = getRegionCounter(E->getRHS()); + if (!shouldVisitRHS(E->getLHS())) { + GapRegionCounter = OutCount; + } + // Extract the Parent Region Counter. Counter ParentCnt = getRegion().getCounter(); // Create Branch Region around LHS condition. - createBranchRegion(E->getLHS(), subtractCounters(ParentCnt, RHSExecCnt), - RHSExecCnt); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(E->getLHS(), subtractCounters(ParentCnt, RHSExecCnt), + RHSExecCnt, DecisionLHS); // Create Branch Region around RHS condition. - createBranchRegion(E->getRHS(), subtractCounters(RHSExecCnt, RHSFalseCnt), - RHSFalseCnt); + if (!llvm::EnableSingleByteCoverage) + createBranchRegion(E->getRHS(), subtractCounters(RHSExecCnt, RHSFalseCnt), + RHSFalseCnt, DecisionRHS); + + // Create MCDC Decision Region if at top-level (root). + if (IsRootNode) + createOrCancelDecision(E, SourceRegionsSince); } void VisitLambdaExpr(const LambdaExpr *LE) { // Lambdas are treated as their own functions for now, so we shouldn't // propagate counts into them. } + + void VisitArrayInitLoopExpr(const ArrayInitLoopExpr *AILE) { + Visit(AILE->getCommonExpr()->getSourceExpr()); + } + + void VisitPseudoObjectExpr(const PseudoObjectExpr *POE) { + // Just visit syntatic expression as this is what users actually write. + VisitStmt(POE->getSyntacticForm()); + } + + void VisitOpaqueValueExpr(const OpaqueValueExpr* OVE) { + if (OVE->isUnique()) + Visit(OVE->getSourceExpr()); + } }; } // end anonymous namespace @@ -1566,17 +2367,36 @@ static void dump(llvm::raw_ostream &OS, StringRef FunctionName, OS << "Gap,"; break; case CounterMappingRegion::BranchRegion: + case CounterMappingRegion::MCDCBranchRegion: OS << "Branch,"; break; + case CounterMappingRegion::MCDCDecisionRegion: + OS << "Decision,"; + break; } OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = "; - Ctx.dump(R.Count, OS); - if (R.Kind == CounterMappingRegion::BranchRegion) { - OS << ", "; - Ctx.dump(R.FalseCount, OS); + if (const auto *DecisionParams = + std::get_if<mcdc::DecisionParameters>(&R.MCDCParams)) { + OS << "M:" << DecisionParams->BitmapIdx; + OS << ", C:" << DecisionParams->NumConditions; + } else { + Ctx.dump(R.Count, OS); + + if (R.Kind == CounterMappingRegion::BranchRegion || + R.Kind == CounterMappingRegion::MCDCBranchRegion) { + OS << ", "; + Ctx.dump(R.FalseCount, OS); + } + } + + if (const auto *BranchParams = + std::get_if<mcdc::BranchParameters>(&R.MCDCParams)) { + OS << " [" << BranchParams->ID + 1 << "," + << BranchParams->Conds[true] + 1; + OS << "," << BranchParams->Conds[false] + 1 << "] "; } if (R.Kind == CounterMappingRegion::ExpansionRegion) @@ -1587,16 +2407,27 @@ static void dump(llvm::raw_ostream &OS, StringRef FunctionName, CoverageMappingModuleGen::CoverageMappingModuleGen( CodeGenModule &CGM, CoverageSourceInfo &SourceInfo) - : CGM(CGM), SourceInfo(SourceInfo) { - ProfilePrefixMap = CGM.getCodeGenOpts().ProfilePrefixMap; + : CGM(CGM), SourceInfo(SourceInfo) {} + +std::string CoverageMappingModuleGen::getCurrentDirname() { + if (!CGM.getCodeGenOpts().CoverageCompilationDir.empty()) + return CGM.getCodeGenOpts().CoverageCompilationDir; + + SmallString<256> CWD; + llvm::sys::fs::current_path(CWD); + return CWD.str().str(); } std::string CoverageMappingModuleGen::normalizeFilename(StringRef Filename) { llvm::SmallString<256> Path(Filename); - llvm::sys::fs::make_absolute(Path); llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true); - for (const auto &Entry : ProfilePrefixMap) { - if (llvm::sys::path::replace_path_prefix(Path, Entry.first, Entry.second)) + + /// Traverse coverage prefix map in reverse order because prefix replacements + /// are applied in reverse order starting from the last one when multiple + /// prefix replacement options are provided. + for (const auto &[From, To] : + llvm::reverse(CGM.getCodeGenOpts().CoveragePrefixMap)) { + if (llvm::sys::path::replace_path_prefix(Path, From, To)) break; } return Path.str().str(); @@ -1631,7 +2462,7 @@ void CoverageMappingModuleGen::emitFunctionMappingRecord( #include "llvm/ProfileData/InstrProfData.inc" }; auto *FunctionRecordTy = - llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes), + llvm::StructType::get(Ctx, ArrayRef(FunctionRecordTypes), /*isPacked=*/true); // Create the function record constant. @@ -1639,8 +2470,8 @@ void CoverageMappingModuleGen::emitFunctionMappingRecord( llvm::Constant *FunctionRecordVals[] = { #include "llvm/ProfileData/InstrProfData.inc" }; - auto *FuncRecordConstant = llvm::ConstantStruct::get( - FunctionRecordTy, makeArrayRef(FunctionRecordVals)); + auto *FuncRecordConstant = + llvm::ConstantStruct::get(FunctionRecordTy, ArrayRef(FunctionRecordVals)); // Create the function record global. auto *FuncRecord = new llvm::GlobalVariable( @@ -1660,13 +2491,11 @@ void CoverageMappingModuleGen::emitFunctionMappingRecord( void CoverageMappingModuleGen::addFunctionMappingRecord( llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash, const std::string &CoverageMapping, bool IsUsed) { - llvm::LLVMContext &Ctx = CGM.getLLVMContext(); const uint64_t NameHash = llvm::IndexedInstrProf::ComputeHash(NameValue); FunctionRecords.push_back({NameHash, FuncHash, CoverageMapping, IsUsed}); if (!IsUsed) - FunctionNames.push_back( - llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx))); + FunctionNames.push_back(NamePtr); if (CGM.getCodeGenOpts().DumpCoverageMapping) { // Dump the coverage mapping data for this function by decoding the @@ -1674,18 +2503,17 @@ void CoverageMappingModuleGen::addFunctionMappingRecord( // also processed by the CoverageMappingWriter which performs // additional minimization operations such as reducing the number of // expressions. + llvm::SmallVector<std::string, 16> FilenameStrs; std::vector<StringRef> Filenames; std::vector<CounterExpression> Expressions; std::vector<CounterMappingRegion> Regions; - llvm::SmallVector<std::string, 16> FilenameStrs; - llvm::SmallVector<StringRef, 16> FilenameRefs; - FilenameStrs.resize(FileEntries.size()); - FilenameRefs.resize(FileEntries.size()); + FilenameStrs.resize(FileEntries.size() + 1); + FilenameStrs[0] = normalizeFilename(getCurrentDirname()); for (const auto &Entry : FileEntries) { auto I = Entry.second; - FilenameStrs[I] = normalizeFilename(Entry.first->getName()); - FilenameRefs[I] = FilenameStrs[I]; + FilenameStrs[I] = normalizeFilename(Entry.first.getName()); } + ArrayRef<std::string> FilenameRefs = llvm::ArrayRef(FilenameStrs); RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames, Expressions, Regions); if (Reader.read()) @@ -1702,19 +2530,18 @@ void CoverageMappingModuleGen::emit() { // Create the filenames and merge them with coverage mappings llvm::SmallVector<std::string, 16> FilenameStrs; - llvm::SmallVector<StringRef, 16> FilenameRefs; - FilenameStrs.resize(FileEntries.size()); - FilenameRefs.resize(FileEntries.size()); + FilenameStrs.resize(FileEntries.size() + 1); + // The first filename is the current working directory. + FilenameStrs[0] = normalizeFilename(getCurrentDirname()); for (const auto &Entry : FileEntries) { auto I = Entry.second; - FilenameStrs[I] = normalizeFilename(Entry.first->getName()); - FilenameRefs[I] = FilenameStrs[I]; + FilenameStrs[I] = normalizeFilename(Entry.first.getName()); } std::string Filenames; { llvm::raw_string_ostream OS(Filenames); - CoverageFilenamesSectionWriter(FilenameRefs).write(OS); + CoverageFilenamesSectionWriter(FilenameStrs).write(OS); } auto *FilenamesVal = llvm::ConstantDataArray::getString(Ctx, Filenames, false); @@ -1732,20 +2559,19 @@ void CoverageMappingModuleGen::emit() { #include "llvm/ProfileData/InstrProfData.inc" }; auto CovDataHeaderTy = - llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes)); + llvm::StructType::get(Ctx, ArrayRef(CovDataHeaderTypes)); llvm::Constant *CovDataHeaderVals[] = { #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init, #include "llvm/ProfileData/InstrProfData.inc" }; - auto CovDataHeaderVal = llvm::ConstantStruct::get( - CovDataHeaderTy, makeArrayRef(CovDataHeaderVals)); + auto CovDataHeaderVal = + llvm::ConstantStruct::get(CovDataHeaderTy, ArrayRef(CovDataHeaderVals)); // Create the coverage data record llvm::Type *CovDataTypes[] = {CovDataHeaderTy, FilenamesVal->getType()}; - auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes)); + auto CovDataTy = llvm::StructType::get(Ctx, ArrayRef(CovDataTypes)); llvm::Constant *TUDataVals[] = {CovDataHeaderVal, FilenamesVal}; - auto CovDataVal = - llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals)); + auto CovDataVal = llvm::ConstantStruct::get(CovDataTy, ArrayRef(TUDataVals)); auto CovData = new llvm::GlobalVariable( CGM.getModule(), CovDataTy, true, llvm::GlobalValue::PrivateLinkage, CovDataVal, llvm::getCoverageMappingVarName()); @@ -1757,7 +2583,7 @@ void CoverageMappingModuleGen::emit() { CGM.addUsedGlobal(CovData); // Create the deferred function records array if (!FunctionNames.empty()) { - auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx), + auto NamesArrTy = llvm::ArrayType::get(llvm::PointerType::getUnqual(Ctx), FunctionNames.size()); auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames); // This variable will *NOT* be emitted to the object file. It is used @@ -1768,19 +2594,20 @@ void CoverageMappingModuleGen::emit() { } } -unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) { +unsigned CoverageMappingModuleGen::getFileID(FileEntryRef File) { auto It = FileEntries.find(File); if (It != FileEntries.end()) return It->second; - unsigned FileID = FileEntries.size(); + unsigned FileID = FileEntries.size() + 1; FileEntries.insert(std::make_pair(File, FileID)); return FileID; } void CoverageMappingGen::emitCounterMapping(const Decl *D, llvm::raw_ostream &OS) { - assert(CounterMap); - CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts); + assert(CounterMap && MCDCState); + CounterCoverageMappingBuilder Walker(CVM, *CounterMap, *MCDCState, SM, + LangOpts); Walker.VisitDecl(D); Walker.write(OS); } |