This patch adds support in gcc+gcov for modified condition/decision coverage (MC/DC) with the -fprofile-conditions flag. MC/DC is a type of test/code coverage, and it is particularly important in the avation and automotive industries for safety-critical applications. In particular, it is required or recommended by: * DO-178C for the most critical software (Level A) in avionics * IEC 61508 for SIL 4 * ISO 26262-6 for ASIL D From the SQLite webpage: Two methods of measuring test coverage were described above: "statement" and "branch" coverage. There are many other test coverage metrics besides these two. Another popular metric is "Modified Condition/Decision Coverage" or MC/DC. Wikipedia defines MC/DC as follows: * Each decision tries every possible outcome. * Each condition in a decision takes on every possible outcome. * Each entry and exit point is invoked. * Each condition in a decision is shown to independently affect the outcome of the decision. In the C programming language where && and || are "short-circuit" operators, MC/DC and branch coverage are very nearly the same thing. The primary difference is in boolean vector tests. One can test for any of several bits in bit-vector and still obtain 100% branch test coverage even though the second element of MC/DC - the requirement that each condition in a decision take on every possible outcome - might not be satisfied. https://sqlite.org/testing.html#mcdc Wahlen, Heimdahl, and De Silva "Efficient Test Coverage Measurement for MC/DC" describes an algorithm for adding instrumentation by carrying over information from the AST, but my algorithm does analysis on the control flow graph. This should make it work for any language gcc supports, although I have only tested it on constructs in C and C++, see testsuite/gcc.misc-tests and testsuite/g++.dg. Like Wahlen et al this implementation uses bitsets to store conditions, which gcov later interprets. This is very fast, but introduces an max limit for the number of terms in a single boolean expression. This limit is the number of bits in a gcov_unsigned_type (which is typedef'd to uint64_t), so for most practical purposes this would be acceptable. limitation can be relaxed with a more sophisticated way of storing and updating bitsets (for example length-encoding). In action it looks pretty similar to the branch coverage. The -g short opt carries no significance, but was chosen because it was an available option with the upper-case free too. gcov --conditions: 3: 17:void fn (int a, int b, int c, int d) { 3: 18: if ((a && (b || c)) && d) conditions covered 5/8 condition 1 not covered (false) condition 2 not covered (true) condition 2 not covered (false) 1: 19: x = 1; -: 20: else 2: 21: x = 2; 3: 22:} gcov --conditions --json-format: "conditions": [ { "not_covered_false": [ 1, 2 ], "count": 8, "covered": 5, "not_covered_true": [ 2 ] } ], C++ destructors will add extra conditionals that are not explicitly present in source code. These are present in the CFG, which means the condition coverage will show them. gcov --conditions -: 5:struct A { 1: 6: explicit A (int x) : v (x) {} 1: 7: operator bool () const { return bool(v); } 1: 8: ~A() {} -: 9: -: 10: int v; -: 11:}; -: 12: 2: 13:void fn (int a, int b) { 2*: 14: x = a && A(b); conditions covered 2/4 condition 0 not covered (true) condition 1 not covered (true) conditions covered 2/2 They are also reported by the branch coverage. gcov -bc 2*: 14: x = a && A(b); branch 0 taken 1 (fallthrough) branch 1 taken 1 call 2 returned 1 call 3 returned 1 branch 4 taken 0 (fallthrough) branch 5 taken 1 branch 6 taken 1 (fallthrough) branch 7 taken 1 The algorithm struggles in a particular case where gcc would generate identical CFGs for different expressions: and.c: if (a && b && c) x = 1; ifs.c: if (a) if (b) if (c) x = 1; if (a && b && c) x = 1; and.c.gcov: #####: 2: if (a && b && c) conditions covered 2/2 conditions covered 2/2 conditions covered 2/2 #####: 3: x = 1; ifs.c.gcov: #####: 2: if (a) conditions covered 2/2 #####: 3: 2 if (b) conditions covered 2/2 #####: 4: 2 if (c) conditions covered 2/2 #####: 5: x = 1; These programs are semantically equivalent, and are interpreted as 3 separate conditional expressions. It does not matter w.r.t. coverage, but is not ideal. Adding an else to and.c fixes the issue: #####: 2: if (a && b && c) conditions covered 6/6 #####: 3: x = 1; #####: 4: else x = x; In the (a && b && c) case the else block must be shared between all three conditionals, and for if (a) if (b) if (c) there would be three *separate* else blocks. Since the algorithm works on CFGs, it cannot detect conditionals (from ternaries) that don't get an entry in the cfg. For example, int x = a ? 0 : 1 in gimple becomes _x = (_a == 0). From source you would expect coverage, but it gets neither branch nor condition coverage. For completeness, it could be achieved by scanning all gimple statements for comparisons, and insert an extra instruction for recording the outcome. The test suite consists of all different CFG kinds and control flow structures I could find, but there is certainly room for many more. Alternative email: Jørgen Kvalsvik -- Some final remarks (not a part of the commit message), this is written in a C++ style that I felt meshed well with what was already there, but if the maintainers would prefer a different approach then I'm happy to to make adjustments. I plan to write a more thorough description of the algorithm, as well as adding the same feature to clang as it is very useful for us at Woven Planet. I tried to pick flag names and options that were comfortable and descriptive, but if you have better names or different ideas for flags then I am happy to change them. The --coverage flag was not changed to imply -fprofile-conditions, but it is possibly something to consider. gcc/ChangeLog: * common.opt: Add new options -fprofile-conditions and -Wcoverage-too-many-conditions. * doc/gcov.texi: Add --conditions documentation. * doc/invoke.texi: Add -fprofile-conditions documentation. * gcov-counter.def (GCOV_COUNTER_CONDS): New. * gcov-io.h (GCOV_TAG_CONDS): New. (GCOV_TAG_CONDS_LENGTH): Likewise. (GCOV_TAG_CONDS_NUM): Likewise. * gcov.cc (class condition_info): New. (condition_info::condition_info): New. (condition_info::popcount): New. (struct coverage_info): New. (add_condition_counts): New. (output_conditions): New. (print_usage): Add -g, --conditions. (process_args): Likewise. (output_intermediate_json_line): Output conditions. (read_graph_file): Read conditions counters. (read_count_file): Read conditions counters. (file_summary): Print conditions. (accumulate_line_info): Accumulate conditions. (output_line_details): Print conditions. * profile.cc (find_conditions): New declaration. (instrument_decisions): New declaration. (branch_prob): Call find_conditions, instrument_decisions. (init_branch_prob): Add total_num_conds. (end_branch_prob): Likewise. * tree-profile.cc (INCLUDE_ALGORITHM): Define. (struct conds_ctx): New. (CONDITIONS_MAX_TERMS): New. (index_of): New. (index_lt): New. (single): New. (single_edge): New. (contract_edge): New. (contract_edge_up): New. (is_conditional_p): New. (collect_neighbors): New. (find_first_conditional): New. (emit_bitwise_op): New. (collect_conditions): New. (find_conditions): New. (instrument_decisions): New. gcc/testsuite/ChangeLog: * lib/gcov.exp: * g++.dg/gcov/gcov-18.C: New test. * gcc.misc-tests/gcov-19.c: New test. --- gcc/common.opt | 8 + gcc/doc/gcov.texi | 36 ++ gcc/doc/invoke.texi | 19 + gcc/gcov-counter.def | 3 + gcc/gcov-io.h | 3 + gcc/gcov.cc | 177 +++++- gcc/profile.cc | 51 +- gcc/testsuite/g++.dg/gcov/gcov-18.C | 209 ++++++ gcc/testsuite/gcc.misc-tests/gcov-19.c | 726 +++++++++++++++++++++ gcc/testsuite/lib/gcov.exp | 187 +++++- gcc/tree-profile.cc | 838 +++++++++++++++++++++++++ 11 files changed, 2248 insertions(+), 9 deletions(-) create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-18.C create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-19.c