[ This patch depends on c++: Use two levels of caching in satisfy_atom
https://gcc.gnu.org/pipermail/gcc-patches/2020-November/558096.html ] 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 <class T> concept range = range_v<T>; template <class U> void foo () requires range<U>; template <class U, class V> void bar () requires range<U>; The associated constraints of foo and bar are equivalent: they both consist of the atom range_v<T> (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 are relevant to a satisfaction value of an atom. This patch eliminates this assumption and makes the sat_cache instead care about just the subset of args of an (atom,args) pair that's used in the targets of an atom's parameter mapping. 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. Bootstrapped and regtested on x86_64-pc-linux-gnu. 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. (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. --- gcc/cp/constraint.cc | 66 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 63 insertions(+), 3 deletions(-) diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index c612bfba13b..221c5b21c7f 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 template + parameters of ORIG_DECL. */ + + tree orig_decl = NULL_TREE; }; static tree normalize_expression (tree, tree, norm_info); @@ -758,6 +765,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; @@ -2322,7 +2351,20 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> } hashval_t value = htab_hash_pointer (e->constr); - return iterative_hash_template_arg (e->args, value); + + tree map = ATOMIC_CONSTR_MAP (e->constr); + if (map) + 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 +2385,25 @@ struct sat_hasher : ggc_ptr_hash<sat_entry> the caching of ATOMIC_CONSTRs performed therein. */ if (e1->constr != e2->constr) return false; - return template_args_equal (e1->args, e2->args); + + tree map = ATOMIC_CONSTR_MAP (e1->constr); + if (map) + /* Only the parameters that are used in the targets of the mapping + affect the satisfaction value of the atom. We compare 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 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; } }; -- 2.29.2.154.g7f7ebe054a
