From d3fd75d869480044213553000d2c9dc236a4f7af Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Mon, 9 Nov 2020 18:16:48 -0500 Subject: [PATCH] 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 +++++++++++++++++++++++-- gcc/cp/pt.c | 10 ++++ gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C | 12 ++++ 3 files changed, 92 insertions(+), 6 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C 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; } }; diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index 88644b9..a2655a0 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -10617,6 +10617,16 @@ keep_template_parm (tree t, void* data) if (!ftpi->parms.add (t)) ftpi->parm_list = tree_cons (NULL_TREE, t, ftpi->parm_list); + /* Verify the parameter we found has a valid index. */ + if (flag_checking) + { + tree parms = ftpi->ctx_parms; + while (TMPL_PARMS_DEPTH (parms) > level) + parms = TREE_CHAIN (parms); + if (int len = TREE_VEC_LENGTH (TREE_VALUE (parms))) + gcc_assert (index < len); + } + return 0; } diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C b/gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C new file mode 100644 index 0000000..529dab1 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C @@ -0,0 +1,12 @@ +// { dg-do compile { target c++20 } } + +template concept C = requires(T t) { t; }; + +template using A = decltype((T{}, int{})); + +template concept D = C>; + +template void f() requires D; + +template +void g() { f(); } -- 2.7.4