public inbox for gcc-cvs@sourceware.org help / color / mirror / Atom feed
From: Patrick Palka <ppalka@gcc.gnu.org> To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-1047] c++: improve TYPENAME_TYPE hashing [PR65328] Date: Fri, 10 Jun 2022 20:10:49 +0000 (GMT) [thread overview] Message-ID: <20220610201049.C9C55385627E@sourceware.org> (raw) https://gcc.gnu.org/g:343d83c7a89d0c7a78139e685395228115a28f6e commit r13-1047-g343d83c7a89d0c7a78139e685395228115a28f6e Author: Patrick Palka <ppalka@redhat.com> Date: Fri Jun 10 16:10:02 2022 -0400 c++: improve TYPENAME_TYPE hashing [PR65328] For the testcase in this PR, compilation takes very long ultimately due to our poor hashing of TYPENAME_TYPE causing a huge number of collisions in the spec_hasher and typename_hasher tables. In spec_hasher, we don't hash the components of TYPENAME_TYPE, which means most TYPENAME_TYPE arguments end up contributing the same hash. This is the safe thing to do uniformly since structural_comptypes may try resolving a TYPENAME_TYPE via the current instantiation. But this behavior of structural_comptypes is suppressed from spec_hasher::equal via the comparing_specializations flag, which means spec_hasher::hash can assume it's disabled too. To that end, this patch makes spec_hasher::hash set the flag, and teaches iterative_hash_template_arg to hash the relevant components of TYPENAME_TYPE when the flag is set. And in typename_hasher, the hash function considers TYPE_IDENTIFIER instead of the more informative TYPENAME_TYPE_FULLNAME, which this patch fixes accordingly. After this patch, compile time for the testcase in the PR falls to around 30 seconds on my machine (down from dozens of minutes). PR c++/65328 gcc/cp/ChangeLog: * decl.cc (typename_hasher::hash): Add extra overloads. Use iterative_hash_object instead of htab_hash_pointer. Hash TYPENAME_TYPE_FULLNAME instead of TYPE_IDENTIFIER. (build_typename_type): Use typename_hasher::hash. * pt.cc (spec_hasher::hash): Add two-parameter overload. Set comparing_specializations around the call to hash_tmpl_and_args. (iterative_hash_template_arg) <case TYPENAME_TYPE>: When comparing_specializations, hash the TYPE_CONTEXT and TYPENAME_TYPE_FULLNAME. (tsubst_function_decl): Use spec_hasher::hash instead of hash_tmpl_and_args. (tsubst_template_decl): Likewise. (tsubst_decl): Likewise. Diff: --- gcc/cp/decl.cc | 23 ++++++++++++++++------- gcc/cp/pt.cc | 33 +++++++++++++++++++++++++++++---- 2 files changed, 45 insertions(+), 11 deletions(-) diff --git a/gcc/cp/decl.cc b/gcc/cp/decl.cc index 7f3b3c3c588..29fc36534c2 100644 --- a/gcc/cp/decl.cc +++ b/gcc/cp/decl.cc @@ -4007,14 +4007,24 @@ struct typename_hasher : ggc_ptr_hash<tree_node> /* Hash a TYPENAME_TYPE. */ static hashval_t - hash (tree t) + hash (tree context, tree fullname) { - hashval_t hash; + hashval_t hash = 0; + hash = iterative_hash_object (context, hash); + hash = iterative_hash_object (fullname, hash); + return hash; + } - hash = (htab_hash_pointer (TYPE_CONTEXT (t)) - ^ htab_hash_pointer (TYPE_IDENTIFIER (t))); + static hashval_t + hash (const typename_info *ti) + { + return typename_hasher::hash (ti->scope, ti->template_id); + } - return hash; + static hashval_t + hash (tree t) + { + return typename_hasher::hash (TYPE_CONTEXT (t), TYPENAME_TYPE_FULLNAME (t)); } /* Compare two TYPENAME_TYPEs. */ @@ -4053,8 +4063,7 @@ build_typename_type (tree context, tree name, tree fullname, ti.class_p = (tag_type == class_type || tag_type == record_type || tag_type == union_type); - hashval_t hash = (htab_hash_pointer (ti.scope) - ^ htab_hash_pointer (ti.name)); + hashval_t hash = typename_hasher::hash (&ti); /* See if we already have this type. */ tree *e = typename_htab->find_slot_with_hash (&ti, hash, INSERT); diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc index 1f91fc20f7f..28edc6ae988 100644 --- a/gcc/cp/pt.cc +++ b/gcc/cp/pt.cc @@ -106,6 +106,7 @@ static bool excessive_deduction_depth; struct spec_hasher : ggc_ptr_hash<spec_entry> { + static hashval_t hash (tree, tree); static hashval_t hash (spec_entry *); static bool equal (spec_entry *, spec_entry *); }; @@ -1768,13 +1769,22 @@ hash_tmpl_and_args (tree tmpl, tree args) return iterative_hash_template_arg (args, val); } +hashval_t +spec_hasher::hash (tree tmpl, tree args) +{ + ++comparing_specializations; + hashval_t val = hash_tmpl_and_args (tmpl, args); + --comparing_specializations; + return val; +} + /* Returns a hash for a spec_entry node based on the TMPL and ARGS members, ignoring SPEC. */ hashval_t spec_hasher::hash (spec_entry *e) { - return hash_tmpl_and_args (e->tmpl, e->args); + return spec_hasher::hash (e->tmpl, e->args); } /* Recursively calculate a hash value for a template argument ARG, for use @@ -1960,6 +1970,21 @@ iterative_hash_template_arg (tree arg, hashval_t val) val = iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val); break; + case TYPENAME_TYPE: + if (comparing_specializations) + { + /* Hash the components that are relevant to TYPENAME_TYPE + equivalence as determined by structural_comptypes. We + can only coherently do this when comparing_specializations + is set, because otherwise structural_comptypes tries + resolving TYPENAME_TYPE via the current instantiation. */ + tree context = TYPE_MAIN_VARIANT (TYPE_CONTEXT (arg)); + tree fullname = TYPENAME_TYPE_FULLNAME (arg); + val = iterative_hash_template_arg (context, val); + val = iterative_hash_template_arg (fullname, val); + } + break; + default: if (tree canonical = TYPE_CANONICAL (arg)) val = iterative_hash_object (TYPE_HASH (canonical), val); @@ -14116,7 +14141,7 @@ tsubst_function_decl (tree t, tree args, tsubst_flags_t complain, /* Check to see if we already have this specialization. */ if (!lambda_fntype) { - hash = hash_tmpl_and_args (gen_tmpl, argvec); + hash = spec_hasher::hash (gen_tmpl, argvec); if (tree spec = retrieve_specialization (gen_tmpl, argvec, hash)) /* The spec for these args might be a partial instantiation of the template, but here what we want is the FUNCTION_DECL. */ @@ -14419,7 +14444,7 @@ tsubst_template_decl (tree t, tree args, tsubst_flags_t complain, if (full_args == tmpl_args) return t; - hash = hash_tmpl_and_args (t, full_args); + hash = spec_hasher::hash (t, full_args); spec = retrieve_specialization (t, full_args, hash); if (spec != NULL_TREE) { @@ -14963,7 +14988,7 @@ tsubst_decl (tree t, tree args, tsubst_flags_t complain) if (argvec == error_mark_node) RETURN (error_mark_node); } - hash = hash_tmpl_and_args (gen_tmpl, argvec); + hash = spec_hasher::hash (gen_tmpl, argvec); spec = retrieve_specialization (gen_tmpl, argvec, hash); } }
reply other threads:[~2022-06-10 20:10 UTC|newest] Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
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=20220610201049.C9C55385627E@sourceware.org \ --to=ppalka@gcc.gnu.org \ --cc=gcc-cvs@gcc.gnu.org \ /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: linkBe 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).