[PATCH 3/4 v2] c++: Use two levels of caching in satisfy_atom
Patrick Palka
ppalka@redhat.com
Fri Nov 6 01:40:31 GMT 2020
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 <class T> concept range = range_v<T>;
template <class U, class V> void foo () requires range<U> && range<V>;
are range_v<T> (with mapping T -> U) /\ range_v<T> (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 avoid substituting the instantiated
mapping into the second atom's expression. This in general results in
a higher cache hit rate in satisfy_atom.
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 +++++++++++++++++++++++++++++++++-----------
gcc/cp/cp-tree.h | 7 ++++++
2 files changed, 50 insertions(+), 14 deletions(-)
diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index 613ced26e2b..9dd5d892ce9 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -2310,17 +2310,37 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
{
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 %<bool%>",
- a, TREE_TYPE (result));
+ t, TREE_TYPE (result));
else
- inform (loc, "the expression %qE evaluated to %<false%>", a);
- ggc_free (a);
+ inform (loc, "the expression %qE evaluated to %<false%>", t);
}
}
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index eda4c56b406..c2673fb0cef 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -435,6 +435,7 @@ extern GTY(()) tree cp_global_trees[CPTI_MAX];
REINTERPRET_CAST_P (in NOP_EXPR)
ALIGNOF_EXPR_STD_P (in ALIGNOF_EXPR)
OVL_DEDUP_P (in OVERLOAD)
+ ATOMIC_CONSTR_MAP_INSTANTIATED_P (in ATOMIC_CONSTR)
1: IDENTIFIER_KIND_BIT_1 (in IDENTIFIER_NODE)
TI_PENDING_TEMPLATE_FLAG.
TEMPLATE_PARMS_FOR_INLINE.
@@ -1593,6 +1594,12 @@ check_constraint_info (tree t)
#define ATOMIC_CONSTR_MAP(NODE) \
TREE_OPERAND (TREE_CHECK (NODE, ATOMIC_CONSTR), 0)
+/* Whether the parameter mapping of this atomic constraint
+ is already instantiated with concrete template arguments.
+ Used only in satisfy_atom and in the satisfaction cache. */
+#define ATOMIC_CONSTR_MAP_INSTANTIATED_P(NODE) \
+ TREE_LANG_FLAG_0 (ATOMIC_CONSTR_CHECK (NODE))
+
/* The expression of an atomic constraint. */
#define ATOMIC_CONSTR_EXPR(NODE) \
CONSTR_EXPR (ATOMIC_CONSTR_CHECK (NODE))
--
2.29.2.154.g7f7ebe054a
More information about the Gcc-patches
mailing list