From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 5933D3858C52; Sun, 20 Nov 2022 18:04:56 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5933D3858C52 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1668967496; bh=tpHvCSDk8x5mm5+UEBaFTVOUHIaCgLud5WmUAt5vIP8=; h=From:To:Subject:Date:From; b=BgveDtHkzS9YXQ2Qn6Z+bIdOKAHvJb1y8kKf44lieWwEF/0Lv4Am7fAlemjs1qGdu O3DHlNwrWe/Tdpwp1iUidNDDIwqp9Rae6JyI7gcsA1EkaEJdmYyuFp5SaTc7xrJPMt vcrDrlRGbSbLtClPWeGO28cICloHYRrBZBPO3q7I= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-4177] c++: cache the normal form of a concept-id X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: b36a5f8404d7c3681435b497ef6b27d69cba0a14 X-Git-Newrev: 1ad735dbfcce07dd913f82308619324171825c58 Message-Id: <20221120180456.5933D3858C52@sourceware.org> Date: Sun, 20 Nov 2022 18:04:56 +0000 (GMT) List-Id: https://gcc.gnu.org/g:1ad735dbfcce07dd913f82308619324171825c58 commit r13-4177-g1ad735dbfcce07dd913f82308619324171825c58 Author: Patrick Palka 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 concept complicated = /* ... */; template void f() requires complicated && /* ... */; template void g() requires complicated && /* ... */; then despite this high-level caching we'd still redundantly have to expand the concept-id complicated 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 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 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 +{ + 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_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::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 (); + **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::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 (normalized_map, tmpl, norm); + { + norm_entry **slot = norm_cache->find_slot (&entry, INSERT); + entry.norm = norm; + *slot = ggc_alloc (); + **slot = entry; + } return norm; }