c++: set TYPE_CANONICAL for most templated types

  When processing a class template specialization, lookup_template_class
uses structural equality for the specialized type whenever one of its
template arguments uses structural equality.  This the sensible thing to
do in a vacuum, but given that we already effectively deduplicate class
specializations via the spec_hasher, it seems to me we can safely assume
that each class specialization is unique and therefore canonical,
regardless of the structure 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 (added in 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 I understand it.  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.

This change improves compile time of heavily templated 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 it goes from 5.38s to 4.88s.
The total number of calls to structural_comptypes for the latter test
drops from 8.5M to 1.5M.  Memory use is unchanged (unsurpisingly).

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
trunk?  Also tested on cmcstl2 and range-v3 and various boost libraries.
Will also do more testing overnight...

gcc/cp/ChangeLog:

	* pt.cc (any_template_arguments_need_structural_equality_p):
	Remove.
	(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): Don't call a_t_a_n_s_e_p.  Inline
	the PARM_DECL special case from that subroutine into here.
	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Remove special
	TYPE_CANONICAL handling specific to ttps, and perform the
	remaining handling later.
	(find_parm_usage_r): Remove.
	* 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 using
	dependent_alias_template_spec_p.
---
 gcc/cp/pt.cc     | 166 ++++++++++++++++-------------------------------
 gcc/cp/tree.cc   |  16 ++++-
 gcc/cp/typeck.cc |   2 +
 3 files changed, 73 insertions(+), 111 deletions(-)
  

On 5/16/22 15:58, Patrick Palka wrote:
> When processing a class template specialization, lookup_template_class
> uses structural equality for the specialized type whenever one of its
> template arguments uses structural equality.  This the sensible thing to
> do in a vacuum, but given that we already effectively deduplicate class
> specializations via the spec_hasher, it seems to me we can safely assume
> that each class specialization is unique and therefore canonical,
> regardless of the structure of the template arguments.

Makes sense.

> 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 (added in 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 I understand it.

I think that comment from r120341 became obsolete when r129844 (later 
that year) 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.
> 
> This change improves compile time of heavily templated 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 it goes from 5.38s to 4.88s.
> The total number of calls to structural_comptypes for the latter test
> drops from 8.5M to 1.5M.  Memory use is unchanged (unsurpisingly).

Nice!

> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
> trunk?  Also tested on cmcstl2 and range-v3 and various boost libraries.
> Will also do more testing overnight...

One comment below.

> gcc/cp/ChangeLog:
> 
> 	* pt.cc (any_template_arguments_need_structural_equality_p):
> 	Remove.
> 	(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): Don't call a_t_a_n_s_e_p.  Inline
> 	the PARM_DECL special case from that subroutine into here.
> 	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Remove special
> 	TYPE_CANONICAL handling specific to ttps, and perform the
> 	remaining handling later.
> 	(find_parm_usage_r): Remove.
> 	* 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 using
> 	dependent_alias_template_spec_p.
> ---
>   gcc/cp/pt.cc     | 166 ++++++++++++++++-------------------------------
>   gcc/cp/tree.cc   |  16 ++++-
>   gcc/cp/typeck.cc |   2 +
>   3 files changed, 73 insertions(+), 111 deletions(-)
> 
> diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
> index fa05e9134df..76562877355 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);
> -
> -  gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM);
> +  if (ctp_table == NULL)
> +    ctp_table = hash_table<ctp_hasher>::create_ggc (61);
>   
> -  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);
> @@ -10130,11 +10139,29 @@ lookup_template_class_1 (tree d1, tree arglist, tree in_decl, tree context,
>   	       template type. Set the TYPE_CANONICAL field
>   	       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 if (!current_function_decl && processing_template_decl)
> +	    {
> +	      auto find_parm_usage_r = [] (tree *tp, int*, void*) {
> +		if (TREE_CODE (*tp) == PARM_DECL)
> +		  return *tp;
> +		return NULL_TREE;
> +	      };
> +	      if (cp_walk_tree_without_duplicates (&arglist, find_parm_usage_r,
> +						   nullptr))
> +		/* 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.  Deciding on a canonical type at this
> +		   point (which depends on the DECL_CONTEXT of the function
> +		   parameter, which can get mutated after the fact by
> +		   duplicate_decls) is therefore premature, so instead use
> +		   structural equality (PR52830).  */
> +		SET_TYPE_STRUCTURAL_EQUALITY (t);

Don't we need to check for this in bind_template_template_parm as well? 
  Might keep any_template_arguments_need_structural_equality_p for 
sharing this check.

> +	    }
> +	  /* Otherwise, this class specialization is unique and therefore its
> +	     TYPE_CANONICAL points to itself.  */
>   	}
>         else
>   	gcc_unreachable ();
> @@ -15908,20 +15935,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 +15952,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;
>   
> @@ -28211,78 +28229,6 @@ dependent_template_arg_p (tree arg)
>       return value_dependent_expression_p (arg);
>   }
>   
> -/* Identify any expressions that use function parms.  */
> -
> -static tree
> -find_parm_usage_r (tree *tp, int *walk_subtrees, void*)
> -{
> -  tree t = *tp;
> -  if (TREE_CODE (t) == PARM_DECL)
> -    {
> -      *walk_subtrees = 0;
> -      return t;
> -    }
> -  return NULL_TREE;
> -}
> -
> -/* Returns true if ARGS (a collection of template arguments) contains
> -   any types that require structural equality testing.  */
> -
> -bool
> -any_template_arguments_need_structural_equality_p (tree args)
> -{
> -  int i;
> -  int j;
> -
> -  if (!args)
> -    return false;
> -  if (args == error_mark_node)
> -    return true;
> -
> -  for (i = 0; i < TMPL_ARGS_DEPTH (args); ++i)
> -    {
> -      tree level = TMPL_ARGS_LEVEL (args, i + 1);
> -      for (j = 0; j < TREE_VEC_LENGTH (level); ++j)
> -	{
> -	  tree arg = TREE_VEC_ELT (level, j);
> -	  tree packed_args = NULL_TREE;
> -	  int k, len = 1;
> -
> -	  if (ARGUMENT_PACK_P (arg))
> -	    {
> -	      /* Look inside the argument pack.  */
> -	      packed_args = ARGUMENT_PACK_ARGS (arg);
> -	      len = TREE_VEC_LENGTH (packed_args);
> -	    }
> -
> -	  for (k = 0; k < len; ++k)
> -	    {
> -	      if (packed_args)
> -		arg = TREE_VEC_ELT (packed_args, k);
> -
> -	      if (error_operand_p (arg))
> -		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)))
> -		return true;
> -	      /* Checking current_function_decl because this structural
> -		 comparison is only necessary for redeclaration.  */
> -	      else if (!current_function_decl
> -		       && dependent_template_arg_p (arg)
> -		       && (cp_walk_tree_without_duplicates
> -			   (&arg, find_parm_usage_r, NULL)))
> -		return true;
> -	    }
> -	}
> -    }
> -
> -  return false;
> -}
> -
>   /* Returns true if ARGS (a collection of template arguments) contains
>      any dependent arguments.  */
>   
> diff --git a/gcc/cp/tree.cc b/gcc/cp/tree.cc
> index bc38c8fbdbe..940f1420bba 100644
> --- a/gcc/cp/tree.cc
> +++ b/gcc/cp/tree.cc
> @@ -2901,7 +2901,21 @@ 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);
> +
> +  bool use_structural_equality = false;
> +  for (tree arg : tree_vec_range (newargs))
> +    if (arg == any_targ_node)
> +      {
> +	/* This BOUND_TEMPLATE_TEMPLATE_PARM has an any_targ_node argument
> +	   (added by add_defaults_to_ttp), for which template_args_equal
> +	   always returns true, so this bound ttp is not canonicalizable.  */
> +	use_structural_equality = true;
> +	break;
> +      }
> +  if (use_structural_equality)
> +    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;
>       }
  

On 5/18/22, Jason Merrill wrote:
> On 5/16/22 15:58, Patrick Palka wrote:
> > When processing a class template specialization, lookup_template_class
> > uses structural equality for the specialized type whenever one of its
> > template arguments uses structural equality.  This the sensible thing to
> > do in a vacuum, but given that we already effectively deduplicate class
> > specializations via the spec_hasher, it seems to me we can safely assume
> > that each class specialization is unique and therefore canonical,
> > regardless of the structure of the template arguments.
> 
> Makes sense.
> 
> > 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 (added in 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 I understand it.
> 
> I think that comment from r120341 became obsolete when r129844 (later that
> year) started to substitute the template parms of ttps.

Ah, I see.  I'll make note of this in the v2 commit message.

> 
> > 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.
> > 
> > This change improves compile time of heavily templated 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 it goes from 5.38s to 4.88s.
> > The total number of calls to structural_comptypes for the latter test
> > drops from 8.5M to 1.5M.  Memory use is unchanged (unsurpisingly).
> 
> Nice!
> 
> > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
> > trunk?  Also tested on cmcstl2 and range-v3 and various boost libraries.
> > Will also do more testing overnight...
> 
> One comment below.
> 
> > gcc/cp/ChangeLog:
> > 
> > 	* pt.cc (any_template_arguments_need_structural_equality_p):
> > 	Remove.
> > 	(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): Don't call a_t_a_n_s_e_p.  Inline
> > 	the PARM_DECL special case from that subroutine into here.
> > 	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Remove special
> > 	TYPE_CANONICAL handling specific to ttps, and perform the
> > 	remaining handling later.
> > 	(find_parm_usage_r): Remove.
> > 	* 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 using
> > 	dependent_alias_template_spec_p.
> > ---
> >   gcc/cp/pt.cc     | 166 ++++++++++++++++-------------------------------
> >   gcc/cp/tree.cc   |  16 ++++-
> >   gcc/cp/typeck.cc |   2 +
> >   3 files changed, 73 insertions(+), 111 deletions(-)
> > 
> > diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
> > index fa05e9134df..76562877355 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);
> > -
> > -  gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM);
> > +  if (ctp_table == NULL)
> > +    ctp_table = hash_table<ctp_hasher>::create_ggc (61);
> >   -  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);
> > @@ -10130,11 +10139,29 @@ lookup_template_class_1 (tree d1, tree arglist,
> > tree in_decl, tree context,
> >   	       template type. Set the TYPE_CANONICAL field
> >   	       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 if (!current_function_decl && processing_template_decl)
> > +	    {
> > +	      auto find_parm_usage_r = [] (tree *tp, int*, void*) {
> > +		if (TREE_CODE (*tp) == PARM_DECL)
> > +		  return *tp;
> > +		return NULL_TREE;
> > +	      };
> > +	      if (cp_walk_tree_without_duplicates (&arglist,
> > find_parm_usage_r,
> > +						   nullptr))
> > +		/* 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.  Deciding on a canonical type at this
> > +		   point (which depends on the DECL_CONTEXT of the function
> > +		   parameter, which can get mutated after the fact by
> > +		   duplicate_decls) is therefore premature, so instead use
> > +		   structural equality (PR52830).  */
> > +		SET_TYPE_STRUCTURAL_EQUALITY (t);
> 
> Don't we need to check for this in bind_template_template_parm as well?  Might
> keep any_template_arguments_need_structural_equality_p for sharing this check.

Ah yeah, good point.  Without checking this in
bind_template_template_parm, we crash on constexpr-pr52830a.C below.

Here's v2 with the following changes:

 * updated commit message
 * keep any_template_arguments_need_structural_equality_p and use it
   bind_template_template_parm.
 * in rewrite_template_template_parm, we need to set TYPE_CANONICAL
   later, after the ttp adjustment stuff.  (This was causing a crash
   in a libc++ test.)

-- >8 --

Subject: [PATCH] c++: treat more template types as canonical

When processing 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 spec_hasher, it seems to me we can safely
assume that each class specialization is unique and therefore canonical,
regardless of the structure 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
r0-78177-g06d40de8bb0359) became obsolete when r0-84235-gef3b7b17610049
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 heavily templated 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 non-trivial calls to structural_comptypes for the latter test
drops from 8.5M to 1.5M.  Memory use is unaffected (as expected).

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 outdated comment after
	any_template_arguments_need_structural_equality_p test.
	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Don't specifically
	clear TYPE_CANONICAL for ttps.  Perform the remaning
	TYPE_CANONICAL handling later.
	(any_template_arguments_need_structural_equality_p): Return
	true for any_targ_node.  Add comment for the PARM_DECL 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 using
	dependent_alias_template_spec_p.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp0x/constexpr-52830a.C: New test.
---
 gcc/cp/cp-tree.h                              |   1 +
 gcc/cp/pt.cc                                  | 102 ++++++++++--------
 gcc/cp/tree.cc                                |   6 +-
 gcc/cp/typeck.cc                              |   2 +
 gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C |  38 +++++++
 5 files changed, 102 insertions(+), 47 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 0325e36f32e..32c75b325e8 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 632b65b8a24..dd98c94fbe5 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);
@@ -10129,9 +10138,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
@@ -15906,20 +15912,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);
@@ -15937,6 +15929,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;
 
@@ -28264,17 +28261,29 @@ 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))
+	      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
+		   should only see this for a bound ttp, when called from
+		   bind_template_template_parm.  */
 		return true;
-	      else if (!TYPE_P (arg) && TREE_TYPE (arg)
-		       && TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (arg)))
-		return true;
-	      /* Checking current_function_decl because this structural
-		 comparison is only necessary for redeclaration.  */
 	      else if (!current_function_decl
+		       /* Checking current_function_decl because this structural
+			  comparison is only necessary for redeclaration.  */
 		       && 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 use
+		   structural equality in this case (PR52830).  */
 		return true;
 	    }
 	}
@@ -29142,10 +29151,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)
 	{
@@ -29187,6 +29192,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..da0d4473783
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C
@@ -0,0 +1,38 @@
+// PR c++/52830
+// { dg-do compile { target c++11 } }
+// { dg-additional-options "-fchecking" }
+// A version of constexpr-52830.C using a 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);
+}
  

On 5/23/22 16:25, Patrick Palka wrote:
> On 5/18/22, Jason Merrill wrote:
>> On 5/16/22 15:58, Patrick Palka wrote:
>>> When processing a class template specialization, lookup_template_class
>>> uses structural equality for the specialized type whenever one of its
>>> template arguments uses structural equality.  This the sensible thing to
>>> do in a vacuum, but given that we already effectively deduplicate class
>>> specializations via the spec_hasher, it seems to me we can safely assume
>>> that each class specialization is unique and therefore canonical,
>>> regardless of the structure of the template arguments.
>> Makes sense.
>>
>>> 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 (added in 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 I understand it.
>> I think that comment from r120341 became obsolete when r129844 (later that
>> year) started to substitute the template parms of ttps.
> Ah, I see.  I'll make note of this in the v2 commit message.
>
>>> 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.
>>>
>>> This change improves compile time of heavily templated 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 it goes from 5.38s to 4.88s.
>>> The total number of calls to structural_comptypes for the latter test
>>> drops from 8.5M to 1.5M.  Memory use is unchanged (unsurpisingly).
>> Nice!
>>
>>> Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
>>> trunk?  Also tested on cmcstl2 and range-v3 and various boost libraries.
>>> Will also do more testing overnight...
>> One comment below.
>>
>>> gcc/cp/ChangeLog:
>>>
>>> 	* pt.cc (any_template_arguments_need_structural_equality_p):
>>> 	Remove.
>>> 	(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): Don't call a_t_a_n_s_e_p.  Inline
>>> 	the PARM_DECL special case from that subroutine into here.
>>> 	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Remove special
>>> 	TYPE_CANONICAL handling specific to ttps, and perform the
>>> 	remaining handling later.
>>> 	(find_parm_usage_r): Remove.
>>> 	* 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 using
>>> 	dependent_alias_template_spec_p.
>>> ---
>>>    gcc/cp/pt.cc     | 166 ++++++++++++++++-------------------------------
>>>    gcc/cp/tree.cc   |  16 ++++-
>>>    gcc/cp/typeck.cc |   2 +
>>>    3 files changed, 73 insertions(+), 111 deletions(-)
>>>
>>> diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc
>>> index fa05e9134df..76562877355 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);
>>> -
>>> -  gcc_assert (TREE_CODE (type) != TEMPLATE_TEMPLATE_PARM);
>>> +  if (ctp_table == NULL)
>>> +    ctp_table = hash_table<ctp_hasher>::create_ggc (61);
>>>    -  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);
>>> @@ -10130,11 +10139,29 @@ lookup_template_class_1 (tree d1, tree arglist,
>>> tree in_decl, tree context,
>>>    	       template type. Set the TYPE_CANONICAL field
>>>    	       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 if (!current_function_decl && processing_template_decl)
>>> +	    {
>>> +	      auto find_parm_usage_r = [] (tree *tp, int*, void*) {
>>> +		if (TREE_CODE (*tp) == PARM_DECL)
>>> +		  return *tp;
>>> +		return NULL_TREE;
>>> +	      };
>>> +	      if (cp_walk_tree_without_duplicates (&arglist,
>>> find_parm_usage_r,
>>> +						   nullptr))
>>> +		/* 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.  Deciding on a canonical type at this
>>> +		   point (which depends on the DECL_CONTEXT of the function
>>> +		   parameter, which can get mutated after the fact by
>>> +		   duplicate_decls) is therefore premature, so instead use
>>> +		   structural equality (PR52830).  */
>>> +		SET_TYPE_STRUCTURAL_EQUALITY (t);
>> Don't we need to check for this in bind_template_template_parm as well?  Might
>> keep any_template_arguments_need_structural_equality_p for sharing this check.
> Ah yeah, good point.  Without checking this in
> bind_template_template_parm, we crash on constexpr-pr52830a.C below.
>
> Here's v2 with the following changes:
>
>   * updated commit message
>   * keep any_template_arguments_need_structural_equality_p and use it
>     bind_template_template_parm.
>   * in rewrite_template_template_parm, we need to set TYPE_CANONICAL
>     later, after the ttp adjustment stuff.  (This was causing a crash
>     in a libc++ test.)
>
> -- >8 --
>
> Subject: [PATCH] c++: treat more template types as canonical
>
> When processing 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 spec_hasher, it seems to me we can safely
> assume that each class specialization is unique and therefore canonical,
> regardless of the structure 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
> r0-78177-g06d40de8bb0359) became obsolete when r0-84235-gef3b7b17610049

I prefer to use the shorter SVN revs rather than r0-nnnnn, but this is fine.

> 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 heavily templated 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 non-trivial calls to structural_comptypes for the latter test
> drops from 8.5M to 1.5M.  Memory use is unaffected (as expected).
>
> 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 outdated comment after
> 	any_template_arguments_need_structural_equality_p test.
> 	(tsubst) <case TEMPLATE_TEMPLATE_PARM, etc>: Don't specifically
> 	clear TYPE_CANONICAL for ttps.  Perform the remaning
> 	TYPE_CANONICAL handling later.
> 	(any_template_arguments_need_structural_equality_p): Return
> 	true for any_targ_node.  Add comment for the PARM_DECL 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 using
> 	dependent_alias_template_spec_p.
>
> gcc/testsuite/ChangeLog:
>
> 	* g++.dg/cpp0x/constexpr-52830a.C: New test.
> ---
>   gcc/cp/cp-tree.h                              |   1 +
>   gcc/cp/pt.cc                                  | 102 ++++++++++--------
>   gcc/cp/tree.cc                                |   6 +-
>   gcc/cp/typeck.cc                              |   2 +
>   gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C |  38 +++++++
>   5 files changed, 102 insertions(+), 47 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C
>
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 0325e36f32e..32c75b325e8 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 632b65b8a24..dd98c94fbe5 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);
> @@ -10129,9 +10138,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
> @@ -15906,20 +15912,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);
> @@ -15937,6 +15929,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;
>   
> @@ -28264,17 +28261,29 @@ 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))
> +	      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
> +		   should only see this for a bound ttp, when called from
> +		   bind_template_template_parm.  */
>   		return true;
> -	      else if (!TYPE_P (arg) && TREE_TYPE (arg)
> -		       && TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (arg)))
> -		return true;
> -	      /* Checking current_function_decl because this structural
> -		 comparison is only necessary for redeclaration.  */
>   	      else if (!current_function_decl
> +		       /* Checking current_function_decl because this structural
> +			  comparison is only necessary for redeclaration.  */

Let's avoid moving comments unnecessarily.  OK with that change.

>   		       && 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 use
> +		   structural equality in this case (PR52830).  */
>   		return true;
>   	    }
>   	}
> @@ -29142,10 +29151,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)
>   	{
> @@ -29187,6 +29192,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..da0d4473783
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-52830a.C
> @@ -0,0 +1,38 @@
> +// PR c++/52830
> +// { dg-do compile { target c++11 } }
> +// { dg-additional-options "-fchecking" }
> +// A version of constexpr-52830.C using a 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);
> +}