[PATCH 10/22] Prune search for boolean expr on goto, return

["Jørgen Kvalsvik" <j@lambda.is>]

The search for the initial candidate set for a decision is a delicate
affair in complex CFGs with gotos (mostly from returns). Gotos and
returns in the then-block could create graphs where the goto/return edge
would also be searched for candidates for G, even though they can never
be a part of the expression being searched for.

Nodes may have complex predecessor edges which should be silently
ignored. Complex edges signify some odd or abnormal control flow, and
the flow of evaluation of terms in a boolean expression certainly does
not fall into this category.
---
 gcc/testsuite/gcc.misc-tests/gcov-19.c | 53 ++++++++++++++++++++++++--
 gcc/tree-profile.cc                    | 33 +++++++++++++++-
 2 files changed, 82 insertions(+), 4 deletions(-)

diff --git a/gcc/testsuite/gcc.misc-tests/gcov-19.c b/gcc/testsuite/gcc.misc-tests/gcov-19.c
index 73e268ab15e..662f4ca2864 100644
--- a/gcc/testsuite/gcc.misc-tests/gcov-19.c
+++ b/gcc/testsuite/gcc.misc-tests/gcov-19.c
@@ -312,6 +312,30 @@ begin:
 	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)
@@ -557,9 +581,6 @@ mcdc017a (int a)
     } while (a > 0); /* conditions(2/2) */
 }
 
-void
-noop () {}
-
 void
 mcdc017b (int a, int b)
 {
@@ -845,6 +866,29 @@ mcdc022d (int a)
 	x = a + 1;
 }
 
+/* Adapted from openssl-3.0.1/crypto/cmp/cmp_msg.c ossl_cmp_error_new ().
+   Without proper limiting of the initial candidate search this misidentified
+   { ...; if (fn ()) goto err; } if (c) goto err; as a 2-term expression.  */
+void
+mcdc022e (int a, int b, int c, int d)
+{
+    if (a || b) /* conditions(1/4) true(0) false(0 1) */
+		/* conditions(end) */
+    {
+	if (always (c)) /* conditions(1/2) false(0) */
+			/* conditions(end) */
+	    goto err;
+    }
+
+    if (d)  /* conditions(0/2) true(0) false(0) */
+	    /* conditions(end) */
+	goto err;
+    return;
+
+err:
+    noop ();
+}
+
 /* 023 specifically tests that masking works correctly, which gets complicated
    fast with a mix of operators and deep subexpressions.  These tests violates
    the style guide slightly to emphasize the nesting.  They all share the same
@@ -1128,6 +1172,8 @@ int main ()
     mcdc007c (0, 1, 1);
     mcdc007c (1, 0, 1);
 
+    mcdc007d (0, 1, 0, 1, 1);
+
     mcdc008a (0);
 
     mcdc008b (0);
@@ -1232,6 +1278,7 @@ int main ()
     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);
diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
index adab0f59c07..f98bb1f76c8 100644
--- a/gcc/tree-profile.cc
+++ b/gcc/tree-profile.cc
@@ -618,11 +618,40 @@ masking_vectors (conds_ctx& ctx, array_slice<basic_block> blocks,
     }
 }
 
+/* Check that all predecessors are conditional and belong to the current
+   expression.  This check is necessary in the presence of gotos, setjmp and
+   other complicated control flow that creates extra edges and creates odd
+   reachable paths from mid-expression terms and paths escaping nested
+   expressions.  If a node has an incoming non-complex edge (after contraction)
+   it can not be a part of a single, multi-term conditional expression.
+
+   If the expr[i] is set then nodes[i] is reachable from the leftmost operand
+   and b is a viable candidate.  Otherwise, this has to be an independent but
+   following expression.
+ */
+bool
+all_preds_conditional_p (basic_block b, const sbitmap expr)
+{
+    for (edge e : b->preds)
+    {
+	e = contract_edge_up (e);
+	if (!(e->flags & (EDGE_CONDITION | EDGE_COMPLEX)))
+	    return false;
+
+	if (!bitmap_bit_p (expr, e->src->index))
+	    return false;
+    }
+    return true;
+}
+
 /* Find the nodes reachable from p by following only (possibly contracted)
    condition edges and ignoring DFS back edges.  From a high level this is
    partitioning the CFG into subgraphs by removing all non-condition edges and
    selecting a single connected subgraph.  This creates a cut C = (G, G') where
-   G is the returned explicitly by this function.
+   G is the returned explicitly by this function and forms the candidate set
+   for an expression.  All nodes in an expression should be connected only by
+   true|false edges, so a node with a non-conditional predecessor must be a
+   part of a different expression and in G', not G.
 
    It is assumed that all paths from p go through q (q post-dominates p).  p
    must always be the first term in an expression and a condition node.
@@ -652,6 +681,8 @@ cond_reachable_from (basic_block p, basic_block q, sbitmap expr,
 		continue;
 	    if (e->flags & EDGE_DFS_BACK)
 		continue;
+	    if (!all_preds_conditional_p (dest, expr))
+		continue;
 
 	    bitmap_set_bit (expr, dest->index);
 	    out.safe_push (dest);
-- 
2.30.2