* [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS @ 2023-05-29 16:19 Martin Jambor 2023-05-30 6:58 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Martin Jambor @ 2023-05-29 16:19 UTC (permalink / raw) To: GCC Patches; +Cc: Jan Hubicka 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 <mjambor@suse.cz> * 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<const_tree, unsigned>::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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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<ipa_argagg_value, va_gc> *m_agg_values; - /* Known bits information. */ - vec<ipa_bits *, va_gc> *bits; - /* Value range information. */ - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; + /* Known bits information. */ + vec<ipa_bits *, va_gc> *bits; + /* Value range information. */ + vec<ipa_vr, va_gc> *m_vr; + /* If there are many parameters, a hash map to speed-up look-ups of their + indices. */ + hash_map<const_tree, unsigned> *m_tree_to_idx; }; inline -- 2.40.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 2023-05-29 16:19 [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS Martin Jambor @ 2023-05-30 6:58 ` Richard Biener 2023-05-30 14:21 ` Jan Hubicka 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2023-05-30 6:58 UTC (permalink / raw) To: Martin Jambor; +Cc: GCC Patches, Jan Hubicka On Mon, May 29, 2023 at 6:20 PM Martin Jambor <mjambor@suse.cz> wrote: > > 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. Since ipcp_transformation is short-lived (is it?) is it worth the trouble? Comments below ... > 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 <mjambor@suse.cz> > > * 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<const_tree, unsigned>::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); I think allocating the hash-map with 'c' for some numbers (depending on the "prime" chosen) will necessarily cause re-allocation of the hash since we keep a load factor of at most 3/4 upon insertion. But - I wonder if a UID sorted array isn't a very much better data structure for this? That is, a vec<std::pair<int, unsigned> >? > +} > 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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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<ipa_argagg_value, va_gc> *m_agg_values; > - /* Known bits information. */ > - vec<ipa_bits *, va_gc> *bits; > - /* Value range information. */ > - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; > + /* Known bits information. */ > + vec<ipa_bits *, va_gc> *bits; > + /* Value range information. */ > + vec<ipa_vr, va_gc> *m_vr; > + /* If there are many parameters, a hash map to speed-up look-ups of their > + indices. */ > + hash_map<const_tree, unsigned> *m_tree_to_idx; > }; > > inline > -- > 2.40.1 > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 2023-05-30 6:58 ` Richard Biener @ 2023-05-30 14:21 ` Jan Hubicka 2023-05-31 7:03 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Jan Hubicka @ 2023-05-30 14:21 UTC (permalink / raw) To: Richard Biener; +Cc: Martin Jambor, GCC Patches > On Mon, May 29, 2023 at 6:20 PM Martin Jambor <mjambor@suse.cz> wrote: > > > > 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. > > Since ipcp_transformation is short-lived (is it?) is it worth the trouble? > Comments below ... It lives from ipa-cp time to WPA stream-out or IPA transform stage, so memory consumption is a concern with -flto. > > + m_tree_to_idx = hash_map<const_tree, unsigned>::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); > > I think allocating the hash-map with 'c' for some numbers (depending > on the "prime" > chosen) will necessarily cause re-allocation of the hash since we keep a load > factor of at most 3/4 upon insertion. > > But - I wonder if a UID sorted array isn't a very much better data > structure for this? > That is, a vec<std::pair<int, unsigned> >? Yeah, I was thinking along this lines too. Having field directly in PARM_DECL node would be probably prettiest. In general this is probably not that important as wast amount of time we have few parameters and linear lookup is just fine. Honza > > > +} > > 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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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<ipa_argagg_value, va_gc> *m_agg_values; > > - /* Known bits information. */ > > - vec<ipa_bits *, va_gc> *bits; > > - /* Value range information. */ > > - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; > > + /* Known bits information. */ > > + vec<ipa_bits *, va_gc> *bits; > > + /* Value range information. */ > > + vec<ipa_vr, va_gc> *m_vr; > > + /* If there are many parameters, a hash map to speed-up look-ups of their > > + indices. */ > > + hash_map<const_tree, unsigned> *m_tree_to_idx; > > }; > > > > inline > > -- > > 2.40.1 > > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 2023-05-30 14:21 ` Jan Hubicka @ 2023-05-31 7:03 ` Richard Biener 2023-05-31 16:08 ` Martin Jambor 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2023-05-31 7:03 UTC (permalink / raw) To: Jan Hubicka; +Cc: Martin Jambor, GCC Patches On Tue, May 30, 2023 at 4:21 PM Jan Hubicka <hubicka@ucw.cz> wrote: > > > On Mon, May 29, 2023 at 6:20 PM Martin Jambor <mjambor@suse.cz> wrote: > > > > > > 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. > > > > Since ipcp_transformation is short-lived (is it?) is it worth the trouble? > > Comments below ... > > It lives from ipa-cp time to WPA stream-out or IPA transform stage, > so memory consumption is a concern with -flto. > > > + m_tree_to_idx = hash_map<const_tree, unsigned>::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); > > > > I think allocating the hash-map with 'c' for some numbers (depending > > on the "prime" > > chosen) will necessarily cause re-allocation of the hash since we keep a load > > factor of at most 3/4 upon insertion. > > > > But - I wonder if a UID sorted array isn't a very much better data > > structure for this? > > That is, a vec<std::pair<int, unsigned> >? > > Yeah, I was thinking along this lines too. > Having field directly in PARM_DECL node would be probably prettiest. > In general this is probably not that important as wast amount of time we > have few parameters and linear lookup is just fine. There is 6 bits of DECL_OFFSET_ALIGN that could be re-purposed, but 64 parameters is a bit low. _Maybe_ PARM_DECL doesn't need any of the tree_base bits so could use the full word for sth else as well ... I also though it might be interesting to only record PARM_DECLs that we have interesting info for and skip VARYING ones. So with an indirection DECL_OFFSET_ALIGN -> index to non-varying param or -1 the encoding space could shrink. But still using a vec<> looks like a straight-forward improvement here. Richard. > Honza > > > > > +} > > > 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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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<ipa_argagg_value, va_gc> *m_agg_values; > > > - /* Known bits information. */ > > > - vec<ipa_bits *, va_gc> *bits; > > > - /* Value range information. */ > > > - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; > > > + /* Known bits information. */ > > > + vec<ipa_bits *, va_gc> *bits; > > > + /* Value range information. */ > > > + vec<ipa_vr, va_gc> *m_vr; > > > + /* If there are many parameters, a hash map to speed-up look-ups of their > > > + indices. */ > > > + hash_map<const_tree, unsigned> *m_tree_to_idx; > > > }; > > > > > > inline > > > -- > > > 2.40.1 > > > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 2023-05-31 7:03 ` Richard Biener @ 2023-05-31 16:08 ` Martin Jambor 2023-06-02 8:36 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Martin Jambor @ 2023-05-31 16:08 UTC (permalink / raw) To: Richard Biener, Jan Hubicka; +Cc: GCC Patches Hello, On Wed, May 31 2023, Richard Biener wrote: > On Tue, May 30, 2023 at 4:21 PM Jan Hubicka <hubicka@ucw.cz> wrote: >> >> > On Mon, May 29, 2023 at 6:20 PM Martin Jambor <mjambor@suse.cz> wrote: >> > > >> > > 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. >> > >> > Since ipcp_transformation is short-lived (is it?) is it worth the trouble? >> > Comments below ... >> >> It lives from ipa-cp time to WPA stream-out or IPA transform stage, >> so memory consumption is a concern with -flto. It lives longer, until the function is finished, it holds the information we want to use during PRE, after all (and Honza also already added queries to it to tree-ssa-ccp.cc though those probably could be avoided). The proposed mapping for long chains would only be created in the transformation IPA-CP hook, so would only live in LTRANS and only throughout the compilation of a single function. (But I am adding a pointer to the transformation summary of all.) >> > > + m_tree_to_idx = hash_map<const_tree, unsigned>::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); >> > >> > I think allocating the hash-map with 'c' for some numbers (depending >> > on the "prime" >> > chosen) will necessarily cause re-allocation of the hash since we keep a load >> > factor of at most 3/4 upon insertion. Oh, right. >> > >> > But - I wonder if a UID sorted array isn't a very much better data >> > structure for this? >> > That is, a vec<std::pair<int, unsigned> >? >> >> Yeah, I was thinking along this lines too. >> Having field directly in PARM_DECL node would be probably prettiest. >> In general this is probably not that important as wast amount of time we >> have few parameters and linear lookup is just fine. > > There is 6 bits of DECL_OFFSET_ALIGN that could be re-purposed, but > 64 parameters is a bit low. _Maybe_ PARM_DECL doesn't need any of > the tree_base bits so could use the full word for sth else as well ... > > I also though it might be interesting to only record PARM_DECLs that > we have interesting info for and skip VARYING ones. So with an > indirection DECL_OFFSET_ALIGN -> index to non-varying param or > -1 the encoding space could shrink. > > But still using a vec<> looks like a straight-forward improvement here. Yeah, 64 parameters seems too tight. I guess a testcase in which we would record information for that many parameters would be quite artificial, but I can imagine something like that in machine generated code. Below is the patch based on DECL_UIDs in a vector. The problem with std::pair is that it is not GC-friendly and the transformation summary unfortunately needs to live in GC. So I added a simple GTY marked structure. Bootstrapped, tested and (together with the subsequent patch) LTO bootstrapped on an x86_64-linux, as is and with lower threshold to create the mapping. OK for master now? Thanks, Martin Subject: [PATCH 1/2] 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 <mjambor@suse.cz> * 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. --- 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 0f37bb5e336..fb069bf2319 100644 --- a/gcc/ipa-cp.cc +++ b/gcc/ipa-cp.cc @@ -6761,3 +6761,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 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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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..c570e8ec25a 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<ipa_argagg_value, va_gc> *m_agg_values; - /* Known bits information. */ - vec<ipa_bits *, va_gc> *bits; - /* Value range information. */ - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; + /* Known bits information. */ + vec<ipa_bits *, va_gc> *bits; + /* Value range information. */ + vec<ipa_vr, va_gc> *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<ipa_uid_to_idx_map_elt, va_gc> *m_uid_to_idx; }; inline -- 2.40.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS 2023-05-31 16:08 ` Martin Jambor @ 2023-06-02 8:36 ` Richard Biener 0 siblings, 0 replies; 6+ messages in thread From: Richard Biener @ 2023-06-02 8:36 UTC (permalink / raw) To: Martin Jambor; +Cc: Jan Hubicka, GCC Patches On Wed, May 31, 2023 at 6:08 PM Martin Jambor <mjambor@suse.cz> wrote: > > Hello, > > On Wed, May 31 2023, Richard Biener wrote: > > On Tue, May 30, 2023 at 4:21 PM Jan Hubicka <hubicka@ucw.cz> wrote: > >> > >> > On Mon, May 29, 2023 at 6:20 PM Martin Jambor <mjambor@suse.cz> wrote: > >> > > > >> > > 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. > >> > > >> > Since ipcp_transformation is short-lived (is it?) is it worth the trouble? > >> > Comments below ... > >> > >> It lives from ipa-cp time to WPA stream-out or IPA transform stage, > >> so memory consumption is a concern with -flto. > > It lives longer, until the function is finished, it holds the > information we want to use during PRE, after all (and Honza also already > added queries to it to tree-ssa-ccp.cc though those probably could be > avoided). > > The proposed mapping for long chains would only be created in the > transformation IPA-CP hook, so would only live in LTRANS and only > throughout the compilation of a single function. (But I am adding a > pointer to the transformation summary of all.) > > >> > > + m_tree_to_idx = hash_map<const_tree, unsigned>::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); > >> > > >> > I think allocating the hash-map with 'c' for some numbers (depending > >> > on the "prime" > >> > chosen) will necessarily cause re-allocation of the hash since we keep a load > >> > factor of at most 3/4 upon insertion. > > Oh, right. > > >> > > >> > But - I wonder if a UID sorted array isn't a very much better data > >> > structure for this? > >> > That is, a vec<std::pair<int, unsigned> >? > >> > >> Yeah, I was thinking along this lines too. > >> Having field directly in PARM_DECL node would be probably prettiest. > >> In general this is probably not that important as wast amount of time we > >> have few parameters and linear lookup is just fine. > > > > There is 6 bits of DECL_OFFSET_ALIGN that could be re-purposed, but > > 64 parameters is a bit low. _Maybe_ PARM_DECL doesn't need any of > > the tree_base bits so could use the full word for sth else as well ... > > > > I also though it might be interesting to only record PARM_DECLs that > > we have interesting info for and skip VARYING ones. So with an > > indirection DECL_OFFSET_ALIGN -> index to non-varying param or > > -1 the encoding space could shrink. > > > > But still using a vec<> looks like a straight-forward improvement here. > > Yeah, 64 parameters seems too tight. I guess a testcase in which we > would record information for that many parameters would be quite > artificial, but I can imagine something like that in machine generated > code. > > Below is the patch based on DECL_UIDs in a vector. The problem with > std::pair is that it is not GC-friendly and the transformation summary > unfortunately needs to live in GC. So I added a simple GTY marked > structure. > > Bootstrapped, tested and (together with the subsequent patch) LTO > bootstrapped on an x86_64-linux, as is and with lower threshold to > create the mapping. OK for master now? LGTM now. Thanks, Richard. > Thanks, > > Martin > > > Subject: [PATCH 1/2] 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 <mjambor@suse.cz> > > * 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. > --- > 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 0f37bb5e336..fb069bf2319 100644 > --- a/gcc/ipa-cp.cc > +++ b/gcc/ipa-cp.cc > @@ -6761,3 +6761,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 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<ipa_bits *, va_gc> &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<ipa_vr, va_gc> &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..c570e8ec25a 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<ipa_argagg_value, va_gc> *m_agg_values; > - /* Known bits information. */ > - vec<ipa_bits *, va_gc> *bits; > - /* Value range information. */ > - vec<ipa_vr, va_gc> *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<ipa_argagg_value, va_gc> *m_agg_values; > + /* Known bits information. */ > + vec<ipa_bits *, va_gc> *bits; > + /* Value range information. */ > + vec<ipa_vr, va_gc> *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<ipa_uid_to_idx_map_elt, va_gc> *m_uid_to_idx; > }; > > inline > -- > 2.40.1 > ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2023-06-02 8:36 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-05-29 16:19 [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS Martin Jambor 2023-05-30 6:58 ` Richard Biener 2023-05-30 14:21 ` Jan Hubicka 2023-05-31 7:03 ` Richard Biener 2023-05-31 16:08 ` Martin Jambor 2023-06-02 8:36 ` Richard Biener
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).