From patchwork Tue Feb 14 15:18:30 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 57065 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:adf:eb09:0:0:0:0:0 with SMTP id s9csp3036269wrn; Tue, 14 Feb 2023 07:19:16 -0800 (PST) X-Google-Smtp-Source: AK7set8U0vLWljifUEOCCV0GPJWIhI9OQFHvBgIiO5SY7JjHIua5Tr+GybJ+BfGzSLjbPgn1ZJXS X-Received: by 2002:a17:907:779a:b0:8af:301c:e201 with SMTP id ky26-20020a170907779a00b008af301ce201mr3278641ejc.67.1676387956118; Tue, 14 Feb 2023 07:19:16 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1676387956; cv=none; d=google.com; s=arc-20160816; b=pJFKKnAogl8caJOhclPwEPCWiAw6+tQSYKUDdRKOXrd6d2yfJENZOSqfN4tALVjuIv Ju7Bdg/IEZJdM+NcdAhO5J1FwT5RuUMa6aqdVkAHCvN4Je5VEYk9dvjt+yRJNx2CP5d/ rGwAe1HyXnWtTbRgcpGKQqDzogY/soW8YoUqKnOA7CM/VCzkFyTAk9R1sC7Vxsw0NhuN KeI7OvRa9MSaXP4RiThujLoVg3JTYLqxqx1hZo+NWgZ7xx48vXpopum26t84pU2bjGGC WNPqatZnFvX5pGVJq6g3PaZMR2ncdTjoCBC4MvEAmPnu3EYyrxhBnuqnpk0Yb2Ed1j2V TMyQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence:message-id :mime-version:subject:to:date:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=QSCwqr9kebuJS7cPJmNltOlEUJlY2FpMyBw1OPURtKI=; b=ckcNJk+KtZxchWhpgvVSMn0HMM0d5osTpV0stL5RuCEV2BDS1/z7hISalwFwEEL/LU lQNCwwKqHWE95CzQKu0epDIPXSTPcxsF/aemrIvIevrWTQHPGZZHdbIFrPq8JuSXVidj TXXHK1U4wyRdKs9Chgh1nrMgCG5CN44kGMMUE2KektejZOpEFx6r5GRx5N2DY+OvQVAL rRIAwSco6TU4e/Pj+nfH3VxIlcFBtX66Afu0yur2HEx2CZpzds8z2KINSFhfVTfp9/rZ 0ARot3mPfOSTur5Fl0zKff+wxbhmyM8JcTBQnKHzJWLdreNf+qXJ4rrBzYsQdXU2JDYr WS6g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SFUBIsGH; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from sourceware.org (ip-8-43-85-97.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id u9-20020a170906108900b008b1318e0bf6si2291083eju.74.2023.02.14.07.19.15 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 Feb 2023 07:19:16 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b=SFUBIsGH; spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=gnu.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 266BC3858D33 for ; Tue, 14 Feb 2023 15:19:15 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 266BC3858D33 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1676387955; bh=QSCwqr9kebuJS7cPJmNltOlEUJlY2FpMyBw1OPURtKI=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=SFUBIsGHr5R5+S3QCNOFRL8vT51QZynRGgSeb85rLo57oKjDYqC14s2Luo2IYCLP2 Kae6SH5Rg3SF+2BwBbyv4/LraULd2ijdC1NJH0EPHRmld7O0tIhoyMcb8bw01m2RpV +p1Jmk6yOOl5ShuvWY6XBaKlrem7/p07cjUEr7yA= 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 [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 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) 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) To: gcc-patches@gcc.gnu.org Subject: [PATCH] Improve VN PHI hash table handling MIME-Version: 1.0 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 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+ouuuleilei=gmail.com@gcc.gnu.org Sender: "Gcc-patches" X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1757820177360877557?= X-GMAIL-MSGID: =?utf-8?q?1757820177360877557?= 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);