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 AE582388206D for ; Wed, 4 Oct 2023 12:41:03 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org AE582388206D 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 DA98B20AB2E2; Wed, 4 Oct 2023 14:41:02 +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=1696423261; x=1698237662; bh=RH/dW56YqWBIiT4iWheYXUAAtCQN7H5bmxCJ6IN2iPM=; b=OoUlbPzn739w ipNMuPhZseENaPdteGPWnjEtblkRxhO2sgcFCvgQ9m3BZKclrejSfF/Dk3vWY+yC NtDqCLuf4P+0Css0X1b7/pvG8eHFbIx3Wo4tGzWkQ534AxNDELpL9bVCyCMkf89b tQebKM3OcoGtEF0VhdKR9H5jwD3M33qICXK8i2UJyKaAlCphtBSV8u6K/8LJmzVc 3L0se5seFq/Wu3SjLC8a/NqyKfAUQylUqqnN5V5KtMTjp6l325rfOYqSKVX5AB4T T6XVwa95aKvX49x3fwZD+Q5emEh7clzs1NvBHDFU+C2bSLZ+qmQtzePJAOHkCqT6 3gUCtQa9H0fBsBBKudKla4KX2dKf+7rWON900yswVsqzWY+BatUa9XRbwWiD864L +HYUdgcohZjaoC0JNgUXkzRmhPtEBfkHIVip4hZk2Tv98xmLZtlM1FUf9RuJrs5I u7lPRM60tRUqty758ekKQY1vk7EkyYX7Bl46OLnFv+AXSp1EYazO/iUl5+t2WMan QW3jLPVBw8aHpkGsL4soya8YafnWdY6TODgYk42xTlS0iMSrv/wpqY54kkyn+mat cI8AahjwgFE6cCR+c2/Aw20H6zzXCJgmqs63U1aO6ZLQV+HEuMkONBNdyRfoYL57 QwfWRQhPPW3Lh2tvMGsT7XsbwNLHDXo= X-Virus-Scanned: amavis at mykolab.com X-Spam-Score: -0.999 X-Spam-Level: X-Spam-Status: No, score=-12.2 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 mTmBQ5M0RE5Q; Wed, 4 Oct 2023 14:41:01 +0200 (CEST) Received: from int-mx009.mykolab.com (unknown [10.9.13.9]) by mx.kolabnow.com (Postfix) with ESMTPS id D691020C81FD; Wed, 4 Oct 2023 14:41:01 +0200 (CEST) Received: from ext-subm010.mykolab.com (unknown [10.9.6.10]) by int-mx009.mykolab.com (Postfix) with ESMTPS id C080D20D6AE9; Wed, 4 Oct 2023 14:41:01 +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 17/22] Mark contracted-past nodes in reachable Date: Wed, 4 Oct 2023 21:39:17 +0900 Message-Id: <20231004123921.634024-18-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: When there was no candidate set reduction phase this was not necessary, as every neighbor's predecessor would always be in the reachable set. Now that the graph cut is refined multiple times this may not hold, which would lead to incorrect termination of the ancestors search when a node in the candidate set was reduced to neighbor (effectively moving the cut) as its predecessor may have been contracted by. --- gcc/testsuite/gcc.misc-tests/gcov-23.c | 75 ++++++++++++++++++++++++++ gcc/tree-profile.cc | 41 +++++++++----- 2 files changed, 102 insertions(+), 14 deletions(-) create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-23.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..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 *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& blocks, sbitmap G, vec& 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& 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& 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); -- 2.30.2