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