[gcc r13-4177] c++: cache the normal form of a concept-id

[Patrick Palka <ppalka@gcc.gnu.org>]

https://gcc.gnu.org/g:1ad735dbfcce07dd913f82308619324171825c58

commit r13-4177-g1ad735dbfcce07dd913f82308619324171825c58
Author: Patrick Palka <ppalka@redhat.com>
Date:   Sun Nov 20 13:02:24 2022 -0500

    c++: cache the normal form of a concept-id
    
    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 something like
    
      template<class T> concept complicated = /* ... */;
      template<class T> void f() requires complicated<T> && /* ... */;
      template<class T> void g() requires complicated<T> && /* ... */;
    
    then despite this high-level caching we'd still redundantly have to
    expand the concept-id complicated<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 complicated<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 normalize_concept_check's caching
    of the normal form of a concept definition (which is equivalent to the
    normal form of the concept-id C<gtargs> where gtargs is C's generic
    arguments) so this patch unifies the caching accordingly.
    
    gcc/cp/ChangeLog:
    
            * constraint.cc (struct norm_entry): Define.
            (struct norm_hasher): Define.
            (norm_cache): Define.
            (normalize_concept_check): Add function comment.  Cache the
            the normal form of the substituted concept-id.  Canonicalize
            generic arguments as NULL_TREE.  Don't coerce arguments unless
            they were substituted.
            (normalize_concept_definition): Simplify.  Use norm_cache
            instead of normalized_map.

Diff:
---
 gcc/cp/constraint.cc | 95 ++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 81 insertions(+), 14 deletions(-)

diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index a113d3e269e..ab0f66b3d7e 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -698,6 +698,39 @@ 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 *e)
+  {
+    hashval_t hash = iterative_hash_template_arg (e->tmpl, 0);
+    return iterative_hash_template_arg (e->args, hash);
+  }
+
+  static bool equal (norm_entry *e1, norm_entry *e2)
+  {
+    return e1->tmpl == e2->tmpl
+      && template_args_equal (e1->args, e2->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 +753,52 @@ 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);
-  --processing_template_decl;
-  if (subst == error_mark_node)
+  if (targs && args)
+    /* As an optimization, coerce the arguments only if necessary
+       (i.e. if they were substituted).  */
+    targs = coerce_template_parms (parms, targs, tmpl, tf_none);
+  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 ())
+    {
+      /* Cache the normal form of the substituted concept-id (when not
+	 diagnosing).  */
+      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 since norm_cache may have been expanded during
+	 the 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 +1002,16 @@ 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 +1020,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;
 }