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
