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
