From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1851) id BD11B383A60D; Tue, 21 Jun 2022 07:49:30 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BD11B383A60D Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Martin Liska To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/marxin/heads/gcov-conditions-v5)] Add it. X-Act-Checkin: gcc X-Git-Author: Martin Liska X-Git-Refname: refs/users/marxin/heads/gcov-conditions-v5 X-Git-Oldrev: 70454c50b4592fe6876ecca13268264e395e058f X-Git-Newrev: 6e9108867c0cccbe7a1fd34e5798dc2ef768c125 Message-Id: <20220621074930.BD11B383A60D@sourceware.org> Date: Tue, 21 Jun 2022 07:49:30 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 21 Jun 2022 07:49:30 -0000 https://gcc.gnu.org/g:6e9108867c0cccbe7a1fd34e5798dc2ef768c125 commit 6e9108867c0cccbe7a1fd34e5798dc2ef768c125 Author: Martin Liska Date: Tue Jun 21 09:47:46 2022 +0200 Add it. Diff: --- gcc/builtins.cc | 2 +- gcc/collect2.cc | 5 +- gcc/common.opt | 8 + gcc/doc/gcov.texi | 36 + gcc/doc/invoke.texi | 19 + gcc/gcc.cc | 4 +- gcc/gcov-counter.def | 3 + gcc/gcov-dump.cc | 24 + gcc/gcov-io.h | 3 + gcc/gcov.cc | 193 +++++- gcc/ipa-inline.cc | 2 +- gcc/ipa-split.cc | 3 +- gcc/passes.cc | 3 +- gcc/profile.cc | 80 ++- gcc/profile.h | 23 + gcc/testsuite/g++.dg/gcov/gcov-18.C | 234 +++++++ gcc/testsuite/gcc.misc-tests/gcov-19.c | 1136 ++++++++++++++++++++++++++++++++ gcc/testsuite/gcc.misc-tests/gcov-20.c | 22 + gcc/testsuite/gcc.misc-tests/gcov-21.c | 16 + gcc/testsuite/lib/gcov.exp | 187 +++++- gcc/tree-profile.cc | 956 ++++++++++++++++++++++++++- 21 files changed, 2930 insertions(+), 29 deletions(-) diff --git a/gcc/builtins.cc b/gcc/builtins.cc index 971b18c3745..a922ab0b99d 100644 --- a/gcc/builtins.cc +++ b/gcc/builtins.cc @@ -5581,7 +5581,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 diff --git a/gcc/collect2.cc b/gcc/collect2.cc index d81c7f28f16..7b0968d535d 100644 --- a/gcc/collect2.cc +++ b/gcc/collect2.cc @@ -1032,9 +1032,9 @@ main (int argc, char **argv) lto_mode = LTO_MODE_LTO; } - /* -fno-profile-arcs -fno-test-coverage -fno-branch-probabilities + /* -fno-profile-arcs -fno-profile-conditions -fno-test-coverage -fno-branch-probabilities -fno-exceptions -w -fno-whole-program */ - num_c_args += 6; + 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"; diff --git a/gcc/common.opt b/gcc/common.opt index 32917aafcae..5aa629d10a8 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -865,6 +865,10 @@ 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 coverage gives up. + Wmissing-profile Common Var(warn_missing_profile) Init(1) Warning Warn in case profiles in -fprofile-use do not exist. @@ -2317,6 +2321,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. diff --git a/gcc/doc/gcov.texi b/gcc/doc/gcov.texi index a1f7d26e610..7f2c0d00d94 100644 --- a/gcc/doc/gcov.texi +++ b/gcc/doc/gcov.texi @@ -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,13 @@ 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). + @item -d @itemx --display-progress Display the progress on the standard output. @@ -293,6 +301,7 @@ Each @var{line} has the following form: @{ "branches": ["$branch"], "count": 2, + "conditions": ["$condition"], "line_number": 15, "unexecuted_block": false, "function_name": "foo", @@ -341,6 +350,33 @@ Fields of the @var{branch} element have following semantics: @var{throw}: true when the branch is an exceptional branch @end itemize +Each @var{condition} element have the following semantics: + +@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 conditions in this expression + +@item +@var{covered}: number of covered conditions 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). diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 50f57877477..994ffdace40 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -601,6 +601,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 @gol +-fprofile-conditions @gol -fprofile-abs-path @gol -fprofile-dir=@var{path} -fprofile-generate -fprofile-generate=@var{path} @gol -fprofile-info-section -fprofile-info-section=@var{name} @gol @@ -6061,6 +6062,13 @@ error. @option{-Wno-coverage-invalid-line-number} can be used to disable the warning or @option{-Wno-error=coverage-invalid-line-number} can be used to disable the error. +@item -Wno-coverage-too-many-conditions +@opindex Wno-coverage-too-many-conditions +@opindex Wcoverage-too-many-conditions +Warn in case a condition 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. + @item -Wno-cpp @r{(C, Objective-C, C++, Objective-C++ and Fortran only)} @opindex Wno-cpp @opindex Wcpp @@ -15442,6 +15450,13 @@ E.g. @code{gcc a.c b.c -o binary} would generate @file{binary-a.gcda} and @xref{Cross-profiling}. +@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. The +data may be used to verify that all terms in a booleans are tested and have an +effect on the outcome of a condition. + @cindex @command{gcov} @item --coverage @opindex coverage @@ -15502,6 +15517,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 boolean values that have an independent effect +on the outcome of that expression. + @need 2000 @item -ftest-coverage @opindex ftest-coverage diff --git a/gcc/gcc.cc b/gcc/gcc.cc index 5cbb38560b2..3c0c40bf388 100644 --- a/gcc/gcc.cc +++ b/gcc/gcc.cc @@ -1165,7 +1165,7 @@ proper position among the other output files. */ %:include(libgomp.spec)%(link_gomp)}\ %{fgnu-tm:%:include(libitm.spec)%(link_itm)}\ %(mflib) " 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 @@ -1282,7 +1282,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}}}"; diff --git a/gcc/gcov-counter.def b/gcc/gcov-counter.def index 6d2182bd3db..96563a59a45 100644 --- a/gcc/gcov-counter.def +++ b/gcc/gcov-counter.def @@ -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) diff --git a/gcc/gcov-dump.cc b/gcc/gcov-dump.cc index 0804c794e9e..12830e5984e 100644 --- a/gcc/gcov-dump.cc +++ b/gcc/gcov-dump.cc @@ -35,6 +35,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); @@ -71,6 +72,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} @@ -381,6 +383,28 @@ tag_arcs (const char *filename ATTRIBUTE_UNUSED, } } +static void +tag_conditions (const char *filename ATTRIBUTE_UNUSED, + unsigned tag ATTRIBUTE_UNUSED, int length ATTRIBUTE_UNUSED, + unsigned depth) +{ + unsigned n_conditions = GCOV_TAG_CONDS_NUM (length); + + printf (" %u conditionals", 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, diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h index 30947634d73..eaf3f366f5d 100644 --- a/gcc/gcov-io.h +++ b/gcc/gcov-io.h @@ -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) diff --git a/gcc/gcov.cc b/gcc/gcov.cc index 27be5ff0911..04bbc774eec 100644 --- a/gcc/gcov.cc +++ b/gcc/gcov.cc @@ -79,6 +79,7 @@ using namespace std; class function_info; class block_info; class source_info; +class condition_info; /* Describes an arc between two basic blocks. */ @@ -132,6 +133,28 @@ public: vector lines; }; +class condition_info +{ +public: + condition_info (); + + int popcount () const; + + gcov_type_unsigned truev; + gcov_type_unsigned falsev; + + unsigned n_terms; +}; + +condition_info::condition_info (): truev (0), falsev (0), n_terms (0) +{ +} + +int condition_info::popcount () const +{ + return __builtin_popcountll (truev) + __builtin_popcountll (falsev); +} + /* Describes a basic block. Contains lists of arcs to successor and predecessor blocks. */ @@ -165,6 +188,8 @@ public: /* Block is a landing pad for longjmp or throw. */ unsigned is_nonlocal_return : 1; + condition_info conditions; + vector locations; struct @@ -275,6 +300,8 @@ public: vector blocks; unsigned blocks_executed; + vector conditions; + /* Raw arc coverage counts. */ vector counts; @@ -351,6 +378,9 @@ struct coverage_info int branches_executed; int branches_taken; + int conditions; + int conditions_covered; + int calls; int calls_executed; @@ -550,6 +580,10 @@ static int multiple_files = 0; static int flag_branches = 0; +/* Output conditions (modified condition/decision coverage) */ + +static int flag_conditions = 0; + /* Show unconditional branches too. */ static int flag_unconditional = 0; @@ -656,6 +690,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 *); @@ -664,6 +699,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 *); @@ -928,6 +964,7 @@ 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 condition coverage in output (MC/DC)\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"); @@ -980,6 +1017,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' }, @@ -1008,7 +1046,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) @@ -1025,6 +1063,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. */ @@ -1132,6 +1173,45 @@ output_intermediate_json_line (json::array *object, } } + json::array *conditions = new json::array (); + lineo->set ("conditions", conditions); + if (flag_conditions) + { + vector::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); } @@ -1956,6 +2036,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 (); @@ -2086,11 +2188,26 @@ read_count_file (void) goto cleanup; } } - else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn) + 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); if (length != GCOV_TAG_COUNTER_LENGTH (fn->counts.size ())) - goto mismatch; + goto mismatch; if (read_length > 0) for (ix = 0; ix != fn->counts.size (); ix++) @@ -2430,6 +2547,13 @@ add_branch_counts (coverage_info *coverage, const arc_info *arc) } } +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. */ @@ -2533,7 +2657,14 @@ file_summary (const coverage_info *coverage) coverage->calls); else fnotice (stdout, "No calls\n"); + } + + if (flag_conditions) + fnotice (stdout, "Conditions covered:%s of %d\n", + format_gcov (coverage->conditions_covered, + coverage->conditions, 2), + coverage->conditions); } /* Canonicalize the filename NAME by canonicalizing directory @@ -2760,6 +2891,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::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 @@ -2861,6 +2998,31 @@ accumulate_line_counts (source_info *src) } } +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, "conditions 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)) + fnotice (gcov_file, "condition %2u not covered (true)\n", i); + if (!(index & info.falsev)) + fnotice (gcov_file, "condition %2u not covered (false)\n", i); + } +} + /* Output information about ARC number IX. Returns nonzero if anything is output. */ @@ -3071,16 +3233,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::const_iterator it = line->branches.begin (); + it != line->branches.end (); it++) + ix += output_branch_count (f, ix, (*it)); + } - ix = 0; - for (vector::const_iterator it = line->branches.begin (); - it != line->branches.end (); it++) - ix += output_branch_count (f, ix, (*it)); + if (flag_conditions) + { + for (vector::const_iterator it = line->blocks.begin (); + it != line->blocks.end (); it++) + output_conditions (f, *it); + } } } diff --git a/gcc/ipa-inline.cc b/gcc/ipa-inline.cc index 22a009b7435..52493e2dceb 100644 --- a/gcc/ipa-inline.cc +++ b/gcc/ipa-inline.cc @@ -646,7 +646,7 @@ can_early_inline_edge_p (struct cgraph_edge *e) " edge not inlinable: not in SSA form\n"); return false; } - else if (profile_arc_flag + else 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", diff --git a/gcc/ipa-split.cc b/gcc/ipa-split.cc index 60021bad13c..9890518e11f 100644 --- a/gcc/ipa-split.cc +++ b/gcc/ipa-split.cc @@ -1929,7 +1929,8 @@ 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 + && !profile_condition_flag); } } // anon namespace diff --git a/gcc/passes.cc b/gcc/passes.cc index 36e5b4ac45f..ee099188844 100644 --- a/gcc/passes.cc +++ b/gcc/passes.cc @@ -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 (); diff --git a/gcc/profile.cc b/gcc/profile.cc index 08af512cbca..fa023596d2a 100644 --- a/gcc/profile.cc +++ b/gcc/profile.cc @@ -66,9 +66,12 @@ 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" +int instrument_decisions (basic_block*, int, int, tree*, gcov_type_unsigned*); + /* Map from BBs/edges to gcov counters. */ vec bb_gcov_counts; hash_map *edge_gcov_counts; @@ -100,6 +103,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 *); @@ -1154,6 +1158,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 @@ -1172,6 +1182,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++; @@ -1380,7 +1391,7 @@ branch_prob (bool thunk) /* Compute two different checksums. Note that we want to compute the checksum in only once place, since it depends on the shape - of the control flow which can change during + of the control flow which can change during various transformations. */ if (thunk) { @@ -1396,10 +1407,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)); @@ -1511,29 +1530,75 @@ branch_prob (bool thunk) remove_fake_edges (); + if (profile_condition_flag || profile_arc_flag) + gimple_init_gcov_profiler (); + + if (profile_condition_flag) + { + condition_coverage cov; + const int nconds = cov.find_conditions (cfun); + total_num_conds += nconds; + + if (coverage_counter_alloc (GCOV_COUNTER_CONDS, 2 * nconds)) + { + /* Add two extra variables to the function for the local + accumulators, which are zero'd on the entry of a new conditional. + The local accumulators are conceptually independent, but are + reused so that less extra stack spaced required which matters for + embedded targets (who are particularly interested in condition + coverage). */ + tree accu[2] = { + build_decl (UNKNOWN_LOCATION, VAR_DECL, + get_identifier ("__accu_t"), get_gcov_type ()), + build_decl (UNKNOWN_LOCATION, VAR_DECL, + get_identifier ("__accu_f"), get_gcov_type ()), + }; + + gcov_position_t offset {}; + if (output_to_file) + offset = gcov_write_tag (GCOV_TAG_CONDS); + + for (int i = 0; i < nconds; ++i) + { + array_slice expr = cov.blocks (i); + array_slice masks = cov.masks (i); + gcc_assert (expr.is_valid ()); + gcc_assert (masks.is_valid ()); + + int terms = instrument_decisions (expr.begin (), expr.size (), i, + accu, masks.begin ()); + if (output_to_file) + { + gcov_write_unsigned (expr.front ()->index); + gcov_write_unsigned (terms); + } + } + if (output_to_file) + gcov_write_length (offset); + } + } + /* 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 (); + coverage_end_function (lineno_checksum, cfg_checksum); if (flag_branch_probabilities && (profile_status_for_fn (cfun) == PROFILE_READ)) @@ -1663,6 +1728,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; } @@ -1702,5 +1768,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); } } diff --git a/gcc/profile.h b/gcc/profile.h index c5b6f488996..16ec083dcc1 100644 --- a/gcc/profile.h +++ b/gcc/profile.h @@ -77,4 +77,27 @@ extern void get_working_sets (void); profile.cc. */ extern struct gcov_summary *profile_info; +/* Condition coverage. Implemented in tree-profile.cc */ +struct condition_coverage +{ +public: + condition_coverage () = default; + + int find_conditions (struct function*); + + unsigned length () const noexcept (true); + + /* Get the blocks for the nth conditional expression in this function. */ + array_slice blocks (unsigned) noexcept (true); + + /* Get the masking vectors for the nth conditional expression in this + function. */ + array_slice masks (unsigned) noexcept (true); + +private: + auto_vec m_index; + auto_vec m_blocks; + auto_vec m_masks; +}; + #endif /* PROFILE_H */ diff --git a/gcc/testsuite/g++.dg/gcov/gcov-18.C b/gcc/testsuite/g++.dg/gcov/gcov-18.C new file mode 100644 index 00000000000..310ed5297c0 --- /dev/null +++ b/gcc/testsuite/g++.dg/gcov/gcov-18.C @@ -0,0 +1,234 @@ +/* { dg-options "--coverage -fprofile-conditions -std=c++11" } */ +/* { dg-do run { target native } } */ + +#include +#include + +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 } } } */ diff --git a/gcc/testsuite/gcc.misc-tests/gcov-19.c b/gcc/testsuite/gcc.misc-tests/gcov-19.c new file mode 100644 index 00000000000..93b597bee68 --- /dev/null +++ b/gcc/testsuite/gcc.misc-tests/gcov-19.c @@ -0,0 +1,1136 @@ +/* { dg-options "-fprofile-conditions -ftest-coverage" } */ +/* { dg-do run { target native } } */ + +/* some side effect to stop branches from being pruned */ +int x = 0; + +/* || 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) */ + x = a + b + c; + } + else + { + x = c; + } +} + +/* 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: + /* similar 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) */ + /* conditions(end) */ + goto then; +} + +/* 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--; +} + +/* 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) { 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 MC/DC, even with all input combinations, because not all + * variables independently affect the decision + */ +void +mcdc013a (int a, int /* b */, int c) +{ + /* + * Specification: (a && b) || c + * + * But the expression was implemented wrong. 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; + } +} + + +/* 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 +noop () {} + +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) */ + { + right = b > right ? a : right; /* conditions(2/2) */ + } + } while (n-- > 0); /* conditions(2/2) */ +} + +int id (int x) { return x; } +int inv (int x) { return !x; } + +/* 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) */ + 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) */ +} + +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; +} + +/* 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; +} + +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); + + 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); + + 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); + + 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); + + 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); + + 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); +} + +/* { dg-final { run-gcov conditions { --conditions gcov-19.c } } } */ diff --git a/gcc/testsuite/gcc.misc-tests/gcov-20.c b/gcc/testsuite/gcc.misc-tests/gcov-20.c new file mode 100644 index 00000000000..847dae495db --- /dev/null +++ b/gcc/testsuite/gcc.misc-tests/gcov-20.c @@ -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 } } } */ diff --git a/gcc/testsuite/gcc.misc-tests/gcov-21.c b/gcc/testsuite/gcc.misc-tests/gcov-21.c new file mode 100644 index 00000000000..978be3276a2 --- /dev/null +++ b/gcc/testsuite/gcc.misc-tests/gcov-21.c @@ -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 () +{ +} diff --git a/gcc/testsuite/lib/gcov.exp b/gcc/testsuite/lib/gcov.exp index 9d5b2cdb86b..88f28d26bb6 100644 --- a/gcc/testsuite/lib/gcov.exp +++ b/gcc/testsuite/lib/gcov.exp @@ -174,6 +174,180 @@ 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 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 uncovered (true) for terms $shouldt" + set ok 0 + } + + if {[llength $shouldf] != 0} { + fail "$prefix: expected uncovered (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 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 \(true\)} "$line" all cond] { + set i [lsearch $shouldt $cond] + if {$i != -1} { + set shouldt [lreplace $shouldt $i $i] + } else { + fail "$testname line $n: unexpected uncovered term $cond (true)" + set ok 0 + } + } elseif [regexp {condition +(\d+) not covered \(false\)} "$line" all cond] { + set i [lsearch $shouldf $cond] + if {$i != -1} { + set shouldf [lreplace $shouldf $i $i] + } else { + fail "$testname line $n: unexpected uncovered term $cond (false)" + set ok 0 + } + } elseif [regexp {conditions 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 +495,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 +506,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 +582,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 +601,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 } diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc index 97aab8801d0..3b85d01437a 100644 --- a/gcc/tree-profile.cc +++ b/gcc/tree-profile.cc @@ -1,4 +1,4 @@ -/* Calculate branch probabilities, and basic block execution counts. +/* Calculate branch probahilities, and basic block execution counts. Copyright (C) 1990-2022 Free Software Foundation, Inc. Contributed by James E. Wilson, UC Berkeley/Cygnus Support; based on some ideas from Dain Samples of UC Berkeley. @@ -58,6 +58,11 @@ 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" + +#include "tree.h" +#include "gimple-pretty-print.h" static GTY(()) tree gcov_type_node; static GTY(()) tree tree_interval_profiler_fn; @@ -73,6 +78,949 @@ static GTY(()) tree ic_tuple_var; static GTY(()) tree ic_tuple_counters_field; static GTY(()) tree ic_tuple_callee_field; +namespace +{ + +struct conds_ctx +{ + /* 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 (the number of terms plus the two outcomes). */ + auto_vec blocks; + + /* 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; + + /* 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 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_sbitmap G1; + auto_sbitmap G2; + auto_sbitmap G3; + auto_vec B1; + auto_vec B2; + + explicit conds_ctx (unsigned size) noexcept (true) : marks (size), + G1 (size), G2 (size), G3 (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& 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& 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 (sizeof (gcov_type_unsigned) * BITS_PER_UNIT) +#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* im = (const vec*) 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 checks. 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 blocks) +{ + const int size = int (blocks.size ()); + for (int i = 0; i < size; i++) + if (blocks[i] == needle) + return 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 [1], it should be considered a + single-successor. + + [1] if this is not possible, these functions can be removed and replaced by + their basic-block.h cousins. */ +bool +single (const vec *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 *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. */ +edge +contract_edge (edge e) +{ + edge source = e; + while (true) + { + basic_block dest = e->dest; + if (!single (dest->preds)) + return source; + if (e->flags & EDGE_DFS_BACK) + return source; + if (block_conditional_p (dest)) + return e; + + e = single_edge (dest->succs); + if (!e) + return source; + } +} + +/* 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 (src->preds)) + return e; + e = single_edge (src->preds); + } +} + +/* Scan upwards and find the ancestors of the node pre that are also in G, + stopping at post. The ancestors are recorded in the bimap. + dfs_enumerate_from () won't work as the filter function needs edge + information. */ +void +scan_up (sbitmap ancestors, basic_block pre, basic_block post, const sbitmap G) +{ + if (!bitmap_bit_p (G, pre->index)) + return; + + bitmap_set_bit (ancestors, pre->index); + bitmap_set_bit (ancestors, post->index); + if (pre == post) + return; + + auto_vec stack; + stack.safe_push (pre); + + while (!stack.is_empty()) + { + basic_block b = stack.pop (); + if (single (b->preds)) + { + edge e = single_edge (b->preds); + e = contract_edge_up (e); + b = e->dest; + } + + for (edge e : b->preds) + { + basic_block src = e->src; + if (bitmap_bit_p (ancestors, e->src->index)) + continue; + if (!bitmap_bit_p (G, e->src->index)) + continue; + bitmap_set_bit (ancestors, src->index); + 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 = (e)->dest; + if (e->flags & EDGE_FALSE_VALUE) + c.f = (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 appears as short circuiting in the reversed expression. + This means we can find the limits, the last term in previous subexpressions + by following the edges that short circuit to the same outcome. + +TODO: doc algo + + 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. lim = a.succs[0] = b, which has 1 ancestor a and so + the masking vector is b[1] = {a}. + + 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} + + b[0] and d[0] are identical to the a || b example, but d[1]. + T.preds = {b,d}, top = b, bot = d, and b.succs[0] = c. ancestors(c) = {a,b} + which is d[1] and the search terminates as a.preds is empty and b.preds are + discarded. + + The masking vector is represented as two bitfields per term in the + expression. The expression a || b && c becomes the term vector [a b c] and + the bitsets are masks = [a.true a.false b.true ...]. The kth bit is set if + the the kth term is masked by the node-outcome. */ +void +build_masks (conds_ctx& ctx, array_slice blocks, + array_slice masks) +{ + gcc_assert (!blocks.empty ()); + gcc_assert (blocks.is_valid ()); + gcc_assert (masks.is_valid ()); + + sbitmap marks = ctx.G1; + sbitmap expr = ctx.G2; + vec& queue = ctx.B1; + const vec& index_map = ctx.index_map; + bitmap_clear (expr); + + for (const basic_block b : blocks) + bitmap_set_bit (expr, b->index); + + // Ignore the first term as it cannot mask anything + array_slice tail (blocks.begin () + 1, blocks.size () - 1); + + for (const basic_block b : tail) + { + for (edge e1 : b->preds) + for (edge e2 : b->preds) + { + const basic_block top = e1->src; + const basic_block bot = e2->src; + const unsigned flag = e1->flags & e2->flags & (EDGE_CONDITION); + + if (!flag) + 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 term = index_of (bot, blocks); + const int m = term*2 + condition_index (flag); + 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] |= gcov_type_unsigned (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); + } + } + } + } +} + +/* TODO: doc */ +void +scan_down (basic_block pre, basic_block post, sbitmap expr, + vec& out) +{ + out.safe_push (pre); + bitmap_set_bit (expr, pre->index); + for (unsigned pos = 0; pos < out.length (); pos++) + { + for (edge e : out[pos]->succs) + { + basic_block dest = contract_edge (e)->dest; + if (dest == post) + continue; + if (!dominated_by_p (CDI_DOMINATORS, dest, pre)) + continue; + if (!block_conditional_p (dest)) + continue; + if (bitmap_bit_p (expr, dest->index)) + continue; + if (e->flags & EDGE_DFS_BACK) + continue; + + bitmap_set_bit (expr, dest->index); + out.safe_push (dest); + } + } +} + +/* Find the neighborhood of the graph G = [blocks, blocks+n), the + successors of nodes in G that are not also in G. */ +void +neighborhood (vec& blocks, const sbitmap G, vec& out) +{ + for (const basic_block b : blocks) + { + for (edge e : b->succs) + { + basic_block dest = contract_edge (e)->dest; + if (bitmap_bit_p (G, dest->index)) + continue; + if (!out.contains (dest)) + out.safe_push (dest); + } + } +} + +/* Find and isolate the expression starting at pre. + + Make a cut C = (G, G') by following all condition edges from pre and find + the neighborhood of G. The first conditional expression is made up of the + intersection of ancestors of every node in the neighborhood. */ +void +find_first_conditional (conds_ctx &ctx, basic_block pre, vec& out) +{ + sbitmap expr = ctx.G1; + sbitmap reachable = ctx.G2; + sbitmap ancestors = ctx.G3; + bitmap_clear (expr); + bitmap_clear (reachable); + + vec& G = ctx.B1; + vec& NG = ctx.B2; + G.truncate (0); + NG.truncate (0); + + basic_block post = get_immediate_dominator (CDI_POST_DOMINATORS, pre); + scan_down (pre, post, expr, G); + if (G.length () == 1) + { + out.safe_push (pre); + return; + } + + neighborhood (G, expr, NG); + bitmap_copy (reachable, expr); + + for (const basic_block neighbor : NG) + { + bitmap_clear (ancestors); + for (edge e : neighbor->preds) + scan_up (ancestors, e->src, pre, reachable); + bitmap_and (expr, expr, ancestors); + } + + for (const basic_block b : G) + if (bitmap_bit_p (expr, b->index)) + out.safe_push (b); + out.sort (cmp_index_map, &ctx.index_map); +} + +/* Emit lhs = op1 op2 on edges. This emits non-atomic instructions and + should only be used on the local accumulators. */ +void +emit_bitwise_op (edge e, tree lhs, tree op1, tree_code op, tree op2) +{ + tree tmp; + gassign *read; + gassign *bitw; + gimple *write; + + tmp = make_temp_ssa_name (gcov_type_node, NULL, "__conditions_tmp"); + read = gimple_build_assign (tmp, op1); + tmp = make_temp_ssa_name (gcov_type_node, NULL, "__conditions_tmp"); + bitw = gimple_build_assign (tmp, op, gimple_assign_lhs (read), op2); + write = gimple_build_assign (lhs, gimple_assign_lhs (bitw)); + + gsi_insert_on_edge (e, read); + gsi_insert_on_edge (e, bitw); + gsi_insert_on_edge (e, write); +} + +/* Visitor for make_index_map. */ +void +make_index_map_visit (basic_block b, vec& L, vec& 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& blocks, int max_index, + vec& L, vec& 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 int nblocks = L.length (); + for (int i = 0; i < nblocks; i++) + { + gcc_assert (L[i]->index != -1); + index_map[L[i]->index] = 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& +collect_conditions (conds_ctx& ctx, const basic_block block) +{ + vec& 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; + } + + find_first_conditional (ctx, block, blocks); + ctx.mark (blocks); + + if (blocks.length () <= CONDITIONS_MAX_TERMS) + { + outcomes out = conditional_succs (blocks.last ()); + blocks.safe_push (out.t); + blocks.safe_push (out.f); + } + else + { + blocks.truncate (0); + 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", + blocks.length ()); + } + return blocks; +} + +/* Used for dfs_enumerate_from () to include all reachable nodes. */ +bool yes (const_basic_block, const void *) { + return true; +} + +} + +array_slice +condition_coverage::blocks (unsigned n) noexcept (true) +{ + if (n >= m_index.length ()) + return array_slice::invalid (); + + basic_block *begin = m_blocks.begin () + m_index[n]; + basic_block *end = m_blocks.begin () + m_index[n + 1]; + return array_slice (begin, end - begin); +} + +array_slice +condition_coverage::masks (unsigned n) noexcept (true) +{ + if (n >= m_index.length ()) + return array_slice::invalid (); + + gcov_type_unsigned *begin = m_masks.begin () + 2*m_index[n]; + gcov_type_unsigned *end = m_masks.begin () + 2*m_index[n + 1]; + return array_slice (begin, end - begin); +} + +unsigned +condition_coverage::length () const noexcept (true) +{ + if (m_index.is_empty ()) + return 0; + return m_index.length () - 1; +} + +/* 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 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 reduce work. + + 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. + + Implementation and interface + ---------------------------- + Two public functions - find_conditions and instrument_decisions. + + find_conditions outputs two arrays, blocks and sizes. The sizes describes + the ranges of blocks that make up every conditional, in a [first, last) + fashion, i.e. begin = blocks[sizes[n]], end = blocks[sizes[n+1]] for + expression n. The function returns the number of expressions. + + The coverage is designed to get most of its memory needs met by the caller, + and heavily uses the end of the blocks array for buffer. This is both for + performance (no resizes, amortized cost of allocation) and + ease-of-implementation. This makes the caller responsible for allocating + large enough arrays. + + blocks: + Every permanent conditions add 2 blocks (the true & false dest blocks), and + assuming a worst case of one-block-per-expr just storing the output needs + 3*n_basic_blocks_for_fn (). Additionally, the searches might need to buffer + the full graph between entry and exit [1]. In total that means + 5*n_basic_blocks_for_fn () should should be plenty, and the savings for + reducing this number is probably not worth the risk. + sizes: + sizes gets one entry per expression plus initial, so + 1+n_basic_blocks_for_fn () is sufficient. + + instrument_decisions uses the information provided by find_conditions to + inject code onto edges in the CFG. Every instrumented function gets local + accumulators zero'd on function entry, which on function exit are flushed to + the global accumulators (created by coverage_counter_alloc ()). + + [1] In truth, the set of nodes that could be buffered gets smaller as the + algorithm walks the CFG, but assuming just using node-count comes at + little run-time cost and is guaranteed to be sufficient. + */ +int +condition_coverage::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 int nblocks = n_basic_blocks_for_fn (fn); + conds_ctx ctx (nblocks); + + auto_vec 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); + + /* 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). */ + m_index.safe_push (0); + for (const basic_block b : dfs) + { + const vec& expr = collect_conditions (ctx, b); + if (!expr.is_empty ()) + { + m_blocks.safe_splice (expr); + m_index.safe_push (m_blocks.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); + + // TODO: must be grow_cleared; if reset (), truncate + m_masks.safe_grow_cleared (2 * m_index.last()); + for (unsigned i = 0; i < this->length (); i++) + build_masks (ctx, blocks (i), masks (i)); + + return this->length (); +} + +int instrument_decisions (basic_block *blocks, int nblocks, int condno, + tree *accu, gcov_type_unsigned *masks) +{ + /* Zero the local accumulators. */ + tree zero = build_int_cst (get_gcov_type (), 0); + for (edge e : blocks[0]->succs) + { + gsi_insert_on_edge (e, gimple_build_assign (accu[0], zero)); + gsi_insert_on_edge (e, gimple_build_assign (accu[1], zero)); + } + /* The true/false target blocks are included in the nblocks set, but + their outgoing edges should not be instrumented. */ + gcc_assert (nblocks > 2); + + array_slice body(blocks, nblocks - 2); + + /* Add instructions for updating the function-local accumulators. */ + for (int i = 0; i < nblocks - 2; i++) + { + for (edge e : blocks[i]->succs) + { + if (!edge_conditional_p (e)) + continue; + + /* accu |= expr[i] */ + const int k = condition_index (e->flags); + tree rhs = build_int_cst (gcov_type_node, 1ULL << i); + emit_bitwise_op (e, accu[k], accu[k], BIT_IOR_EXPR, rhs); + + if (masks[2*i + k] == 0) + continue; + + /* accu &= mask[i] */ + tree mask = build_int_cst (gcov_type_node, ~masks[2*i + k]); + for (int j = 0; j < 2; j++) + emit_bitwise_op (e, accu[j], accu[j], BIT_AND_EXPR, mask); + } + } + + 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); + + /* Add instructions for flushing the local accumulators. + The two last blocks are the outcome blocks, and we need to flush the + accumulators at the end-of-expression. If it is done later then flushes + could be lost to exception handling or unexpected termination. + + It is important that the flushes happen on on the outcome's incoming + edges as it might not have outgoing edges: + + 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. */ + const basic_block outcome_blocks[] = { + blocks[nblocks - 2], + blocks[nblocks - 2], + blocks[nblocks - 1], + blocks[nblocks - 1], + }; + const int outcome[] = { 0, 1, 0, 1 }; + + // TODO: ref -> counter + for (int i = 0; i < 4; i++) + { + const int k = outcome[i]; + for (edge e : outcome_blocks[i]->preds) + { + /* Only instrument edges from inside the expression. Sometimes + complicated control flow (like sigsetjmp and gotos) add + predecessors that don't come from the boolean expression. */ + if (index_of (e->src, body) == -1) + continue; + + tree ref = tree_coverage_counter_ref (GCOV_COUNTER_CONDS, + 2*condno + k); + tree tmp = make_temp_ssa_name (gcov_type_node, NULL, + "__conditions_tmp"); + if (atomic) + { + tree relaxed = build_int_cst (integer_type_node, + MEMMODEL_RELAXED); + ref = unshare_expr (ref); + gassign *read = gimple_build_assign (tmp, accu[k]); + gcall *flush = gimple_build_call (atomic_ior, 3, + build_addr (ref), + gimple_assign_lhs (read), + relaxed); + + gsi_insert_on_edge (e, read); + gsi_insert_on_edge (e, flush); + } + else + { + gassign *read = gimple_build_assign (tmp, ref); + tmp = gimple_assign_lhs (read); + gsi_insert_on_edge (e, read); + ref = unshare_expr (ref); + emit_bitwise_op (e, ref, accu[k], BIT_IOR_EXPR, tmp); + } + } + } + return body.size (); +} + +#undef CONDITIONS_MAX_TERMS +#undef EDGE_CONDITION + /* Do initialization work for the edge profiler. */ /* Add code: @@ -758,7 +1706,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 +1751,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) @@ -897,7 +1845,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