Re: [PATCH 1/2] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS

[Richard Biener <richard.guenther@gmail.com>]

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
>