From: Jason Merrill <jason@redhat.com>
To: Patrick Palka <ppalka@redhat.com>, gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] c++: cache the normal form of a concept-id
Date: Fri, 18 Nov 2022 21:57:06 -0500 [thread overview]
Message-ID: <6a811bb5-9032-5fd7-4573-6dee801b6173@redhat.com> (raw)
In-Reply-To: <20221118214339.3620949-1-ppalka@redhat.com>
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;
> }
prev parent reply other threads:[~2022-11-19 2:57 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-18 21:43 Patrick Palka
2022-11-19 2:57 ` Jason Merrill [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=6a811bb5-9032-5fd7-4573-6dee801b6173@redhat.com \
--to=jason@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=ppalka@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).