Re: [PATCH v2] Add condition coverage profiling

["Jørgen Kvalsvik" <jorgen.kvalsvik@woven-planet.global>]

On 02/12/2022 00:05, Martin Liška wrote:
> 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
> 

Hello,

Thanks! I'll revert the documentation back to texinfo, I'm sorry sphinx fell
through.

Who can approve the remaining bits (the tree-profile presumably)? I'll submit v3
shortly.

Thanks,
Jørgen