From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1611) id 2A1773858D1E; Tue, 20 Jun 2023 16:17:24 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 2A1773858D1E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1687277844; bh=2GPmiDy/IaAYK2e574h9PRMDmP2cvmCFnfDJYCdQCr0=; h=From:To:Subject:Date:From; b=u1vA+He17EpZCLM6Bmhe6RYYCohR9sH9f7XjLoq3Ze4myNAZescSLNUOh2Pb6hOIL ls+cBu+O25NQNQx4xs4Ejw0fQOokuEXrxYBTqGfcUeTGyUwF46z1NTKtwcHV+XG0NB V4+yGZTD8kQnJt0mV4KjvR7hbZ38hgwSoodl5rYA= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Martin Jambor To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-1997] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS X-Act-Checkin: gcc X-Git-Author: Martin Jambor X-Git-Refname: refs/heads/master X-Git-Oldrev: 86df278de15b4a51d6cdb0e8922c2d05adfb64a4 X-Git-Newrev: 7f986e2ed9323099bf142756d282002baa869289 Message-Id: <20230620161724.2A1773858D1E@sourceware.org> Date: Tue, 20 Jun 2023 16:17:24 +0000 (GMT) List-Id: https://gcc.gnu.org/g:7f986e2ed9323099bf142756d282002baa869289 commit r14-1997-g7f986e2ed9323099bf142756d282002baa869289 Author: Martin Jambor Date: Tue Jun 20 18:15:22 2023 +0200 ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 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 vector sorted according to PARM_DECLs 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. gcc/ChangeLog: 2023-05-31 Martin Jambor * ipa-prop.h (ipa_uid_to_idx_map_elt): New type. (struct ipcp_transformation): Rearrange members according to C++ class coding convention, add m_uid_to_idx, get_param_index and maybe_create_parm_idx_map. * ipa-cp.cc (ipcp_transformation::get_param_index): New function. (compare_uids): Likewise. (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. Diff: --- gcc/ipa-cp.cc | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-prop.cc | 44 +++++++++++++++------------------ gcc/ipa-prop.h | 44 +++++++++++++++++++++++++++------ 3 files changed, 131 insertions(+), 33 deletions(-) diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc index f0a314c490c..846dcf8a7f3 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -6779,3 +6779,79 @@ 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 + DECL_UID-sorted vector if available (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_uid_to_idx) + { + unsigned puid = DECL_UID (param); + const ipa_uid_to_idx_map_elt *res + = std::lower_bound (m_uid_to_idx->begin(), m_uid_to_idx->end (), puid, + [] (const ipa_uid_to_idx_map_elt &elt, unsigned uid) + { + return elt.uid < uid; + }); + if (res == m_uid_to_idx->end () + || res->uid != puid) + { + gcc_assert (DECL_STATIC_CHAIN (fndecl)); + return -1; + } + return res->index; + } + + 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; +} + +/* Helper function to qsort a vector of ipa_uid_to_idx_map_elt elements + according to the uid. */ + +static int +compare_uids (const void *a, const void *b) +{ + const ipa_uid_to_idx_map_elt *e1 = (const ipa_uid_to_idx_map_elt *) a; + const ipa_uid_to_idx_map_elt *e2 = (const ipa_uid_to_idx_map_elt *) b; + if (e1->uid < e2->uid) + return -1; + if (e1->uid > e2->uid) + return 1; + gcc_unreachable (); +} + +/* Assuming THIS describes FNDECL and it has sufficiently many parameters to + justify the overhead, create a DECL_UID-sorted vector to speed up mapping + from parameters to their indices in DECL_ARGUMENTS chain. */ + +void +ipcp_transformation::maybe_create_parm_idx_map (tree fndecl) +{ + int c = count_formal_params (fndecl); + if (c < 32) + return; + + m_uid_to_idx = NULL; + vec_safe_reserve (m_uid_to_idx, c, true); + unsigned index = 0; + for (tree p = DECL_ARGUMENTS (fndecl); p; p = DECL_CHAIN (p), index++) + { + ipa_uid_to_idx_map_elt elt; + elt.uid = DECL_UID (p); + elt.index = index; + m_uid_to_idx->quick_push (elt); + } + m_uid_to_idx->qsort (compare_uids); +} diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc index eea81176864..704fe01b02c 100644 --- a/gcc/ipa-prop.cc +++ b/gcc/ipa-prop.cc @@ -5778,16 +5778,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) { @@ -5804,16 +5797,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 (); @@ -5915,14 +5904,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 (); @@ -5998,10 +5985,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 3a591a8f44d..9b7fee4c930 100644 --- a/gcc/ipa-prop.h +++ b/gcc/ipa-prop.h @@ -921,20 +921,24 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i) return (*info->descriptors)[i].used_by_polymorphic_call; } +/* GTY-marked structure used to map DECL_UIDs of APRAMs to their indices in + their DECL_ARGUMENTs chain. */ +struct GTY(()) ipa_uid_to_idx_map_elt +{ + /* DECL_UID of the PARAM. */ + unsigned uid; + /* Its index in the DECL_ARGUMETs chain. */ + unsigned index; +}; + /* Structure holding information for the transformation phase of IPA-CP. */ 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_uid_to_idx (nullptr) { } /* Default destructor. */ @@ -944,6 +948,30 @@ 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 + DECL_UID-sorted vector if available (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 FNDECL and it has sufficiently many parameters to + justify the overhead, create a DECL_UID-sorted vector to speed up mapping + from parameters to their indices in DECL_ARGUMENTS chain. */ + + 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, this is a vector sorted by their DECL_UIDs + to map them to their indices in the DECL_ARGUMENT chain. */ + vec *m_uid_to_idx; }; inline