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