Re: [PATCH v2] Add condition coverage profiling

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

On 11/11/22 06:21, Jørgen Kvalsvik wrote:
> From: Jørgen Kvalsvik <j@lambda.is>
> 
> 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. MC/DC it is
> required for 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 analyses the the control
> flow graph to instrument for coverage. This has the benefit of being
> programming language independent and faithful to compiler decisions
> and transformations, 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 records coverage in fixed-size
> bitsets which gcov knows how to interpret. This is very fast, but
> introduces a limit on the number of terms in a single boolean
> expression, 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. This limitation is in the implementation and not the
> algorithm, so support for more conditions can be added by also
> introducing arbitrary-sized bitsets.
> 
> For space overhead, the instrumentation needs two accumulators
> (gcov_unsigned_type) per condition in the program which will be written
> to the gcov file. In addition, every function gets a pair of local
> accumulators, but these accmulators are reused between conditions in the
> same function.
> 
> For time overhead, there is a zeroing of the local accumulators for
> every condition and one or two bitwise operation on every edge taken in
> the an expression.
> 
> 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)
> condition outcomes covered 3/8
> condition  0 not covered (true false)
> condition  1 not covered (true)
> condition  2 not covered (true)
> condition  3 not covered (true)
>         1:   19:        x = 1;
>         -:   20:    else
>         2:   21:        x = 2;
>         3:   22:}
> 
> gcov --conditions --json-format:
> 
>     "conditions": [
>         {
>             "not_covered_false": [
>                 0
>             ],
>             "count": 8,
>             "covered": 3,
>             "not_covered_true": [
>                 0,
>                 1,
>                 2,
>                 3
>             ]
>         }
>     ],
> 
> Some expressions, mostly those without else-blocks, are effectively
> "rewritten" in the CFG construction making the algorithm unable to
> distinguish them:
> 
> and.c:
> 
>     if (a && b && c)
>         x = 1;
> 
> ifs.c:
> 
>     if (a)
>         if (b)
>             if (c)
>                 x = 1;
> 
> gcc will build the same graph for both these programs, and gcov will
> report boths as 3-term expressions. It is vital that it is not
> interpreted the other way around (which is consistent with the shape of
> the graph) because otherwise the masking would be wrong for the and.c
> program which is a more severe error. While surprising, users would
> probably expect some minor rewriting of semantically-identical
> expressions.
> 
> and.c.gcov:
>     #####:    2:    if (a && b && c)
> condition outcomes covered 6/6
>     #####:    3:        x = 1;
> 
> ifs.c.gcov:
>     #####:    2:    if (a)
>     #####:    3:        if (b)
>     #####:    4:            if (c)
>     #####:    5:                x = 1;
> condition outcomes covered 6/6
> 
> Adding else clauses alters the program (ifs.c can have 3 elses, and.c
> only 1) and coverage becomes less surprising
> 
> ifs.c.gcov:
>     #####:    2:    if (a)
> condition outcomes covered 2/2
>     #####:    4:    {
>     #####:    4:        if (b)
> condition outcomes covered 2/2
>               5:        {
>     #####:    6:            if (c)
> condition outcomes covered 2/2
>     #####:    7:                x = 1;
>     #####:    8:        }
>     #####:    9:        else
>     #####:   10:            x = 2;
>     #####:   11:    }
>     #####:   12:    else
>     #####:   13:        x = 3;
> 
> Since the algorithm works on CFGs, it cannot detect some ternary
> operator introduced conditionals. 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 such
> comparisons, and insert an extra instruction for recording the outcome.
> 

Hello.

Thanks for the rebased version of the patch. Please, update the documentation
bits as the Sphinx conversion didn't make it. Sorry for that.

I approve the GCOV-part of the patch and I'm fine with the rest of the patch
(though I can't approve it).

What a nice work!

Cheers,
Martin