diff options
Diffstat (limited to 'clang/lib')
| -rw-r--r-- | clang/lib/CodeGen/CGClass.cpp | 6 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CGExprScalar.cpp | 57 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CGStmt.cpp | 14 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CodeGenFunction.cpp | 98 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CodeGenFunction.h | 58 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CodeGenPGO.cpp | 263 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CodeGenPGO.h | 14 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CoverageMappingGen.cpp | 405 | ||||
| -rw-r--r-- | clang/lib/CodeGen/CoverageMappingGen.h | 12 | ||||
| -rw-r--r-- | clang/lib/Driver/ToolChains/Clang.cpp | 11 |
10 files changed, 868 insertions, 70 deletions
diff --git a/clang/lib/CodeGen/CGClass.cpp b/clang/lib/CodeGen/CGClass.cpp index d18f186..3431938 100644 --- a/clang/lib/CodeGen/CGClass.cpp +++ b/clang/lib/CodeGen/CGClass.cpp @@ -856,6 +856,7 @@ void CodeGenFunction::EmitConstructorBody(FunctionArgList &Args) { EnterCXXTryStmt(*cast<CXXTryStmt>(Body), true); incrementProfileCounter(Body); + maybeCreateMCDCCondBitmap(); RunCleanupsScope RunCleanups(*this); @@ -1444,8 +1445,10 @@ void CodeGenFunction::EmitDestructorBody(FunctionArgList &Args) { } Stmt *Body = Dtor->getBody(); - if (Body) + if (Body) { incrementProfileCounter(Body); + maybeCreateMCDCCondBitmap(); + } // The call to operator delete in a deleting destructor happens // outside of the function-try-block, which means it's always @@ -1548,6 +1551,7 @@ void CodeGenFunction::emitImplicitAssignmentOperatorBody(FunctionArgList &Args) LexicalScope Scope(*this, RootCS->getSourceRange()); incrementProfileCounter(RootCS); + maybeCreateMCDCCondBitmap(); AssignmentMemcpyizer AM(*this, AssignOp, Args); for (auto *I : RootCS->body()) AM.emitAssignment(I); diff --git a/clang/lib/CodeGen/CGExprScalar.cpp b/clang/lib/CodeGen/CGExprScalar.cpp index d2c4c7e..9ec1851 100644 --- a/clang/lib/CodeGen/CGExprScalar.cpp +++ b/clang/lib/CodeGen/CGExprScalar.cpp @@ -4564,6 +4564,12 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { if (LHSCondVal) { // If we have 1 && X, just emit X. CGF.incrementProfileCounter(E); + // If the top of the logical operator nest, reset the MCDC temp to 0. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeResetMCDCCondBitmap(E); + + CGF.MCDCLogOpStack.push_back(E); + Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS()); // If we're generating for profiling or coverage, generate a branch to a @@ -4572,6 +4578,7 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { // "FalseBlock" after the increment is done. if (InstrumentRegions && CodeGenFunction::isInstrumentedCondition(E->getRHS())) { + CGF.maybeUpdateMCDCCondBitmap(E->getRHS(), RHSCond); llvm::BasicBlock *FBlock = CGF.createBasicBlock("land.end"); llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt"); Builder.CreateCondBr(RHSCond, RHSBlockCnt, FBlock); @@ -4581,6 +4588,11 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { CGF.EmitBlock(FBlock); } + CGF.MCDCLogOpStack.pop_back(); + // If the top of the logical operator nest, update the MCDC bitmap. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeUpdateMCDCTestVectorBitmap(E); + // ZExt result to int or bool. return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "land.ext"); } @@ -4590,6 +4602,12 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { return llvm::Constant::getNullValue(ResTy); } + // If the top of the logical operator nest, reset the MCDC temp to 0. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeResetMCDCCondBitmap(E); + + CGF.MCDCLogOpStack.push_back(E); + llvm::BasicBlock *ContBlock = CGF.createBasicBlock("land.end"); llvm::BasicBlock *RHSBlock = CGF.createBasicBlock("land.rhs"); @@ -4622,6 +4640,7 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { // condition coverage. if (InstrumentRegions && CodeGenFunction::isInstrumentedCondition(E->getRHS())) { + CGF.maybeUpdateMCDCCondBitmap(E->getRHS(), RHSCond); llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("land.rhscnt"); Builder.CreateCondBr(RHSCond, RHSBlockCnt, ContBlock); CGF.EmitBlock(RHSBlockCnt); @@ -4639,6 +4658,11 @@ Value *ScalarExprEmitter::VisitBinLAnd(const BinaryOperator *E) { // Insert an entry into the phi node for the edge with the value of RHSCond. PN->addIncoming(RHSCond, RHSBlock); + CGF.MCDCLogOpStack.pop_back(); + // If the top of the logical operator nest, update the MCDC bitmap. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeUpdateMCDCTestVectorBitmap(E); + // Artificial location to preserve the scope information { auto NL = ApplyDebugLocation::CreateArtificial(CGF); @@ -4680,6 +4704,12 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { if (!LHSCondVal) { // If we have 0 || X, just emit X. CGF.incrementProfileCounter(E); + // If the top of the logical operator nest, reset the MCDC temp to 0. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeResetMCDCCondBitmap(E); + + CGF.MCDCLogOpStack.push_back(E); + Value *RHSCond = CGF.EvaluateExprAsBool(E->getRHS()); // If we're generating for profiling or coverage, generate a branch to a @@ -4688,6 +4718,7 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { // "FalseBlock" after the increment is done. if (InstrumentRegions && CodeGenFunction::isInstrumentedCondition(E->getRHS())) { + CGF.maybeUpdateMCDCCondBitmap(E->getRHS(), RHSCond); llvm::BasicBlock *FBlock = CGF.createBasicBlock("lor.end"); llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt"); Builder.CreateCondBr(RHSCond, FBlock, RHSBlockCnt); @@ -4697,6 +4728,11 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { CGF.EmitBlock(FBlock); } + CGF.MCDCLogOpStack.pop_back(); + // If the top of the logical operator nest, update the MCDC bitmap. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeUpdateMCDCTestVectorBitmap(E); + // ZExt result to int or bool. return Builder.CreateZExtOrBitCast(RHSCond, ResTy, "lor.ext"); } @@ -4706,6 +4742,12 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { return llvm::ConstantInt::get(ResTy, 1); } + // If the top of the logical operator nest, reset the MCDC temp to 0. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeResetMCDCCondBitmap(E); + + CGF.MCDCLogOpStack.push_back(E); + llvm::BasicBlock *ContBlock = CGF.createBasicBlock("lor.end"); llvm::BasicBlock *RHSBlock = CGF.createBasicBlock("lor.rhs"); @@ -4742,6 +4784,7 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { // condition coverage. if (InstrumentRegions && CodeGenFunction::isInstrumentedCondition(E->getRHS())) { + CGF.maybeUpdateMCDCCondBitmap(E->getRHS(), RHSCond); llvm::BasicBlock *RHSBlockCnt = CGF.createBasicBlock("lor.rhscnt"); Builder.CreateCondBr(RHSCond, ContBlock, RHSBlockCnt); CGF.EmitBlock(RHSBlockCnt); @@ -4755,6 +4798,11 @@ Value *ScalarExprEmitter::VisitBinLOr(const BinaryOperator *E) { CGF.EmitBlock(ContBlock); PN->addIncoming(RHSCond, RHSBlock); + CGF.MCDCLogOpStack.pop_back(); + // If the top of the logical operator nest, update the MCDC bitmap. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeUpdateMCDCTestVectorBitmap(E); + // ZExt result to int. return Builder.CreateZExtOrBitCast(PN, ResTy, "lor.ext"); } @@ -4899,6 +4947,10 @@ VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { return Builder.CreateSelect(CondV, LHS, RHS, "cond"); } + // If the top of the logical operator nest, reset the MCDC temp to 0. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeResetMCDCCondBitmap(condExpr); + llvm::BasicBlock *LHSBlock = CGF.createBasicBlock("cond.true"); llvm::BasicBlock *RHSBlock = CGF.createBasicBlock("cond.false"); llvm::BasicBlock *ContBlock = CGF.createBasicBlock("cond.end"); @@ -4934,6 +4986,11 @@ VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { llvm::PHINode *PN = Builder.CreatePHI(LHS->getType(), 2, "cond"); PN->addIncoming(LHS, LHSBlock); PN->addIncoming(RHS, RHSBlock); + + // If the top of the logical operator nest, update the MCDC bitmap. + if (CGF.MCDCLogOpStack.empty()) + CGF.maybeUpdateMCDCTestVectorBitmap(condExpr); + return PN; } diff --git a/clang/lib/CodeGen/CGStmt.cpp b/clang/lib/CodeGen/CGStmt.cpp index 0f79a2e..b89017d 100644 --- a/clang/lib/CodeGen/CGStmt.cpp +++ b/clang/lib/CodeGen/CGStmt.cpp @@ -837,7 +837,19 @@ void CodeGenFunction::EmitIfStmt(const IfStmt &S) { if (!ThenCount && !getCurrentProfileCount() && CGM.getCodeGenOpts().OptimizationLevel) LH = Stmt::getLikelihood(S.getThen(), S.getElse()); - EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, ThenCount, LH); + + // When measuring MC/DC, always fully evaluate the condition up front using + // EvaluateExprAsBool() so that the test vector bitmap can be updated prior to + // executing the body of the if.then or if.else. This is useful for when + // there is a 'return' within the body, but this is particularly beneficial + // when one if-stmt is nested within another if-stmt so that all of the MC/DC + // updates are kept linear and consistent. + if (!CGM.getCodeGenOpts().MCDCCoverage) + EmitBranchOnBoolExpr(S.getCond(), ThenBlock, ElseBlock, ThenCount, LH); + else { + llvm::Value *BoolCondVal = EvaluateExprAsBool(S.getCond()); + Builder.CreateCondBr(BoolCondVal, ThenBlock, ElseBlock); + } // Emit the 'then' code. EmitBlock(ThenBlock); diff --git a/clang/lib/CodeGen/CodeGenFunction.cpp b/clang/lib/CodeGen/CodeGenFunction.cpp index 2199d7b..2673e4a 100644 --- a/clang/lib/CodeGen/CodeGenFunction.cpp +++ b/clang/lib/CodeGen/CodeGenFunction.cpp @@ -1256,6 +1256,7 @@ void CodeGenFunction::StartFunction(GlobalDecl GD, QualType RetTy, void CodeGenFunction::EmitFunctionBody(const Stmt *Body) { incrementProfileCounter(Body); + maybeCreateMCDCCondBitmap(); if (const CompoundStmt *S = dyn_cast<CompoundStmt>(Body)) EmitCompoundStmtWithoutScope(*S); else @@ -1601,6 +1602,13 @@ bool CodeGenFunction::mightAddDeclToScope(const Stmt *S) { bool CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond, bool &ResultBool, bool AllowLabels) { + // If MC/DC is enabled, disable folding so that we can instrument all + // conditions to yield complete test vectors. We still keep track of + // folded conditions during region mapping and visualization. + if (!AllowLabels && CGM.getCodeGenOpts().hasProfileClangInstr() && + CGM.getCodeGenOpts().MCDCCoverage) + return false; + llvm::APSInt ResultInt; if (!ConstantFoldsToSimpleInteger(Cond, ResultInt, AllowLabels)) return false; @@ -1629,16 +1637,20 @@ bool CodeGenFunction::ConstantFoldsToSimpleInteger(const Expr *Cond, return true; } +/// Strip parentheses and simplistic logical-NOT operators. +const Expr *CodeGenFunction::stripCond(const Expr *C) { + while (const UnaryOperator *Op = dyn_cast<UnaryOperator>(C->IgnoreParens())) { + if (Op->getOpcode() != UO_LNot) + break; + C = Op->getSubExpr(); + } + return C->IgnoreParens(); +} + /// Determine whether the given condition is an instrumentable condition /// (i.e. no "&&" or "||"). bool CodeGenFunction::isInstrumentedCondition(const Expr *C) { - // Bypass simplistic logical-NOT operator before determining whether the - // condition contains any other logical operator. - if (const UnaryOperator *UnOp = dyn_cast<UnaryOperator>(C->IgnoreParens())) - if (UnOp->getOpcode() == UO_LNot) - C = UnOp->getSubExpr(); - - const BinaryOperator *BOp = dyn_cast<BinaryOperator>(C->IgnoreParens()); + const BinaryOperator *BOp = dyn_cast<BinaryOperator>(stripCond(C)); return (!BOp || !BOp->isLogicalOp()); } @@ -1717,17 +1729,19 @@ void CodeGenFunction::EmitBranchToCounterBlock( /// statement) to the specified blocks. Based on the condition, this might try /// to simplify the codegen of the conditional based on the branch. /// \param LH The value of the likelihood attribute on the True branch. -void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, - llvm::BasicBlock *TrueBlock, - llvm::BasicBlock *FalseBlock, - uint64_t TrueCount, - Stmt::Likelihood LH) { +/// \param ConditionalOp Used by MC/DC code coverage to track the result of the +/// ConditionalOperator (ternary) through a recursive call for the operator's +/// LHS and RHS nodes. +void CodeGenFunction::EmitBranchOnBoolExpr( + const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock, + uint64_t TrueCount, Stmt::Likelihood LH, const Expr *ConditionalOp) { Cond = Cond->IgnoreParens(); if (const BinaryOperator *CondBOp = dyn_cast<BinaryOperator>(Cond)) { - // Handle X && Y in a condition. if (CondBOp->getOpcode() == BO_LAnd) { + MCDCLogOpStack.push_back(CondBOp); + // If we have "1 && X", simplify the code. "0 && X" would have constant // folded if the case was simple enough. bool ConstantBool = false; @@ -1735,8 +1749,10 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, ConstantBool) { // br(1 && X) -> br(X). incrementProfileCounter(CondBOp); - return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock, - FalseBlock, TrueCount, LH); + EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock, + FalseBlock, TrueCount, LH); + MCDCLogOpStack.pop_back(); + return; } // If we have "X && 1", simplify the code to use an uncond branch. @@ -1744,8 +1760,10 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) && ConstantBool) { // br(X && 1) -> br(X). - return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LAnd, TrueBlock, - FalseBlock, TrueCount, LH, CondBOp); + EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LAnd, TrueBlock, + FalseBlock, TrueCount, LH, CondBOp); + MCDCLogOpStack.pop_back(); + return; } // Emit the LHS as a conditional. If the LHS conditional is false, we @@ -1774,11 +1792,13 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LAnd, TrueBlock, FalseBlock, TrueCount, LH); eval.end(*this); - + MCDCLogOpStack.pop_back(); return; } if (CondBOp->getOpcode() == BO_LOr) { + MCDCLogOpStack.push_back(CondBOp); + // If we have "0 || X", simplify the code. "1 || X" would have constant // folded if the case was simple enough. bool ConstantBool = false; @@ -1786,8 +1806,10 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, !ConstantBool) { // br(0 || X) -> br(X). incrementProfileCounter(CondBOp); - return EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock, - FalseBlock, TrueCount, LH); + EmitBranchToCounterBlock(CondBOp->getRHS(), BO_LOr, TrueBlock, + FalseBlock, TrueCount, LH); + MCDCLogOpStack.pop_back(); + return; } // If we have "X || 0", simplify the code to use an uncond branch. @@ -1795,10 +1817,11 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, if (ConstantFoldsToSimpleInteger(CondBOp->getRHS(), ConstantBool) && !ConstantBool) { // br(X || 0) -> br(X). - return EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LOr, TrueBlock, - FalseBlock, TrueCount, LH, CondBOp); + EmitBranchToCounterBlock(CondBOp->getLHS(), BO_LOr, TrueBlock, + FalseBlock, TrueCount, LH, CondBOp); + MCDCLogOpStack.pop_back(); + return; } - // Emit the LHS as a conditional. If the LHS conditional is true, we // want to jump to the TrueBlock. llvm::BasicBlock *LHSFalse = createBasicBlock("lor.lhs.false"); @@ -1829,14 +1852,20 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, RHSCount, LH); eval.end(*this); - + MCDCLogOpStack.pop_back(); return; } } if (const UnaryOperator *CondUOp = dyn_cast<UnaryOperator>(Cond)) { // br(!x, t, f) -> br(x, f, t) - if (CondUOp->getOpcode() == UO_LNot) { + // Avoid doing this optimization when instrumenting a condition for MC/DC. + // LNot is taken as part of the condition for simplicity, and changing its + // sense negatively impacts test vector tracking. + bool MCDCCondition = CGM.getCodeGenOpts().hasProfileClangInstr() && + CGM.getCodeGenOpts().MCDCCoverage && + isInstrumentedCondition(Cond); + if (CondUOp->getOpcode() == UO_LNot && !MCDCCondition) { // Negate the count. uint64_t FalseCount = getCurrentProfileCount() - TrueCount; // The values of the enum are chosen to make this negation possible. @@ -1876,14 +1905,14 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, { ApplyDebugLocation DL(*this, Cond); EmitBranchOnBoolExpr(CondOp->getLHS(), TrueBlock, FalseBlock, - LHSScaledTrueCount, LH); + LHSScaledTrueCount, LH, CondOp); } cond.end(*this); cond.begin(*this); EmitBlock(RHSBlock); EmitBranchOnBoolExpr(CondOp->getRHS(), TrueBlock, FalseBlock, - TrueCount - LHSScaledTrueCount, LH); + TrueCount - LHSScaledTrueCount, LH, CondOp); cond.end(*this); return; @@ -1906,6 +1935,21 @@ void CodeGenFunction::EmitBranchOnBoolExpr(const Expr *Cond, CondV = EvaluateExprAsBool(Cond); } + // If not at the top of the logical operator nest, update MCDC temp with the + // boolean result of the evaluated condition. + if (!MCDCLogOpStack.empty()) { + const Expr *MCDCBaseExpr = Cond; + // When a nested ConditionalOperator (ternary) is encountered in a boolean + // expression, MC/DC tracks the result of the ternary, and this is tied to + // the ConditionalOperator expression and not the ternary's LHS or RHS. If + // this is the case, the ConditionalOperator expression is passed through + // the ConditionalOp parameter and then used as the MCDC base expression. + if (ConditionalOp) + MCDCBaseExpr = ConditionalOp; + + maybeUpdateMCDCCondBitmap(MCDCBaseExpr, CondV); + } + llvm::MDNode *Weights = nullptr; llvm::MDNode *Unpredictable = nullptr; diff --git a/clang/lib/CodeGen/CodeGenFunction.h b/clang/lib/CodeGen/CodeGenFunction.h index 751d811..07c7678 100644 --- a/clang/lib/CodeGen/CodeGenFunction.h +++ b/clang/lib/CodeGen/CodeGenFunction.h @@ -287,6 +287,9 @@ public: /// nest would extend. SmallVector<llvm::CanonicalLoopInfo *, 4> OMPLoopNestStack; + /// Stack to track the Logical Operator recursion nest for MC/DC. + SmallVector<const BinaryOperator *, 16> MCDCLogOpStack; + /// Number of nested loop to be consumed by the last surrounding /// loop-associated directive. int ExpectedOMPLoopDepth = 0; @@ -1521,6 +1524,9 @@ private: CodeGenPGO PGO; + /// Bitmap used by MC/DC to track condition outcomes of a boolean expression. + Address MCDCCondBitmapAddr = Address::invalid(); + /// Calculate branch weights appropriate for PGO data llvm::MDNode *createProfileWeights(uint64_t TrueCount, uint64_t FalseCount) const; @@ -1539,6 +1545,52 @@ public: PGO.setCurrentStmt(S); } + bool isMCDCCoverageEnabled() const { + return (CGM.getCodeGenOpts().hasProfileClangInstr() && + CGM.getCodeGenOpts().MCDCCoverage && + !CurFn->hasFnAttribute(llvm::Attribute::NoProfile)); + } + + /// Allocate a temp value on the stack that MCDC can use to track condition + /// results. + void maybeCreateMCDCCondBitmap() { + if (isMCDCCoverageEnabled()) { + PGO.emitMCDCParameters(Builder); + MCDCCondBitmapAddr = + CreateIRTemp(getContext().UnsignedIntTy, "mcdc.addr"); + } + } + + bool isBinaryLogicalOp(const Expr *E) const { + const BinaryOperator *BOp = dyn_cast<BinaryOperator>(E->IgnoreParens()); + return (BOp && BOp->isLogicalOp()); + } + + /// Zero-init the MCDC temp value. + void maybeResetMCDCCondBitmap(const Expr *E) { + if (isMCDCCoverageEnabled() && isBinaryLogicalOp(E)) { + PGO.emitMCDCCondBitmapReset(Builder, E, MCDCCondBitmapAddr); + PGO.setCurrentStmt(E); + } + } + + /// Increment the profiler's counter for the given expression by \p StepV. + /// If \p StepV is null, the default increment is 1. + void maybeUpdateMCDCTestVectorBitmap(const Expr *E) { + if (isMCDCCoverageEnabled() && isBinaryLogicalOp(E)) { + PGO.emitMCDCTestVectorBitmapUpdate(Builder, E, MCDCCondBitmapAddr); + PGO.setCurrentStmt(E); + } + } + + /// Update the MCDC temp value with the condition's evaluated result. + void maybeUpdateMCDCCondBitmap(const Expr *E, llvm::Value *Val) { + if (isMCDCCoverageEnabled()) { + PGO.emitMCDCCondBitmapUpdate(Builder, E, MCDCCondBitmapAddr, Val); + PGO.setCurrentStmt(E); + } + } + /// Get the profiler's count for the given statement. uint64_t getProfileCount(const Stmt *S) { return PGO.getStmtCount(S).value_or(0); @@ -4626,6 +4678,9 @@ public: bool ConstantFoldsToSimpleInteger(const Expr *Cond, llvm::APSInt &Result, bool AllowLabels = false); + /// Ignore parentheses and logical-NOT to track conditions consistently. + static const Expr *stripCond(const Expr *C); + /// isInstrumentedCondition - Determine whether the given condition is an /// instrumentable condition (i.e. no "&&" or "||"). static bool isInstrumentedCondition(const Expr *C); @@ -4648,7 +4703,8 @@ public: /// evaluate to true based on PGO data. void EmitBranchOnBoolExpr(const Expr *Cond, llvm::BasicBlock *TrueBlock, llvm::BasicBlock *FalseBlock, uint64_t TrueCount, - Stmt::Likelihood LH = Stmt::LH_None); + Stmt::Likelihood LH = Stmt::LH_None, + const Expr *ConditionalOp = nullptr); /// Given an assignment `*LHS = RHS`, emit a test that checks if \p RHS is /// nonnull, if \p LHS is marked _Nonnull. diff --git a/clang/lib/CodeGen/CodeGenPGO.cpp b/clang/lib/CodeGen/CodeGenPGO.cpp index 81bf8ea..d68844d 100644 --- a/clang/lib/CodeGen/CodeGenPGO.cpp +++ b/clang/lib/CodeGen/CodeGenPGO.cpp @@ -161,13 +161,24 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> { PGOHash Hash; /// The map of statements to counters. llvm::DenseMap<const Stmt *, unsigned> &CounterMap; + /// The next bitmap byte index to assign. + unsigned NextMCDCBitmapIdx; + /// The map of statements to MC/DC bitmap coverage objects. + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap; + /// Maximum number of supported MC/DC conditions in a boolean expression. + unsigned MCDCMaxCond; /// The profile version. uint64_t ProfileVersion; + /// Diagnostics Engine used to report warnings. + DiagnosticsEngine &Diag; MapRegionCounters(PGOHashVersion HashVersion, uint64_t ProfileVersion, - llvm::DenseMap<const Stmt *, unsigned> &CounterMap) + llvm::DenseMap<const Stmt *, unsigned> &CounterMap, + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap, + unsigned MCDCMaxCond, DiagnosticsEngine &Diag) : NextCounter(0), Hash(HashVersion), CounterMap(CounterMap), - ProfileVersion(ProfileVersion) {} + NextMCDCBitmapIdx(0), MCDCBitmapMap(MCDCBitmapMap), + MCDCMaxCond(MCDCMaxCond), ProfileVersion(ProfileVersion), Diag(Diag) {} // Blocks and lambdas are handled as separate functions, so we need not // traverse them in the parent context. @@ -207,15 +218,126 @@ struct MapRegionCounters : public RecursiveASTVisitor<MapRegionCounters> { return Type; } + /// The following stacks are used with dataTraverseStmtPre() and + /// dataTraverseStmtPost() to track the depth of nested logical operators in a + /// boolean expression in a function. The ultimate purpose is to keep track + /// of the number of leaf-level conditions in the boolean expression so that a + /// profile bitmap can be allocated based on that number. + /// + /// The stacks are also used to find error cases and notify the user. A + /// standard logical operator nest for a boolean expression could be in a form + /// similar to this: "x = a && b && c && (d || f)" + unsigned NumCond = 0; + bool SplitNestedLogicalOp = false; + SmallVector<const Stmt *, 16> NonLogOpStack; + SmallVector<const BinaryOperator *, 16> LogOpStack; + + // Hook: dataTraverseStmtPre() is invoked prior to visiting an AST Stmt node. + bool dataTraverseStmtPre(Stmt *S) { + /// If MC/DC is not enabled, MCDCMaxCond will be set to 0. Do nothing. + if (MCDCMaxCond == 0) + return true; + + /// At the top of the logical operator nest, reset the number of conditions. + if (LogOpStack.empty()) + NumCond = 0; + + if (const Expr *E = dyn_cast<Expr>(S)) { + const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens()); + if (BinOp && BinOp->isLogicalOp()) { + /// Check for "split-nested" logical operators. This happens when a new + /// boolean expression logical-op nest is encountered within an existing + /// boolean expression, separated by a non-logical operator. For + /// example, in "x = (a && b && c && foo(d && f))", the "d && f" case + /// starts a new boolean expression that is separated from the other + /// conditions by the operator foo(). Split-nested cases are not + /// supported by MC/DC. + SplitNestedLogicalOp = SplitNestedLogicalOp || !NonLogOpStack.empty(); + + LogOpStack.push_back(BinOp); + return true; + } + } + + /// Keep track of non-logical operators. These are OK as long as we don't + /// encounter a new logical operator after seeing one. + if (!LogOpStack.empty()) + NonLogOpStack.push_back(S); + + return true; + } + + // Hook: dataTraverseStmtPost() is invoked by the AST visitor after visiting + // an AST Stmt node. MC/DC will use it to to signal when the top of a + // logical operation (boolean expression) nest is encountered. + bool dataTraverseStmtPost(Stmt *S) { + /// If MC/DC is not enabled, MCDCMaxCond will be set to 0. Do nothing. + if (MCDCMaxCond == 0) + return true; + + if (const Expr *E = dyn_cast<Expr>(S)) { + const BinaryOperator *BinOp = dyn_cast<BinaryOperator>(E->IgnoreParens()); + if (BinOp && BinOp->isLogicalOp()) { + assert(LogOpStack.back() == BinOp); + LogOpStack.pop_back(); + + /// At the top of logical operator nest: + if (LogOpStack.empty()) { + /// Was the "split-nested" logical operator case encountered? + if (SplitNestedLogicalOp) { + unsigned DiagID = Diag.getCustomDiagID( + DiagnosticsEngine::Warning, + "unsupported MC/DC boolean expression; " + "contains an operation with a nested boolean expression. " + "Expression will not be covered"); + Diag.Report(S->getBeginLoc(), DiagID); + return false; + } + + /// Was the maximum number of conditions encountered? + if (NumCond > MCDCMaxCond) { + unsigned DiagID = Diag.getCustomDiagID( + DiagnosticsEngine::Warning, + "unsupported MC/DC boolean expression; " + "number of conditions (%0) exceeds max (%1). " + "Expression will not be covered"); + Diag.Report(S->getBeginLoc(), DiagID) << NumCond << MCDCMaxCond; + return false; + } + + // Otherwise, allocate the number of bytes required for the bitmap + // based on the number of conditions. Must be at least 1-byte long. + MCDCBitmapMap[BinOp] = NextMCDCBitmapIdx; + unsigned SizeInBits = std::max<unsigned>(1L << NumCond, CHAR_BIT); + NextMCDCBitmapIdx += SizeInBits / CHAR_BIT; + } + return true; + } + } + + if (!LogOpStack.empty()) + NonLogOpStack.pop_back(); + + return true; + } + /// The RHS of all logical operators gets a fresh counter in order to count /// how many times the RHS evaluates to true or false, depending on the /// semantics of the operator. This is only valid for ">= v7" of the profile - /// version so that we facilitate backward compatibility. + /// version so that we facilitate backward compatibility. In addition, in + /// order to use MC/DC, count the number of total LHS and RHS conditions. bool VisitBinaryOperator(BinaryOperator *S) { - if (ProfileVersion >= llvm::IndexedInstrProf::Version7) - if (S->isLogicalOp() && - CodeGenFunction::isInstrumentedCondition(S->getRHS())) - CounterMap[S->getRHS()] = NextCounter++; + if (S->isLogicalOp()) { + if (CodeGenFunction::isInstrumentedCondition(S->getLHS())) + NumCond++; + + if (CodeGenFunction::isInstrumentedCondition(S->getRHS())) { + if (ProfileVersion >= llvm::IndexedInstrProf::Version7) + CounterMap[S->getRHS()] = NextCounter++; + + NumCond++; + } + } return Base::VisitBinaryOperator(S); } @@ -851,8 +973,22 @@ void CodeGenPGO::mapRegionCounters(const Decl *D) { ProfileVersion = PGOReader->getVersion(); } + // If MC/DC is enabled, set the MaxConditions to a preset value. Otherwise, + // set it to zero. This value impacts the number of conditions accepted in a + // given boolean expression, which impacts the size of the bitmap used to + // track test vector execution for that boolean expression. Because the + // bitmap scales exponentially (2^n) based on the number of conditions seen, + // the maximum value is hard-coded at 6 conditions, which is more than enough + // for most embedded applications. Setting a maximum value prevents the + // bitmap footprint from growing too large without the user's knowledge. In + // the future, this value could be adjusted with a command-line option. + unsigned MCDCMaxConditions = (CGM.getCodeGenOpts().MCDCCoverage) ? 6 : 0; + RegionCounterMap.reset(new llvm::DenseMap<const Stmt *, unsigned>); - MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap); + RegionMCDCBitmapMap.reset(new llvm::DenseMap<const Stmt *, unsigned>); + MapRegionCounters Walker(HashVersion, ProfileVersion, *RegionCounterMap, + *RegionMCDCBitmapMap, MCDCMaxConditions, + CGM.getDiags()); if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(D)) Walker.TraverseDecl(const_cast<FunctionDecl *>(FD)); else if (const ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(D)) @@ -863,6 +999,7 @@ void CodeGenPGO::mapRegionCounters(const Decl *D) { Walker.TraverseDecl(const_cast<CapturedDecl *>(CD)); assert(Walker.NextCounter > 0 && "no entry counter mapped for decl"); NumRegionCounters = Walker.NextCounter; + MCDCBitmapBytes = Walker.NextMCDCBitmapIdx; FunctionHash = Walker.Hash.finalize(); } @@ -894,9 +1031,11 @@ void CodeGenPGO::emitCounterRegionMapping(const Decl *D) { std::string CoverageMapping; llvm::raw_string_ostream OS(CoverageMapping); - CoverageMappingGen MappingGen(*CGM.getCoverageMapping(), - CGM.getContext().getSourceManager(), - CGM.getLangOpts(), RegionCounterMap.get()); + RegionCondIDMap.reset(new llvm::DenseMap<const Stmt *, unsigned>); + CoverageMappingGen MappingGen( + *CGM.getCoverageMapping(), CGM.getContext().getSourceManager(), + CGM.getLangOpts(), RegionCounterMap.get(), RegionMCDCBitmapMap.get(), + RegionCondIDMap.get()); MappingGen.emitCounterMapping(D, OS); OS.flush(); @@ -972,6 +1111,108 @@ void CodeGenPGO::emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S, ArrayRef(Args)); } +bool CodeGenPGO::canEmitMCDCCoverage(const CGBuilderTy &Builder) { + return (CGM.getCodeGenOpts().hasProfileClangInstr() && + CGM.getCodeGenOpts().MCDCCoverage && Builder.GetInsertBlock()); +} + +void CodeGenPGO::emitMCDCParameters(CGBuilderTy &Builder) { + if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap) + return; + + auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext()); + + // Emit intrinsic representing MCDC bitmap parameters at function entry. + // This is used by the instrumentation pass, but it isn't actually lowered to + // anything. + llvm::Value *Args[3] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy), + Builder.getInt64(FunctionHash), + Builder.getInt32(MCDCBitmapBytes)}; + Builder.CreateCall( + CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_parameters), Args); +} + +void CodeGenPGO::emitMCDCTestVectorBitmapUpdate(CGBuilderTy &Builder, + const Expr *S, + Address MCDCCondBitmapAddr) { + if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap) + return; + + S = S->IgnoreParens(); + + auto ExprMCDCBitmapMapIterator = RegionMCDCBitmapMap->find(S); + if (ExprMCDCBitmapMapIterator == RegionMCDCBitmapMap->end()) + return; + + // Extract the ID of the global bitmap associated with this expression. + unsigned MCDCTestVectorBitmapID = ExprMCDCBitmapMapIterator->second; + auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext()); + + // Emit intrinsic responsible for updating the global bitmap corresponding to + // a boolean expression. The index being set is based on the value loaded + // from a pointer to a dedicated temporary value on the stack that is itself + // updated via emitMCDCCondBitmapReset() and emitMCDCCondBitmapUpdate(). The + // index represents an executed test vector. + llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy), + Builder.getInt64(FunctionHash), + Builder.getInt32(MCDCBitmapBytes), + Builder.getInt32(MCDCTestVectorBitmapID), + MCDCCondBitmapAddr.getPointer()}; + Builder.CreateCall( + CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_tvbitmap_update), Args); +} + +void CodeGenPGO::emitMCDCCondBitmapReset(CGBuilderTy &Builder, const Expr *S, + Address MCDCCondBitmapAddr) { + if (!canEmitMCDCCoverage(Builder) || !RegionMCDCBitmapMap) + return; + + S = S->IgnoreParens(); + + if (RegionMCDCBitmapMap->find(S) == RegionMCDCBitmapMap->end()) + return; + + // Emit intrinsic that resets a dedicated temporary value on the stack to 0. + Builder.CreateStore(Builder.getInt32(0), MCDCCondBitmapAddr); +} + +void CodeGenPGO::emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S, + Address MCDCCondBitmapAddr, + llvm::Value *Val) { + if (!canEmitMCDCCoverage(Builder) || !RegionCondIDMap) + return; + + // 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. + S = CodeGenFunction::stripCond(S); + + auto ExprMCDCConditionIDMapIterator = RegionCondIDMap->find(S); + if (ExprMCDCConditionIDMapIterator == RegionCondIDMap->end()) + return; + + // Extract the ID of the condition we are setting in the bitmap. + unsigned CondID = ExprMCDCConditionIDMapIterator->second; + assert(CondID > 0 && "Condition has no ID!"); + + auto *I8PtrTy = llvm::PointerType::getUnqual(CGM.getLLVMContext()); + + // Emit intrinsic that updates a dedicated temporary value on the stack after + // a condition is evaluated. After the set of conditions has been updated, + // the resulting value is used to update the boolean expression's bitmap. + llvm::Value *Args[5] = {llvm::ConstantExpr::getBitCast(FuncNameVar, I8PtrTy), + Builder.getInt64(FunctionHash), + Builder.getInt32(CondID - 1), + MCDCCondBitmapAddr.getPointer(), Val}; + Builder.CreateCall( + CGM.getIntrinsic(llvm::Intrinsic::instrprof_mcdc_condbitmap_update), + Args); +} + void CodeGenPGO::setValueProfilingFlag(llvm::Module &M) { if (CGM.getCodeGenOpts().hasProfileClangInstr()) M.addModuleFlag(llvm::Module::Warning, "EnableValueProfiling", diff --git a/clang/lib/CodeGen/CodeGenPGO.h b/clang/lib/CodeGen/CodeGenPGO.h index 392ec5a..6596b6c 100644 --- a/clang/lib/CodeGen/CodeGenPGO.h +++ b/clang/lib/CodeGen/CodeGenPGO.h @@ -33,8 +33,11 @@ private: std::array <unsigned, llvm::IPVK_Last + 1> NumValueSites; unsigned NumRegionCounters; + unsigned MCDCBitmapBytes; uint64_t FunctionHash; std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionCounterMap; + std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionMCDCBitmapMap; + std::unique_ptr<llvm::DenseMap<const Stmt *, unsigned>> RegionCondIDMap; std::unique_ptr<llvm::DenseMap<const Stmt *, uint64_t>> StmtCountMap; std::unique_ptr<llvm::InstrProfRecord> ProfRecord; std::vector<uint64_t> RegionCounts; @@ -43,7 +46,8 @@ private: public: CodeGenPGO(CodeGenModule &CGModule) : CGM(CGModule), FuncNameVar(nullptr), NumValueSites({{0}}), - NumRegionCounters(0), FunctionHash(0), CurrentRegionCount(0) {} + NumRegionCounters(0), MCDCBitmapBytes(0), FunctionHash(0), + CurrentRegionCount(0) {} /// Whether or not we have PGO region data for the current function. This is /// false both when we have no data at all and when our data has been @@ -103,10 +107,18 @@ private: bool IsInMainFile); bool skipRegionMappingForDecl(const Decl *D); void emitCounterRegionMapping(const Decl *D); + bool canEmitMCDCCoverage(const CGBuilderTy &Builder); public: void emitCounterIncrement(CGBuilderTy &Builder, const Stmt *S, llvm::Value *StepV); + void emitMCDCTestVectorBitmapUpdate(CGBuilderTy &Builder, const Expr *S, + Address MCDCCondBitmapAddr); + void emitMCDCParameters(CGBuilderTy &Builder); + void emitMCDCCondBitmapReset(CGBuilderTy &Builder, const Expr *S, + Address MCDCCondBitmapAddr); + void emitMCDCCondBitmapUpdate(CGBuilderTy &Builder, const Expr *S, + Address MCDCCondBitmapAddr, llvm::Value *Val); /// Return the region count for the counter at the given index. uint64_t getRegionCount(const Stmt *S) { diff --git a/clang/lib/CodeGen/CoverageMappingGen.cpp b/clang/lib/CodeGen/CoverageMappingGen.cpp index 56411e2..bf22738 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.cpp +++ b/clang/lib/CodeGen/CoverageMappingGen.cpp @@ -95,6 +95,8 @@ void CoverageSourceInfo::updateNextTokLoc(SourceLocation Loc) { } namespace { +using MCDCConditionID = CounterMappingRegion::MCDCConditionID; +using MCDCParameters = CounterMappingRegion::MCDCParameters; /// A region of source code that can be mapped to a counter. class SourceMappingRegion { @@ -104,6 +106,9 @@ class SourceMappingRegion { /// Secondary Counter used for Branch Regions for "False" branches. std::optional<Counter> FalseCount; + /// Parameters used for Modified Condition/Decision Coverage + MCDCParameters MCDCParams; + /// The region's starting location. std::optional<SourceLocation> LocStart; @@ -122,11 +127,18 @@ public: } SourceMappingRegion(Counter Count, std::optional<Counter> FalseCount, + MCDCParameters MCDCParams, std::optional<SourceLocation> LocStart, std::optional<SourceLocation> LocEnd, bool GapRegion = false) - : Count(Count), FalseCount(FalseCount), LocStart(LocStart), - LocEnd(LocEnd), GapRegion(GapRegion) {} + : Count(Count), FalseCount(FalseCount), MCDCParams(MCDCParams), + LocStart(LocStart), LocEnd(LocEnd), GapRegion(GapRegion) {} + + SourceMappingRegion(MCDCParameters MCDCParams, + std::optional<SourceLocation> LocStart, + std::optional<SourceLocation> LocEnd) + : MCDCParams(MCDCParams), LocStart(LocStart), LocEnd(LocEnd), + GapRegion(false) {} const Counter &getCounter() const { return Count; } @@ -163,6 +175,10 @@ public: void setGap(bool Gap) { GapRegion = Gap; } bool isBranch() const { return FalseCount.has_value(); } + + bool isMCDCDecision() const { return MCDCParams.NumConditions != 0; } + + const MCDCParameters &getMCDCParams() const { return MCDCParams; } }; /// Spelling locations for the start and end of a source region. @@ -454,8 +470,13 @@ public: 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)); + Region.getCounter(), Region.getFalseCounter(), + Region.getMCDCParams(), *CovFileID, SR.LineStart, SR.ColumnStart, + SR.LineEnd, SR.ColumnEnd)); + } else if (Region.isMCDCDecision()) { + MappingRegions.push_back(CounterMappingRegion::makeDecisionRegion( + Region.getMCDCParams(), *CovFileID, SR.LineStart, SR.ColumnStart, + SR.LineEnd, SR.ColumnEnd)); } else { MappingRegions.push_back(CounterMappingRegion::makeRegion( Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart, @@ -542,6 +563,239 @@ struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder { } }; +/// 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 stacks + /// 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<MCDCConditionID> AndRHS; + llvm::SmallVector<MCDCConditionID> OrRHS; + llvm::SmallVector<const BinaryOperator *> NestLevel; + llvm::DenseMap<const Stmt *, MCDCConditionID> &CondIDs; + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap; + MCDCConditionID NextID = 1; + bool NotMapped = false; + + /// Is this a logical-AND operation? + bool isLAnd(const BinaryOperator *E) const { + return E->getOpcode() == BO_LAnd; + } + + /// Push an ID onto the corresponding RHS stack. + void pushRHS(const BinaryOperator *E) { + llvm::SmallVector<MCDCConditionID> &rhs = isLAnd(E) ? AndRHS : OrRHS; + rhs.push_back(CondIDs[CodeGenFunction::stripCond(E->getRHS())]); + } + + /// Pop an ID from the corresponding RHS stack. + void popRHS(const BinaryOperator *E) { + llvm::SmallVector<MCDCConditionID> &rhs = isLAnd(E) ? AndRHS : OrRHS; + if (!rhs.empty()) + rhs.pop_back(); + } + + /// If the expected ID is on top, pop it off the corresponding RHS stack. + void popRHSifTop(const BinaryOperator *E) { + if (!OrRHS.empty() && CondIDs[E] == OrRHS.back()) + OrRHS.pop_back(); + else if (!AndRHS.empty() && CondIDs[E] == AndRHS.back()) + AndRHS.pop_back(); + } + +public: + MCDCCoverageBuilder(CodeGenModule &CGM, + llvm::DenseMap<const Stmt *, MCDCConditionID> &CondIDMap, + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap) + : CGM(CGM), CondIDs(CondIDMap), MCDCBitmapMap(MCDCBitmapMap) {} + + /// Return the ID of the RHS of the next, upper nest-level logical-OR. + MCDCConditionID getNextLOrCondID() const { + return OrRHS.empty() ? 0 : OrRHS.back(); + } + + /// Return the ID of the RHS of the next, upper nest-level logical-AND. + MCDCConditionID getNextLAndCondID() const { + return AndRHS.empty() ? 0 : AndRHS.back(); + } + + /// Return the ID of a given condition. + MCDCConditionID getCondID(const Expr *Cond) const { + auto I = CondIDs.find(CodeGenFunction::stripCond(Cond)); + if (I == CondIDs.end()) + return 0; + else + return I->second; + } + + /// 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 (NestLevel.empty() && MCDCBitmapMap.find(CodeGenFunction::stripCond( + E)) == MCDCBitmapMap.end()) + NotMapped = true; + + // Push Stmt on 'NestLevel' stack to keep track of nest location. + NestLevel.push_back(E); + + // Don't go any further if we don't need to map condition IDs. + if (NotMapped) + return; + + // If the operator itself has an assigned ID, this means it represents a + // larger subtree. In this case, pop its ID out of the RHS stack and + // assign that ID to its LHS node. Its RHS will receive a new ID. + if (CondIDs.find(CodeGenFunction::stripCond(E)) != CondIDs.end()) { + // If Stmt has an ID, assign its ID to LHS + CondIDs[CodeGenFunction::stripCond(E->getLHS())] = CondIDs[E]; + + // Since the operator's LHS assumes the operator's same ID, pop the + // operator from the RHS stack so that if LHS short-circuits, it won't be + // incorrectly re-used as the node executed next. + popRHSifTop(E); + } else { + // Otherwise, assign ID+1 to LHS. + CondIDs[CodeGenFunction::stripCond(E->getLHS())] = NextID++; + } + + // Assign ID+1 to RHS. + CondIDs[CodeGenFunction::stripCond(E->getRHS())] = NextID++; + + // Push ID of Stmt's RHS so that LHS nodes know about it + pushRHS(E); + } + + /// Pop the binary operator from the next level. If the walk is at the top of + /// the next, assign the total number of conditions. + unsigned popAndReturnCondCount(const BinaryOperator *E) { + if (!CGM.getCodeGenOpts().MCDCCoverage) + return 0; + + unsigned TotalConds = 0; + + // Pop Stmt from 'NestLevel' stack. + assert(NestLevel.back() == E); + NestLevel.pop_back(); + + // Reset state if not doing mapping. + if (NestLevel.empty() && NotMapped) { + NotMapped = false; + return 0; + } + + // Pop RHS ID. + popRHS(E); + + // If at the parent (NestLevel=0), set conds and reset. + if (NestLevel.empty()) { + TotalConds = NextID - 1; + + // Reset ID back to beginning. + NextID = 1; + } + return TotalConds; + } +}; + /// A StmtVisitor that creates coverage mapping regions which map /// from the source code locations to the PGO counters. struct CounterCoverageMappingBuilder @@ -550,8 +804,14 @@ struct CounterCoverageMappingBuilder /// The map of statements to count values. llvm::DenseMap<const Stmt *, unsigned> &CounterMap; + /// The map of statements to bitmap coverage object values. + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap; + /// A stack of currently live regions. - std::vector<SourceMappingRegion> RegionStack; + llvm::SmallVector<SourceMappingRegion> RegionStack; + + /// An object to manage MCDC regions. + MCDCCoverageBuilder MCDCBuilder; CounterExpressionBuilder Builder; @@ -589,6 +849,8 @@ struct CounterCoverageMappingBuilder return Counter::getCounter(CounterMap[S]); } + unsigned getRegionBitmap(const Stmt *S) { return MCDCBitmapMap[S]; } + /// Push a region onto the stack. /// /// Returns the index on the stack where the region was pushed. This can be @@ -596,7 +858,9 @@ struct CounterCoverageMappingBuilder size_t pushRegion(Counter Count, std::optional<SourceLocation> StartLoc = std::nullopt, std::optional<SourceLocation> EndLoc = std::nullopt, - std::optional<Counter> FalseCount = std::nullopt) { + std::optional<Counter> FalseCount = std::nullopt, + MCDCConditionID ID = 0, MCDCConditionID TrueID = 0, + MCDCConditionID FalseID = 0) { if (StartLoc && !FalseCount) { MostRecentLocation = *StartLoc; @@ -615,7 +879,19 @@ struct CounterCoverageMappingBuilder StartLoc = std::nullopt; if (EndLoc && EndLoc->isInvalid()) EndLoc = std::nullopt; - RegionStack.emplace_back(Count, FalseCount, StartLoc, EndLoc); + RegionStack.emplace_back(Count, FalseCount, + MCDCParameters{0, 0, ID, TrueID, FalseID}, + StartLoc, EndLoc); + + return RegionStack.size() - 1; + } + + size_t pushRegion(unsigned BitmapIdx, unsigned Conditions, + std::optional<SourceLocation> StartLoc = std::nullopt, + std::optional<SourceLocation> EndLoc = std::nullopt) { + + RegionStack.emplace_back(MCDCParameters{BitmapIdx, Conditions}, StartLoc, + EndLoc); return RegionStack.size() - 1; } @@ -746,7 +1022,9 @@ 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, + MCDCConditionID ID = 0, MCDCConditionID TrueID = 0, + MCDCConditionID FalseID = 0) { // Check for NULL conditions. if (!C) return; @@ -764,13 +1042,21 @@ 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(), ID, TrueID, FalseID)); 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, ID, + TrueID, FalseID)); } } + /// 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, unsigned BitmapIdx, unsigned Conds) { + popRegions(pushRegion(BitmapIdx, Conds, 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, @@ -851,8 +1137,12 @@ struct CounterCoverageMappingBuilder // we've seen this region. if (StartLocs.insert(Loc).second) { if (I.isBranch()) - SourceRegions.emplace_back(I.getCounter(), I.getFalseCounter(), Loc, - getEndOfFileOrMacro(Loc), I.isBranch()); + SourceRegions.emplace_back( + I.getCounter(), I.getFalseCounter(), + MCDCParameters{0, 0, I.getMCDCParams().ID, + I.getMCDCParams().TrueID, + I.getMCDCParams().FalseID}, + Loc, getEndOfFileOrMacro(Loc), I.isBranch()); else SourceRegions.emplace_back(I.getCounter(), Loc, getEndOfFileOrMacro(Loc)); @@ -971,9 +1261,13 @@ struct CounterCoverageMappingBuilder CounterCoverageMappingBuilder( CoverageMappingModuleGen &CVM, - llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM, - const LangOptions &LangOpts) - : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap) {} + llvm::DenseMap<const Stmt *, unsigned> &CounterMap, + llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap, + llvm::DenseMap<const Stmt *, MCDCConditionID> &CondIDMap, + SourceManager &SM, const LangOptions &LangOpts) + : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap), + MCDCBitmapMap(MCDCBitmapMap), + MCDCBuilder(CVM.getCodeGenModule(), CondIDMap, MCDCBitmapMap) {} /// Write the mapping data to the output stream void write(llvm::raw_ostream &OS) { @@ -1519,6 +1813,9 @@ struct CounterCoverageMappingBuilder } void VisitBinLAnd(const BinaryOperator *E) { + // 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())); @@ -1527,6 +1824,11 @@ struct CounterCoverageMappingBuilder extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); + // Process Binary Operator and create MCDC Decision Region if top-level + unsigned NumConds = 0; + if ((NumConds = MCDCBuilder.popAndReturnCondCount(E))) + createDecisionRegion(E, getRegionBitmap(E), NumConds); + // Extract the RHS's Execution Counter. Counter RHSExecCnt = getRegionCounter(E); @@ -1536,13 +1838,30 @@ struct CounterCoverageMappingBuilder // Extract the Parent Region Counter. Counter ParentCnt = getRegion().getCounter(); + // Extract the MCDC condition IDs (returns 0 if not needed). + MCDCConditionID NextOrID = MCDCBuilder.getNextLOrCondID(); + MCDCConditionID NextAndID = MCDCBuilder.getNextLAndCondID(); + MCDCConditionID LHSid = MCDCBuilder.getCondID(E->getLHS()); + MCDCConditionID RHSid = MCDCBuilder.getCondID(E->getRHS()); + // Create Branch Region around LHS condition. + // MC/DC: For "LHS && RHS" + // - If LHS is TRUE, execution goes to the RHS. + // - If LHS is FALSE, execution goes to the LHS of the next logical-OR. + // If that does not exist, execution exits (ID == 0). createBranchRegion(E->getLHS(), RHSExecCnt, - subtractCounters(ParentCnt, RHSExecCnt)); + subtractCounters(ParentCnt, RHSExecCnt), LHSid, RHSid, + NextOrID); // Create Branch Region around RHS condition. + // MC/DC: For "LHS && RHS" + // - If RHS is TRUE, execution goes to LHS of the next logical-AND. + // If that does not exist, execution exits (ID == 0). + // - If RHS is FALSE, execution goes to the LHS of the next logical-OR. + // If that does not exist, execution exits (ID == 0). createBranchRegion(E->getRHS(), RHSTrueCnt, - subtractCounters(RHSExecCnt, RHSTrueCnt)); + subtractCounters(RHSExecCnt, RHSTrueCnt), RHSid, + NextAndID, NextOrID); } // Determine whether the right side of OR operation need to be visited. @@ -1556,6 +1875,9 @@ struct CounterCoverageMappingBuilder } void VisitBinLOr(const BinaryOperator *E) { + // Keep track of Binary Operator and assign MCDC condition IDs + MCDCBuilder.pushAndAssignIDs(E); + extendRegion(E->getLHS()); Counter OutCount = propagateCounts(getRegion().getCounter(), E->getLHS()); handleFileExit(getEnd(E->getLHS())); @@ -1564,6 +1886,11 @@ struct CounterCoverageMappingBuilder extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); + // Process Binary Operator and create MCDC Decision Region if top-level + unsigned NumConds = 0; + if ((NumConds = MCDCBuilder.popAndReturnCondCount(E))) + createDecisionRegion(E, getRegionBitmap(E), NumConds); + // Extract the RHS's Execution Counter. Counter RHSExecCnt = getRegionCounter(E); @@ -1577,13 +1904,28 @@ struct CounterCoverageMappingBuilder // Extract the Parent Region Counter. Counter ParentCnt = getRegion().getCounter(); + // Extract the MCDC condition IDs (returns 0 if not needed). + MCDCConditionID NextOrID = MCDCBuilder.getNextLOrCondID(); + MCDCConditionID NextAndID = MCDCBuilder.getNextLAndCondID(); + MCDCConditionID LHSid = MCDCBuilder.getCondID(E->getLHS()); + MCDCConditionID RHSid = MCDCBuilder.getCondID(E->getRHS()); + // Create Branch Region around LHS condition. + // MC/DC: For "LHS || RHS" + // - If LHS is TRUE, execution goes to the LHS of the next logical-AND. + // If that does not exist, execution exits (ID == 0). + // - If LHS is FALSE, execution goes to the RHS. createBranchRegion(E->getLHS(), subtractCounters(ParentCnt, RHSExecCnt), - RHSExecCnt); + RHSExecCnt, LHSid, NextAndID, RHSid); // Create Branch Region around RHS condition. + // MC/DC: For "LHS || RHS" + // - If RHS is TRUE, execution goes to LHS of the next logical-AND. + // If that does not exist, execution exits (ID == 0). + // - If RHS is FALSE, execution goes to the LHS of the next logical-OR. + // If that does not exist, execution exits (ID == 0). createBranchRegion(E->getRHS(), subtractCounters(RHSExecCnt, RHSFalseCnt), - RHSFalseCnt); + RHSFalseCnt, RHSid, NextAndID, NextOrID); } void VisitLambdaExpr(const LambdaExpr *LE) { @@ -1633,11 +1975,23 @@ static void dump(llvm::raw_ostream &OS, StringRef FunctionName, 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 (R.Kind == CounterMappingRegion::MCDCDecisionRegion) { + OS << "M:" << R.MCDCParams.BitmapIdx; + OS << ", C:" << R.MCDCParams.NumConditions; + } else { + Ctx.dump(R.Count, OS); + + if (R.Kind == CounterMappingRegion::BranchRegion || + R.Kind == CounterMappingRegion::MCDCBranchRegion) { + OS << ", "; + Ctx.dump(R.FalseCount, OS); + } + } + + if (R.Kind == CounterMappingRegion::MCDCBranchRegion) { + OS << " [" << R.MCDCParams.ID << "," << R.MCDCParams.TrueID; + OS << "," << R.MCDCParams.FalseID << "] "; } if (R.Kind == CounterMappingRegion::ExpansionRegion) @@ -1846,8 +2200,9 @@ unsigned CoverageMappingModuleGen::getFileID(FileEntryRef File) { void CoverageMappingGen::emitCounterMapping(const Decl *D, llvm::raw_ostream &OS) { - assert(CounterMap); - CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts); + assert(CounterMap && MCDCBitmapMap); + CounterCoverageMappingBuilder Walker(CVM, *CounterMap, *MCDCBitmapMap, + *CondIDMap, SM, LangOpts); Walker.VisitDecl(D); Walker.write(OS); } diff --git a/clang/lib/CodeGen/CoverageMappingGen.h b/clang/lib/CodeGen/CoverageMappingGen.h index 77d7c6c..62cea17 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.h +++ b/clang/lib/CodeGen/CoverageMappingGen.h @@ -150,16 +150,22 @@ class CoverageMappingGen { SourceManager &SM; const LangOptions &LangOpts; llvm::DenseMap<const Stmt *, unsigned> *CounterMap; + llvm::DenseMap<const Stmt *, unsigned> *MCDCBitmapMap; + llvm::DenseMap<const Stmt *, unsigned> *CondIDMap; public: CoverageMappingGen(CoverageMappingModuleGen &CVM, SourceManager &SM, const LangOptions &LangOpts) - : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(nullptr) {} + : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(nullptr), + MCDCBitmapMap(nullptr), CondIDMap(nullptr) {} CoverageMappingGen(CoverageMappingModuleGen &CVM, SourceManager &SM, const LangOptions &LangOpts, - llvm::DenseMap<const Stmt *, unsigned> *CounterMap) - : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(CounterMap) {} + llvm::DenseMap<const Stmt *, unsigned> *CounterMap, + llvm::DenseMap<const Stmt *, unsigned> *MCDCBitmapMap, + llvm::DenseMap<const Stmt *, unsigned> *CondIDMap) + : CVM(CVM), SM(SM), LangOpts(LangOpts), CounterMap(CounterMap), + MCDCBitmapMap(MCDCBitmapMap), CondIDMap(CondIDMap) {} /// Emit the coverage mapping data which maps the regions of /// code to counters that will be used to find the execution diff --git a/clang/lib/Driver/ToolChains/Clang.cpp b/clang/lib/Driver/ToolChains/Clang.cpp index acfa119..2d8ef84 100644 --- a/clang/lib/Driver/ToolChains/Clang.cpp +++ b/clang/lib/Driver/ToolChains/Clang.cpp @@ -698,6 +698,17 @@ static void addPGOAndCoverageFlags(const ToolChain &TC, Compilation &C, CmdArgs.push_back("-fcoverage-mapping"); } + if (Args.hasFlag(options::OPT_fmcdc_coverage, options::OPT_fno_mcdc_coverage, + false)) { + if (!Args.hasFlag(options::OPT_fcoverage_mapping, + options::OPT_fno_coverage_mapping, false)) + D.Diag(clang::diag::err_drv_argument_only_allowed_with) + << "-fcoverage-mcdc" + << "-fcoverage-mapping"; + + CmdArgs.push_back("-fcoverage-mcdc"); + } + if (Arg *A = Args.getLastArg(options::OPT_ffile_compilation_dir_EQ, options::OPT_fcoverage_compilation_dir_EQ)) { if (A->getOption().matches(options::OPT_ffile_compilation_dir_EQ)) |