[gcc r13-737] c++: set TYPE_CANONICAL for more template types

[gcc r13-737] c++: set TYPE_CANONICAL for more template types

[Patrick Palka]

https://gcc.gnu.org/g:d0ef9e06197d14d7ba60404e37bd27c21791ba3d

commit r13-737-gd0ef9e06197d14d7ba60404e37bd27c21791ba3d
Author: Patrick Palka <ppalka@redhat.com>
Date:   Tue May 24 09:27:39 2022 -0400

    c++: set TYPE_CANONICAL for more template types
    
    When forming a class template specialization, lookup_template_class
    uses structural equality for the specialized type whenever one of its
    template arguments uses structural equality.  This is the sensible thing
    to do in a vacuum, but given that we already effectively deduplicate class
    specializations via the type_specializations table, we ought to be able
    to safely assume that each class specialization is unique and therefore
    canonical, regardless of the canonicity of the template arguments.
    
    To that end this patch makes us use the canonical type machinery for all
    type specializations, except for the case where a PARM_DECL appears in
    the template arguments (this special case was recently added by
    r12-3766-g72394d38d929c7).
    
    Additionally, this patch makes us use the canonical type machinery for
    TEMPLATE_TEMPLATE_PARMs and BOUND_TEMPLATE_TEMPLATE_PARMs, by extending
    canonical_type_parameter appropriately.  A comment in tsubst says it's
    unsafe to set TYPE_CANONICAL for a lowered TEMPLATE_TEMPLATE_PARM, but
    I'm not sure this is true anymore.  According to Jason, this comment
    (from r120341) became obsolete when later that year r129844 started to
    substitute the template parms of ttps.  Note that r10-7817-ga6f400239d792d
    recently changed process_template_parm to clear TYPE_CANONICAL for
    TEMPLATE_TEMPLATE_PARM consistent with the tsubst comment; this patch
    changes both functions to set instead of clear TYPE_CANONICAL for ttps.
    
    These changes improve compile time of template-heavy code by around 10%
    for me (with a release compiler).  For instance, compile time for the
    libstdc++ test std/ranges/adaptors/all.cc drops from 1.45s to 1.25s, and
    for the range-v3 test test/view/zip.cpp from 5.38s to 4.88s.  The total
    number of calls to structural_comptypes for the latter test drops from
    10.5M to 1.8M.  Memory use is unaffected (as expected).
    
    The new testcase verifies we check the r12-3766 PARM_DECL special case
    in bind_template_template_parm too.
    
    gcc/cp/ChangeLog:
    
            * cp-tree.h (any_template_arguments_need_structural_equality_p):
            Declare.
            * pt.cc (struct ctp_hasher): Define.
            (ctp_table): Define.
            (canonical_type_parameter): Use it.
            (process_template_parm): Set TYPE_CANONICAL for
            TEMPLATE_TEMPLATE_PARM too.
            (lookup_template_class_1): Remove now outdated comment for the
            any_template_arguments_need_structural_equality_p test.
            (tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Don't specifically
            clear TYPE_CANONICAL for ttps.  Set TYPE_CANONICAL on the
            substituted type later.
            (any_template_arguments_need_structural_equality_p): Return
            true for any_targ_node.  Don't return true just because a
            template argument uses structural equality.  Add comment for
            the PARM_DECL special case.
            (rewrite_template_parm): Set TYPE_CANONICAL on the rewritten
            parm's type later.
            * tree.cc (bind_template_template_parm): Set TYPE_CANONICAL
            when safe to do so.
            * typeck.cc (structural_comptypes) [check_alias]: Increment
            processing_template_decl before checking
            dependent_alias_template_spec_p.
    
    gcc/testsuite/ChangeLog:
    
            * g++.dg/cpp0x/constexpr-52830a.C: New test.

Diff:
---
 gcc/cp/cp-tree.h                              |   1 +
 gcc/cp/pt.cc                                  | 101 ++++++++++++++------------
 gcc/cp/tree.cc                                |   6 +-
 gcc/cp/typeck.cc                              |   2 +
 gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C |  39 ++++++++++
 5 files changed, 102 insertions(+), 47 deletions(-)

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index b2df6fc0ad4..ba986e892b6 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -6647,6 +6647,7 @@ extern bool make_safe_copy_elision		(tree, tree);
 extern bool cp_handle_deprecated_or_unavailable (tree, tsubst_flags_t = tf_warning_or_error);
 extern void cp_warn_deprecated_use_scopes	(tree);
 extern tree get_function_version_dispatcher	(tree);
+extern bool any_template_arguments_need_structural_equality_p (tree);
 
 /* in class.cc */
 extern tree build_vfield_ref			(tree, tree);
diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
index 5037627b93f..b45a29926d2 100644
--- a/gcc/cp/pt.cc
+++ b/gcc/cp/pt.cc
@@ -203,7 +203,6 @@ static tree copy_default_args_to_explicit_spec_1 (tree, tree);
 static void copy_default_args_to_explicit_spec (tree);
 static bool invalid_nontype_parm_type_p (tree, tsubst_flags_t);
 static bool dependent_template_arg_p (tree);
-static bool any_template_arguments_need_structural_equality_p (tree);
 static bool dependent_type_p_r (tree);
 static tree tsubst_copy	(tree, tree, tsubst_flags_t, tree);
 static tree tsubst_decl (tree, tree, tsubst_flags_t);
@@ -4526,6 +4525,27 @@ build_template_parm_index (int index,
   return t;
 }
 
+struct ctp_hasher : ggc_ptr_hash<tree_node>
+{
+  static hashval_t hash (tree t)
+  {
+    tree_code code = TREE_CODE (t);
+    hashval_t val = iterative_hash_object (code, 0);
+    val = iterative_hash_object (TEMPLATE_TYPE_LEVEL (t), val);
+    val = iterative_hash_object (TEMPLATE_TYPE_IDX (t), val);
+    if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
+      val = iterative_hash_template_arg (TYPE_TI_ARGS (t), val);
+    return val;
+  }
+
+  static bool equal (tree t, tree u)
+  {
+    return comptypes (t, u, COMPARE_STRUCTURAL);
+  }
+};
+
+static GTY (()) hash_table<ctp_hasher> *ctp_table;
+
 /* Find the canonical type parameter for the given template type
    parameter.  Returns the canonical type parameter, which may be TYPE
    if no such parameter existed.  */
@@ -4533,21 +4553,13 @@ build_template_parm_index (int index,
 tree
 canonical_type_parameter (tree type)
 {
-  int idx = TEMPLATE_TYPE_IDX (type);
+  if (ctp_table == NULL)
+    ctp_table = hash_table<ctp_hasher>::create_ggc (61);
 
-  gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM);
-
-  if (vec_safe_length (canonical_template_parms) <= (unsigned) idx)
-    vec_safe_grow_cleared (canonical_template_parms, idx + 1, true);
-
-  for (tree list = (*canonical_template_parms)[idx];
-       list; list = TREE_CHAIN (list))
-    if (comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
-      return TREE_VALUE (list);
-
-  (*canonical_template_parms)[idx]
-    = tree_cons (NULL_TREE, type, (*canonical_template_parms)[idx]);
-  return type;
+  tree& slot = *ctp_table->find_slot (type, INSERT);
+  if (slot == NULL_TREE)
+    slot = type;
+  return slot;
 }
 
 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
@@ -4720,10 +4732,7 @@ process_template_parm (tree list, location_t parm_loc, tree parm,
 				     current_template_depth,
 				     decl, TREE_TYPE (parm));
       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
-      if (TREE_CODE (t) == TEMPLATE_TEMPLATE_PARM)
-	SET_TYPE_STRUCTURAL_EQUALITY (t);
-      else
-	TYPE_CANONICAL (t) = canonical_type_parameter (t);
+      TYPE_CANONICAL (t) = canonical_type_parameter (t);
     }
   DECL_ARTIFICIAL (decl) = 1;
   SET_DECL_TEMPLATE_PARM_P (decl);
@@ -10131,9 +10140,6 @@ lookup_template_class_1 (tree d1, tree arglist, tree in_decl, tree context,
 	       appropriately. */
 	    TYPE_CANONICAL (t) = template_type;
 	  else if (any_template_arguments_need_structural_equality_p (arglist))
-	    /* Some of the template arguments require structural
-	       equality testing, so this template class requires
-	       structural equality testing. */
 	    SET_TYPE_STRUCTURAL_EQUALITY (t);
 	}
       else
@@ -15908,20 +15914,6 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 		       only instantiated during satisfaction.  */
 		    PLACEHOLDER_TYPE_CONSTRAINTS_INFO (r) = ci;
 
-		if (TREE_CODE (r) == TEMPLATE_TEMPLATE_PARM)
-		  /* We have reduced the level of the template
-		     template parameter, but not the levels of its
-		     template parameters, so canonical_type_parameter
-		     will not be able to find the canonical template
-		     template parameter for this level. Thus, we
-		     require structural equality checking to compare
-		     TEMPLATE_TEMPLATE_PARMs. */
-		  SET_TYPE_STRUCTURAL_EQUALITY (r);
-		else if (TYPE_STRUCTURAL_EQUALITY_P (t))
-		  SET_TYPE_STRUCTURAL_EQUALITY (r);
-		else
-		  TYPE_CANONICAL (r) = canonical_type_parameter (r);
-
 		if (code == BOUND_TEMPLATE_TEMPLATE_PARM)
 		  {
 		    tree tinfo = TYPE_TEMPLATE_INFO (t);
@@ -15939,6 +15931,11 @@ tsubst (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 		    TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (r)
 		      = build_template_info (tmpl, argvec);
 		  }
+
+		if (TYPE_STRUCTURAL_EQUALITY_P (t))
+		  SET_TYPE_STRUCTURAL_EQUALITY (r);
+		else
+		  TYPE_CANONICAL (r) = canonical_type_parameter (r);
 	      }
 	    break;
 
@@ -28227,8 +28224,8 @@ find_parm_usage_r (tree *tp, int *walk_subtrees, void*)
   return NULL_TREE;
 }
 
-/* Returns true if ARGS (a collection of template arguments) contains
-   any types that require structural equality testing.  */
+/* Returns true if a type specialization formed using the template
+   arguments ARGS needs to use structural equality.  */
 
 bool
 any_template_arguments_need_structural_equality_p (tree args)
@@ -28266,10 +28263,11 @@ any_template_arguments_need_structural_equality_p (tree args)
 		return true;
 	      else if (TREE_CODE (arg) == TEMPLATE_DECL)
 		continue;
-	      else if (TYPE_P (arg) && TYPE_STRUCTURAL_EQUALITY_P (arg))
-		return true;
-	      else if (!TYPE_P (arg) && TREE_TYPE (arg)
-		       && TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (arg)))
+	      else if (arg == any_targ_node)
+		/* An any_targ_node argument (added by add_defaults_to_ttp)
+		   makes the corresponding specialization not canonicalizable,
+		   since template_args_equal always return true for it.  We
+		   may see this when called from bind_template_template_parm.  */
 		return true;
 	      /* Checking current_function_decl because this structural
 		 comparison is only necessary for redeclaration.  */
@@ -28277,6 +28275,16 @@ any_template_arguments_need_structural_equality_p (tree args)
 		       && dependent_template_arg_p (arg)
 		       && (cp_walk_tree_without_duplicates
 			   (&arg, find_parm_usage_r, NULL)))
+		/* The identity of a class template specialization that uses
+		   a function parameter depends on the identity of the function.
+		   And if this specialization appeared in the trailing return
+		   type thereof, we don't know the identity of the function
+		   (e.g. if it's a redeclaration or a new function) until we
+		   form its signature and go through duplicate_decls.  Thus
+		   it's unsafe to decide on a canonical type now (which depends
+		   on the DECL_CONTEXT of the function parameter, which can get
+		   mutated after the fact by duplicate_decls), so just require
+		   structural equality in this case (PR52830).  */
 		return true;
 	    }
 	}
@@ -29144,10 +29152,6 @@ rewrite_template_parm (tree olddecl, unsigned index, unsigned level,
       TEMPLATE_PARM_PARAMETER_PACK (newidx)
 	= TEMPLATE_PARM_PARAMETER_PACK (oldidx);
       TYPE_STUB_DECL (newtype) = TYPE_NAME (newtype) = newdecl;
-      if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (olddecl)))
-	SET_TYPE_STRUCTURAL_EQUALITY (newtype);
-      else
-	TYPE_CANONICAL (newtype) = canonical_type_parameter (newtype);
 
       if (TREE_CODE (olddecl) == TEMPLATE_DECL)
 	{
@@ -29189,6 +29193,11 @@ rewrite_template_parm (tree olddecl, unsigned index, unsigned level,
 	  // All done.
 	  DECL_TEMPLATE_PARMS (newdecl) = ttparms;
 	}
+
+      if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (olddecl)))
+	SET_TYPE_STRUCTURAL_EQUALITY (newtype);
+      else
+	TYPE_CANONICAL (newtype) = canonical_type_parameter (newtype);
     }
   else
     {
diff --git a/gcc/cp/tree.cc b/gcc/cp/tree.cc
index bc38c8fbdbe..09162795801 100644
--- a/gcc/cp/tree.cc
+++ b/gcc/cp/tree.cc
@@ -2901,7 +2901,11 @@ bind_template_template_parm (tree t, tree newargs)
   TYPE_NAME (t2) = decl;
   TYPE_STUB_DECL (t2) = decl;
   TYPE_SIZE (t2) = 0;
-  SET_TYPE_STRUCTURAL_EQUALITY (t2);
+
+  if (any_template_arguments_need_structural_equality_p (newargs))
+    SET_TYPE_STRUCTURAL_EQUALITY (t2);
+  else
+    TYPE_CANONICAL (t2) = canonical_type_parameter (t2);
 
   return t2;
 }
diff --git a/gcc/cp/typeck.cc b/gcc/cp/typeck.cc
index 6ecdd97697d..385cdf4d733 100644
--- a/gcc/cp/typeck.cc
+++ b/gcc/cp/typeck.cc
@@ -1511,8 +1511,10 @@ structural_comptypes (tree t1, tree t2, int strict)
 	 substitute into the specialization arguments at instantiation
 	 time.  And aliases can't be equivalent without being ==, so
 	 we don't need to look any deeper.  */
+      ++processing_template_decl;
       tree dep1 = dependent_alias_template_spec_p (t1, nt_transparent);
       tree dep2 = dependent_alias_template_spec_p (t2, nt_transparent);
+      --processing_template_decl;
       if ((dep1 || dep2) && dep1 != dep2)
 	return false;
     }
diff --git a/gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C b/gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C
new file mode 100644
index 00000000000..224f2cd50eb
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C
@@ -0,0 +1,39 @@
+// PR c++/52830
+// { dg-do compile { target c++11 } }
+// { dg-additional-options "-fchecking" }
+// A version of constexpr-52830.C that uses an intermediate template template
+// parameter.
+
+template<bool b> struct eif { typedef void type; };
+template<>       struct eif<false> {};
+
+template<class A, class B> struct same
+{
+  static constexpr bool value = false;
+};
+template<class A>
+struct same<A, A>
+{
+  static constexpr bool value = true;
+};
+
+
+struct foo {
+  template<class T, template<class, class> class SAME = same>
+  void func(T && a,
+            typename eif<SAME<decltype(a), int&&>::value>::type * = 0);
+};
+
+template<class T, template<class, class> class SAME>
+void
+foo::
+func(T && a,
+     typename eif<SAME<decltype(a), int&&>::value>::type * )
+{
+}
+
+void do_stuff()
+{
+  foo f;
+  f.func(12);
+}