[PATCH] c++: cache the normal form of a concept-id

[PATCH] c++: cache the normal form of a concept-id

[Patrick Palka]

We already cache the overall normal form of a declaration's constraints
under the assumption that it can't change over the translation unit.
But if we have two constrained declarations such as

  template<class T> void f() requires expensive<T> && A<T>;
  template<class T> void g() requires expensive<T> && B<T>;

then despite this high-level caching we'd still redundantly have to
expand the concept-id expensive<T> twice, once during normalization of
f's constraints and again during normalization of g's.  Ideally, we'd
reuse the previously computed normal form of expensive<T> the second
time around.

To that end this patch introduces an intermediate layer of caching
during constraint normalization -- caching of the normal form of a
concept-id -- that sits between our high-level caching of the overall
normal form of a declaration's constraints and our low-level caching of
each individual atomic constraint.

It turns out this caching generalizes some ad-hoc caching of the normal
form of concept definition (which is equivalent to the normal form of
the concept-id C<gtargs> where gtargs are C's generic arguments) so
this patch unifies the caching accordingly.

This change improves compile time/memory usage for e.g. the libstdc++
test std/ranges/adaptors/join.cc by 10%/5%.

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
trunk?

gcc/cp/ChangeLog:

	* constraint.cc (struct norm_entry): Define.
	(struct norm_hasher): Define.
	(norm_cache): Define.
	(normalize_concept_check): Add function comment.  Cache the
	result of concept-id normalization.  Canonicalize generic
	arguments as NULL_TREE.  Don't coerce arguments unless
	substitution occurred.
	(normalize_concept_definition): Simplify.  Use norm_cache
	instead of ad-hoc caching.
---
 gcc/cp/constraint.cc | 94 ++++++++++++++++++++++++++++++++++++++------
 1 file changed, 82 insertions(+), 12 deletions(-)

diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index a113d3e269e..c9740b1ec78 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -698,6 +698,40 @@ normalize_logical_operation (tree t, tree args, tree_code c, norm_info info)
   return build2 (c, ci, t0, t1);
 }
 
+/* Data types and hash functions for caching the normal form of a concept-id.
+   This essentially memoizes calls to normalize_concept_check.  */
+
+struct GTY((for_user)) norm_entry
+{
+  /* The CONCEPT_DECL of the concept-id.  */
+  tree tmpl;
+  /* The arguments of the concept-id.  */
+  tree args;
+  /* The normal form of the concept-id.  */
+  tree norm;
+};
+
+struct norm_hasher : ggc_ptr_hash<norm_entry>
+{
+  static hashval_t hash (norm_entry *t)
+  {
+    hashval_t hash = iterative_hash_template_arg (t->tmpl, 0);
+    hash = iterative_hash_template_arg (t->args, hash);
+    return hash;
+  }
+
+  static bool equal (norm_entry *t1, norm_entry *t2)
+  {
+    return t1->tmpl == t2->tmpl
+      && template_args_equal (t1->args, t2->args);
+  }
+};
+
+static GTY((deletable)) hash_table<norm_hasher> *norm_cache;
+
+/* Normalize the concept check CHECK where ARGS are the
+   arguments to be substituted into CHECK's arguments.  */
+
 static tree
 normalize_concept_check (tree check, tree args, norm_info info)
 {
@@ -720,24 +754,53 @@ normalize_concept_check (tree check, tree args, norm_info info)
     targs = tsubst_template_args (targs, args, info.complain, info.in_decl);
   if (targs == error_mark_node)
     return error_mark_node;
+  if (template_args_equal (targs, generic_targs_for (tmpl)))
+    /* Canonicalize generic arguments as NULL_TREE, as an optimization.  */
+    targs = NULL_TREE;
 
   /* Build the substitution for the concept definition.  */
   tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
-  /* Turn on template processing; coercing non-type template arguments
-     will automatically assume they're non-dependent.  */
   ++processing_template_decl;
-  tree subst = coerce_template_parms (parms, targs, tmpl, tf_none);
+  if (targs && args)
+    /* If substitution occurred, coerce the resulting arguments.  */
+    targs = coerce_template_parms (parms, targs, tmpl, tf_none);
   --processing_template_decl;
-  if (subst == error_mark_node)
+  if (targs == error_mark_node)
     return error_mark_node;
 
+  if (!norm_cache)
+    norm_cache = hash_table<norm_hasher>::create_ggc (31);
+  norm_entry entry = {tmpl, targs, NULL_TREE};
+  norm_entry **slot = nullptr;
+  hashval_t hash = 0;
+  if (!info.generate_diagnostics ())
+    {
+      /* If we're not diagnosing, cache the normal form of the
+	 substituted concept-id.  */
+      hash = norm_hasher::hash (&entry);
+      slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT);
+      if (*slot)
+	return (*slot)->norm;
+    }
+
   /* The concept may have been ill-formed.  */
   tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
   if (def == error_mark_node)
     return error_mark_node;
 
   info.update_context (check, args);
-  return normalize_expression (def, subst, info);
+  tree norm = normalize_expression (def, targs, info);
+  if (slot)
+    {
+      /* Recompute SLOT, as norm_cache may have been expanded during
+	 a recursive call.  */
+      slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT);
+      gcc_checking_assert (!*slot);
+      entry.norm = norm;
+      *slot = ggc_alloc<norm_entry> ();
+      **slot = entry;
+    }
+  return norm;
 }
 
 /* Used by normalize_atom to cache ATOMIC_CONSTRs.  */
@@ -941,15 +1004,17 @@ get_normalized_constraints_from_decl (tree d, bool diag = false)
 /* Returns the normal form of TMPL's definition.  */
 
 static tree
-normalize_concept_definition (tree tmpl, bool diag = false)
+normalize_concept_definition (tree tmpl, bool diag)
 {
+  if (!norm_cache)
+    norm_cache = hash_table<norm_hasher>::create_ggc (31);
+
+  norm_entry entry = {tmpl, NULL_TREE, NULL_TREE};
+
   if (!diag)
-    if (tree *p = hash_map_safe_get (normalized_map, tmpl))
-      return *p;
+    if (norm_entry *found = norm_cache->find (&entry))
+      return found->norm;
 
-  gcc_assert (concept_definition_p (tmpl));
-  if (OVL_P (tmpl))
-    tmpl = OVL_FIRST (tmpl);
   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
   tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
   ++processing_template_decl;
@@ -958,7 +1023,12 @@ normalize_concept_definition (tree tmpl, bool diag = false)
   --processing_template_decl;
 
   if (!diag)
-    hash_map_safe_put<hm_ggc> (normalized_map, tmpl, norm);
+    {
+      norm_entry **slot = norm_cache->find_slot (&entry, INSERT);
+      entry.norm = norm;
+      *slot = ggc_alloc<norm_entry> ();
+      **slot = entry;
+    }
 
   return norm;
 }
-- 
2.38.1.436.geea7033409

Re: [PATCH] c++: cache the normal form of a concept-id

[Jason Merrill]

On 11/18/22 16:43, Patrick Palka wrote:
> We already cache the overall normal form of a declaration's constraints
> under the assumption that it can't change over the translation unit.
> But if we have two constrained declarations such as
> 
>    template<class T> void f() requires expensive<T> && A<T>;
>    template<class T> void g() requires expensive<T> && B<T>;
> 
> then despite this high-level caching we'd still redundantly have to
> expand the concept-id expensive<T> twice, once during normalization of
> f's constraints and again during normalization of g's.  Ideally, we'd
> reuse the previously computed normal form of expensive<T> the second
> time around.
> 
> To that end this patch introduces an intermediate layer of caching
> during constraint normalization -- caching of the normal form of a
> concept-id -- that sits between our high-level caching of the overall
> normal form of a declaration's constraints and our low-level caching of
> each individual atomic constraint.
> 
> It turns out this caching generalizes some ad-hoc caching of the normal
> form of concept definition (which is equivalent to the normal form of
> the concept-id C<gtargs> where gtargs are C's generic arguments) so
> this patch unifies the caching accordingly.
> 
> This change improves compile time/memory usage for e.g. the libstdc++
> test std/ranges/adaptors/join.cc by 10%/5%.
> 
> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
> trunk?

Hmm, if we cache at this level, do we still also need to cache the full 
normal form of the decl's constraints?

Exploring that doesn't seem like stage 3 material, though.  The patch is OK.

> gcc/cp/ChangeLog:
> 
> 	* constraint.cc (struct norm_entry): Define.
> 	(struct norm_hasher): Define.
> 	(norm_cache): Define.
> 	(normalize_concept_check): Add function comment.  Cache the
> 	result of concept-id normalization.  Canonicalize generic
> 	arguments as NULL_TREE.  Don't coerce arguments unless
> 	substitution occurred.
> 	(normalize_concept_definition): Simplify.  Use norm_cache
> 	instead of ad-hoc caching.
> ---
>   gcc/cp/constraint.cc | 94 ++++++++++++++++++++++++++++++++++++++------
>   1 file changed, 82 insertions(+), 12 deletions(-)
> 
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index a113d3e269e..c9740b1ec78 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -698,6 +698,40 @@ normalize_logical_operation (tree t, tree args, tree_code c, norm_info info)
>     return build2 (c, ci, t0, t1);
>   }
>   
> +/* Data types and hash functions for caching the normal form of a concept-id.
> +   This essentially memoizes calls to normalize_concept_check.  */
> +
> +struct GTY((for_user)) norm_entry
> +{
> +  /* The CONCEPT_DECL of the concept-id.  */
> +  tree tmpl;
> +  /* The arguments of the concept-id.  */
> +  tree args;
> +  /* The normal form of the concept-id.  */
> +  tree norm;
> +};
> +
> +struct norm_hasher : ggc_ptr_hash<norm_entry>
> +{
> +  static hashval_t hash (norm_entry *t)
> +  {
> +    hashval_t hash = iterative_hash_template_arg (t->tmpl, 0);
> +    hash = iterative_hash_template_arg (t->args, hash);
> +    return hash;
> +  }
> +
> +  static bool equal (norm_entry *t1, norm_entry *t2)
> +  {
> +    return t1->tmpl == t2->tmpl
> +      && template_args_equal (t1->args, t2->args);
> +  }
> +};
> +
> +static GTY((deletable)) hash_table<norm_hasher> *norm_cache;
> +
> +/* Normalize the concept check CHECK where ARGS are the
> +   arguments to be substituted into CHECK's arguments.  */
> +
>   static tree
>   normalize_concept_check (tree check, tree args, norm_info info)
>   {
> @@ -720,24 +754,53 @@ normalize_concept_check (tree check, tree args, norm_info info)
>       targs = tsubst_template_args (targs, args, info.complain, info.in_decl);
>     if (targs == error_mark_node)
>       return error_mark_node;
> +  if (template_args_equal (targs, generic_targs_for (tmpl)))
> +    /* Canonicalize generic arguments as NULL_TREE, as an optimization.  */
> +    targs = NULL_TREE;
>   
>     /* Build the substitution for the concept definition.  */
>     tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
> -  /* Turn on template processing; coercing non-type template arguments
> -     will automatically assume they're non-dependent.  */
>     ++processing_template_decl;
> -  tree subst = coerce_template_parms (parms, targs, tmpl, tf_none);
> +  if (targs && args)
> +    /* If substitution occurred, coerce the resulting arguments.  */
> +    targs = coerce_template_parms (parms, targs, tmpl, tf_none);
>     --processing_template_decl;
> -  if (subst == error_mark_node)
> +  if (targs == error_mark_node)
>       return error_mark_node;
>   
> +  if (!norm_cache)
> +    norm_cache = hash_table<norm_hasher>::create_ggc (31);
> +  norm_entry entry = {tmpl, targs, NULL_TREE};
> +  norm_entry **slot = nullptr;
> +  hashval_t hash = 0;
> +  if (!info.generate_diagnostics ())
> +    {
> +      /* If we're not diagnosing, cache the normal form of the
> +	 substituted concept-id.  */
> +      hash = norm_hasher::hash (&entry);
> +      slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT);
> +      if (*slot)
> +	return (*slot)->norm;
> +    }
> +
>     /* The concept may have been ill-formed.  */
>     tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
>     if (def == error_mark_node)
>       return error_mark_node;
>   
>     info.update_context (check, args);
> -  return normalize_expression (def, subst, info);
> +  tree norm = normalize_expression (def, targs, info);
> +  if (slot)
> +    {
> +      /* Recompute SLOT, as norm_cache may have been expanded during
> +	 a recursive call.  */
> +      slot = norm_cache->find_slot_with_hash (&entry, hash, INSERT);
> +      gcc_checking_assert (!*slot);
> +      entry.norm = norm;
> +      *slot = ggc_alloc<norm_entry> ();
> +      **slot = entry;
> +    }
> +  return norm;
>   }
>   
>   /* Used by normalize_atom to cache ATOMIC_CONSTRs.  */
> @@ -941,15 +1004,17 @@ get_normalized_constraints_from_decl (tree d, bool diag = false)
>   /* Returns the normal form of TMPL's definition.  */
>   
>   static tree
> -normalize_concept_definition (tree tmpl, bool diag = false)
> +normalize_concept_definition (tree tmpl, bool diag)
>   {
> +  if (!norm_cache)
> +    norm_cache = hash_table<norm_hasher>::create_ggc (31);
> +
> +  norm_entry entry = {tmpl, NULL_TREE, NULL_TREE};
> +
>     if (!diag)
> -    if (tree *p = hash_map_safe_get (normalized_map, tmpl))
> -      return *p;
> +    if (norm_entry *found = norm_cache->find (&entry))
> +      return found->norm;
>   
> -  gcc_assert (concept_definition_p (tmpl));
> -  if (OVL_P (tmpl))
> -    tmpl = OVL_FIRST (tmpl);
>     gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
>     tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl));
>     ++processing_template_decl;
> @@ -958,7 +1023,12 @@ normalize_concept_definition (tree tmpl, bool diag = false)
>     --processing_template_decl;
>   
>     if (!diag)
> -    hash_map_safe_put<hm_ggc> (normalized_map, tmpl, norm);
> +    {
> +      norm_entry **slot = norm_cache->find_slot (&entry, INSERT);
> +      entry.norm = norm;
> +      *slot = ggc_alloc<norm_entry> ();
> +      **slot = entry;
> +    }
>   
>     return norm;
>   }