From patchwork Tue Jan 10 15:53:28 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 62897 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5E31B385843E for ; Tue, 10 Jan 2023 15:53:59 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5E31B385843E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1673366039; bh=F+rwqnt1QE/MA+Ew92g4fQmBxwAPrZKT7aHOW86alEU=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=LlWjXVdGB2JfG552hMva2js+5WNqxhRd7iWUx5NMeRWcXkKC5dKldGuPcFUkm0ola xWyE6YfdeyEKqV8cqk9KCbrfpG3TLYm1QLd26IA70CeWRjQOo9c0UJ72t5K3HdMmNS HoPBzeDtOqjPF6/XmBaN1IXJCdqEEEkbCiOvf1EE= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [IPv6:2001:67c:2178:6::1d]) by sourceware.org (Postfix) with ESMTPS id 6F9893858CDA for ; Tue, 10 Jan 2023 15:53:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6F9893858CDA Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 7337F3DCE for ; Tue, 10 Jan 2023 15:53:28 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 5B4AC13338 for ; Tue, 10 Jan 2023 15:53:28 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id cGILFfiJvWO4EAAAMHmgww (envelope-from ) for ; Tue, 10 Jan 2023 15:53:28 +0000 Date: Tue, 10 Jan 2023 16:53:28 +0100 (CET) To: gcc-patches@gcc.gnu.org Subject: [PATCH] tree-optimization/106293 - missed DSE with virtual LC PHI MIME-Version: 1.0 Message-Id: <20230110155328.5B4AC13338@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.7 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Degenerate virtual PHIs can break DSEs fragile heuristic as to what defs it can handle for further processing. The following enhances it to look through degenerate PHIs by means of a worklist, processing the degenerate PHI defs uses to the defs array. The rewrite of virtuals into loop-closed SSA caused this to issue appear more often. The patch itself is mostly re-indenting the new loop body. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. PR tree-optimization/106293 * tree-ssa-dse.cc (dse_classify_store): Use a worklist to process degenerate PHI defs. * gcc.dg/tree-ssa/ssa-dse-46.c: New testcase. --- gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c | 23 +++ gcc/tree-ssa-dse.cc | 181 +++++++++++---------- 2 files changed, 121 insertions(+), 83 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c new file mode 100644 index 00000000000..68b36433ffc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dse-46.c @@ -0,0 +1,23 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-dse1" } */ + +int a; +static long b = 4073709551612, d; +short c; +void foo(); +char e(int **f) { + **f = 0; + if (a) { + unsigned long *g = &b; + unsigned long **h = &g; + for (; d;) { + foo(); + for (; c;) { + unsigned long ***i = &h; + } + } + } + return 1; +} + +/* { dg-final { scan-tree-dump-not "&b" "dse1" } } */ diff --git a/gcc/tree-ssa-dse.cc b/gcc/tree-ssa-dse.cc index 89e2fa2c3f5..46ab57d5754 100644 --- a/gcc/tree-ssa-dse.cc +++ b/gcc/tree-ssa-dse.cc @@ -984,108 +984,123 @@ dse_classify_store (ao_ref *ref, gimple *stmt, else defvar = gimple_vdef (temp); - /* If we're instructed to stop walking at region boundary, do so. */ - if (defvar == stop_at_vuse) - return DSE_STORE_LIVE; - auto_vec defs; gphi *first_phi_def = NULL; gphi *last_phi_def = NULL; - FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) + + auto_vec worklist; + worklist.quick_push (defvar); + + do { - /* Limit stmt walking. */ - if (++cnt > param_dse_max_alias_queries_per_store) - { - fail = true; - break; - } + defvar = worklist.pop (); + /* If we're instructed to stop walking at region boundary, do so. */ + if (defvar == stop_at_vuse) + return DSE_STORE_LIVE; - /* In simple cases we can look through PHI nodes, but we - have to be careful with loops and with memory references - containing operands that are also operands of PHI nodes. - See gcc.c-torture/execute/20051110-*.c. */ - if (gimple_code (use_stmt) == GIMPLE_PHI) + FOR_EACH_IMM_USE_STMT (use_stmt, ui, defvar) { - /* If we already visited this PHI ignore it for further - processing. */ - if (!bitmap_bit_p (visited, - SSA_NAME_VERSION (PHI_RESULT (use_stmt)))) + /* Limit stmt walking. */ + if (++cnt > param_dse_max_alias_queries_per_store) { - /* If we visit this PHI by following a backedge then we have - to make sure ref->ref only refers to SSA names that are - invariant with respect to the loop represented by this - PHI node. */ - if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), - gimple_bb (use_stmt)) - && !for_each_index (ref->ref ? &ref->ref : &ref->base, - check_name, gimple_bb (use_stmt))) - return DSE_STORE_LIVE; - defs.safe_push (use_stmt); - if (!first_phi_def) - first_phi_def = as_a (use_stmt); - last_phi_def = as_a (use_stmt); + fail = true; + break; } - } - /* If the statement is a use the store is not dead. */ - else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) - { - if (dse_stmt_to_dr_map - && ref->ref - && is_gimple_assign (use_stmt)) + + /* In simple cases we can look through PHI nodes, but we + have to be careful with loops and with memory references + containing operands that are also operands of PHI nodes. + See gcc.c-torture/execute/20051110-*.c. */ + if (gimple_code (use_stmt) == GIMPLE_PHI) { - if (!dra) - dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt, - false, false)); - bool existed_p; - data_reference_p &drb - = dse_stmt_to_dr_map->get_or_insert (use_stmt, &existed_p); - if (!existed_p) - drb = create_data_ref (NULL, NULL, - gimple_assign_rhs1 (use_stmt), - use_stmt, false, false); - if (!dr_may_alias_p (dra.get (), drb, NULL)) + /* Look through single-argument PHIs. */ + if (gimple_phi_num_args (use_stmt) == 1) + worklist.safe_push (gimple_phi_result (use_stmt)); + + /* If we already visited this PHI ignore it for further + processing. */ + else if (!bitmap_bit_p (visited, + SSA_NAME_VERSION + (PHI_RESULT (use_stmt)))) { - if (gimple_vdef (use_stmt)) - defs.safe_push (use_stmt); - continue; + /* If we visit this PHI by following a backedge then we + have to make sure ref->ref only refers to SSA names + that are invariant with respect to the loop + represented by this PHI node. */ + if (dominated_by_p (CDI_DOMINATORS, gimple_bb (stmt), + gimple_bb (use_stmt)) + && !for_each_index (ref->ref ? &ref->ref : &ref->base, + check_name, gimple_bb (use_stmt))) + return DSE_STORE_LIVE; + defs.safe_push (use_stmt); + if (!first_phi_def) + first_phi_def = as_a (use_stmt); + last_phi_def = as_a (use_stmt); } } + /* If the statement is a use the store is not dead. */ + else if (ref_maybe_used_by_stmt_p (use_stmt, ref)) + { + if (dse_stmt_to_dr_map + && ref->ref + && is_gimple_assign (use_stmt)) + { + if (!dra) + dra.reset (create_data_ref (NULL, NULL, ref->ref, stmt, + false, false)); + bool existed_p; + data_reference_p &drb + = dse_stmt_to_dr_map->get_or_insert (use_stmt, + &existed_p); + if (!existed_p) + drb = create_data_ref (NULL, NULL, + gimple_assign_rhs1 (use_stmt), + use_stmt, false, false); + if (!dr_may_alias_p (dra.get (), drb, NULL)) + { + if (gimple_vdef (use_stmt)) + defs.safe_push (use_stmt); + continue; + } + } - /* Handle common cases where we can easily build an ao_ref - structure for USE_STMT and in doing so we find that the - references hit non-live bytes and thus can be ignored. + /* Handle common cases where we can easily build an ao_ref + structure for USE_STMT and in doing so we find that the + references hit non-live bytes and thus can be ignored. - TODO: We can also use modref summary to handle calls. */ - if (byte_tracking_enabled - && is_gimple_assign (use_stmt)) - { - ao_ref use_ref; - ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); - if (valid_ao_ref_for_dse (&use_ref) - && operand_equal_p (use_ref.base, ref->base, - OEP_ADDRESS_OF) - && !live_bytes_read (&use_ref, ref, live_bytes)) + TODO: We can also use modref summary to handle calls. */ + if (byte_tracking_enabled + && is_gimple_assign (use_stmt)) { - /* If this is a store, remember it as we possibly - need to walk the defs uses. */ - if (gimple_vdef (use_stmt)) - defs.safe_push (use_stmt); - continue; + ao_ref use_ref; + ao_ref_init (&use_ref, gimple_assign_rhs1 (use_stmt)); + if (valid_ao_ref_for_dse (&use_ref) + && operand_equal_p (use_ref.base, ref->base, + OEP_ADDRESS_OF) + && !live_bytes_read (&use_ref, ref, live_bytes)) + { + /* If this is a store, remember it as we possibly + need to walk the defs uses. */ + if (gimple_vdef (use_stmt)) + defs.safe_push (use_stmt); + continue; + } } - } - fail = true; - break; + fail = true; + break; + } + /* We have visited ourselves already so ignore STMT for the + purpose of chaining. */ + else if (use_stmt == stmt) + ; + /* If this is a store, remember it as we possibly need to walk the + defs uses. */ + else if (gimple_vdef (use_stmt)) + defs.safe_push (use_stmt); } - /* We have visited ourselves already so ignore STMT for the - purpose of chaining. */ - else if (use_stmt == stmt) - ; - /* If this is a store, remember it as we possibly need to walk the - defs uses. */ - else if (gimple_vdef (use_stmt)) - defs.safe_push (use_stmt); } + while (!fail && !worklist.is_empty ()); if (fail) {