Re: [PATCH] c++: set TYPE_CANONICAL for most templated types
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) : 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
+{
+ 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_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 =
Re: [PATCH] c++: set TYPE_CANONICAL for most templated types
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) : 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
> > +{
> > + 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_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
Re: [PATCH] c++: set TYPE_CANONICAL for most templated types
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) : 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
+{
+ 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_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::create_ggc (61);
- if (vec_safe_length (canonical_template_parms) <= (unsigned) idx)
-vec_safe_grow_cleared
[PATCH] 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) : 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
+{
+ 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_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::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);
-
-
