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

  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(-)
  

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
>
  

> 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
> >
  

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
> > >
  

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
  

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
>