From patchwork Mon May 16 20:51:12 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jason Merrill X-Patchwork-Id: 95835 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 93437B6EED for ; Tue, 17 May 2011 06:51:36 +1000 (EST) Received: (qmail 12589 invoked by alias); 16 May 2011 20:51:34 -0000 Received: (qmail 12578 invoked by uid 22791); 16 May 2011 20:51:33 -0000 X-SWARE-Spam-Status: No, hits=-6.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 16 May 2011 20:51:13 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p4GKpDLS001296 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Mon, 16 May 2011 16:51:13 -0400 Received: from [127.0.0.1] (ovpn-113-120.phx2.redhat.com [10.3.113.120]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p4GKpCCv025470 for ; Mon, 16 May 2011 16:51:13 -0400 Message-ID: <4DD18E40.3090605@redhat.com> Date: Mon, 16 May 2011 16:51:12 -0400 From: Jason Merrill User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.17) Gecko/20110428 Fedora/3.1.10-1.fc14 Lightning/1.0b2 Thunderbird/3.1.10 MIME-Version: 1.0 To: gcc-patches List Subject: Re: C++ PATCH for c++/48969 (infinite template recursion with enum scope) References: <4DCDAF1A.1060802@redhat.com> In-Reply-To: <4DCDAF1A.1060802@redhat.com> Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 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"