From 343d83c7a89d0c7a78139e685395228115a28f6e Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Fri, 10 Jun 2022 16:10:02 -0400 Subject: [PATCH] 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/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 7f3b3c3..29fc365 100644 --- a/gcc/cp/decl.cc +++ b/gcc/cp/decl.cc @@ -4007,14 +4007,24 @@ struct typename_hasher : ggc_ptr_hash /* 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 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); } } -- 2.7.4