From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mx.kolabnow.com (mx.kolabnow.com [212.103.80.155]) by sourceware.org (Postfix) with ESMTPS id CECA3386192F for ; Wed, 4 Oct 2023 12:40:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CECA3386192F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=lambda.is Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=lambda.is Received: from localhost (unknown [127.0.0.1]) by mx.kolabnow.com (Postfix) with ESMTP id 03A9320AB2E3; Wed, 4 Oct 2023 14:40:46 +0200 (CEST) Authentication-Results: ext-mx-out011.mykolab.com (amavis); dkim=pass (4096-bit key) reason="pass (just generated, assumed good)" header.d=kolabnow.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=kolabnow.com; h= content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:date:subject:subject:from:from:received :received:received; s=dkim20160331; t=1696423245; x=1698237646; bh=A+YRdYxiM/PgcZEdUhx4GRRUlZBF2fCFrRiDwDE2MOA=; b=1ApUKGQKVUBZ Hda3Nt333kJWEsIc455qeIlUI5Hfcj6uWThok5DdxXnddeDQnqwfM8fQlOvo+NwV Oke4OKNt2rsm13wAEhLXV+X9QQ0hBUfIk9gfc59e4+Mu7vvXFB3fefBi8ymCrmbW cEDTYUlCps4LBamoYImtwvvh7UtpJlCpMIinMWkUx6o7rg8RwIzJ+0BbBtZRJMf8 faOr1SNSHMiz2URVRK8iq2qjLcPK99iF9nfcs1cvR3u21Gr06EJtTW2vEDxIfH9G 0M0hgqnYtVhHrnpV9b5hCNAy5nsQW5juBouZYkSns9o2KBk2C46oV+6UBbwELaLH JiHoAEDdQJE6AJLLOJntSWojbedU+LQo3eeWRJNzyvELEekTpMnkK2u2NDjDV7NF CzSwiOkJXCC/7SUym/xxTTimatiIGc1PNLod1PbczJeV8TOQb18/YhvcjLZ9XPaM jF3NEiHA47PNofjo28lk5Frsn/cSbt6sGh4V03+WRi3d4qiopqntnH7OdSbeSQJc zUM9tzk7bsDbVbZPj10evcSYV531HUMUZYi5nvmQZh9Jw8dYScnT7lgbeduJ0QR/ E1LxMpUJxzR2YkQDX3DRQkq1KCPo2ncvrDt2tQiMny4stqhJc3GiHjWNiu2S/GWs 61srfQn3n3ExFuEcsgzYcGO+LonP6es= X-Virus-Scanned: amavis at mykolab.com X-Spam-Score: -0.999 X-Spam-Level: X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 Received: from mx.kolabnow.com ([127.0.0.1]) by localhost (ext-mx-out011.mykolab.com [127.0.0.1]) (amavis, port 10024) with ESMTP id bqo4zgzdcG4S; Wed, 4 Oct 2023 14:40:45 +0200 (CEST) Received: from int-mx009.mykolab.com (unknown [10.9.13.9]) by mx.kolabnow.com (Postfix) with ESMTPS id 1A7E020AB2E2; Wed, 4 Oct 2023 14:40:45 +0200 (CEST) Received: from ext-subm010.mykolab.com (unknown [10.9.6.10]) by int-mx009.mykolab.com (Postfix) with ESMTPS id 0A8E720D6AE9; Wed, 4 Oct 2023 14:40:45 +0200 (CEST) From: =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?= To: gcc-patches@gcc.gnu.org Cc: mliska@suse.cz, jh@suse.cz, =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?= Subject: [PATCH 10/22] Prune search for boolean expr on goto, return Date: Wed, 4 Oct 2023 21:39:10 +0900 Message-Id: <20231004123921.634024-11-j@lambda.is> In-Reply-To: <20231004123921.634024-1-j@lambda.is> References: <20231004123921.634024-1-j@lambda.is> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: 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 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