[gcc r14-1997] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS

[gcc r14-1997] ipa-cp: Avoid long linear searches through DECL_ARGUMENTS

[Martin Jambor]

https://gcc.gnu.org/g:7f986e2ed9323099bf142756d282002baa869289

commit r14-1997-g7f986e2ed9323099bf142756d282002baa869289
Author: Martin Jambor <mjambor@suse.cz>
Date:   Tue Jun 20 18:15:22 2023 +0200

    ipa-cp: Avoid long linear searches through DECL_ARGUMENTS
    
    There have been concerns that linear searches through DECL_ARGUMENTS
    that are often necessary to compute the index of a particular
    PARM_DECL which is the key to results of IPA-CP can happen often
    enough to be a compile time issue, especially if we plug the results
    into value numbering, as I intend to do with a follow-up patch.
    
    This patch creates a vector sorted according to PARM_DECLs to do the look-up
    for all functions which have some information discovered by IPA-CP and which
    have 32 parameters or more.  32 is a hard-wired magical constant here to
    capture the trade-off between the memory allocation overhead and length of the
    linear search.  I do not think it is worth making it a --param but if people
    think it appropriate, I can turn it into one.
    
    gcc/ChangeLog:
    
    2023-05-31  Martin Jambor  <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.

Diff:
---
 gcc/ipa-cp.cc   | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/ipa-prop.cc | 44 +++++++++++++++------------------
 gcc/ipa-prop.h  | 44 +++++++++++++++++++++++++++------
 3 files changed, 131 insertions(+), 33 deletions(-)

diff --git a/gcc/ipa-cp.cc b/gcc/ipa-cp.cc
index f0a314c490c..846dcf8a7f3 100644
--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -6779,3 +6779,79 @@ ipa_cp_cc_finalize (void)
   orig_overall_size = 0;
   ipcp_free_transformation_sum ();
 }
+
+/* Given PARAM which must be a parameter of function FNDECL described by THIS,
+   return its index in the DECL_ARGUMENTS chain, using a pre-computed
+   DECL_UID-sorted vector if available (which is pre-computed only if there are
+   many parameters).  Can return -1 if param is static chain not represented
+   among DECL_ARGUMENTS. */
+
+int
+ipcp_transformation::get_param_index (const_tree fndecl, const_tree param) const
+{
+  gcc_assert (TREE_CODE (param) == PARM_DECL);
+  if (m_uid_to_idx)
+    {
+      unsigned puid = DECL_UID (param);
+      const ipa_uid_to_idx_map_elt *res
+	= std::lower_bound (m_uid_to_idx->begin(), m_uid_to_idx->end (), puid,
+			    [] (const ipa_uid_to_idx_map_elt &elt, unsigned uid)
+			    {
+			      return elt.uid < uid;
+			    });
+      if (res == m_uid_to_idx->end ()
+	  || res->uid != puid)
+	{
+	  gcc_assert (DECL_STATIC_CHAIN (fndecl));
+	  return -1;
+	}
+      return res->index;
+    }
+
+  unsigned index = 0;
+  for (tree p = DECL_ARGUMENTS (fndecl); p; p = DECL_CHAIN (p), index++)
+    if (p == param)
+      return (int) index;
+
+  gcc_assert (DECL_STATIC_CHAIN (fndecl));
+  return -1;
+}
+
+/* Helper function to qsort a vector of ipa_uid_to_idx_map_elt elements
+   according to the uid.  */
+
+static int
+compare_uids (const void *a, const void *b)
+{
+  const ipa_uid_to_idx_map_elt *e1 = (const ipa_uid_to_idx_map_elt *) a;
+  const ipa_uid_to_idx_map_elt *e2 = (const ipa_uid_to_idx_map_elt *) b;
+  if (e1->uid < e2->uid)
+    return -1;
+  if (e1->uid > e2->uid)
+    return 1;
+  gcc_unreachable ();
+}
+
+/* Assuming THIS describes FNDECL and it has sufficiently many parameters to
+   justify the overhead, create a DECL_UID-sorted vector to speed up mapping
+   from parameters to their indices in DECL_ARGUMENTS chain.  */
+
+void
+ipcp_transformation::maybe_create_parm_idx_map (tree fndecl)
+{
+  int c = count_formal_params (fndecl);
+  if (c < 32)
+    return;
+
+  m_uid_to_idx = NULL;
+  vec_safe_reserve (m_uid_to_idx, c, true);
+  unsigned index = 0;
+  for (tree p = DECL_ARGUMENTS (fndecl); p; p = DECL_CHAIN (p), index++)
+    {
+      ipa_uid_to_idx_map_elt elt;
+      elt.uid = DECL_UID (p);
+      elt.index = index;
+      m_uid_to_idx->quick_push (elt);
+    }
+  m_uid_to_idx->qsort (compare_uids);
+}
diff --git a/gcc/ipa-prop.cc b/gcc/ipa-prop.cc
index eea81176864..704fe01b02c 100644
--- a/gcc/ipa-prop.cc
+++ b/gcc/ipa-prop.cc
@@ -5778,16 +5778,9 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_int *mask)
   if (!ts || vec_safe_length (ts->bits) == 0)
     return false;
 
-  int i = 0;
-  for (tree p = DECL_ARGUMENTS (current_function_decl);
-       p != parm; p = DECL_CHAIN (p))
-    {
-      i++;
-      /* Ignore static chain.  */
-      if (!p)
-	return false;
-    }
-
+  int i = ts->get_param_index (current_function_decl, parm);
+  if (i < 0)
+    return false;
   clone_info *cinfo = clone_info::get (cnode);
   if (cinfo && cinfo->param_adjustments)
     {
@@ -5804,16 +5797,12 @@ ipcp_get_parm_bits (tree parm, tree *value, widest_int *mask)
   return true;
 }
 
-
-/* Update bits info of formal parameters as described in
-   ipcp_transformation.  */
+/* Update bits info of formal parameters of NODE as described in TS.  */
 
 static void
-ipcp_update_bits (struct cgraph_node *node)
+ipcp_update_bits (struct cgraph_node *node, ipcp_transformation *ts)
 {
-  ipcp_transformation *ts = ipcp_get_transformation_summary (node);
-
-  if (!ts || vec_safe_length (ts->bits) == 0)
+  if (vec_safe_is_empty (ts->bits))
     return;
   vec<ipa_bits *, va_gc> &bits = *ts->bits;
   unsigned count = bits.length ();
@@ -5915,14 +5904,12 @@ ipcp_update_bits (struct cgraph_node *node)
     }
 }
 
-/* Update value range of formal parameters as described in
-   ipcp_transformation.  */
+/* Update value range of formal parameters of NODE as described in TS.  */
 
 static void
-ipcp_update_vr (struct cgraph_node *node)
+ipcp_update_vr (struct cgraph_node *node, ipcp_transformation *ts)
 {
-  ipcp_transformation *ts = ipcp_get_transformation_summary (node);
-  if (!ts || vec_safe_length (ts->m_vr) == 0)
+  if (vec_safe_is_empty (ts->m_vr))
     return;
   const vec<ipa_vr, va_gc> &vr = *ts->m_vr;
   unsigned count = vr.length ();
@@ -5998,10 +5985,17 @@ ipcp_transform_function (struct cgraph_node *node)
     fprintf (dump_file, "Modification phase of node %s\n",
 	     node->dump_name ());
 
-  ipcp_update_bits (node);
-  ipcp_update_vr (node);
   ipcp_transformation *ts = ipcp_get_transformation_summary (node);
-  if (!ts || vec_safe_is_empty (ts->m_agg_values))
+  if (!ts
+      || (vec_safe_is_empty (ts->m_agg_values)
+	  && vec_safe_is_empty (ts->bits)
+	  && vec_safe_is_empty (ts->m_vr)))
+    return 0;
+
+  ts->maybe_create_parm_idx_map (cfun->decl);
+  ipcp_update_bits (node, ts);
+  ipcp_update_vr (node, ts);
+  if (vec_safe_is_empty (ts->m_agg_values))
       return 0;
   param_count = count_formal_params (node->decl);
   if (param_count == 0)
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 3a591a8f44d..9b7fee4c930 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -921,20 +921,24 @@ ipa_is_param_used_by_polymorphic_call (class ipa_node_params *info, int i)
   return (*info->descriptors)[i].used_by_polymorphic_call;
 }
 
+/* GTY-marked structure used to map DECL_UIDs of APRAMs to their indices in
+   their DECL_ARGUMENTs chain.  */
+struct GTY(()) ipa_uid_to_idx_map_elt
+{
+  /* DECL_UID of the PARAM.  */
+  unsigned uid;
+  /* Its index in the DECL_ARGUMETs chain.  */
+  unsigned index;
+};
+
 /* Structure holding information for the transformation phase of IPA-CP.  */
 
 struct GTY(()) ipcp_transformation
 {
-  /* Known aggregate values.  */
-  vec<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