[17/22] Mark contracted-past nodes in reachable

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..c4afc5e700d
--- /dev/null
+++ b/gcc/testsuite/gcc.misc-tests/gcov-23.c
@@ -0,0 +1,75 @@ 
+/* { dg-options "-fprofile-conditions -ftest-coverage -O2 -c" } */
+
+int id (int);
+int idp (int *);
+int err;
+
+/* This becomes problematic only under optimization for the case when the
+   compiler cannot inline the function but have to generate a call.  It is not
+   really interesting to run, only see if it builds.  Notably, both the
+   function calls and the return values are important to construct a
+   problematic graph.
+
+   This test is also a good example of where optimization makes condition
+   coverage unpredictable, but not unusable.  If this is built without
+   optimization the conditions work as you would expect from reading the
+   source.  */
+/* Adapted from cpio-2.14 gnu/utmens.c lutimens ().  */
+int
+mcdc001 (int *v)
+{
+    int adjusted;
+    int adjustment_needed = 0;
+
+    int *ts = v ? &adjusted : 0; /* conditions(0/4) true(0 1) false(0 1) */
+				 /* conditions(end) */
+    if (ts)
+	adjustment_needed = idp (ts);
+    if (adjustment_needed < 0)
+	return -1;
+
+    if (adjustment_needed)  /* conditions(0/2) true(0) false(0) */
+			    /* conditions(end) */
+    {
+	if (adjustment_needed != 3) /* conditions(0/2) true(0) false(0) */
+				    /* conditions(end) */
+	    return -1;
+	if (ts) /* conditions(0/2) true(0) false(0) */
+		/* conditions(end) */
+	    return 0;
+    }
+
+    if (adjustment_needed && idp (&adjusted)) /* conditions(0/2) true(0) false(0) */
+					      /* conditions(end) */
+	return -1;
+    if (adjusted)   /* conditions(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	return idp (ts);
+
+    return -1;
+}
+
+/* This failed when the candidate set internal/contracted-past nodes were not
+   properly marked as reachable in the candidate reduction phase.  */
+/* Adapted from cpio-2.14 gnu/mktime.c mktime_internal ().  */
+int
+mcdc002 ()
+{
+    int a;
+    if (idp (&a)) /* conditions(0/2) true(0) false(0) */
+		  /* conditions(end) */
+    {
+	if (id (a)) /* conditions(0/2) true(0/2) true(0) false(0) */
+		    /* conditions(end) */
+	    goto exit;
+
+	if (err) /* conditions(0/2) true(0/2) true(0) false(0) */
+		 /* conditions(end) */
+	    return -1;
+    }
+
+exit:
+    return a;
+}
+
+/* { dg-final { run-gcov conditions { --conditions gcov-23.c } } } */
diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
index 98593f53862..26e1924d444 100644
--- a/gcc/tree-profile.cc
+++ b/gcc/tree-profile.cc
@@ -279,23 +279,27 @@  single_edge (const vec<edge, va_gc> *edges)
    merged.
 
    Only chains of single-exit single-entry nodes that end with a condition
-   should be contracted.  */
+   should be contracted.  If the optional bitset G is passed, the intermediate
+   "contracted-past" nodes will be recorded, which is only meaningful if the
+   non-source edge is returned.  */
 edge
-contract_edge (edge e)
+contract_edge (edge e, sbitmap G = nullptr)
 {
     edge source = e;
     while (true)
     {
 	basic_block dest = e->dest;
-	if (!single (dest->preds))
-	    return source;
 	if (e->flags & EDGE_DFS_BACK)
 	    return source;
-	if (block_conditional_p (dest))
-	    return e;
 	if (dest->index == EXIT_BLOCK)
 	    return source;
+	if (!single (dest->preds))
+	    return source;
+	if (block_conditional_p (dest))
+	    return e;
 
+	if (G)
+	    bitmap_set_bit (G, dest->index);
 	e = single_edge (dest->succs);
 	if (!e)
 	    return source;
@@ -673,6 +677,8 @@  cond_reachable_from (basic_block p, basic_block q, sbitmap expr,
 	    if (!all_preds_conditional_p (dest, expr))
 		continue;
 
+	    if (dest != e->dest)
+		contract_edge (e, expr);
 	    bitmap_set_bit (expr, dest->index);
 	    out.safe_push (dest);
 	}
@@ -692,8 +698,14 @@  neighborhood (const vec<basic_block>& blocks, sbitmap G, vec<basic_block>& out)
 	    basic_block dest = contract_edge (e)->dest;
 	    if (bitmap_bit_p (G, dest->index))
 		continue;
-	    if (!out.contains (dest))
-		out.safe_push (dest);
+	    if (out.contains (dest))
+		continue;
+	    /* There was a contraction, so replay it but this time also record
+	       the intermediate nodes, so that the reachable set becomes
+	       complete.  This is necessary when reducing the candidate set.  */
+	    if (dest != e->dest)
+		contract_edge (e, G);
+	    out.safe_push (dest);
 	}
     }
 
@@ -784,12 +796,6 @@  isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
 		    bitmap_clear_bit (expr, NG[j]->index);
 		    bitmap_set_bit (expr, b->index);
 		    NG.safe_push (b);
-		    /* It could be that the predecessor edge from the ancestor
-		       was contracted past, in which case we need to mark it to
-		       make sure its ancestors_of do not immediately terminate.  */
-		    for (edge e : b->preds)
-			if (ctx.index_map[e->src->index] > ctx.index_map[p->index])
-			    bitmap_set_bit (reachable, e->src->index);
 		}
 	    }
 	}
@@ -813,6 +819,13 @@  isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
 	bitmap_clear (reachable);
 	for (basic_block b : G)
 	    bitmap_set_bit (reachable, b->index);
+
+	/* Contracted-past nodes in the subgraph must be re-marked, otherwise
+	   the next neighborhood may be computed wrong.  */
+	for (basic_block b : G)
+	    for (edge e : b->succs)
+		if (bitmap_bit_p (reachable, contract_edge (e)->dest->index))
+		    contract_edge (e, reachable);
     }
 
     out.safe_splice (G);