On 6/10/22 09:40, Patrick Palka wrote:
The reason compiling the testcase in this PR is so slow is ultimately
due to our poor hashing of TYPENAME_TYPE causing a huge amount of hash
table collisions in the spec_hasher and typename_hasher tables.
In spec_hasher, we don't hash the components of a TYPENAME_TYPE at all,
presumably because TYPENAME_TYPE equivalence as determined by
structural_comptypes depends on whether the comparing_specializations
flag is set. This patch fixes this by setting comparing_specializations
from spec_hasher::hash, and making iterative_hash_template_arg hash the
relevant components of a TYPENAME_TYPE when this flag is set.
consistently.
And in typename_hasher, the hash function doesn't consider the
TYPENAME_TYPE_FULLNAME, which this patch fixes accordingly.
After this patch, compile time for the testcase in the PR is around
34 seconds (10% faster than Clang).
Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK
for trunk?
PR c++/65328
gcc/cp/ChangeLog:
* decl.cc (typename_hasher::hash): Add extra overloads.
Use iterative_hash_object instead of htab_hash_pointer.
Hash the TYPENAME_TYPE_FULLNAME too.
(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.
---
gcc/cp/decl.cc | 26 +++++++++++++++++++-------
gcc/cp/pt.cc | 28 ++++++++++++++++++++++++----
2 files changed, 43 insertions(+), 11 deletions(-)
diff --git a/gcc/cp/decl.cc b/gcc/cp/decl.cc
index 7f3b3c3c588..b7f624ca50b 100644
--- a/gcc/cp/decl.cc
+++ b/gcc/cp/decl.cc
@@ -4007,14 +4007,27 @@ struct typename_hasher : ggc_ptr_hash<tree_node>
/* Hash a TYPENAME_TYPE. */
static hashval_t
- hash (tree t)
+ hash (tree context, tree name, tree fullname)
{
- hashval_t hash;
+ hashval_t hash = 0;
+ hash = iterative_hash_object (context, hash);
+ hash = iterative_hash_object (name, hash);
I'd think we could omit considering 'name', since fullname is either the
same as name or a wrapper for it?
+ 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->name, ti->template_id);
+ }
- return hash;
+ static hashval_t
+ hash (tree t)
+ {
+ return typename_hasher::hash (TYPE_CONTEXT (t),
+ TYPE_IDENTIFIER (t),
+ TYPENAME_TYPE_FULLNAME (t));
}
/* Compare two TYPENAME_TYPEs. */
@@ -4053,8 +4066,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 55129cf6f2c..381fc337cb0 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -107,6 +107,7 @@ static bool excessive_deduction_depth;
struct spec_hasher : ggc_ptr_hash<spec_entry>
{
static hashval_t hash (spec_entry *);
+ static hashval_t hash (tree, tree);
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,16 @@ 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)
Please add a comment that this is to match structural_comptypes.
OK with these changes.
+ {
+ 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 +14136,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 +14439,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)
{
@@ -14958,7 +14978,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);
}
}
