[PATCH 4/4 v2] c++: Consider only relevant template arguments in sat_hasher

Jason Merrill jason@redhat.com
Fri Nov 6 20:44:12 GMT 2020


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>(); }
> 



More information about the Gcc-patches mailing list