Re: [PATCH] Add condition coverage profiling

["Martin Liška" <mliska@suse.cz>]

On 3/21/22 12:55, Jørgen Kvalsvik via Gcc-patches wrote:

Hello.

Thanks for very interesting extension of the existing GCOV profiling.

I briefly read the patch and investigated what happens and I've got various
questions/comments about it:

1) Do I correctly understand that __conditions_accu_true/false track
every short-circuit sub-expression of a condition and record
if a given sub-expr is seen to be true or false?

2) As mentioned these are bit sets, can you please explain why you (& -value)
from these sets?

3) I noticed a false report for a simple test-case:

$ cat cond.c
int x;

void foo (int a, int b)
{
     if (a || b)
       x = 1;
     else
       x = 2;
}

int main()
{
   foo (0, 1);
   return 0;
}

$ rm *gcda ; gcc --coverage cond.c -fprofile-conditions && ./a.out && gcov -g -t a-cond.c
         -:    0:Source:cond.c
         -:    0:Graph:a-cond.gcno
         -:    0:Data:a-cond.gcda
         -:    0:Runs:1
         -:    1:int x;
         -:    2:
         1:    3:void foo (int a, int b)
         -:    4:{
         1:    5:    if (a || b)
conditions covered 1/4
condition  0 not covered (true)
condition  0 not covered (false) <-- this was executed if I'm correct
condition  1 not covered (false)
         1:    6:      x = 1;
         -:    7:    else
     #####:    8:      x = 2;
         1:    9:}
         -:   10:
         1:   11:int main()
         -:   12:{
         1:   13:  foo (0, 1);
         1:   14:  return 0;
         -:   15:}

4) I noticed various CFG patterns in tree-profile.cc which are handled. Can you please
explain how the algorithm works even without knowing the original paper?

5) I noticed the following ICE:

$ gcc cond.c -fprofile-conditions -fprofile-generate
during IPA pass: profile
cond.c: In function ‘foo’:
cond.c:15:1: internal compiler error: Segmentation fault
    15 | }
       | ^
0xf4d64a crash_signal
	/home/marxin/Programming/gcc/gcc/toplev.cc:322
0x7ffff78b93cf ???
	/usr/src/debug/glibc-2.35-2.1.x86_64/signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0
0x7ffff78f29ed __GI__IO_ftell
	/usr/src/debug/glibc-2.35-2.1.x86_64/libio/ioftell.c:37
0xa9dfda gcov_position
	/home/marxin/Programming/gcc/gcc/gcov-io.cc:48
0xa9dfda gcov_write_tag(unsigned int)
	/home/marxin/Programming/gcc/gcc/gcov-io.cc:321
0xe9734a branch_prob(bool)
	/home/marxin/Programming/gcc/gcc/profile.cc:1542
0x1032e08 tree_profiling
	/home/marxin/Programming/gcc/gcc/tree-profile.cc:1620
0x1032e08 execute
	/home/marxin/Programming/gcc/gcc/tree-profile.cc:1726
Please submit a full bug report, with preprocessed source (by using -freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

6) Please follow the GNU coding style, most notable we replace 8 spaces with a tab.
And we break line before {, (, ... Remove noexcept specifiers for functions and I think
most of the newly added functions can be static. And each newly added function should
have a comment.

7) Please consider supporting of -profile-update=atomic where you'll need to utilize
an atomic builts (see how other instrumentation looks like with it).

That's the very first round of the review. Hope it's helpful.

Cheers,
Martin

> 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 <j@lambda.is>
> 
> --
> 
> 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