c++: improve TYPENAME_TYPE hashing [PR65328]

  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(-)
  

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);
>   	      }
>   	  }