On 11/5/20 11:18 AM, Patrick Palka wrote:
[ 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.
This seems like another situation where caching only after substitution
of the parameter mapping might make things simpler.
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;
}
};
