Hello,
This patch adds support in gcc+gcov for modified condition/decision
coverage (MC/DC) with the -fcondition-coverage flag. MC/DC is a type of
test/code coverage and it is particularly important for safety-critical
applicaitons in industries like aviation and automotive. Notably, MC/DC
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
MC/DC comes in different flavours, the most important being unique
cause MC/DC and masking MC/DC - this patch implements masking MC/DC,
which is works well with short circuiting semantics, and according to
John Chilenski's "An Investigation of Three Forms of the Modified
Condition Decision Coverage (MCDC) Criterion" (2001) is as good as
unique cause at catching bugs.
Whalen, Heimdahl, and De Silva "Efficient Test Coverage Measurement for
MC/DC" describes an algorithm for determining masking from an AST walk,
but my algorithm figures this out from analyzing the control flow graph.
The CFG is considered a binary decision diagram and an evaluation
becomes a path through the BDD, which is recorded. Certain paths will
mask ("null out") the contribution from earlier path segments, which can
be determined by finding short circuit endpoints. Masking is the
short circuiting of terms in the reverse-ordered Boolean function, and
the masked terms do not affect the decision like short-circuited
terms do not affect the decision.
A tag/discriminator mapping from gcond->uid is created during
gimplification and made available through the function struct. The
values are unimportant as long as basic conditions constructed from a
single Boolean expression are given the same identifier. This happens in
the breaking down of ANDIF/ORIF trees, so the coverage generally works
well for frontends that create such trees.
Like Whalen et al this implementation records coverage in fixed-size
bitsets which gcov knows how to interpret. This takes only a few bitwise
operations per condition and is very fast, but comes with a limit on the
number of terms in a single boolean expression; the number of bits in a
gcov_unsigned_type (which is usually typedef'd to uint64_t). For most
practical purposes this is acceptable, and by default a warning will be
issued if gcc cannot instrument the expression. This is a practical
limitation in the implementation, not the algorithm, so support for more
conditions can be added by also introducing arbitrary-sized bitsets.
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 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
]
}
],
Expressions with constants may be heavily rewritten before it reaches
the gimplification, so constructs like int x = a ? 0 : 1 becomes
_x = (_a == 0). From source you would expect coverage, but it gets
neither branch nor condition coverage. The same applies to expressions
like int x = 1 || a which are simply replaced by a constant.
The test suite contains a lot of small programs and functions. Some of
these were designed by hand to test for specific behaviours and graph
shapes, and some are previously-failed test cases in other programs
adapted into the test suite.
gcc/ChangeLog:
* builtins.cc (expand_builtin_fork_or_exec): Check
condition_coverage_flag.
* collect2.cc (main): Add -fno-condition-coverage to OBSTACK.
* common.opt: Add new options -fcondition-coverage and
-Wcoverage-too-many-conditions.
* doc/gcov.texi: Add --conditions documentation.
* doc/invoke.texi: Add -fcondition-coverage documentation.
* function.cc (allocate_struct_function): Init cond_uids.
* function.h (struct function): Add cond_uids.
* gcc.cc: Link gcov on -fcondition-coverage.
* gcov-counter.def (GCOV_COUNTER_CONDS): New.
* gcov-dump.cc (tag_conditions): New.
* gcov-io.h (GCOV_TAG_CONDS): New.
(GCOV_TAG_CONDS_LENGTH): New.
(GCOV_TAG_CONDS_NUM): New.
* 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 condition counters.
(read_count_file): Likewise.
(file_summary): Print conditions.
(accumulate_line_info): Accumulate conditions.
(output_line_details): Print conditions.
* gimplify.cc (next_cond_uid): New.
(reset_cond_uid): New.
(shortcut_cond_r): Set condition discriminator.
(tag_shortcut_cond): New.
(shortcut_cond_expr): Set condition discriminator.
(gimplify_cond_expr): Likewise.
(gimplify_function_tree): Call reset_cond_uid.
* ipa-inline.cc (can_early_inline_edge_p): Check
condition_coverage_flag.
* ipa-split.cc (pass_split_functions::gate): Likewise.
* passes.cc (finish_optimization_passes): Likewise.
* profile.cc (struct condcov): New declaration.
(cov_length): Likewise.
(cov_blocks): Likewise.
(cov_masks): Likewise.
(cov_maps): Likewise.
(cov_free): Likewise.
(instrument_decisions): New.
(read_thunk_profile): Control output to file.
(branch_prob): Call find_conditions, instrument_decisions.
(init_branch_prob): Add total_num_conds.
(end_branch_prob): Likewise.
* tree-core.h (struct tree_exp): Add condition_uid.
* tree-profile.cc (struct conds_ctx): New.
(CONDITIONS_MAX_TERMS): New.
(EDGE_CONDITION): New.
(topological_cmp): New.
(index_of): New.
(single_p): New.
(single_edge): New.
(contract_edge_up): New.
(struct outcomes): New.
(conditional_succs): New.
(condition_index): New.
(condition_uid): New.
(masking_vectors): New.
(emit_assign): New.
(emit_bitwise_op): New.
(make_top_index_visit): New.
(make_top_index): New.
(paths_between): New.
(struct condcov): New.
(cov_length): New.
(cov_blocks): New.
(cov_masks): New.
(cov_maps): New.
(cov_free): New.
(find_conditions): New.
(struct counters): New.
(find_counters): New.
(resolve_counter): New.
(resolve_counters): New.
(instrument_decisions): New.
(tree_profiling): Check condition_coverage_flag.
(pass_ipa_tree_profile::gate): Likewise.
* tree.h (SET_EXPR_UID): New.
(EXPR_COND_UID): New.
libgcc/ChangeLog:
* libgcov-merge.c (__gcov_merge_ior): New.
gcc/testsuite/ChangeLog:
* lib/gcov.exp: Add condition coverage test function.
* g++.dg/gcov/gcov-18.C: New test.
* gcc.misc-tests/gcov-19.c: New test.
* gcc.misc-tests/gcov-20.c: New test.
* gcc.misc-tests/gcov-21.c: New test.
* gcc.misc-tests/gcov-22.c: New test.
* gcc.misc-tests/gcov-23.c: New test.
diff --git a/gcc/function.cc b/gcc/function.cc
index 89841787ff8..e57d0488c7a 100644
--- a/gcc/function.cc
+++ b/gcc/function.cc
@@ -4793,6 +4793,7 @@ allocate_struct_function (tree fndecl, bool abstract_p)
cfun = ggc_cleared_alloc<function> ();
+ cfun->cond_uids = hash_map <gcond*, unsigned>::create_ggc ();
There are a lot of struct functions created during WPA ICF stage, where
this hash will be completely unused. I think you can initialize it to
NULL here, allocate it at the gimplification time only and also
deallocate in free_after_compilation.
It would be good to arrange the patch to do nothing unless the condition
coverage command line option is used. At the moment it seems you
compute conditional uids just to ignore them later.
Also at the moment the hash will dangle pointers to statements that was
optimized out. There are two options. Either initialize it with
GTY((cache)) which will make garbage collector to remove entries to
statements not reachable otherwise.
Other option would be move it out of gabrage collector completely and
extend gsi_remove to also remove entry in the hash just as it does so
This should also make it possible to move it out of ggc.
for EH (see calls to remove_stmt_from_eh_lp).
@@ -134,6 +136,33 @@ public:
vector<unsigned> lines;
};
+/* Describes a single conditional expression and the (recorded) conditions
+ shown to independently affect the outcome. */
+class condition_info
+{
+public:
+ condition_info ();
+
+ int popcount () const;
+
+ /* Bitsets storing the independently significant outcomes for true and false,
+ * respectively. */
Extra * here.
+ gcov_type_unsigned truev;
+ gcov_type_unsigned falsev;
+
+ /* Number of terms in the expression; if (x) -> 1, if (x && y) -> 2 etc. */
+ unsigned n_terms;
+};
diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
index 342e43a7f25..591cb50193c 100644
--- a/gcc/gimplify.cc
+++ b/gcc/gimplify.cc
@@ -71,6 +71,24 @@ along with GCC; see the file COPYING3. If not see
#include "context.h"
#include "tree-nested.h"
By coding style there should be acomment what nextuid is used for.
+static unsigned nextuid = 1;
+/* Get a fresh identifier for a new condition expression. This is used for
+ condition coverage. */
+static unsigned
+next_cond_uid ()
+{
+ return nextuid++;
+}
+/* Reset the condition uid to the value it should have when compiling a new
+ function. 0 is already the default/untouched value, so start at non-zero.
+ A valid and set id should always be > 0. This is used for condition
+ coverage. */
+static void
+reset_cond_uid ()
+{
+ nextuid = 1;
+}
+
/* Hash set of poisoned variables in a bind expr. */
+/* Given a multi-term condition (ANDIF, ORIF), walk the predicate and tag every
+ term with uid. When two basic conditions share the uid discriminator when
+ they belong to the same predicate, which used by the condition coverage.
+ Doing this as an explicit step makes for a simpler implementation than
+ weaving it into the splitting code as the splitting code eventually reaches
+ back up to gimplfiy_expr which makes bookkeeping complicated. */
Coding style also asks to document parameters (and reffer to them in
uppercase, like PRED/CONDITION_UID)
+static void
+tag_shortcut_cond (tree pred, unsigned condition_uid)
+{
+ if (TREE_CODE (pred) == TRUTH_ANDIF_EXPR
+ || TREE_CODE (pred) == TRUTH_ORIF_EXPR)
+ {
+ tree fst = TREE_OPERAND (pred, 0);
+ tree lst = TREE_OPERAND (pred, 1);
+
+ if (TREE_CODE (fst) == TRUTH_ANDIF_EXPR
+ || TREE_CODE (fst) == TRUTH_ORIF_EXPR)
+ tag_shortcut_cond (fst, condition_uid);
+ else if (TREE_CODE (fst) == COND_EXPR)
+ SET_EXPR_UID (fst, condition_uid);
+
+ if (TREE_CODE (lst) == TRUTH_ANDIF_EXPR
+ || TREE_CODE (lst) == TRUTH_ORIF_EXPR)
+ tag_shortcut_cond (lst, condition_uid);
+ else if (TREE_CODE (lst) == COND_EXPR)
+ SET_EXPR_UID (lst, condition_uid);
+ }
+}
/* Given a conditional expression EXPR with short-circuit boolean
predicates using TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR, break the
predicate apart into the equivalent sequence of conditionals. */
static tree
-shortcut_cond_expr (tree expr)
+shortcut_cond_expr (tree expr, unsigned condition_uid)
Similarly here CONDITION_UID should be documented.
+
+/* Compare two basic blocks by their order in the expression i.e. for (a || b)
+ then topological_cmp (a, b, ...) < 0. The result is undefined if lhs, rhs
+ belong to different expressions. The top_index argument should be the
+ top_index vector from ctx. */
Please use LHS/RHS and TOP_INDEX in commants (in all functions you aded).
It also seems that you are not releasing the hash after its use. It
leaks points to gimple statments that are removed, so it may
The patch look OK to me with the hash memory management change above.
I really do apologize for being so slow on the reviews - it is an
interesting feature and I should have handled it faster.
Honza
