From patchwork Wed Oct 4 12:39:15 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?J=C3=B8rgen_Kvalsvik?= X-Patchwork-Id: 1843306 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (4096-bit key; secure) header.d=kolabnow.com header.i=@kolabnow.com header.a=rsa-sha256 header.s=dkim20160331 header.b=mUKki9H+; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4S0vTn5ZVmz1yng for ; Wed, 4 Oct 2023 23:42:21 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 550A9388B6A9 for ; Wed, 4 Oct 2023 12:42:14 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mx.kolabnow.com (mx.kolabnow.com [212.103.80.155]) by sourceware.org (Postfix) with ESMTPS id 4C4E73830B7B for ; Wed, 4 Oct 2023 12:40:59 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4C4E73830B7B 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 7A9CD20C81F2; Wed, 4 Oct 2023 14:40:58 +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=1696423257; x=1698237658; bh=VgN6uJlcL/elZ5+jH2WeFHxVTMlAk7PPuWFX1SrHg4Q=; b=mUKki9H+F6OJ fCIfukYzvA+v2r0+3el/6P/GO6MH7f11woLNFoQalwvHHXyXd1n0bphL8B49FLDp 7rHOctm58LlEA8H5U9eBFhvfHPxReuCKvjldMV2b/GfmaQqPHwohffpX8todvOqB ZQb9Y209wjVgxjFtZQKSmYpXpFVG0W3V+gEsX/nbAXQpKwVMMVCfSZ9/+4W1h4Uc sauqShn12D5YaBlcGKFOdHnvNc2hmLyh3n+wgCeIuIVJ5s0Sbw1SPDcSk8RnSGys ewNXI2YfRAUORSGNyHCCTj/rYYAMWRznt74QINZ3mFENXQ4cvySOSaXlK7aRNyr9 vVnj4m+Rj7xqVSMSg60NmdG4ttxEELVcMKMsEAP6GEmK61Rm8NdWidhfY6wHaZyk U5bwmF+0nqpR135g8yi9p4PRAzMrQR1Qlsj9EWhqAlcmp6iwf62iMYE9X2IZOmjB +a0g03Fm46O2LSA31vzaVIdLndwpqk5Asb02ZUQE/JPyOLJcqmLgWRiO7B5M2FPF zuO3YstZLOJamse7rUb8WJyCOqfsaDwosGxZoHHmuBqgbDTwOeRIkAHcLsIJITiA mFIiBIEfM73Ggbf+3wJsL3EKyhrRyrXm8hzoUek+puPh3TDioI+Ax0YVHC5i8jA2 hCHdaoXx8zeZdUDj0NXAJq8/paux6CY= X-Virus-Scanned: amavis at mykolab.com X-Spam-Score: -0.999 X-Spam-Level: X-Spam-Status: No, score=-12.0 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 7YOXM8QYysP5; Wed, 4 Oct 2023 14:40:57 +0200 (CEST) Received: from int-mx011.mykolab.com (unknown [10.9.13.11]) by mx.kolabnow.com (Postfix) with ESMTPS id 9B55520AB2E2; Wed, 4 Oct 2023 14:40:57 +0200 (CEST) Received: from ext-subm010.mykolab.com (unknown [10.9.6.10]) by int-mx011.mykolab.com (Postfix) with ESMTPS id 814283081E50; Wed, 4 Oct 2023 14:40:57 +0200 (CEST) From: =?utf-8?q?J=C3=B8rgen_Kvalsvik?= To: gcc-patches@gcc.gnu.org Cc: mliska@suse.cz, jh@suse.cz, =?utf-8?q?J=C3=B8rgen_Kvalsvik?= Subject: [PATCH 15/22] Fix candidate, neighborhood set reduction phase Date: Wed, 4 Oct 2023 21:39:15 +0900 Message-Id: <20231004123921.634024-16-j@lambda.is> In-Reply-To: <20231004123921.634024-1-j@lambda.is> References: <20231004123921.634024-1-j@lambda.is> MIME-Version: 1.0 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org This phase did not at all behave like advertised, which in turn lead to ICEs for the new tests. --- gcc/testsuite/gcc.misc-tests/gcov-19.c | 35 +++++++++++++++++++++++--- gcc/tree-profile.cc | 29 +++++++++++++++------ 2 files changed, 54 insertions(+), 10 deletions(-) diff --git a/gcc/testsuite/gcc.misc-tests/gcov-19.c b/gcc/testsuite/gcc.misc-tests/gcov-19.c index 1c671f7e186..5daa06cb7f4 100644 --- a/gcc/testsuite/gcc.misc-tests/gcov-19.c +++ b/gcc/testsuite/gcc.misc-tests/gcov-19.c @@ -4,6 +4,9 @@ /* 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) @@ -395,6 +398,15 @@ mcdc009a (int a, int b) x = a--; } +/* Multi-term loop condition with empty body, which can give neighborhoods of + size 1. */ +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) @@ -537,6 +549,21 @@ mcdc015c (int a, int b) } } +/* Early returns, gotos can create candidate sets where the neighborhood + internally shares dominator nodes that are not the first-in-expression which + implies the neighborhood belongs to some other boolean expression. When + this happens, the candidate set must be properly tidied up. */ +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) */ +} + /* check nested loops */ void @@ -639,9 +666,6 @@ mcdc017c (int a, int b) } while (n-- > 0); /* conditions(2/2) */ } -int id (int x) { return x; } -int inv (int x) { return !x; } - /* 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) { @@ -1332,6 +1356,9 @@ int main () mcdc009a (0, 0); mcdc009a (1, 1); + mcdc009b (0, 0); + mcdc009b (1, 0); + mcdc010a (0, 0); mcdc010a (0, 9); mcdc010a (2, 1); @@ -1369,6 +1396,8 @@ int main () mcdc015c (0, 5); mcdc015c (6, 1); + mcdc015d (1, 0, 0); + mcdc016a (5, 5); mcdc016b (5, 5); diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc index b75736a22a0..98593f53862 100644 --- a/gcc/tree-profile.cc +++ b/gcc/tree-profile.cc @@ -759,6 +759,10 @@ isolate_expression (conds_ctx &ctx, basic_block p, vec& out) if (bitmap_count_bits (expr) == 2) break; + /* This can happen for loops with no body. */ + if (bitmap_count_bits (expr) == 1 && bb_loop_header_p (p)) + break; + /* If the neighborhood does not change between iterations (a fixed point) we cannot understand the graph properly, and this would loop infinitely. If this should happen, we should bail out and give up @@ -768,21 +772,32 @@ isolate_expression (conds_ctx &ctx, basic_block p, vec& out) gcc_assert (false); bitmap_copy (prev, expr); - for (unsigned i = 0; i != NG.length () - 1; i++) + const unsigned NGlen = NG.length (); + for (unsigned i = 0; i != NGlen - 1; i++) { - for (unsigned j = i+1; j != NG.length (); j++) + for (unsigned j = i+1; j != NGlen; j++) { - auto b = nearest_common_dominator (CDI_DOMINATORS, NG[i], NG[j]); + basic_block b = nearest_common_dominator (CDI_DOMINATORS, NG[i], NG[j]); if (ctx.index_map[b->index] > ctx.index_map[p->index]) { - bitmap_clear_bit (reachable, NG[i]->index); - bitmap_clear_bit (reachable, NG[j]->index); - bitmap_set_bit (reachable, b->index); + bitmap_clear_bit (expr, NG[i]->index); + 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); } } } - bitmap_copy (expr, reachable); + for (unsigned i = 0; i != NG.length (); i++) + if (!bitmap_bit_p (expr, NG[i]->index)) + NG.unordered_remove (i--); + bitmap_copy (expr, reachable); for (const basic_block neighbor : NG) { bitmap_clear (ancestors);