From 343d83c7a89d0c7a78139e685395228115a28f6e Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Fri, 10 Jun 2022 16:10:02 -0400 Subject: 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) : 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. --- gcc/cp/pt.cc | 33 +++++++++++++++++++++++++++++---- 1 file changed, 29 insertions(+), 4 deletions(-) (limited to 'gcc/cp/pt.cc') diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc index 1f91fc2..28edc6a 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 { + 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); } } -- cgit v1.1