When the std::pair constructors got more complex to handle, it aggravated a preexisting algorithmic problem in template overload resolution:
As part of template argument deduction in a call, once we've deduced all the template arguments we can but before we substitute them to form an actual declaration, for any function parameters that don't involve template parameters we need to check that it's possible to convert the argument to the parameter type (wg21.link/cwg1391). As a result, we end up calculating the conversion twice: once here, and then again in add_function_candidate as part of normal overload resolution. Normally this isn't a big deal, but when the argument is a multiply-nested initializer list, doubling the conversion processing at each level leads to combinatorial explosion. The patch for GCC 8 just disables the deduction-time check for a multiply nested initializer list. This is a small correctness regression, but is unlikely to affect real code. The patch for trunk avoids the duplication by remembering the conversion we calculate at deduction time and then reusing it in overload resolution rather than calculating it again. Tested x86_64-pc-linux-gnu, applying to trunk and 8 (respectively).
commit 10b1142610715b75d526c3313897740033694ac9 Author: Jason Merrill <ja...@redhat.com> Date: Tue Jun 26 09:56:53 2018 -0400 PR c++/80290 - memory-hog with std::pair. * pt.c (fn_type_unification): Add convs parameter. (check_non_deducible_conversion): Remember conversion. (check_non_deducible_conversions): New. Do checks here. (type_unification_real): Not here. Remove flags parm. * call.c (add_function_candidate): Make convs a parameter. Don't recalculate the conversion if it's already set. (add_template_candidate_real): Allocate convs here. (good_conversion, conv_flags): New. diff --git a/gcc/cp/call.c b/gcc/cp/call.c index aa0e696972a..209c1fd2f0e 100644 --- a/gcc/cp/call.c +++ b/gcc/cp/call.c @@ -192,7 +192,7 @@ static struct z_candidate *add_conv_candidate tree, tsubst_flags_t); static struct z_candidate *add_function_candidate (struct z_candidate **, tree, tree, tree, const vec<tree, va_gc> *, tree, - tree, int, tsubst_flags_t); + tree, int, conversion**, tsubst_flags_t); static conversion *implicit_conversion (tree, tree, tree, bool, int, tsubst_flags_t); static conversion *reference_binding (tree, tree, tree, bool, int, @@ -1929,6 +1929,23 @@ implicit_conversion (tree to, tree from, tree expr, bool c_cast_p, return NULL; } +/* Like implicit_conversion, but return NULL if the conversion is bad. + + This is not static so that check_non_deducible_conversion can call it within + add_template_candidate_real as part of overload resolution; it should not be + called outside of overload resolution. */ + +conversion * +good_conversion (tree to, tree from, tree expr, + int flags, tsubst_flags_t complain) +{ + conversion *c = implicit_conversion (to, from, expr, /*cast*/false, + flags, complain); + if (c && c->bad_p) + c = NULL; + return c; +} + /* Add a new entry to the list of candidates. Used by the add_*_candidate functions. ARGS will not be changed until a single candidate is selected. */ @@ -1975,6 +1992,37 @@ remaining_arguments (tree arg) return n; } +/* [over.match.copy]: When initializing a temporary object (12.2) to be bound + to the first parameter of a constructor where the parameter is of type + "reference to possibly cv-qualified T" and the constructor is called with a + single argument in the context of direct-initialization of an object of type + "cv2 T", explicit conversion functions are also considered. + + So set LOOKUP_COPY_PARM to let reference_binding know that + it's being called in that context. */ + +int +conv_flags (int i, int nargs, tree fn, tree arg, int flags) +{ + int lflags = flags; + tree t; + if (i == 0 && nargs == 1 && DECL_CONSTRUCTOR_P (fn) + && (t = FUNCTION_FIRST_USER_PARMTYPE (fn)) + && (same_type_ignoring_top_level_qualifiers_p + (non_reference (TREE_VALUE (t)), DECL_CONTEXT (fn)))) + { + if (!(flags & LOOKUP_ONLYCONVERTING)) + lflags |= LOOKUP_COPY_PARM; + if ((flags & LOOKUP_LIST_INIT_CTOR) + && BRACE_ENCLOSED_INITIALIZER_P (arg)) + lflags |= LOOKUP_NO_CONVERSION; + } + else + lflags |= LOOKUP_ONLYCONVERTING; + + return lflags; +} + /* Create an overload candidate for the function or method FN called with the argument list FIRST_ARG/ARGS and add it to CANDIDATES. FLAGS is passed on to implicit_conversion. @@ -1989,11 +2037,11 @@ add_function_candidate (struct z_candidate **candidates, tree fn, tree ctype, tree first_arg, const vec<tree, va_gc> *args, tree access_path, tree conversion_path, int flags, + conversion **convs, tsubst_flags_t complain) { tree parmlist = TYPE_ARG_TYPES (TREE_TYPE (fn)); int i, len; - conversion **convs; tree parmnode; tree orig_first_arg = first_arg; int skip; @@ -2025,7 +2073,8 @@ add_function_candidate (struct z_candidate **candidates, skip = 0; len = vec_safe_length (args) - skip + (first_arg != NULL_TREE ? 1 : 0); - convs = alloc_conversions (len); + if (!convs) + convs = alloc_conversions (len); /* 13.3.2 - Viable functions [over.match.viable] First, to be a viable function, a candidate function shall have enough @@ -2122,6 +2171,13 @@ add_function_candidate (struct z_candidate **candidates, if (parmnode == void_list_node) break; + if (convs[i]) + { + /* Already set during deduction. */ + parmnode = TREE_CHAIN (parmnode); + continue; + } + if (i == 0 && first_arg != NULL_TREE) arg = first_arg; else @@ -2135,7 +2191,6 @@ add_function_candidate (struct z_candidate **candidates, if (parmnode) { tree parmtype = TREE_VALUE (parmnode); - int lflags = flags; parmnode = TREE_CHAIN (parmnode); @@ -2173,32 +2228,7 @@ add_function_candidate (struct z_candidate **candidates, } } - /* Core issue 899: When [copy-]initializing a temporary to be bound - to the first parameter of a copy constructor (12.8) called with - a single argument in the context of direct-initialization, - explicit conversion functions are also considered. - - So set LOOKUP_COPY_PARM to let reference_binding know that - it's being called in that context. We generalize the above - to handle move constructors and template constructors as well; - the standardese should soon be updated similarly. */ - if (ctype && i == 0 && (len-skip == 1) - && DECL_CONSTRUCTOR_P (fn) - && parmtype != error_mark_node - && (same_type_ignoring_top_level_qualifiers_p - (non_reference (parmtype), ctype))) - { - if (!(flags & LOOKUP_ONLYCONVERTING)) - lflags |= LOOKUP_COPY_PARM; - /* We allow user-defined conversions within init-lists, but - don't list-initialize the copy parm, as that would mean - using two levels of braces for the same type. */ - if ((flags & LOOKUP_LIST_INIT_CTOR) - && BRACE_ENCLOSED_INITIALIZER_P (arg)) - lflags |= LOOKUP_NO_CONVERSION; - } - else - lflags |= LOOKUP_ONLYCONVERTING; + int lflags = conv_flags (i, len-skip, fn, arg, flags); t = implicit_conversion (parmtype, argtype, arg, /*c_cast_p=*/false, lflags, complain); @@ -3102,6 +3132,7 @@ add_template_candidate_real (struct z_candidate **candidates, tree tmpl, tree fn; struct rejection_reason *reason = NULL; int errs; + conversion **convs = NULL; /* We don't do deduction on the in-charge parameter, the VTT parameter or 'this'. */ @@ -3176,11 +3207,13 @@ add_template_candidate_real (struct z_candidate **candidates, tree tmpl, gcc_assert (ia == nargs_without_in_chrg); errs = errorcount+sorrycount; + if (!obj) + convs = alloc_conversions (nargs); fn = fn_type_unification (tmpl, explicit_targs, targs, args_without_in_chrg, nargs_without_in_chrg, - return_type, strict, flags, false, - complain & tf_decltype); + return_type, strict, flags, convs, + false, complain & tf_decltype); if (fn == error_mark_node) { @@ -3216,7 +3249,7 @@ add_template_candidate_real (struct z_candidate **candidates, tree tmpl, else cand = add_function_candidate (candidates, fn, ctype, first_arg, arglist, access_path, - conversion_path, flags, complain); + conversion_path, flags, convs, complain); if (DECL_TI_TEMPLATE (fn) != tmpl) /* This situation can occur if a member template of a template class is specialized. Then, instantiate_template might return @@ -3541,7 +3574,7 @@ print_z_candidate (location_t loc, const char *msgstr, r->u.template_unification.return_type, r->u.template_unification.strict, r->u.template_unification.flags, - true, false); + NULL, true, false); break; case rr_invalid_copy: inform (cloc, @@ -5517,6 +5550,7 @@ add_candidates (tree fns, tree first_arg, const vec<tree, va_gc> *args, access_path, conversion_path, flags, + NULL, complain); } } diff --git a/gcc/cp/class.c b/gcc/cp/class.c index 9a397e3856c..8d8339c9951 100644 --- a/gcc/cp/class.c +++ b/gcc/cp/class.c @@ -7816,7 +7816,7 @@ resolve_address_of_overloaded_function (tree target_type, instantiation = fn_type_unification (fn, explicit_targs, targs, args, nargs, ret, DEDUCE_EXACT, LOOKUP_NORMAL, - false, false); + NULL, false, false); if (instantiation == error_mark_node) /* Instantiation failed. */ continue; diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index 284b44343d3..0fac7e9892f 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -6041,6 +6041,8 @@ extern bool can_convert_arg (tree, tree, tree, int, tsubst_flags_t); extern bool can_convert_arg_bad (tree, tree, tree, int, tsubst_flags_t); +extern int conv_flags (int, int, tree, tree, int); +extern struct conversion * good_conversion (tree, tree, tree, int, tsubst_flags_t); extern location_t get_fndecl_argument_location (tree, int); @@ -6607,6 +6609,7 @@ extern tree instantiate_template (tree, tree, tsubst_flags_t); extern tree fn_type_unification (tree, tree, tree, const tree *, unsigned int, tree, unification_kind_t, int, + struct conversion **, bool, bool); extern void mark_decl_instantiated (tree, int); extern int more_specialized_fn (tree, tree, int); diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index e1e2f0152c1..3780f3492aa 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -155,10 +155,12 @@ static void tsubst_enum (tree, tree, tree); static tree add_to_template_args (tree, tree); static tree add_outermost_template_args (tree, tree); static bool check_instantiated_args (tree, tree, tsubst_flags_t); +static int check_non_deducible_conversion (tree, tree, int, int, + struct conversion **, bool); static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*, tree); static int type_unification_real (tree, tree, tree, const tree *, - unsigned int, int, unification_kind_t, int, + unsigned int, int, unification_kind_t, vec<deferred_access_check, va_gc> **, bool); static void note_template_header (int); @@ -19358,6 +19360,58 @@ pack_deducible_p (tree parm, tree fn) return true; } +/* Subroutine of fn_type_unification: check non-dependent parms for + convertibility. */ + +static int +check_non_deducible_conversions (tree parms, const tree *args, unsigned nargs, + tree fn, unification_kind_t strict, int flags, + struct conversion **convs, bool explain_p) +{ + /* Non-constructor methods need to leave a conversion for 'this', which + isn't included in nargs here. */ + unsigned offset = (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn) + && !DECL_CONSTRUCTOR_P (fn)); + + for (unsigned ia = 0; + parms && parms != void_list_node && ia < nargs; ) + { + tree parm = TREE_VALUE (parms); + + if (TREE_CODE (parm) == TYPE_PACK_EXPANSION + && (!TREE_CHAIN (parms) + || TREE_CHAIN (parms) == void_list_node)) + /* For a function parameter pack that occurs at the end of the + parameter-declaration-list, the type A of each remaining + argument of the call is compared with the type P of the + declarator-id of the function parameter pack. */ + break; + + parms = TREE_CHAIN (parms); + + if (TREE_CODE (parm) == TYPE_PACK_EXPANSION) + /* For a function parameter pack that does not occur at the + end of the parameter-declaration-list, the type of the + parameter pack is a non-deduced context. */ + continue; + + if (!uses_template_parms (parm)) + { + tree arg = args[ia]; + conversion **conv_p = convs ? &convs[ia+offset] : NULL; + int lflags = conv_flags (ia, nargs, fn, arg, flags); + + if (check_non_deducible_conversion (parm, arg, strict, lflags, + conv_p, explain_p)) + return 1; + } + + ++ia; + } + + return 0; +} + /* The FN is a TEMPLATE_DECL for a function. ARGS is an array with NARGS elements of the arguments that are being used when calling it. TARGS is a vector into which the deduced template arguments @@ -19400,6 +19454,7 @@ fn_type_unification (tree fn, tree return_type, unification_kind_t strict, int flags, + struct conversion **convs, bool explain_p, bool decltype_p) { @@ -19604,7 +19659,7 @@ fn_type_unification (tree fn, ok = !type_unification_real (DECL_INNERMOST_TEMPLATE_PARMS (fn), full_targs, parms, args, nargs, /*subr=*/0, - strict, flags, &checks, explain_p); + strict, &checks, explain_p); if (!explain_p) pop_tinst_level (); if (!ok) @@ -19638,6 +19693,12 @@ fn_type_unification (tree fn, goto fail; } + /* DR 1391: All parameters have args, now check non-dependent parms for + convertibility. */ + if (check_non_deducible_conversions (parms, args, nargs, fn, strict, flags, + convs, explain_p)) + goto fail; + /* All is well so far. Now, check: [temp.deduct] @@ -19826,14 +19887,15 @@ maybe_adjust_types_for_deduction (unification_kind_t strict, return result; } -/* Subroutine of unify_one_argument. PARM is a function parameter of a - template which does contain any deducible template parameters; check if +/* Subroutine of fn_type_unification. PARM is a function parameter of a + template which doesn't contain any deducible template parameters; check if ARG is a suitable match for it. STRICT, FLAGS and EXPLAIN_P are as in unify_one_argument. */ static int check_non_deducible_conversion (tree parm, tree arg, int strict, - int flags, bool explain_p) + int flags, struct conversion **conv_p, + bool explain_p) { tree type; @@ -19845,17 +19907,23 @@ check_non_deducible_conversion (tree parm, tree arg, int strict, if (same_type_p (parm, type)) return unify_success (explain_p); + tsubst_flags_t complain = (explain_p ? tf_warning_or_error : tf_none); if (strict == DEDUCE_CONV) { - if (can_convert_arg (type, parm, NULL_TREE, flags, - explain_p ? tf_warning_or_error : tf_none)) + if (can_convert_arg (type, parm, NULL_TREE, flags, complain)) return unify_success (explain_p); } else if (strict != DEDUCE_EXACT) { - if (can_convert_arg (parm, type, - TYPE_P (arg) ? NULL_TREE : arg, - flags, explain_p ? tf_warning_or_error : tf_none)) + bool ok = false; + tree conv_arg = TYPE_P (arg) ? NULL_TREE : arg; + if (conv_p) + /* Avoid recalculating this in add_function_candidate. */ + ok = (*conv_p + = good_conversion (parm, type, conv_arg, flags, complain)); + else + ok = can_convert_arg (parm, type, conv_arg, flags, complain); + if (ok) return unify_success (explain_p); } @@ -20157,7 +20225,6 @@ type_unification_real (tree tparms, unsigned int xnargs, int subr, unification_kind_t strict, - int flags, vec<deferred_access_check, va_gc> **checks, bool explain_p) { @@ -20345,57 +20412,6 @@ type_unification_real (tree tparms, return unify_parameter_deduction_failure (explain_p, tparm); } - /* DR 1391: All parameters have args, now check non-dependent parms for - convertibility. */ - if (saw_undeduced < 2) - for (ia = 0, parms = xparms, args = xargs, nargs = xnargs; - parms && parms != void_list_node && ia < nargs; ) - { - parm = TREE_VALUE (parms); - - if (TREE_CODE (parm) == TYPE_PACK_EXPANSION - && (!TREE_CHAIN (parms) - || TREE_CHAIN (parms) == void_list_node)) - /* For a function parameter pack that occurs at the end of the - parameter-declaration-list, the type A of each remaining - argument of the call is compared with the type P of the - declarator-id of the function parameter pack. */ - break; - - parms = TREE_CHAIN (parms); - - if (TREE_CODE (parm) == TYPE_PACK_EXPANSION) - /* For a function parameter pack that does not occur at the - end of the parameter-declaration-list, the type of the - parameter pack is a non-deduced context. */ - continue; - - arg = args[ia]; - ++ia; - - if (uses_template_parms (parm)) - continue; - if (check_non_deducible_conversion (parm, arg, strict, flags, - explain_p)) - return 1; - - if (BRACE_ENCLOSED_INITIALIZER_P (arg) - && (TREE_CODE (parm) == ARRAY_TYPE || is_std_init_list (parm))) - { - tree elt, elttype; - unsigned int i; - - if (TREE_CODE (parm) == ARRAY_TYPE) - elttype = TREE_TYPE (parm); - else - elttype = TREE_VEC_ELT (CLASSTYPE_TI_ARGS (parm), 0); - FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (arg), i, elt) - if (check_non_deducible_conversion (elttype, elt, strict, - flags, explain_p)) - return 1; - } - } - /* Now substitute into the default template arguments. */ for (i = 0; i < ntparms; i++) { @@ -22019,7 +22035,7 @@ unify (tree tparms, tree targs, tree parm, tree arg, int strict, if (type_unification_real (tparms, targs, TYPE_ARG_TYPES (parm), args, nargs, 1, DEDUCE_EXACT, - LOOKUP_NORMAL, NULL, explain_p)) + NULL, explain_p)) return 1; if (flag_noexcept_type) @@ -22663,7 +22679,8 @@ get_bindings (tree fn, tree decl, tree explicit_args, bool check_rettype) args, ix, (check_rettype || DECL_CONV_FN_P (fn) ? TREE_TYPE (decl_type) : NULL_TREE), - DEDUCE_EXACT, LOOKUP_NORMAL, /*explain_p=*/false, + DEDUCE_EXACT, LOOKUP_NORMAL, NULL, + /*explain_p=*/false, /*decltype*/false) == error_mark_node) return NULL_TREE; @@ -26799,7 +26816,7 @@ do_auto_deduction (tree type, tree init, tree auto_node, targs = make_tree_vec (TREE_VEC_LENGTH (tparms)); int val = type_unification_real (tparms, targs, parms, &init, 1, 0, - DEDUCE_CALL, LOOKUP_NORMAL, + DEDUCE_CALL, NULL, /*explain_p=*/false); if (val > 0) { @@ -26818,7 +26835,7 @@ do_auto_deduction (tree type, tree init, tree auto_node, else error ("unable to deduce %qT from %qE", type, init); type_unification_real (tparms, targs, parms, &init, 1, 0, - DEDUCE_CALL, LOOKUP_NORMAL, + DEDUCE_CALL, NULL, /*explain_p=*/true); } return error_mark_node;
commit b8f9db98f696ec175e4e9896904c2673b031fc51 Author: Jason Merrill <ja...@redhat.com> Date: Mon Jun 25 17:07:21 2018 -0400 PR c++/80290 - memory-hog with std::pair. * pt.c (type_unification_real): Skip non-dependent conversion check for a nested list argument. (braced_init_depth): New. diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index c0f0b428d49..9a8ce883acd 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -20145,6 +20145,24 @@ try_array_deduction (tree tparms, tree targs, tree parm) /*nondeduced*/false, array_deduction_r); } +/* Returns how many levels of { } INIT contains. */ + +static int +braced_init_depth (tree init) +{ + if (!init || !BRACE_ENCLOSED_INITIALIZER_P (init)) + return 0; + unsigned i; tree val; + unsigned max = 0; + FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (init), i, val) + { + unsigned elt_d = braced_init_depth (val); + if (elt_d > max) + max = elt_d; + } + return max + 1; +} + /* Most parms like fn_type_unification. If SUBR is 1, we're being called recursively (to unify the @@ -20380,6 +20398,10 @@ type_unification_real (tree tparms, if (uses_template_parms (parm)) continue; + /* Workaround for c++/80290: avoid combinatorial explosion on + deeply nested braced init-lists. */ + if (braced_init_depth (arg) > 2) + continue; if (check_non_deducible_conversion (parm, arg, strict, flags, explain_p)) return 1;