On 11/5/20 8:40 PM, Patrick Palka wrote:
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
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 with 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.
---
gcc/cp/constraint.cc | 78 +++++++++++++++++--
gcc/cp/pt.c | 10 +++
.../g++.dg/cpp2a/concepts-decltype2.C | 12 +++
3 files changed, 94 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 9dd5d892ce9..90901bf7277 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<tree> 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<hm_ggc> (normalized_map, tmpl, norm);
@@ -2325,7 +2361,22 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
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);
+ tree map = ATOMIC_CONSTR_MAP (e->constr);
+ if (map)
Move the declaration of map into the condition?
+ /* 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 +2394,22 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
if (e1->constr != e2->constr)
return false;
- return template_args_equal (e1->args, e2->args);
+
+ tree map = ATOMIC_CONSTR_MAP (e1->constr);
+ if (map)
Likewise. OK with that change.
+ 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 f401c75b9e5..f064a417568 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 00000000000..529dab11fcb
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-decltype2.C
@@ -0,0 +1,12 @@
+// { dg-do compile { target c++20 } }
+
+template <class T> concept C = requires(T t) { t; };
+
+template <class T> using A = decltype((T{}, int{}));
+
+template <class T> concept D = C<A<T>>;
+
+template <class T> void f() requires D<T>;
+
+template <class, class>
+void g() { f<int>(); }
