@@ -5879,7 +5879,7 @@ expand_builtin_fork_or_exec (tree fn, tree exp, rtx target, int ignore)
tree call;
/* If we are not profiling, just call the function. */
- if (!profile_arc_flag)
+ if (!profile_arc_flag && !profile_condition_flag)
return NULL_RTX;
/* Otherwise call the wrapper. This should be equivalent for the rest of
@@ -1032,9 +1032,9 @@ main (int argc, char **argv)
lto_mode = LTO_MODE_LTO;
}
- /* -fno-profile-arcs -fno-test-coverage -fno-branch-probabilities
- -fno-exceptions -w -fno-whole-program */
- num_c_args += 6;
+ /* -fno-profile-arcs -fno-profile-conditions -fno-test-coverage
+ -fno-branch-probabilities -fno-exceptions -w -fno-whole-program */
+ num_c_args += 7;
c_argv = XCNEWVEC (char *, num_c_args);
c_ptr = CONST_CAST2 (const char **, char **, c_argv);
@@ -1230,6 +1230,7 @@ main (int argc, char **argv)
}
obstack_free (&temporary_obstack, temporary_firstobj);
*c_ptr++ = "-fno-profile-arcs";
+ *c_ptr++ = "-fno-profile-conditions";
*c_ptr++ = "-fno-test-coverage";
*c_ptr++ = "-fno-branch-probabilities";
*c_ptr++ = "-fno-exceptions";
@@ -862,6 +862,11 @@ Wcoverage-invalid-line-number
Common Var(warn_coverage_invalid_linenum) Init(1) Warning
Warn in case a function ends earlier than it begins due to an invalid linenum macros.
+Wcoverage-too-many-conditions
+Common Var(warn_too_many_conditions) Init(1) Warning
+Warn when a conditional has too many terms and condition coverage profiling
+gives up instrumenting the expression.
+
Wmissing-profile
Common Var(warn_missing_profile) Init(1) Warning
Warn in case profiles in -fprofile-use do not exist.
@@ -2377,6 +2382,10 @@ fprofile-arcs
Common Var(profile_arc_flag)
Insert arc-based program profiling code.
+fprofile-conditions
+Common Var(profile_condition_flag)
+Insert condition coverage profiling code.
+
fprofile-dir=
Common Joined RejectNegative Var(profile_data_prefix)
Set the top-level directory for storing the profile data.
@@ -124,6 +124,7 @@ gcov [@option{-v}|@option{--version}] [@option{-h}|@option{--help}]
[@option{-a}|@option{--all-blocks}]
[@option{-b}|@option{--branch-probabilities}]
[@option{-c}|@option{--branch-counts}]
+ [@option{-g}|@option{--conditions}]
[@option{-d}|@option{--display-progress}]
[@option{-f}|@option{--function-summaries}]
[@option{-j}|@option{--json-format}]
@@ -169,6 +170,14 @@ be shown, unless the @option{-u} option is given.
Write branch frequencies as the number of branches taken, rather than
the percentage of branches taken.
+@item -g
+@itemx --conditions
+Write condition coverage to the output file, and write condition summary info
+to the standard output. This option allows you to see if the conditions in
+your program at least once had an independent effect on the outcome of the
+boolean expression (modified condition/decision coverage). This requires you
+to compile the source with @option{-fprofile-conditions}.
+
@item -d
@itemx --display-progress
Display the progress on the standard output.
@@ -301,6 +310,7 @@ Each @var{line} has the following form:
"branches": ["$branch"],
"calls": ["$call"],
"count": 2,
+ "conditions": ["$condition"],
"line_number": 15,
"unexecuted_block": false,
"function_name": "foo",
@@ -384,6 +394,34 @@ to @var{line::count})
@var{destination_block_id}: ID of the basic block this calls continues after return
@end itemize
+Each @var{condition} has the following form:
+
+@smallexample
+@{
+ "count": 4,
+ "covered": 2,
+ "not_covered_false": [],
+ "not_covered_true": [0, 1],
+@}
+
+@end smallexample
+
+Fields of the @var{condition} element have following semantics:
+
+@itemize @bullet
+@item
+@var{count}: number of condition outcomes in this expression
+
+@item
+@var{covered}: number of covered condition outcomes in this expression
+
+@item
+@var{not_covered_true}: terms, by index, not seen as true in this expression
+
+@item
+@var{not_covered_false}: terms, by index, not seen as false in this expression
+@end itemize
+
@item -H
@itemx --human-readable
Write counts in human readable format (like 24.6k).
@@ -628,6 +628,7 @@ Objective-C and Objective-C++ Dialects}.
@item Program Instrumentation Options
@xref{Instrumentation Options,,Program Instrumentation Options}.
@gccoptlist{-p -pg -fprofile-arcs --coverage -ftest-coverage
+-fprofile-conditions
-fprofile-abs-path
-fprofile-dir=@var{path} -fprofile-generate -fprofile-generate=@var{path}
-fprofile-info-section -fprofile-info-section=@var{name}
@@ -6474,6 +6475,14 @@ poorly optimized code and is useful only in the
case of very minor changes such as bug fixes to an existing code-base.
Completely disabling the warning is not recommended.
+@opindex Wno-coverage-too-many-conditions
+@opindex Wcoverage-too-many-conditions
+@item -Wno-coverage-too-many-conditions
+Warn if @option{-fprofile-conditions} is used and an expression have too many
+terms and GCC gives up coverage. Coverage is given up when there are more
+terms in the conditional than there are bits in a @code{gcov_type_unsigned}.
+This warning is enabled by default.
+
@opindex Wno-coverage-invalid-line-number
@opindex Wcoverage-invalid-line-number
@item -Wno-coverage-invalid-line-number
@@ -16627,6 +16636,14 @@ Note that if a command line directly links source files, the corresponding
E.g. @code{gcc a.c b.c -o binary} would generate @file{binary-a.gcda} and
@file{binary-b.gcda} files.
+@item -fprofile-conditions
+@opindex fprofile-conditions
+Add code so that program conditions are instrumented. During execution the
+program records what terms in a conditional contributes to a decision, which
+can be used to verify that all terms in a booleans are tested and have an
+independent effect on the outcome of a decision. The result can be read with
+@code{gcov --conditions}.
+
@xref{Cross-profiling}.
@cindex @command{gcov}
@@ -16689,6 +16706,10 @@ executed. When an arc is the only exit or only entrance to a block, the
instrumentation code can be added to the block; otherwise, a new basic
block must be created to hold the instrumentation code.
+With @option{-fprofile-conditions}, for each conditional in your program GCC
+creates a bitset and records the exercised boolean values that have an
+independent effect on the outcome of that expression.
+
@need 2000
@opindex ftest-coverage
@item -ftest-coverage
@@ -1157,7 +1157,7 @@ proper position among the other output files. */
%:include(libgomp.spec)%(link_gomp)}\
%{fgnu-tm:%:include(libitm.spec)%(link_itm)}\
" STACK_SPLIT_SPEC "\
- %{fprofile-arcs|fprofile-generate*|coverage:-lgcov} " SANITIZER_SPEC " \
+ %{fprofile-arcs|fprofile-conditions|fprofile-generate*|coverage:-lgcov} " SANITIZER_SPEC " \
%{!nostdlib:%{!r:%{!nodefaultlibs:%(link_ssp) %(link_gcc_c_sequence)}}}\
%{!nostdlib:%{!r:%{!nostartfiles:%E}}} %{T*} \n%(post_link) }}}}}}"
#endif
@@ -1276,7 +1276,7 @@ static const char *cc1_options =
%{!fsyntax-only:%{S:%W{o*}%{!o*:-o %w%b.s}}}\
%{fsyntax-only:-o %j} %{-param*}\
%{coverage:-fprofile-arcs -ftest-coverage}\
- %{fprofile-arcs|fprofile-generate*|coverage:\
+ %{fprofile-arcs|fprofile-conditions|fprofile-generate*|coverage:\
%{!fprofile-update=single:\
%{pthread:-fprofile-update=prefer-atomic}}}";
@@ -49,3 +49,6 @@ DEF_GCOV_COUNTER(GCOV_COUNTER_IOR, "ior", _ior)
/* Time profile collecting first run of a function */
DEF_GCOV_COUNTER(GCOV_TIME_PROFILER, "time_profiler", _time_profile)
+
+/* Conditions. The counter is interpreted as a bit-set. */
+DEF_GCOV_COUNTER(GCOV_COUNTER_CONDS, "conditions", _ior)
@@ -38,6 +38,7 @@ static void print_version (void);
static void tag_function (const char *, unsigned, int, unsigned);
static void tag_blocks (const char *, unsigned, int, unsigned);
static void tag_arcs (const char *, unsigned, int, unsigned);
+static void tag_conditions (const char *, unsigned, int, unsigned);
static void tag_lines (const char *, unsigned, int, unsigned);
static void tag_counters (const char *, unsigned, int, unsigned);
static void tag_summary (const char *, unsigned, int, unsigned);
@@ -77,6 +78,7 @@ static const tag_format_t tag_table[] =
{GCOV_TAG_FUNCTION, "FUNCTION", tag_function},
{GCOV_TAG_BLOCKS, "BLOCKS", tag_blocks},
{GCOV_TAG_ARCS, "ARCS", tag_arcs},
+ {GCOV_TAG_CONDS, "CONDITIONS", tag_conditions},
{GCOV_TAG_LINES, "LINES", tag_lines},
{GCOV_TAG_OBJECT_SUMMARY, "OBJECT_SUMMARY", tag_summary},
{0, NULL, NULL}
@@ -392,6 +394,28 @@ tag_arcs (const char *filename ATTRIBUTE_UNUSED,
}
}
+/* Print number of conditions (not outcomes, i.e. if (x && y) is 2, not 4). */
+static void
+tag_conditions (const char *filename, unsigned /* tag */, int length,
+ unsigned depth)
+{
+ unsigned n_conditions = GCOV_TAG_CONDS_NUM (length);
+
+ printf (" %u conditions", n_conditions);
+ if (flag_dump_contents)
+ {
+ for (unsigned ix = 0; ix != n_conditions; ix++)
+ {
+ const unsigned blockno = gcov_read_unsigned ();
+ const unsigned nterms = gcov_read_unsigned ();
+
+ printf ("\n");
+ print_prefix (filename, depth, gcov_position ());
+ printf (VALUE_PADDING_PREFIX "block %u:", blockno);
+ printf (" %u", nterms);
+ }
+ }
+}
static void
tag_lines (const char *filename ATTRIBUTE_UNUSED,
unsigned tag ATTRIBUTE_UNUSED, int length ATTRIBUTE_UNUSED,
@@ -261,6 +261,9 @@ typedef uint64_t gcov_type_unsigned;
#define GCOV_TAG_ARCS ((gcov_unsigned_t)0x01430000)
#define GCOV_TAG_ARCS_LENGTH(NUM) (1 + (NUM) * 2 * GCOV_WORD_SIZE)
#define GCOV_TAG_ARCS_NUM(LENGTH) (((LENGTH / GCOV_WORD_SIZE) - 1) / 2)
+#define GCOV_TAG_CONDS ((gcov_unsigned_t)0x01470000)
+#define GCOV_TAG_CONDS_LENGTH(NUM) ((NUM) * 2 * GCOV_WORD_SIZE)
+#define GCOV_TAG_CONDS_NUM(LENGTH) (((LENGTH) / GCOV_WORD_SIZE) / 2)
#define GCOV_TAG_LINES ((gcov_unsigned_t)0x01450000)
#define GCOV_TAG_COUNTER_BASE ((gcov_unsigned_t)0x01a10000)
#define GCOV_TAG_COUNTER_LENGTH(NUM) ((NUM) * 2 * GCOV_WORD_SIZE)
@@ -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. */
@@ -1158,6 +1206,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);
}
@@ -1982,6 +2069,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 ();
@@ -2112,6 +2221,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);
@@ -2456,6 +2580,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. */
@@ -2559,6 +2692,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");
}
}
@@ -2793,6 +2938,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
@@ -2894,6 +3045,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. */
@@ -3104,16 +3286,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);
+ }
}
}
@@ -682,7 +682,7 @@ can_early_inline_edge_p (struct cgraph_edge *e)
}
gcc_assert (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
&& gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)));
- if (profile_arc_flag
+ if ((profile_arc_flag || profile_condition_flag)
&& ((lookup_attribute ("no_profile_instrument_function",
DECL_ATTRIBUTES (caller->decl)) == NULL_TREE)
!= (lookup_attribute ("no_profile_instrument_function",
@@ -1930,7 +1930,7 @@ pass_split_functions::gate (function *)
/* When doing profile feedback, we want to execute the pass after profiling
is read. So disable one in early optimization. */
return (flag_partial_inlining
- && !profile_arc_flag && !flag_branch_probabilities);
+ && !profile_arc_flag && !flag_branch_probabilities);
}
} // anon namespace
@@ -352,7 +352,8 @@ finish_optimization_passes (void)
gcc::dump_manager *dumps = m_ctxt->get_dumps ();
timevar_push (TV_DUMP);
- if (profile_arc_flag || flag_test_coverage || flag_branch_probabilities)
+ if (profile_arc_flag || profile_condition_flag || flag_test_coverage
+ || flag_branch_probabilities)
{
dumps->dump_start (pass_profile_1->static_pass_number, NULL);
end_branch_prob ();
@@ -66,9 +66,19 @@ along with GCC; see the file COPYING3. If not see
#include "cfgloop.h"
#include "sreal.h"
#include "file-prefix-map.h"
+#include "stringpool.h"
#include "profile.h"
+struct condcov;
+struct condcov *find_conditions (struct function*);
+size_t cov_length (const struct condcov*);
+array_slice<basic_block> cov_graphs (struct condcov*, size_t);
+array_slice<uint64_t> cov_masks (struct condcov*, size_t);
+void cov_free (struct condcov*);
+size_t instrument_decisions (array_slice<basic_block>, size_t,
+ array_slice<gcov_type_unsigned>);
+
/* Map from BBs/edges to gcov counters. */
vec<gcov_type> bb_gcov_counts;
hash_map<edge,gcov_type> *edge_gcov_counts;
@@ -100,6 +110,7 @@ static int total_num_passes;
static int total_num_times_called;
static int total_hist_br_prob[20];
static int total_num_branches;
+static int total_num_conds;
/* Forward declarations. */
static void find_spanning_tree (struct edge_list *);
@@ -1155,6 +1166,12 @@ read_thunk_profile (struct cgraph_node *node)
the flow graph that are needed to reconstruct the dynamic behavior of the
flow graph. This data is written to the gcno file for gcov.
+ When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
+ edges in the control flow graph to track what conditions are evaluated to in
+ order to determine what conditions are covered and have an independent
+ effect on the outcome (modified condition/decision coverage). This data is
+ written to the gcno file for gcov.
+
When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
information from the gcda file containing edge count information from
previous executions of the function being compiled. In this case, the
@@ -1173,6 +1190,7 @@ branch_prob (bool thunk)
struct edge_list *el;
histogram_values values = histogram_values ();
unsigned cfg_checksum, lineno_checksum;
+ bool output_to_file;
total_num_times_called++;
@@ -1239,6 +1257,9 @@ branch_prob (bool thunk)
basic_block new_bb = split_edge (e);
edge ne = single_succ_edge (new_bb);
ne->goto_locus = e->goto_locus;
+ /* Mark the edge with IGNORE so condition coverage knows that
+ the edge split occurred and this should be contracted. */
+ ne->flags |= EDGE_IGNORE;
}
if ((e->flags & (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL))
&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
@@ -1397,10 +1418,18 @@ branch_prob (bool thunk)
/* Write the data from which gcov can reconstruct the basic block
graph and function line numbers (the gcno file). */
+ output_to_file = false;
if (coverage_begin_function (lineno_checksum, cfg_checksum))
{
gcov_position_t offset;
+ /* The condition coverage needs a deeper analysis to identify expressions
+ of conditions, which means it is not yet ready to write to the gcno
+ file. It will write its entries later, but needs to know if it do it
+ in the first place, which is controlled by the return value of
+ coverage_begin_function. */
+ output_to_file = true;
+
/* Basic block flags */
offset = gcov_write_tag (GCOV_TAG_BLOCKS);
gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
@@ -1514,29 +1543,68 @@ branch_prob (bool thunk)
remove_fake_edges ();
+ if (profile_condition_flag || profile_arc_flag)
+ gimple_init_gcov_profiler ();
+
+ if (profile_condition_flag)
+ {
+ struct condcov *cov = find_conditions (cfun);
+ gcc_assert (cov);
+ const size_t nconds = cov_length (cov);
+ total_num_conds += nconds;
+
+ if (coverage_counter_alloc (GCOV_COUNTER_CONDS, 2 * nconds))
+ {
+ gcov_position_t offset {};
+ if (output_to_file)
+ offset = gcov_write_tag (GCOV_TAG_CONDS);
+
+ for (size_t i = 0; i != nconds; ++i)
+ {
+ array_slice<basic_block> expr = cov_graphs (cov, i);
+ array_slice<uint64_t> masks = cov_masks (cov, i);
+ gcc_assert (expr.is_valid ());
+ gcc_assert (masks.is_valid ());
+
+ size_t terms = instrument_decisions (expr, i, masks);
+ if (output_to_file)
+ {
+ gcov_write_unsigned (expr.front ()->index);
+ gcov_write_unsigned (terms);
+ }
+ }
+ if (output_to_file)
+ gcov_write_length (offset);
+ }
+ cov_free (cov);
+ }
+
/* For each edge not on the spanning tree, add counting code. */
if (profile_arc_flag
&& coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
{
unsigned n_instrumented;
- gimple_init_gcov_profiler ();
-
n_instrumented = instrument_edges (el);
gcc_assert (n_instrumented == num_instrumented);
if (flag_profile_values)
instrument_values (values);
-
- /* Commit changes done by instrumentation. */
- gsi_commit_edge_inserts ();
}
free_aux_for_edges ();
values.release ();
free_edge_list (el);
+ /* Commit changes done by instrumentation. */
+ gsi_commit_edge_inserts ();
+
+ /* Unset all EDGE_IGNORE set in this pass. */
+ FOR_EACH_BB_FN (bb, cfun)
+ for (edge e : bb->succs)
+ e->flags &= ~EDGE_IGNORE;
+
coverage_end_function (lineno_checksum, cfg_checksum);
if (flag_branch_probabilities
&& (profile_status_for_fn (cfun) == PROFILE_READ))
@@ -1669,6 +1737,7 @@ init_branch_prob (void)
total_num_passes = 0;
total_num_times_called = 0;
total_num_branches = 0;
+ total_num_conds = 0;
for (i = 0; i < 20; i++)
total_hist_br_prob[i] = 0;
}
@@ -1708,5 +1777,7 @@ end_branch_prob (void)
(total_hist_br_prob[i] + total_hist_br_prob[19-i]) * 100
/ total_num_branches, 5*i, 5*i+5);
}
+ fprintf (dump_file, "Total number of conditions: %d\n",
+ total_num_conds);
}
}
new file mode 100644
@@ -0,0 +1,246 @@
+/* { dg-options "--coverage -fprofile-conditions -std=c++11" } */
+/* { dg-do run { target native } } */
+
+#include <vector>
+#include <stdexcept>
+
+class nontrivial_destructor
+{
+public:
+ explicit nontrivial_destructor (int v) : val (v) {}
+ ~nontrivial_destructor () {}
+
+ explicit operator bool() const { return bool(val); }
+
+ int val;
+};
+
+int identity (int x) { return x; }
+int throws (int) { throw std::runtime_error("exception"); }
+
+int
+throw_if (int x)
+{
+ if (x) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ throw std::runtime_error("exception");
+ return x;
+}
+
+/* used for side effects to insert nodes in conditional bodies etc. */
+int x = 0;
+
+/* conditionals work in the presence of non-trivial destructors */
+void
+mcdc001a (int a)
+{
+ nontrivial_destructor v (a);
+
+ if (v.val > 0) /* conditions(2/2) */
+ x = v.val;
+ else
+ x = -v.val;
+}
+
+/* non-trivial destructor in-loop temporary */
+nontrivial_destructor
+mcdc002a (int a, int b)
+{
+ for (int i = 0; i < a; i++) /* conditions(2/2) */
+ {
+ nontrivial_destructor tmp (a);
+ if (tmp.val % b) /* conditions(2/2) */
+ return nontrivial_destructor (0);
+ x += i;
+ } /* conditions(suppress) */
+ /* conditions(end) */
+
+ return nontrivial_destructor (a * b);
+}
+
+/* conditional in constructor */
+void
+mcdc003a (int a)
+{
+ class C
+ {
+ public:
+ explicit C (int e) : v (e)
+ {
+ if (e) /* conditions(1/2) false(0) */
+ v = x - e;
+ }
+ int v;
+ };
+
+ C c (a);
+ if (c.v > 2) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = c.v + a;
+}
+
+/* conditional in destructor */
+void
+mcdc004a (int a)
+{
+ class C
+ {
+ public:
+ explicit C (int e) : v (e) {}
+ ~C ()
+ {
+ if (v) /* conditions(2/2) */
+ x = 2 * v;
+ }
+ int v;
+ };
+
+ C c (a);
+ x = 1; // arbitrary action between ctor+dtor
+}
+
+/* conditional in try */
+void
+mcdc005a (int a)
+{
+ try
+ {
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = 2 * identity (a);
+ else
+ x = 1;
+ }
+ catch (...)
+ {
+ x = 0;
+ }
+}
+
+/* conditional in catch */
+void
+mcdc006a (int a) {
+ try
+ {
+ throws (a);
+ }
+ catch (std::exception&)
+ {
+ if (a) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ x = identity (a);
+ else
+ x = 0;
+ }
+}
+
+void
+mcdc006b (int a)
+{
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ throws (a);
+ else
+ x = 1;
+}
+
+void
+mcdc006c (int a) try
+{
+ throws (a);
+}
+catch (...) {
+ if (a) /* conditions(2/2) */
+ x = 5;
+}
+
+/* temporary with destructor as term */
+void
+mcdc007a (int a, int b)
+{
+ x = a && nontrivial_destructor (b); /* conditions(3/4) false(1) destructor() */
+}
+
+void
+mcdc007b (int a, int b)
+{
+ if (a || throw_if (b)) /* conditions(3/4) true(1) destructor() */
+ x = -1;
+ else
+ x = 1;
+}
+
+void
+mcdc007c (int a, int b)
+{
+ if (throw_if (a) || throw_if (b)) /* conditions(2/4) true(0 1) destructor() */
+ x = -1;
+ else
+ x = 1;
+}
+
+/* destructor with delete */
+void
+mcdc008a (int a)
+{
+ class C
+ {
+ public:
+ int size = 5;
+ int* ptr = nullptr;
+
+ explicit C (int v) : size (v + 5), ptr (new int[size]) /* conditions(suppress) */
+ /* conditions(end) */
+ {
+ for (int i = 0; i < size; i++) /* conditions(2/2) */
+ ptr[i] = i + 1;
+ }
+ ~C()
+ {
+ // delete with implicit nullptr check
+ delete ptr; /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ }
+ };
+
+ C c (a);
+ if (c.ptr[a + 1]) /* conditions(1/2) false(0) */
+ x = a;
+}
+
+int
+main (void)
+{
+ mcdc001a (0);
+ mcdc001a (1);
+
+ mcdc002a (1, 1);
+ mcdc002a (1, 2);
+
+ mcdc003a (1);
+
+ mcdc004a (0);
+ mcdc004a (1);
+
+ mcdc005a (0);
+
+ mcdc006a (1);
+
+ mcdc006b (0);
+
+ mcdc006c (0);
+ mcdc006c (1);
+
+ mcdc007a (0, 0);
+ mcdc007a (1, 1);
+
+ mcdc007b (0, 0);
+ mcdc007b (1, 0);
+
+ mcdc007c (0, 0);
+
+ mcdc008a (1);
+
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-18.C } } } */
new file mode 100644
@@ -0,0 +1,1471 @@
+/* { dg-options "-fprofile-conditions -ftest-coverage" } */
+/* { dg-do run { target native } } */
+
+/* some side effect to stop branches from being pruned */
+int x = 0;
+
+int id (int x) { return x; }
+int inv (int x) { return !x; }
+
+/* || works */
+void
+mcdc001a (int a, int b)
+{
+ if (a || b) /* conditions(1/4) true(0) false(0 1) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc001b (int a, int b)
+{
+ if (a || b) /* conditions(3/4) true(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc001c (int a, int b)
+{
+ if (a || b) /* conditions(4/4) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc001d (int a, int b, int c)
+{
+ if (a || b || c) /* conditions(2/6) false(0 1 2) true(2) */
+ /* conditions(end) */
+ x = 1;
+}
+
+/* && works */
+void
+mcdc002a (int a, int b)
+{
+ if (a && b) /* conditions(1/4) true(0 1) false(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc002b (int a, int b)
+{
+ if (a && b) /* conditions(3/4) false(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc002c (int a, int b)
+{
+ if (a && b) /* conditions(4/4) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc002d (int a, int b, int c)
+{
+ if (a && b && c) /* conditions(4/6) false(0 2) */
+ /* conditions(end) */
+ x = 1;
+}
+
+/* negation works */
+void
+mcdc003a (int a, int b)
+{
+ if (!a || !b) /* conditions(2/4) false(0 1) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+/* single conditionals with and without else */
+void
+mcdc004a (int a)
+{
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc004b (int a)
+{
+ if (a) /* conditions(2/2) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc004c (int a)
+{
+ if (a) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ x = 1;
+}
+
+void
+mcdc004d (int a, int b, int c)
+{
+ /* With no else this is interpreted as (a && (b || c)) */
+ if (a) /* conditions(3/6) true(2) false(1 2)*/
+ {
+ if (b || c)
+ x = a + b + c;
+ }
+}
+
+void
+mcdc004e (int a, int b, int c)
+{
+ /* With the else, this is interpreted as 2 expressions */
+ if (a) /* conditions(2/2) */
+ {
+ if (b || c) /* conditions(1/4) true(1) false(0 1) */
+ /* conditions(end) */
+ x = a + b + c;
+ }
+ else
+ {
+ x = c;
+ }
+}
+
+/* else-if is not immune to the else-less fuse. This test is also put in as a
+ * detection mechanism - sif this should register as 3 individual decisions
+ * then the test should be updated and fixed to reflect it. */
+int
+mcdc004f (int a, int b, int c)
+{
+ if (a) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ x = 1;
+ }
+ else if (b) /* conditions(0/4) true(0 1) false(0 1) */
+ /* conditions(end) */
+ {
+ x = 2;
+ if (c)
+ x = 3;
+ }
+}
+
+/* mixing && and || works */
+void
+mcdc005a (int a, int b, int c)
+{
+ if ((a && b) || c) /* conditions(1/6) true(0 1) false(0 1 2) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc005b (int a, int b, int c, int d)
+{
+ /* This is where masking MC/DC gets unintuitive:
+
+ 1 1 0 0 => covers 1 (d = 0) as && 0 masks everything to the left
+ 1 0 0 0 => covers 2 (b = 0, c = 0) as (a && 0) masks a and d is never
+ evaluated. */
+ if ((a && (b || c)) && d) /* conditions(3/8) true(0 1 2 3) false(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc005c (int a, int b, int c, int d)
+{
+ if (a || (b && c) || d) /* conditions(2/8) true(0 3) false(0 1 2 3) */
+ /* conditions(end) */
+ x = a + b + c + d;
+}
+
+void
+mcdc005d (int a, int b, int c, int d)
+{
+ /* This test is quite significant - it has a single input
+ (1, 0, 0, 0) and tests specifically for when a multi-term left operand
+ is masked. d = 0 should mask a || b and for the input there are no other
+ sources for masking a (since b = 0). */
+ if ((a || b) && (c || d)) /* conditions(2/8) true(0 1 2 3) false(0 1) */
+ /* conditions(end) */
+ x = a + b;
+ else
+ x = c + d;
+}
+
+/* nested conditionals */
+void
+mcdc006a (int a, int b, int c, int d, int e)
+{
+ if (a) /* conditions(2/2) */
+ {
+ if (b && c) /* conditions(3/4) false(1) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+ }
+ else
+ {
+ if (c || d) /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+ x = 3;
+ else
+ x = 4;
+ }
+}
+
+void
+mcdc006b (int a, int b, int c)
+{
+ if (a) /* conditions(6/6) */
+ if (b)
+ if (c)
+ x = a + b + c;
+}
+
+void
+mcdc006c (int a, int b, int c)
+{
+ if (a) /* conditions(2/2) */
+ {
+ if (b) /*conditions(2/2) */
+ {
+ if (c) /* conditions(2/2) */
+ {
+ x = a + b + c;
+ }
+ }
+ else
+ {
+ x = b;
+ }
+ }
+ else
+ {
+ x = a;
+ }
+}
+
+/* else/if */
+void
+mcdc007a (int a, int b, int c, int d)
+{
+ if (a) /* conditions(2/2) */
+ {
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+ }
+ else if (c) /* conditions(2/2) */
+ {
+ if (d) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = 3;
+ else
+ x = 4;
+ }
+}
+
+void
+mcdc007b (int a, int b, int c)
+{
+ goto begin;
+then:
+ x = 1;
+ return;
+begin:
+ /* Evaluates to if (a || b || c) x = 1 */
+ if (a) /* conditions(2/2) */
+ goto then;
+ else if (b) /* conditions(2/2) */
+ goto then;
+ else if (c) /* conditions(1/2) true(0) */
+ goto then;
+}
+
+void
+mcdc007c (int a, int b, int c)
+{
+ goto begin;
+then1:
+ x = 1;
+ return;
+then2:
+ x = 1;
+ return;
+then3:
+ x = 1;
+ return;
+begin:
+ /* similar to if (a || b || c) x = 1 */
+ if (a) /* conditions(2/2) */
+ goto then1;
+ else if (b) /* conditions(2/2) */
+ goto then2;
+ else if (c) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ goto then3;
+}
+
+void
+noop () {}
+
+int
+mcdc007d (int a, int b, int c, int d, int e)
+{
+ noop ();
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b || c) /* conditions(0/4) true(0 1) false(0 1) */
+ /* conditions(end) */
+ x = 2;
+ if (d) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 1;
+ }
+ if (e) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ return 0;
+
+ return 2;
+}
+
+/* while loop */
+void
+mcdc008a (int a)
+{
+ while (a < 10) /* conditions(2/2) */
+ x = a++;
+}
+
+void
+mcdc008b (int a)
+{
+ while (a > 10) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = a--;
+}
+
+void
+mcdc008c (int a)
+{
+ // should work, even with no body
+ while (a) /* conditions(2/2) */
+ break;
+}
+
+void
+mcdc008d (int a, int b, int c, int d)
+{
+ /* multi-term loop conditional */
+ while ((a && (b || c)) && d) /* conditions(8/8) */
+ a = b = c = d = 0;
+}
+
+void
+mcdc009a (int a, int b)
+{
+ while (a > 0 && b > 0) /* conditions(3/4) false(1) */
+ /* conditions(end) */
+ x = a--;
+}
+
+/* Multi-term loop condition with empty body, which can give neighborhoods of
+ size 1. */
+void
+mcdc009b (int a, int b)
+{
+ while (a-- > 0 && b) {} /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+}
+
+/* for loop */
+void
+mcdc010a (int a, int b)
+{
+ for (int i = 0; i < b; i++) /* conditions(2/2) */
+ {
+ if (a < b) /* conditions(2/2) */
+ x = 1;
+ else
+ x = a += 2;
+ }
+}
+
+void
+mcdc010b ()
+{
+ for (int a = 0; a <= 1; ++a) /* conditions(2/2) */
+ {
+ x = a;
+ }
+}
+
+int always (int x) { (void) x; return 1; }
+
+/* no-condition infinite loops */
+void
+mcdc010c (int a)
+{
+ for (;;)
+ {
+ if (always(a)) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ x = a;
+ break;
+ }
+ x += a + 1;
+ }
+}
+
+/* conditionals without control flow constructs work */
+void
+mcdc011a (int a, int b, int c)
+{
+ x = (a && b) || c; /* conditions(5/6) false(1) */
+ /* conditions(end) */
+}
+
+/* sequential expressions are handled independently */
+void
+mcdc012a (int a, int b, int c)
+{
+ if (a || b) /* conditions(3/4) true(0) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+
+ if (c) /* conditions(2/2) */
+ x = 1;
+}
+
+/* Cannot ever satisfy (masking) MC/DC, even with all input combinations,
+ because not all variables independently affect the decision. */
+void
+mcdc013a (int a, int b, int c)
+{
+ (void)b;
+ /* Specification: (a && b) || c
+ The implementation does not match the specification. This has branch
+ coverage, but not MC/DC. */
+ if ((a && !c) || c) /* conditions(5/6) false(1) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+void
+mcdc014a ()
+{
+ int conds[64] = { 0 };
+ /* conditions(64/128) true(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63) */
+ x = conds[ 0] || conds[ 1] || conds[ 2] || conds[ 3] || conds[ 4] ||
+ conds[ 5] || conds[ 6] || conds[ 7] || conds[ 8] || conds[ 9] ||
+ conds[10] || conds[11] || conds[12] || conds[13] || conds[14] ||
+ conds[15] || conds[16] || conds[17] || conds[18] || conds[19] ||
+ conds[20] || conds[21] || conds[22] || conds[23] || conds[24] ||
+ conds[25] || conds[26] || conds[27] || conds[28] || conds[29] ||
+ conds[30] || conds[31] || conds[32] || conds[33] || conds[34] ||
+ conds[35] || conds[36] || conds[37] || conds[38] || conds[39] ||
+ conds[40] || conds[41] || conds[42] || conds[43] || conds[44] ||
+ conds[45] || conds[46] || conds[47] || conds[48] || conds[49] ||
+ conds[50] || conds[51] || conds[52] || conds[53] || conds[54] ||
+ conds[55] || conds[56] || conds[57] || conds[58] || conds[59] ||
+ conds[60] || conds[61] || conds[62] || conds[63]
+ ; /* conditions(end) */
+}
+
+/* early returns */
+void
+mcdc015a (int a, int b)
+{
+ if (a) /* conditions(2/2) */
+ return;
+
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x = 1;
+}
+
+void
+mcdc015b (int a, int b)
+{
+ for (int i = 5; i > a; i--) /* conditions(2/2) */
+ {
+ if (i == b) /* conditions(2/2) */
+ return;
+ x = i;
+ }
+}
+
+void
+mcdc015c (int a, int b)
+{
+ for (int i = 5; i > a; i--) /* conditions(2/2) */
+ {
+ if (i == b) /* conditions(2/2) */
+ {
+ x = 0;
+ return;
+ }
+ else
+ {
+ x = 1;
+ return;
+ }
+
+ x = i;
+ }
+}
+
+/* Early returns, gotos can create candidate sets where the neighborhood
+ internally shares dominator nodes that are not the first-in-expression which
+ implies the neighborhood belongs to some other boolean expression. When
+ this happens, the candidate set must be properly tidied up. */
+void
+mcdc015d (int a, int b, int c)
+{
+ if (a) return; /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ if (id (b)) return; /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ if (id (c)) return; /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+}
+
+
+/* check nested loops */
+void
+mcdc016a (int a, int b)
+{
+ for (int i = 0; i < a; i++) /* conditions(2/2) */
+ for (int k = 0; k < b; k++) /* conditions(2/2) */
+ x = i + k;
+}
+
+void
+mcdc016b (int a, int b)
+{
+ for (int i = 0; i < a; i++) /* conditions(2/2) */
+ {
+ if (a > 5) /* conditions(2/2) */
+ break;
+
+ for (int k = 0; k < b; k++) /* conditions(2/2) */
+ x = i + k;
+ }
+}
+
+void
+mcdc016c (int a, int b)
+{
+ for (int i = 0; i < a; i++) /* conditions(2/2) */
+ {
+ if (a > 5) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ return;
+
+ for (int k = 0; k < b; k++) /* conditions(2/2) */
+ x = i + k;
+ }
+}
+
+void
+mcdc016d (int a, int b)
+{
+ for (int i = 0; i < a; i++) /* conditions(2/2) */
+ {
+ for (int k = 0; k < 5; k++) /* conditions(2/2) */
+ {
+ if (b > 5) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ return;
+ x = i + k;
+ }
+
+ }
+}
+
+/* do-while loops */
+void
+mcdc017a (int a)
+{
+ do
+ {
+ a--;
+ } while (a > 0); /* conditions(2/2) */
+}
+
+void
+mcdc017b (int a, int b)
+{
+ do
+ {
+ /*
+ * This call is important; it can add more nodes to the body in the
+ * CFG, which has changes how close exits and breaks are to the loop
+ * conditional.
+ */
+ noop ();
+ a--;
+ if (b) /* conditions(2/2) */
+ break;
+
+ } while (a > 0); /* conditions(2/2) */
+}
+
+void
+mcdc017c (int a, int b)
+{
+ int left = 0;
+ int right = 0;
+ int n = a + b;
+ do
+ {
+ if (a) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ left = a > left ? b : left; /* conditions(2/2) */
+ }
+ if (b) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ right = b > right ? a : right; /* conditions(2/2) */
+ }
+ } while (n-- > 0); /* conditions(2/2) */
+}
+
+/* collection of odd cases lifted-and-adapted from real-world code */
+int mcdc018a (int a, int b, int c, int d, int e, int f, int g, int len)
+{
+ int n;
+ /* adapted from zlib/gz_read */
+ do
+ {
+ n = -1;
+ if (n > len) /* conditions(2/2) */
+ n = len;
+
+ if (b) /* conditions(2/2) */
+ {
+ if (b < 5) /* conditions(2/2) */
+ x = 1;
+ noop();
+ }
+ else if (c && d) /* conditions(3/4) false(1) */
+ {
+ x = 2;
+ break;
+ }
+ else if (e || f) /* conditions(2/4) false(0 1) */
+ /* conditions(end) */
+ {
+ if (id(g)) /* conditions(2/2) */
+ return 0;
+ continue;
+ }
+ } while (a-- > 0); /* conditions(2/2) */
+
+ return 1;
+}
+
+void
+mcdc018b (int a, int b, int c)
+{
+ int n;
+ while (a) /* conditions(2/2) */
+ {
+ /* else block does not make a difference for the problem, but ensures
+ loop termination. */
+ if (b) /* conditions(2/2) */
+ n = c ? 0 : 0; // does not show up in CFG (embedded in the block)
+ else
+ n = 0;
+ a = n;
+ }
+}
+
+/* Adapted from zlib/compress2 */
+void
+mcdc018c (int a, int b)
+{
+ int err;
+ do
+ {
+ a = inv (a);
+ err = a;
+ } while (err); /* conditions(1/2) true(0) */
+ /* conditions(end) */
+
+ a = id (a);
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ x *= a + 1;
+}
+
+/* too many conditions, coverage gives up */
+void
+mcdc019a ()
+{
+ int conds[65] = { 0 };
+ #pragma GCC diagnostic push
+ #pragma GCC diagnostic ignored "-Wcoverage-too-many-conditions"
+ x = conds[ 0] || conds[ 1] || conds[ 2] || conds[ 3] || conds[ 4] ||
+ conds[ 5] || conds[ 6] || conds[ 7] || conds[ 8] || conds[ 9] ||
+ conds[10] || conds[11] || conds[12] || conds[13] || conds[14] ||
+ conds[15] || conds[16] || conds[17] || conds[18] || conds[19] ||
+ conds[20] || conds[21] || conds[22] || conds[23] || conds[24] ||
+ conds[25] || conds[26] || conds[27] || conds[28] || conds[29] ||
+ conds[30] || conds[31] || conds[32] || conds[33] || conds[34] ||
+ conds[35] || conds[36] || conds[37] || conds[38] || conds[39] ||
+ conds[40] || conds[41] || conds[42] || conds[43] || conds[44] ||
+ conds[45] || conds[46] || conds[47] || conds[48] || conds[49] ||
+ conds[50] || conds[51] || conds[52] || conds[53] || conds[54] ||
+ conds[55] || conds[56] || conds[57] || conds[58] || conds[59] ||
+ conds[60] || conds[61] || conds[62] || conds[63] || conds[64]
+ ;
+ #pragma GCC diagnostic pop
+}
+
+/* ternary */
+void
+mcdc020a (int a)
+{
+ // special case, this can be reduced to:
+ // _1 = argc != 0;
+ // e = (int) _1;
+ x = a ? 1 : 0;
+
+ // changing to different int makes branch
+ x = a ? 2 : 1; /* conditions(2/2) */
+}
+
+void
+mcdc020b (int a, int b)
+{
+ x = (a || b) ? 1 : 0; /* conditions(3/4) true(1) */
+ /* conditions(end) */
+}
+
+void
+mcdc020c (int a, int b)
+{
+ x = a ? 0
+ : b ? 1 /* conditions(2/2) */
+ : 2; /* conditions(1/2) false(0) */
+ /* conditions(end) */
+}
+
+/* Infinite loop (no exit-edge), this should not be called, but it should
+ compile fine */
+void
+mcdc021a ()
+{
+ while (1)
+ ;
+}
+
+/* Computed goto can give all sorts of problems, including difficult path
+ contractions. */
+void
+mcdc021b ()
+{
+ void *op = &&dest;
+dest:
+ if (op) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ goto * 0;
+}
+
+int __sigsetjmp ();
+
+/* This should compile, but not called. */
+void
+mcdc021c ()
+{
+ while (x) /* conditions(0/2) true(0) false(0)*/
+ /* conditions(end) */
+ __sigsetjmp ();
+}
+
+/* If edges are not properly contracted the a && id (b) will be interpreted as
+ two independent expressions. */
+void
+mcdc021d (int a, int b, int c, int d)
+{
+ if (a && id (b)) /* conditions(1/4) true(0 1) false(0) */
+ /* conditions(end) */
+ x = 1;
+ else if (c && id (d)) /* conditions(1/4) true(0 1) false(0) */
+ /* conditions(end) */
+ x = 2;
+ else
+ x = 3;
+}
+
+/* Adapted from linux arch/x86/tools/relocs.c
+ With poor edge contracting this became an infinite loop. */
+void
+mcdc022a (int a, int b)
+{
+ for (int i = 0; i < 5; i++) /* conditions(2/2) */
+ {
+ x = i;
+ for (int j = i; j < 5; j++) /* conditions(2/2) */
+ {
+ if (id (id (a)) || id (b)) /* conditions(3/4) true(0) */
+ /* conditions(end) */
+ continue;
+ b = inv(b);
+ }
+ }
+}
+
+int
+mcdc022b (int a)
+{
+ int devt;
+ if (a) /* conditions(2/2) */
+ {
+ x = a * 2;
+ if (x != a / 10 || x != a % 10) /* conditions(1/4) true(1) false(0 1) */
+ /* conditions(end) */
+ return 0;
+ } else {
+ devt = id (a);
+ if (devt) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ return 0;
+ }
+
+ return devt;
+}
+
+/* Adapted from linux arch/x86/events/intel/ds.c
+
+ It broken sorting so that the entry block was not the first node after
+ sorting. */
+void
+mcdc022c (int a)
+{
+ if (!a) /* conditions(2/2) */
+ return;
+
+ for (int i = 0; i < 5; i++) /* conditions(2/2) */
+ {
+ if (id (a + i) || inv (a - 1)) /* conditions(1/4) false(0 1) true(1) */
+ /* conditions(end) */
+ x = a + i;
+ if (inv (a)) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ break;
+ }
+}
+
+void
+mcdc022d (int a)
+{
+ int i;
+ for (i = 0; i < id (a); i++) /* conditions(1/2) false(0) */
+ {
+ if (!inv (a)) /* conditions(1/2) false(0)*/
+ /* conditions(end) */
+ break;
+ }
+
+ if (i < a) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ x = a + 1;
+}
+
+/* Adapted from openssl-3.0.1/crypto/cmp/cmp_msg.c ossl_cmp_error_new ().
+ Without proper limiting of the initial candidate search this misidentified
+ { ...; if (fn ()) goto err; } if (c) goto err; as a 2-term expression. */
+void
+mcdc022e (int a, int b, int c, int d)
+{
+ if (a || b) /* conditions(1/4) true(0) false(0 1) */
+ /* conditions(end) */
+ {
+ if (always (c)) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ goto err;
+ }
+
+ if (d) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ goto err;
+ return;
+
+err:
+ noop ();
+}
+
+/* 023 specifically tests that masking works correctly, which gets complicated
+ fast with a mix of operators and deep subexpressions. These tests violates
+ the style guide slightly to emphasize the nesting. They all share the same
+ implementation and only one input is given to each function to obtain clean
+ coverage results. */
+void
+mcdc023a (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ // [a m n] = 0, [b, ...] = 1
+ // a is masked by b and the remaining terms should be short circuited
+ if (/* conditions(1/24) true(0 2 3 4 5 6 7 8 9 10 11) false(0 1 2 3 4 5 6 7 8 9 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023b (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ // [a b d h] = 0, [c, ...] = 1
+ // h = 0 => false but does not mask (a || b) or (c && d). d = 0 masks c.
+ if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 4 5 6 8 9 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023c (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ /* [m n a b] = 0, [...] = 1
+ n,m = 0 should mask all other terms than a, b */
+ if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 3 4 5 6 7 8 9) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023d (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ /* [a b] = 0, [h, ...] = 1
+ n,m = 0 should mask all other terms than a, b */
+ if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 3 4 5 6 7 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023e (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ /* [a b d] = 0, [c h, ...] = 1
+ h = 1 should mask c, d, leave other terms intact.
+ If [k l m n] were false then h itself would be masked.
+ [a b] are masked as collateral by [m n]. */
+ if (/* conditions(5/24) true(0 1 2 3 6 9 11) false(0 1 2 3 4 5 6 7 8 9 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023f (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ /* [a b c f g] = 0, [e, ...] = 1
+ [f g] = 0 should mask e, leave [c d] intact. */
+ if (/* conditions(5/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(3 4 7 8 9 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+void
+mcdc023g (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+ int l, int m, int n)
+{
+ /* [a b d f g] = 0, [e c, ...] = 1
+ Same as 023f but with [c d] flipped so d masks c rather than c
+ short-circuits. This should not be lost. */
+ if (/* conditions(5/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 4 7 8 9 10 11) */
+ /* conditions(end) */
+ (a || b)
+ || ( ((c && d) || (e && (f || g) && h))
+ && (k || l)
+ && (m || n)))
+ x = a + b;
+ else
+ x = b + c;
+}
+
+/* Gotos, return, labels can make odd graphs. It is important that conditions
+ are assigned to the right expression, and that there are no miscounts. In
+ these tests values may be re-used, as checking things like masking an
+ independence is done in other test cases and not so useful here. */
+void
+mcdc024a (int a, int b)
+{
+ if (a && b) /* conditions(1/4) true(0 1) false(1) */
+ /* conditions(end) */
+ {
+label1:
+ x = 1;
+ }
+ else
+ {
+ x = 2;
+ }
+
+ if (a || b) /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+ {
+label2:
+ x = 1;
+ }
+ else
+ {
+ x = 2;
+ }
+}
+
+void
+mcdc024b (int a, int b)
+{
+
+ if (a && b) /* conditions(1/4) true(0 1) false(1) */
+ /* conditions(end) */
+ {
+ x = 1;
+ }
+ else
+ {
+label1:
+ x = 2;
+ }
+
+ if (a || b) /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+ {
+ x = 1;
+ }
+ else
+ {
+label2:
+ x = 2;
+ }
+}
+
+void
+mcdc024c (int a, int b)
+{
+ if (a && b) /* conditions(1/4) true(0 1) false(1) */
+ /* conditions(end) */
+ {
+label1:
+ x = 1;
+ }
+ else
+ {
+label2:
+ x = 2;
+ }
+
+ if (a || b) /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+ {
+label3:
+ x = 1;
+ }
+ else
+ {
+label4:
+ x = 2;
+ }
+}
+
+int
+mcdc024d (int a, int b, int c)
+{
+ /* Graphs can get complicated with the innermost returns and else-less if,
+ so we must make sure these conditions are counted correctly. */
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (c) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 1;
+ else
+ return 2;
+ }
+
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 3;
+ }
+
+ return 5;
+}
+
+/* Nested else-less ifs with inner returns needs to be counted right, which
+ puts some pressure on the expression isolation. The fallthrough from inner
+ expressions into the next if cause the cfg to have edges from deeper in
+ subexpression to the next block sequence, which can confuse the expression
+ isolation. */
+int
+mcdc024e (int a, int b, int c)
+{
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (c) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 1;
+ else
+ return 2;
+ }
+
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 3;
+ }
+
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 4;
+ }
+ return 5;
+}
+
+int
+mcdc024f (int a, int b, int c)
+{
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ return 0;
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ b += 2;
+ if (b & 0xFF) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c++;
+
+ return c;
+ }
+ c += 10;
+ }
+}
+
+
+int
+mcdc024g (int a, int b, int c)
+{
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ goto inner;
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ ++a;
+
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+inner:
+ b += 2;
+ if (b & 0xFF) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c++;
+
+ return c;
+ }
+ c += 10;
+ }
+}
+
+int main ()
+{
+ mcdc001a (0, 1);
+
+ mcdc001b (0, 1);
+ mcdc001b (0, 0);
+
+ mcdc001c (0, 1);
+ mcdc001c (0, 0);
+ mcdc001c (1, 1);
+
+ mcdc001d (1, 1, 1);
+ mcdc001d (0, 1, 0);
+
+ mcdc002a (1, 0);
+
+ mcdc002b (1, 0);
+ mcdc002b (1, 1);
+
+ mcdc002c (0, 0);
+ mcdc002c (1, 1);
+ mcdc002c (1, 0);
+
+ mcdc002d (1, 1, 1);
+ mcdc002d (1, 0, 0);
+
+ mcdc003a (0, 0);
+ mcdc003a (1, 0);
+
+ mcdc004a (0);
+ mcdc004b (0);
+ mcdc004b (1);
+ mcdc004c (1);
+
+ mcdc004d (0, 0, 0);
+ mcdc004d (1, 1, 1);
+
+ mcdc004e (0, 0, 0);
+ mcdc004e (1, 1, 1);
+
+ mcdc004f (1, 1, 1);
+
+ mcdc005a (1, 0, 1);
+
+ mcdc005b (1, 1, 0, 0);
+ mcdc005b (1, 0, 0, 0);
+
+ mcdc005c (0, 1, 1, 0);
+
+ mcdc005d (1, 0, 0, 0);
+
+ mcdc006a (0, 0, 0, 0, 0);
+ mcdc006a (1, 0, 0, 0, 0);
+ mcdc006a (1, 1, 1, 0, 0);
+
+ mcdc006b (0, 0, 0);
+ mcdc006b (1, 0, 0);
+ mcdc006b (1, 1, 0);
+ mcdc006b (1, 1, 1);
+
+ mcdc006c (0, 0, 0);
+ mcdc006c (1, 0, 0);
+ mcdc006c (1, 1, 0);
+ mcdc006c (1, 1, 1);
+
+ mcdc007a (0, 0, 0, 0);
+ mcdc007a (1, 0, 0, 0);
+ mcdc007a (0, 0, 1, 0);
+
+ mcdc007b (0, 0, 0);
+ mcdc007b (0, 1, 1);
+ mcdc007b (1, 0, 1);
+
+ mcdc007c (0, 0, 0);
+ mcdc007c (0, 1, 1);
+ mcdc007c (1, 0, 1);
+
+ mcdc007d (0, 1, 0, 1, 1);
+
+ mcdc008a (0);
+
+ mcdc008b (0);
+
+ mcdc008c (0);
+ mcdc008c (1);
+
+ mcdc008d (0, 0, 0, 0);
+ mcdc008d (1, 0, 0, 0);
+ mcdc008d (1, 0, 1, 0);
+ mcdc008d (1, 0, 1, 1);
+ mcdc008d (1, 1, 1, 1);
+
+ mcdc009a (0, 0);
+ mcdc009a (1, 1);
+
+ mcdc009b (0, 0);
+ mcdc009b (1, 0);
+
+ mcdc010a (0, 0);
+ mcdc010a (0, 9);
+ mcdc010a (2, 1);
+
+ mcdc010b ();
+
+ mcdc010c (1);
+
+ mcdc011a (0, 0, 0);
+ mcdc011a (1, 1, 0);
+ mcdc011a (1, 0, 1);
+
+ mcdc012a (0, 0, 0);
+ mcdc012a (0, 1, 1);
+
+ mcdc013a (0, 0, 0);
+ mcdc013a (0, 0, 1);
+ mcdc013a (0, 1, 0);
+ mcdc013a (0, 1, 1);
+ mcdc013a (1, 0, 0);
+ mcdc013a (1, 0, 1);
+ mcdc013a (1, 1, 0);
+ mcdc013a (1, 1, 1);
+
+ mcdc014a ();
+
+ mcdc015a (0, 0);
+ mcdc015a (1, 0);
+
+ mcdc015b (0, 0);
+ mcdc015b (0, 1);
+ mcdc015b (6, 1);
+
+ mcdc015c (0, 0);
+ mcdc015c (0, 5);
+ mcdc015c (6, 1);
+
+ mcdc015d (1, 0, 0);
+
+ mcdc016a (5, 5);
+
+ mcdc016b (5, 5);
+ mcdc016b (6, 5);
+
+ mcdc016c (5, 5);
+
+ mcdc016d (1, 0);
+
+ mcdc017a (0);
+ mcdc017a (2);
+
+ mcdc017b (2, 0);
+ mcdc017b (0, 1);
+
+ mcdc017c (1, 1);
+
+ mcdc018a (0, 0, 1, 1, 0, 0, 0, 0);
+ mcdc018a (0, 1, 0, 0, 0, 0, 1, -2);
+ mcdc018a (0, 6, 0, 0, 0, 0, 1, -2);
+ mcdc018a (0, 6, 0, 0, 0, 0, 1, -2);
+ mcdc018a (0, 0, 0, 1, 0, 1, 1, 0);
+ mcdc018a (1, 0, 0, 0, 1, 1, 0, 0);
+
+ mcdc018b (1, 0, 0);
+ mcdc018b (1, 1, 0);
+
+ mcdc018c (1, 1);
+
+ mcdc019a ();
+
+ mcdc020a (0);
+ mcdc020a (1);
+
+ mcdc020b (0, 0);
+ mcdc020b (1, 0);
+
+ mcdc020c (0, 1);
+ mcdc020c (1, 1);
+
+ mcdc021d (1, 0, 1, 0);
+
+ mcdc022a (0, 0);
+
+ mcdc022b (0);
+ mcdc022b (1);
+
+ mcdc022c (0);
+ mcdc022c (1);
+
+ mcdc022d (1);
+ mcdc022e (0, 1, 1, 0);
+
+ mcdc023a (0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+ mcdc023b (0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1);
+ mcdc023c (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0);
+ mcdc023d (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1);
+ mcdc023e (0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+ mcdc023f (0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1);
+ mcdc023g (0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1);
+
+ mcdc024a (0, 0);
+ mcdc024b (0, 0);
+ mcdc024c (0, 0);
+ mcdc024d (0, 0, 0);
+ mcdc024e (0, 0, 0);
+ mcdc024f (0, 0, 0);
+ mcdc024g (0, 0, 0);
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-19.c } } } */
new file mode 100644
@@ -0,0 +1,22 @@
+/* { dg-options "-fprofile-conditions -ftest-coverage -fprofile-update=atomic" } */
+/* { dg-do run { target native } } */
+
+/* some side effect to stop branches from being pruned */
+int x = 0;
+
+void
+conditions_atomic001 (int a, int b)
+{
+ if (a || b) /* conditions(1/4) true(0) false(0 1) */
+ /* conditions(end) */
+ x = 1;
+ else
+ x = 2;
+}
+
+int main ()
+{
+ conditions_atomic001 (0, 1);
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-20.c } } } */
new file mode 100644
@@ -0,0 +1,16 @@
+/* { dg-options "-fprofile-conditions" } */
+
+/* https://gcc.gnu.org/pipermail/gcc-patches/2022-April/592927.html */
+char trim_filename_name;
+int r;
+
+void trim_filename() {
+ if (trim_filename_name)
+ r = 123;
+ while (trim_filename_name)
+ ;
+}
+
+int main ()
+{
+}
new file mode 100644
@@ -0,0 +1,71 @@
+/* { dg-options "-fprofile-conditions -ftest-coverage" } */
+/* { dg-do run { target native } } */
+
+#include <setjmp.h>
+jmp_buf buf;
+
+void noop() {}
+int identity(int x) { return x; }
+
+/* This function is a test to verify that the expression isolation does not
+ break on a CFG with the right set of complex edges. The (_ && setjmp)
+ created complex edges after the function calls and a circular pair of
+ complex edges around the setjmp call. This triggered a bug when the search
+ for right operands only would consider nodes dominated by the left-most
+ term, as this would only be the case if the complex edges were removed.
+
+ __builtin_setjmp did not trigger this, so we need setjmp from libc. */
+void
+setjmp001 (int a, int b, int c)
+{
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ noop ();
+
+ if (b) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ noop ();
+
+ if (c && setjmp (buf)) /* conditions(1/4) true(0 1) false(1) */
+ /* conditions(end) */
+ noop ();
+}
+
+/* Adapted from freetype-2.13.0 gxvalid/gxvmod.c classic_kern_validate */
+int
+setjmp002 (int a)
+{
+ int error = identity(a);
+
+ if (error) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ goto Exit;
+
+ if (a+1) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ noop ();
+ if (setjmp (buf)) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ noop ();
+
+ if (error) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ noop ();
+ }
+
+ error--;
+
+Exit:
+ return error;
+}
+
+int
+main ()
+{
+ setjmp001 (0, 1, 0);
+ setjmp002 (0);
+}
+
+
+/* { dg-final { run-gcov conditions { --conditions gcov-22.c } } } */
new file mode 100644
@@ -0,0 +1,197 @@
+/* { dg-options "-fprofile-conditions -ftest-coverage -O2 -c" } */
+
+#include <setjmp.h>
+jmp_buf buf;
+
+int id (int);
+int idp (int *);
+int err;
+char c;
+
+/* This becomes problematic only under optimization for the case when the
+ compiler cannot inline the function but have to generate a call. It is not
+ really interesting to run, only see if it builds. Notably, both the
+ function calls and the return values are important to construct a
+ problematic graph.
+
+ This test is also a good example of where optimization makes condition
+ coverage unpredictable, but not unusable. If this is built without
+ optimization the conditions work as you would expect from reading the
+ source. */
+/* Adapted from cpio-2.14 gnu/utmens.c lutimens (). */
+int
+mcdc001 (int *v)
+{
+ int adjusted;
+ int adjustment_needed = 0;
+
+ int *ts = v ? &adjusted : 0; /* conditions(0/4) true(0 1) false(0 1) */
+ /* conditions(end) */
+ if (ts)
+ adjustment_needed = idp (ts);
+ if (adjustment_needed < 0)
+ return -1;
+
+ if (adjustment_needed) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (adjustment_needed != 3) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return -1;
+ if (ts) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 0;
+ }
+
+ if (adjustment_needed && idp (&adjusted)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return -1;
+ if (adjusted) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return idp (ts);
+
+ return -1;
+}
+
+/* This failed when the candidate set internal/contracted-past nodes were not
+ properly marked as reachable in the candidate reduction phase. */
+/* Adapted from cpio-2.14 gnu/mktime.c mktime_internal (). */
+int
+mcdc002 ()
+{
+ int a;
+ if (idp (&a)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (id (a)) /* conditions(0/2) true(0/2) true(0) false(0) */
+ /* conditions(end) */
+ goto exit;
+
+ if (err) /* conditions(0/2) true(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return -1;
+ }
+
+exit:
+ return a;
+}
+
+/* Adapted from icu4c-73.1 common/ucase.cpp ucase_getCaseLocale (). */
+int
+mcdc003 (const char *locale)
+{
+ /* extern, so its effect won't be optimized out. */
+ c = *locale++;
+ if (c == 'z') /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ return 1;
+ }
+ else if (c >= 'a') /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (id (c)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c = *locale++;
+ }
+ else
+ {
+ if (c == 'T')
+ {
+ if (id (c)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c = *locale++;
+ if (id (c)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c = *locale++;
+ }
+ /* This may or may not become a jump table. */
+ else if (c == 'L') /* conditions(suppress) */
+ /* conditions(end) */
+ c = *locale++;
+ else if (c == 'E') /* conditions(suppress) */
+ /* conditions(end) */
+ c = *locale++;
+ else if (c == 'N') /* conditions(suppress) */
+ /* conditions(end) */
+ c = *locale++;
+ else if (c == 'H') /* conditions(suppress) */
+ /* conditions(end) */
+ {
+ c = *locale++;
+ if (id (c)) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c = *locale++;
+ }
+ }
+
+ return 1;
+}
+
+/* The || will be changed to |, so it is impractical to predict the number of
+ conditions. If the walk is not properly implemented this will not finish
+ compiling, so the actual coverage is not interesting. */
+/* Adapted from icu4c-73.1 common/uresdata.cpp res_findResource (). */
+int
+mcdc004 (int r, char* path, char* key)
+{
+ char *idcc (char *, char);
+ #define is_kind1(type) ((type) == 23 || (type) == 14 || (type == 115))
+ #define is_kind2(type) ((type) == 16 || (type) == 77 || (type == 118))
+ #define is_kind12(type) (is_kind1 ((type)) || is_kind2 ((type)))
+
+ char *nextSepP = path;
+ int t1 = r;
+ int type = id (t1);
+
+ if (!is_kind12 (type)) /* conditions(suppress) */
+ /* conditions(end) */
+ return -1;
+
+ while (*path && t1 != -1 && is_kind12(type)) /* conditions(suppress) */
+ /* conditions(end) */
+ {
+ nextSepP = idcc(path, '/');
+ if(nextSepP == path) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return -1;
+
+ if (*nextSepP == 'a') /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ *key = *path;
+ else if (*nextSepP == 'b') /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ *key = 0;
+ type = t1;
+ }
+
+ return t1;
+}
+
+/* Adapted from jxl 0.8.2 lib/extras/dec/apng.cc processing_start ().
+ This created a graph where depth-first traversal of the CFG would not
+ process nodes in the wrong order (the extra control inserted from setjmp
+ created a path of complexes from root to !b without going through !a).
+
+ This only happened under optimization. */
+int
+mcdc005 (int a, int b)
+{
+ a = id (a);
+ b = id (b);
+
+ /* The a || b gets transformed to a | b, then fused with setjmp because
+ they both have the same return value. */
+ if (a || b) /* conditions(0/4) true(0 1) false(0 1) */
+ /* conditions(end) */
+ return 1;
+ else
+ a += 1;
+
+ if (setjmp (buf))
+ return 1;
+
+ return a;
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-23.c } } } */
@@ -174,6 +174,184 @@ proc verify-branches { testname testcase file } {
return $failed
}
+#
+# verify-conditions -- check that conditions are checked as expected
+#
+# TESTNAME is the name of the test, including unique flags.
+# TESTCASE is the name of the test file.
+# FILE is the name of the gcov output file.
+#
+# Checks are based on comments in the source file. Condition coverage comes
+# with with two types of output, a summary and a list of the uncovered
+# conditions. Both must be checked to pass the test
+#
+# To check for conditions, add a comment the line of a conditional:
+# /* conditions(n/m) true(0 1) false(1) */
+#
+# where n/m are the covered and total conditions in the expression. The true()
+# and false() take the indices expected *not* covered.
+#
+# This means that all coverage statements should have been seen:
+# /* conditions(end) */
+#
+# If all conditions are covered i.e. n == m, then conditions(end) can be
+# omitted. If either true() or false() are empty they can be omitted too.
+#
+# C++ can insert conditionals in the CFG that are not present in source code.
+# These must be manually suppressed since unexpected and unhandled conditions
+# are an error (to help combat regressions). Output can be suppressed with
+# conditions(suppress) and conditions(end). suppress should usually be on a
+# closing brace.
+#
+# Some expressions, when using unnamed temporaries as operands, will have
+# destructors in expressions. The coverage of the destructor will be reported
+# on the same line as the expression itself, but suppress() would also swallow
+# the expected tested-for messages. To handle these, use the destructor() [1]
+# which will suppress everything from and including the second "conditions
+# covered".
+#
+# [1] it is important that the destructor() is *on the same line* as the
+# conditions(m/n)
+proc verify-conditions { testname testcase file } {
+ set failed 0
+ set suppress 0
+ set destructor 0
+ set should ""
+ set shouldt ""
+ set shouldf ""
+ set shouldall ""
+ set fd [open $file r]
+ set n 0
+ set keywords {"end" "suppress"}
+ while {[gets $fd line] >= 0} {
+ regexp "^\[^:\]+: *(\[0-9\]+):" "$line" all n
+ set prefix "$testname line $n"
+
+ if {![regexp "condition" $line]} {
+ continue
+ }
+
+ # Missing coverage for both true and false will cause a failure, but
+ # only count it once for the report.
+ set ok 1
+ if [regexp {conditions *\(([0-9a-z/]+)\)} "$line" all e] {
+ # *Very* coarse sanity check: conditions() should either be a
+ # keyword or n/m, anything else means a buggy test case. end is
+ # optional for cases where all conditions are covered, since it
+ # only expects a single line of output.
+ if {([lsearch -exact $keywords $e] >= 0 || [regexp {\d+/\d+} "$e"]) == 0} {
+ fail "$prefix: expected conditions (n/m), (suppress) or (end); was ($e)"
+ incr failed
+ continue
+ }
+
+ # Any keyword means a new context. Set the error flag if not all
+ # expected output has been seen, and reset the state.
+
+ if {[llength $shouldt] != 0} {
+ fail "$prefix: expected 'not covered (true)' for terms: $shouldt"
+ set ok 0
+ }
+
+ if {[llength $shouldf] != 0} {
+ fail "$prefix: expected 'not covered (false)' for terms: $shouldf"
+ set ok 0
+ }
+
+ if {$shouldall ne ""} {
+ fail "$prefix: coverage summary not found; expected $shouldall"
+ set ok 0
+ }
+
+ set suppress 0
+ set destructor 0
+ set should ""
+ set shouldt ""
+ set shouldf ""
+ set shouldall ""
+ set newt ""
+ set newf ""
+
+ if [regexp {destructor\(\)} "$line"] {
+ set destructor 1
+ }
+
+ if [regexp {(\d+)/(\d+)} "$e" all i k] {
+ regexp {true\(([0-9 ]+)\)} "$line" all newt
+ regexp {false\(([0-9 ]+)\)} "$line" all newf
+
+ # Sanity check - if the true() and false() vectors should have
+ # m-n elements to cover all uncovered conditions. Because of
+ # masking it can sometimes be surprising what terms are
+ # independent, so this makes for more robust test at the cost
+ # of being slightly more annoying to write.
+ set nterms [expr [llength $newt] + [llength $newf]]
+ set nexpected [expr {$k - $i}]
+ if {$nterms != $nexpected} {
+ fail "$prefix: expected $nexpected uncovered terms; got $nterms"
+ set ok 0
+ }
+ set shouldall $e
+ set shouldt $newt
+ set shouldf $newf
+ } elseif {$e == "end"} {
+ # no-op - state has already been reset, and errors flagged
+ } elseif {$e == "suppress"} {
+ set suppress 1
+ } else {
+ # this should be unreachable,
+ fail "$prefix: unhandled control ($e), should be unreachable"
+ set ok 0
+ }
+ } elseif {$suppress == 1} {
+ # ignore everything in a suppress block. C++ especially can insert
+ # conditionals in exceptions and destructors which would otherwise
+ # be considered unhandled.
+ continue
+ } elseif [regexp {condition +(\d+) not covered \((.*)\)} "$line" all cond condv] {
+ foreach v {true false} {
+ if [regexp $v $condv] {
+ if {"$v" == "true"} {
+ set should shouldt
+ } else {
+ set should shouldf
+ }
+
+ set i [lsearch [set $should] $cond]
+ if {$i != -1} {
+ set $should [lreplace [set $should] $i $i]
+ } else {
+ fail "$testname line $n: unexpected uncovered term $cond ($v)"
+ set ok 0
+ }
+ }
+ }
+ } elseif [regexp {condition outcomes covered (\d+/\d+)} "$line" all cond] {
+ # the destructor-generated "conditions covered" lines will be
+ # written after all expression-related output. Handle these by
+ # turning on suppression if the destructor-suppression is
+ # requested.
+ if {$shouldall == "" && $destructor == 1} {
+ set suppress 1
+ continue
+ }
+
+ if {$cond == $shouldall} {
+ set shouldall ""
+ } else {
+ fail "$testname line $n: unexpected summary $cond"
+ set ok 0
+ }
+ }
+
+ if {$ok != 1} {
+ incr failed
+ }
+ }
+ close $fd
+ return $failed
+}
+
#
# verify-calls -- check that call return percentages are as expected
#
@@ -321,6 +499,7 @@ proc run-gcov { args } {
set gcov_args ""
set gcov_verify_calls 0
set gcov_verify_branches 0
+ set gcov_verify_conditions 0
set gcov_verify_lines 1
set gcov_verify_intermediate 0
set gcov_remove_gcda 0
@@ -331,10 +510,13 @@ proc run-gcov { args } {
set gcov_verify_calls 1
} elseif { $a == "branches" } {
set gcov_verify_branches 1
+ } elseif { $a == "conditions" } {
+ set gcov_verify_conditions 1
} elseif { $a == "intermediate" } {
set gcov_verify_intermediate 1
set gcov_verify_calls 0
set gcov_verify_branches 0
+ set gcov_verify_conditions 0
set gcov_verify_lines 0
} elseif { $a == "remove-gcda" } {
set gcov_remove_gcda 1
@@ -404,6 +586,11 @@ proc run-gcov { args } {
} else {
set bfailed 0
}
+ if { $gcov_verify_conditions } {
+ set cdfailed [verify-conditions $testname $testcase $testcase.gcov]
+ } else {
+ set cdfailed 0
+ }
if { $gcov_verify_calls } {
set cfailed [verify-calls $testname $testcase $testcase.gcov]
} else {
@@ -418,12 +605,12 @@ proc run-gcov { args } {
# Report whether the gcov test passed or failed. If there were
# multiple failures then the message is a summary.
- set tfailed [expr $lfailed + $bfailed + $cfailed + $ifailed]
+ set tfailed [expr $lfailed + $bfailed + $cdfailed + $cfailed + $ifailed]
if { $xfailed } {
setup_xfail "*-*-*"
}
if { $tfailed > 0 } {
- fail "$testname gcov: $lfailed failures in line counts, $bfailed in branch percentages, $cfailed in return percentages, $ifailed in intermediate format"
+ fail "$testname gcov: $lfailed failures in line counts, $bfailed in branch percentages, $cdfailed in condition/decision, $cfailed in return percentages, $ifailed in intermediate format"
if { $xfailed } {
clean-gcov $testcase
}
@@ -58,6 +58,8 @@ along with GCC; see the file COPYING3. If not see
#include "alloc-pool.h"
#include "symbol-summary.h"
#include "symtab-thunks.h"
+#include "cfganal.h"
+#include "cfgloop.h"
static GTY(()) tree gcov_type_node;
static GTY(()) tree tree_interval_profiler_fn;
@@ -73,6 +75,1315 @@ static GTY(()) tree ic_tuple_var;
static GTY(()) tree ic_tuple_counters_field;
static GTY(()) tree ic_tuple_callee_field;
+/* These functions support measuring modified conditition/decision coverage
+ (MC/DC). MC/DC requires all of the below during testing:
+
+ - Each entry and exit point is invoked
+ - Each decision takes every possible outcome
+ - Each condition in a decision takes every possible outcome
+ - Each condition in a decision is shown to independently affect the outcome
+ of the decision
+
+ Independence of a condition is shown by proving that only one condition
+ changes at a time. This feature adds some instrumentation code, a few
+ bitwise operators, that records the branches taken in conditions and applies
+ a filter for the masking effect. Masking is essentially short-circuiting in
+ reverse: a condition does not contribute to the outcome if it would short
+ circuit the (sub) expression if it was evaluated right-to-left, (_ && false)
+ and (_ || true).
+
+ The program is essentially rewritten this way:
+
+ - if (a || b) { fn () }
+ + if (a) { _t |= 0x1; goto _then; }
+ + else { _f |= 0x1;
+ + if (b) { _t |= 0x2; _mask |= 0x1; goto _then; }
+ + else { _f |= 0x2; goto _else; }
+ + _then:
+ + _gcov_t |= (_t & _mask);
+ + _gcov_f |= (_f & _mask);
+ + fn (); goto _end;
+ + _else:
+ + _gcov_t |= (_t & _mask);
+ + _gcov_f |= (_f & _mask);
+ + fn ();
+ + _end:
+
+ The first phase is analyzing the structure of the CFG to find the subgraphs
+ that correspond to Boolean expressions. Then, the structure of subgraphs are
+ analyzed to determine the masking effect of each condition (what previous
+ terms, if any, would not contribute to coverage by reaching this node).
+ The final phase is walking the subgraphs and adding instrumentation, which
+ are flushed to the gcov counters when the expression evaluates to
+ completion. */
+namespace
+{
+/* Some context and reused instances between function calls. Large embedded
+ buffers are used to up-front request enough memory for most programs and
+ merge them into a single allocation at the cost of using more memory in the
+ average case. Some numbers from linux v5.13 which is assumed to be a
+ reasonably diverse code base: 75% of the functions in linux have less than
+ 16 nodes in the CFG and approx 2.5% have more than 64 nodes. The functions
+ that go beyond a few dozen nodes tend to be very large (>100) and so 64
+ seems like a good balance.
+
+ This is really just a performance balance of the cost of allocation and
+ wasted memory. */
+struct conds_ctx
+{
+ /* Bitmap of the processed blocks. Bit n set means basic_block->index has
+ been processed either explicitly or as a part of an expression. */
+ auto_sbitmap marks;
+
+ /* This is both a reusable shared allocation which is also used to return
+ single expressions, which means it for most code should only hold a
+ couple of elements. */
+ auto_vec<basic_block, 32> blocks;
+
+ /* Map from basic_block->index to an ordering so that for a single
+ expression (a || b && c) => index_map[a] < index_map[b] < index_map[c].
+ The values do not have to be consecutive and can be interleaved by
+ values from other expressions, so comparisons only make sense for blocks
+ that belong to the same expression. */
+ auto_vec<int, 64> index_map;
+
+ /* Pre-allocate bitmaps and vectors for per-function book keeping. This is
+ pure instance reuse and the bitmaps carry no data between function
+ calls. */
+ auto_vec<basic_block, 64> B1;
+ auto_vec<basic_block, 64> B2;
+ auto_sbitmap G1;
+ auto_sbitmap G2;
+ auto_sbitmap G3;
+ auto_sbitmap G4;
+
+ explicit conds_ctx (unsigned size) noexcept (true) : marks (size),
+ G1 (size), G2 (size), G3 (size), G4 (size)
+ {
+ bitmap_clear (marks);
+ }
+
+ /* Mark a node as processed so nodes are not processed twice for example in
+ loops, gotos. */
+ void mark (const basic_block b) noexcept (true)
+ {
+ gcc_assert (!bitmap_bit_p (marks, b->index));
+ bitmap_set_bit (marks, b->index);
+ }
+
+ /* Mark nodes as processed so they are not processed twice. */
+ void mark (const vec<basic_block>& bs) noexcept (true)
+ {
+ for (const basic_block b : bs)
+ mark (b);
+ }
+
+ /* Check if all nodes are marked. A successful run should visit & mark
+ every reachable node exactly once. */
+ bool all_marked (const vec<basic_block>& reachable) const noexcept (true)
+ {
+ for (const basic_block b : reachable)
+ if (!bitmap_bit_p (marks, b->index))
+ return false;
+ return true;
+ }
+};
+
+/* Only instrument terms with fewer than number of bits in a (wide) gcov
+ integer, which is probably 64. The algorithm itself does not impose this
+ limitation, but it makes for a simpler implementation.
+
+ * Allocating the output data structure (coverage_counter_alloc ()) can
+ assume pairs of gcov_type_unsigned and not use a separate length field.
+ * A pair gcov_type_unsigned can be used as accumulators.
+ * Updating accumulators is can use the bitwise operations |=, &= and not
+ custom operators that work for arbitrary-sized bit-sets.
+
+ Most real-world code should be unaffected by this, but it is possible
+ (especially for generated code) to exceed this limit. */
+#define CONDITIONS_MAX_TERMS (TYPE_PRECISION (gcov_type_node))
+#define EDGE_CONDITION (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
+
+/* Compare two basic blocks by their order in the expression i.e. for (a || b)
+ then cmp_index_map (a, b, ...) < 0. The result is undefined if lhs, rhs
+ belong to different expressions. */
+int
+cmp_index_map (const void *lhs, const void *rhs, void *index_map)
+{
+ const_basic_block l = *(const basic_block*) lhs;
+ const_basic_block r = *(const basic_block*) rhs;
+ const vec<int>* im = (const vec<int>*) index_map;
+ return (*im)[l->index] - (*im)[r->index];
+}
+
+/* Find the index of needle in blocks; return -1 if not found. This has two
+ uses, sometimes for the index and sometimes for set member c hecks. Sets are
+ typically very small (number of conditions, >8 is uncommon) so linear search
+ should be very fast. */
+int
+index_of (const basic_block needle, array_slice<basic_block> blocks)
+{
+ for (size_t i = 0; i < blocks.size (); i++)
+ if (blocks[i] == needle)
+ return int (i);
+ return -1;
+}
+
+/* Returns true if this is a conditional node, i.e. it has outgoing true and
+ false edges. */
+bool
+block_conditional_p (const basic_block b)
+{
+ unsigned t = 0;
+ unsigned f = 0;
+ for (edge e : b->succs)
+ {
+ t |= (e->flags & EDGE_TRUE_VALUE);
+ f |= (e->flags & EDGE_FALSE_VALUE);
+ }
+ return t && f;
+}
+
+/* Check if the edge is a conditional. */
+bool
+edge_conditional_p (const edge e)
+{
+ return e->flags & EDGE_CONDITION;
+}
+
+/* Special cases of the single_*_p and single_*_edge functions in basic-block.h
+ that don't consider exception handling or other complex edges. This helps
+ create a view of the CFG with only normal edges - if a basic block has both
+ an outgoing fallthrough and exceptional edge, it should be considered a
+ single-successor. */
+bool
+single_p (const vec<edge, va_gc> *edges)
+{
+ int n = EDGE_COUNT (edges);
+ if (n == 0)
+ return false;
+
+ for (edge e : edges)
+ if (e->flags & EDGE_COMPLEX)
+ n -= 1;
+
+ return n == 1;
+}
+
+/* Get the single, non-complex edge. Behavior is undefined edges have more
+ than 1 non-complex edges. */
+edge
+single_edge (const vec<edge, va_gc> *edges)
+{
+ gcc_checking_assert (single_p (edges));
+ for (edge e : edges)
+ {
+ if (e->flags & EDGE_COMPLEX)
+ continue;
+ return e;
+ }
+ return NULL;
+}
+
+/* Sometimes, for example with function calls and C++ destructors, the CFG gets
+ extra nodes that are essentially single-entry-single-exit in the middle of
+ boolean expressions. For example:
+
+ x || can_throw (y)
+
+ A
+ /|
+ / |
+ B |
+ | |
+ C |
+ / \ |
+ / \|
+ F T
+
+ Without the extra node inserted by the function + exception it becomes a
+ proper 2-term graph, not 2 single-term graphs.
+
+ A
+ /|
+ C |
+ / \|
+ F T
+
+ contract_edge ignores the series of intermediate nodes and makes a virtual
+ edge A -> C without having to construct a new simplified CFG explicitly. It
+ gets more complicated as non-conditional edges is how the body of the
+ then/else blocks are separated from the boolean expression, so only edges
+ that are inserted because of function calls in the expression itself must be
+ merged.
+
+ Only chains of single-exit single-entry nodes that end with a condition
+ should be contracted. If the optional bitset G is passed, the intermediate
+ "contracted-past" nodes will be recorded, which is only meaningful if the
+ non-source edge is returned. */
+edge
+contract_edge (edge e)
+{
+ edge source = e;
+ while (true)
+ {
+ basic_block dest = e->dest;
+ if (e->flags & EDGE_DFS_BACK)
+ return source;
+ if (dest->index == EXIT_BLOCK)
+ return source;
+ if (!single_p (dest->preds))
+ return source;
+ if (block_conditional_p (dest))
+ return e;
+ /* This happens for switches, and must be checked after the is-conditional
+ (which is also not single). */
+ if (!single_p (dest->succs))
+ return source;
+
+ e = single_edge (dest->succs);
+ }
+}
+
+/* This is the predecessor dual of contract_edge; it collapses the predecessor
+ blocks between two operands in a boolean expression. */
+edge
+contract_edge_up (edge e)
+{
+ while (true)
+ {
+ basic_block src = e->src;
+ if (edge_conditional_p (e))
+ return e;
+ if (!single_p (src->preds))
+ return e;
+ e = single_edge (src->preds);
+ }
+}
+
+/* "Undo" an edge split. Sometimes the sink of a boolean expression will be
+ split into multiple blocks to accurately track line coverage, for example
+ when there is a goto-label at the top of the then/else block:
+
+ if (a && b)
+ {
+ l1:
+ ...
+ }
+ else
+ {
+ l2:
+ ...
+ }
+
+ and the corresponding CFG where a1 and b1 are created in edge splits to the
+ same destination (F):
+
+ a
+ |\
+ | a1
+ b \
+ |\ |
+ | b1|
+ | \|
+ T F
+
+ When this split happens it flags the edge with EDGE_IGNORE. */
+basic_block
+merge_split_outcome (basic_block b)
+{
+ if (!single_p (b->succs))
+ return b;
+ edge e = single_edge (b->succs);
+ if (e->flags & EDGE_IGNORE)
+ return e->dest;
+ return b;
+}
+
+
+/* Find the set {ancestors (source) intersect reachable} where ancestors is the
+ recursive set of predecessors for p. Limiting to the ancestors that are
+ also in reachable (see cond_reachable_from) and by qroot is an optimization
+ as ancestors outside reachable have no effect when isolating expressions.
+ root should be the root of the current Boolean expression being analyzed.
+
+ dfs_enumerate_from () does not work as the filter function needs edge
+ information and dfs_enumerate_from () only considers blocks. */
+void
+ancestors_of (basic_block source, basic_block root, const sbitmap reachable,
+ sbitmap ancestors)
+{
+ if (!bitmap_bit_p (reachable, source->index))
+ return;
+
+ bitmap_set_bit (ancestors, source->index);
+ bitmap_set_bit (ancestors, root->index);
+ if (source == root)
+ return;
+
+ auto_vec<basic_block, 16> stack;
+ stack.safe_push (source);
+ while (!stack.is_empty ())
+ {
+ basic_block b = stack.pop ();
+ for (edge e : b->preds)
+ {
+ basic_block src = e->src;
+ if (!bitmap_bit_p (reachable, src->index))
+ continue;
+ if (!bitmap_set_bit (ancestors, src->index))
+ continue;
+ stack.safe_push (src);
+ }
+ }
+}
+
+/* A simple struct for storing/returning outcome block pairs. Either both
+ blocks are set or both are NULL. */
+struct outcomes
+{
+ basic_block t = NULL;
+ basic_block f = NULL;
+
+ operator bool () const noexcept (true)
+ {
+ return t && f;
+ }
+};
+
+/* Get the true/false successors of a basic block. If b is not a conditional
+ block both edges are NULL. */
+outcomes
+conditional_succs (const basic_block b)
+{
+ outcomes c;
+ for (edge e : b->succs)
+ {
+ if (e->flags & EDGE_TRUE_VALUE)
+ c.t = merge_split_outcome (e->dest);
+ if (e->flags & EDGE_FALSE_VALUE)
+ c.f = merge_split_outcome (e->dest);
+ }
+
+ gcc_assert ((c.t && c.f) || (!c.t && !c.f));
+ return c;
+}
+
+/* Get the index or offset of a conditional flag, 0 for true and 1 for false.
+ These indices carry no semantics but must be consistent as they are used to
+ index into data structures in code generation and gcov. */
+unsigned
+condition_index (unsigned flag)
+{
+ return (flag & EDGE_CONDITION) == EDGE_TRUE_VALUE ? 0 : 1;
+}
+
+/* Compute the masking vector.
+
+ Masking and short circuiting are deeply connected - masking occurs when
+ control flow reaches a state that is also reachable with short circuiting.
+ In fact, masking corresponds to short circuiting in the CFG for the reversed
+ expression. This means we can find the limits, the last term in preceeding
+ subexpressions, by following the edges that short circuit to the same
+ outcome.
+
+ In the simplest case a || b:
+
+ a
+ |\
+ | b
+ |/ \
+ T F
+
+ T has has multiple incoming edges and is the outcome of a short circuit,
+ with top = a, bot = b. The top node (a) is masked when the edge (b, T) is
+ taken.
+
+ The names "top" and "bot" refer to a pair of nodes with a shared
+ destination. The top is always the node corresponding to the left-most
+ operand of the two it holds that index_map[top] < index_map[bot].
+
+ Now consider (a && b) || (c && d) and its masking vectors:
+
+ a
+ |\
+ b \
+ |\|
+ | c
+ | |\
+ | d \
+ |/ \|
+ T F
+
+ a[0] = {}
+ a[1] = {}
+ b[0] = {a}
+ b[1] = {}
+ c[0] = {}
+ c[1] = {}
+ d[0] = {c}
+ d[1] = {a,b}
+
+ Note that 0 and 1 are indices and not boolean values - a[0] is the index in
+ the masking vector when a takes the true edge.
+
+ b[0] and d[0] are identical to the a || b example, and d[1] is the bot in
+ the triangle [d, b] -> T. b is the top node in the [d, b] relationship and
+ last term in (a && b). To find the other terms masked we use the fact that
+ all nodes in an expression have outgoing edges to either the outcome or some
+ other node in the expression. The "bot" node is also the last term in a
+ masked subexpression, so the problem becomes finding the subgraph where all
+ paths end up in the successors to bot.
+
+ We find the terms by marking the outcomes (in this case c, T) and walk the
+ predecessors starting at top (in this case b) and masking nodes when both
+ successors are marked.
+
+ The masking vector is represented as two bitfields per term in the
+ expression with the index corresponding to the term in the source
+ expression. a || b && c becomes the term vector [a b c] and the masking
+ vectors [a[0] a[1] b[0] ...]. The kth bit of a masking vector is set if the
+ the kth term is masked by taking the edge.
+
+ The out masks are in uint64_t (the practical maximum for gcov_type_node for
+ any target) as it has to be big enough to store the target size gcov types
+ independent of the host. */
+void
+masking_vectors (conds_ctx& ctx, array_slice<basic_block> blocks,
+ array_slice<uint64_t> masks)
+{
+ gcc_assert (blocks.is_valid ());
+ gcc_assert (!blocks.empty ());
+ gcc_assert (masks.is_valid ());
+ gcc_assert (sizeof (masks[0]) * BITS_PER_UNIT >= CONDITIONS_MAX_TERMS);
+
+ sbitmap marks = ctx.G1;
+ sbitmap expr = ctx.G2;
+ vec<basic_block>& queue = ctx.B1;
+ vec<basic_block>& body = ctx.B2;
+ const vec<int>& index_map = ctx.index_map;
+ bitmap_clear (expr);
+
+ for (const basic_block b : blocks)
+ bitmap_set_bit (expr, b->index);
+
+ /* Set up for the iteration - include two outcome nodes in the traversal and
+ ignore the leading term since it cannot mask anything. The algorithm is
+ not sensitive to the traversal order. */
+ body.truncate (0);
+ body.reserve (blocks.size () + 2);
+ for (const basic_block b : blocks)
+ body.quick_push (b);
+
+ outcomes out = conditional_succs (blocks.back ());
+ body.quick_push (out.t);
+ body.quick_push (out.f);
+ body[0] = body.pop ();
+
+ for (const basic_block b : body)
+ {
+ for (edge e1 : b->preds)
+ for (edge e2 : b->preds)
+ {
+ const basic_block top = e1->src;
+ const basic_block bot = e2->src;
+ const unsigned cond = e1->flags & e2->flags & (EDGE_CONDITION);
+
+ if (!cond)
+ continue;
+ if (e1 == e2)
+ continue;
+ if (!bitmap_bit_p (expr, top->index))
+ continue;
+ if (!bitmap_bit_p (expr, bot->index))
+ continue;
+ if (index_map[top->index] > index_map[bot->index])
+ continue;
+
+ outcomes out = conditional_succs (top);
+ gcc_assert (out);
+ bitmap_clear (marks);
+ bitmap_set_bit (marks, out.t->index);
+ bitmap_set_bit (marks, out.f->index);
+ queue.truncate (0);
+ queue.safe_push (top);
+
+ // The edge bot -> outcome triggers the masking
+ const int m = 2*index_of (bot, blocks) + condition_index (cond);
+ while (!queue.is_empty ())
+ {
+ basic_block q = queue.pop ();
+ /* q may have been processed & completed by being added to the
+ queue multiple times, so check that there is still work to
+ do before continuing. */
+ if (bitmap_bit_p (marks, q->index))
+ continue;
+
+ outcomes succs = conditional_succs (q);
+ if (!bitmap_bit_p (marks, succs.t->index))
+ continue;
+ if (!bitmap_bit_p (marks, succs.f->index))
+ continue;
+
+ const int index = index_of (q, blocks);
+ gcc_assert (index != -1);
+ masks[m] |= uint64_t (1) << index;
+ bitmap_set_bit (marks, q->index);
+
+ for (edge e : q->preds)
+ {
+ e = contract_edge_up (e);
+ if (!edge_conditional_p (e))
+ continue;
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+ if (bitmap_bit_p (marks, e->src->index))
+ continue;
+ if (!bitmap_bit_p (expr, e->src->index))
+ continue;
+ queue.safe_push (e->src);
+ }
+ }
+ }
+ }
+}
+
+/* Check that all predecessors are conditional and belong to the current
+ expression. This check is necessary in the presence of gotos, setjmp and
+ other complicated control flow that creates extra edges and creates odd
+ reachable paths from mid-expression terms and paths escaping nested
+ expressions. If a node has an incoming non-complex edge (after contraction)
+ it can not be a part of a single, multi-term conditional expression.
+
+ If the expr[i] is set then nodes[i] is reachable from the leftmost operand
+ and b is a viable candidate. Otherwise, this has to be an independent but
+ following expression.
+ */
+bool
+all_preds_conditional_p (basic_block b, const sbitmap expr)
+{
+ for (edge e : b->preds)
+ {
+ e = contract_edge_up (e);
+ if (!(e->flags & (EDGE_CONDITION | EDGE_COMPLEX)))
+ return false;
+
+ if (!bitmap_bit_p (expr, e->src->index))
+ return false;
+ }
+ return true;
+}
+
+/* Find the nodes reachable from p by following only (possibly contracted)
+ condition edges and ignoring DFS back edges. From a high level this is
+ partitioning the CFG into subgraphs by removing all non-condition edges and
+ selecting a single connected subgraph. This creates a cut C = (G, G') where
+ G is the returned explicitly by this function and forms the candidate set
+ for an expression. All nodes in an expression should be connected only by
+ true|false edges, so a node with a non-conditional predecessor must be a
+ part of a different expression and in G', not G.
+
+ p must always be the first term in an expression and a condition node.
+
+ If |G| = 1 then this is a single term expression. If |G| > 1 then either
+ this is a multi-term expression or the first block in the then/else block is
+ a conditional expression as well.
+
+ The function outputs both a bitmap and a vector as both are useful to the
+ caller. */
+void
+cond_reachable_from (basic_block p, basic_block q, sbitmap expr,
+ vec<basic_block>& out)
+{
+ out.safe_push (p);
+ bitmap_set_bit (expr, p->index);
+ for (unsigned pos = 0; pos != out.length (); pos++)
+ {
+ for (edge e : out[pos]->succs)
+ {
+ basic_block dest = contract_edge (e)->dest;
+ if (dest == q)
+ continue;
+ if (!block_conditional_p (dest))
+ continue;
+ if (bitmap_bit_p (expr, dest->index))
+ continue;
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+ if (!all_preds_conditional_p (dest, expr))
+ continue;
+
+ bitmap_set_bit (expr, dest->index);
+ out.safe_push (dest);
+
+ /* We still want nodes skipped past by contract_edge in this set,
+ as it removes the need for keeping track of contracted-by edges
+ later. */
+ for (basic_block b = e->dest; b != dest; b = single_edge (b->succs)->dest)
+ {
+ out.safe_insert (pos++, b);
+ bitmap_set_bit (expr, b->index);
+ }
+ }
+ }
+}
+
+/* Find the neighborhood of the graph G = [blocks, blocks+n), the
+ successors of nodes in G that are not also in G. In the cut C = (G, G')
+ these are the nodes in G' with incoming edges that cross the span. */
+void
+neighborhood (const vec<basic_block>& blocks, sbitmap reachable,
+ vec<basic_block>& out)
+{
+ for (const basic_block b : blocks)
+ {
+ for (edge e : b->succs)
+ {
+ basic_block dest = e->dest;
+ if (e->flags & EDGE_COMPLEX)
+ continue;
+ if (bitmap_bit_p (reachable, dest->index))
+ continue;
+ if (out.contains (dest))
+ continue;
+
+ /* Fix the case where the edge into the outcome is split, an
+ artifact of other profiling phases. When this happens the
+ intermediate node should be marked as a part of the current
+ graph so that it would not break the ancestor search. */
+ basic_block far = merge_split_outcome (dest);
+ if (far != dest)
+ bitmap_set_bit (reachable, dest->index);
+ out.safe_push (far);
+ }
+ }
+}
+
+/* Find and isolate the expression starting at root.
+
+ Make a cut C = (G, G') following only condition edges. G (candidates) is a
+ superset of the expression B (out), as the walk may include expressions from
+ the then/else blocks if they start with conditions. Only the subgraph B is
+ the ancestor of *both* the then/else outcome, which means B is the
+ intersection of the ancestors of the nodes in the neighborhood N(G).
+
+ In complex graphs this may capture more than the expression proper. In that
+ case, keep reducing the candidate set by finding the neighboorhood of the
+ previous step's intersection-of-ancestors until the neighborhood is exactly
+ two nodes (the then/else blocks). Unless there is complex control flow with
+ deep early returns, gotos and else-less ifs this will be found in a step or
+ two. */
+void
+isolate_expression (conds_ctx &ctx, basic_block root, vec<basic_block>& out)
+{
+ sbitmap expr = ctx.G1;
+ sbitmap reachable = ctx.G2;
+ sbitmap ancestors = ctx.G3;
+ sbitmap prev = ctx.G4;
+ bitmap_clear (expr);
+ bitmap_clear (reachable);
+ bitmap_clear (prev);
+
+ vec<basic_block>& candidates = ctx.B1;
+ vec<basic_block>& neighbors = ctx.B2;
+ candidates.truncate (0);
+
+ basic_block post = get_immediate_dominator (CDI_POST_DOMINATORS, root);
+ cond_reachable_from (root, post, reachable, candidates);
+ if (candidates.length () == 1)
+ {
+ out.safe_push (root);
+ return;
+ }
+
+ while (true)
+ {
+ neighbors.truncate (0);
+ neighborhood (candidates, reachable, neighbors);
+ gcc_assert (!neighbors.is_empty ());
+
+ bitmap_clear (expr);
+ for (basic_block b : neighbors)
+ bitmap_set_bit (expr, b->index);
+
+ if (bitmap_count_bits (expr) == 2)
+ break;
+
+ /* This can happen for loops with no body. */
+ if (bitmap_count_bits (expr) == 1 && bb_loop_header_p (root))
+ break;
+
+ /* If the neighborhood does not change between iterations (a fixed
+ point) we cannot understand the graph properly, and this would loop
+ infinitely. If this should happen, we should bail out and give up
+ instrumentation for the function altogether. It is possible no such
+ CFGs exist, so for now this is an assert. */
+ gcc_assert (!bitmap_equal_p (prev, expr));
+ gcc_assert (bitmap_count_bits (expr) > 2);
+ bitmap_copy (prev, expr);
+
+ bitmap_copy (expr, reachable);
+ for (const basic_block neighbor : neighbors)
+ {
+ bitmap_clear (ancestors);
+ for (edge e : neighbor->preds)
+ ancestors_of (e->src, root, reachable, ancestors);
+ bitmap_and (expr, expr, ancestors);
+ }
+
+ for (unsigned i = 0; i != candidates.length (); i++)
+ if (!bitmap_bit_p (expr, candidates[i]->index))
+ candidates.unordered_remove (i--);
+
+ bitmap_clear (reachable);
+ for (basic_block b : candidates)
+ bitmap_set_bit (reachable, b->index);
+ }
+
+ out.safe_splice (candidates);
+ out.sort (cmp_index_map, &ctx.index_map);
+}
+
+/* Emit <lhs> = <rhs> on edges. This is just a short hand that automates the
+ building of the assign and immediately puts it on the edge, which becomes
+ noisy. */
+tree
+emit_assign (edge e, tree lhs, tree rhs)
+{
+ gassign *w = gimple_build_assign (lhs, rhs);
+ gsi_insert_on_edge (e, w);
+ return lhs;
+}
+
+/* Emit lhs = <rhs> on edges. */
+tree
+emit_assign (edge e, tree rhs)
+{
+ return emit_assign (e, make_ssa_name (gcov_type_node), rhs);
+}
+
+/* Emit lhs = op1 <op> op2 on edges. */
+tree
+emit_bitwise_op (edge e, tree op1, tree_code op, tree op2 = NULL_TREE)
+{
+ tree lhs = make_ssa_name (gcov_type_node);
+ gassign *w = gimple_build_assign (lhs, op, op1, op2);
+ gsi_insert_on_edge (e, w);
+ return lhs;
+}
+
+/* Visitor for make_index_map. */
+void
+make_index_map_visit (basic_block b, vec<basic_block>& L, vec<int>& marks)
+{
+ if (marks[b->index])
+ return;
+
+ for (edge e : b->succs)
+ if (!(e->flags & EDGE_DFS_BACK))
+ make_index_map_visit (e->dest, L, marks);
+
+ marks[b->index] = 1;
+ L.quick_push (b);
+}
+
+/* Find a topological sorting of the blocks in a function so that left operands
+ are before right operands including subexpressions. Sorting on block index
+ does not guarantee this property and the syntactical order of terms is very
+ important to the condition coverage. The sorting algorithm is from Cormen
+ et al (2001) but with back-edges ignored and thus there is no need for
+ temporary marks (for cycle detection).
+
+ It is important to select unvisited nodes in DFS order to ensure the
+ roots/leading terms of boolean expressions are visited first (the other
+ terms being covered by the recursive step), but the visiting order of
+ individual boolean expressions carries no significance.
+
+ For the expression (a || (b && c) || d) the blocks should be [a b c d]. */
+void
+make_index_map (const vec<basic_block>& blocks, int max_index,
+ vec<basic_block>& L, vec<int>& index_map)
+{
+ L.truncate (0);
+ L.reserve (max_index);
+
+ /* Use of the output map as a temporary for tracking visited status. */
+ index_map.truncate (0);
+ index_map.safe_grow_cleared (max_index);
+ for (const basic_block b : blocks)
+ make_index_map_visit (b, L, index_map);
+
+ /* Insert canaries - if there are unreachable nodes (for example infinite
+ loops) then the unreachable nodes should never be needed for comparison,
+ and L.length () < max_index. An index mapping should also never be
+ recorded twice. */
+ for (unsigned i = 0; i < index_map.length (); i++)
+ index_map[i] = -1;
+
+ gcc_assert (blocks.length () == L.length ());
+ L.reverse ();
+ const unsigned nblocks = L.length ();
+ for (unsigned i = 0; i < nblocks; i++)
+ {
+ gcc_assert (L[i]->index != -1);
+ index_map[L[i]->index] = int (i);
+ }
+}
+
+/* Walk the CFG and collect conditionals.
+
+ 1. Collect a candidate set G by walking from the root following all
+ (contracted) condition edges.
+ 2. This creates a cut C = (G, G'); find the neighborhood N(G).
+ 3. For every node in N(G), follow the edges across the cut and collect all
+ ancestors (that are also in G).
+ 4. The intersection of all these ancestor sets is the boolean expression B
+ that starts in root.
+
+ Walking is not guaranteed to find nodes in the order of the expression, it
+ might find (a || b) && c as [a c b], so the result must be sorted by the
+ index map. */
+const vec<basic_block>&
+collect_conditions (conds_ctx& ctx, const basic_block block)
+{
+ vec<basic_block>& blocks = ctx.blocks;
+ blocks.truncate (0);
+
+ if (bitmap_bit_p (ctx.marks, block->index))
+ return blocks;
+
+ if (!block_conditional_p (block))
+ {
+ ctx.mark (block);
+ return blocks;
+ }
+
+ isolate_expression (ctx, block, blocks);
+ ctx.mark (blocks);
+
+ unsigned nconds = 0;
+ for (basic_block b : blocks)
+ if (block_conditional_p (b))
+ nconds++;
+
+ if (nconds > CONDITIONS_MAX_TERMS)
+ {
+ location_t loc = gimple_location (gsi_stmt (gsi_last_bb (block)));
+ warning_at (loc, OPT_Wcoverage_too_many_conditions,
+ "Too many conditions (found %u); giving up coverage",
+ nconds);
+ blocks.truncate (0);
+ }
+ return blocks;
+}
+
+/* Used for dfs_enumerate_from () to include all reachable nodes. */
+bool
+yes (const_basic_block, const void *)
+{
+ return true;
+}
+
+}
+
+/* Context object for the condition coverage. This stores conds_ctx (the
+ buffers reused when analyzing the cfg) and the output arrays. This is
+ designed to be heap allocated and aggressively preallocates large buffers to
+ avoid having to reallocate for most programs. */
+struct condcov
+{
+ explicit condcov (unsigned nblocks) noexcept (true) : ctx (nblocks)
+ {}
+ auto_vec<size_t, 128> m_index;
+ auto_vec<size_t, 128> m_graph_index;
+ auto_vec<basic_block, 256> m_blocks;
+ auto_vec<basic_block, 256> m_graphs;
+ auto_vec<uint64_t, 512> m_masks;
+ conds_ctx ctx;
+};
+
+/* Get the length, that is the number of Boolean expression found. cov_length
+ is the one-past index for cov_{blocks,graphs,masks}. */
+size_t
+cov_length (const struct condcov* cov)
+{
+ if (cov->m_index.is_empty ())
+ return 0;
+ return cov->m_index.length () - 1;
+}
+
+/* The subgraph, exluding intermediates, for the nth Boolean expression. */
+array_slice<basic_block>
+cov_blocks (struct condcov* cov, size_t n)
+{
+ if (n >= cov->m_index.length ())
+ return array_slice<basic_block>::invalid ();
+
+ basic_block *begin = cov->m_blocks.begin () + cov->m_index[n];
+ basic_block *end = cov->m_blocks.begin () + cov->m_index[n + 1];
+ return array_slice<basic_block> (begin, end - begin);
+}
+
+/* The subgraph, including intermediates, for the nth Boolean expression. All
+ nodes in cov_graphs are conditional. */
+array_slice<basic_block>
+cov_graphs (struct condcov* cov, size_t n)
+{
+ if (n >= cov->m_index.length ())
+ return array_slice<basic_block>::invalid ();
+
+ basic_block *begin = cov->m_graphs.begin () + cov->m_graph_index[n];
+ basic_block *end = cov->m_graphs.begin () + cov->m_graph_index[n + 1];
+ return array_slice<basic_block> (begin, end - begin);
+}
+
+/* The masks for the nth Boolean expression. */
+array_slice<uint64_t>
+cov_masks (struct condcov* cov, size_t n)
+{
+ if (n >= cov->m_index.length ())
+ return array_slice<uint64_t>::invalid ();
+
+ uint64_t *begin = cov->m_masks.begin () + 2*cov->m_index[n];
+ uint64_t *end = cov->m_masks.begin () + 2*cov->m_index[n + 1];
+ return array_slice<uint64_t> (begin, end - begin);
+}
+
+/* Deleter for condcov. */
+void
+cov_free (struct condcov* cov)
+{
+ delete cov;
+}
+
+/* Condition coverage (MC/DC)
+
+ Algorithm
+ ---------
+ Whalen, Heimdahl, De Silva in "Efficient Test Coverage Measurement for
+ MC/DC" describe an algorithm for modified condition/decision coverage based
+ on AST analysis. This algorithm analyses the control flow graph to analyze
+ expressions and compute masking vectors, but is inspired by their marking
+ functions for recording outcomes. The individual phases are described in
+ more detail closer to the implementation.
+
+ The CFG is traversed in topological order. It is important that the first
+ basic block in an expression is the first one visited, but the order of
+ independent expressions does not matter. When the function terminates,
+ every node in the graph should have been processed and marked exactly once.
+ If there are unreachable nodes they are ignored and not instrumented.
+ Topological order is necessary to correctly handle highly connected graphs
+ (many complex edges with nodes) such as those created by setjmp, otherwise
+ depth-first would be fine.
+
+ The CFG is broken up into segments between dominators. This isn't strictly
+ necessary, but since boolean expressions cannot cross dominators it makes
+ for a nice way to introduce limits to searches.
+
+ The coverage only considers the positions, not the symbols, in a
+ conditional, e.g. !A || (!B && A) is a 3-term conditional even though A
+ appears twice. Subexpressions have no effect on term ordering:
+ (a && (b || (c && d)) || e) comes out as [a b c d e].
+
+ The output for gcov is a vector of pairs of unsigned integers, interpreted
+ as bit-sets, where the bit index corresponds to the index of the condition
+ in the expression.
+
+ The returned condcov should be free'd by the caller with cov_free. */
+struct condcov*
+find_conditions (struct function *fn)
+{
+ record_loop_exits ();
+ mark_dfs_back_edges (fn);
+
+ const bool have_dom = dom_info_available_p (fn, CDI_DOMINATORS);
+ const bool have_post_dom = dom_info_available_p (fn, CDI_POST_DOMINATORS);
+ if (!have_dom)
+ calculate_dominance_info (CDI_DOMINATORS);
+ if (!have_post_dom)
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+
+ const unsigned nblocks = n_basic_blocks_for_fn (fn);
+ condcov *cov = new condcov (nblocks);
+ conds_ctx& ctx = cov->ctx;
+
+ auto_vec<basic_block, 16> dfs;
+ dfs.safe_grow (nblocks);
+ const basic_block entry = ENTRY_BLOCK_PTR_FOR_FN (fn);
+ const basic_block exit = ENTRY_BLOCK_PTR_FOR_FN (fn);
+ int n = dfs_enumerate_from (entry, 0, yes, dfs.address (), nblocks, exit);
+ dfs.truncate (n);
+ make_index_map (dfs, nblocks, ctx.B1, ctx.index_map);
+ dfs.sort (cmp_index_map, &ctx.index_map);
+
+ /* Visit all reachable nodes and collect conditions. DFS order is
+ important so the first node of a boolean expression is visited first
+ (it will mark subsequent terms). */
+ cov->m_index.safe_push (0);
+ cov->m_graph_index.safe_push (0);
+ for (const basic_block b : dfs)
+ {
+ const vec<basic_block>& expr = collect_conditions (ctx, b);
+ if (!expr.is_empty ())
+ {
+ cov->m_graphs.safe_splice (expr);
+ for (basic_block b : expr)
+ if (block_conditional_p (b))
+ cov->m_blocks.safe_push (b);
+ cov->m_index.safe_push (cov->m_blocks.length ());
+ cov->m_graph_index.safe_push (cov->m_graphs.length ());
+ }
+ }
+ gcc_assert (ctx.all_marked (dfs));
+
+ if (!have_dom)
+ free_dominance_info (fn, CDI_DOMINATORS);
+ if (!have_post_dom)
+ free_dominance_info (fn, CDI_POST_DOMINATORS);
+
+ cov->m_masks.safe_grow_cleared (2 * cov->m_index.last());
+ const size_t length = cov_length (cov);
+ for (size_t i = 0; i != length; i++)
+ masking_vectors (ctx, cov_blocks (cov, i), cov_masks (cov, i));
+
+ return cov;
+}
+
+namespace
+{
+
+/* Stores the incoming edge and previous counters (in SSA form) on that edge
+ for the node e->deston that edge for the node e->dest. The counters record
+ the seen-true (0), seen-false (1), and current-mask (2). They are stored in
+ an array rather than proper members for access-by-index as the code paths
+ tend to be identical for the different counters. */
+struct counters
+{
+ edge e;
+ tree counter[3];
+ tree& operator [] (size_t i) { return counter[i]; }
+};
+
+/* Find the counters for the incoming edge, or null if the edge has not been
+ recorded (could be for complex incoming edges). */
+counters*
+find_counters (vec<counters>& candidates, edge e)
+{
+ for (counters& candidate : candidates)
+ if (candidate.e == e)
+ return &candidate;
+ return NULL;
+}
+
+/* Resolve the SSA for a specific counter. If it is not modified by any
+ incoming edges, simply forward it, otherwise create a phi node of all the
+ candidate counters and return it. */
+tree
+resolve_counter (vec<counters>& cands, size_t kind)
+{
+ gcc_assert (!cands.is_empty ());
+ gcc_assert (kind < 3);
+
+ counters& fst = cands[0];
+ if (!fst.e || fst.e->dest->preds->length () == 1)
+ {
+ gcc_assert (cands.length () == 1);
+ return fst[kind];
+ }
+
+ tree zero0 = build_int_cst (gcov_type_node, 0);
+ tree ssa = make_ssa_name (gcov_type_node);
+ gphi *phi = create_phi_node (ssa, fst.e->dest);
+ for (edge e : fst.e->dest->preds)
+ {
+ counters *prev = find_counters (cands, e);
+ if (prev)
+ add_phi_arg (phi, (*prev)[kind], e, UNKNOWN_LOCATION);
+ else
+ {
+ tree zero = make_ssa_name (gcov_type_node);
+ gimple_stmt_iterator gsi = gsi_start_bb (e->src);
+ gassign *set = gimple_build_assign (zero, zero0);
+ gsi_insert_before (&gsi, set, GSI_NEW_STMT);
+ add_phi_arg (phi, zero, e, UNKNOWN_LOCATION);
+ }
+ }
+ return ssa;
+}
+
+/* Resolve all the counters for a node. Note that the edge is undefined, as
+ * the counters are intended to form the base to push to the successors, and
+ * because the is only meaningful for nodes with a single predecessor. */
+counters
+resolve_counters (vec<counters>& cands)
+{
+ counters next;
+ next[0] = resolve_counter (cands, 0);
+ next[1] = resolve_counter (cands, 1);
+ next[2] = resolve_counter (cands, 2);
+ return next;
+}
+
+}
+
+/* Add instrumentation to a decision subgraph. expr should be the
+ (topologically sorted) block of nodes returned by cov_graphs, and masks the
+ block of bitsets returned by cov_blocks. condno should be the index of this
+ condition in the function, i.e. the same argument given to
+ cov_{masks,graphs}. expr may contain nodes in-between the conditions, e.g.
+ when an operand contains a function call, or there is a setjmp and the cfg
+ is filled with complex edges.
+
+ Every node is annotated with three counters; the true, false, and mask
+ value. First, walk the graph and determine what if there are multiple
+ possible values for either accumulator depending on the path taken, in which
+ case a phi node is created and registered as the accumulator. Then, those
+ values are pushed as accumulators to the immediate successors. Because expr
+ is topologically ordered, all predecessors will have been considered before
+ the successor. Finally, expr is traversed again to look for edges to the
+ outcomes, that is, edges with a destination outside of expr, and the local
+ accumulators are flushed to the global gcov counters on these edges. In
+ some cases there are edge splits that cause 3+ edges to the two outcome
+ nodes.
+
+ If a complex edge is taken (e.g. on a longjmp) the accumulators are poisoned
+ so that there will be no change to the global counters.
+
+ It is important that the flushes happen on on the outcome's incoming
+ edges, otherwise flushes could be lost to exception handling.
+
+ void fn (int a)
+ {
+ if (a)
+ fclose ();
+ exit ();
+ }
+
+ Can yield the CFG:
+ A
+ |\
+ | B
+ |/
+ e
+
+ This typically only happen in optimized builds, but gives linker errors
+ because the counter is left as an undefined symbol. */
+size_t
+instrument_decisions (array_slice<basic_block> expr, size_t condno,
+ array_slice<uint64_t> masks)
+{
+ tree zero = build_int_cst (gcov_type_node, 0);
+ tree poison = build_int_cst (gcov_type_node, ~0ULL);
+
+ hash_map<basic_block, auto_vec<counters>> table;
+ counters fst;
+ fst.e = NULL;
+ fst[0] = zero;
+ fst[1] = zero;
+ fst[2] = zero;
+ table.get_or_insert (expr[0]).safe_push (fst);
+
+ unsigned xi = 0;
+ tree rhs = build_int_cst (gcov_type_node, 1ULL << xi);
+ for (basic_block current : expr)
+ {
+ vec<counters> *candidates = table.get (current);
+ gcc_assert (candidates);
+ counters prev = resolve_counters (*candidates);
+
+ int increment = 0;
+ for (edge e : current->succs)
+ {
+ counters next = prev;
+ next.e = e;
+
+ if (e->flags & EDGE_CONDITION)
+ {
+ const int k = condition_index (e->flags);
+ next[k] = emit_bitwise_op (e, prev[k], BIT_IOR_EXPR, rhs);
+ if (masks[2*xi + k])
+ {
+ tree m = build_int_cst (gcov_type_node, masks[2*xi + k]);
+ next[2] = emit_bitwise_op (e, prev[2], BIT_IOR_EXPR, m);
+ }
+ increment = 1;
+ }
+ else if (e->flags & EDGE_COMPLEX)
+ {
+ /* A complex edge has been taken - wipe the accumulators and
+ poison the mask so that this path does not contribute to
+ coverage. */
+ next[0] = poison;
+ next[1] = poison;
+ next[2] = poison;
+ }
+ table.get_or_insert (e->dest).safe_push (next);
+ }
+ xi += increment;
+ if (increment)
+ rhs = build_int_cst (gcov_type_node, 1ULL << xi);
+ }
+
+ gcc_assert (xi > 0);
+
+ const tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
+ const bool atomic = flag_profile_update == PROFILE_UPDATE_ATOMIC;
+ const tree atomic_ior = builtin_decl_explicit
+ (TYPE_PRECISION (gcov_type_node) > 32
+ ? BUILT_IN_ATOMIC_FETCH_OR_8
+ : BUILT_IN_ATOMIC_FETCH_OR_4);
+
+ /* Flush to the gcov counters. */
+ for (const basic_block b : expr)
+ {
+ if (!block_conditional_p (b))
+ continue;
+
+ for (edge e : b->succs)
+ {
+ if ((index_of (e->dest, expr) != -1) && !(e->flags & EDGE_DFS_BACK))
+ continue;
+
+ vec<counters> *cands = table.get (e->dest);
+ gcc_assert (cands);
+ counters *prevp = find_counters (*cands, e);
+ gcc_assert (prevp);
+ counters prev = *prevp;
+
+ /* _true &= ~mask, _false &= ~mask */
+ counters next;
+ next[2] = emit_bitwise_op (e, prev[2], BIT_NOT_EXPR);
+ next[0] = emit_bitwise_op (e, prev[0], BIT_AND_EXPR, next[2]);
+ next[1] = emit_bitwise_op (e, prev[1], BIT_AND_EXPR, next[2]);
+
+ /* _global_t |= _true, _global_false |= _false */
+ for (size_t k = 0; k != 2; ++k)
+ {
+ tree ref = tree_coverage_counter_ref (GCOV_COUNTER_CONDS,
+ 2*condno + k);
+ if (atomic)
+ {
+ ref = unshare_expr (ref);
+ gcall *flush = gimple_build_call (atomic_ior, 3,
+ build_addr (ref),
+ next[k], relaxed);
+ gsi_insert_on_edge (e, flush);
+ }
+ else
+ {
+ tree get = emit_assign (e, ref);
+ tree put = emit_bitwise_op (e, next[k], BIT_IOR_EXPR, get);
+ emit_assign (e, unshare_expr (ref), put);
+ }
+ }
+ }
+ }
+ return xi;
+}
+
+#undef CONDITIONS_MAX_TERMS
+#undef EDGE_CONDITION
+
/* Do initialization work for the edge profiler. */
/* Add code:
@@ -758,7 +2069,7 @@ tree_profiling (void)
thunk = true;
/* When generate profile, expand thunk to gimple so it can be
instrumented same way as other functions. */
- if (profile_arc_flag)
+ if (profile_arc_flag || profile_condition_flag)
expand_thunk (node, false, true);
/* Read cgraph profile but keep function as thunk at profile-use
time. */
@@ -803,7 +2114,7 @@ tree_profiling (void)
release_profile_file_filtering ();
/* Drop pure/const flags from instrumented functions. */
- if (profile_arc_flag || flag_test_coverage)
+ if (profile_arc_flag || profile_condition_flag || flag_test_coverage)
FOR_EACH_DEFINED_FUNCTION (node)
{
if (!gimple_has_body_p (node->decl)
@@ -920,7 +2231,7 @@ pass_ipa_tree_profile::gate (function *)
disabled. */
return (!in_lto_p && !flag_auto_profile
&& (flag_branch_probabilities || flag_test_coverage
- || profile_arc_flag));
+ || profile_arc_flag || profile_condition_flag));
}
} // anon namespace
@@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters __attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}
#endif
+#ifdef L_gcov_merge_ior
+void __gcov_merge_ior (gcov_type *counters __attribute__ ((unused)),
+ unsigned n_counters __attribute__ ((unused))) {}
+#endif
+
#ifdef L_gcov_merge_topn
void __gcov_merge_topn (gcov_type *counters __attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}