[PATCH 3/4 v2] c++: Use two levels of caching in satisfy_atom

[Jason Merrill]

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))
>