From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id C9C55385627E; Fri, 10 Jun 2022 20:10:49 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C9C55385627E 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-1047] c++: improve TYPENAME_TYPE hashing [PR65328] X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: f9b5a8e58dfd0642bea932d449ad46da9e57396f X-Git-Newrev: 343d83c7a89d0c7a78139e685395228115a28f6e Message-Id: <20220610201049.C9C55385627E@sourceware.org> Date: Fri, 10 Jun 2022 20:10:49 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 10 Jun 2022 20:10:49 -0000 https://gcc.gnu.org/g:343d83c7a89d0c7a78139e685395228115a28f6e commit r13-1047-g343d83c7a89d0c7a78139e685395228115a28f6e Author: Patrick Palka 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) : 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 /* 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 { + 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); } }