From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id CE93E3858409 for ; Tue, 14 Feb 2023 15:18:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CE93E3858409 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=suse.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.de 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 A06101FD79 for ; Tue, 14 Feb 2023 15:18:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_rsa; t=1676387910; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=QSCwqr9kebuJS7cPJmNltOlEUJlY2FpMyBw1OPURtKI=; b=pvMmdHsNRzaZvwK9JajcW2w2UGJ+kCo/SXyRYuLeQ5aNg3ED6M9J/qY/bbjiIdFgtIXvoO npHJxMA/av7OES8EP1geZf4wH/0OmETr/9khVdh2xKRA6YcbzfJjOT+b/rNbITUynvxd2b 4GCQQEH+y9yX8q2zamXvqCdSB6xtOd0= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.de; s=susede2_ed25519; t=1676387910; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type; bh=QSCwqr9kebuJS7cPJmNltOlEUJlY2FpMyBw1OPURtKI=; b=mm1Ls/MKoFQWB2YUpOqjcvgP0ggRneGbUJ/8NFevUhQmAzYY97rnOVadLeteSCcQj07US7 QACnaaT4ww/2mkDw== 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 8EEAF138E3 for ; Tue, 14 Feb 2023 15:18:30 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id Is3cIUam62MmbgAAMHmgww (envelope-from ) for ; Tue, 14 Feb 2023 15:18:30 +0000 Date: Tue, 14 Feb 2023 16:18:30 +0100 (CET) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Improve VN PHI hash table handling MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Message-Id: <20230214151830.8EEAF138E3@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 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: The hash function of PHIs is weak since we want to be able to CSE them even across basic-blocks in some cases. The following avoids weakening the hash for cases we are never going to CSE, reducing the number of collisions and avoiding redundant work in the hash and equality functions. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * tree-ssa-sccvn.cc (vn_phi_compute_hash): Key skipping basic block index hashing on the availability of ->cclhs. (vn_phi_eq): Avoid re-doing sanity checks for CSE but rely on ->cclhs availability. (vn_phi_lookup): Set ->cclhs only when we are eventually going to CSE the PHI. (vn_phi_insert): Likewise. --- gcc/tree-ssa-sccvn.cc | 77 ++++++++++++++++++++++++------------------- 1 file changed, 43 insertions(+), 34 deletions(-) diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc index e5bb278196a..8ee77fd2b78 100644 --- a/gcc/tree-ssa-sccvn.cc +++ b/gcc/tree-ssa-sccvn.cc @@ -4629,9 +4629,9 @@ vn_phi_compute_hash (vn_phi_t vp1) case 1: break; case 2: - if (vp1->block->loop_father->header == vp1->block) - ; - else + /* When this is a PHI node subject to CSE for different blocks + avoid hashing the block index. */ + if (vp1->cclhs) break; /* Fallthru. */ default: @@ -4715,32 +4715,33 @@ vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2) case 2: { - /* Rule out backedges into the PHI. */ - if (vp1->block->loop_father->header == vp1->block - || vp2->block->loop_father->header == vp2->block) + /* Make sure both PHIs are classified as CSEable. */ + if (! vp1->cclhs || ! vp2->cclhs) return false; + /* Rule out backedges into the PHI. */ + gcc_checking_assert + (vp1->block->loop_father->header != vp1->block + && vp2->block->loop_father->header != vp2->block); + /* If the PHI nodes do not have compatible types they are not the same. */ if (!types_compatible_p (vp1->type, vp2->type)) return false; + /* If the immediate dominator end in switch stmts multiple + values may end up in the same PHI arg via intermediate + CFG merges. */ basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block); basic_block idom2 = get_immediate_dominator (CDI_DOMINATORS, vp2->block); - /* If the immediate dominator end in switch stmts multiple - values may end up in the same PHI arg via intermediate - CFG merges. */ - if (EDGE_COUNT (idom1->succs) != 2 - || EDGE_COUNT (idom2->succs) != 2) - return false; + gcc_checking_assert (EDGE_COUNT (idom1->succs) == 2 + && EDGE_COUNT (idom2->succs) == 2); /* Verify the controlling stmt is the same. */ - gcond *last1 = safe_dyn_cast (last_stmt (idom1)); - gcond *last2 = safe_dyn_cast (last_stmt (idom2)); - if (! last1 || ! last2) - return false; + gcond *last1 = as_a (last_stmt (idom1)); + gcond *last2 = as_a (last_stmt (idom2)); bool inverted_p; if (! cond_stmts_equal_p (last1, vp1->cclhs, vp1->ccrhs, last2, vp2->cclhs, vp2->ccrhs, @@ -4835,15 +4836,19 @@ vn_phi_lookup (gimple *phi, bool backedges_varying_p) /* Extract values of the controlling condition. */ vp1->cclhs = NULL_TREE; vp1->ccrhs = NULL_TREE; - basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block); - if (EDGE_COUNT (idom1->succs) == 2) - if (gcond *last1 = safe_dyn_cast (last_stmt (idom1))) - { - /* ??? We want to use SSA_VAL here. But possibly not - allow VN_TOP. */ - vp1->cclhs = vn_valueize (gimple_cond_lhs (last1)); - vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1)); - } + if (EDGE_COUNT (vp1->block->preds) == 2 + && vp1->block->loop_father->header != vp1->block) + { + basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block); + if (EDGE_COUNT (idom1->succs) == 2) + if (gcond *last1 = safe_dyn_cast (last_stmt (idom1))) + { + /* ??? We want to use SSA_VAL here. But possibly not + allow VN_TOP. */ + vp1->cclhs = vn_valueize (gimple_cond_lhs (last1)); + vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1)); + } + } vp1->hashcode = vn_phi_compute_hash (vp1); slot = valid_info->phis->find_slot_with_hash (vp1, vp1->hashcode, NO_INSERT); if (!slot) @@ -4885,15 +4890,19 @@ vn_phi_insert (gimple *phi, tree result, bool backedges_varying_p) /* Extract values of the controlling condition. */ vp1->cclhs = NULL_TREE; vp1->ccrhs = NULL_TREE; - basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block); - if (EDGE_COUNT (idom1->succs) == 2) - if (gcond *last1 = safe_dyn_cast (last_stmt (idom1))) - { - /* ??? We want to use SSA_VAL here. But possibly not - allow VN_TOP. */ - vp1->cclhs = vn_valueize (gimple_cond_lhs (last1)); - vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1)); - } + if (EDGE_COUNT (vp1->block->preds) == 2 + && vp1->block->loop_father->header != vp1->block) + { + basic_block idom1 = get_immediate_dominator (CDI_DOMINATORS, vp1->block); + if (EDGE_COUNT (idom1->succs) == 2) + if (gcond *last1 = safe_dyn_cast (last_stmt (idom1))) + { + /* ??? We want to use SSA_VAL here. But possibly not + allow VN_TOP. */ + vp1->cclhs = vn_valueize (gimple_cond_lhs (last1)); + vp1->ccrhs = vn_valueize (gimple_cond_rhs (last1)); + } + } vp1->result = result; vp1->hashcode = vn_phi_compute_hash (vp1); -- 2.35.3