llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: Alan Phipps (evodius96) <details> <summary>Changes</summary> Clean-up of the algorithm that assigns MC/DC True/False control-flow condition IDs when constructing an MC/DC decision region. This patch creates a common API for setting/getting the condition IDs, making the binary logical operator visitor functions much cleaner. This patch also fixes a bug in which the decision which was malformed due to an incorrect calculation of the True/False condition IDs. Previously, this calculation was done as the logical operation stack was being popped, yielding off-by-one errors. This is now done when the logical operation stack is being pushed. --- Full diff: https://github.com/llvm/llvm-project/pull/78202.diff 3 Files Affected: - (modified) clang/lib/CodeGen/CoverageMappingGen.cpp (+82-45) - (modified) clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp (+50) - (modified) llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h (+1-1) ``````````diff diff --git a/clang/lib/CodeGen/CoverageMappingGen.cpp b/clang/lib/CodeGen/CoverageMappingGen.cpp index 916016601a9327..ca7b65e3f4b08d 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.cpp +++ b/clang/lib/CodeGen/CoverageMappingGen.cpp @@ -668,6 +668,8 @@ struct MCDCCoverageBuilder { llvm::SmallVector<const BinaryOperator *> NestLevel; llvm::DenseMap<const Stmt *, MCDCConditionID> &CondIDs; llvm::DenseMap<const Stmt *, unsigned> &MCDCBitmapMap; + llvm::DenseMap<const Stmt *, MCDCConditionID> TrueCondIDs; + llvm::DenseMap<const Stmt *, MCDCConditionID> FalseCondIDs; MCDCConditionID NextID = 1; bool NotMapped = false; @@ -713,6 +715,21 @@ struct MCDCCoverageBuilder { return AndRHS.empty() ? 0 : AndRHS.back(); } + /// Set the given condition's ID. + void setCondID(const Expr *Cond, MCDCConditionID ID) { + CondIDs[CodeGenFunction::stripCond(Cond)] = ID; + } + + /// Set the ID of the next condition when the given condition is True. + void setTrueCondID(const Expr *Cond, MCDCConditionID ID) { + TrueCondIDs[CodeGenFunction::stripCond(Cond)] = ID; + } + + /// Set the ID of the next condition when the given condition is False. + void setFalseCondID(const Expr *Cond, MCDCConditionID ID) { + FalseCondIDs[CodeGenFunction::stripCond(Cond)] = ID; + } + /// Return the ID of a given condition. MCDCConditionID getCondID(const Expr *Cond) const { auto I = CondIDs.find(CodeGenFunction::stripCond(Cond)); @@ -722,6 +739,24 @@ struct MCDCCoverageBuilder { return I->second; } + /// Return the ID of the next condition when the given condition is True. + MCDCConditionID getNextIfTrueCondID(const Expr *Cond) const { + auto I = TrueCondIDs.find(CodeGenFunction::stripCond(Cond)); + if (I == TrueCondIDs.end()) + return 0; + else + return I->second; + } + + /// Return the ID of the next condition when the given condition is False. + MCDCConditionID getNextIfFalseCondID(const Expr *Cond) const { + auto I = FalseCondIDs.find(CodeGenFunction::stripCond(Cond)); + if (I == FalseCondIDs.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. @@ -746,7 +781,7 @@ struct MCDCCoverageBuilder { // assign that ID to its LHS node. Its RHS will receive a new ID. if (CondIDs.contains(CodeGenFunction::stripCond(E))) { // If Stmt has an ID, assign its ID to LHS - CondIDs[CodeGenFunction::stripCond(E->getLHS())] = CondIDs[E]; + setCondID(E->getLHS(), getCondID(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 @@ -754,13 +789,44 @@ struct MCDCCoverageBuilder { popRHSifTop(E); } else { // Otherwise, assign ID+1 to LHS. - CondIDs[CodeGenFunction::stripCond(E->getLHS())] = NextID++; + setCondID(E->getLHS(), NextID++); } // Assign ID+1 to RHS. - CondIDs[CodeGenFunction::stripCond(E->getRHS())] = NextID++; + setCondID(E->getRHS(), NextID++); + + // Assign the True and False condition IDs for the LHS and RHS. + if (isLAnd(E)) { + // 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 LOr. + // If that does not exist, execution exits (ID == 0). + setTrueCondID(E->getLHS(), getCondID(E->getRHS())); + setFalseCondID(E->getLHS(), getNextLOrCondID()); + + // - If RHS is TRUE, execution goes to LHS node of the next LAnd. + // If that does not exist, execution exits (ID == 0). + // - If RHS is FALSE, execution goes to the LHS node of the next LOr. + // If that does not exist, execution exits (ID == 0). + setTrueCondID(E->getRHS(), getNextLAndCondID()); + setFalseCondID(E->getRHS(), getNextLOrCondID()); + } else { + // For logical-OR ("LHS || RHS"): + // - If LHS is TRUE, execution goes to the LHS node of the next LAnd. + // If that does not exist, execution exits (ID == 0). + // - If LHS is FALSE, execution goes to the RHS node. + setTrueCondID(E->getLHS(), getNextLAndCondID()); + setFalseCondID(E->getLHS(), getCondID(E->getRHS())); + + // - If RHS is TRUE, execution goes to LHS node of the next LAnd. + // If that does not exist, execution exits (ID == 0). + // - If RHS is FALSE, execution goes to the LHS node of the next LOr. + // If that does not exist, execution exits (ID == 0). + setTrueCondID(E->getRHS(), getNextLAndCondID()); + setFalseCondID(E->getRHS(), getNextLOrCondID()); + } - // Push ID of Stmt's RHS so that LHS nodes know about it + // Push ID of Stmt's RHS so that LHS nodes know about it. pushRHS(E); } @@ -1022,9 +1088,7 @@ 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, - MCDCConditionID ID = 0, MCDCConditionID TrueID = 0, - MCDCConditionID FalseID = 0) { + void createBranchRegion(const Expr *C, Counter TrueCnt, Counter FalseCnt) { // Check for NULL conditions. if (!C) return; @@ -1034,6 +1098,11 @@ struct CounterCoverageMappingBuilder // function's SourceRegions) because it doesn't apply to any other source // code other than the Condition. if (CodeGenFunction::isInstrumentedCondition(C)) { + // Extract the MCDC condition IDs (returns 0 if not needed). + MCDCConditionID ID = MCDCBuilder.getCondID(C); + MCDCConditionID TrueID = MCDCBuilder.getNextIfTrueCondID(C); + MCDCConditionID FalseID = MCDCBuilder.getNextIfFalseCondID(C); + // 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. @@ -1833,7 +1902,7 @@ struct CounterCoverageMappingBuilder extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); - // Process Binary Operator and create MCDC Decision Region if top-level + // Process Binary Operator and create MCDC Decision Region if top-level. unsigned NumConds = 0; if ((NumConds = MCDCBuilder.popAndReturnCondCount(E))) createDecisionRegion(E, getRegionBitmap(E), NumConds); @@ -1847,30 +1916,13 @@ 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), LHSid, RHSid, - NextOrID); + subtractCounters(ParentCnt, RHSExecCnt)); // 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), RHSid, - NextAndID, NextOrID); + subtractCounters(RHSExecCnt, RHSTrueCnt)); } // Determine whether the right side of OR operation need to be visited. @@ -1895,7 +1947,7 @@ struct CounterCoverageMappingBuilder extendRegion(E->getRHS()); propagateCounts(getRegionCounter(E), E->getRHS()); - // Process Binary Operator and create MCDC Decision Region if top-level + // Process Binary Operator and create MCDC Decision Region if top-level. unsigned NumConds = 0; if ((NumConds = MCDCBuilder.popAndReturnCondCount(E))) createDecisionRegion(E, getRegionBitmap(E), NumConds); @@ -1913,28 +1965,13 @@ 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, LHSid, NextAndID, RHSid); + RHSExecCnt); // 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, RHSid, NextAndID, NextOrID); + RHSFalseCnt); } void VisitLambdaExpr(const LambdaExpr *LE) { diff --git a/clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp b/clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp index 5b13cc3507e96c..b1d32bdd746cb4 100644 --- a/clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp +++ b/clang/test/CoverageMapping/mcdc-logical-stmt-ids-all.cpp @@ -129,3 +129,53 @@ bool func_ternary_or(bool a, bool b, bool c, bool d, bool e, bool f) { // CHECK: Branch,File 0, 122:26 -> 122:27 = (#6 - #7), #7 [4,0,3] // CHECK: Branch,File 0, 122:31 -> 122:32 = (#4 - #5), #5 [3,0,2] // CHECK: Branch,File 0, 122:36 -> 122:37 = (#2 - #3), #3 [2,0,0] + +bool func_if_nested_and_if(bool a, bool b, bool c, bool d, bool e) { + if (a || (b && c) || d || e) + return true; + else + return false; +} + +// CHECK-LABEL: Decision,File 0, 134:7 -> 134:30 = M:0, C:5 +// CHECK-NEXT: Branch,File 0, 134:7 -> 134:8 = (#0 - #6), #6 [1,0,4] +// CHECK: Branch,File 0, 134:13 -> 134:14 = #7, (#6 - #7) [4,5,3] +// CHECK: Branch,File 0, 134:18 -> 134:19 = #8, (#7 - #8) [5,0,3] +// CHECK: Branch,File 0, 134:24 -> 134:25 = (#4 - #5), #5 [3,0,2] +// CHECK: Branch,File 0, 134:29 -> 134:30 = (#2 - #3), #3 [2,0,0] + +bool func_ternary_nested_and_if(bool a, bool b, bool c, bool d, bool e) { + return (a || (b && c) || d || e) ? true : false; +} + +// CHECK-LABEL: Decision,File 0, 148:11 -> 148:34 = M:0, C:5 +// CHECK-NEXT: Branch,File 0, 148:11 -> 148:12 = (#0 - #6), #6 [1,0,4] +// CHECK: Branch,File 0, 148:17 -> 148:18 = #7, (#6 - #7) [4,5,3] +// CHECK: Branch,File 0, 148:22 -> 148:23 = #8, (#7 - #8) [5,0,3] +// CHECK: Branch,File 0, 148:28 -> 148:29 = (#4 - #5), #5 [3,0,2] +// CHECK: Branch,File 0, 148:33 -> 148:34 = (#2 - #3), #3 [2,0,0] + +bool func_if_nested_and_if_2(bool a, bool b, bool c, bool d, bool e) { + if (a || ((b && c) || d) && e) + return true; + else + return false; +} + +// CHECK-LABEL: Decision,File 0, 159:7 -> 159:32 = M:0, C:5 +// CHECK-NEXT: Branch,File 0, 159:7 -> 159:8 = (#0 - #2), #2 [1,0,2] +// CHECK: Branch,File 0, 159:14 -> 159:15 = #7, (#2 - #7) [2,5,4] +// CHECK: Branch,File 0, 159:19 -> 159:20 = #8, (#7 - #8) [5,3,4] +// CHECK: Branch,File 0, 159:25 -> 159:26 = (#5 - #6), #6 [4,3,0] +// CHECK: Branch,File 0, 159:31 -> 159:32 = #4, (#3 - #4) [3,0,0] + +bool func_ternary_nested_and_if_2(bool a, bool b, bool c, bool d, bool e) { + return (a || ((b && c) || d) && e) ? true : false; +} + +// CHECK-LABEL: Decision,File 0, 173:11 -> 173:36 = M:0, C:5 +// CHECK-NEXT: Branch,File 0, 173:11 -> 173:12 = (#0 - #2), #2 [1,0,2] +// CHECK: Branch,File 0, 173:18 -> 173:19 = #7, (#2 - #7) [2,5,4] +// CHECK: Branch,File 0, 173:23 -> 173:24 = #8, (#7 - #8) [5,3,4] +// CHECK: Branch,File 0, 173:29 -> 173:30 = (#5 - #6), #6 [4,3,0] +// CHECK: Branch,File 0, 173:35 -> 173:36 = #4, (#3 - #4) [3,0,0] diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 2757b8cd54a69c..367c884957ff6d 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -298,7 +298,7 @@ struct CounterMappingRegion { unsigned ExpandedFileID, unsigned LineStart, unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind) - : MCDCParams(MCDCParams), ExpandedFileID(ExpandedFileID), + : MCDCParams(MCDCParams), FileID(FileID), ExpandedFileID(ExpandedFileID), LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd), ColumnEnd(ColumnEnd), Kind(Kind) {} `````````` </details> https://github.com/llvm/llvm-project/pull/78202 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
