Add condition coverage (MC/DC)

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 flavors, 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 finding the masking table from an AST
walk, but my algorithm figures this out by analyzing the control flow
graph.  The CFG is considered a reduced ordered binary decision diagram
and an input vector a path through the BDD, which is recorded.  Specific
edges will mask ("null out") the contribution from earlier path
segments, which can be determined by finding short circuit endpoints.
Masking is most easily understood as circuiting of terms in the
reverse-ordered Boolean function, and the masked conditions do not
affect the decision like short-circuited conditions 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. Recording conditions only
requires 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, and
not a limitation of the algorithm, so support for more conditions can be
supported by 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 (free_after_compilation): Free 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.
	(gimple_associate_condition_with_expr): 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.

1 files changed, 202 insertions, 7 deletions

diff --git a/gcc/gcov.cc b/gcc/gcov.cc
index fad704e..fd4a5cd 100644
--- a/gcc/gcov.cc
+++ b/gcc/gcov.cc
@@ -46,6 +46,7 @@ along with Gcov; see the file COPYING3.  If not see
 #include "color-macros.h"
 #include "pretty-print.h"
 #include "json.h"
+#include "hwint.h"
 
 #include <zlib.h>
 #include <getopt.h>
@@ -81,6 +82,7 @@ using namespace std;
 class function_info;
 class block_info;
 class source_info;
+class condition_info;
 
 /* Describes an arc between two basic blocks.  */
 
@@ -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.  */
+  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;
+};
+
+condition_info::condition_info (): truev (0), falsev (0), n_terms (0)
+{
+}
+
+int condition_info::popcount () const
+{
+    return popcount_hwi (truev) + popcount_hwi (falsev);
+}
+
 /* Describes a basic block. Contains lists of arcs to successor and
    predecessor blocks.  */
 
@@ -167,6 +196,8 @@ public:
   /* Block is a landing pad for longjmp or throw.  */
   unsigned is_nonlocal_return : 1;
 
+  condition_info conditions;
+
   vector<block_location_info> locations;
 
   struct
@@ -277,6 +308,8 @@ public:
   vector<block_info> blocks;
   unsigned blocks_executed;
 
+  vector<condition_info*> conditions;
+
   /* Raw arc coverage counts.  */
   vector<gcov_type> counts;
 
@@ -353,6 +386,9 @@ struct coverage_info
   int branches_executed;
   int branches_taken;
 
+  int conditions;
+  int conditions_covered;
+
   int calls;
   int calls_executed;
 
@@ -552,6 +588,10 @@ static int multiple_files = 0;
 
 static int flag_branches = 0;
 
+/* Output conditions (modified condition/decision coverage).  */
+
+static bool flag_conditions = 0;
+
 /* Show unconditional branches too.  */
 static int flag_unconditional = 0;
 
@@ -658,6 +698,7 @@ static int read_count_file (void);
 static void solve_flow_graph (function_info *);
 static void find_exception_blocks (function_info *);
 static void add_branch_counts (coverage_info *, const arc_info *);
+static void add_condition_counts (coverage_info *, const block_info *);
 static void add_line_counts (coverage_info *, function_info *);
 static void executed_summary (unsigned, unsigned);
 static void function_summary (const coverage_info *);
@@ -666,6 +707,7 @@ static const char *format_gcov (gcov_type, gcov_type, int);
 static void accumulate_line_counts (source_info *);
 static void output_gcov_file (const char *, source_info *);
 static int output_branch_count (FILE *, int, const arc_info *);
+static void output_conditions (FILE *, const block_info *);
 static void output_lines (FILE *, const source_info *);
 static string make_gcov_file_name (const char *, const char *);
 static char *mangle_name (const char *);
@@ -930,6 +972,8 @@ print_usage (int error_p)
   fnotice (file, "  -b, --branch-probabilities      Include branch probabilities in output\n");
   fnotice (file, "  -c, --branch-counts             Output counts of branches taken\n\
                                     rather than percentages\n");
+  fnotice (file, "  -g, --conditions                Include modified condition/decision\n\
+                                    coverage in output\n");
   fnotice (file, "  -d, --display-progress          Display progress information\n");
   fnotice (file, "  -D, --debug			    Display debugging dumps\n");
   fnotice (file, "  -f, --function-summaries        Output summaries for each function\n");
@@ -983,6 +1027,7 @@ static const struct option options[] =
   { "all-blocks",           no_argument,       NULL, 'a' },
   { "branch-probabilities", no_argument,       NULL, 'b' },
   { "branch-counts",        no_argument,       NULL, 'c' },
+  { "conditions",	    no_argument,       NULL, 'g' },
   { "json-format",	    no_argument,       NULL, 'j' },
   { "human-readable",	    no_argument,       NULL, 'H' },
   { "no-output",            no_argument,       NULL, 'n' },
@@ -1011,7 +1056,7 @@ process_args (int argc, char **argv)
 {
   int opt;
 
-  const char *opts = "abcdDfhHijklmno:pqrs:tuvwx";
+  const char *opts = "abcdDfghHijklmno:pqrs:tuvwx";
   while ((opt = getopt_long (argc, argv, opts, options, NULL)) != -1)
     {
       switch (opt)
@@ -1028,6 +1073,9 @@ process_args (int argc, char **argv)
 	case 'f':
 	  flag_function_summary = 1;
 	  break;
+	case 'g':
+	  flag_conditions = 1;
+	  break;
 	case 'h':
 	  print_usage (false);
 	  /* print_usage will exit.  */
@@ -1152,6 +1200,45 @@ output_intermediate_json_line (json::array *object,
 	  }
       }
 
+  json::array *conditions = new json::array ();
+  lineo->set ("conditions", conditions);
+  if (flag_conditions)
+  {
+    vector<block_info *>::const_iterator it;
+    for (it = line->blocks.begin (); it != line->blocks.end (); it++)
+      {
+	const condition_info& info = (*it)->conditions;
+	if (info.n_terms == 0)
+	    continue;
+
+	const int count = 2 * info.n_terms;
+	const int covered = info.popcount ();
+
+	json::object *cond = new json::object ();
+	cond->set ("count", new json::integer_number (count));
+	cond->set ("covered", new json::integer_number (covered));
+
+	json::array *mtrue = new json::array ();
+	json::array *mfalse = new json::array ();
+	cond->set ("not_covered_true", mtrue);
+	cond->set ("not_covered_false", mfalse);
+
+	if (count != covered)
+	  {
+	    for (unsigned i = 0; i < info.n_terms; i++)
+	      {
+		gcov_type_unsigned index = 1;
+		index <<= i;
+		if (!(index & info.truev))
+		    mtrue->append (new json::integer_number (i));
+		if (!(index & info.falsev))
+		    mfalse->append (new json::integer_number (i));
+	      }
+	  }
+	conditions->append (cond);
+      }
+  }
+
   object->append (lineo);
 }
 
@@ -1969,6 +2056,28 @@ read_graph_file (void)
 		  }
 	    }
 	}
+      else if (fn && tag == GCOV_TAG_CONDS)
+	{
+	  unsigned num_dests = GCOV_TAG_CONDS_NUM (length);
+
+	  if (!fn->conditions.empty ())
+	    fnotice (stderr, "%s:already seen conditions for '%s'\n",
+		     bbg_file_name, fn->get_name ());
+	  else
+	    fn->conditions.resize (num_dests);
+
+	  for (unsigned i = 0; i < num_dests; ++i)
+	    {
+	      unsigned idx = gcov_read_unsigned ();
+
+	      if (idx >= fn->blocks.size ())
+		goto corrupt;
+
+	      condition_info *info = &fn->blocks[idx].conditions;
+	      info->n_terms = gcov_read_unsigned ();
+	      fn->conditions[i] = info;
+	    }
+	}
       else if (fn && tag == GCOV_TAG_LINES)
 	{
 	  unsigned blockno = gcov_read_unsigned ();
@@ -2099,6 +2208,21 @@ read_count_file (void)
 	      goto cleanup;
 	    }
 	}
+      else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_CONDS) && fn)
+	{
+	  length = abs (read_length);
+	  if (length != GCOV_TAG_COUNTER_LENGTH (2 * fn->conditions.size ()))
+	      goto mismatch;
+
+	  if (read_length > 0)
+	    {
+	      for (ix = 0; ix != fn->conditions.size (); ix++)
+		{
+		  fn->conditions[ix]->truev  |= gcov_read_counter ();
+		  fn->conditions[ix]->falsev |= gcov_read_counter ();
+		}
+	    }
+	}
       else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
 	{
 	  length = abs (read_length);
@@ -2443,6 +2567,15 @@ add_branch_counts (coverage_info *coverage, const arc_info *arc)
     }
 }
 
+/* Increment totals in COVERAGE according to to block BLOCK.  */
+
+static void
+add_condition_counts (coverage_info *coverage, const block_info *block)
+{
+  coverage->conditions += 2 * block->conditions.n_terms;
+  coverage->conditions_covered += block->conditions.popcount ();
+}
+
 /* Format COUNT, if flag_human_readable_numbers is set, return it human
    readable format.  */
 
@@ -2546,6 +2679,18 @@ file_summary (const coverage_info *coverage)
 		 coverage->calls);
       else
 	fnotice (stdout, "No calls\n");
+
+    }
+
+  if (flag_conditions)
+    {
+      if (coverage->conditions)
+	fnotice (stdout, "Condition outcomes covered:%s of %d\n",
+		 format_gcov (coverage->conditions_covered,
+			      coverage->conditions, 2),
+		 coverage->conditions);
+      else
+	fnotice (stdout, "No conditions\n");
     }
 }
 
@@ -2780,6 +2925,12 @@ static void accumulate_line_info (line_info *line, source_info *src,
 	 it != line->branches.end (); it++)
       add_branch_counts (&src->coverage, *it);
 
+  if (add_coverage)
+    for (vector<block_info *>::iterator it = line->blocks.begin ();
+	 it != line->blocks.end (); it++)
+      add_condition_counts (&src->coverage, *it);
+
+
   if (!line->blocks.empty ())
     {
       /* The user expects the line count to be the number of times
@@ -2881,6 +3032,37 @@ accumulate_line_counts (source_info *src)
       }
 }
 
+/* Output information about the conditions in block BINFO.  The output includes
+ * a summary (n/m outcomes covered) and a list of the missing (uncovered)
+ * outcomes.  */
+
+static void
+output_conditions (FILE *gcov_file, const block_info *binfo)
+{
+    const condition_info& info = binfo->conditions;
+    if (info.n_terms == 0)
+	return;
+
+    const int expected = 2 * info.n_terms;
+    const int got = info.popcount ();
+
+    fnotice (gcov_file, "condition outcomes covered %d/%d\n", got, expected);
+    if (expected == got)
+	return;
+
+    for (unsigned i = 0; i < info.n_terms; i++)
+    {
+	gcov_type_unsigned index = 1;
+	index <<= i;
+	if ((index & info.truev & info.falsev))
+	    continue;
+
+	const char *t = (index & info.truev) ? "" : "true";
+	const char *f = (index & info.falsev) ? "" : " false";
+	fnotice (gcov_file, "condition %2u not covered (%s%s)\n", i, t, f + !t[0]);
+    }
+}
+
 /* Output information about ARC number IX.  Returns nonzero if
    anything is output.  */
 
@@ -3091,16 +3273,29 @@ output_line_details (FILE *f, const line_info *line, unsigned line_num)
 	  if (flag_branches)
 	    for (arc = (*it)->succ; arc; arc = arc->succ_next)
 	      jx += output_branch_count (f, jx, arc);
+
+	  if (flag_conditions)
+	      output_conditions (f, *it);
 	}
     }
-  else if (flag_branches)
+  else
     {
-      int ix;
+      if (flag_branches)
+	{
+	  int ix;
+
+	  ix = 0;
+	  for (vector<arc_info *>::const_iterator it = line->branches.begin ();
+		  it != line->branches.end (); it++)
+	      ix += output_branch_count (f, ix, (*it));
+	}
 
-      ix = 0;
-      for (vector<arc_info *>::const_iterator it = line->branches.begin ();
-	   it != line->branches.end (); it++)
-	ix += output_branch_count (f, ix, (*it));
+      if (flag_conditions)
+	{
+	  for (vector<block_info *>::const_iterator it = line->blocks.begin ();
+	       it != line->blocks.end (); it++)
+	      output_conditions (f, *it);
+	}
     }
 }