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
