[PATCH v9 1/2] Add condition coverage (MC/DC)

Jørgen Kvalsvik j@lambda.is
Sun Dec 31 15:51:26 GMT 2023


This patch adds support in gcc+gcov for modified condition/decision
coverage (MC/DC) with the -fcondition-coverage flag. MC/DC is a type of
test/code coverage and it is particularly important for safety-critical
applicaitons in industries like aviation and automotive. Notably, MC/DC
is required or recommended by:

    * DO-178C for the most critical software (Level A) in avionics.
    * IEC 61508 for SIL 4.
    * ISO 26262-6 for ASIL D.

>From the SQLite webpage:

    Two methods of measuring test coverage were described above:
    "statement" and "branch" coverage. There are many other test
    coverage metrics besides these two. Another popular metric is
    "Modified Condition/Decision Coverage" or MC/DC. Wikipedia defines
    MC/DC as follows:

        * Each decision tries every possible outcome.
        * Each condition in a decision takes on every possible outcome.
        * Each entry and exit point is invoked.
        * Each condition in a decision is shown to independently affect
          the outcome of the decision.

    In the C programming language where && and || are "short-circuit"
    operators, MC/DC and branch coverage are very nearly the same thing.
    The primary difference is in boolean vector tests. One can test for
    any of several bits in bit-vector and still obtain 100% branch test
    coverage even though the second element of MC/DC - the requirement
    that each condition in a decision take on every possible outcome -
    might not be satisfied.

    https://sqlite.org/testing.html#mcdc

MC/DC comes in different flavours, the most important being unique
cause MC/DC and masking MC/DC - this patch implements masking MC/DC,
which is works well with short circuiting semantics, and according to
John Chilenski's "An Investigation of Three Forms of the Modified
Condition Decision Coverage (MCDC) Criterion" (2001) is as good as
unique cause at catching bugs.

Whalen, Heimdahl, and De Silva "Efficient Test Coverage Measurement for
MC/DC" describes an algorithm for determining masking from an AST walk,
but my algorithm figures this out from analyzing the control flow graph.
The CFG is considered a binary decision diagram and an evaluation
becomes a path through the BDD, which is recorded. Certain paths will
mask ("null out") the contribution from earlier path segments, which can
be determined by finding short circuit endpoints. Masking is the
short circuiting of terms in the reverse-ordered Boolean function, and
the masked terms do not affect the decision like short-circuited
terms do not affect the decision.

A tag/discriminator mapping from gcond->uid is created during
gimplification and made available through the function struct. The
values are unimportant as long as basic conditions constructed from a
single Boolean expression are given the same identifier. This happens in
the breaking down of ANDIF/ORIF trees, so the coverage generally works
well for frontends that create such trees.

Like Whalen et al this implementation records coverage in fixed-size
bitsets which gcov knows how to interpret. This takes only a few bitwise
operations per condition and is very fast, but comes with a limit on the
number of terms in a single boolean expression; the number of bits in a
gcov_unsigned_type (which is usually typedef'd to uint64_t). For most
practical purposes this is acceptable, and by default a warning will be
issued if gcc cannot instrument the expression.  This is a practical
limitation in the implementation, not the algorithm, so support for more
conditions can be added by also introducing arbitrary-sized bitsets.

In action it looks pretty similar to the branch coverage. The -g short
opt carries no significance, but was chosen because it was an available
option with the upper-case free too.

gcov --conditions:

        3:   17:void fn (int a, int b, int c, int d) {
        3:   18:    if ((a && (b || c)) && d)
conditions covered 3/8
condition  0 not covered (true false)
condition  1 not covered (true)
condition  2 not covered (true)
condition  3 not covered (true)
        1:   19:        x = 1;
        -:   20:    else
        2:   21:        x = 2;
        3:   22:}

gcov --conditions --json-format:

"conditions": [
    {
        "not_covered_false": [
            0
        ],
        "count": 8,
        "covered": 3,
        "not_covered_true": [
            0,
            1,
            2,
            3
        ]
    }
],

Expressions with constants may be heavily rewritten before it reaches
the gimplification, so constructs like int x = a ? 0 : 1 becomes
_x = (_a == 0). From source you would expect coverage, but it gets
neither branch nor condition coverage. The same applies to expressions
like int x = 1 || a which are simply replaced by a constant.

The test suite contains a lot of small programs and functions. Some of
these were designed by hand to test for specific behaviours and graph
shapes, and some are previously-failed test cases in other programs
adapted into the test suite.

gcc/ChangeLog:

	* builtins.cc (expand_builtin_fork_or_exec): Check
	  condition_coverage_flag.
	* collect2.cc (main): Add -fno-condition-coverage to OBSTACK.
	* common.opt: Add new options -fcondition-coverage and
	  -Wcoverage-too-many-conditions.
	* doc/gcov.texi: Add --conditions documentation.
	* doc/invoke.texi: Add -fcondition-coverage documentation.
	* function.cc (allocate_struct_function): Init cond_uids.
	* function.h (struct function): Add cond_uids.
	* gcc.cc: Link gcov on -fcondition-coverage.
	* gcov-counter.def (GCOV_COUNTER_CONDS): New.
	* gcov-dump.cc (tag_conditions): New.
	* gcov-io.h (GCOV_TAG_CONDS): New.
	(GCOV_TAG_CONDS_LENGTH): New.
	(GCOV_TAG_CONDS_NUM): New.
	* gcov.cc (class condition_info): New.
	(condition_info::condition_info): New.
	(condition_info::popcount): New.
	(struct coverage_info): New.
	(add_condition_counts): New.
	(output_conditions): New.
	(print_usage): Add -g, --conditions.
	(process_args): Likewise.
	(output_intermediate_json_line): Output conditions.
	(read_graph_file): Read condition counters.
	(read_count_file): Likewise.
	(file_summary): Print conditions.
	(accumulate_line_info): Accumulate conditions.
	(output_line_details): Print conditions.
	* gimplify.cc (next_cond_uid): New.
	(reset_cond_uid): New.
	(shortcut_cond_r): Set condition discriminator.
	(tag_shortcut_cond): New.
	(shortcut_cond_expr): Set condition discriminator.
	(gimplify_cond_expr): Likewise.
	(gimplify_function_tree): Call reset_cond_uid.
	* ipa-inline.cc (can_early_inline_edge_p): Check
	  condition_coverage_flag.
	* ipa-split.cc (pass_split_functions::gate): Likewise.
	* passes.cc (finish_optimization_passes): Likewise.
	* profile.cc (struct condcov): New declaration.
	(cov_length): Likewise.
	(cov_blocks): Likewise.
	(cov_masks): Likewise.
	(cov_maps): Likewise.
	(cov_free): Likewise.
	(instrument_decisions): New.
	(read_thunk_profile): Control output to file.
	(branch_prob): Call find_conditions, instrument_decisions.
	(init_branch_prob): Add total_num_conds.
	(end_branch_prob): Likewise.
	* tree-core.h (struct tree_exp): Add condition_uid.
	* tree-profile.cc (struct conds_ctx): New.
	(CONDITIONS_MAX_TERMS): New.
	(EDGE_CONDITION): New.
	(topological_cmp): New.
	(index_of): New.
	(single_p): New.
	(single_edge): New.
	(contract_edge_up): New.
	(struct outcomes): New.
	(conditional_succs): New.
	(condition_index): New.
	(condition_uid): New.
	(masking_vectors): New.
	(emit_assign): New.
	(emit_bitwise_op): New.
	(make_top_index_visit): New.
	(make_top_index): New.
	(paths_between): New.
	(struct condcov): New.
	(cov_length): New.
	(cov_blocks): New.
	(cov_masks): New.
	(cov_maps): New.
	(cov_free): New.
	(find_conditions): New.
	(struct counters): New.
	(find_counters): New.
	(resolve_counter): New.
	(resolve_counters): New.
	(instrument_decisions): New.
	(tree_profiling): Check condition_coverage_flag.
	(pass_ipa_tree_profile::gate): Likewise.
	* tree.h (SET_EXPR_UID): New.
	(EXPR_COND_UID): New.

libgcc/ChangeLog:

	* libgcov-merge.c (__gcov_merge_ior): New.

gcc/testsuite/ChangeLog:

	* lib/gcov.exp: Add condition coverage test function.
	* g++.dg/gcov/gcov-18.C: New test.
	* gcc.misc-tests/gcov-19.c: New test.
	* gcc.misc-tests/gcov-20.c: New test.
	* gcc.misc-tests/gcov-21.c: New test.
	* gcc.misc-tests/gcov-22.c: New test.
	* gcc.misc-tests/gcov-23.c: New test.
---
 gcc/builtins.cc                        |    2 +-
 gcc/collect2.cc                        |    7 +-
 gcc/common.opt                         |    9 +
 gcc/doc/gcov.texi                      |   38 +
 gcc/doc/invoke.texi                    |   21 +
 gcc/function.cc                        |    1 +
 gcc/function.h                         |    4 +
 gcc/gcc.cc                             |    4 +-
 gcc/gcov-counter.def                   |    3 +
 gcc/gcov-dump.cc                       |   24 +
 gcc/gcov-io.h                          |    3 +
 gcc/gcov.cc                            |  209 ++-
 gcc/gimplify.cc                        |   94 +-
 gcc/ipa-inline.cc                      |    2 +-
 gcc/ipa-split.cc                       |    2 +-
 gcc/passes.cc                          |    3 +-
 gcc/profile.cc                         |   76 +-
 gcc/testsuite/g++.dg/gcov/gcov-18.C    |  258 ++++
 gcc/testsuite/gcc.misc-tests/gcov-19.c | 1737 ++++++++++++++++++++++++
 gcc/testsuite/gcc.misc-tests/gcov-20.c |   22 +
 gcc/testsuite/gcc.misc-tests/gcov-21.c |   16 +
 gcc/testsuite/gcc.misc-tests/gcov-22.c |  103 ++
 gcc/testsuite/gcc.misc-tests/gcov-23.c |  361 +++++
 gcc/testsuite/lib/gcov.exp             |  259 +++-
 gcc/tree-core.h                        |    3 +
 gcc/tree-profile.cc                    | 1057 +++++++++++++-
 gcc/tree.h                             |    4 +
 libgcc/libgcov-merge.c                 |    5 +
 28 files changed, 4287 insertions(+), 40 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-18.C
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-19.c
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-20.c
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-21.c
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-22.c
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-23.c

---

Changes since v8:

* Annotation uses a hash map instead of (ab)using the gimple.uid field.
* Minor documentation updates

So the problems I had with the gc must have been other problems with my
implementation, as the approach itself is fine. It seems like these
problems are gone with this patch, which again uses a hash map in struct
function to map gcond -> uid.

---

diff --git a/gcc/builtins.cc b/gcc/builtins.cc
index aa86ac1545d..f2a044bbbfa 100644
--- a/gcc/builtins.cc
+++ b/gcc/builtins.cc
@@ -5994,7 +5994,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 && !condition_coverage_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 c943f9f577c..af920ff2033 100644
--- a/gcc/collect2.cc
+++ b/gcc/collect2.cc
@@ -1035,9 +1035,9 @@ main (int argc, char **argv)
       lto_mode = LTO_MODE_LTO;
   }
 
-  /* -fno-profile-arcs -fno-test-coverage -fno-branch-probabilities
-     -fno-exceptions -w -fno-whole-program */
-  num_c_args += 6;
+  /* -fno-profile-arcs -fno-condition-coverage -fno-test-coverage
+     -fno-branch-probabilities -fno-exceptions -w -fno-whole-program */
+  num_c_args += 7;
 
   c_argv = XCNEWVEC (char *, num_c_args);
   c_ptr = CONST_CAST2 (const char **, char **, c_argv);
@@ -1233,6 +1233,7 @@ main (int argc, char **argv)
     }
   obstack_free (&temporary_obstack, temporary_firstobj);
   *c_ptr++ = "-fno-profile-arcs";
+  *c_ptr++ = "-fno-condition-coverage";
   *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 161a035d736..b93850b48dd 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -870,6 +870,11 @@ Wcoverage-invalid-line-number
 Common Var(warn_coverage_invalid_linenum) Init(1) Warning
 Warn in case a function ends earlier than it begins due to an invalid linenum macros.
 
+Wcoverage-too-many-conditions
+Common Var(warn_too_many_conditions) Init(1) Warning
+Warn when a conditional has too many terms and condition coverage profiling
+gives up instrumenting the expression.
+
 Wmissing-profile
 Common Var(warn_missing_profile) Init(1) Warning
 Warn in case profiles in -fprofile-use do not exist.
@@ -2458,6 +2463,10 @@ fprofile-arcs
 Common Var(profile_arc_flag)
 Insert arc-based program profiling code.
 
+fcondition-coverage
+Common Var(condition_coverage_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 3019efc4674..6bd75959e94 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,14 @@ be shown, unless the @option{-u} option is given.
 Write branch frequencies as the number of branches taken, rather than
 the percentage of branches taken.
 
+@item -g
+@itemx --conditions
+Write condition coverage to the output file, and write condition summary info
+to the standard output.  This option allows you to see if the conditions in
+your program at least once had an independent effect on the outcome of the
+boolean expression (modified condition/decision coverage).  This requires you
+to compile the source with @option{-fcondition-coverage}.
+
 @item -d
 @itemx --display-progress
 Display the progress on the standard output.
@@ -301,6 +310,7 @@ Each @var{line} has the following form:
   "branches": ["$branch"],
   "calls": ["$call"],
   "count": 2,
+  "conditions": ["$condition"],
   "line_number": 15,
   "unexecuted_block": false,
   "function_name": "foo",
@@ -384,6 +394,34 @@ to @var{line::count})
 @var{destination_block_id}: ID of the basic block this calls continues after return
 @end itemize
 
+Each @var{condition} has the following form:
+
+@smallexample
+@{
+  "count": 4,
+  "covered": 2,
+  "not_covered_false": [],
+  "not_covered_true": [0, 1],
+@}
+
+@end smallexample
+
+Fields of the @var{condition} element have following semantics:
+
+@itemize @bullet
+@item
+@var{count}: number of condition outcomes in this expression
+
+@item
+@var{covered}: number of covered condition outcomes in this expression
+
+@item
+@var{not_covered_true}: terms, by index, not seen as true in this expression
+
+@item
+@var{not_covered_false}: terms, by index, not seen as false in this expression
+@end itemize
+
 @item -H
 @itemx --human-readable
 Write counts in human readable format (like 24.6k).
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index f93128dbe2b..7bfd2478555 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -635,6 +635,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
+-fcondition-coverage
 -fprofile-abs-path
 -fprofile-dir=@var{path}  -fprofile-generate  -fprofile-generate=@var{path}
 -fprofile-info-section  -fprofile-info-section=@var{name}
@@ -6547,6 +6548,14 @@ poorly optimized code and is useful only in the
 case of very minor changes such as bug fixes to an existing code-base.
 Completely disabling the warning is not recommended.
 
+@opindex Wno-coverage-too-many-conditions
+@opindex Wcoverage-too-many-conditions
+@item -Wno-coverage-too-many-conditions
+Warn if @option{-fcondition-coverage} is used and an expression have too many
+terms and GCC gives up coverage.  Coverage is given up when there are more
+terms in the conditional than there are bits in a @code{gcov_type_unsigned}.
+This warning is enabled by default.
+
 @opindex Wno-coverage-invalid-line-number
 @opindex Wcoverage-invalid-line-number
 @item -Wno-coverage-invalid-line-number
@@ -16867,6 +16876,14 @@ Note that if a command line directly links source files, the corresponding
 E.g. @code{gcc a.c b.c -o binary} would generate @file{binary-a.gcda} and
 @file{binary-b.gcda} files.
 
+@item -fcondition-coverage
+@opindex fcondition-coverage
+Add code so that program conditions are instrumented.  During execution the
+program records what terms in a conditional contributes to a decision, which
+can be used to verify that all terms in a Boolean function are tested and have
+an independent effect on the outcome of a decision.  The result can be read
+with @code{gcov --conditions}.
+
 @xref{Cross-profiling}.
 
 @cindex @command{gcov}
@@ -16929,6 +16946,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{-fcondition-coverage}, for each conditional in your program GCC
+creates a bitset and records the exercised boolean values that have an
+independent effect on the outcome of that expression.
+
 @need 2000
 @opindex ftest-coverage
 @item -ftest-coverage
diff --git a/gcc/function.cc b/gcc/function.cc
index 89841787ff8..e57d0488c7a 100644
--- a/gcc/function.cc
+++ b/gcc/function.cc
@@ -4793,6 +4793,7 @@ allocate_struct_function (tree fndecl, bool abstract_p)
 
   cfun = ggc_cleared_alloc<function> ();
 
+  cfun->cond_uids = hash_map <gcond*, unsigned>::create_ggc ();
   init_eh_for_function ();
 
   if (init_machine_status)
diff --git a/gcc/function.h b/gcc/function.h
index 833c35e3da6..a3a23108ee9 100644
--- a/gcc/function.h
+++ b/gcc/function.h
@@ -270,6 +270,10 @@ struct GTY(()) function {
   /* Value histograms attached to particular statements.  */
   htab_t GTY((skip)) value_histograms;
 
+  /* Annotated gconds so that basic conditions in the same expression have the
+     same uid.  This is used for condition coverage.  */
+  hash_map <gcond*, unsigned> *GTY(()) cond_uids;
+
   /* For function.cc.  */
 
   /* Points to the FUNCTION_DECL of this function.  */
diff --git a/gcc/gcc.cc b/gcc/gcc.cc
index 9f21ad9453e..8578abc84f7 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)}\
     " STACK_SPLIT_SPEC "\
-    %{fprofile-arcs|fprofile-generate*|coverage:-lgcov} " SANITIZER_SPEC " \
+    %{fprofile-arcs|fcondition-coverage|fprofile-generate*|coverage:-lgcov} " SANITIZER_SPEC " \
     %{!nostdlib:%{!r:%{!nodefaultlibs:%(link_ssp) %(link_gcc_c_sequence)}}}\
     %{!nostdlib:%{!r:%{!nostartfiles:%E}}} %{T*}  \n%(post_link) }}}}}}"
 #endif
@@ -1288,7 +1288,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|fcondition-coverage|fprofile-generate*|coverage:\
    %{!fprofile-update=single:\
      %{pthread:-fprofile-update=prefer-atomic}}}";
 
diff --git a/gcc/gcov-counter.def b/gcc/gcov-counter.def
index 727ef424181..4d5b9c65a70 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 20e464022dc..d843223986c 100644
--- a/gcc/gcov-dump.cc
+++ b/gcc/gcov-dump.cc
@@ -38,6 +38,7 @@ static void print_version (void);
 static void tag_function (const char *, unsigned, int, unsigned);
 static void tag_blocks (const char *, unsigned, int, unsigned);
 static void tag_arcs (const char *, unsigned, int, unsigned);
+static void tag_conditions (const char *, unsigned, int, unsigned);
 static void tag_lines (const char *, unsigned, int, unsigned);
 static void tag_counters (const char *, unsigned, int, unsigned);
 static void tag_summary (const char *, unsigned, int, unsigned);
@@ -77,6 +78,7 @@ static const tag_format_t tag_table[] =
   {GCOV_TAG_FUNCTION, "FUNCTION", tag_function},
   {GCOV_TAG_BLOCKS, "BLOCKS", tag_blocks},
   {GCOV_TAG_ARCS, "ARCS", tag_arcs},
+  {GCOV_TAG_CONDS, "CONDITIONS", tag_conditions},
   {GCOV_TAG_LINES, "LINES", tag_lines},
   {GCOV_TAG_OBJECT_SUMMARY, "OBJECT_SUMMARY", tag_summary},
   {0, NULL, NULL}
@@ -392,6 +394,28 @@ tag_arcs (const char *filename ATTRIBUTE_UNUSED,
     }
 }
 
+/* Print number of conditions (not outcomes, i.e. if (x && y) is 2, not 4).  */
+static void
+tag_conditions (const char *filename, unsigned /* tag */, int length,
+		unsigned depth)
+{
+  unsigned n_conditions = GCOV_TAG_CONDS_NUM (length);
+
+  printf (" %u conditions", n_conditions);
+  if (flag_dump_contents)
+    {
+      for (unsigned ix = 0; ix != n_conditions; ix++)
+	{
+	  const unsigned blockno = gcov_read_unsigned ();
+	  const unsigned nterms = gcov_read_unsigned ();
+
+	  printf ("\n");
+	  print_prefix (filename, depth, gcov_position ());
+	  printf (VALUE_PADDING_PREFIX "block %u:", blockno);
+	  printf (" %u", nterms);
+	}
+    }
+}
 static void
 tag_lines (const char *filename ATTRIBUTE_UNUSED,
 	   unsigned tag ATTRIBUTE_UNUSED, int length ATTRIBUTE_UNUSED,
diff --git a/gcc/gcov-io.h b/gcc/gcov-io.h
index e6f33e32652..eda4611ac42 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 8b4748d3a1a..22aa58b6cd9 100644
--- a/gcc/gcov.cc
+++ b/gcc/gcov.cc
@@ -46,6 +46,7 @@ along with Gcov; see the file COPYING3.  If not see
 #include "color-macros.h"
 #include "pretty-print.h"
 #include "json.h"
+#include "hwint.h"
 
 #include <zlib.h>
 #include <getopt.h>
@@ -81,6 +82,7 @@ using namespace std;
 class function_info;
 class block_info;
 class source_info;
+class condition_info;
 
 /* Describes an arc between two basic blocks.  */
 
@@ -134,6 +136,33 @@ public:
   vector<unsigned> lines;
 };
 
+/* Describes a single conditional expression and the (recorded) conditions
+   shown to independently affect the outcome.  */
+class condition_info
+{
+public:
+  condition_info ();
+
+  int popcount () const;
+
+  /* Bitsets storing the independently significant outcomes for true and false,
+   * respectively.  */
+  gcov_type_unsigned truev;
+  gcov_type_unsigned falsev;
+
+  /* Number of terms in the expression; if (x) -> 1, if (x && y) -> 2 etc.  */
+  unsigned n_terms;
+};
+
+condition_info::condition_info (): truev (0), falsev (0), n_terms (0)
+{
+}
+
+int condition_info::popcount () const
+{
+    return popcount_hwi (truev) + popcount_hwi (falsev);
+}
+
 /* Describes a basic block. Contains lists of arcs to successor and
    predecessor blocks.  */
 
@@ -167,6 +196,8 @@ public:
   /* Block is a landing pad for longjmp or throw.  */
   unsigned is_nonlocal_return : 1;
 
+  condition_info conditions;
+
   vector<block_location_info> locations;
 
   struct
@@ -277,6 +308,8 @@ public:
   vector<block_info> blocks;
   unsigned blocks_executed;
 
+  vector<condition_info*> conditions;
+
   /* Raw arc coverage counts.  */
   vector<gcov_type> counts;
 
@@ -353,6 +386,9 @@ struct coverage_info
   int branches_executed;
   int branches_taken;
 
+  int conditions;
+  int conditions_covered;
+
   int calls;
   int calls_executed;
 
@@ -552,6 +588,10 @@ static int multiple_files = 0;
 
 static int flag_branches = 0;
 
+/* Output conditions (modified condition/decision coverage).  */
+
+static bool flag_conditions = 0;
+
 /* Show unconditional branches too.  */
 static int flag_unconditional = 0;
 
@@ -658,6 +698,7 @@ static int read_count_file (void);
 static void solve_flow_graph (function_info *);
 static void find_exception_blocks (function_info *);
 static void add_branch_counts (coverage_info *, const arc_info *);
+static void add_condition_counts (coverage_info *, const block_info *);
 static void add_line_counts (coverage_info *, function_info *);
 static void executed_summary (unsigned, unsigned);
 static void function_summary (const coverage_info *);
@@ -666,6 +707,7 @@ static const char *format_gcov (gcov_type, gcov_type, int);
 static void accumulate_line_counts (source_info *);
 static void output_gcov_file (const char *, source_info *);
 static int output_branch_count (FILE *, int, const arc_info *);
+static void output_conditions (FILE *, const block_info *);
 static void output_lines (FILE *, const source_info *);
 static string make_gcov_file_name (const char *, const char *);
 static char *mangle_name (const char *);
@@ -930,6 +972,8 @@ print_usage (int error_p)
   fnotice (file, "  -b, --branch-probabilities      Include branch probabilities in output\n");
   fnotice (file, "  -c, --branch-counts             Output counts of branches taken\n\
                                     rather than percentages\n");
+  fnotice (file, "  -g, --conditions                Include modified condition/decision\n\
+                                    coverage in output\n");
   fnotice (file, "  -d, --display-progress          Display progress information\n");
   fnotice (file, "  -D, --debug			    Display debugging dumps\n");
   fnotice (file, "  -f, --function-summaries        Output summaries for each function\n");
@@ -983,6 +1027,7 @@ static const struct option options[] =
   { "all-blocks",           no_argument,       NULL, 'a' },
   { "branch-probabilities", no_argument,       NULL, 'b' },
   { "branch-counts",        no_argument,       NULL, 'c' },
+  { "conditions",	    no_argument,       NULL, 'g' },
   { "json-format",	    no_argument,       NULL, 'j' },
   { "human-readable",	    no_argument,       NULL, 'H' },
   { "no-output",            no_argument,       NULL, 'n' },
@@ -1011,7 +1056,7 @@ process_args (int argc, char **argv)
 {
   int opt;
 
-  const char *opts = "abcdDfhHijklmno:pqrs:tuvwx";
+  const char *opts = "abcdDfghHijklmno:pqrs:tuvwx";
   while ((opt = getopt_long (argc, argv, opts, options, NULL)) != -1)
     {
       switch (opt)
@@ -1028,6 +1073,9 @@ process_args (int argc, char **argv)
 	case 'f':
 	  flag_function_summary = 1;
 	  break;
+	case 'g':
+	  flag_conditions = 1;
+	  break;
 	case 'h':
 	  print_usage (false);
 	  /* print_usage will exit.  */
@@ -1152,6 +1200,45 @@ output_intermediate_json_line (json::array *object,
 	  }
       }
 
+  json::array *conditions = new json::array ();
+  lineo->set ("conditions", conditions);
+  if (flag_conditions)
+  {
+    vector<block_info *>::const_iterator it;
+    for (it = line->blocks.begin (); it != line->blocks.end (); it++)
+      {
+	const condition_info& info = (*it)->conditions;
+	if (info.n_terms == 0)
+	    continue;
+
+	const int count = 2 * info.n_terms;
+	const int covered = info.popcount ();
+
+	json::object *cond = new json::object ();
+	cond->set ("count", new json::integer_number (count));
+	cond->set ("covered", new json::integer_number (covered));
+
+	json::array *mtrue = new json::array ();
+	json::array *mfalse = new json::array ();
+	cond->set ("not_covered_true", mtrue);
+	cond->set ("not_covered_false", mfalse);
+
+	if (count != covered)
+	  {
+	    for (unsigned i = 0; i < info.n_terms; i++)
+	      {
+		gcov_type_unsigned index = 1;
+		index <<= i;
+		if (!(index & info.truev))
+		    mtrue->append (new json::integer_number (i));
+		if (!(index & info.falsev))
+		    mfalse->append (new json::integer_number (i));
+	      }
+	  }
+	conditions->append (cond);
+      }
+  }
+
   object->append (lineo);
 }
 
@@ -1969,6 +2056,28 @@ read_graph_file (void)
 		  }
 	    }
 	}
+      else if (fn && tag == GCOV_TAG_CONDS)
+	{
+	  unsigned num_dests = GCOV_TAG_CONDS_NUM (length);
+
+	  if (!fn->conditions.empty ())
+	    fnotice (stderr, "%s:already seen conditions for '%s'\n",
+		     bbg_file_name, fn->get_name ());
+	  else
+	    fn->conditions.resize (num_dests);
+
+	  for (unsigned i = 0; i < num_dests; ++i)
+	    {
+	      unsigned idx = gcov_read_unsigned ();
+
+	      if (idx >= fn->blocks.size ())
+		goto corrupt;
+
+	      condition_info *info = &fn->blocks[idx].conditions;
+	      info->n_terms = gcov_read_unsigned ();
+	      fn->conditions[i] = info;
+	    }
+	}
       else if (fn && tag == GCOV_TAG_LINES)
 	{
 	  unsigned blockno = gcov_read_unsigned ();
@@ -2099,6 +2208,21 @@ read_count_file (void)
 	      goto cleanup;
 	    }
 	}
+      else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_CONDS) && fn)
+	{
+	  length = abs (read_length);
+	  if (length != GCOV_TAG_COUNTER_LENGTH (2 * fn->conditions.size ()))
+	      goto mismatch;
+
+	  if (read_length > 0)
+	    {
+	      for (ix = 0; ix != fn->conditions.size (); ix++)
+		{
+		  fn->conditions[ix]->truev  |= gcov_read_counter ();
+		  fn->conditions[ix]->falsev |= gcov_read_counter ();
+		}
+	    }
+	}
       else if (tag == GCOV_TAG_FOR_COUNTER (GCOV_COUNTER_ARCS) && fn)
 	{
 	  length = abs (read_length);
@@ -2443,6 +2567,15 @@ add_branch_counts (coverage_info *coverage, const arc_info *arc)
     }
 }
 
+/* Increment totals in COVERAGE according to to block BLOCK.  */
+
+static void
+add_condition_counts (coverage_info *coverage, const block_info *block)
+{
+  coverage->conditions += 2 * block->conditions.n_terms;
+  coverage->conditions_covered += block->conditions.popcount ();
+}
+
 /* Format COUNT, if flag_human_readable_numbers is set, return it human
    readable format.  */
 
@@ -2546,6 +2679,18 @@ file_summary (const coverage_info *coverage)
 		 coverage->calls);
       else
 	fnotice (stdout, "No calls\n");
+
+    }
+
+  if (flag_conditions)
+    {
+      if (coverage->conditions)
+	fnotice (stdout, "Condition outcomes covered:%s of %d\n",
+		 format_gcov (coverage->conditions_covered,
+			      coverage->conditions, 2),
+		 coverage->conditions);
+      else
+	fnotice (stdout, "No conditions\n");
     }
 }
 
@@ -2780,6 +2925,12 @@ static void accumulate_line_info (line_info *line, source_info *src,
 	 it != line->branches.end (); it++)
       add_branch_counts (&src->coverage, *it);
 
+  if (add_coverage)
+    for (vector<block_info *>::iterator it = line->blocks.begin ();
+	 it != line->blocks.end (); it++)
+      add_condition_counts (&src->coverage, *it);
+
+
   if (!line->blocks.empty ())
     {
       /* The user expects the line count to be the number of times
@@ -2881,6 +3032,37 @@ accumulate_line_counts (source_info *src)
       }
 }
 
+/* Output information about the conditions in block BINFO.  The output includes
+ * a summary (n/m outcomes covered) and a list of the missing (uncovered)
+ * outcomes.  */
+
+static void
+output_conditions (FILE *gcov_file, const block_info *binfo)
+{
+    const condition_info& info = binfo->conditions;
+    if (info.n_terms == 0)
+	return;
+
+    const int expected = 2 * info.n_terms;
+    const int got = info.popcount ();
+
+    fnotice (gcov_file, "condition outcomes covered %d/%d\n", got, expected);
+    if (expected == got)
+	return;
+
+    for (unsigned i = 0; i < info.n_terms; i++)
+    {
+	gcov_type_unsigned index = 1;
+	index <<= i;
+	if ((index & info.truev & info.falsev))
+	    continue;
+
+	const char *t = (index & info.truev) ? "" : "true";
+	const char *f = (index & info.falsev) ? "" : " false";
+	fnotice (gcov_file, "condition %2u not covered (%s%s)\n", i, t, f + !t[0]);
+    }
+}
+
 /* Output information about ARC number IX.  Returns nonzero if
    anything is output.  */
 
@@ -3091,16 +3273,29 @@ output_line_details (FILE *f, const line_info *line, unsigned line_num)
 	  if (flag_branches)
 	    for (arc = (*it)->succ; arc; arc = arc->succ_next)
 	      jx += output_branch_count (f, jx, arc);
+
+	  if (flag_conditions)
+	      output_conditions (f, *it);
 	}
     }
-  else if (flag_branches)
+  else
     {
-      int ix;
+      if (flag_branches)
+	{
+	  int ix;
+
+	  ix = 0;
+	  for (vector<arc_info *>::const_iterator it = line->branches.begin ();
+		  it != line->branches.end (); it++)
+	      ix += output_branch_count (f, ix, (*it));
+	}
 
-      ix = 0;
-      for (vector<arc_info *>::const_iterator it = line->branches.begin ();
-	   it != line->branches.end (); it++)
-	ix += output_branch_count (f, ix, (*it));
+      if (flag_conditions)
+	{
+	  for (vector<block_info *>::const_iterator it = line->blocks.begin ();
+	       it != line->blocks.end (); it++)
+	      output_conditions (f, *it);
+	}
     }
 }
 
diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
index 342e43a7f25..591cb50193c 100644
--- a/gcc/gimplify.cc
+++ b/gcc/gimplify.cc
@@ -71,6 +71,24 @@ along with GCC; see the file COPYING3.  If not see
 #include "context.h"
 #include "tree-nested.h"
 
+static unsigned nextuid = 1;
+/* Get a fresh identifier for a new condition expression.  This is used for
+   condition coverage.  */
+static unsigned
+next_cond_uid ()
+{
+    return nextuid++;
+}
+/* Reset the condition uid to the value it should have when compiling a new
+   function.  0 is already the default/untouched value, so start at non-zero.
+   A valid and set id should always be > 0.  This is used for condition
+   coverage.  */
+static void
+reset_cond_uid ()
+{
+    nextuid = 1;
+}
+
 /* Hash set of poisoned variables in a bind expr.  */
 static hash_set<tree> *asan_poisoned_variables = NULL;
 
@@ -4131,13 +4149,16 @@ gimplify_call_expr (tree *expr_p, gimple_seq *pre_p, bool want_value)
 
    LOCUS is the source location of the COND_EXPR.
 
+   The condition_uid is a discriminator tag for condition coverage used to map
+   conditions to its corresponding full Boolean function.
+
    This function is the tree equivalent of do_jump.
 
    shortcut_cond_r should only be called by shortcut_cond_expr.  */
 
 static tree
 shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
-		 location_t locus)
+		 location_t locus, unsigned condition_uid)
 {
   tree local_label = NULL_TREE;
   tree t, expr = NULL;
@@ -4159,13 +4180,14 @@ shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
 	false_label_p = &local_label;
 
       /* Keep the original source location on the first 'if'.  */
-      t = shortcut_cond_r (TREE_OPERAND (pred, 0), NULL, false_label_p, locus);
+      t = shortcut_cond_r (TREE_OPERAND (pred, 0), NULL, false_label_p, locus,
+			   condition_uid);
       append_to_statement_list (t, &expr);
 
       /* Set the source location of the && on the second 'if'.  */
       new_locus = rexpr_location (pred, locus);
       t = shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p, false_label_p,
-			   new_locus);
+			   new_locus, condition_uid);
       append_to_statement_list (t, &expr);
     }
   else if (TREE_CODE (pred) == TRUTH_ORIF_EXPR)
@@ -4182,13 +4204,14 @@ shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
 	true_label_p = &local_label;
 
       /* Keep the original source location on the first 'if'.  */
-      t = shortcut_cond_r (TREE_OPERAND (pred, 0), true_label_p, NULL, locus);
+      t = shortcut_cond_r (TREE_OPERAND (pred, 0), true_label_p, NULL, locus,
+			   condition_uid);
       append_to_statement_list (t, &expr);
 
       /* Set the source location of the || on the second 'if'.  */
       new_locus = rexpr_location (pred, locus);
       t = shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p, false_label_p,
-			   new_locus);
+			   new_locus, condition_uid);
       append_to_statement_list (t, &expr);
     }
   else if (TREE_CODE (pred) == COND_EXPR
@@ -4211,9 +4234,11 @@ shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
       new_locus = rexpr_location (pred, locus);
       expr = build3 (COND_EXPR, void_type_node, TREE_OPERAND (pred, 0),
 		     shortcut_cond_r (TREE_OPERAND (pred, 1), true_label_p,
-				      false_label_p, locus),
+				      false_label_p, locus, condition_uid),
 		     shortcut_cond_r (TREE_OPERAND (pred, 2), true_label_p,
-				      false_label_p, new_locus));
+				      false_label_p, new_locus,
+				      condition_uid));
+      SET_EXPR_UID (expr, condition_uid);
     }
   else
     {
@@ -4221,6 +4246,7 @@ shortcut_cond_r (tree pred, tree *true_label_p, tree *false_label_p,
 		     build_and_jump (true_label_p),
 		     build_and_jump (false_label_p));
       SET_EXPR_LOCATION (expr, locus);
+      SET_EXPR_UID (expr, condition_uid);
     }
 
   if (local_label)
@@ -4271,12 +4297,41 @@ find_goto_label (tree expr)
   return NULL_TREE;
 }
 
+
+/* Given a multi-term condition (ANDIF, ORIF), walk the predicate and tag every
+   term with uid.  When two basic conditions share the uid discriminator when
+   they belong to the same predicate, which used by the condition coverage.
+   Doing this as an explicit step makes for a simpler implementation than
+   weaving it into the splitting code as the splitting code eventually reaches
+   back up to gimplfiy_expr which makes bookkeeping complicated.  */
+static void
+tag_shortcut_cond (tree pred, unsigned condition_uid)
+{
+  if (TREE_CODE (pred) == TRUTH_ANDIF_EXPR
+      || TREE_CODE (pred) == TRUTH_ORIF_EXPR)
+    {
+      tree fst = TREE_OPERAND (pred, 0);
+      tree lst = TREE_OPERAND (pred, 1);
+
+      if (TREE_CODE (fst) == TRUTH_ANDIF_EXPR
+	  || TREE_CODE (fst) == TRUTH_ORIF_EXPR)
+	tag_shortcut_cond (fst, condition_uid);
+      else if (TREE_CODE (fst) == COND_EXPR)
+	SET_EXPR_UID (fst, condition_uid);
+
+      if (TREE_CODE (lst) == TRUTH_ANDIF_EXPR
+	  || TREE_CODE (lst) == TRUTH_ORIF_EXPR)
+	tag_shortcut_cond (lst, condition_uid);
+      else if (TREE_CODE (lst) == COND_EXPR)
+	SET_EXPR_UID (lst, condition_uid);
+    }
+}
 /* Given a conditional expression EXPR with short-circuit boolean
    predicates using TRUTH_ANDIF_EXPR or TRUTH_ORIF_EXPR, break the
    predicate apart into the equivalent sequence of conditionals.  */
 
 static tree
-shortcut_cond_expr (tree expr)
+shortcut_cond_expr (tree expr, unsigned condition_uid)
 {
   tree pred = TREE_OPERAND (expr, 0);
   tree then_ = TREE_OPERAND (expr, 1);
@@ -4288,6 +4343,8 @@ shortcut_cond_expr (tree expr)
   bool then_se = then_ && TREE_SIDE_EFFECTS (then_);
   bool else_se = else_ && TREE_SIDE_EFFECTS (else_);
 
+  tag_shortcut_cond (pred, condition_uid);
+
   /* First do simple transformations.  */
   if (!else_se)
     {
@@ -4303,7 +4360,7 @@ shortcut_cond_expr (tree expr)
 	  /* Set the source location of the && on the second 'if'.  */
 	  if (rexpr_has_location (pred))
 	    SET_EXPR_LOCATION (expr, rexpr_location (pred));
-	  then_ = shortcut_cond_expr (expr);
+	  then_ = shortcut_cond_expr (expr, condition_uid);
 	  then_se = then_ && TREE_SIDE_EFFECTS (then_);
 	  pred = TREE_OPERAND (pred, 0);
 	  expr = build3 (COND_EXPR, void_type_node, pred, then_, NULL_TREE);
@@ -4325,7 +4382,7 @@ shortcut_cond_expr (tree expr)
 	  /* Set the source location of the || on the second 'if'.  */
 	  if (rexpr_has_location (pred))
 	    SET_EXPR_LOCATION (expr, rexpr_location (pred));
-	  else_ = shortcut_cond_expr (expr);
+	  else_ = shortcut_cond_expr (expr, condition_uid);
 	  else_se = else_ && TREE_SIDE_EFFECTS (else_);
 	  pred = TREE_OPERAND (pred, 0);
 	  expr = build3 (COND_EXPR, void_type_node, pred, NULL_TREE, else_);
@@ -4333,6 +4390,9 @@ shortcut_cond_expr (tree expr)
 	}
     }
 
+  /* The expr tree should also have the expression id set.  */
+  SET_EXPR_UID (expr, condition_uid);
+
   /* If we're done, great.  */
   if (TREE_CODE (pred) != TRUTH_ANDIF_EXPR
       && TREE_CODE (pred) != TRUTH_ORIF_EXPR)
@@ -4380,7 +4440,7 @@ shortcut_cond_expr (tree expr)
   /* If there was nothing else in our arms, just forward the label(s).  */
   if (!then_se && !else_se)
     return shortcut_cond_r (pred, true_label_p, false_label_p,
-			    EXPR_LOC_OR_LOC (expr, input_location));
+			    EXPR_LOC_OR_LOC (expr, input_location), condition_uid);
 
   /* If our last subexpression already has a terminal label, reuse it.  */
   if (else_se)
@@ -4412,7 +4472,8 @@ shortcut_cond_expr (tree expr)
   jump_over_else = block_may_fallthru (then_);
 
   pred = shortcut_cond_r (pred, true_label_p, false_label_p,
-			  EXPR_LOC_OR_LOC (expr, input_location));
+			  EXPR_LOC_OR_LOC (expr, input_location),
+			  condition_uid);
 
   expr = NULL;
   append_to_statement_list (pred, &expr);
@@ -4688,7 +4749,7 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
   if (TREE_CODE (TREE_OPERAND (expr, 0)) == TRUTH_ANDIF_EXPR
       || TREE_CODE (TREE_OPERAND (expr, 0)) == TRUTH_ORIF_EXPR)
     {
-      expr = shortcut_cond_expr (expr);
+      expr = shortcut_cond_expr (expr, next_cond_uid ());
 
       if (expr != *expr_p)
 	{
@@ -4752,11 +4813,16 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
   else
     label_false = create_artificial_label (UNKNOWN_LOCATION);
 
+  unsigned cond_uid = EXPR_COND_UID (expr);
+  if (cond_uid == 0)
+    cond_uid = next_cond_uid ();
+
   gimple_cond_get_ops_from_tree (COND_EXPR_COND (expr), &pred_code, &arm1,
 				 &arm2);
   cond_stmt = gimple_build_cond (pred_code, arm1, arm2, label_true,
 				 label_false);
   gimple_set_location (cond_stmt, EXPR_LOCATION (expr));
+  cfun->cond_uids->put (cond_stmt, cond_uid);
   copy_warning (cond_stmt, COND_EXPR_COND (expr));
   gimplify_seq_add_stmt (&seq, cond_stmt);
   gimple_stmt_iterator gsi = gsi_last (seq);
@@ -18176,6 +18242,8 @@ gimplify_function_tree (tree fndecl)
   else
     push_struct_function (fndecl);
 
+  reset_cond_uid ();
+
   /* Tentatively set PROP_gimple_lva here, and reset it in gimplify_va_arg_expr
      if necessary.  */
   cfun->curr_properties |= PROP_gimple_lva;
diff --git a/gcc/ipa-inline.cc b/gcc/ipa-inline.cc
index dc120e6da5a..9502a21c741 100644
--- a/gcc/ipa-inline.cc
+++ b/gcc/ipa-inline.cc
@@ -682,7 +682,7 @@ can_early_inline_edge_p (struct cgraph_edge *e)
     }
   gcc_assert (gimple_in_ssa_p (DECL_STRUCT_FUNCTION (e->caller->decl))
 	      && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (callee->decl)));
-  if (profile_arc_flag
+  if ((profile_arc_flag || condition_coverage_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 6730f4f9d0e..ca3bd5e3529 100644
--- a/gcc/ipa-split.cc
+++ b/gcc/ipa-split.cc
@@ -1930,7 +1930,7 @@ pass_split_functions::gate (function *)
   /* When doing profile feedback, we want to execute the pass after profiling
      is read.  So disable one in early optimization.  */
   return (flag_partial_inlining
-	  && !profile_arc_flag && !flag_branch_probabilities);
+      && !profile_arc_flag && !flag_branch_probabilities);
 }
 
 } // anon namespace
diff --git a/gcc/passes.cc b/gcc/passes.cc
index 087aed52934..110a6b0b174 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 || condition_coverage_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 fc59326a19b..bff3b96d871 100644
--- a/gcc/profile.cc
+++ b/gcc/profile.cc
@@ -69,6 +69,17 @@ along with GCC; see the file COPYING3.  If not see
 
 #include "profile.h"
 
+struct condcov;
+struct condcov *find_conditions (struct function*);
+size_t cov_length (const struct condcov*);
+array_slice<basic_block> cov_blocks (struct condcov*, size_t);
+array_slice<uint64_t> cov_masks (struct condcov*, size_t);
+array_slice<sbitmap> cov_maps (struct condcov* cov, size_t n);
+void cov_free (struct condcov*);
+size_t instrument_decisions (array_slice<basic_block>, size_t,
+			     array_slice<sbitmap>,
+			     array_slice<gcov_type_unsigned>);
+
 /* Map from BBs/edges to gcov counters.  */
 vec<gcov_type> bb_gcov_counts;
 hash_map<edge,gcov_type> *edge_gcov_counts;
@@ -100,6 +111,7 @@ static int total_num_passes;
 static int total_num_times_called;
 static int total_hist_br_prob[20];
 static int total_num_branches;
+static int total_num_conds;
 
 /* Forward declarations.  */
 static void find_spanning_tree (struct edge_list *);
@@ -1155,6 +1167,12 @@ read_thunk_profile (struct cgraph_node *node)
    the flow graph that are needed to reconstruct the dynamic behavior of the
    flow graph.  This data is written to the gcno file for gcov.
 
+   When FLAG_PROFILE_CONDITIONS is nonzero, this functions instruments the
+   edges in the control flow graph to track what conditions are evaluated to in
+   order to determine what conditions are covered and have an independent
+   effect on the outcome (modified condition/decision coverage).  This data is
+   written to the gcno file for gcov.
+
    When FLAG_BRANCH_PROBABILITIES is nonzero, this function reads auxiliary
    information from the gcda file containing edge count information from
    previous executions of the function being compiled.  In this case, the
@@ -1173,6 +1191,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++;
 
@@ -1397,10 +1416,18 @@ branch_prob (bool thunk)
 
   /* Write the data from which gcov can reconstruct the basic block
      graph and function line numbers (the gcno file).  */
+  output_to_file = false;
   if (coverage_begin_function (lineno_checksum, cfg_checksum))
     {
       gcov_position_t offset;
 
+      /* The condition coverage needs a deeper analysis to identify expressions
+	 of conditions, which means it is not yet ready to write to the gcno
+	 file.  It will write its entries later, but needs to know if it do it
+	 in the first place, which is controlled by the return value of
+	 coverage_begin_function.  */
+      output_to_file = true;
+
       /* Basic block flags */
       offset = gcov_write_tag (GCOV_TAG_BLOCKS);
       gcov_write_unsigned (n_basic_blocks_for_fn (cfun));
@@ -1514,29 +1541,65 @@ branch_prob (bool thunk)
 
   remove_fake_edges ();
 
+  if (condition_coverage_flag || profile_arc_flag)
+      gimple_init_gcov_profiler ();
+
+  if (condition_coverage_flag)
+    {
+      struct condcov *cov = find_conditions (cfun);
+      gcc_assert (cov);
+      const size_t nconds = cov_length (cov);
+      total_num_conds += nconds;
+
+      if (coverage_counter_alloc (GCOV_COUNTER_CONDS, 2 * nconds))
+	{
+	  gcov_position_t offset {};
+	  if (output_to_file)
+	      offset = gcov_write_tag (GCOV_TAG_CONDS);
+
+	  for (size_t i = 0; i != nconds; ++i)
+	    {
+	      array_slice<basic_block> expr = cov_blocks (cov, i);
+	      array_slice<uint64_t> masks = cov_masks (cov, i);
+	      array_slice<sbitmap> maps = cov_maps (cov, i);
+	      gcc_assert (expr.is_valid ());
+	      gcc_assert (masks.is_valid ());
+	      gcc_assert (maps.is_valid ());
+
+	      size_t terms = instrument_decisions (expr, i, maps, masks);
+	      if (output_to_file)
+		{
+		  gcov_write_unsigned (expr.front ()->index);
+		  gcov_write_unsigned (terms);
+		}
+	    }
+	  if (output_to_file)
+	      gcov_write_length (offset);
+	}
+      cov_free (cov);
+    }
+
   /* For each edge not on the spanning tree, add counting code.  */
   if (profile_arc_flag
       && coverage_counter_alloc (GCOV_COUNTER_ARCS, num_instrumented))
     {
       unsigned n_instrumented;
 
-      gimple_init_gcov_profiler ();
-
       n_instrumented = instrument_edges (el);
 
       gcc_assert (n_instrumented == num_instrumented);
 
       if (flag_profile_values)
 	instrument_values (values);
-
-      /* Commit changes done by instrumentation.  */
-      gsi_commit_edge_inserts ();
     }
 
   free_aux_for_edges ();
 
   values.release ();
   free_edge_list (el);
+  /* Commit changes done by instrumentation.  */
+  gsi_commit_edge_inserts ();
+
   coverage_end_function (lineno_checksum, cfg_checksum);
   if (flag_branch_probabilities
       && (profile_status_for_fn (cfun) == PROFILE_READ))
@@ -1669,6 +1732,7 @@ init_branch_prob (void)
   total_num_passes = 0;
   total_num_times_called = 0;
   total_num_branches = 0;
+  total_num_conds = 0;
   for (i = 0; i < 20; i++)
     total_hist_br_prob[i] = 0;
 }
@@ -1708,5 +1772,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/testsuite/g++.dg/gcov/gcov-18.C b/gcc/testsuite/g++.dg/gcov/gcov-18.C
new file mode 100644
index 00000000000..7c643c51a57
--- /dev/null
+++ b/gcc/testsuite/g++.dg/gcov/gcov-18.C
@@ -0,0 +1,258 @@
+/* { dg-options "--coverage -fcondition-coverage -std=c++11" } */
+/* { dg-do run { target native } } */
+
+#include <vector>
+#include <stdexcept>
+
+class nontrivial_destructor
+{
+public:
+    explicit nontrivial_destructor (int v) : val (v) {}
+    ~nontrivial_destructor () {}
+
+    explicit operator bool() const { return bool(val); }
+
+    int val;
+};
+
+int identity (int x) { return x; }
+int throws (int) { throw std::runtime_error("exception"); }
+
+int
+throw_if (int x)
+{
+    if (x) /* conditions(1/2) true(0) */
+	   /* conditions(end) */
+	throw std::runtime_error("exception");
+    return x;
+}
+
+/* Used for side effects to insert nodes in conditional bodies etc.  */
+int x = 0;
+
+/* Conditionals work in the presence of non-trivial destructors.  */
+void
+mcdc001a (int a)
+{
+    nontrivial_destructor v (a);
+
+    if (v.val > 0) /* conditions(2/2) */
+	x = v.val;
+    else
+	x = -v.val;
+}
+
+/* Non-trivial destructor in-loop temporary.  */
+nontrivial_destructor
+mcdc002a (int a, int b)
+{
+    for (int i = 0; i < a; i++) /* conditions(2/2) */
+    {
+	nontrivial_destructor tmp (a);
+	if (tmp.val % b) /* conditions(2/2) */
+	    return nontrivial_destructor (0);
+	x += i;
+    } /* conditions(suppress) */
+      /* conditions(end) */
+
+    return nontrivial_destructor (a * b);
+}
+
+/* Conditional in constructor.  */
+void
+mcdc003a (int a)
+{
+    class C
+    {
+    public:
+	explicit C (int e) : v (e)
+	{
+	    if (e) /* conditions(1/2) false(0) */
+		v = x - e;
+	}
+	int v;
+    };
+
+    C c (a);
+    if (c.v > 2) /* conditions(1/2) true(0) */
+		 /* conditions(end) */
+	x = c.v + a;
+}
+
+/* Conditional in destructor.  */
+void
+mcdc004a (int a)
+{
+    class C
+    {
+    public:
+	explicit C (int e) : v (e) {}
+	~C ()
+	{
+	    if (v) /* conditions(2/2) */
+		x = 2 * v;
+	}
+	int v;
+    };
+
+    C c (a);
+    x = 1; // arbitrary action between ctor+dtor
+}
+
+/* Conditional in try. */
+void
+mcdc005a (int a)
+{
+    try
+    {
+	if (a) /* conditions(1/2) true(0) */
+	       /* conditions(end) */
+	    x = 2 * identity (a);
+	else
+	    x = 1;
+    }
+    catch (...)
+    {
+	x = 0;
+    }
+}
+
+/* Conditional in catch.  */
+void
+mcdc006a (int a) {
+    try
+    {
+	throws (a);
+    }
+    catch (std::exception&)
+    {
+	if (a) /* conditions(1/2) false(0) */
+	       /* conditions(end) */
+	    x = identity (a);
+	else
+	    x = 0;
+    }
+}
+
+void
+mcdc006b (int a)
+{
+    if (a) /* conditions(1/2) true(0) */
+	   /* conditions(end) */
+	throws (a);
+    else
+	x = 1;
+}
+
+void
+mcdc006c (int a) try
+{
+    throws (a);
+}
+catch (...) {
+    if (a) /* conditions(2/2) */
+	x = 5;
+}
+
+/* Temporary with destructor as term.  */
+void
+mcdc007a (int a, int b)
+{
+    x = a && nontrivial_destructor (b); /* conditions(3/4) false(1) destructor() */
+}
+
+void
+mcdc007b (int a, int b)
+{
+    if (a || throw_if (b)) /* conditions(3/4) true(1) destructor() */
+	x = -1;
+    else
+	x = 1;
+}
+
+void
+mcdc007c (int a, int b)
+{
+    if (throw_if (a) || throw_if (b)) /* conditions(2/4) true(0 1) destructor() */
+	x = -1;
+    else
+	x = 1;
+}
+
+/* Destructor with delete.  */
+void
+mcdc008a (int a)
+{
+    class C
+    {
+    public:
+        int size = 5;
+        int* ptr = nullptr;
+
+        explicit C (int v) : size (v + 5), ptr (new int[size]) /* conditions(suppress) */
+							       /* conditions(end) */
+        {
+	    for (int i = 0; i < size; i++) /* conditions(2/2) */
+		ptr[i] = i + 1;
+        }
+        ~C()
+        {
+	    // delete with implicit nullptr check
+	    delete ptr; /* conditions(1/2) false(0) */
+			/* conditions(end) */
+	}
+    };
+
+    C c (a);
+    if (c.ptr[a + 1]) /* conditions(1/2) false(0) */
+	x = a;
+}
+
+/* Templates.  */
+template <typename T>
+void
+mcdc009a (T a)
+{
+    if (a > 0) /* conditions(1/2) false(0) */
+	       /* conditions(end) */
+	x += 2;
+}
+
+
+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);
+
+    mcdc009a (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..17f1fb4e923
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-19.c
@@ -0,0 +1,1737 @@
+/* { dg-options "-fcondition-coverage -ftest-coverage" } */
+/* { dg-do run { target native } } */
+
+/* Some side effect to stop branches from being pruned.  */
+int x = 0;
+
+int id  (int x) { return  x; }
+int inv (int x) { return !x; }
+
+/* || works.  */
+void
+mcdc001a (int a, int b)
+{
+    if (a || b) /* conditions(1/4) true(0) false(0 1) */
+		/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc001b (int a, int b)
+{
+    if (a || b) /* conditions(3/4) true(0) */
+		/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc001c (int a, int b)
+{
+    if (a || b) /* conditions(4/4) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc001d (int a, int b, int c)
+{
+    if (a || b || c) /* conditions(2/6) false(0 1 2) true(2) */
+		     /* conditions(end) */
+	x = 1;
+}
+
+/* && works */
+void
+mcdc002a (int a, int b)
+{
+    if (a && b) /* conditions(1/4) true(0 1) false(0) */
+		/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc002b (int a, int b)
+{
+    if (a && b) /* conditions(3/4) false(0) */
+		/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc002c (int a, int b)
+{
+    if (a && b) /* conditions(4/4) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc002d (int a, int b, int c)
+{
+    if (a && b && c) /* conditions(4/6) false(0 2) */
+		     /* conditions(end) */
+	x = 1;
+}
+
+/* Negation works.  */
+void
+mcdc003a (int a, int b)
+{
+    if (!a || !b) /* conditions(2/4) false(0 1) */
+		  /* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+/* Single conditionals with and without else.  */
+void
+mcdc004a (int a)
+{
+    if (a) /* conditions(1/2) true(0) */
+	   /* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc004b (int a)
+{
+    if (a) /* conditions(2/2) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc004c (int a)
+{
+    if (a) /* conditions(1/2) false(0) */
+	   /* conditions(end) */
+	x = 1;
+}
+
+void
+mcdc004d (int a, int b, int c)
+{
+    if (a)  /* conditions(2/2) */
+    {
+	if (b || c) /* conditions(1/4) true(1) false(0 1) */
+	    x = a + b + c;
+    }
+}
+
+void
+mcdc004e (int a, int b, int c)
+{
+    if (a)  /* conditions(2/2) */
+    {
+	if (b || c) /* conditions(1/4) true(1) false(0 1) */
+		    /* conditions(end) */
+	    x = a + b + c;
+    }
+    else
+    {
+	x = c;
+    }
+}
+
+void
+mcdc004f (int a, int b, int c)
+{
+    if (a)  /* conditions(1/2) false(0) */
+	    /* conditions(end) */
+    {
+	x = 1;
+    }
+    else if (b) /* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+    {
+	x = 2;
+	if (c)  /* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    x = 3;
+    }
+}
+
+/* mixing && and || works */
+void
+mcdc005a (int a, int b, int c)
+{
+    if ((a && b) || c) /* conditions(1/6) true(0 1) false(0 1 2) */
+		       /* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc005b (int a, int b, int c, int d)
+{
+    /* This is where masking MC/DC gets unintuitive:
+
+       1 1 0 0 => covers 1 (d = 0) as && 0 masks everything to the left
+       1 0 0 0 => covers 2 (b = 0, c = 0) as (a && 0) masks a and d is never
+       evaluated. */
+    if ((a && (b || c)) && d) /* conditions(3/8) true(0 1 2 3) false(0) */
+			      /* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc005c (int a, int b, int c, int d)
+{
+    if (a || (b && c) || d) /* conditions(2/8) true(0 3) false(0 1 2 3) */
+			    /* conditions(end) */
+        x = a + b + c + d;
+}
+
+void
+mcdc005d (int a, int b, int c, int d)
+{
+    /* This test is quite significant - it has a single input
+       (1, 0, 0, 0) and tests specifically for when a multi-term left operand
+       is masked. d = 0 should mask a || b and for the input there are no other
+       sources for masking a (since b = 0). */
+    if ((a || b) && (c || d)) /* conditions(2/8) true(0 1 2 3) false(0 1) */
+			      /* conditions(end) */
+	x = a + b;
+    else
+	x = c + d;
+}
+
+/* Mixing in constants kills the decision removes the term outright.  */
+void
+mcdc005e (int a, int b)
+{
+  x += 0 && a;
+  x += a && 1;
+  x += 0 && a && b;
+  x += a && 1 && b; /* conditions(4/4) */
+  x += a && b && 0;
+  x += 0 && 1;
+  x += 1 && a;
+  x += a && 0;
+  x += 1 || a;
+  x += a || 0;
+  x += 1 || a || b;
+  x += a || 0 || b; /* conditions(4/4) */
+  x += a || b || 1;
+  x += 1 || 0;
+  x += 0 || a;
+  x += a || 1;
+}
+
+/* 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(2/2) */
+	if (b) /* conditions(2/2) */
+	    if (c) /* conditions(2/2) */
+		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;
+    }
+}
+
+void
+mcdc006d (int a, int b, int c)
+{
+    if (a)	/* conditions(1/2) false(0) */
+		/* conditions(end) */
+    {
+	if (b)	/* conditions(1/2) true(0) */
+		/* conditions(end) */
+	    x = a + b;
+	if (c)	/* conditions(2/2) */
+		/* conditions(end) */
+	    x = a + b;
+    }
+}
+
+void
+mcdc006e (int a, int b, int c, int d)
+{
+    if ((a || b || c) && id (d)) /* conditions(4/8) true(0 1 2 3) false() */
+				 /* conditions(end) */
+	x = 1;
+}
+
+/* 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:
+    if (a)	/* conditions(2/2) */
+	goto then;
+    else if (b)	/* conditions(2/2) */
+	goto then;
+    else if (c) /* conditions(1/2) true(0) */
+	goto then;
+}
+
+void
+mcdc007c (int a, int b, int c)
+{
+    goto begin;
+then1:
+    x = 1;
+    return;
+then2:
+    x = 1;
+    return;
+then3:
+    x = 1;
+    return;
+begin:
+    if (a) /* conditions(2/2) */
+	goto then1;
+    else if (b) /* conditions(2/2) */
+	goto then2;
+    else if (c) /* conditions(1/2) true(0) */
+		/* conditions(end) */
+	goto then3;
+}
+
+void
+noop () {}
+
+int
+mcdc007d (int a, int b, int c, int d, int e)
+{
+    noop ();
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b || c) /* conditions(0/4) true(0 1) false(0 1) */
+		    /* conditions(end) */
+	    x = 2;
+	if (d)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return 1;
+    }
+    if (e)  /* conditions(1/2) false(0) */
+	    /* conditions(end) */
+	return 0;
+
+    return 2;
+}
+
+/* while loop.  */
+void
+mcdc008a (int a)
+{
+    while (a < 10) /* conditions(2/2) */
+	x = a++;
+}
+
+void
+mcdc008b (int a)
+{
+    while (a > 10) /* conditions(1/2) true(0) */
+		   /* conditions(end) */
+	x = a--;
+}
+
+void
+mcdc008c (int a)
+{
+    // should work, even with no body
+    while (a) /* conditions(2/2) */
+	break;
+}
+
+/* Multi-term loop conditional.  */
+void
+mcdc008d (int a, int b, int c, int d)
+{
+    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--;
+}
+
+void
+mcdc009b (int a, int b)
+{
+    while (a-- > 0 && b) {} /* conditions(2/4) true(0 1) */
+			    /* conditions(end) */
+}
+
+/* for loop.  */
+void
+mcdc010a (int a, int b)
+{
+    for (int i = 0; i < b; i++) /* conditions(2/2) */
+    {
+	if (a < b) /* conditions(2/2) */
+	    x = 1;
+	else
+	    x = a += 2;
+    }
+}
+
+void
+mcdc010b ()
+{
+    for (int a = 0; a <= 1; ++a) /* conditions(2/2) */
+    {
+	x = a;
+    }
+}
+
+int
+mcdc010c (int a, int b, int c)
+{
+    for (;a || b || c;) /* conditions(4/6) true(0 2) */
+			/* conditions(end) */
+	return 1;
+    return 0;
+}
+
+
+int always (int x) { (void) x; return 1; }
+
+/* No-condition infinite loops.  */
+void
+mcdc010d (int a)
+{
+    for (;;)
+    {
+	if (always(a)) /* conditions(1/2) false(0) */
+		       /* conditions(end) */
+	{
+	    x = a;
+	    break;
+	}
+	x += a + 1;
+    }
+}
+
+/* Conditionals without control flow constructs work.  */
+void
+mcdc011a (int a, int b, int c)
+{
+    x = (a && b) || c; /* conditions(5/6) false(1) */
+		       /* conditions(end) */
+}
+
+/* Sequential expressions are handled independently.  */
+void
+mcdc012a (int a, int b, int c)
+{
+    if (a || b) /* conditions(3/4) true(0) */
+		/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+
+    if (c) /* conditions(2/2) */
+	x = 1;
+}
+
+/* Cannot ever satisfy (masking) MC/DC, even with all input combinations,
+   because not all variables independently affect the decision.  */
+void
+mcdc013a (int a, int b, int c)
+{
+    (void)b;
+    /* Specification: (a && b) || c
+       The implementation does not match the specification.  This has branch
+       coverage, but not MC/DC. */
+    if ((a && !c) || c) /* conditions(5/6) false(1) */
+			/* conditions(end) */
+	x = 1;
+    else
+	x = 2;
+}
+
+void
+mcdc014a ()
+{
+    int conds[64] = { 0 };
+    /* conditions(64/128) true(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63) */
+    x = conds[ 0] || conds[ 1] || conds[ 2] || conds[ 3] || conds[ 4] ||
+	conds[ 5] || conds[ 6] || conds[ 7] || conds[ 8] || conds[ 9] ||
+	conds[10] || conds[11] || conds[12] || conds[13] || conds[14] ||
+	conds[15] || conds[16] || conds[17] || conds[18] || conds[19] ||
+	conds[20] || conds[21] || conds[22] || conds[23] || conds[24] ||
+	conds[25] || conds[26] || conds[27] || conds[28] || conds[29] ||
+	conds[30] || conds[31] || conds[32] || conds[33] || conds[34] ||
+	conds[35] || conds[36] || conds[37] || conds[38] || conds[39] ||
+	conds[40] || conds[41] || conds[42] || conds[43] || conds[44] ||
+	conds[45] || conds[46] || conds[47] || conds[48] || conds[49] ||
+	conds[50] || conds[51] || conds[52] || conds[53] || conds[54] ||
+	conds[55] || conds[56] || conds[57] || conds[58] || conds[59] ||
+	conds[60] || conds[61] || conds[62] || conds[63]
+	;  /* conditions(end) */
+}
+
+/* Early returns.  */
+void
+mcdc015a (int a, int b)
+{
+    if (a) /* conditions(2/2) */
+	return;
+
+    if (b) /* conditions(1/2) true(0) */
+	   /* conditions(end) */
+	x = 1;
+}
+
+void
+mcdc015b (int a, int b)
+{
+    for (int i = 5; i > a; i--) /* conditions(2/2) */
+    {
+	if (i == b) /* conditions(2/2) */
+	    return;
+	x = i;
+    }
+}
+
+void
+mcdc015c (int a, int b)
+{
+    for (int i = 5; i > a; i--) /* conditions(2/2) */
+    {
+	if (i == b) /* conditions(2/2) */
+	{
+	    x = 0;
+	    return;
+	}
+	else
+	{
+	    x = 1;
+	    return;
+	}
+
+	x = i;
+    }
+}
+
+/* Early returns, gotos.  */
+void
+mcdc015d (int a, int b, int c)
+{
+    if (a) return;  /* conditions(1/2) false(0) */
+		    /* conditions(end) */
+    if (id (b)) return; /* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+    if (id (c)) return; /* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+}
+
+
+/* Nested loops.  */
+void
+mcdc016a (int a, int b)
+{
+    for (int i = 0; i < a; i++) /* conditions(2/2) */
+	for (int k = 0; k < b; k++) /* conditions(2/2) */
+	    x = i + k;
+}
+
+void
+mcdc016b (int a, int b)
+{
+    for (int i = 0; i < a; i++) /* conditions(2/2) */
+    {
+	if (a > 5) /* conditions(2/2) */
+	    break;
+
+	for (int k = 0; k < b; k++) /* conditions(2/2) */
+	    x = i + k;
+    }
+}
+
+void
+mcdc016c (int a, int b)
+{
+    for (int i = 0; i < a; i++) /* conditions(2/2) */
+    {
+	if (a > 5) /* conditions(1/2) true(0) */
+		   /* conditions(end) */
+	    return;
+
+	for (int k = 0; k < b; k++) /* conditions(2/2) */
+	    x = i + k;
+    }
+}
+
+void
+mcdc016d (int a, int b)
+{
+    for (int i = 0; i < a; i++) /* conditions(2/2) */
+    {
+	for (int k = 0; k < 5; k++) /* conditions(2/2) */
+	{
+	    if (b > 5) /* conditions(1/2) true(0) */
+		       /* conditions(end) */
+		return;
+	    x = i + k;
+	}
+
+    }
+}
+
+/* do-while loops */
+void
+mcdc017a (int a)
+{
+    do
+    {
+	a--;
+    } while (a > 0); /* conditions(2/2) */
+}
+
+void
+mcdc017b (int a, int b)
+{
+    do
+    {
+	/* This call is important; it can add more nodes to the body in the
+	   CFG, which changes how close exits and breaks are to the loop
+	   conditional.  */
+	noop ();
+	a--;
+	if (b) /* conditions(2/2) */
+	    break;
+
+    } while (a > 0); /* conditions(2/2) */
+}
+
+void
+mcdc017c (int a, int b)
+{
+    int left = 0;
+    int right = 0;
+    int n = a + b;
+    do
+    {
+	if (a) /* conditions(1/2) false(0) */
+	       /* conditions(end) */
+	{
+	    left = a > left ? b : left; /* conditions(2/2) */
+	}
+	if (b) /* conditions(1/2) false(0) */
+	       /* conditions(end) */
+	{
+	    right = b > right ? a : right; /* conditions(2/2) */
+	}
+    } while (n-- > 0); /* conditions(2/2) */
+}
+
+void
+mcdc017d (int a, int b, int c)
+{
+    do
+    {
+	a--;
+    } while (a > 0 && b && c);	/* conditions(0/6) true(0 1 2) false(0 1 2) */
+				/* conditions(end) */
+}
+
+/* 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) */
+			 /* conditions(end) */
+	{
+	    x = 2;
+	    break;
+	}
+	else if (e || f) /* conditions(2/4) false(0 1) */
+			 /* conditions(end) */
+	{
+	    if (id(g)) /* conditions(2/2) */
+		return 0;
+	    continue;
+	}
+    } while (a-- > 0); /* conditions(2/2) */
+
+    return 1;
+}
+
+void
+mcdc018b (int a, int b, int c)
+{
+    int n;
+    while (a) /* conditions(2/2) */
+    {
+	/* else block does not make a difference for the problem, but ensures
+	   loop termination. */
+	if (b) /* conditions(2/2) */
+	    n = c ? 0 : 0; // does not show up in CFG (embedded in the block)
+	else
+	    n = 0;
+	a = n;
+    }
+}
+
+/* Adapted from zlib/compress2.  */
+void
+mcdc018c (int a, int b)
+{
+    int err;
+    do
+    {
+	a = inv (a);
+	err = a;
+    } while (err); /* conditions(1/2) true(0) */
+		   /* conditions(end) */
+
+    a = id (a);
+    if (a) /* conditions(1/2) true(0) */
+	   /* conditions(end) */
+	x *= a + 1;
+}
+
+/* Too many conditions, coverage gives up. */
+void
+mcdc019a ()
+{
+    int conds[65] = { 0 };
+    #pragma GCC diagnostic push
+    #pragma GCC diagnostic ignored "-Wcoverage-too-many-conditions"
+    x = conds[ 0] || conds[ 1] || conds[ 2] || conds[ 3] || conds[ 4] ||
+	conds[ 5] || conds[ 6] || conds[ 7] || conds[ 8] || conds[ 9] ||
+	conds[10] || conds[11] || conds[12] || conds[13] || conds[14] ||
+	conds[15] || conds[16] || conds[17] || conds[18] || conds[19] ||
+	conds[20] || conds[21] || conds[22] || conds[23] || conds[24] ||
+	conds[25] || conds[26] || conds[27] || conds[28] || conds[29] ||
+	conds[30] || conds[31] || conds[32] || conds[33] || conds[34] ||
+	conds[35] || conds[36] || conds[37] || conds[38] || conds[39] ||
+	conds[40] || conds[41] || conds[42] || conds[43] || conds[44] ||
+	conds[45] || conds[46] || conds[47] || conds[48] || conds[49] ||
+	conds[50] || conds[51] || conds[52] || conds[53] || conds[54] ||
+	conds[55] || conds[56] || conds[57] || conds[58] || conds[59] ||
+	conds[60] || conds[61] || conds[62] || conds[63] || conds[64]
+	;
+    #pragma GCC diagnostic pop
+}
+
+/* Ternary.  */
+void
+mcdc020a (int a)
+{
+    // special case, this can be reduced to:
+    // _1 = argc != 0;
+    // e = (int) _1;
+    x = a ? 1 : 0;
+
+    // changing to different int makes branch
+    x = a ? 2 : 1; /* conditions(2/2) */
+}
+
+void
+mcdc020b (int a, int b)
+{
+    x = (a || b) ? 1 : 0; /* conditions(3/4) true(1) */
+			  /* conditions(end) */
+}
+
+void
+mcdc020c (int a, int b)
+{
+    x = a ? 0
+	: b ? 1 /* conditions(2/2) */
+	: 2;    /* conditions(1/2) false(0) */
+		/* conditions(end) */
+}
+
+int
+mcdc020d (int b, int c, int d, int e, int f)
+{
+    return ((b ? c : d) && e && f); /* conditions(7/10) true(2) false(3 4) */
+				    /* conditions(end) */
+}
+
+/* Infinite loop (no exit-edge), this should not be called, but it should
+   compile fine.  */
+void
+mcdc021a ()
+{
+    while (1)
+	;
+}
+
+/* Computed goto can give all sorts of problems, including difficult path
+   contractions. */
+void
+mcdc021b ()
+{
+  void *op = &&dest;
+dest:
+  if (op) /* conditions(0/2) true(0) false(0) */
+	  /* conditions(end) */
+    goto * 0;
+}
+
+int __sigsetjmp ();
+
+/* This should compile, but not called. */
+void
+mcdc021c ()
+{
+  while (x) /* conditions(0/2) true(0) false(0)*/
+	    /* conditions(end) */
+     __sigsetjmp ();
+}
+
+/* If edges are not properly contracted the a && id (b) will be interpreted as
+   two independent expressions. */
+void
+mcdc021d (int a, int b, int c, int d)
+{
+    if (a && id (b)) /* conditions(1/4) true(0 1) false(0) */
+		     /* conditions(end) */
+	x = 1;
+    else if (c && id (d)) /* conditions(1/4) true(0 1) false(0) */
+			  /* conditions(end) */
+	x = 2;
+    else
+	x = 3;
+}
+
+/* Adapted from linux arch/x86/tools/relocs.c
+   With poor edge contracting this became an infinite loop. */
+void
+mcdc022a (int a, int b)
+{
+    for (int i = 0; i < 5; i++) /* conditions(2/2) */
+    {
+	x = i;
+	for (int j = i; j < 5; j++) /* conditions(2/2) */
+	{
+	    if (id (id (a)) || id (b)) /* conditions(3/4) true(0) */
+				       /* conditions(end) */
+		continue;
+	    b = inv(b);
+	}
+    }
+}
+
+int
+mcdc022b (int a)
+{
+    int devt;
+    if (a) /* conditions(2/2) */
+    {
+	x = a * 2;
+	if (x != a / 10 || x != a % 10) /* conditions(1/4) true(1) false(0 1) */
+					/* conditions(end) */
+	    return 0;
+    } else {
+	devt = id (a);
+	if (devt) /* conditions(1/2) true(0) */
+		  /* conditions(end) */
+	    return 0;
+    }
+
+    return devt;
+}
+
+/* Adapted from linux arch/x86/events/intel/ds.c
+
+   It broken sorting so that the entry block was not the first node after
+   sorting. */
+void
+mcdc022c (int a)
+{
+    if (!a) /* conditions(2/2) */
+	return;
+
+    for (int i = 0; i < 5; i++) /* conditions(2/2) */
+    {
+	if (id (a + i) || inv (a - 1)) /* conditions(1/4) false(0 1) true(1) */
+				       /* conditions(end) */
+	    x = a + i;
+	if (inv (a)) /* conditions(1/2) true(0) */
+		     /* conditions(end) */
+	    break;
+    }
+}
+
+void
+mcdc022d (int a)
+{
+    int i;
+    for (i = 0; i < id (a); i++) /* conditions(1/2) false(0) */
+    {
+	if (!inv (a)) /* conditions(1/2) false(0)*/
+		      /* conditions(end) */
+	    break;
+    }
+
+    if (i < a) /* conditions(1/2) false(0) */
+	       /* conditions(end) */
+	x = a + 1;
+}
+
+/* Adapted from openssl-3.0.1/crypto/cmp/cmp_msg.c ossl_cmp_error_new ().  */
+void
+mcdc022e (int a, int b, int c, int d)
+{
+    if (a || b) /* conditions(1/4) true(0) false(0 1) */
+		/* conditions(end) */
+    {
+	if (always (c)) /* conditions(1/2) false(0) */
+			/* conditions(end) */
+	    goto err;
+	d++;
+    }
+
+    if (d)  /* conditions(0/2) true(0) false(0) */
+	    /* conditions(end) */
+	goto err;
+    return;
+
+err:
+    noop ();
+}
+
+/* 023 specifically tests that masking works correctly, which gets complicated
+   fast with a mix of operators and deep subexpressions.  These tests violates
+   the style guide slightly to emphasize the nesting.  They all share the same
+   implementation and only one input is given to each function to obtain clean
+   coverage results. */
+void
+mcdc023a (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    // [a m n] = 0, [b, ...] = 1
+    // a is masked by b and the remaining terms should be short circuited
+    if (/* conditions(1/24) true(0 2 3 4 5 6 7 8 9 10 11) false(0 1 2 3 4 5 6 7 8 9 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023b (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    // [a b d h] = 0, [c, ...] = 1
+    // h = 0 => false but does not mask (a || b) or (c && d). d = 0 masks c.
+    if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 4 5 6 8 9 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023c (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    /* [m n a b] = 0, [...] = 1
+       n,m = 0 should mask all other terms than a, b */
+    if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 3 4 5 6 7 8 9) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023d (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    /* [a b] = 0, [h, ...] = 1
+       n,m = 0 should mask all other terms than a, b */
+    if (/* conditions(4/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 3 4 5 6 7 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023e (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    /* [a b d] = 0, [c h, ...] = 1
+       h = 1 should mask c, d, leave other terms intact.
+       If [k l m n] were false then h itself would be masked.
+       [a b] are masked as collateral by [m n]. */
+    if (/* conditions(5/24) true(0 1 2 3 6 9 11) false(0 1 2 3 4 5 6 7 8 9 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023f (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    /* [a b c f g] = 0, [e, ...] = 1
+       [f g] = 0 should mask e, leave [c d] intact. */
+    if (/* conditions(5/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(3 4 7 8 9 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+void
+mcdc023g (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
+	  int l, int m, int n)
+{
+    /* [a b d f g] = 0, [e c, ...] = 1
+       Same as 023f but with [c d] flipped so d masks c rather than c
+       short-circuits.  This should not be lost. */
+    if (/* conditions(5/24) true(0 1 2 3 4 5 6 7 8 9 10 11) false(2 4 7 8 9 10 11) */
+	/* conditions(end) */
+	   (a || b)
+	|| (   ((c && d) || (e && (f || g) && h))
+	    && (k || l)
+	    && (m || n)))
+	x = a + b;
+    else
+	x = b + c;
+}
+
+/* Gotos, return, labels can make odd graphs.  It is important that conditions
+   are assigned to the right expression, and that there are no miscounts.  In
+   these tests values may be re-used, as checking things like masking an
+   independence is done in other test cases and not so useful here.  */
+void
+mcdc024a (int a, int b)
+{
+    /* This is a reference implementation without the labels, which should not
+       alter behavior.  */
+    if (a && b) /* conditions(2/4) true(0 1) */
+		/* conditions(end) */
+    {
+	x = 1;
+    }
+    else
+    {
+	x = 2;
+    }
+
+    if (a || b) /* conditions(2/4) false(0 1) */
+		/* conditions(end) */
+    {
+	x = 1;
+    }
+    else
+    {
+	x = 2;
+    }
+}
+
+void
+mcdc024b (int a, int b)
+{
+    if (a && b) /* conditions(2/4) true(0 1) */
+		/* conditions(end) */
+    {
+label1:
+	x = 1;
+    }
+    else
+    {
+	x = 2;
+    }
+
+    if (a || b) /* conditions(2/4) false(0 1) */
+		/* conditions(end) */
+    {
+label2:
+	x = 1;
+    }
+    else
+    {
+	x = 2;
+    }
+}
+
+void
+mcdc024c (int a, int b)
+{
+
+    if (a && b) /* conditions(2/4) true(0 1) */
+		/* conditions(end) */
+    {
+	x = 1;
+    }
+    else
+    {
+label1:
+	x = 2;
+    }
+
+    if (a || b) /* conditions(2/4) false(0 1) */
+		/* conditions(end) */
+    {
+	x = 1;
+    }
+    else
+    {
+label2:
+	x = 2;
+    }
+}
+
+void
+mcdc024d (int a, int b)
+{
+    if (a && b) /* conditions(2/4) true(0 1) */
+		/* conditions(end) */
+    {
+label1:
+	x = 1;
+    }
+    else
+    {
+label2:
+	x = 2;
+    }
+
+    if (a || b) /* conditions(2/4) false(0 1) */
+		/* conditions(end) */
+    {
+label3:
+	x = 1;
+    }
+    else
+    {
+label4:
+	x = 2;
+    }
+}
+
+int
+mcdc024e (int a, int b, int c)
+{
+    /* Graphs can get complicated with the innermost returns and else-less if,
+       so we must make sure these conditions are counted correctly.  */
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	{
+	    if (c)  /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+		return 1;
+	    else
+		return 2;
+	}
+
+	if (a)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return 3;
+    }
+
+    return 5;
+}
+
+/* Nested else-less ifs with inner returns needs to be counted right, which
+   puts some pressure on the expression isolation.  */
+int
+mcdc024f (int a, int b, int c)
+{
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	{
+	    if (c)  /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	    {
+		if (a)	/* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+		    return 1;
+		else
+		    return 2;
+	    }
+
+	    if (a)  /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+		return 3;
+	}
+
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return 4;
+    }
+    return 5;
+}
+
+int
+mcdc024g (int a, int b, int c)
+{
+    if (b)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+	return 0;
+
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	{
+	    b += 2;
+	    if (b & 0xFF)   /* conditions(0/2) true(0) false(0) */
+			    /* conditions(end) */
+		c++;
+
+	    return c;
+	}
+	c += 10;
+    }
+    return 1;
+}
+
+
+int
+mcdc024h (int a, int b, int c)
+{
+    if (b)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+	goto inner;
+
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+	++a;
+
+
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	{
+inner:
+	    b += 2;
+	    if (b & 0xFF)   /* conditions(0/2) true(0) false(0) */
+			    /* conditions(end) */
+		c++;
+
+	    return c;
+	}
+	c += 10;
+    }
+    return 1;
+}
+
+int
+mcdc024i (int a, int b, int c)
+{
+fst:
+    b++;
+snd:
+    b++;
+
+    if (b > 10) /* conditions(2/2) */
+		/* conditions(end) */
+	goto end;
+
+    if (b < 5)  /* conditions(2/2) */
+		/* conditions(end) */
+	goto fst;
+    else
+	goto snd;
+
+end:
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+	++a;
+
+
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	{
+	    b += 2;
+	    if (b & 0xFF)   /* conditions(0/2) true(0) false(0) */
+			    /* conditions(end) */
+		c++;
+
+	    return c;
+	}
+	c += 10;
+    }
+    return 1;
+}
+
+/* Adapted from alsa-lib 1.2.8 src/control/control.c.  If two expressions share
+   an outcome with bypass nodes they would be handled twice.  */
+int
+mcdc025a (int a, int b, int c)
+{
+    int err;
+    if (id (a)) /* conditions(1/2) true(0) */
+		/* conditions(end) */
+    {
+	if (b)	/* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return -1;
+    }
+    else
+    {
+	err = id (c);
+	if (err > 0) /* conditions(1/2) false(0) */
+		     /* conditions(end) */
+	    return err;
+    }
+    err = id (a);
+    return err;
+}
+
+/* Boolean expressions in function call parameters.  These tests are all built
+   with a reference expression which should behave the same as the function
+   call versions.  */
+int
+mcdc026a (int a, int b, int c, int d, int e)
+{
+    int cad = c && d; /* conditions(4/4) */
+		      /* conditions(end) */
+    int x = a && b && cad && e;		/* conditions(5/8) false(0 1 3) */
+					/* conditions(end) */
+    int y = a && b && id (c && d) && e;	/* conditions(5/8; 4/4) false(0 1 3;;) */
+					/* conditions(end) */
+    return x + y;
+}
+
+int
+mcdc026b (int a, int b, int c, int d, int e)
+{
+    int dae = d && e; /* conditions(3/4) false(1) */
+		      /* conditions(end) */
+    int x = a && b && c && dae;		/* conditions(6/8) false(0 1) */
+    int y = a && b && c && id (d && e);	/* conditions(6/8; 3/4) false(0 1; 1) */
+					/* conditions(end) */
+    return x + y;
+}
+
+int
+mcdc026c (int a, int b, int c, int d, int e)
+{
+    int cod = c || d;	/* conditions(3/4) true(1) */
+			/* conditions(end) */
+    int x = a && b && cod && e;		/* conditions(5/8) false(0 1 3) */
+    int y = a && b && id (c || d) && e;	/* conditions(5/8; 3/4) true(;1) false(0 1 3;) */
+					/* conditions(end) */
+    return x+y;
+}
+
+int
+mcdc026d (int a, int b, int c, int d, int e)
+{
+    int aab = a && b; /* conditions(2/4) false(0 1) */
+		      /* conditions(end) */
+    int cod = c || d; /* conditions(3/4) true(1) */
+		      /* conditions(end) */
+    int x = aab && cod && e; /* conditions(4/6) false(0 2) */
+			     /* conditions(end) */
+    int y = id (a && b) && id (c || d) && e; /* conditions(2/4;4/6;3/4) true(;;1) false(0 1;0 2;;) */
+					     /* conditions(end) */
+    return x + y;
+}
+
+int
+mcdc026e (int a, int b, int c, int d, int e)
+{
+    int cod = c || d; /* conditions(3/4) true(1) */
+		      /* conditions(end) */
+    int dae = d && e; /* conditions(3/4) false(1) */
+		      /* conditions(end) */
+    int aacod = a && cod; /* conditions(3/4) false(0)*/
+			  /* conditions(end) */
+    int x = aacod && dae; /* conditions(4/4) */
+			  /* conditions(end) */
+    int y = id (a && id (c || d)) && id (d && e); /* conditions(3/4; 3/4; 4/4; 3/4) true(;1;;) false(0;;;1) */
+						  /* conditions(end) */
+    return x + y;
+}
+
+int main ()
+{
+    mcdc001a (0, 1);
+
+    mcdc001b (0, 1);
+    mcdc001b (0, 0);
+
+    mcdc001c (0, 1);
+    mcdc001c (0, 0);
+    mcdc001c (1, 1);
+
+    mcdc001d (1, 1, 1);
+    mcdc001d (0, 1, 0);
+
+    mcdc002a (1, 0);
+
+    mcdc002b (1, 0);
+    mcdc002b (1, 1);
+
+    mcdc002c (0, 0);
+    mcdc002c (1, 1);
+    mcdc002c (1, 0);
+
+    mcdc002d (1, 1, 1);
+    mcdc002d (1, 0, 0);
+
+    mcdc003a (0, 0);
+    mcdc003a (1, 0);
+
+    mcdc004a (0);
+    mcdc004b (0);
+    mcdc004b (1);
+    mcdc004c (1);
+
+    mcdc004d (0, 0, 0);
+    mcdc004d (1, 1, 1);
+
+    mcdc004e (0, 0, 0);
+    mcdc004e (1, 1, 1);
+
+    mcdc004f (1, 1, 1);
+
+    mcdc005a (1, 0, 1);
+
+    mcdc005b (1, 1, 0, 0);
+    mcdc005b (1, 0, 0, 0);
+
+    mcdc005c (0, 1, 1, 0);
+
+    mcdc005d (1, 0, 0, 0);
+
+    mcdc005e (0, 0);
+    mcdc005e (0, 1);
+    mcdc005e (1, 0);
+    mcdc005e (1, 1);
+
+    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);
+
+    mcdc006d (1, 0, 0);
+    mcdc006d (1, 0, 1);
+
+    mcdc006e (0, 0, 0, 0);
+    mcdc006e (0, 0, 1, 0);
+    mcdc006e (0, 1, 0, 0);
+
+    mcdc007a (0, 0, 0, 0);
+    mcdc007a (1, 0, 0, 0);
+    mcdc007a (0, 0, 1, 0);
+
+    mcdc007b (0, 0, 0);
+    mcdc007b (0, 1, 1);
+    mcdc007b (1, 0, 1);
+
+    mcdc007c (0, 0, 0);
+    mcdc007c (0, 1, 1);
+    mcdc007c (1, 0, 1);
+
+    mcdc007d (0, 1, 0, 1, 1);
+
+    mcdc008a (0);
+
+    mcdc008b (0);
+
+    mcdc008c (0);
+    mcdc008c (1);
+
+    mcdc008d (0, 0, 0, 0);
+    mcdc008d (1, 0, 0, 0);
+    mcdc008d (1, 0, 1, 0);
+    mcdc008d (1, 0, 1, 1);
+    mcdc008d (1, 1, 1, 1);
+
+    mcdc009a (0, 0);
+    mcdc009a (1, 1);
+
+    mcdc009b (0, 0);
+    mcdc009b (1, 0);
+
+    mcdc010a (0, 0);
+    mcdc010a (0, 9);
+    mcdc010a (2, 1);
+
+    mcdc010b ();
+
+    mcdc010c (0, 0, 0);
+    mcdc010c (0, 1, 0);
+
+    mcdc010d (1);
+
+    mcdc011a (0, 0, 0);
+    mcdc011a (1, 1, 0);
+    mcdc011a (1, 0, 1);
+
+    mcdc012a (0, 0, 0);
+    mcdc012a (0, 1, 1);
+
+    mcdc013a (0, 0, 0);
+    mcdc013a (0, 0, 1);
+    mcdc013a (0, 1, 0);
+    mcdc013a (0, 1, 1);
+    mcdc013a (1, 0, 0);
+    mcdc013a (1, 0, 1);
+    mcdc013a (1, 1, 0);
+    mcdc013a (1, 1, 1);
+
+    mcdc014a ();
+
+    mcdc015a (0, 0);
+    mcdc015a (1, 0);
+
+    mcdc015b (0, 0);
+    mcdc015b (0, 1);
+    mcdc015b (6, 1);
+
+    mcdc015c (0, 0);
+    mcdc015c (0, 5);
+    mcdc015c (6, 1);
+
+    mcdc015d (1, 0, 0);
+
+    mcdc016a (5, 5);
+
+    mcdc016b (5, 5);
+    mcdc016b (6, 5);
+
+    mcdc016c (5, 5);
+
+    mcdc016d (1, 0);
+
+    mcdc017a (0);
+    mcdc017a (2);
+
+    mcdc017b (2, 0);
+    mcdc017b (0, 1);
+
+    mcdc017c (1, 1);
+
+    mcdc018a (0, 0, 1, 1, 0, 0, 0, 0);
+    mcdc018a (0, 1, 0, 0, 0, 0, 1, -2);
+    mcdc018a (0, 6, 0, 0, 0, 0, 1, -2);
+    mcdc018a (0, 6, 0, 0, 0, 0, 1, -2);
+    mcdc018a (0, 0, 0, 1, 0, 1, 1, 0);
+    mcdc018a (1, 0, 0, 0, 1, 1, 0, 0);
+
+    mcdc018b (1, 0, 0);
+    mcdc018b (1, 1, 0);
+
+    mcdc018c (1, 1);
+
+    mcdc019a ();
+
+    mcdc020a (0);
+    mcdc020a (1);
+
+    mcdc020b (0, 0);
+    mcdc020b (1, 0);
+
+    mcdc020c (0, 1);
+    mcdc020c (1, 1);
+
+    mcdc020d (0, 0, 0, 0, 0);
+    mcdc020d (1, 0, 0, 1, 1);
+    mcdc020d (1, 1, 0, 1, 1);
+
+    mcdc021d (1, 0, 1, 0);
+
+    mcdc022a (0, 0);
+
+    mcdc022b (0);
+    mcdc022b (1);
+
+    mcdc022c (0);
+    mcdc022c (1);
+
+    mcdc022d (1);
+    mcdc022e (0, 1, 1, 0);
+
+    mcdc023a (0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+    mcdc023b (0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1);
+    mcdc023c (0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0);
+    mcdc023d (0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1);
+    mcdc023e (0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1);
+    mcdc023f (0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1);
+    mcdc023g (0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1);
+
+    mcdc024a (0, 1);
+    mcdc024b (0, 1);
+    mcdc024c (0, 1);
+    mcdc024d (0, 1);
+    mcdc024a (1, 0);
+    mcdc024b (1, 0);
+    mcdc024c (1, 0);
+    mcdc024d (1, 0);
+
+    mcdc024e (0, 0, 0);
+    mcdc024f (0, 0, 0);
+    mcdc024g (0, 0, 0);
+    mcdc024h (0, 0, 0);
+    mcdc024i (0, 0, 0);
+
+    mcdc025a (0, 0, 1);
+
+    mcdc026a (1, 1, 1, 0, 1);
+    mcdc026a (1, 1, 0, 0, 1);
+    mcdc026a (1, 1, 1, 1, 1);
+
+    mcdc026b (1, 1, 1, 0, 1);
+    mcdc026b (1, 1, 0, 0, 1);
+    mcdc026b (1, 1, 1, 1, 1);
+
+    mcdc026c (1, 1, 1, 0, 1);
+    mcdc026c (1, 1, 0, 0, 1);
+    mcdc026c (1, 1, 1, 1, 1);
+
+    mcdc026d (1, 1, 1, 0, 1);
+    mcdc026d (1, 1, 0, 0, 1);
+    mcdc026d (1, 1, 1, 1, 1);
+
+    mcdc026e (1, 1, 1, 0, 1);
+    mcdc026e (1, 1, 0, 0, 1);
+    mcdc026e (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..215faffc980
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-20.c
@@ -0,0 +1,22 @@
+/* { dg-options "-fcondition-coverage -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..3395422166a
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-21.c
@@ -0,0 +1,16 @@
+/* { dg-options "-fcondition-coverage" } */
+
+/* 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/gcc.misc-tests/gcov-22.c b/gcc/testsuite/gcc.misc-tests/gcov-22.c
new file mode 100644
index 00000000000..641791a7223
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-22.c
@@ -0,0 +1,103 @@
+/* { dg-options "-fcondition-coverage -ftest-coverage" } */
+/* { dg-do run { target native } } */
+
+#include <setjmp.h>
+jmp_buf buf;
+
+void noop () {}
+int identity (int x) { return x; }
+
+/* This function is a test to verify that the expression isolation does not
+   break on a CFG with the right set of complex edges.  The (_ && setjmp)
+   created complex edges after the function calls and a circular pair of
+   complex edges around the setjmp call.  This triggered a bug when the search
+   for right operands only would consider nodes dominated by the left-most
+   term, as this would only be the case if the complex edges were removed.  (_
+   && setjmp) is undefined behavior, but it does happen in the wild.
+
+   __builtin_setjmp did not trigger this, so we need setjmp from libc.  */
+void
+setjmp001 (int a, int b, int c)
+{
+    if (a)  /* conditions(1/2) true(0) */
+	    /* conditions(end) */
+	noop ();
+
+    if (b)  /* conditions(1/2) false(0) */
+	    /* conditions(end) */
+	noop ();
+
+    if (c && setjmp (buf))  /* conditions(1/4) true(0 1) false(1) */
+			    /* conditions(end) */
+	noop ();
+}
+
+/* Adapted from freetype-2.13.0 gxvalid/gxvmod.c classic_kern_validate */
+int
+setjmp002 (int a)
+{
+    int error = identity(a);
+
+    if (error)	/* conditions(1/2) true(0) */
+		/* conditions(end) */
+	goto Exit;
+
+   if (a+1) /* conditions(1/2) false(0) */
+	    /* conditions(end) */
+   {
+       noop ();
+       if (setjmp (buf))    /* conditions(1/2) true(0) */
+			    /* conditions(end) */
+	   noop ();
+
+	if (error)  /* conditions(1/2) true(0) */
+		    /* conditions(end) */
+	    noop ();
+   }
+
+   error--;
+
+Exit:
+   return error;
+}
+
+int
+setjmp003 (int a)
+{
+    /* || setjmp is undefined behavior, so the result here does not have to
+       make sense.  It would be nice if the result is not something like 35/4
+       conditions covered.  */
+    if (a || setjmp (buf)) /* conditions(suppress) */
+			   /* conditions(end) */
+	a += 12;
+
+    return a;
+}
+
+jmp_buf dest;
+
+int
+setdest ()
+{
+    if (setjmp (dest)) /* conditions(2/2) */
+	return 1;
+    return 2;
+}
+
+void
+jump ()
+{
+    longjmp (dest, 1);
+}
+
+int
+main ()
+{
+    setjmp001 (0, 1, 0);
+    setjmp002 (0);
+    setjmp003 (0);
+    setdest ();
+    jump ();
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-22.c } } } */
diff --git a/gcc/testsuite/gcc.misc-tests/gcov-23.c b/gcc/testsuite/gcc.misc-tests/gcov-23.c
new file mode 100644
index 00000000000..72849d80e3a
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-23.c
@@ -0,0 +1,361 @@
+/* { dg-options "-fcondition-coverage -ftest-coverage -O2 -c" } */
+
+#include <stdint.h>
+#include <limits.h>
+#include <setjmp.h>
+jmp_buf buf;
+
+int id (int);
+int idp (int *);
+int err;
+char c;
+
+/* This becomes problematic only under optimization for the case when the
+   compiler cannot inline the function but have to generate a call.  It is not
+   really interesting to run, only build.  Notably, both the function calls and
+   the return values are important to construct a problematic graph.
+
+   This test is also a good example of where optimization makes condition
+   coverage unpredictable, but not unusable.  If this is built without
+   optimization the conditions work as you would expect from reading the
+   source.  */
+/* Adapted from cpio-2.14 gnu/utmens.c lutimens ().  */
+int
+mcdc001 (int *v)
+{
+    int adjusted;
+    int adjustment_needed = 0;
+
+    int *ts = v ? &adjusted : 0; /* conditions(0/4) true(0 1) false(0 1) */
+				 /* conditions(end) */
+    if (ts)
+	adjustment_needed = idp (ts);
+    if (adjustment_needed < 0)
+	return -1;
+
+    if (adjustment_needed)  /* conditions(0/2) true(0) false(0) */
+			    /* conditions(end) */
+    {
+	if (adjustment_needed != 3) /* conditions(0/2) true(0) false(0) */
+				    /* conditions(end) */
+	    return -1;
+	if (ts) /* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return 0;
+    }
+
+    if (adjustment_needed && idp (&adjusted)) /* conditions(0/4) true(0 1) false(0 1) */
+					      /* conditions(end) */
+	return -1;
+    if (adjusted)   /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	return idp (ts);
+
+    return -1;
+}
+
+/* This failed when the candidate set internal/contracted-past nodes were not
+   properly marked as reachable in the candidate reduction phase.  */
+/* Adapted from cpio-2.14 gnu/mktime.c mktime_internal ().  */
+int
+mcdc002 ()
+{
+    int a;
+    if (idp (&a)) /* conditions(0/2) true(0) false(0) */
+		  /* conditions(end) */
+    {
+	if (id (a)) /* conditions(0/2) true(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	    goto exit;
+
+	if (err) /* conditions(0/2) true(0/2) true(0) false(0) */
+		 /* conditions(end) */
+	    return -1;
+    }
+
+exit:
+    return a;
+}
+
+/* Adapted from icu4c-73.1 common/ucase.cpp ucase_getCaseLocale ().  */
+int
+mcdc003 (const char *locale)
+{
+    /* extern, so its effect won't be optimized out.  */
+    c = *locale++;
+    if (c == 'z') /* conditions(0/2) true(0) false(0) */
+		  /* conditions(end) */
+    {
+	return 1;
+    }
+    else if (c >= 'a') /* conditions(0/2) true(0) false(0) */
+		      /* conditions(end) */
+    {
+	if (id (c)) /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	    c = *locale++;
+    }
+    else
+    {
+	if (c == 'T')
+	{
+	    if (id (c)) /* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+		c = *locale++;
+	    if (id (c)) /* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+		c = *locale++;
+	}
+	/* This may or may not become a jump table.  */
+	else if (c == 'L') /* conditions(suppress) */
+			   /* conditions(end) */
+	    c = *locale++;
+	else if (c == 'E') /* conditions(suppress) */
+			   /* conditions(end) */
+	    c = *locale++;
+	else if (c == 'N') /* conditions(suppress) */
+			   /* conditions(end) */
+	    c = *locale++;
+	else if (c == 'H') /* conditions(suppress) */
+			   /* conditions(end) */
+	{
+	    c = *locale++;
+	    if (id (c)) /* conditions(0/2) true(0) false(0) */
+			/* conditions(end) */
+		c = *locale++;
+	}
+    }
+
+    return 1;
+}
+
+/* The || will be changed to |, so it is impractical to predict the number of
+   conditions.  If the walk is not properly implemented this will not finish
+   compiling, so the actual coverage is not interesting.  */
+/* Adapted from icu4c-73.1 common/uresdata.cpp res_findResource ().  */
+int
+mcdc004 (int r, char* path, char* key)
+{
+    char *idcc (char *, char);
+    #define is_kind1(type) ((type) == 23 || (type) == 14 || (type == 115))
+    #define is_kind2(type) ((type) == 16 || (type) == 77 || (type == 118))
+    #define is_kind12(type) (is_kind1 ((type)) || is_kind2 ((type)))
+
+    char *nextSepP = path;
+    int t1 = r;
+    int type = id (t1);
+
+    if (!is_kind12 (type)) /* conditions(suppress) */
+			   /* conditions(end) */
+	return -1;
+
+    while (*path && t1 != -1 && is_kind12 (type)) /* conditions(suppress) */
+						  /* conditions(end) */
+    {
+	nextSepP = idcc(path, '/');
+	if(nextSepP == path) /* conditions(0/2) true(0) false(0) */
+			     /* conditions(end) */
+	    return -1;
+
+	if (*nextSepP == 'a') /* conditions(0/2) true(0) false(0) */
+			      /* conditions(end) */
+	    *key = *path;
+	else if (*nextSepP == 'b')  /* conditions(0/2) true(0) false(0) */
+				    /* conditions(end) */
+	    *key = 0;
+	type = t1;
+    }
+
+    return t1;
+}
+
+/* Adapted from jxl 0.8.2 lib/extras/dec/apng.cc processing_start ().
+   This created a graph where depth-first traversal of the CFG would not
+   process nodes in the wrong order (the extra control inserted from setjmp
+   created a path of complexes from root to !b without going through !a).
+
+   This only happened under optimization.  */
+int
+mcdc005 (int a, int b)
+{
+    a = id (a);
+    b = id (b);
+
+    /* The a || b gets transformed to a | b, then fused with setjmp because
+       they both have the same return value.  */
+    if (a || b) /* conditions(0/4) true(0 1) false(0 1) */
+		/* conditions(end) */
+	return 1;
+    else
+	a += 1;
+
+    if (setjmp (buf))
+	return 1;
+
+    return a;
+}
+
+/* Adapted from cpio-2.14 gnu/quotearg.c quotearg_buffer_restyled.  The ifs in
+   the cases (with fallthrough) re-use the same value which under optimization
+   causes path reuse which must be sorted out.  */
+int
+mcdc006 (int quoting_style, int elide, int *buffer)
+{
+    int backslash = 0;
+    switch (quoting_style)
+    {
+	case 1:
+	    if (!elide)
+		backslash = 1;
+	case 2:
+	    if (!elide)
+		if (buffer)
+		    *buffer = '"';
+    }
+
+    if (quoting_style == 2 && backslash)
+	quoting_style = 1;
+    return 1;
+}
+
+/* Adapted from pcre2-10.42 pcre2_compile.c pcre2_compile.  If SSA nodes are
+   created at the wrong place in the block it will fail flow analysis (because
+   the label is in the middle of block), caused by the final break in this
+   case.  */
+void
+mcdc007 (int options, int *pso, int len)
+{
+    if (options == 5)
+	return;
+
+    while (options--)
+    {
+	int i;
+	for (i = 0; i < len; i++)
+	{
+	    int *p = pso + i;
+	    int skipatstart = *p + 2;
+	    if (skipatstart) {
+		switch(*p)
+		{
+		    case 1:
+			*p |= *p + 1;
+			break;
+		    case 2:
+			skipatstart += *p - skipatstart;
+			break;
+		}
+		break;
+	    }
+	}
+	if (i >= len) break;
+    }
+}
+
+/* Adapted from alsa-lib 1.2.8 pcm/pcm.c snd_pcm_chmap_print.  */
+int
+mcdc008 (int *map, unsigned maxlen, int *buf)
+{
+    unsigned int len = 0;
+    for (unsigned i = 0; i < *map; i++) {
+	unsigned int p = map[i] & 0xF;
+	if (i > 0) {
+	    if (len >= maxlen)
+		return -1;
+	}
+	if (map[i] & 0xFF)
+	    len += idp (buf + len);
+	else {
+	    len += idp (buf);
+	}
+	if (map[i] & 0xFF00) {
+	    len += idp (buf + len);
+	    if (len >= maxlen)
+		return -1;
+	}
+    }
+    return len;
+}
+
+/* Adapted from cpio-2.14 gnu/mktime.c mktime_internal ().  The combination of
+   goto, automatic variables, and the ternary causes the post dominator of the
+   highest topological ordered node not to be the common post dominator of the
+   expression as a whole.  */
+int
+mcdc009 (int *tp, int t, int isdst)
+{
+    int t0 = tp[0];
+    int t1 = tp[1];
+    int t2 = tp[2];
+
+    if (t0 < 0 || (isdst < 0 ? t1 : (isdst != 0)))
+	goto offset_found;
+
+    if (t == 0)
+	return -1;
+
+    t1 = t2;
+
+offset_found:
+    return t;
+}
+
+/* Adapted from Berkeley db 4.8.30 rep/rep_elect.c __rep_cmp_vote.  This
+   particular combination of fallthrough and folding creates a path into the
+   the inner if () that does not go through the first basic condition.  */
+void
+mcdc010 (int cmp, int *rep, int sites, int priority, int flags)
+{
+    if (sites > 1 && (priority != 0 || (flags & 0xFF)))
+    {
+	if ( (priority != 0 && *rep == 0)
+	|| (((priority == 0 && *rep == 0)
+	||   (priority != 0 && *rep != 0)) && cmp > 0))
+	{
+	    *rep = cmp;
+	}
+    }
+}
+
+/* For not sufficiently protected back edges this would create an infinite
+   loop.  */
+void
+mcdc011 (int a, int b)
+{
+    if (a && id (b))
+	for (;;) {}
+    id (a+1);
+}
+
+/* Adapted from alsa-1.2.8 tlv.c get_tlv_info ().  Under optimization, the
+   conditions may be replaced with min ().  */
+int
+mcdc012 (int x, int y)
+{
+    int err;
+    err = id (x);
+    if (err < 0)
+	return err;
+    err = id (y);
+    if (err < 0)
+	return err;
+    return 0;
+}
+
+/* Adapted from alsa-1.2.8 control.c snd_ctl_elem_id_compare_numid ().  This
+   test is probably not so accurate on targets where int == int64.  Under
+   optimization, the conditions may be replaced with min/max.   */
+int
+mcdc013 (const int64_t *id1, const int64_t *id2)
+{
+    int64_t d;
+    d = *id1 - *id2;
+    if (d & 0xFF)
+    {
+	if (d > INT_MAX)
+	    d = INT_MAX;
+	else if (d < INT_MIN)
+	    d = INT_MIN;
+    }
+    return d;
+}
diff --git a/gcc/testsuite/lib/gcov.exp b/gcc/testsuite/lib/gcov.exp
index e5e94fa5a76..5a3e20ce374 100644
--- a/gcc/testsuite/lib/gcov.exp
+++ b/gcc/testsuite/lib/gcov.exp
@@ -174,6 +174,252 @@ 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.
+#
+# In some very specific cases there is a need to match multiple conditions on
+# the same line, for example if (a && fn (b || c) && d), which is interpreted
+# roughly as tmp _bc = b || c; if (a && _bc && d).  The argument to fn is
+# considered its own expression and its coverage report will be written on the
+# same line.  For these cases, use conditions(n/m; n/m;...) true(0 1;;...)
+# where ; marks the end of the list element where the ith list matches the ith
+# expression. The true()/false() matchers can be omitted if no expression
+# expects them, otherwise use the empty list if all true/false outcomes are
+# covered.
+#
+# C++ can insert conditionals in the CFG that are not present in source code.
+# These must be manually suppressed since unexpected and unhandled conditions
+# are an error (to help combat regressions). Output can be suppressed with
+# conditions(suppress) and conditions(end). suppress should usually be on a
+# closing brace.
+#
+# Some expressions, when using unnamed temporaries as operands, will have
+# destructors in expressions. The coverage of the destructor will be reported
+# on the same line as the expression itself, but suppress() would also swallow
+# the expected tested-for messages. To handle these, use the destructor() [1]
+# which will suppress everything from and including the second "conditions
+# covered".
+#
+# [1] it is important that the destructor() is *on the same line* as the
+#     conditions(m/n)
+proc verify-conditions { testname testcase file } {
+    set failed 0
+    set suppress 0
+    set destructor 0
+    set should ""
+    set shouldt ""
+    set shouldf ""
+    set shouldall ""
+    set fd [open $file r]
+    set lineno 0
+    set checks [list]
+    set keywords {"end" "suppress"}
+    while {[gets $fd line] >= 0} {
+	regexp "^\[^:\]+: *(\[0-9\]+):" "$line" all lineno
+	set prefix "$testname line $lineno"
+
+	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] {
+	    # *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.
+	    regexp {conditions *\(([0-9a-z/]+)\)} "$line" all e
+	    if {([lsearch -exact $keywords $e] >= 0 || [regexp {\d+/\d+} "$e"]) == 0} {
+		fail "$prefix: expected conditions (n/m), (suppress) or (end); was ($e)"
+		incr failed
+		continue
+	    }
+
+	    # Any keyword means a new context. Set the error flag if not all
+	    # expected output has been seen, and reset the state.
+	    if {[llength $shouldt] != 0} {
+		fail "$prefix: expected 'not covered (true)' for terms: $shouldt"
+		set ok 0
+	    }
+
+	    if {[llength $shouldf] != 0} {
+		fail "$prefix: expected 'not covered (false)' for terms: $shouldf"
+		set ok 0
+	    }
+
+	    if {$shouldall ne ""} {
+		fail "$prefix: coverage summary not found; expected $shouldall"
+		set ok 0
+	    }
+
+	    if {[llength $checks] != 0} {
+		set missing [llength checks]
+		fail "$prefix: expected $missing more conditions"
+		set ok 0
+	    }
+
+	    set suppress 0
+	    set destructor 0
+	    set setup 0
+	    set checks [list]
+
+	    if [regexp {destructor\(\)} "$line"] {
+		set destructor 1
+	    }
+
+	    # Find the expressions on this line. There may be more, to support
+	    # constructs like (a && fn (b && c) && d).
+	    # The match produces lists like [conditions(n/m) n m]
+	    set argconds ""
+	    set argtrue ""
+	    set argfalse ""
+	    regexp {conditions *\(([0-9 /;]+)\)} $line _ argconds
+	    regexp {true *\(([0-9 ;]+)\)} $line _ argtrue
+	    regexp {false *\(([0-9 ;]+)\)} $line _ argfalse
+	    set condv [split $argconds ";"]
+	    set truev [split $argtrue ";"]
+	    set falsev [split $argfalse ";"]
+	    set ncases [llength $condv]
+
+	    for {set i 0} {$i < $ncases} {incr i} {
+		set summary [lindex $condv $i]
+		set n [lindex [split $summary "/"] 0]
+		set m [lindex [split $summary "/"] 1]
+		set newt [lindex $truev $i]
+		set newf [lindex $falsev $i]
+
+		# 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 {$m - $n}]
+		if {$nterms != $nexpected} {
+		    fail "$prefix: expected $nexpected uncovered terms; got $nterms"
+		    set ok 0
+		}
+		set shouldall $e
+		set should ""
+		set shouldt $newt
+		set shouldf $newf
+		set shouldall [regsub -all { } "$n/$m" ""]
+		lappend checks [list $should $shouldt $shouldf $shouldall $newt $newf]
+	    }
+
+	    if {[llength $checks] > 0} {
+		# no-op - the stack of checks to do is set up
+	    } elseif {$e == "end"} {
+		# no-op - state should already been reset, and errors flagged
+	    } elseif {$e == "suppress"} {
+		set suppress 1
+	    } else {
+		# this should be unreachable, 
+		fail "$prefix: unhandled control ($e), should be unreachable"
+		set ok 0
+	    }
+	} elseif {$suppress == 1} {
+	    # ignore everything in a suppress block. C++ especially can insert
+	    # conditionals in exceptions and destructors which would otherwise
+	    # be considered unhandled.
+	    continue
+	} elseif [regexp {condition +(\d+) not covered \((.*)\)} "$line" all cond condv] {
+	    foreach v {true false} {
+		if [regexp $v $condv] {
+		    if {"$v" == "true"} {
+			set should shouldt
+		    } else {
+			set should shouldf
+		    }
+
+		    set i [lsearch [set $should] $cond]
+		    if {$i != -1} {
+			set $should [lreplace [set $should] $i $i]
+		    } else {
+			fail "$prefix: unexpected uncovered term $cond ($v)"
+			set ok 0
+		    }
+		}
+	    }
+	} elseif [regexp {condition outcomes covered (\d+/\d+)} "$line" all cond] {
+	    # the destructor-generated "conditions covered" lines will be
+	    # written after all expression-related output. Handle these by
+	    # turning on suppression if the destructor-suppression is
+	    # requested.
+	    if {$shouldall == "" && $destructor == 1} {
+		set suppress 1
+		continue
+	    }
+
+	    if {[llength $checks] == 0} {
+		fail "$prefix: unexpected summary $cond"
+		set ok 0
+	    } else {
+		# Report any missing conditions from the previous set if this
+		# is not the first condition block
+		if {$setup == 1} {
+		    if {[llength $shouldt] != 0} {
+			fail "$prefix: expected 'not covered (true)' for terms: $shouldt"
+			set ok 0
+		    }
+		    if {[llength $shouldf] != 0} {
+			fail "$prefix: expected 'not covered (false)' for terms: $shouldf"
+			set ok 0
+		    }
+		    if {$shouldall ne ""} {
+			fail "$prefix: coverage summary not found; expected $shouldall"
+			set ok 0
+		    }
+		}
+		set setup 1
+		set current [lindex $checks 0]
+		set checks [lreplace $checks 0 0]
+		set should  [lindex $current 0]
+		set shouldt  [lindex $current 1]
+		set shouldf  [lindex $current 2]
+		set shouldall  [lindex $current 3]
+		set newt  [lindex $current 4]
+		set newf  [lindex $current 5]
+
+		if {$cond == $shouldall} {
+		    set shouldall ""
+		} else {
+		    fail "$prefix: unexpected summary - expected $shouldall, got $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 +567,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 +578,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 +654,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 +673,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-core.h b/gcc/tree-core.h
index 65e51b939a2..44b9fa10431 100644
--- a/gcc/tree-core.h
+++ b/gcc/tree-core.h
@@ -1582,6 +1582,9 @@ enum omp_clause_linear_kind
 struct GTY(()) tree_exp {
   struct tree_typed typed;
   location_t locus;
+  /* Discriminator for basic conditions in a Boolean expressions.  Trees that
+     are operands of the same Boolean expression should have the same uid.  */
+  unsigned condition_uid;
   tree GTY ((length ("TREE_OPERAND_LENGTH ((tree)&%h)"))) operands[1];
 };
 
diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
index 9c8fdb8b18f..f19dd3840e0 100644
--- a/gcc/tree-profile.cc
+++ b/gcc/tree-profile.cc
@@ -58,6 +58,7 @@ 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"
 
 static GTY(()) tree gcov_type_node;
 static GTY(()) tree tree_interval_profiler_fn;
@@ -108,6 +109,1054 @@ enum counter_update_method {
 
 static counter_update_method counter_update = COUNTER_UPDATE_SINGLE_THREAD;
 
+/* These functions support measuring modified conditition/decision coverage
+   (MC/DC).  MC/DC requires all of the below during testing:
+
+   - Each entry and exit point is invoked
+   - Each decision takes every possible outcome
+   - Each condition in a decision takes every possible outcome
+   - Each condition in a decision is shown to independently affect the outcome
+     of the decision
+
+   Independence of a condition is shown by proving that only one condition
+   changes at a time.  This feature adds some instrumentation code, a few
+   bitwise operators, that records the branches taken in conditions and applies
+   a filter for the masking effect.  Masking is essentially short-circuiting in
+   reverse: a condition does not contribute to the outcome if it would short
+   circuit the (sub) expression if it was evaluated right-to-left, (_ && false)
+   and (_ || true).
+
+   The program is essentially rewritten this way:
+
+   - if (a || b) { fn () }
+   + if (a) { _t |= 0x1; goto _then; }
+   + else   { _f |= 0x1;
+   +	if (b) { _t |= 0x2; _mask |= 0x1; goto _then; }
+   +	else   { _f |= 0x2; goto _else; }
+   + _then:
+   + _gcov_t |= (_t & _mask);
+   + _gcov_f |= (_f & _mask);
+   + fn (); goto _end;
+   + _else:
+   + _gcov_t |= (_t & _mask);
+   + _gcov_f |= (_f & _mask);
+   + fn ();
+   + _end:
+
+   It is assumed the front end will provide discrimnators so that conditional
+   basic blocks (basic block with a conditional jump and outgoing true/false
+   edges) that belong to the same Boolean expression have the same
+   discriminator.  Masking is determined by analyzing these expressions as a
+   reduced order binary decision diagram.  */
+namespace
+{
+/* Some context and reused instances between function calls.  Large embedded
+   buffers are used to up-front request enough memory for most programs and
+   merge them into a single allocation at the cost of using more memory in the
+   average case.  Some numbers from linux v5.13 which is assumed to be a
+   reasonably diverse code base: 75% of the functions in linux have less than
+   16 nodes in the CFG and approx 2.5% have more than 64 nodes.  The functions
+   that go beyond a few dozen nodes tend to be very large (>100) and so 64
+   seems like a good balance.
+
+   This is really just a performance balance of the cost of allocation and
+   wasted memory.  */
+struct conds_ctx
+{
+    /* This is both a reusable shared allocation which is also used to return
+       single expressions, which means it for most code should only hold a
+       couple of elements.  */
+    auto_vec<basic_block, 64> blocks;
+
+    /* Index for the topological order indexed by basic_block->index to an
+       ordering so that expression (a || b && c) => top_index[a] < top_index[b]
+       < top_index[c].  */
+    auto_vec<int, 256> top_index;
+
+    /* Pre-allocate bitmaps and vectors for per-function book keeping.  This is
+       pure instance reuse and the bitmaps carry no data between function
+       calls.  */
+    auto_vec<basic_block, 64> B1;
+    auto_vec<basic_block, 64> B2;
+    auto_sbitmap G1;
+    auto_sbitmap G2;
+    auto_sbitmap G3;
+
+    explicit conds_ctx (unsigned size) noexcept (true) : G1 (size), G2 (size),
+    G3 (size)
+    {
+    }
+};
+
+/* Only instrument terms with fewer than number of bits in a (wide) gcov
+   integer, which is probably 64.  The algorithm itself does not impose this
+   limitation, but it makes for a simpler implementation.
+
+   * Allocating the output data structure (coverage_counter_alloc ()) can
+     assume pairs of gcov_type_unsigned and not use a separate length field.
+   * A pair gcov_type_unsigned can be used as accumulators.
+   * Updating accumulators is can use the bitwise operations |=, &= and not
+     custom operators that work for arbitrary-sized bit-sets.
+
+   Most real-world code should be unaffected by this, but it is possible
+   (especially for generated code) to exceed this limit.  */
+#define CONDITIONS_MAX_TERMS (TYPE_PRECISION (gcov_type_node))
+#define EDGE_CONDITION (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)
+
+/* Compare two basic blocks by their order in the expression i.e. for (a || b)
+   then topological_cmp (a, b, ...) < 0.  The result is undefined if lhs, rhs
+   belong to different expressions.  The top_index argument should be the
+   top_index vector from ctx.  */
+int
+topological_cmp (const void *lhs, const void *rhs, void *top_index)
+{
+    const_basic_block l = *(const basic_block*) lhs;
+    const_basic_block r = *(const basic_block*) rhs;
+    const vec<int>* im = (const vec<int>*) top_index;
+    return (*im)[l->index] - (*im)[r->index];
+}
+
+/* Find the index of needle in blocks; return -1 if not found.  This has two
+   uses, sometimes for the index and sometimes for set member c hecks.  Sets are
+   typically very small (number of conditions, >8 is uncommon) so linear search
+   should be very fast.  */
+int
+index_of (const basic_block needle, array_slice<basic_block> blocks)
+{
+    for (size_t i = 0; i < blocks.size (); i++)
+	if (blocks[i] == needle)
+	    return int (i);
+    return -1;
+}
+
+/* Special cases of the single_*_p and single_*_edge functions in basic-block.h
+   that don't consider exception handling or other complex edges.  This helps
+   create a view of the CFG with only normal edges - if a basic block has both
+   an outgoing fallthrough and exceptional edge, it should be considered a
+   single-successor.  */
+bool
+single_p (const vec<edge, va_gc> *edges)
+{
+    int n = EDGE_COUNT (edges);
+    if (n == 0)
+	return false;
+
+    for (edge e : edges)
+	if (e->flags & EDGE_COMPLEX)
+	    n -= 1;
+
+    return n == 1;
+}
+
+/* Get the single, non-complex edge.  Behavior is undefined edges have more
+   than 1 non-complex edges.  */
+edge
+single_edge (const vec<edge, va_gc> *edges)
+{
+    gcc_checking_assert (single_p (edges));
+    for (edge e : edges)
+    {
+	if (e->flags & EDGE_COMPLEX)
+	    continue;
+	return e;
+    }
+    return NULL;
+}
+
+/* Sometimes, for example with function calls, goto labels, 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
+
+   This function finds the source edge of these paths.  This is often the
+   identity function.  */
+edge
+contract_edge_up (edge e)
+{
+    while (true)
+    {
+	basic_block src = e->src;
+	if (!single_p (src->preds))
+	    return e;
+	if (!single_p (src->succs))
+	    return e;
+	e = single_edge (src->preds);
+    }
+}
+
+/* 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;
+}
+
+/* Returns the condition identifier for the basic block if set, otherwise 0.
+   This is only meaningful in GIMPLE and is used for condition coverage.
+
+   There may be conditions created that did not get an uid, such as those
+   implicitly created by destructors.  We could include them in the condition
+   coverage for completeness (i.e. condition coverage implies (implicit) branch
+   coverage), but they have no natural buckets and should all be single-term.
+   For now these are ignored and given uid = 0, and branch coverage is left to
+   -fprofile-arcs.
+
+   Under optimization, COND_EXPRs may be folded, replaced with switches,
+   min-max, etc., which leaves ghost identifiers in basic blocks that do not
+   end with a conditional jump.  They are not really meaningful for condition
+   coverage anymore, but since coverage is unreliable under optimization anyway
+   this is not a big problem.  */
+unsigned
+condition_uid (struct function *fn, basic_block b)
+{
+    gimple *stmt = gsi_stmt (gsi_last_bb (b));
+    if (!safe_is_a<gcond *> (stmt))
+	return 0;
+
+    unsigned *v = fn->cond_uids->get (as_a <gcond*> (stmt));
+    return v ? *v : 0;
+}
+
+/* Compute the masking vector.
+
+   Masking and short circuiting are deeply connected - masking occurs when
+   control flow reaches a state that is also reachable with short circuiting.
+   In fact, masking corresponds to short circuiting for the reversed
+   expression.  This means we can find the limits, the last term in preceeding
+   subexpressions, by following the edges that short circuit to the same
+   outcome.  The algorithm treats the CFG as a reduced order binary decision
+   diagram (see Randall E. Bryant's Graph Based Algorithms for Boolean
+   Function Manipulation (1987)).
+
+   In the simplest case a || b:
+
+   a
+   |\
+   | b
+   |/ \
+   T   F
+
+   T has has multiple incoming edges and is the outcome of a short circuit,
+   with top = a, bot = b.  The top node (a) is masked when the edge (b, T) is
+   taken.
+
+   The names "top" and "bot" refer to a pair of nodes with a shared
+   successor.  The top is always the node corresponding to the left-most
+   operand of the two, and it holds that top < bot in a topological ordering.
+
+   Now consider (a && b) || (c && d) and its masking vectors:
+
+   a
+   |\
+   b \
+   |\|
+   | c
+   | |\
+   | d \
+   |/ \|
+   T   F
+
+   a[0] = {}
+   a[1] = {}
+   b[0] = {a}
+   b[1] = {}
+   c[0] = {}
+   c[1] = {}
+   d[0] = {c}
+   d[1] = {a,b}
+
+   Note that 0 and 1 are indices and not boolean values - a[0] is the index in
+   the masking vector when a takes the true edge.
+
+   b[0] and d[0] are identical to the a || b example, and d[1] is the bot in
+   the triangle [d, b] -> T.  b is the top node in the [d, b] relationship and
+   last term in (a && b).  To find the other terms masked we use the fact that
+   all paths in an expression go through either of the outcomes, found by
+   collecting all non-complex edges that go out of the expression (the
+   neighborhood).  In some cases the outgoing edge go through intermediate (or
+   bypass) nodes, and we collect these paths too (see contract_edge_up).
+
+   We find the terms by marking the outcomes (in this case c, T) and walk the
+   predecessors starting at top (in this case b) and masking nodes when both
+   successors are marked.
+
+   The masking vector is represented as two bitfields per term in the
+   expression with the index corresponding to the term in the source
+   expression.  a || b && c becomes the term vector [a b c] and the masking
+   vectors [a[0] a[1] b[0] ...].  The kth bit of a masking vector is set if the
+   the kth term is masked by taking the edge.
+
+   The out masks are in uint64_t (the practical maximum for gcov_type_node for
+   any target) as it has to be big enough to store the target size gcov types
+   independent of the host.  */
+void
+masking_vectors (conds_ctx& ctx, array_slice<basic_block> blocks,
+		 array_slice<sbitmap> maps, array_slice<uint64_t> masks)
+{
+    gcc_assert (blocks.is_valid ());
+    gcc_assert (!blocks.empty ());
+    gcc_assert (maps.is_valid ());
+    gcc_assert (masks.is_valid ());
+    gcc_assert (sizeof (masks[0]) * BITS_PER_UNIT >= CONDITIONS_MAX_TERMS);
+
+    if (bitmap_count_bits (maps[0]) == 1)
+	return;
+
+    sbitmap marks = ctx.G1;
+    const sbitmap core = maps[0];
+    const sbitmap allg = maps[1];
+    vec<basic_block>& queue = ctx.B1;
+    vec<basic_block>& body = ctx.B2;
+    const vec<int>& top_index = ctx.top_index;
+
+    /* Set up for the iteration - include the outcome nodes in the traversal.
+       The algorithm compares pairs of nodes and is not really sensitive to
+       traversal order, but need to maintain topological order because the
+       index of masking nodes maps to the index in the accumulators.  We must
+       also check the incoming-to-outcome pairs.  These edges may in turn be
+       split (this happens with labels on top of then/else blocks) so we must
+       follow any single-in single-out path.  The non-condition blocks do not
+       have to be in order as they are non-condition blocks and will not be
+       considered for the set-bit index.  */
+    body.truncate (0);
+    body.reserve (blocks.size () + 2);
+    for (const basic_block b : blocks)
+	if (bitmap_bit_p (core, b->index))
+	    body.quick_push (b);
+
+    for (basic_block b : blocks)
+    {
+	if (!bitmap_bit_p (core, b->index))
+	    continue;
+
+	for (edge e : b->succs)
+	{
+	    if (e->flags & EDGE_COMPLEX)
+		continue;
+	    if (bitmap_bit_p (allg, e->dest->index))
+		continue;
+	    body.safe_push (e->dest);
+
+	    /* There may be multiple nodes between the condition edge and the
+	       actual outcome, and we need to know when these paths join to
+	       determine if there is short circuit/masking.  This is
+	       effectively creating a virtual edge from the condition node to
+	       the real outcome.  */
+	    while (!(e->flags & EDGE_DFS_BACK) && single_p (e->dest->succs))
+	    {
+		e = single_edge (e->dest->succs);
+		body.safe_push (e->dest);
+	    }
+	}
+    }
+
+    /* Find the masking.  The leftmost element cannot mask anything, so
+       start at 1.  */
+    for (size_t i = 1; i != body.length (); i++)
+    {
+	const basic_block b = body[i];
+	for (edge e1 : b->preds)
+	for (edge e2 : b->preds)
+	{
+	    if (e1 == e2)
+		continue;
+	    if ((e1->flags | e2->flags) & EDGE_COMPLEX)
+		continue;
+
+	    edge etop = contract_edge_up (e1);
+	    edge ebot = contract_edge_up (e2);
+	    gcc_assert (etop != ebot);
+
+	    const basic_block top = etop->src;
+	    const basic_block bot = ebot->src;
+	    const unsigned cond = etop->flags & ebot->flags & EDGE_CONDITION;
+	    if (!cond)
+		continue;
+	    if (top_index[top->index] > top_index[bot->index])
+		continue;
+	    if (!bitmap_bit_p (core, top->index))
+		continue;
+	    if (!bitmap_bit_p (core, bot->index))
+		continue;
+
+	    outcomes out = conditional_succs (top);
+	    gcc_assert (out);
+	    bitmap_clear (marks);
+	    bitmap_set_bit (marks, out.t->index);
+	    bitmap_set_bit (marks, out.f->index);
+	    queue.truncate (0);
+	    queue.safe_push (top);
+
+	    // The edge bot -> outcome triggers the masking
+	    const int m = 2*index_of (bot, body) + condition_index (cond);
+	    gcc_assert (m >= 0);
+	    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, body);
+		gcc_assert (index != -1);
+		masks[m] |= uint64_t (1) << index;
+		bitmap_set_bit (marks, q->index);
+
+		for (edge e : q->preds)
+		{
+		    e = contract_edge_up (e);
+		    if (e->flags & EDGE_DFS_BACK)
+			continue;
+		    if (bitmap_bit_p (marks, e->src->index))
+			continue;
+		    if (!bitmap_bit_p (core, e->src->index))
+			continue;
+		    queue.safe_push (e->src);
+		}
+	    }
+	}
+    }
+}
+
+/* Emit <lhs> = <rhs> on edges.  This is just a short hand that automates the
+   building of the assign and immediately puts it on the edge, which becomes
+   noisy.  */
+tree
+emit_assign (edge e, tree lhs, tree rhs)
+{
+    gassign *w = gimple_build_assign (lhs, rhs);
+    gsi_insert_on_edge (e, w);
+    return lhs;
+}
+
+/* Emit lhs = <rhs> on edges.  */
+tree
+emit_assign (edge e, tree rhs)
+{
+    return emit_assign (e, make_ssa_name (gcov_type_node), rhs);
+}
+
+/* Emit lhs = op1 <op> op2 on edges.  */
+tree
+emit_bitwise_op (edge e, tree op1, tree_code op, tree op2 = NULL_TREE)
+{
+    tree lhs = make_ssa_name (gcov_type_node);
+    gassign *w = gimple_build_assign (lhs, op, op1, op2);
+    gsi_insert_on_edge (e, w);
+    return lhs;
+}
+
+/* Visitor for make_top_index.  */
+void
+make_top_index_visit (basic_block b, vec<basic_block>& L, vec<int>& marks)
+{
+    if (marks[b->index])
+	return;
+
+    /* Follow the false edge first, if it exists, so that true paths are given
+       the lower index in the ordering.  Any iteration order
+       would yield a valid and useful topological ordering, but making sure the
+       true branch has the lower index first makes reporting work better for
+       expressions with ternaries.  Walk the false branch first because the
+       array will be reversed to finalize the topological order.
+
+       With the wrong ordering (a ? b : c) && d could become [a c b d], but the
+       (expected) order is really [a b c d].  */
+
+    const unsigned false_fwd = EDGE_DFS_BACK | EDGE_FALSE_VALUE;
+    for (edge e : b->succs)
+	if ((e->flags & false_fwd) == EDGE_FALSE_VALUE)
+	    make_top_index_visit (e->dest, L, marks);
+
+    for (edge e : b->succs)
+	if (!(e->flags & false_fwd))
+	    make_top_index_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).  The L argument is a buffer/working
+   memory, and the output will be written to top_index.
+
+   For the expression (a || (b && c) || d) the blocks should be [a b c d].  */
+void
+make_top_index (array_slice<basic_block> blocks, vec<basic_block>& L,
+		vec<int>& top_index)
+{
+    L.truncate (0);
+    L.reserve (blocks.size ());
+
+    /* Use of the output map as a temporary for tracking visited status.  */
+    top_index.truncate (0);
+    top_index.safe_grow_cleared (blocks.size ());
+    for (const basic_block b : blocks)
+	make_top_index_visit (b, L, top_index);
+
+    /* 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 != top_index.length (); i++)
+	top_index[i] = -1;
+
+    gcc_assert (blocks.size () == L.length ());
+    L.reverse ();
+    const unsigned nblocks = L.length ();
+    for (unsigned i = 0; i != nblocks; i++)
+    {
+	gcc_assert (L[i]->index != -1);
+	top_index[L[i]->index] = int (i);
+    }
+}
+
+/* Find all nodes including non-conditions in a Boolean expression.  We need to
+   know the paths through the expression so that the masking and
+   instrumentation phases can limit searches and know what subgraphs must be
+   threaded through, but not counted, such as the (b || c) in
+   a && fn (b || c) && d.
+
+   It is essentially the intersection of downwards paths from the expression
+   nodices to the post-dominator and upwards from the post-dominator.  Finding
+   the dominator is slightly more involved than picking the first/last,
+   particularly under optimization, because both incoming and outgoing paths
+   may have multiple entries/exits.
+
+   It is assumed the graph is an array_slice to the basic blocks of this
+   function sorted by the basic block index.  */
+vec<basic_block>&
+paths_between (conds_ctx &ctx, array_slice<basic_block> graph,
+	       const vec<basic_block>& expr)
+{
+    if (expr.length () == 1)
+    {
+	ctx.blocks.truncate (0);
+	ctx.blocks.safe_push (expr[0]);
+	return ctx.blocks;
+    }
+
+    basic_block dom;
+    sbitmap up = ctx.G1;
+    sbitmap down = ctx.G2;
+    sbitmap paths = ctx.G3;
+    vec<basic_block>& queue = ctx.B1;
+
+    queue.truncate (0);
+    bitmap_clear (down);
+    dom = get_immediate_dominator (CDI_POST_DOMINATORS, expr[0]);
+    for (basic_block b : expr)
+	if (dom != b)
+	    dom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, b);
+    queue.safe_splice (expr);
+    while (!queue.is_empty ())
+    {
+	basic_block b = queue.pop ();
+	if (!bitmap_set_bit (down, b->index))
+	    continue;
+	if (b == dom)
+	    continue;
+	for (edge e : b->succs)
+	    if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK)))
+		queue.safe_push (e->dest);
+    }
+
+    queue.truncate (0);
+    bitmap_clear (up);
+    dom = expr[0];
+    for (basic_block b : expr)
+	if (dom != b)
+	    dom = nearest_common_dominator (CDI_DOMINATORS, dom, b);
+    queue.safe_splice (expr);
+    while (!queue.is_empty ())
+    {
+	basic_block b = queue.pop ();
+	if (!bitmap_set_bit (up, b->index))
+	    continue;
+	if (b == dom)
+	    continue;
+	for (edge e : b->preds)
+	    if (!(e->flags & (EDGE_COMPLEX | EDGE_DFS_BACK)))
+		queue.safe_push (e->src);
+    }
+
+    bitmap_and (paths, up, down);
+    vec<basic_block>& blocks = ctx.blocks;
+    blocks.truncate (0);
+    blocks.reserve (graph.size ());
+    sbitmap_iterator itr;
+    unsigned index;
+    EXECUTE_IF_SET_IN_BITMAP (paths, 0, index, itr)
+	blocks.quick_push (graph[index]);
+    return blocks;
+}
+
+}
+
+/* Context object for the condition coverage.  This stores conds_ctx (the
+   buffers reused when analyzing the cfg) and the output arrays.  This is
+   designed to be heap allocated and aggressively preallocates large buffers to
+   avoid having to reallocate for most programs.  */
+struct condcov
+{
+    explicit condcov (unsigned nblocks) noexcept (true) : ctx (nblocks),
+    m_maps (sbitmap_vector_alloc (2 * nblocks, nblocks))
+    {
+	bitmap_vector_clear (m_maps, 2 * nblocks);
+    }
+    auto_vec<size_t, 128> m_index;
+    auto_vec<basic_block, 256> m_blocks;
+    auto_vec<uint64_t, 512> m_masks;
+    conds_ctx ctx;
+    sbitmap *m_maps;
+};
+
+/* Get the length, that is the number of Boolean expression found.  cov_length
+   is the one-past index for cov_{blocks,masks,maps}.  */
+size_t
+cov_length (const struct condcov* cov)
+{
+    if (cov->m_index.is_empty ())
+	return 0;
+    return cov->m_index.length () - 1;
+}
+
+/* The subgraph, exluding intermediates, for the nth Boolean expression.  */
+array_slice<basic_block>
+cov_blocks (struct condcov* cov, size_t n)
+{
+    if (n >= cov->m_index.length ())
+	return array_slice<basic_block>::invalid ();
+
+    basic_block *begin = cov->m_blocks.begin () + cov->m_index[n];
+    basic_block *end = cov->m_blocks.begin () + cov->m_index[n + 1];
+    return array_slice<basic_block> (begin, end - begin);
+}
+
+/* The masks for the nth Boolean expression.  */
+array_slice<uint64_t>
+cov_masks (struct condcov* cov, size_t n)
+{
+    if (n >= cov->m_index.length ())
+	return array_slice<uint64_t>::invalid ();
+
+    uint64_t *begin = cov->m_masks.begin () + 2*cov->m_index[n];
+    uint64_t *end = cov->m_masks.begin () + 2*cov->m_index[n + 1];
+    return array_slice<uint64_t> (begin, end - begin);
+}
+
+/* The maps for the nth Boolean expression.  */
+array_slice<sbitmap>
+cov_maps (struct condcov* cov, size_t n)
+{
+    if (n >= cov->m_index.length ())
+	return array_slice<sbitmap>::invalid ();
+
+    sbitmap *begin = cov->m_maps + 2*n;
+    sbitmap *end = begin + 2;
+    return array_slice<sbitmap> (begin, end - begin);
+}
+
+/* Deleter for condcov.  */
+void
+cov_free (struct condcov* cov)
+{
+    sbitmap_vector_free (cov->m_maps);
+    delete cov;
+}
+
+/* Condition coverage (MC/DC)
+
+   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 does analyzes the control flow graph
+   (interpreted as a binary decision diagram) to determine the masking vectors.
+   The individual phases are described in more detail closer to the
+   implementation.
+
+   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].  Functions whose
+   arguments are Boolean expressions are treated as separate expressions, that
+   is, a && fn (b || c) && d is treated as [a _fn d] and [b c], not [a b c d].
+
+   The output for gcov is a vector of pairs of unsigned integers, interpreted
+   as bit-sets, where the bit index corresponds to the index of the condition
+   in the expression.
+
+   The returned condcov should be released by the caller with cov_free.  */
+struct condcov*
+find_conditions (struct function *fn)
+{
+    mark_dfs_back_edges (fn);
+    const bool have_dom = dom_info_available_p (fn, CDI_DOMINATORS);
+    const bool have_post_dom = dom_info_available_p (fn, CDI_POST_DOMINATORS);
+    if (!have_dom)
+	calculate_dominance_info (CDI_DOMINATORS);
+    if (!have_post_dom)
+	calculate_dominance_info (CDI_POST_DOMINATORS);
+
+    const unsigned nblocks = n_basic_blocks_for_fn (fn);
+    basic_block *fnblocksp = basic_block_info_for_fn (fn)->address ();
+    condcov *cov = new condcov (nblocks);
+    conds_ctx& ctx = cov->ctx;
+    array_slice<basic_block> fnblocks (fnblocksp, nblocks);
+    make_top_index (fnblocks, ctx.B1, ctx.top_index);
+
+    /* Bin the Boolean expressions so that exprs[id] -> [x1, x2, ...].  */
+    hash_map<int_hash<unsigned, 0>, vec<basic_block>> exprs;
+    for (basic_block b : fnblocks)
+    {
+	const unsigned uid = condition_uid (fn, b);
+	if (uid == 0)
+	    continue;
+	exprs.get_or_insert (uid).safe_push (b);
+    }
+
+    /* Visit all reachable nodes and collect conditions.  Topological order is
+       important so the first node of a boolean expression is visited first
+       (it will mark subsequent terms).  */
+    cov->m_index.safe_push (0);
+    for (auto expr : exprs)
+    {
+	vec<basic_block>& conds = expr.second;
+	if (conds.length () > CONDITIONS_MAX_TERMS)
+	{
+	    location_t loc = gimple_location (gsi_stmt (gsi_last_bb (conds[0])));
+	    warning_at (loc, OPT_Wcoverage_too_many_conditions,
+			"Too many conditions (found %u); giving up coverage",
+			conds.length ());
+	    continue;
+	}
+	conds.sort (topological_cmp, &ctx.top_index);
+	vec<basic_block>& subgraph = paths_between (ctx, fnblocks, conds);
+	subgraph.sort (topological_cmp, &ctx.top_index);
+	const unsigned index = cov->m_index.length () - 1;
+	sbitmap condm = cov->m_maps[0 + 2*index];
+	sbitmap subgm = cov->m_maps[1 + 2*index];
+	for (basic_block b : conds)
+	    bitmap_set_bit (condm, b->index);
+	for (basic_block b : subgraph)
+	    bitmap_set_bit (subgm, b->index);
+	cov->m_blocks.safe_splice (subgraph);
+	cov->m_index.safe_push (cov->m_blocks.length ());
+    }
+
+    if (!have_dom)
+	free_dominance_info (fn, CDI_DOMINATORS);
+    if (!have_post_dom)
+	free_dominance_info (fn, CDI_POST_DOMINATORS);
+
+    cov->m_masks.safe_grow_cleared (2 * cov->m_index.last ());
+    const size_t length = cov_length (cov);
+    for (size_t i = 0; i != length; i++)
+	masking_vectors (ctx, cov_blocks (cov, i), cov_maps (cov, i),
+			 cov_masks (cov, i));
+
+    return cov;
+}
+
+namespace
+{
+
+/* Stores the incoming edge and previous counters (in SSA form) on that edge
+   for the node e->deston that edge for the node e->dest.  The counters record
+   the seen-true (0), seen-false (1), and current-mask (2).  They are stored in
+   an array rather than proper members for access-by-index as the code paths
+   tend to be identical for the different counters.  */
+struct counters
+{
+    edge e;
+    tree counter[3];
+    tree& operator [] (size_t i) { return counter[i]; }
+};
+
+/* Find the counters for the incoming edge, or null if the edge has not been
+   recorded (could be for complex incoming edges).  */
+counters*
+find_counters (vec<counters>& candidates, edge e)
+{
+    for (counters& candidate : candidates)
+	if (candidate.e == e)
+	    return &candidate;
+    return NULL;
+}
+
+/* Resolve the SSA for a specific counter.  If it is not modified by any
+   incoming edges, simply forward it, otherwise create a phi node of all the
+   candidate counters and return it.  */
+tree
+resolve_counter (vec<counters>& cands, size_t kind)
+{
+    gcc_assert (!cands.is_empty ());
+    gcc_assert (kind < 3);
+
+    counters& fst = cands[0];
+
+    if (!fst.e || fst.e->dest->preds->length () == 1)
+    {
+	gcc_assert (cands.length () == 1);
+	return fst[kind];
+    }
+
+    tree zero0 = build_int_cst (gcov_type_node, 0);
+    tree ssa = make_ssa_name (gcov_type_node);
+    gphi *phi = create_phi_node (ssa, fst.e->dest);
+    for (edge e : fst.e->dest->preds)
+    {
+	counters *prev = find_counters (cands, e);
+	if (prev)
+	    add_phi_arg (phi, (*prev)[kind], e, UNKNOWN_LOCATION);
+	else
+	{
+	    tree zero = make_ssa_name (gcov_type_node);
+	    gimple_stmt_iterator gsi = gsi_after_labels (e->src);
+	    gassign *set = gimple_build_assign (zero, zero0);
+	    gsi_insert_before (&gsi, set, GSI_NEW_STMT);
+	    add_phi_arg (phi, zero, e, UNKNOWN_LOCATION);
+	}
+    }
+    return ssa;
+}
+
+/* Resolve all the counters for a node.  Note that the edge is undefined, as
+   the counters are intended to form the base to push to the successors, and
+   because the is only meaningful for nodes with a single predecessor.  */
+counters
+resolve_counters (vec<counters>& cands)
+{
+    counters next;
+    next[0] = resolve_counter (cands, 0);
+    next[1] = resolve_counter (cands, 1);
+    next[2] = resolve_counter (cands, 2);
+    return next;
+}
+
+}
+
+/* Add instrumentation to a decision subgraph.  expr should be the
+   (topologically sorted) block of nodes returned by cov_blocks, maps the
+   bitmaps returned by cov_maps, and masks the block of bitsets returned by
+   cov_masks.  condno should be the index of this condition in the function,
+   i.e. the same argument given to cov_{masks,graphs}.  expr may contain nodes
+   in-between the conditions, e.g.  when an operand contains a function call,
+   or there is a setjmp and the cfg is filled with complex edges.
+
+   Every node is annotated with three counters; the true, false, and mask
+   value.  First, walk the graph and determine what if there are multiple
+   possible values for either accumulator depending on the path taken, in which
+   case a phi node is created and registered as the accumulator.  Then, those
+   values are pushed as accumulators to the immediate successors.  For some
+   very particular programs there may be multiple paths into the expression
+   (e.g. when prior terms are determined by a surrounding conditional) in which
+   case the default zero-counter is pushed, otherwise all predecessors will
+   have been considered before the successor because of topologically ordered
+   traversal.  Finally, expr is traversed again to look for edges to the
+   outcomes, that is, edges with a destination outside of expr, and the local
+   accumulators are flushed to the global gcov counters on these edges.  In
+   some cases there are edge splits that cause 3+ edges to the two outcome
+   nodes.
+
+   If a complex edge is taken (e.g. on a longjmp) the accumulators are
+   attempted poisoned so that there would be no change to the global counters,
+   but this has proven unreliable in the presence of undefined behavior, see
+   the setjmp003 test.
+
+   It is important that the flushes happen on the basic condition outgoing
+   edge, otherwise flushes could be lost to exception handling or other
+   abnormal control flow.  */
+size_t
+instrument_decisions (array_slice<basic_block> expr, size_t condno,
+		      array_slice<sbitmap> maps, array_slice<uint64_t> masks)
+{
+    tree zero = build_int_cst (gcov_type_node, 0);
+    tree poison = build_int_cst (gcov_type_node, ~0ULL);
+    const sbitmap core = maps[0];
+    const sbitmap allg = maps[1];
+
+    hash_map<basic_block, vec<counters>> table;
+    counters zerocounter;
+    zerocounter.e = NULL;
+    zerocounter[0] = zero;
+    zerocounter[1] = zero;
+    zerocounter[2] = zero;
+
+    unsigned xi = 0;
+    tree rhs = build_int_cst (gcov_type_node, 1ULL << xi);
+    for (basic_block current : expr)
+    {
+	vec<counters>& candidates = table.get_or_insert (current);
+	if (candidates.is_empty ())
+	    candidates.safe_push (zerocounter);
+	counters prev = resolve_counters (candidates);
+
+	int increment = 0;
+	for (edge e : current->succs)
+	{
+	    counters next = prev;
+	    next.e = e;
+
+	    if (bitmap_bit_p (core, e->src->index) && (e->flags & EDGE_CONDITION))
+	    {
+		const int k = condition_index (e->flags);
+		next[k] = emit_bitwise_op (e, prev[k], BIT_IOR_EXPR, rhs);
+		if (masks[2*xi + k])
+		{
+		    tree m = build_int_cst (gcov_type_node, masks[2*xi + k]);
+		    next[2] = emit_bitwise_op (e, prev[2], BIT_IOR_EXPR, m);
+		}
+		increment = 1;
+	    }
+	    else if (e->flags & EDGE_COMPLEX)
+	    {
+		/* A complex edge has been taken - wipe the accumulators and
+		   poison the mask so that this path does not contribute to
+		   coverage.  */
+		next[0] = poison;
+		next[1] = poison;
+		next[2] = poison;
+	    }
+	    table.get_or_insert (e->dest).safe_push (next);
+	}
+	xi += increment;
+	if (increment)
+	    rhs = build_int_cst (gcov_type_node, 1ULL << xi);
+    }
+
+    gcc_assert (xi == bitmap_count_bits (core));
+
+    const tree relaxed = build_int_cst (integer_type_node, MEMMODEL_RELAXED);
+    const bool atomic = flag_profile_update == PROFILE_UPDATE_ATOMIC;
+    const tree atomic_ior = builtin_decl_explicit
+	(TYPE_PRECISION (gcov_type_node) > 32
+	 ? BUILT_IN_ATOMIC_FETCH_OR_8
+	 : BUILT_IN_ATOMIC_FETCH_OR_4);
+
+    /* Flush to the gcov accumulators.  */
+    for (const basic_block b : expr)
+    {
+	if (!bitmap_bit_p (core, b->index))
+	    continue;
+
+	for (edge e : b->succs)
+	{
+	    /* Flush the accumulators on leaving the Boolean function.  The
+	       destination may be inside the function only when it returns to
+	       the loop header, such as do { ... } while (x);  */
+	    if (bitmap_bit_p (allg, e->dest->index)) {
+		if (!(e->flags & EDGE_DFS_BACK))
+		    continue;
+		if (e->dest != expr[0])
+		    continue;
+	    }
+
+	    vec<counters> *cands = table.get (e->dest);
+	    gcc_assert (cands);
+	    counters *prevp = find_counters (*cands, e);
+	    gcc_assert (prevp);
+	    counters prev = *prevp;
+
+	    /* _true &= ~mask, _false &= ~mask  */
+	    counters next;
+	    next[2] = emit_bitwise_op (e, prev[2], BIT_NOT_EXPR);
+	    next[0] = emit_bitwise_op (e, prev[0], BIT_AND_EXPR, next[2]);
+	    next[1] = emit_bitwise_op (e, prev[1], BIT_AND_EXPR, next[2]);
+
+	    /* _global_true |= _true, _global_false |= _false  */
+	    for (size_t k = 0; k != 2; ++k)
+	    {
+		tree ref = tree_coverage_counter_ref (GCOV_COUNTER_CONDS,
+						      2*condno + k);
+		if (atomic)
+		{
+		    ref = unshare_expr (ref);
+		    gcall *flush = gimple_build_call (atomic_ior, 3,
+						      build_addr (ref),
+						      next[k], relaxed);
+		    gsi_insert_on_edge (e, flush);
+		}
+		else
+		{
+		    tree get = emit_assign (e, ref);
+		    tree put = emit_bitwise_op (e, next[k], BIT_IOR_EXPR, get);
+		    emit_assign (e, unshare_expr (ref), put);
+		}
+	    }
+	}
+    }
+
+    return xi;
+}
+
+#undef CONDITIONS_MAX_TERMS
+#undef EDGE_CONDITION
+
 /* Do initialization work for the edge profiler.  */
 
 /* Add code:
@@ -837,7 +1886,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 || condition_coverage_flag)
 	    expand_thunk (node, false, true);
 	  /* Read cgraph profile but keep function as thunk at profile-use
 	     time.  */
@@ -882,7 +1931,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 || condition_coverage_flag || flag_test_coverage)
     FOR_EACH_DEFINED_FUNCTION (node)
       {
 	if (!gimple_has_body_p (node->decl)
@@ -914,7 +1963,7 @@ tree_profiling (void)
 
       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
 
-      if (profile_arc_flag || flag_test_coverage)
+      if (profile_arc_flag || condition_coverage_flag || flag_test_coverage)
 	FOR_EACH_BB_FN (bb, cfun)
 	  {
 	    gimple_stmt_iterator gsi;
@@ -999,7 +2048,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 || condition_coverage_flag));
 }
 
 } // anon namespace
diff --git a/gcc/tree.h b/gcc/tree.h
index 086b55f0375..f4186a72b5c 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1358,6 +1358,10 @@ class auto_suppress_location_wrappers
   ~auto_suppress_location_wrappers () { --suppress_location_wrappers; }
 };
 
+/* COND_EXPR identificer/discriminator accessors.  */
+#define SET_EXPR_UID(t, v) EXPR_CHECK ((t))->exp.condition_uid = (v)
+#define EXPR_COND_UID(t) EXPR_CHECK ((t))->exp.condition_uid
+
 /* In a TARGET_EXPR node.  */
 #define TARGET_EXPR_SLOT(NODE) TREE_OPERAND_CHECK_CODE (NODE, TARGET_EXPR, 0)
 #define TARGET_EXPR_INITIAL(NODE) TREE_OPERAND_CHECK_CODE (NODE, TARGET_EXPR, 1)
diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
index 5d6e17d1483..eed3556373b 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters  __attribute__ ((unused)),
                        unsigned n_counters __attribute__ ((unused))) {}
 #endif
 
+#ifdef L_gcov_merge_ior
+void __gcov_merge_ior (gcov_type *counters  __attribute__ ((unused)),
+		       unsigned n_counters __attribute__ ((unused))) {}
+#endif
+
 #ifdef L_gcov_merge_topn
 void __gcov_merge_topn (gcov_type *counters  __attribute__ ((unused)),
 			unsigned n_counters __attribute__ ((unused))) {}
-- 
2.30.2



More information about the Gcc-patches mailing list