[gcc r13-1047] c++: improve TYPENAME_TYPE hashing [PR65328]

[gcc r13-1047] c++: improve TYPENAME_TYPE hashing [PR65328]

[Patrick Palka]

https://gcc.gnu.org/g:343d83c7a89d0c7a78139e685395228115a28f6e

commit r13-1047-g343d83c7a89d0c7a78139e685395228115a28f6e
Author: Patrick Palka <ppalka@redhat.com>
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) <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.

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<tree_node>
   /* 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<spec_entry>
 {
+  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);
 	      }
 	  }