From 5681668765e233735b4c5e6a305e73ae1f80a328 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Thu, 29 Oct 2020 14:02:59 -0400 Subject: c++: Tolerate empty initial args during normalization [PR97412] When normalizing the constraint-expression of a nested-requirement, we pass NULL_TREE as the initial template arguments for normalization, but tsubst_argument_pack is not prepared to handle a NULL_TREE args vector. This causes us to ICE when normalizing a variadic concept as part of a nested-requirement. This patch fixes the ICE by guarding the call to tsubst_template_args in normalize_concept_check appropriately. This will also enable us to simplify many of the normalization routines to just pass NULL_TREE (instead of a set of generic template arguments) as the initial template arguments. gcc/cp/ChangeLog: PR c++/97412 * constraint.cc (normalize_concept_check): Don't call tsubst_template_args when 'args' is NULL. gcc/testsuite/ChangeLog: PR c++/97412 * g++.dg/cpp2a/concepts-variadic2.C: New test. --- gcc/cp/constraint.cc | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index f4f5174..75457a2 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -686,7 +686,8 @@ normalize_concept_check (tree check, tree args, norm_info info) } /* Substitute through the arguments of the concept check. */ - targs = tsubst_template_args (targs, args, info.complain, info.in_decl); + if (args) + targs = tsubst_template_args (targs, args, info.complain, info.in_decl); if (targs == error_mark_node) return error_mark_node; -- cgit v1.1 From e1344fe7b6a96966281c78e46e777b456d5c2e19 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Thu, 29 Oct 2020 14:03:03 -0400 Subject: c++: Simplify constraint normalization routines Many of the high-level constraint normalization routines allow the caller to supply the initial template arguments for normalization, but in practice all of the callers supply something equivalent to the identity mapping(*). This patch hard-codes this prevalent choice of initial template arguments by making get_normalized_constraints always pass NULL_TREE as the args to normalize_expression. This admits some simplifications in the high-level routines, such as removing their 'args' parameter and consolidating the two versions of normalize_constraint_expression. (*): In particular, a set of generic template arguments or NULL_TREE. In the case of the two-parm version of normalize_constraint_expression, we were suspiciously using the template arguments of a concept-id when normalizing the concept-id as a constraint-expression. gcc/cp/ChangeLog: * constraint.cc (get_normalized_constraints): Remove 'args' parameter. Pass NULL_TREE as the initial template arguments to normalize_expression. (get_normalized_constraints_from_info): Remove 'args' parameter and adjust the call to get_normalized_constraints. (get_normalized_constraints_from_decl): Remove 'args' local variable and adjust call to get_normalized_constraints_from_info. (normalize_concept_definition): Remove 'args' local variable and adjust call to get_normalized_constraints. (normalize_constraint_expression): Remove the two-parameter overload. Remove 'args' parameter from the three-parameter overload and update function comment accordingly. Remove default argument from 'diag' parameter. Adjust call to get_normalized_constraints. (finish_nested_requirement): Adjust call to normalize_constraint_expression. (strictly_subsumes): Remove 'args' parameter. Adjust call to get_normalized_constraints_from_info. (weakly_subsumes): Likewise. * cp-tree.h (strictly_subsumes): Remove 'args' parameter. (weakly_subsumes): Likewise. * pt.c (process_partial_specialization): Adjust call to strictly_subsumes. (is_compatible_template_arg): Adjust call to weakly_subsumes. --- gcc/cp/constraint.cc | 69 +++++++++++++++------------------------------------- 1 file changed, 20 insertions(+), 49 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 75457a2..d6354ed 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -759,20 +759,18 @@ normalize_expression (tree t, tree args, norm_info info) static GTY((deletable)) hash_map *normalized_map; static tree -get_normalized_constraints (tree t, tree args, norm_info info) +get_normalized_constraints (tree t, norm_info info) { auto_timevar time (TV_CONSTRAINT_NORM); - return normalize_expression (t, args, info); + return normalize_expression (t, NULL_TREE, info); } /* Returns the normalized constraints from a constraint-info object - or NULL_TREE if the constraints are null. ARGS provide the initial - arguments for normalization and IN_DECL provides the declaration - to which the constraints belong. */ + or NULL_TREE if the constraints are null. IN_DECL provides the + declaration to which the constraints belong. */ static tree -get_normalized_constraints_from_info (tree ci, tree args, tree in_decl, - bool diag = false) +get_normalized_constraints_from_info (tree ci, tree in_decl, bool diag = false) { if (ci == NULL_TREE) return NULL_TREE; @@ -780,8 +778,7 @@ get_normalized_constraints_from_info (tree ci, tree args, tree in_decl, /* Substitution errors during normalization are fatal. */ ++processing_template_decl; norm_info info (in_decl, diag ? tf_norm : tf_none); - tree t = get_normalized_constraints (CI_ASSOCIATED_CONSTRAINTS (ci), - args, info); + tree t = get_normalized_constraints (CI_ASSOCIATED_CONSTRAINTS (ci), info); --processing_template_decl; return t; @@ -843,9 +840,8 @@ get_normalized_constraints_from_decl (tree d, bool diag = false) push_nested_class_guard pncs (DECL_CONTEXT (d)); - tree args = generic_targs_for (tmpl); tree ci = get_constraints (decl); - tree norm = get_normalized_constraints_from_info (ci, args, tmpl, diag); + tree norm = get_normalized_constraints_from_info (ci, tmpl, diag); if (!diag) hash_map_safe_put (normalized_map, tmpl, norm); @@ -866,11 +862,10 @@ normalize_concept_definition (tree tmpl, bool diag = false) if (OVL_P (tmpl)) tmpl = OVL_FIRST (tmpl); gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL); - tree args = generic_targs_for (tmpl); tree def = get_concept_definition (DECL_TEMPLATE_RESULT (tmpl)); ++processing_template_decl; norm_info info (tmpl, diag ? tf_norm : tf_none); - tree norm = get_normalized_constraints (def, args, info); + tree norm = get_normalized_constraints (def, info); --processing_template_decl; if (!diag) @@ -895,42 +890,20 @@ normalize_nontemplate_requirements (tree decl, bool diag = false) return get_normalized_constraints_from_decl (decl, diag); } -/* Normalize an EXPR as a constraint using ARGS. */ +/* Normalize an EXPR as a constraint. */ static tree -normalize_constraint_expression (tree expr, tree args, bool diag = false) +normalize_constraint_expression (tree expr, bool diag) { if (!expr || expr == error_mark_node) return expr; ++processing_template_decl; norm_info info (diag ? tf_norm : tf_none); - tree norm = get_normalized_constraints (expr, args, info); + tree norm = get_normalized_constraints (expr, info); --processing_template_decl; return norm; } -/* Normalize an EXPR as a constraint. */ - -static tree -normalize_constraint_expression (tree expr, bool diag = false) -{ - if (!expr || expr == error_mark_node) - return expr; - - /* For concept checks, use the supplied template arguments as those used - for normalization. Otherwise, there are no template arguments. */ - tree args; - if (concept_check_p (expr)) - { - tree id = unpack_concept_check (expr); - args = TREE_OPERAND (id, 1); - } - else - args = NULL_TREE; - - return normalize_constraint_expression (expr, args, diag); -} - /* 17.4.1.2p2. Two constraints are identical if they are formed from the same expression and the targets of the parameter mapping are equivalent. */ @@ -2998,9 +2971,7 @@ finish_compound_requirement (location_t loc, tree expr, tree type, bool noexcept tree finish_nested_requirement (location_t loc, tree expr) { - /* Currently open template headers have dummy arg vectors, so don't - pass into normalization. */ - tree norm = normalize_constraint_expression (expr, NULL_TREE, false); + tree norm = normalize_constraint_expression (expr, false); /* Build the constraint, saving its normalization as its type. */ tree r = build1 (NESTED_REQ, norm, expr); @@ -3105,25 +3076,25 @@ subsumes_constraints (tree a, tree b) return subsumes (a, b); } -/* Returns true when the constraints in CI (with arguments - ARGS) strictly subsume the associated constraints of TMPL. */ +/* Returns true when the constraints in CI strictly subsume + the associated constraints of TMPL. */ bool -strictly_subsumes (tree ci, tree args, tree tmpl) +strictly_subsumes (tree ci, tree tmpl) { - tree n1 = get_normalized_constraints_from_info (ci, args, NULL_TREE); + tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE); tree n2 = get_normalized_constraints_from_decl (tmpl); return subsumes (n1, n2) && !subsumes (n2, n1); } -/* REturns true when the constraints in CI (with arguments ARGS) subsume - the associated constraints of TMPL. */ +/* Returns true when the constraints in CI subsume the + associated constraints of TMPL. */ bool -weakly_subsumes (tree ci, tree args, tree tmpl) +weakly_subsumes (tree ci, tree tmpl) { - tree n1 = get_normalized_constraints_from_info (ci, args, NULL_TREE); + tree n1 = get_normalized_constraints_from_info (ci, NULL_TREE); tree n2 = get_normalized_constraints_from_decl (tmpl); return subsumes (n1, n2); -- cgit v1.1 From bebabf70a01b78d9bea65a0bbe8744a2adb6b373 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 2 Nov 2020 13:19:29 -0500 Subject: c++: Don't purge the satisfaction caches The adoption of P2104 ("Disallow changing concept values") means we can memoize the result of satisfaction indefinitely and no longer have to clear the satisfaction caches on various events that would affect satisfaction. To that end, this patch removes the invalidation routine clear_satisfaction_cache and adjusts its callers appropriately. This provides a large reduction in compile time and memory use in some cases. For example, on the libstdc++ test std/ranges/adaptor/join.cc, compile time and memory usage drops nearly 75%, from 7.5s/770MB to 2s/230MB, with a --enable-checking=release compiler. gcc/cp/ChangeLog: * class.c (finish_struct_1): Don't call clear_satisfaction_cache. * constexpr.c (clear_cv_and_fold_caches): Likewise. Remove bool parameter. * constraint.cc (clear_satisfaction_cache): Remove definition. * cp-tree.h (clear_satisfaction_cache): Remove declaration. (clear_cv_and_fold_caches): Remove bool parameter. * typeck2.c (store_init_value): Remove argument to clear_cv_and_fold_caches. gcc/testsuite/ChangeLog: * g++.dg/cpp2a/concepts-complete1.C: Delete test that became ill-formed after P2104. --- gcc/cp/constraint.cc | 9 --------- 1 file changed, 9 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index d6354ed..b6f6f0d 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2327,15 +2327,6 @@ save_satisfaction (tree constr, tree args, tree result) *slot = entry; } -void -clear_satisfaction_cache () -{ - if (sat_cache) - sat_cache->empty (); - if (decl_satisfied_cache) - decl_satisfied_cache->empty (); -} - /* A tool to help manage satisfaction caching in satisfy_constraint_r. Note the cache is only used when not diagnosing errors. */ -- cgit v1.1 From 71a8040716c1342547a19c25bd0203ac29258ef3 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 9 Nov 2020 18:12:42 -0500 Subject: c++: Fix ICE with variadic concepts and aliases [PR93907] This patch (naively) extends the PR93907 fix to also apply to variadic concepts invoked with a type argument pack. Without this, we ICE on the below testcase (a variadic version of concepts-using2.C) in the same manner as we used to on concepts-using2.C before r10-7133. gcc/cp/ChangeLog: PR c++/93907 * constraint.cc (tsubst_parameter_mapping): Also canonicalize the type arguments of a TYPE_ARGUMENT_PACk. gcc/testsuite/ChangeLog: PR c++/93907 * g++.dg/cpp2a/concepts-using3.C: New test, based off of concepts-using2.C. --- gcc/cp/constraint.cc | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index b6f6f0d..c871a8a 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2252,6 +2252,16 @@ tsubst_parameter_mapping (tree map, tree args, subst_info info) new_arg = tsubst_template_arg (arg, args, complain, in_decl); if (TYPE_P (new_arg)) new_arg = canonicalize_type_argument (new_arg, complain); + if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK) + { + tree pack_args = ARGUMENT_PACK_ARGS (new_arg); + for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++) + { + tree& pack_arg = TREE_VEC_ELT (pack_args, i); + if (TYPE_P (pack_arg)) + pack_arg = canonicalize_type_argument (pack_arg, complain); + } + } } if (new_arg == error_mark_node) return error_mark_node; -- cgit v1.1 From 2096ebd393a5a25921c85de1209b38c715924e22 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 9 Nov 2020 18:12:47 -0500 Subject: c++: Reuse identical ATOMIC_CONSTRs during normalization Profiling revealed that sat_hasher::equal accounts for nearly 40% of compile time in some cmcstl2 tests. This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs returned by normalize_atom. This in turn allows us to replace the expensive atomic_constraints_identical_p check in sat_hasher::equal with cheap pointer equality, with no loss in cache hit rate. With this patch, compile time for the cmcstl2 test test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with an --enable-checking=release compiler. gcc/cp/ChangeLog: * constraint.cc (atom_cache): Define this deletable hash_table. (normalize_atom): Use it to cache ATOMIC_CONSTRs when not generating diagnostics. (sat_hasher::hash): Use htab_hash_pointer instead of hash_atomic_constraint. (sat_hasher::equal): Test for pointer equality instead of atomic_constraints_identical_p. * cp-tree.h (struct atom_hasher): Moved and renamed from ... * logic.cc (struct constraint_hash): ... here. (clause::m_set): Adjust accordingly. --- gcc/cp/constraint.cc | 27 ++++++++++++++++++++++++--- 1 file changed, 24 insertions(+), 3 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index c871a8a..613ced2 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -710,6 +710,10 @@ normalize_concept_check (tree check, tree args, norm_info info) return normalize_expression (def, subst, info); } +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ + +static GTY((deletable)) hash_table *atom_cache; + /* The normal form of an atom depends on the expression. The normal form of a function call to a function concept is a check constraint for that concept. The normal form of a reference to a variable @@ -729,7 +733,19 @@ normalize_atom (tree t, tree args, norm_info info) /* Build a new info object for the atom. */ tree ci = build_tree_list (t, info.context); - return build1 (ATOMIC_CONSTR, ci, map); + tree atom = build1 (ATOMIC_CONSTR, ci, map); + if (!info.generate_diagnostics ()) + { + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal + later can cheaply compare two atoms using just pointer equality. */ + if (!atom_cache) + atom_cache = hash_table::create_ggc (31); + tree *slot = atom_cache->find_slot (atom, INSERT); + if (*slot) + return *slot; + *slot = atom; + } + return atom; } /* Returns the normal form of an expression. */ @@ -2294,13 +2310,18 @@ struct sat_hasher : ggc_ptr_hash { static hashval_t hash (sat_entry *e) { - hashval_t value = hash_atomic_constraint (e->constr); + /* Since normalize_atom caches the ATOMIC_CONSTRs it returns, + we can assume pointer-based identity for fast hashing and + comparison. Even if this assumption is violated, that's + okay, we'll just get a cache miss. */ + hashval_t value = htab_hash_pointer (e->constr); return iterative_hash_template_arg (e->args, value); } static bool equal (sat_entry *e1, sat_entry *e2) { - if (!atomic_constraints_identical_p (e1->constr, e2->constr)) + /* As in sat_hasher::hash. */ + if (e1->constr != e2->constr) return false; return template_args_equal (e1->args, e2->args); } -- cgit v1.1 From 3d56e969cb1cf44a9e3ffaef891f22ae516fdc85 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 9 Nov 2020 18:12:49 -0500 Subject: c++: Use two levels of caching in satisfy_atom This improves the effectiveness of caching in satisfy_atom by querying the cache again after we've instantiated the atom's parameter mapping. Before instantiating its mapping, the identity of an (atom,args) pair within the satisfaction cache is determined by idiosyncratic things like the level and index of each template parameter used in targets of the parameter mapping. For example, the associated constraints of foo in template concept range = range_v; template void foo () requires range && range; are range_v (with mapping T -> U) /\ range_v (with mapping T -> V). If during satisfaction the template arguments supplied for U and V are the same, then the satisfaction value of these two atoms will be the same (despite their uninstantiated parameter mappings being different). But sat_cache doesn't see this because it compares the uninstantiated parameter mapping and the supplied template arguments of sat_entry's independently. So satisy_atom on this latter atom will end up fully evaluating it instead of reusing the satisfaction value of the former. But there is a point when the two atoms do look the same to sat_cache, and that's after instantiating their parameter mappings. By querying the cache again at this point, we can avoid substituting the same instantiated parameter mapping into the same expression a second time around. With this patch, compile time and memory usage for the cmcstl2 test test/algorithm/set_symmetric_diference4.cpp drops from 11s/1.4GB to 8.5s/1.2GB with an --enable-checking=release compiler. gcc/cp/ChangeLog: * cp-tree.h (ATOMIC_CONSTR_MAP_INSTANTIATED_P): Define this flag for ATOMIC_CONSTRs. * constraint.cc (sat_hasher::hash): Use hash_atomic_constraint if the flag is set, otherwise keep using a pointer hash. (sat_hasher::equal): Return false if the flag's setting differs on two atoms. Call atomic_constraints_identical_p if the flag is set, otherwise keep using a pointer equality test. (satisfy_atom): After instantiating the parameter mapping, form another ATOMIC_CONSTR using the instantiated mapping and query the cache again. Cache the satisfaction value of both atoms. (diagnose_atomic_constraint): Simplify now that the supplied atom has an instantiated mapping. --- gcc/cp/constraint.cc | 57 +++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 43 insertions(+), 14 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 613ced2..9dd5d89 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2310,17 +2310,37 @@ struct sat_hasher : ggc_ptr_hash { static hashval_t hash (sat_entry *e) { - /* Since normalize_atom caches the ATOMIC_CONSTRs it returns, - we can assume pointer-based identity for fast hashing and - comparison. Even if this assumption is violated, that's - okay, we'll just get a cache miss. */ + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->constr)) + { + /* Atoms with instantiated mappings are built during satisfaction. + They live only inside the sat_cache, and we build one to query + the cache with each time we instantiate a mapping. */ + gcc_assert (!e->args); + return hash_atomic_constraint (e->constr); + } + + /* Atoms with uninstantiated mappings are built during normalization. + Since normalize_atom caches the atoms it returns, we can assume + pointer-based identity for fast hashing and comparison. Even if this + assumption is violated, that's okay, we'll just get a cache miss. */ hashval_t value = htab_hash_pointer (e->constr); + return iterative_hash_template_arg (e->args, value); } static bool equal (sat_entry *e1, sat_entry *e2) { - /* As in sat_hasher::hash. */ + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr) + != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->constr)) + return false; + + /* See sat_hasher::hash. */ + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr)) + { + gcc_assert (!e1->args && !e2->args); + return atomic_constraints_identical_p (e1->constr, e2->constr); + } + if (e1->constr != e2->constr) return false; return template_args_equal (e1->args, e2->args); @@ -2614,6 +2634,18 @@ satisfy_atom (tree t, tree args, subst_info info) return cache.save (boolean_false_node); } + /* Now build a new atom using the instantiated mapping. We use + this atom as a second key to the satisfaction cache, and we + also pass it to diagnose_atomic_constraint so that diagnostics + which refer to the atom display the instantiated mapping. */ + t = copy_node (t); + ATOMIC_CONSTR_MAP (t) = map; + gcc_assert (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (t)); + ATOMIC_CONSTR_MAP_INSTANTIATED_P (t) = true; + satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info.complain); + if (tree r = inst_cache.get ()) + return cache.save (r); + /* Rebuild the argument vector from the parameter mapping. */ args = get_mapped_args (map); @@ -2626,19 +2658,19 @@ satisfy_atom (tree t, tree args, subst_info info) is not satisfied. Replay the substitution. */ if (info.noisy ()) tsubst_expr (expr, args, info.complain, info.in_decl, false); - return cache.save (boolean_false_node); + return cache.save (inst_cache.save (boolean_false_node)); } /* [17.4.1.2] ... lvalue-to-rvalue conversion is performed as necessary, and EXPR shall be a constant expression of type bool. */ result = force_rvalue (result, info.complain); if (result == error_mark_node) - return cache.save (error_mark_node); + return cache.save (inst_cache.save (error_mark_node)); if (!same_type_p (TREE_TYPE (result), boolean_type_node)) { if (info.noisy ()) diagnose_atomic_constraint (t, map, result, info); - return cache.save (error_mark_node); + return cache.save (inst_cache.save (error_mark_node)); } /* Compute the value of the constraint. */ @@ -2655,7 +2687,7 @@ satisfy_atom (tree t, tree args, subst_info info) if (result == boolean_false_node && info.noisy ()) diagnose_atomic_constraint (t, map, result, info); - return cache.save (result); + return cache.save (inst_cache.save (result)); } /* Determine if the normalized constraint T is satisfied. @@ -3495,14 +3527,11 @@ diagnose_atomic_constraint (tree t, tree map, tree result, subst_info info) diagnose_requires_expr (expr, map, info.in_decl); break; default: - tree a = copy_node (t); - ATOMIC_CONSTR_MAP (a) = map; if (!same_type_p (TREE_TYPE (result), boolean_type_node)) error_at (loc, "constraint %qE has type %qT, not %", - a, TREE_TYPE (result)); + t, TREE_TYPE (result)); else - inform (loc, "the expression %qE evaluated to %", a); - ggc_free (a); + inform (loc, "the expression %qE evaluated to %", t); } } -- cgit v1.1 From d3fd75d869480044213553000d2c9dc236a4f7af Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 9 Nov 2020 18:16:48 -0500 Subject: c++: Consider only relevant template arguments in sat_hasher A large source of cache misses in satisfy_atom is caused by the identity of an (atom,args) pair within the satisfaction cache being determined by the entire set of supplied template arguments rather than by the subset of template arguments that the atom actually depends on. For instance, consider template concept range = range_v; template void foo () requires range; template void bar () requires range; The associated constraints of foo and bar are equivalent: they both consist of the atom range_v (with mapping T -> U). But the sat_cache currently will never reuse a satisfaction value between the two atoms because foo has one template parameter and bar has two, and the satisfaction cache conservatively assumes that all template parameters of the constrained decl are relevant to a satisfaction value of one of its atoms. This patch eliminates this assumption and makes the sat_cache instead care about just the subset of args of an (atom,args) pair that is relevant to satisfaction. This patch additionally fixes a seemingly latent bug that was found when testing against range-v3. In the testcase concepts-decltype2.C below, during normalization of f's constraints we end up forming a TARGET_EXPR whose _SLOT has a DECL_CONTEXT that points to g instead of f because current_function_decl is not updated before we start normalizing. This patch fixes this accordingly, and also adds a sanity check to keep_template_parm to verify each found parameter has a valid index. With this patch, compile time and memory usage for the cmcstl2 test test/algorithm/set_symmetric_difference4.cpp drops from 8.5s/1.2GB to 3.5s/0.4GB. gcc/cp/ChangeLog: * constraint.cc (norm_info::norm_info): Initialize orig_decl. (norm_info::orig_decl): New data member. (normalize_atom): When caching an atom for the first time, compute a list of template parameters used in the targets of the parameter mapping and store it in the TREE_TYPE of the mapping. (get_normalized_constraints_from_decl): Set current_function_decl appropriately when normalizing. As an optimization, don't set up a push_nested_class_guard when decl has no constraints. (sat_hasher::hash): Use this list to hash only the template arguments that are relevant to the atom. (satisfy_atom): Use this list to compare only the template arguments that are relevant to the atom. * pt.c (keep_template_parm): Do a sanity check on the parameter's index when flag_checking. --- gcc/cp/constraint.cc | 76 +++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 70 insertions(+), 6 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 9dd5d89..8691281 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -616,7 +616,8 @@ struct norm_info : subst_info norm_info (tree in_decl, tsubst_flags_t complain) : subst_info (tf_warning_or_error | complain, in_decl), - context (make_context (in_decl)) + context (make_context (in_decl)), + orig_decl (in_decl) {} bool generate_diagnostics() const @@ -647,6 +648,12 @@ struct norm_info : subst_info for that check. */ tree context; + + /* The declaration whose constraints we're normalizing. The targets + of the parameter mapping of each atom will be in terms of the + template parameters of ORIG_DECL. */ + + tree orig_decl = NULL_TREE; }; static tree normalize_expression (tree, tree, norm_info); @@ -743,6 +750,28 @@ normalize_atom (tree t, tree args, norm_info info) tree *slot = atom_cache->find_slot (atom, INSERT); if (*slot) return *slot; + + /* Find all template parameters used in the targets of the parameter + mapping, and store a list of them in the TREE_TYPE of the mapping. + This list will be used by sat_hasher to determine the subset of + supplied template arguments that the satisfaction value of the atom + depends on. */ + if (map) + { + tree targets = make_tree_vec (list_length (map)); + int i = 0; + for (tree node = map; node; node = TREE_CHAIN (node)) + { + tree target = TREE_PURPOSE (node); + TREE_VEC_ELT (targets, i++) = target; + } + tree ctx_parms = (info.orig_decl + ? DECL_TEMPLATE_PARMS (info.orig_decl) + : current_template_parms); + tree target_parms = find_template_parameters (targets, ctx_parms); + TREE_TYPE (map) = target_parms; + } + *slot = atom; } return atom; @@ -854,10 +883,17 @@ get_normalized_constraints_from_decl (tree d, bool diag = false) if (tree *p = hash_map_safe_get (normalized_map, tmpl)) return *p; - push_nested_class_guard pncs (DECL_CONTEXT (d)); + tree norm = NULL_TREE; + if (tree ci = get_constraints (decl)) + { + push_nested_class_guard pncs (DECL_CONTEXT (d)); + + temp_override ovr (current_function_decl); + if (TREE_CODE (decl) == FUNCTION_DECL) + current_function_decl = decl; - tree ci = get_constraints (decl); - tree norm = get_normalized_constraints_from_info (ci, tmpl, diag); + norm = get_normalized_constraints_from_info (ci, tmpl, diag); + } if (!diag) hash_map_safe_put (normalized_map, tmpl, norm); @@ -2325,7 +2361,21 @@ struct sat_hasher : ggc_ptr_hash assumption is violated, that's okay, we'll just get a cache miss. */ hashval_t value = htab_hash_pointer (e->constr); - return iterative_hash_template_arg (e->args, value); + if (tree map = ATOMIC_CONSTR_MAP (e->constr)) + /* Only the parameters that are used in the targets of the mapping + affect the satisfaction value of the atom. So we consider only + the arguments for these parameters, and ignore the rest. */ + for (tree target_parms = TREE_TYPE (map); + target_parms; + target_parms = TREE_CHAIN (target_parms)) + { + int level, index; + tree parm = TREE_VALUE (target_parms); + template_parm_level_and_index (parm, &level, &index); + tree arg = TMPL_ARG (e->args, level, index); + value = iterative_hash_template_arg (arg, value); + } + return value; } static bool equal (sat_entry *e1, sat_entry *e2) @@ -2343,7 +2393,21 @@ struct sat_hasher : ggc_ptr_hash if (e1->constr != e2->constr) return false; - return template_args_equal (e1->args, e2->args); + + if (tree map = ATOMIC_CONSTR_MAP (e1->constr)) + for (tree target_parms = TREE_TYPE (map); + target_parms; + target_parms = TREE_CHAIN (target_parms)) + { + int level, index; + tree parm = TREE_VALUE (target_parms); + template_parm_level_and_index (parm, &level, &index); + tree arg1 = TMPL_ARG (e1->args, level, index); + tree arg2 = TMPL_ARG (e2->args, level, index); + if (!template_args_equal (arg1, arg2)) + return false; + } + return true; } }; -- cgit v1.1 From ca23341b28cd3af7985b83a6479107d9ea145a90 Mon Sep 17 00:00:00 2001 From: Martin Sebor Date: Wed, 25 Nov 2020 14:05:01 -0700 Subject: Clean up -Wformat-diag warnings (PR bootstrap/97622, PR bootstrap/94982) gcc/c-family/ChangeLog: PR bootstrap/94982 * c-attribs.c (handle_patchable_function_entry_attribute): Avoid -Wformat-diag. gcc/cp/ChangeLog: PR bootstrap/94982 * constraint.cc (debug_argument_list): Avoid -Wformat-diag. * error.c (function_category): Same. (print_template_differences): Same. * logic.cc (debug): Same. * name-lookup.c (lookup_using_decl): Same. * parser.c (maybe_add_cast_fixit): Same. (cp_parser_template_introduction): Same. * typeck.c (access_failure_info::add_fixit_hint): Same. gcc/ChangeLog: PR bootstrap/97622 PR bootstrap/94982 * config/i386/i386-options.c (ix86_valid_target_attribute_inner_p): Avoid -Wformat-diag. * digraph.cc (struct test_edge): Same. * dumpfile.c (dump_loc): Same. (dump_context::begin_scope): Same. * edit-context.c (edited_file::print_diff): Same. (edited_file::print_diff_hunk): Same. * json.cc (object::print): Same. * lto-wrapper.c (merge_and_complain): Same. * reload.c (find_reloads): Same. * tree-diagnostic-path.cc (print_path_summary_as_text): Same. * ubsan.c (ubsan_type_descriptor): Same. gcc/jit/ChangeLog: PR bootstrap/94982 * jit-recording.c (recording::function::dump_to_dot): Avoid -Wformat-diag. (recording::block::dump_to_dot): Same. gcc/testsuite/ChangeLog: PR bootstrap/94982 * c-c++-common/patchable_function_entry-error-3.c: Adjust text of expected warning. --- gcc/cp/constraint.cc | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 8691281..00d2f2e 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -533,9 +533,9 @@ debug_argument_list (tree args) { tree arg = TREE_VEC_ELT (args, i); if (TYPE_P (arg)) - verbatim ("ARG %qT", arg); + verbatim ("argument %qT", arg); else - verbatim ("ARG %qE", arg); + verbatim ("argument %qE", arg); } } -- cgit v1.1 From 904ac8577521b8152b97e9b549c1a1ca569a3d1f Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Sat, 5 Dec 2020 13:47:22 -0500 Subject: c++: Distinguish unsatisfaction vs errors during satisfaction [PR97093] During satisfaction, the flag info.noisy() controls three things: whether to diagnose ill-formed satisfaction (such as the satisfaction value of an atom being non-bool or non-constant); whether to diagnose unsatisfaction; and whether to bypass the satisfaction cache. The flag turns out to be too coarse however, because in some cases we want to diagnose ill-formed satisfaction (and bypass the satisfaction cache) but not diagnose unsatisfaction, for instance when replaying an erroneous satisfaction result from constraint_satisfaction_value, evaluate_concept_check and tsubst_nested_requirement. And when noisily evaluating a disjunction, we want to first evaluate its branches noisily (bypassing the satisfaction cache) but suppress unsatisfaction diagnostics. We currently work around this by instead first evaluating each branch quietly, but that means the recursive calls to satisfy_atom will use the satisfaction cache. To fix this, this patch adds the info.diagnose_unsatisfaction_p() flag, which refines the info.noisy() flag as part of a new sat_info class that derives from subst_info. During satisfaction, info.noisy() now controls whether to diagnose ill-formed satisfaction, and info.diagnose_unsatisfaction_p() controls whether to additionally diagnose unsatisfaction. This enables us to address the above two issues straightforwardly. Incidentally, the change to satisfy_disjunction suppresses the ICE in the PR97093 testcase because we no longer insert atoms into the satisfaction cache that have been incorrectly re-normalized in diagnose_nested_requirement (after losing the necessary template context). But the underlying re-normalization issue remains, and will be fixed in a subsequent patch. gcc/cp/ChangeLog: PR c++/97093 * constraint.cc (struct sat_info): Define. (tsubst_nested_requirement): Pass a sat_info object to satisfy_constraint. (satisfy_constraint_r): Take a sat_info argument instead of subst_info. (satisfy_conjunction): Likewise. (satisfy_disjunction): Likewise. Instead of first evaluating each branch quietly, evaluate each branch only with unsatisfaction diagnostics disabled. Exit early if evaluation of a branch returns error_mark_node. (satisfy_atom): Take a sat_info argument instead of subst_info. Fix a comment. Check diagnose_unsatisfaction_p() instead of noisy() before replaying a substitution failure. (satisfy_constraint): Take a sat_info argument instead of subst_info. (satisfy_associated_constraints): Likewise. (satisfy_constraint_expression): Likewise. (satisfy_declaration_constraints): Likewise. (constraint_satisfaction_value): Likewise and adjust accordingly. Fix formatting. (constraints_satisfied_p): Pass a sat_info object to constraint_satisfaction_value. (evaluate_concept_check): Pass a sat_info object to satisfy_constraint_expression. (diagnose_nested_requirement): Likewise. (diagnose_constraints): Pass an appropriate sat_info object to constraint_satisfaction_value. gcc/testsuite/ChangeLog: PR c++/97093 * g++.dg/concepts/pr94252.C: Verify we no longer issue a spurious unsatisfaction note when diagnosing ill-formed satisfaction. * g++.dg/cpp2a/concepts-requires18.C: No longer expect a spurious unsatisfaction diagnostic when evaluating the nested-requirement subst of a requires-expression that appears outside of a template. * g++.dg/cpp2a/concepts-requires21.C: Verify we no longer issue a spurious unsatisfaction note when evaluating a nested-requirement of a requires-expression that appears outside of a template. * g++.dg/cpp2a/concepts-nonbool3.C: New test. * g++.dg/cpp2a/concepts-pr97093.C: New test. --- gcc/cp/constraint.cc | 155 +++++++++++++++++++++++++++++++++------------------ 1 file changed, 102 insertions(+), 53 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 00d2f2e..1117508 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -98,7 +98,42 @@ struct subst_info tree in_decl; }; -static tree satisfy_constraint (tree, tree, subst_info); +/* Provides additional context for satisfaction. + + The flag noisy() controls whether to diagnose ill-formed satisfaction, + such as the satisfaction value of an atom being non-bool or non-constant. + + The flag diagnose_unsatisfaction_p() controls whether to explain why + a constraint is not satisfied. + + The entrypoints to satisfaction for which we set noisy+unsat are + diagnose_constraints and diagnose_nested_requirement. The entrypoints for + which we set noisy-unsat are the replays inside constraint_satisfaction_value, + evaluate_concept_check and tsubst_nested_requirement. In other entrypoints, + e.g. constraints_satisfied_p, we enter satisfaction quietly (both flags + cleared). */ + +struct sat_info : subst_info +{ + sat_info (tsubst_flags_t cmp, tree in, bool diag_unsat = false) + : subst_info (cmp, in), diagnose_unsatisfaction (diag_unsat) + { + if (diagnose_unsatisfaction_p ()) + gcc_checking_assert (noisy ()); + } + + /* True if we should diagnose the cause of satisfaction failure. + Implies noisy(). */ + bool + diagnose_unsatisfaction_p () const + { + return diagnose_unsatisfaction; + } + + bool diagnose_unsatisfaction; +}; + +static tree satisfy_constraint (tree, tree, sat_info); /* True if T is known to be some type other than bool. Note that this is false for dependent types and errors. */ @@ -2059,10 +2094,11 @@ tsubst_nested_requirement (tree t, tree args, subst_info info) { /* Ensure that we're in an evaluation context prior to satisfaction. */ tree norm = TREE_TYPE (t); - tree result = satisfy_constraint (norm, args, info); + tree result = satisfy_constraint (norm, args, + sat_info (info.complain, info.in_decl)); if (result == error_mark_node && info.quiet ()) { - subst_info noisy (tf_warning_or_error, info.in_decl); + sat_info noisy (tf_warning_or_error, info.in_decl); satisfy_constraint (norm, args, noisy); } if (result != boolean_true_node) @@ -2499,12 +2535,12 @@ tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl) return expr; } -static tree satisfy_constraint_r (tree, tree, subst_info info); +static tree satisfy_constraint_r (tree, tree, sat_info info); /* Compute the satisfaction of a conjunction. */ static tree -satisfy_conjunction (tree t, tree args, subst_info info) +satisfy_conjunction (tree t, tree args, sat_info info) { tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, info); if (lhs == error_mark_node || lhs == boolean_false_node) @@ -2558,20 +2594,25 @@ collect_operands_of_disjunction (tree t, auto_vec *operands) /* Compute the satisfaction of a disjunction. */ static tree -satisfy_disjunction (tree t, tree args, subst_info info) +satisfy_disjunction (tree t, tree args, sat_info info) { - /* Evaluate the operands quietly. */ - subst_info quiet (tf_none, NULL_TREE); + /* Evaluate each operand with unsatisfaction diagnostics disabled. */ + sat_info sub = info; + sub.diagnose_unsatisfaction = false; - /* Register the constraint for diagnostics, if needed. */ - diagnosing_failed_constraint failure (t, args, info.noisy ()); + tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, sub); + if (lhs == boolean_true_node || lhs == error_mark_node) + return lhs; - tree lhs = satisfy_constraint_r (TREE_OPERAND (t, 0), args, quiet); - if (lhs == boolean_true_node) - return boolean_true_node; - tree rhs = satisfy_constraint_r (TREE_OPERAND (t, 1), args, quiet); - if (rhs != boolean_true_node && info.noisy ()) + tree rhs = satisfy_constraint_r (TREE_OPERAND (t, 1), args, sub); + if (rhs == boolean_true_node || rhs == error_mark_node) + return rhs; + + /* Both branches evaluated to false. Explain the satisfaction failure in + each branch. */ + if (info.diagnose_unsatisfaction_p ()) { + diagnosing_failed_constraint failure (t, args, info.noisy ()); cp_expr disj_expr = CONSTR_EXPR (t); inform (disj_expr.get_location (), "no operand of the disjunction is satisfied"); @@ -2592,7 +2633,8 @@ satisfy_disjunction (tree t, tree args, subst_info info) } } } - return rhs; + + return boolean_false_node; } /* Ensures that T is a truth value and not (accidentally, as sometimes @@ -2673,7 +2715,7 @@ static void diagnose_atomic_constraint (tree, tree, tree, subst_info); /* Compute the satisfaction of an atomic constraint. */ static tree -satisfy_atom (tree t, tree args, subst_info info) +satisfy_atom (tree t, tree args, sat_info info) { satisfaction_cache cache (t, args, info.complain); if (tree r = cache.get ()) @@ -2691,9 +2733,9 @@ satisfy_atom (tree t, tree args, subst_info info) tree map = tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, quiet); if (map == error_mark_node) { - /* If instantiation of the parameter mapping fails, the program - is ill-formed. */ - if (info.noisy()) + /* If instantiation of the parameter mapping fails, the constraint is + not satisfied. Replay the substitution. */ + if (info.diagnose_unsatisfaction_p ()) tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info); return cache.save (boolean_false_node); } @@ -2720,7 +2762,7 @@ satisfy_atom (tree t, tree args, subst_info info) { /* If substitution results in an invalid type or expression, the constraint is not satisfied. Replay the substitution. */ - if (info.noisy ()) + if (info.diagnose_unsatisfaction_p ()) tsubst_expr (expr, args, info.complain, info.in_decl, false); return cache.save (inst_cache.save (boolean_false_node)); } @@ -2748,7 +2790,7 @@ satisfy_atom (tree t, tree args, subst_info info) result = error_mark_node; } result = satisfaction_value (result); - if (result == boolean_false_node && info.noisy ()) + if (result == boolean_false_node && info.diagnose_unsatisfaction_p ()) diagnose_atomic_constraint (t, map, result, info); return cache.save (inst_cache.save (result)); @@ -2766,7 +2808,7 @@ satisfy_atom (tree t, tree args, subst_info info) constraint only matters for subsumption. */ static tree -satisfy_constraint_r (tree t, tree args, subst_info info) +satisfy_constraint_r (tree t, tree args, sat_info info) { if (t == error_mark_node) return error_mark_node; @@ -2787,7 +2829,7 @@ satisfy_constraint_r (tree t, tree args, subst_info info) /* Check that the normalized constraint T is satisfied for ARGS. */ static tree -satisfy_constraint (tree t, tree args, subst_info info) +satisfy_constraint (tree t, tree args, sat_info info) { auto_timevar time (TV_CONSTRAINT_SAT); @@ -2805,7 +2847,7 @@ satisfy_constraint (tree t, tree args, subst_info info) value (either true, false, or error). */ static tree -satisfy_associated_constraints (tree t, tree args, subst_info info) +satisfy_associated_constraints (tree t, tree args, sat_info info) { /* If there are no constraints then this is trivially satisfied. */ if (!t) @@ -2823,7 +2865,7 @@ satisfy_associated_constraints (tree t, tree args, subst_info info) satisfaction value. */ static tree -satisfy_constraint_expression (tree t, tree args, subst_info info) +satisfy_constraint_expression (tree t, tree args, sat_info info) { if (t == error_mark_node) return error_mark_node; @@ -2852,12 +2894,12 @@ satisfy_constraint_expression (tree t, tree args, subst_info info) tree satisfy_constraint_expression (tree expr) { - subst_info info (tf_none, NULL_TREE); + sat_info info (tf_none, NULL_TREE); return satisfy_constraint_expression (expr, NULL_TREE, info); } static tree -satisfy_declaration_constraints (tree t, subst_info info) +satisfy_declaration_constraints (tree t, sat_info info) { gcc_assert (DECL_P (t)); const tree saved_t = t; @@ -2917,7 +2959,7 @@ satisfy_declaration_constraints (tree t, subst_info info) } static tree -satisfy_declaration_constraints (tree t, tree args, subst_info info) +satisfy_declaration_constraints (tree t, tree args, sat_info info) { /* Update the declaration for diagnostics. */ info.in_decl = t; @@ -2942,9 +2984,8 @@ satisfy_declaration_constraints (tree t, tree args, subst_info info) } static tree -constraint_satisfaction_value (tree t, tsubst_flags_t complain) +constraint_satisfaction_value (tree t, sat_info info) { - subst_info info (complain, NULL_TREE); tree r; if (DECL_P (t)) r = satisfy_declaration_constraints (t, info); @@ -2952,26 +2993,31 @@ constraint_satisfaction_value (tree t, tsubst_flags_t complain) r = satisfy_constraint_expression (t, NULL_TREE, info); if (r == error_mark_node && info.quiet () && !(DECL_P (t) && TREE_NO_WARNING (t))) - { - constraint_satisfaction_value (t, tf_warning_or_error); - if (DECL_P (t)) - /* Avoid giving these errors again. */ - TREE_NO_WARNING (t) = true; - } + { + /* Replay the error with re-normalized requirements. */ + sat_info noisy (tf_warning_or_error, info.in_decl); + constraint_satisfaction_value (t, noisy); + if (DECL_P (t)) + /* Avoid giving these errors again. */ + TREE_NO_WARNING (t) = true; + } return r; } static tree -constraint_satisfaction_value (tree t, tree args, tsubst_flags_t complain) +constraint_satisfaction_value (tree t, tree args, sat_info info) { - subst_info info (complain, NULL_TREE); tree r; if (DECL_P (t)) r = satisfy_declaration_constraints (t, args, info); else r = satisfy_constraint_expression (t, args, info); if (r == error_mark_node && info.quiet ()) - constraint_satisfaction_value (t, args, tf_warning_or_error); + { + /* Replay the error with re-normalized requirements. */ + sat_info noisy (tf_warning_or_error, info.in_decl); + constraint_satisfaction_value (t, args, noisy); + } return r; } @@ -2984,7 +3030,8 @@ constraints_satisfied_p (tree t) if (!flag_concepts) return true; - return constraint_satisfaction_value (t, tf_none) == boolean_true_node; + sat_info quiet (tf_none, NULL_TREE); + return constraint_satisfaction_value (t, quiet) == boolean_true_node; } /* True iff the result of satisfying T with ARGS is BOOLEAN_TRUE_NODE @@ -2996,7 +3043,8 @@ constraints_satisfied_p (tree t, tree args) if (!flag_concepts) return true; - return constraint_satisfaction_value (t, args, tf_none) == boolean_true_node; + sat_info quiet (tf_none, NULL_TREE); + return constraint_satisfaction_value (t, args, quiet) == boolean_true_node; } /* Evaluate a concept check of the form C. This is only used for the @@ -3011,14 +3059,14 @@ evaluate_concept_check (tree check, tsubst_flags_t complain) gcc_assert (concept_check_p (check)); /* Check for satisfaction without diagnostics. */ - subst_info quiet (tf_none, NULL_TREE); + sat_info quiet (tf_none, NULL_TREE); tree result = satisfy_constraint_expression (check, NULL_TREE, quiet); if (result == error_mark_node && (complain & tf_error)) - { - /* Replay the error with re-normalized requirements. */ - subst_info noisy (tf_warning_or_error, NULL_TREE); - satisfy_constraint_expression (check, NULL_TREE, noisy); - } + { + /* Replay the error with re-normalized requirements. */ + sat_info noisy (tf_warning_or_error, NULL_TREE); + satisfy_constraint_expression (check, NULL_TREE, noisy); + } return result; } @@ -3496,7 +3544,7 @@ diagnose_nested_requirement (tree req, tree args) /* Quietly check for satisfaction first. We can elaborate details later if needed. */ tree norm = TREE_TYPE (req); - subst_info info (tf_none, NULL_TREE); + sat_info info (tf_none, NULL_TREE); tree result = satisfy_constraint (norm, args, info); if (result == boolean_true_node) return; @@ -3507,7 +3555,7 @@ diagnose_nested_requirement (tree req, tree args) { /* Replay the substitution error. */ inform (loc, "nested requirement %qE is not satisfied, because", expr); - subst_info noisy (tf_warning_or_error, NULL_TREE); + sat_info noisy (tf_warning_or_error, NULL_TREE, /*diag_unsat=*/true); satisfy_constraint_expression (expr, args, noisy); } else @@ -3651,11 +3699,12 @@ diagnose_constraints (location_t loc, tree t, tree args) if (concepts_diagnostics_max_depth == 0) return; - /* Replay satisfaction, but diagnose errors. */ + /* Replay satisfaction, but diagnose unsatisfaction. */ + sat_info noisy (tf_warning_or_error, NULL_TREE, /*diag_unsat=*/true); if (!args) - constraint_satisfaction_value (t, tf_warning_or_error); + constraint_satisfaction_value (t, noisy); else - constraint_satisfaction_value (t, args, tf_warning_or_error); + constraint_satisfaction_value (t, args, noisy); static bool suggested_p; if (concepts_diagnostics_max_depth_exceeded_p -- cgit v1.1 From 40234200864b6c0d0079abbcdc7a4139b60257ff Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Sat, 5 Dec 2020 13:44:20 -0500 Subject: c++: Normalize nested-requirements twice at parse time [PR97093] The re-normalization performed from diagnose_nested_requirement doesn't always work because we may have already lost the necessary template context that determines the set of in-scope template parameters used by the nested-requirement. This leads to normalization producing atoms that have incomplete/bogus parameter mappings, which breaks satisfaction. To fix this, we could just use the normal form that we previously computed at parse time, but this normal form lacks the diagnostic information that leads to good error messages. Instead, this patch makes diagnose_nested_requirement normalize twice at parse time -- once without diagnostic information and once with -- so that routines can use the "regular" normal form when performing satisfaction quietly and the "diagnostic" normal form when performing satisfaction noisily. Moreover, this patch makes tsubst_nested_requirement always first perform satisfaction quietly so that the satisfaction cache can get consistently utilized. This patch also adds some sanity checks to build_parameter_mapping that would have caught the underlying bug sooner (and deterministically). gcc/cp/ChangeLog: PR c++/97093 * constraint.cc (parameter_mapping_equivalent_p): Add some sanity checks. Clarify comment. (tsubst_nested_requirement): Always perform satisfaction quietly first. If that yields an erroneous result, emit a context message and replay satisfaction noisily with the diagnostic normal form. (finish_nested_requirement): Normalize the constraint-expression twice, once with diagnostic information and once without. Store them in a TREE_LIST within the TREE_TYPE. (diagnose_nested_requirement): When replaying satisfaction, use the diagnostic normal form instead of renormalizing on the spot. gcc/testsuite/ChangeLog: PR c++/97093 * g++.dg/cpp2a/concepts-requires22.C: New test. --- gcc/cp/constraint.cc | 41 ++++++++++++++++++++++++++--------------- 1 file changed, 26 insertions(+), 15 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 1117508..b4c501b 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -619,7 +619,8 @@ build_parameter_mapping (tree expr, tree args, tree decl) return map; } -/* True if the parameter mappings of two atomic constraints are equivalent. */ +/* True if the parameter mappings of two atomic constraints formed + from the same expression are equivalent. */ static bool parameter_mapping_equivalent_p (tree t1, tree t2) @@ -628,6 +629,7 @@ parameter_mapping_equivalent_p (tree t1, tree t2) tree map2 = ATOMIC_CONSTR_MAP (t2); while (map1 && map2) { + gcc_checking_assert (TREE_VALUE (map1) == TREE_VALUE (map2)); tree arg1 = TREE_PURPOSE (map1); tree arg2 = TREE_PURPOSE (map2); if (!template_args_equal (arg1, arg2)) @@ -635,6 +637,7 @@ parameter_mapping_equivalent_p (tree t1, tree t2) map1 = TREE_CHAIN (map1); map2 = TREE_CHAIN (map2); } + gcc_checking_assert (!map1 && !map2); return true; } @@ -2092,14 +2095,16 @@ tsubst_compound_requirement (tree t, tree args, subst_info info) static tree tsubst_nested_requirement (tree t, tree args, subst_info info) { - /* Ensure that we're in an evaluation context prior to satisfaction. */ - tree norm = TREE_TYPE (t); - tree result = satisfy_constraint (norm, args, - sat_info (info.complain, info.in_decl)); - if (result == error_mark_node && info.quiet ()) + /* Perform satisfaction quietly with the regular normal form. */ + sat_info quiet (tf_none, info.in_decl); + tree norm = TREE_VALUE (TREE_TYPE (t)); + tree diag_norm = TREE_PURPOSE (TREE_TYPE (t)); + tree result = satisfy_constraint (norm, args, quiet); + if (result == error_mark_node) { + /* Replay the error using the diagnostic normal form. */ sat_info noisy (tf_warning_or_error, info.in_decl); - satisfy_constraint (norm, args, noisy); + satisfy_constraint (diag_norm, args, noisy); } if (result != boolean_true_node) return error_mark_node; @@ -3137,10 +3142,15 @@ finish_compound_requirement (location_t loc, tree expr, tree type, bool noexcept tree finish_nested_requirement (location_t loc, tree expr) { - tree norm = normalize_constraint_expression (expr, false); + /* We need to normalize the constraints now, at parse time, while + we have the necessary template context. We normalize twice, + once without diagnostic information and once with, which we'll + later use for quiet and noisy satisfaction respectively. */ + tree norm = normalize_constraint_expression (expr, /*diag=*/false); + tree diag_norm = normalize_constraint_expression (expr, /*diag=*/true); - /* Build the constraint, saving its normalization as its type. */ - tree r = build1 (NESTED_REQ, norm, expr); + /* Build the constraint, saving its two normalizations as its type. */ + tree r = build1 (NESTED_REQ, build_tree_list (diag_norm, norm), expr); SET_EXPR_LOCATION (r, loc); return r; } @@ -3541,9 +3551,10 @@ diagnose_type_requirement (tree req, tree args, tree in_decl) static void diagnose_nested_requirement (tree req, tree args) { - /* Quietly check for satisfaction first. We can elaborate details - later if needed. */ - tree norm = TREE_TYPE (req); + /* Quietly check for satisfaction first using the regular normal form. + We can elaborate details later if needed. */ + tree norm = TREE_VALUE (TREE_TYPE (req)); + tree diag_norm = TREE_PURPOSE (TREE_TYPE (req)); sat_info info (tf_none, NULL_TREE); tree result = satisfy_constraint (norm, args, info); if (result == boolean_true_node) @@ -3553,10 +3564,10 @@ diagnose_nested_requirement (tree req, tree args) location_t loc = cp_expr_location (expr); if (diagnosing_failed_constraint::replay_errors_p ()) { - /* Replay the substitution error. */ + /* Replay the substitution error using the diagnostic normal form. */ inform (loc, "nested requirement %qE is not satisfied, because", expr); sat_info noisy (tf_warning_or_error, NULL_TREE, /*diag_unsat=*/true); - satisfy_constraint_expression (expr, args, noisy); + satisfy_constraint (diag_norm, args, noisy); } else inform (loc, "nested requirement %qE is not satisfied", expr); -- cgit v1.1 From 20f292863f6ed230335c443893d4db664a8140d0 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Thu, 17 Dec 2020 22:18:00 -0500 Subject: c++: Diagnose unstable satisfaction This implements lightweight heuristical detection and diagnosing of satisfaction whose result changes at different points in the program, which renders the program ill-formed NDR as of P2104. We've recently started to more aggressively cache satisfaction results, and so the goal with this patch is to make this caching behavior more transparent to the user. A satisfaction result is flagged as "potentially unstable" (at the atom granularity) if during its computation, some type completion failure occurs. This is detected by making complete_type_or_maybe_complain increment a counter upon failure and comparing the value of the counter before and after satisfaction. (We don't instrument complete_type directly because it's used "opportunistically" in many spots where type completion failure doesn't necessary lead to substitution failure.) Such flagged satisfaction results are always recomputed from scratch, even when performing satisfaction quietly. When saving a satisfaction result, we now compare the computed result with the cached result, and if they differ, proceed with diagnosing the instability. Most of the implementation is confined to the satisfaction_cache class, which has been completely rewritten. gcc/cp/ChangeLog: * constraint.cc (failed_type_completion_count): New. (note_failed_type_completion_for_satisfaction): New. (sat_entry::constr): Rename to ... (sat_entry::atom): ... this. (sat_entry::location): New member. (sat_entry::maybe_unstable): New member. (sat_entry::diagnose_instability): New member. (struct sat_hasher): Adjust after the above renaming. (get_satisfaction, save_satisfaction): Remove. (satisfaction_cache): Rewrite completely. (satisfy_atom): When instantiation of the parameter mapping fails, set diagnose_instability. Propagate location from inst_cache.entry to cache.entry if the secondary lookup succeeded. (satisfy_declaration_constraints): When failed_type_completion_count differs before and after satisfaction, then don't cache the satisfaction result. * cp-tree.h (note_failed_type_completion_for_satisfaction): Declare. * pt.c (tsubst) : Use complete_type_or_maybe_complain instead of open-coding it. * typeck.c (complete_type_or_maybe_complain): Call note_failed_type_completion_for_satisfaction when type completion fails. gcc/testsuite/ChangeLog: * g++.dg/cpp2a/concepts-complete1.C: New test. * g++.dg/cpp2a/concepts-complete2.C: New test. * g++.dg/cpp2a/concepts-complete3.C: New test. --- gcc/cp/constraint.cc | 265 ++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 211 insertions(+), 54 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index b4c501b..47cf882 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2374,35 +2374,82 @@ tsubst_parameter_mapping (tree map, tree args, tsubst_flags_t complain, tree in_ Constraint satisfaction ---------------------------------------------------------------------------*/ -/* Hash functions for satisfaction entries. */ +/* A counter incremented by note_failed_type_completion_for_satisfaction(). + It's used by the satisfaction caches in order to flag "potentially unstable" + satisfaction results. */ + +static unsigned failed_type_completion_count; + +/* Called whenever a type completion failure occurs that definitely affects + the semantics of the program, by e.g. inducing substitution failure. */ + +void +note_failed_type_completion_for_satisfaction (tree type) +{ + gcc_checking_assert (!COMPLETE_TYPE_P (type)); + if (CLASS_TYPE_P (type) + && CLASSTYPE_TEMPLATE_INSTANTIATION (type)) + /* After instantiation, a class template specialization that's + incomplete will remain incomplete, so for our purposes we can + ignore this completion failure event. */; + else + ++failed_type_completion_count; +} + +/* Hash functions and data types for satisfaction cache entries. */ struct GTY((for_user)) sat_entry { - tree constr; + /* The relevant ATOMIC_CONSTR. */ + tree atom; + + /* The relevant template arguments. */ tree args; + + /* The result of satisfaction of ATOM+ARGS. + This is either boolean_true_node, boolean_false_node or error_mark_node, + where error_mark_node indicates ill-formed satisfaction. + It's set to NULL_TREE while computing satisfaction of ATOM+ARGS for + the first time. */ tree result; + + /* The value of input_location when satisfaction of ATOM+ARGS was first + performed. */ + location_t location; + + /* True if this satisfaction result is flagged as "potentially unstable", + i.e. the result might change at different points in the program if + recomputed from scratch (which would be ill-formed). This flag controls + whether to recompute a cached satisfaction result from scratch even when + evaluating quietly. */ + bool maybe_unstable; + + /* True if we want to diagnose the above instability when it's detected. + We don't always want to do so, in order to avoid emitting duplicate + diagnostics in some cases. */ + bool diagnose_instability; }; struct sat_hasher : ggc_ptr_hash { static hashval_t hash (sat_entry *e) { - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->constr)) + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->atom)) { /* Atoms with instantiated mappings are built during satisfaction. They live only inside the sat_cache, and we build one to query the cache with each time we instantiate a mapping. */ gcc_assert (!e->args); - return hash_atomic_constraint (e->constr); + return hash_atomic_constraint (e->atom); } /* Atoms with uninstantiated mappings are built during normalization. Since normalize_atom caches the atoms it returns, we can assume pointer-based identity for fast hashing and comparison. Even if this assumption is violated, that's okay, we'll just get a cache miss. */ - hashval_t value = htab_hash_pointer (e->constr); + hashval_t value = htab_hash_pointer (e->atom); - if (tree map = ATOMIC_CONSTR_MAP (e->constr)) + if (tree map = ATOMIC_CONSTR_MAP (e->atom)) /* Only the parameters that are used in the targets of the mapping affect the satisfaction value of the atom. So we consider only the arguments for these parameters, and ignore the rest. */ @@ -2421,21 +2468,21 @@ struct sat_hasher : ggc_ptr_hash static bool equal (sat_entry *e1, sat_entry *e2) { - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr) - != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->constr)) + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom) + != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->atom)) return false; /* See sat_hasher::hash. */ - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr)) + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom)) { gcc_assert (!e1->args && !e2->args); - return atomic_constraints_identical_p (e1->constr, e2->constr); + return atomic_constraints_identical_p (e1->atom, e2->atom); } - if (e1->constr != e2->constr) + if (e1->atom != e2->atom) return false; - if (tree map = ATOMIC_CONSTR_MAP (e1->constr)) + if (tree map = ATOMIC_CONSTR_MAP (e1->atom)) for (tree target_parms = TREE_TYPE (map); target_parms; target_parms = TREE_CHAIN (target_parms)) @@ -2458,58 +2505,145 @@ static GTY((deletable)) hash_table *sat_cache; /* Cache the result of constraint_satisfaction_value. */ static GTY((deletable)) hash_map *decl_satisfied_cache; -static tree -get_satisfaction (tree constr, tree args) +/* A tool used by satisfy_atom to help manage satisfaction caching and to + diagnose "unstable" satisfaction values. We insert into the cache only + when performing satisfaction quietly. */ + +struct satisfaction_cache { - if (!sat_cache) - return NULL_TREE; - sat_entry elt = { constr, args, NULL_TREE }; - sat_entry* found = sat_cache->find (&elt); - if (found) - return found->result; - else - return NULL_TREE; -} + satisfaction_cache (tree, tree, sat_info); + tree get (); + tree save (tree); -static void -save_satisfaction (tree constr, tree args, tree result) + sat_entry *entry; + sat_info info; + unsigned ftc_count; +}; + +/* Constructor for the satisfaction_cache class. We're performing satisfaction + of ATOM+ARGS according to INFO. */ + +satisfaction_cache +::satisfaction_cache (tree atom, tree args, sat_info info) + : entry(nullptr), info(info), ftc_count(failed_type_completion_count) { if (!sat_cache) sat_cache = hash_table::create_ggc (31); - sat_entry elt = {constr, args, result}; - sat_entry** slot = sat_cache->find_slot (&elt, INSERT); - sat_entry* entry = ggc_alloc (); - *entry = elt; - *slot = entry; + + /* When noisy, we query the satisfaction cache in order to diagnose + "unstable" satisfaction values. */ + if (info.noisy ()) + { + /* When noisy, constraints have been re-normalized, and that breaks the + pointer-based identity assumption of sat_cache (for atoms with + uninstantiated mappings). So undo this re-normalization by looking in + the atom_cache for the corresponding atom that was used during quiet + satisfaction. */ + if (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom)) + { + if (tree found = atom_cache->find (atom)) + atom = found; + else + /* The lookup should always succeed, but if it fails then let's + just leave 'entry' empty, effectively disabling the cache. */ + return; + } + } + + /* Look up or create the corresponding satisfaction entry. */ + sat_entry elt; + elt.atom = atom; + elt.args = args; + sat_entry **slot = sat_cache->find_slot (&elt, INSERT); + if (*slot) + entry = *slot; + else if (info.quiet ()) + { + entry = ggc_alloc (); + entry->atom = atom; + entry->args = args; + entry->result = NULL_TREE; + entry->location = input_location; + entry->maybe_unstable = false; + entry->diagnose_instability = false; + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom)) + /* We always want to diagnose instability of an atom with an + instantiated parameter mapping. For atoms with an uninstantiated + mapping, we set this flag (in satisfy_atom) only if substitution + into its mapping previously failed. */ + entry->diagnose_instability = true; + *slot = entry; + } + else + /* We shouldn't get here, but if we do, let's just leave 'entry' + empty, effectively disabling the cache. */ + return; } -/* A tool to help manage satisfaction caching in satisfy_constraint_r. - Note the cache is only used when not diagnosing errors. */ +/* Returns the cached satisfaction result if we have one and we're not + recomputing the satisfaction result from scratch. Otherwise returns + NULL_TREE. */ -struct satisfaction_cache +tree +satisfaction_cache::get () { - satisfaction_cache (tree constr, tree args, tsubst_flags_t complain) - : constr(constr), args(args), complain(complain) - { } + if (!entry) + return NULL_TREE; - tree get () - { - if (complain == tf_none) - return get_satisfaction (constr, args); + if (info.noisy () || entry->maybe_unstable) + /* We're recomputing the satisfaction result from scratch. */ return NULL_TREE; - } + else + return entry->result; +} - tree save (tree result) - { - if (complain == tf_none) - save_satisfaction (constr, args, result); +/* RESULT is the computed satisfaction result. If RESULT differs from the + previously cached result, this routine issues an appropriate error. + Otherwise, when evaluating quietly, updates the cache appropriately. */ + +tree +satisfaction_cache::save (tree result) +{ + if (!entry) return result; - } - tree constr; - tree args; - tsubst_flags_t complain; -}; + if (entry->result && result != entry->result) + { + if (info.quiet ()) + /* Return error_mark_node to force satisfaction to get replayed + noisily. */ + return error_mark_node; + else + { + if (entry->diagnose_instability) + { + auto_diagnostic_group d; + error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)), + "satisfaction value of atomic constraint %qE changed " + "from %qE to %qE", entry->atom, entry->result, result); + inform (entry->location, + "satisfaction value first evaluated to %qE from here", + entry->result); + } + /* For sake of error recovery, allow this latest satisfaction result + to prevail. */ + entry->result = result; + return result; + } + } + + if (info.quiet ()) + { + entry->result = result; + /* We heuristically flag this satisfaction result as potentially unstable + iff during its computation, completion of a type failed. Note that + this may also clear the flag if the result turned out to be + independent of the previously detected type completion failure. */ + entry->maybe_unstable = (ftc_count != failed_type_completion_count); + } + + return result; +} static int satisfying_constraint = 0; @@ -2722,7 +2856,7 @@ static void diagnose_atomic_constraint (tree, tree, tree, subst_info); static tree satisfy_atom (tree t, tree args, sat_info info) { - satisfaction_cache cache (t, args, info.complain); + satisfaction_cache cache (t, args, info); if (tree r = cache.get ()) return r; @@ -2742,6 +2876,11 @@ satisfy_atom (tree t, tree args, sat_info info) not satisfied. Replay the substitution. */ if (info.diagnose_unsatisfaction_p ()) tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info); + if (info.quiet ()) + /* Since instantiation of the parameter mapping failed, we + want to diagnose potential instability of this satisfaction + result. */ + cache.entry->diagnose_instability = true; return cache.save (boolean_false_node); } @@ -2753,9 +2892,12 @@ satisfy_atom (tree t, tree args, sat_info info) ATOMIC_CONSTR_MAP (t) = map; gcc_assert (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (t)); ATOMIC_CONSTR_MAP_INSTANTIATED_P (t) = true; - satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info.complain); + satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info); if (tree r = inst_cache.get ()) - return cache.save (r); + { + cache.entry->location = inst_cache.entry->location; + return cache.save (r); + } /* Rebuild the argument vector from the parameter mapping. */ args = get_mapped_args (map); @@ -2946,6 +3088,8 @@ satisfy_declaration_constraints (tree t, sat_info info) norm = normalize_nontemplate_requirements (t, info.noisy ()); } + unsigned ftc_count = failed_type_completion_count; + tree result = boolean_true_node; if (norm) { @@ -2957,7 +3101,20 @@ satisfy_declaration_constraints (tree t, sat_info info) pop_tinst_level (); } - if (info.quiet ()) + /* True if this satisfaction is (heuristically) potentially unstable, i.e. + if its result may depend on where in the program it was performed. */ + bool maybe_unstable_satisfaction = false; + + if (ftc_count != failed_type_completion_count) + /* Type completion failure occurred during satisfaction. The satisfaction + result may (or may not) materially depend on the completeness of a type, + so we consider it potentially unstable. */ + maybe_unstable_satisfaction = true; + + if (maybe_unstable_satisfaction) + /* Don't cache potentially unstable satisfaction, to allow satisfy_atom + to check the stability the next time around. */; + else if (info.quiet ()) hash_map_safe_put (decl_satisfied_cache, saved_t, result); return result; -- cgit v1.1 From 79f57d5cb070bb02ea0a34b5f42658d6659b19a8 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Thu, 17 Dec 2020 22:18:07 -0500 Subject: c++: Diagnose self-recursive satisfaction This patch further extends the satisfaction_cache class to diagnose self-recursive satisfaction. gcc/cp/ChangeLog: * constraint.cc (sat_entry::evaluating): New member. (satisfaction_cache::get): If entry->evaluating, diagnose self-recursive satisfaction. Otherwise, set entry->evaluating if we're not reusing a cached satisfaction result. (satisfaction_cache::save): Clear entry->evaluating. (satisfy_atom): Set up diagnosing_failed_constraint before the first call to get(). gcc/testsuite/ChangeLog: PR c++/96840 * g++.dg/cpp2a/concepts-pr88395.C: Adjust to expect the self-recursive satisfaction to get directly diagnosed. * g++.dg/cpp2a/concepts-recursive-sat2.C: Likewise. * g++.dg/cpp2a/concepts-recursive-sat4.C: New test. --- gcc/cp/constraint.cc | 39 +++++++++++++++++++++++++++++++-------- 1 file changed, 31 insertions(+), 8 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 47cf882..40e499b 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2428,6 +2428,11 @@ struct GTY((for_user)) sat_entry We don't always want to do so, in order to avoid emitting duplicate diagnostics in some cases. */ bool diagnose_instability; + + /* True if we're in the middle of computing this satisfaction result. + Used during both quiet and noisy satisfaction to detect self-recursive + satisfaction. */ + bool evaluating; }; struct sat_hasher : ggc_ptr_hash @@ -2572,6 +2577,7 @@ satisfaction_cache mapping, we set this flag (in satisfy_atom) only if substitution into its mapping previously failed. */ entry->diagnose_instability = true; + entry->evaluating = false; *slot = entry; } else @@ -2590,9 +2596,23 @@ satisfaction_cache::get () if (!entry) return NULL_TREE; - if (info.noisy () || entry->maybe_unstable) - /* We're recomputing the satisfaction result from scratch. */ - return NULL_TREE; + if (entry->evaluating) + { + /* If we get here, it means satisfaction is self-recursive. */ + gcc_checking_assert (!entry->result); + if (info.noisy ()) + error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)), + "satisfaction of atomic constraint %qE depends on itself", + entry->atom); + return error_mark_node; + } + + if (info.noisy () || entry->maybe_unstable || !entry->result) + { + /* We're computing the satisfaction result from scratch. */ + entry->evaluating = true; + return NULL_TREE; + } else return entry->result; } @@ -2607,6 +2627,9 @@ satisfaction_cache::save (tree result) if (!entry) return result; + gcc_checking_assert (entry->evaluating); + entry->evaluating = false; + if (entry->result && result != entry->result) { if (info.quiet ()) @@ -2856,6 +2879,11 @@ static void diagnose_atomic_constraint (tree, tree, tree, subst_info); static tree satisfy_atom (tree t, tree args, sat_info info) { + /* In case there is a diagnostic, we want to establish the context + prior to printing errors. If no errors occur, this context is + removed before returning. */ + diagnosing_failed_constraint failure (t, args, info.noisy ()); + satisfaction_cache cache (t, args, info); if (tree r = cache.get ()) return r; @@ -2863,11 +2891,6 @@ satisfy_atom (tree t, tree args, sat_info info) /* Perform substitution quietly. */ subst_info quiet (tf_none, NULL_TREE); - /* In case there is a diagnostic, we want to establish the context - prior to printing errors. If no errors occur, this context is - removed before returning. */ - diagnosing_failed_constraint failure (t, args, info.noisy ()); - /* Instantiate the parameter mapping. */ tree map = tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, quiet); if (map == error_mark_node) -- cgit v1.1 From 731a32b3fa779bd5bcff7571ce66b8a79ee2d336 Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Thu, 17 Dec 2020 22:18:09 -0500 Subject: c++: More precise tracking of potentially unstable satisfaction This makes tracking of potentially unstable satisfaction results more precise by recording the specific types for which completion failed during satisfaction. We now recompute a satisfaction result only if one of these types has been completed since the last time we computed the satisfaction result. Thus the number of times that we recompute a satisfaction result is now bounded by the number of such incomplete types, rather than being effectively unbounded. This allows us to remove the invalid assumption in note_ftc_for_satisfaction that was added to avoid a compile time performance regression in cmcstl2 due to repeated recomputation of a satisfaction result that depended on completion of a permanently incomplete class template specialization. In order to continue to detect the instability in concepts-complete3.C, we also need to explicitly keep track of return type deduction failure alongside type completion failure. So this patch also adds a call to note_ftc_for_satisfaction in require_deduced_type. gcc/cp/ChangeLog: * constraint.cc (satisfying_constraint): Move up definition and give it bool type. (failed_type_completion_count): Replace with ... (failed_type_completions): ... this. (note_failed_type_completion_for_satisfaction): Append the supplied argument to failed_type_completions. (some_type_complete_p): Define. (sat_entry::maybe_unstable): Replace with ... (sat_entry::ftc_begin, sat_entry::ftc_end): ... these. (satisfaction_cache::ftc_count): Replace with ... (satisfaction_cache::ftc_begin): ... this. (satisfaction_cache::satisfaction_cache): Adjust accordingly. (satisfaction_cache::get): Adjust accordingly, using some_type_complete_p. (satisfaction_cache::save): Adjust accordingly. (satisfying_constraint_p): Remove unused function. (satisfy_constraint): Set satisfying_constraint. (satisfy_declaration_constraints): Likewise. * decl.c (require_deduced_type): Call note_failed_type_completion_for_satisfaction. --- gcc/cp/constraint.cc | 114 +++++++++++++++++++++++++++++---------------------- 1 file changed, 64 insertions(+), 50 deletions(-) (limited to 'gcc/cp/constraint.cc') diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index 40e499b..24fcbaa 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -2374,26 +2374,51 @@ tsubst_parameter_mapping (tree map, tree args, tsubst_flags_t complain, tree in_ Constraint satisfaction ---------------------------------------------------------------------------*/ -/* A counter incremented by note_failed_type_completion_for_satisfaction(). - It's used by the satisfaction caches in order to flag "potentially unstable" - satisfaction results. */ +/* True if we are currently satisfying a constraint. */ -static unsigned failed_type_completion_count; +static bool satisfying_constraint; -/* Called whenever a type completion failure occurs that definitely affects - the semantics of the program, by e.g. inducing substitution failure. */ +/* A vector of incomplete types (and of declarations with undeduced return type), + appended to by note_failed_type_completion_for_satisfaction. The + satisfaction caches use this in order to keep track of "potentially unstable" + satisfaction results. + + Since references to entries in this vector are stored only in the + GC-deletable sat_cache, it's safe to make this deletable as well. */ + +static GTY((deletable)) vec *failed_type_completions; + +/* Called whenever a type completion (or return type deduction) failure occurs + that definitely affects the meaning of the program, by e.g. inducing + substitution failure. */ void -note_failed_type_completion_for_satisfaction (tree type) -{ - gcc_checking_assert (!COMPLETE_TYPE_P (type)); - if (CLASS_TYPE_P (type) - && CLASSTYPE_TEMPLATE_INSTANTIATION (type)) - /* After instantiation, a class template specialization that's - incomplete will remain incomplete, so for our purposes we can - ignore this completion failure event. */; - else - ++failed_type_completion_count; +note_failed_type_completion_for_satisfaction (tree t) +{ + if (satisfying_constraint) + { + gcc_checking_assert ((TYPE_P (t) && !COMPLETE_TYPE_P (t)) + || (DECL_P (t) && undeduced_auto_decl (t))); + vec_safe_push (failed_type_completions, t); + } +} + +/* Returns true if the range [BEGIN, END) of elements within the + failed_type_completions vector contains a complete type (or a + declaration with a non-placeholder return type). */ + +static bool +some_type_complete_p (int begin, int end) +{ + for (int i = begin; i < end; i++) + { + tree t = (*failed_type_completions)[i]; + if (TYPE_P (t) && COMPLETE_TYPE_P (t)) + return true; + if (DECL_P (t) && !undeduced_auto_decl (t)) + return true; + } + return false; } /* Hash functions and data types for satisfaction cache entries. */ @@ -2417,12 +2442,10 @@ struct GTY((for_user)) sat_entry performed. */ location_t location; - /* True if this satisfaction result is flagged as "potentially unstable", - i.e. the result might change at different points in the program if - recomputed from scratch (which would be ill-formed). This flag controls - whether to recompute a cached satisfaction result from scratch even when - evaluating quietly. */ - bool maybe_unstable; + /* The range of elements appended to the failed_type_completions vector + during computation of this satisfaction result, encoded as a begin/end + pair of offsets. */ + int ftc_begin, ftc_end; /* True if we want to diagnose the above instability when it's detected. We don't always want to do so, in order to avoid emitting duplicate @@ -2522,7 +2545,7 @@ struct satisfaction_cache sat_entry *entry; sat_info info; - unsigned ftc_count; + int ftc_begin; }; /* Constructor for the satisfaction_cache class. We're performing satisfaction @@ -2530,7 +2553,7 @@ struct satisfaction_cache satisfaction_cache ::satisfaction_cache (tree atom, tree args, sat_info info) - : entry(nullptr), info(info), ftc_count(failed_type_completion_count) + : entry(nullptr), info(info), ftc_begin(-1) { if (!sat_cache) sat_cache = hash_table::create_ggc (31); @@ -2569,7 +2592,7 @@ satisfaction_cache entry->args = args; entry->result = NULL_TREE; entry->location = input_location; - entry->maybe_unstable = false; + entry->ftc_begin = entry->ftc_end = -1; entry->diagnose_instability = false; if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom)) /* We always want to diagnose instability of an atom with an @@ -2607,10 +2630,16 @@ satisfaction_cache::get () return error_mark_node; } - if (info.noisy () || entry->maybe_unstable || !entry->result) + /* This satisfaction result is "potentially unstable" if a type for which + type completion failed during its earlier computation is now complete. */ + bool maybe_unstable = some_type_complete_p (entry->ftc_begin, + entry->ftc_end); + + if (info.noisy () || maybe_unstable || !entry->result) { /* We're computing the satisfaction result from scratch. */ entry->evaluating = true; + ftc_begin = vec_safe_length (failed_type_completions); return NULL_TREE; } else @@ -2658,32 +2687,16 @@ satisfaction_cache::save (tree result) if (info.quiet ()) { entry->result = result; - /* We heuristically flag this satisfaction result as potentially unstable - iff during its computation, completion of a type failed. Note that - this may also clear the flag if the result turned out to be - independent of the previously detected type completion failure. */ - entry->maybe_unstable = (ftc_count != failed_type_completion_count); + /* Store into this entry the list of relevant failed type completions + that occurred during (re)computation of the satisfaction result. */ + gcc_checking_assert (ftc_begin != -1); + entry->ftc_begin = ftc_begin; + entry->ftc_end = vec_safe_length (failed_type_completions); } return result; } -static int satisfying_constraint = 0; - -/* Returns true if we are currently satisfying a constraint. - - This is used to guard against recursive calls to evaluate_concept_check - during template argument substitution. - - TODO: Do we need this now that we fully normalize prior to evaluation? - I think not. */ - -bool -satisfying_constraint_p () -{ - return satisfying_constraint; -} - /* Substitute ARGS into constraint-expression T during instantiation of a member of a class template. */ @@ -3003,6 +3016,8 @@ satisfy_constraint (tree t, tree args, sat_info info) { auto_timevar time (TV_CONSTRAINT_SAT); + auto ovr = make_temp_override (satisfying_constraint, true); + /* Turn off template processing. Constraint satisfaction only applies to non-dependent terms, so we want to ensure full checking here. */ processing_template_decl_sentinel proc (true); @@ -3111,7 +3126,7 @@ satisfy_declaration_constraints (tree t, sat_info info) norm = normalize_nontemplate_requirements (t, info.noisy ()); } - unsigned ftc_count = failed_type_completion_count; + unsigned ftc_count = vec_safe_length (failed_type_completions); tree result = boolean_true_node; if (norm) @@ -3127,8 +3142,7 @@ satisfy_declaration_constraints (tree t, sat_info info) /* True if this satisfaction is (heuristically) potentially unstable, i.e. if its result may depend on where in the program it was performed. */ bool maybe_unstable_satisfaction = false; - - if (ftc_count != failed_type_completion_count) + if (ftc_count != vec_safe_length (failed_type_completions)) /* Type completion failure occurred during satisfaction. The satisfaction result may (or may not) materially depend on the completeness of a type, so we consider it potentially unstable. */ -- cgit v1.1