Re: C++ PATCH for c++/48969 (infinite template recursion with enum scope)

[Jason Merrill <jason at redhat dot com>]

On 05/13/2011 06:22 PM, Jason Merrill wrote:
> My initial implementation used a VEC to keep track of current deductions
> in process, but I switched it to use a hash table instead; the overhead
> for using a hash table rather than a VEC on the most common case (very
> low deduction nesting) is small, but on highly recursive template
> metaprogramming the difference in complexity can make a difference.
>
> Unfortunately, the difference one way or the other is dwarfed by the
> overhead from doing this checking at all (about 2% of compile time
> compiling stdc++.h), but I don't see how to avoid it.

The 2% number was wrong; most of that is the call to tsubst which we 
would be doing anyway.  But using a hash table did create significant 
overhead (about 0.9%) in typical code with low deduction nesting, so I 
decided to have it both ways: we start with a VEC and then switch to a 
hash table if the VEC gets large.

Tested x86_64-pc-linux-gnu, applying to trunk.
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.

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index e441a70..cc14f02 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -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"