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

Jason Merrill via Gcc-patches Fri, 18 Nov 2022 18:57:22 -0800

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

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

Reply via email to