commit 42bcea7fed71740a505406947d0541f253dc6f84
Author: Jason Merrill <jason@redhat.com>
Date: Mon May 16 13:50:21 2011 -0400
PR c++/48969
* pt.c (deduction_tsubst_fntype): Use a VEC initially.
@@ -13526,17 +13526,30 @@ check_instantiated_args (tree tmpl, tree args, tsubst_flags_t complain)
return result;
}
-static GTY((param_is (spec_entry))) htab_t current_deduction_substs;
+DEF_VEC_O (spec_entry);
+DEF_VEC_ALLOC_O (spec_entry,gc);
+static GTY(()) VEC(spec_entry,gc) *current_deduction_vec;
+static GTY((param_is (spec_entry))) htab_t current_deduction_htab;
/* In C++0x, it's possible to have a function template whose type depends
on itself recursively. This is most obvious with decltype, but can also
occur with enumeration scope (c++/48969). So we need to catch infinite
- recursion and reject the substitution at deduction time. */
+ recursion and reject the substitution at deduction time.
+
+ Use of a VEC here is O(n^2) in the depth of function template argument
+ deduction substitution, but using a hash table creates a lot of constant
+ overhead for the typical case of very low depth. So to make the typical
+ case fast we start out with a VEC and switch to a hash table only if
+ depth gets to be significant; in one metaprogramming testcase, even at
+ depth 80 the overhead of the VEC relative to a hash table was only about
+ 0.5% of compile time. */
static tree
deduction_tsubst_fntype (tree fn, tree targs)
{
+ unsigned i;
spec_entry **slot;
+ spec_entry *p;
spec_entry elt;
tree r;
hashval_t hash;
@@ -13547,29 +13560,83 @@ deduction_tsubst_fntype (tree fn, tree targs)
if (cxx_dialect < cxx0x)
return tsubst (fntype, targs, tf_none, NULL_TREE);
+ /* If we're seeing a lot of recursion, switch over to a hash table. The
+ constant 40 is fairly arbitrary. */
+ if (!current_deduction_htab
+ && VEC_length (spec_entry, current_deduction_vec) > 40)
+ {
+ current_deduction_htab = htab_create_ggc (40*2, hash_specialization,
+ eq_specializations, ggc_free);
+ FOR_EACH_VEC_ELT (spec_entry, current_deduction_vec, i, p)
+ {
+ slot = (spec_entry **) htab_find_slot (current_deduction_htab,
+ p, INSERT);
+ *slot = ggc_alloc_spec_entry ();
+ **slot = *p;
+ }
+ VEC_free (spec_entry, gc, current_deduction_vec);
+ }
+
+ /* Now check everything in the vector, if any. */
+ FOR_EACH_VEC_ELT (spec_entry, current_deduction_vec, i, p)
+ if (p->tmpl == fn && comp_template_args (p->args, targs))
+ {
+ p->spec = error_mark_node;
+ return error_mark_node;
+ }
+
elt.tmpl = fn;
elt.args = targs;
elt.spec = NULL_TREE;
- hash = hash_specialization (&elt);
- slot = (spec_entry **)
- htab_find_slot_with_hash (current_deduction_substs, &elt, hash, INSERT);
- if (*slot)
- /* We already have an entry for this. */
- (*slot)->spec = r = error_mark_node;
+ /* If we've created a hash table, look there. */
+ if (current_deduction_htab)
+ {
+ hash = hash_specialization (&elt);
+ slot = (spec_entry **)
+ htab_find_slot_with_hash (current_deduction_htab, &elt, hash, INSERT);
+ if (*slot)
+ {
+ /* We already have an entry for this. */
+ (*slot)->spec = error_mark_node;
+ return error_mark_node;
+ }
+ else
+ {
+ /* Create a new entry. */
+ *slot = ggc_alloc_spec_entry ();
+ **slot = elt;
+ }
+ }
else
{
- /* Create a new entry. */
- spec_entry *p = *slot = ggc_alloc_spec_entry ();
- *p = elt;
+ /* No hash table, so add it to the VEC. */
+ hash = 0;
+ VEC_safe_push (spec_entry, gc, current_deduction_vec, &elt);
+ }
- r = tsubst (fntype, targs, tf_none, NULL_TREE);
- if (p->spec == error_mark_node)
- r = error_mark_node;
+ r = tsubst (fntype, targs, tf_none, NULL_TREE);
- htab_remove_elt_with_hash (current_deduction_substs, p, hash);
+ /* After doing the substitution, make sure we didn't hit it again. Note
+ that we might have switched to a hash table during tsubst. */
+ if (current_deduction_htab)
+ {
+ if (hash == 0)
+ hash = hash_specialization (&elt);
+ slot = (spec_entry **)
+ htab_find_slot_with_hash (current_deduction_htab, &elt, hash,
+ NO_INSERT);
+ if ((*slot)->spec == error_mark_node)
+ r = error_mark_node;
+ htab_clear_slot (current_deduction_htab, (void**)slot);
+ }
+ else
+ {
+ if (VEC_last (spec_entry, current_deduction_vec)->spec
+ == error_mark_node)
+ r = error_mark_node;
+ VEC_pop (spec_entry, current_deduction_vec);
}
-
return r;
}
@@ -19331,10 +19398,6 @@ init_template_processing (void)
hash_specialization,
eq_specializations,
ggc_free);
- if (cxx_dialect >= cxx0x)
- current_deduction_substs = htab_create_ggc (37, hash_specialization,
- eq_specializations,
- ggc_free);
}
/* Print stats about the template hash tables for -fstats. */
@@ -19350,10 +19413,11 @@ print_template_statistics (void)
"%f collisions\n", (long) htab_size (type_specializations),
(long) htab_elements (type_specializations),
htab_collisions (type_specializations));
- fprintf (stderr, "current_deduction_substs: size %ld, %ld elements, "
- "%f collisions\n", (long) htab_size (current_deduction_substs),
- (long) htab_elements (current_deduction_substs),
- htab_collisions (current_deduction_substs));
+ if (current_deduction_htab)
+ fprintf (stderr, "current_deduction_htab: size %ld, %ld elements, "
+ "%f collisions\n", (long) htab_size (current_deduction_htab),
+ (long) htab_elements (current_deduction_htab),
+ htab_collisions (current_deduction_htab));
}
#include "gt-cp-pt.h"