Message ID | 20201106014032.3841458-3-ppalka@redhat.com |
---|---|
State | New |
Headers | show |
Series | [1/4] c++: Fix ICE with variadic concepts and aliases [PR93907] | expand |
On 11/5/20 8:40 PM, Patrick Palka wrote: > 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. OK. > 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)) >
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))