From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out1.suse.de (smtp-out1.suse.de [IPv6:2a07:de40:b251:101:10:150:64:1]) by sourceware.org (Postfix) with ESMTPS id 5F1A13858D20 for ; Wed, 15 May 2024 17:25:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 5F1A13858D20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 5F1A13858D20 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a07:de40:b251:101:10:150:64:1 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1715793927; cv=none; b=J7uFvKBVZwULavxRVS1WReIvbRsVMNazABB8464co33zhVOs4ZloF8hpwOEmb7giv2nlrx46/N/HaUYOSkJ8BvBVa/PlTXge2RQiN4nZzGZqSj36DwV3j7lfMiIDNZDIuZALVBLibE1QpNpvDZocVOt4lrdMInaFzAmsk1Xn40w= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1715793927; c=relaxed/simple; bh=oG3XG2jkCo+zlCT20oUhbgt+07abFzOR+ATPKhGvLwM=; h=DKIM-Signature:DKIM-Signature:DKIM-Signature:DKIM-Signature:Date: From:To:Subject:MIME-Version:Message-Id; b=Z+1R3vI86UIRomLocNXwkM4io2glpZoAkRb+biy1vyVKK6XxRKpFUKMSoipBmf3TP/w0KBJoge5sDjT6NNBmnMo+4s+mvOHcGeklmfViCAB0oP6nyoCm4VrW3NMXjaf0vJQazhuEqeDscoXxgpnkjH/e0mcf8l8GXFoiCLdJnwE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: from imap1.dmz-prg2.suse.org (imap1.dmz-prg2.suse.org [IPv6:2a07:de40:b281:104:10:150:64:97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id B53EA33DBF for ; Wed, 15 May 2024 17:25:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1715793923; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ZUyAqnmPD8YKf5LnH+gpBimGpIMFEyz764RymXqglDE=; b=wcxjCV3OZS4v1C1P4tIyel/2fx3+PMWpO/7DRarXOcq0SKqg5+dCBWkHHQ1Z6rs4GoZdYF 505QiM0F8tbTBy9MKFESdVckA5SgRto4RoUdSfhoSFfPwqX9trcj04fkyObwtapSPt2QDK FLQ9BOStulACWAraHaaulHr/6pPMkaM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1715793923; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ZUyAqnmPD8YKf5LnH+gpBimGpIMFEyz764RymXqglDE=; b=u6FfbLK8C1nGqpxaIiJE/0GicTFzTRrQJYYcRV9kbl7cv93rss+Nf2ruJr0QJJTDJvfRZ6 I34PKT8e7Y6DMgCw== Authentication-Results: smtp-out1.suse.de; dkim=pass header.d=suse.de header.s=susede2_rsa header.b=wcxjCV3O; dkim=pass header.d=suse.de header.s=susede2_ed25519 header.b=u6FfbLK8 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1715793923; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ZUyAqnmPD8YKf5LnH+gpBimGpIMFEyz764RymXqglDE=; b=wcxjCV3OZS4v1C1P4tIyel/2fx3+PMWpO/7DRarXOcq0SKqg5+dCBWkHHQ1Z6rs4GoZdYF 505QiM0F8tbTBy9MKFESdVckA5SgRto4RoUdSfhoSFfPwqX9trcj04fkyObwtapSPt2QDK FLQ9BOStulACWAraHaaulHr/6pPMkaM= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1715793923; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=ZUyAqnmPD8YKf5LnH+gpBimGpIMFEyz764RymXqglDE=; b=u6FfbLK8C1nGqpxaIiJE/0GicTFzTRrQJYYcRV9kbl7cv93rss+Nf2ruJr0QJJTDJvfRZ6 I34PKT8e7Y6DMgCw== Received: from imap1.dmz-prg2.suse.org (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by imap1.dmz-prg2.suse.org (Postfix) with ESMTPS id 9C338136A8 for ; Wed, 15 May 2024 17:25:23 +0000 (UTC) Received: from dovecot-director2.suse.de ([2a07:de40:b281:106:10:150:64:167]) by imap1.dmz-prg2.suse.org with ESMTPSA id 1gyDJAPwRGZHNAAAD6G6ig (envelope-from ) for ; Wed, 15 May 2024 17:25:23 +0000 Date: Wed, 15 May 2024 19:25:23 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/79958 - make DSE track multiple paths MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20240515172523.9C338136A8@imap1.dmz-prg2.suse.org> X-Spam-Score: -6.51 X-Rspamd-Action: no action X-Rspamd-Queue-Id: B53EA33DBF X-Spam-Level: X-Rspamd-Server: rspamd2.dmz-prg2.suse.org X-Spamd-Result: default: False [-6.51 / 50.00]; BAYES_HAM(-3.00)[100.00%]; DWL_DNSWL_MED(-2.00)[suse.de:dkim]; NEURAL_HAM_LONG(-1.00)[-1.000]; R_DKIM_ALLOW(-0.20)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; NEURAL_HAM_SHORT(-0.20)[-1.000]; MIME_GOOD(-0.10)[text/plain]; MX_GOOD(-0.01)[]; RCVD_TLS_ALL(0.00)[]; ARC_NA(0.00)[]; RCPT_COUNT_ONE(0.00)[1]; RCVD_VIA_SMTP_AUTH(0.00)[]; MIME_TRACE(0.00)[0:+]; MISSING_XM_UA(0.00)[]; FUZZY_BLOCKED(0.00)[rspamd.com]; DNSWL_BLOCKED(0.00)[2a07:de40:b281:106:10:150:64:167:received]; DKIM_SIGNED(0.00)[suse.de:s=susede2_rsa,suse.de:s=susede2_ed25519]; FROM_EQ_ENVFROM(0.00)[]; FROM_HAS_DN(0.00)[]; DBL_BLOCKED_OPENRESOLVER(0.00)[suse.de:dkim]; RCVD_COUNT_TWO(0.00)[2]; TO_MATCH_ENVRCPT_ALL(0.00)[]; TO_DN_NONE(0.00)[]; PREVIOUSLY_DELIVERED(0.00)[gcc-patches@gcc.gnu.org]; DKIM_TRACE(0.00)[suse.de:+] X-Spam-Status: No, score=-11.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: DSE currently gives up when the path we analyze forks. This leads to multiple missed dead store elimination PRs. The following fixes this by recursing for each path and maintaining the visited bitmap to avoid visiting CFG re-merges multiple times. The overall cost is still limited by the same bound, it's just more likely we'll hit the limit now. The patch doesn't try to deal with byte tracking once a path forks but drops info on the floor and only handling fully dead stores in that case. Bootstrapped on x86_64-unknown-linux-gnu for all languages, testing in progress. Richard. PR tree-optimization/79958 PR tree-optimization/109087 PR tree-optimization/100314 PR tree-optimization/114774 * tree-ssa-dse.cc (dse_classify_store): New forwarder. (dse_classify_store): Add arguments cnt and visited, recurse to track multiple paths when we end up with multiple defs. * gcc.dg/tree-ssa/ssa-dse-48.c: New testcase. * gcc.dg/tree-ssa/ssa-dse-49.c: Likewise. * gcc.dg/tree-ssa/ssa-dse-50.c: Likewise. * gcc.dg/tree-ssa/ssa-dse-51.c: Likewise. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c | 17 ++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c | 18 +++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c | 25 +++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c | 24 +++++++++++++++++ gcc/tree-ssa-dse.cc | 31 +++++++++++++++++++--- 5 files changed, 111 insertions(+), 4 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c new file mode 100644 index 00000000000..edfc62c7e4a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-48.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-dse1-details" } */ + +int a; +int foo (void); +int bar (void); + +void +baz (void) +{ + int *b[6]; + b[0] = &a; + if (foo ()) + a |= bar (); +} + +/* { dg-final { scan-tree-dump "Deleted dead store: b\\\[0\\\] = &a;" "dse1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c new file mode 100644 index 00000000000..1eec284a415 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-49.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fno-tree-dce -fdump-tree-dse1-details" } */ + +struct X { int i; }; +void bar (); +void foo (int b) +{ + struct X x; + x.i = 1; + if (b) + { + bar (); + __builtin_abort (); + } + bar (); +} + +/* { dg-final { scan-tree-dump "Deleted dead store: x.i = 1;" "dse1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c new file mode 100644 index 00000000000..7c42ae6a67a --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-50.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-dse1-details" } */ + +extern void foo(void); +static int a, *c, g, **j; +int b; +static void e() { + int k, *l[5] = {&k, &k, &k, &k, &k}; + while (g) { + j = &l[0]; + b++; + } +} +static void d(int m) { + int **h[30] = {&c}, ***i[1] = {&h[3]}; + if (m) + foo(); + e(); +} +int main() { + d(a); + return 0; +} + +/* { dg-final { scan-tree-dump-times "Deleted dead store" 8 "dse1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c new file mode 100644 index 00000000000..ac9d1bb1fc8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-51.c @@ -0,0 +1,24 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fstrict-aliasing -fdump-tree-dse1-details" } */ + +int a; +short *p; +void +test (int b) +{ + a=1; + if (b) + { + (*p)++; + a=2; + __builtin_printf ("1\n"); + } + else + { + (*p)++; + a=3; + __builtin_printf ("2\n"); + } +} + +/* { dg-final { scan-tree-dump "Deleted dead store: a = 1;" "dse1" } } */ diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc index fce4fc76a56..9252ca34050 100644 --- a/gcc/tree-ssa-dse.cc +++ b/gcc/tree-ssa-dse.cc @@ -971,14 +971,13 @@ static hash_map *dse_stmt_to_dr_map; if only clobber statements influenced the classification result. Returns the classification. */ -dse_store_status +static dse_store_status dse_classify_store (ao_ref *ref, gimple *stmt, bool byte_tracking_enabled, sbitmap live_bytes, - bool *by_clobber_p, tree stop_at_vuse) + bool *by_clobber_p, tree stop_at_vuse, int &cnt, + bitmap visited) { gimple *temp; - int cnt = 0; - auto_bitmap visited; std::unique_ptr dra (nullptr, free_data_ref); @@ -1238,6 +1237,19 @@ dse_classify_store (ao_ref *ref, gimple *stmt, /* If all defs kill the ref we are done. */ if (defs.is_empty ()) return DSE_STORE_DEAD; + /* If more than one def survives we have to analyze multiple + paths. We can handle this by recursing, sharing 'visited' + to avoid redundant work and limiting it by shared 'cnt'. + For now do not bother with byte-tracking in this case. */ + while (defs.length () > 1) + { + if (dse_classify_store (ref, defs.last (), false, NULL, + by_clobber_p, stop_at_vuse, cnt, + visited) != DSE_STORE_DEAD) + break; + byte_tracking_enabled = false; + defs.pop (); + } /* If more than one def survives fail. */ if (defs.length () > 1) { @@ -1265,6 +1277,17 @@ dse_classify_store (ao_ref *ref, gimple *stmt, while (1); } +dse_store_status +dse_classify_store (ao_ref *ref, gimple *stmt, + bool byte_tracking_enabled, sbitmap live_bytes, + bool *by_clobber_p, tree stop_at_vuse) +{ + int cnt = 0; + auto_bitmap visited; + return dse_classify_store (ref, stmt, byte_tracking_enabled, live_bytes, + by_clobber_p, stop_at_vuse, cnt, visited); +} + /* Delete a dead call at GSI, which is mem* call of some kind. */ static void -- 2.35.3