From patchwork Mon May 29 16:19:39 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Martin Jambor X-Patchwork-Id: 1787184 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org 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=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=suse.cz header.i=@suse.cz header.a=rsa-sha256 header.s=susede2_rsa header.b=F1YPrCXN; dkim=pass header.d=suse.cz header.i=@suse.cz header.a=ed25519-sha256 header.s=susede2_ed25519 header.b=uC0bj/by; dkim-atps=neutral Received: from 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 (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4QVLMx5r47z20PW for ; Tue, 30 May 2023 02:19:56 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id B6D91385696A for ; Mon, 29 May 2023 16:19:53 +0000 (GMT) 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 22D773858C00 for ; Mon, 29 May 2023 16:19:41 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 22D773858C00 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=suse.cz 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 3E1721F88E; Mon, 29 May 2023 16:19:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1685377180; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=mEaz7Vd9R6yEL4VO23aC54qzrbR0AUF8rb5qOG6INvA=; b=F1YPrCXNpyMKQyXd3h3uLus3tVkCDLmak5iZxC3GxJCEA6/BbZ+6TLuGpA85+IQ0qf9+k7 TbzW8S4asX3ZdmvyNT4O+LJYzQWMml6hNVgvrZ7jfuGEcsEHZ3kAAwXl2LomBaRAF6lgBv aN0EywJipkEql7KNrlAy7Ep4l6g+z7Q= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1685377180; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type; bh=mEaz7Vd9R6yEL4VO23aC54qzrbR0AUF8rb5qOG6INvA=; b=uC0bj/by0rwSJ23zdI+h5kLj5haJDKCinLbPq/4vZwlukj/NNOTuIi4Jj/N53LpUW+r0Ms bIeJSCjzaVtQqbAQ== 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 31F2F13466; Mon, 29 May 2023 16:19:40 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id ZTcoDJzQdGQpUgAAMHmgww (envelope-from ); Mon, 29 May 2023 16:19:40 +0000 From: Martin Jambor To: GCC Patches Cc: Jan Hubicka Subject: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS User-Agent: Notmuch/0.37 (https://notmuchmail.org) Emacs/28.2 (x86_64-suse-linux-gnu) Date: Mon, 29 May 2023 18:19:39 +0200 Message-ID: MIME-Version: 1.0 X-Spam-Status: No, score=-11.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_SOFTFAIL, TXREP, T_SCC_BODY_TEXT_LINE 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: , Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Hi, there have been concerns that linear searches through DECL_ARGUMENTS that are often necessary to compute the index of a particular PARM_DECL which is the key to results of IPA-CP can happen often enough to be a compile time issue, especially if we plug the results into value numbering, as I intend to do with a follow-up patch. This patch creates a hash map to do the look-up for all functions which have some information discovered by IPA-CP and which have 32 parameters or more. 32 is a hard-wired magical constant here to capture the trade-off between the memory allocation overhead and length of the linear search. I do not think it is worth making it a --param but if people think it appropriate, I can turn it into one. Bootstrapped, tested and LTO bootstrapped on x86_64-linux, both as-is and with themagical constant dropped to 4 so that the has lookup path is also well excercised. OK for master? Thanks, Martin gcc/ChangeLog: 2023-05-26 Martin Jambor * ipa-prop.h (struct ipcp_transformation): Rearrange members according to C++ class coding convention, add m_tree_to_idx, get_param_index and maybe_create_parm_idx_map. * ipa-cp.cc (ipcp_transformation::get_param_index): New function. (ipcp_transformation::maype_create_parm_idx_map): Likewise. * ipa-prop.cc (ipcp_get_parm_bits): Use get_param_index. (ipcp_update_bits): Accept TS as a parameter, assume it is not NULL. (ipcp_update_vr): Likewise. (ipcp_transform_function): Call, maybe_create_parm_idx_map of TS, bail out quickly if empty, pass it to ipcp_update_bits and ipcp_update_vr. --- gcc/ipa-cp.cc | 45 +++++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-prop.cc | 44 +++++++++++++++++++------------------------- gcc/ipa-prop.h | 33 +++++++++++++++++++++++++-------- 3 files changed, 89 insertions(+), 33 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index 0f37bb5e336..9f8b07b2398 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -6761,3 +6761,48 @@ ipa_cp_cc_finalize (void) orig_overall_size = 0; ipcp_free_transformation_sum (); } + +/* Given PARAM which must be a parameter of function FNDECL described by THIS, + return its index in the DECL_ARGUMENTS chain, using a pre-computed hash map + if avialable (which is pre-computed only if there are many parameters). Can + return -1 if param is static chain not represented among DECL_ARGUMENTS. */ + +int +ipcp_transformation::get_param_index (const_tree fndecl, const_tree param) const +{ + gcc_assert (TREE_CODE (param) == PARM_DECL); + if (m_tree_to_idx) + { + unsigned *pr = m_tree_to_idx->get(param); + if (!pr) + { + gcc_assert (DECL_STATIC_CHAIN (fndecl)); + return -1; + } + return (int) *pr; + } + + unsigned index = 0; + for (tree p = DECL_ARGUMENTS (fndecl); p; p = DECL_CHAIN (p), index++) + if (p == param) + return (int) index; + + gcc_assert (DECL_STATIC_CHAIN (fndecl)); + return -1; +} + +/* Assuming THIS describes FNDECL and it has sufficiently many parameters to + justify the overhead, creat a has map from parameter trees to their + indices. */ +void +ipcp_transformation::maybe_create_parm_idx_map (tree fndecl) +{ + int c = count_formal_params (fndecl); + if (c < 32) + return; + + m_tree_to_idx = hash_map::create_ggc (c); + unsigned index = 0; + for (tree p = DECL_ARGUMENTS (fndecl); p; p = DECL_CHAIN (p), index++) + m_tree_to_idx->put (p, index); +} diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index ab6de9f10da..f0976e363f7 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -5776,16 +5776,9 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_int *mask) if (!ts || vec_safe_length (ts->bits) == 0) return false; - int i = 0; - for (tree p = DECL_ARGUMENTS (current_function_decl); - p != parm; p = DECL_CHAIN (p)) - { - i++; - /* Ignore static chain. */ - if (!p) - return false; - } - + int i = ts->get_param_index (current_function_decl, parm); + if (i < 0) + return false; clone_info *cinfo = clone_info::get (cnode); if (cinfo && cinfo->param_adjustments) { @@ -5802,16 +5795,12 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_int *mask) return true; } - -/* Update bits info of formal parameters as described in - ipcp_transformation. */ +/* Update bits info of formal parameters of NODE as described in TS. */ static void -ipcp_update_bits (struct cgraph_node *node) +ipcp_update_bits (struct cgraph_node *node, ipcp_transformation *ts) { - ipcp_transformation *ts = ipcp_get_transformation_summary (node); - - if (!ts || vec_safe_length (ts->bits) == 0) + if (vec_safe_is_empty (ts->bits)) return; vec &bits = *ts->bits; unsigned count = bits.length (); @@ -5913,14 +5902,12 @@ ipcp_update_bits (struct cgraph_node *node) } } -/* Update value range of formal parameters as described in - ipcp_transformation. */ +/* Update value range of formal parameters of NODE as described in TS. */ static void -ipcp_update_vr (struct cgraph_node *node) +ipcp_update_vr (struct cgraph_node *node, ipcp_transformation *ts) { - ipcp_transformation *ts = ipcp_get_transformation_summary (node); - if (!ts || vec_safe_length (ts->m_vr) == 0) + if (vec_safe_is_empty (ts->m_vr)) return; const vec &vr = *ts->m_vr; unsigned count = vr.length (); @@ -5996,10 +5983,17 @@ ipcp_transform_function (struct cgraph_node *node) fprintf (dump_file, "Modification phase of node %s\n", node->dump_name ()); - ipcp_update_bits (node); - ipcp_update_vr (node); ipcp_transformation *ts = ipcp_get_transformation_summary (node); - if (!ts || vec_safe_is_empty (ts->m_agg_values)) + if (!ts + || (vec_safe_is_empty (ts->m_agg_values) + && vec_safe_is_empty (ts->bits) + && vec_safe_is_empty (ts->m_vr))) + return 0; + + ts->maybe_create_parm_idx_map (cfun->decl); + ipcp_update_bits (node, ts); + ipcp_update_vr (node, ts); + if (vec_safe_is_empty (ts->m_agg_values)) return 0; param_count = count_formal_params (node->decl); if (param_count == 0) diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h index f306f8a377e..211b12ff6b3 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -925,16 +925,10 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i) struct GTY(()) ipcp_transformation { - /* Known aggregate values. */ - vec *m_agg_values; - /* Known bits information. */ - vec *bits; - /* Value range information. */ - vec *m_vr; - /* Default constructor. */ ipcp_transformation () - : m_agg_values (NULL), bits (NULL), m_vr (NULL) + : m_agg_values (nullptr), bits (nullptr), m_vr (nullptr), + m_tree_to_idx (nullptr) { } /* Default destructor. */ @@ -944,6 +938,29 @@ struct GTY(()) ipcp_transformation vec_free (bits); vec_free (m_vr); } + + /* Given PARAM which must be a parameter of function FNDECL described by + THIS, return its index in the DECL_ARGUMENTS chain, using a pre-computed + hash map if avialable (which is pre-computed only if there are many + parameters). Can return -1 if param is static chain not represented among + DECL_ARGUMENTS. */ + int get_param_index (const_tree fndecl, const_tree param) const; + + /* Assuming THIS describes FUNC and it has sufficiently many parameters to + justify the overhead, creat a has map from parameter trees to their + indices. */ + + void maybe_create_parm_idx_map (tree fndecl); + + /* Known aggregate values. */ + vec *m_agg_values; + /* Known bits information. */ + vec *bits; + /* Value range information. */ + vec *m_vr; + /* If there are many parameters, a hash map to speed-up look-ups of their + indices. */ + hash_map *m_tree_to_idx; }; inline