[PATCH 1/4] c++: Fix ICE with variadic concepts and aliases [PR93907]

[PATCH 1/4] c++: Fix ICE with variadic concepts and aliases [PR93907]

[Patrick Palka]

This patch (naively) extends the PR93907 fix to also apply to variadic
concepts invoked with a type argument pack.  Without this, we ICE on
the below testcase (a variadic version of concepts-using2.C) in the same
manner as we used to on concepts-using2.C before r10-7133.

Patch series bootstrapped and regtested on x86_64-pc-linux-gnu,
and also tested against cmcstl2 and range-v3.

gcc/cp/ChangeLog:

	PR c++/93907
	* constraint.cc (tsubst_parameter_mapping): Also canonicalize
	the type arguments of a TYPE_ARGUMENT_PACk.

gcc/testsuite/ChangeLog:

	PR c++/93907
	* g++.dg/cpp2a/concepts-using3.C: New test, based off of
	concepts-using2.C.
---
 gcc/cp/constraint.cc                         | 10 ++++
 gcc/testsuite/g++.dg/cpp2a/concepts-using3.C | 52 ++++++++++++++++++++
 2 files changed, 62 insertions(+)
 create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-using3.C

diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index b6f6f0d02a5..c871a8ab86a 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -2252,6 +2252,16 @@ tsubst_parameter_mapping (tree map, tree args, subst_info info)
 	  new_arg = tsubst_template_arg (arg, args, complain, in_decl);
 	  if (TYPE_P (new_arg))
 	    new_arg = canonicalize_type_argument (new_arg, complain);
+	  if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK)
+	    {
+	      tree pack_args = ARGUMENT_PACK_ARGS (new_arg);
+	      for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++)
+		{
+		  tree& pack_arg = TREE_VEC_ELT (pack_args, i);
+		  if (TYPE_P (pack_arg))
+		    pack_arg = canonicalize_type_argument (pack_arg, complain);
+		}
+	    }
 	}
       if (new_arg == error_mark_node)
 	return error_mark_node;
diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
new file mode 100644
index 00000000000..2c8ad40d104
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
@@ -0,0 +1,52 @@
+// PR c++/93907
+// { dg-options -std=gnu++20 }
+
+// This testcase is a variadic version of concepts-using2.C; the only
+// difference is that 'cd' and 'ce' are now variadic concepts.
+
+template <int a> struct c {
+  static constexpr int d = a;
+  typedef c e;
+};
+template <typename> struct f;
+template <typename b> using g = typename f<b>::e;
+struct b;
+template <typename b> struct f { using e = b; };
+template <typename ai> struct m { typedef g<ai> aj; };
+template <typename b> struct n { typedef typename m<b>::aj e; };
+template <typename b> using an = typename n<b>::e;
+template <typename> constexpr bool ao = c<true>::d;
+template <typename> constexpr bool i = c<1>::d;
+template <typename> concept bb = i<b>;
+#ifdef __SIZEOF_INT128__
+using cc = __int128;
+#else
+using cc = long long;
+#endif
+template <typename...> concept cd = bb<cc>;
+template <typename... bt> concept ce = requires { requires cd<bt...>; };
+template <typename bt> concept h = ce<bt>;
+template <typename bt> concept l = h<bt>;
+template <typename> concept cl = ao<b>;
+template <typename b> concept cp = requires(b j) {
+  requires h<an<decltype(j.begin())>>;
+};
+struct o {
+  template <cl b> requires cp<b> auto operator()(b) {}
+};
+template <typename b> using cm = decltype(o{}(b()));
+template <typename bt> concept ct = l<bt>;
+template <typename da> concept dd = ct<cm<da>>;
+template <typename da> concept de = dd<da>;
+struct {
+  template <de da, typename b> void operator()(da, b);
+} di;
+struct p {
+  void begin();
+};
+template <typename> using df = p;
+template <int> void q() {
+  df<int> k;
+  int d;
+  di(k, d);
+}
-- 
2.29.2.154.g7f7ebe054a

[PATCH 2/4 v2] c++: Reuse identical ATOMIC_CONSTRs during normalization

[Patrick Palka]

Profiling revealed that sat_hasher::equal accounts for nearly 40% of
compile time in some cmcstl2 tests.

This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs
returned by normalize_atom.  This in turn allows us to replace the
expensive atomic_constraints_identical_p check in sat_hasher::equal
with cheap pointer equality, with no loss in cache hit rate.

With this patch, compile time for the cmcstl2 test
test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with
an --enable-checking=release compiler.

gcc/cp/ChangeLog:

	* constraint.cc (atom_cache): Define this deletable hash_table.
	(normalize_atom): Use it to cache ATOMIC_CONSTRs when not
	generating diagnostics.
	(sat_hasher::hash): Use htab_hash_pointer instead of
	hash_atomic_constraint.
	(sat_hasher::equal): Test for pointer equality instead of
	atomic_constraints_identical_p.
	* cp-tree.h (struct atom_hasher): Moved and renamed from ...
	* logic.cc (struct constraint_hash): ... here.
	(clause::m_set): Adjust accordingly.
---
 gcc/cp/constraint.cc | 27 ++++++++++++++++++++++++---
 gcc/cp/cp-tree.h     | 15 +++++++++++++++
 gcc/cp/logic.cc      | 17 +----------------
 3 files changed, 40 insertions(+), 19 deletions(-)

diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index c871a8ab86a..613ced26e2b 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -710,6 +710,10 @@ normalize_concept_check (tree check, tree args, norm_info info)
   return normalize_expression (def, subst, info);
 }
 
+/* Used by normalize_atom to cache ATOMIC_CONSTRs.  */
+
+static GTY((deletable)) hash_table<atom_hasher> *atom_cache;
+
 /* The normal form of an atom depends on the expression. The normal
    form of a function call to a function concept is a check constraint
    for that concept. The normal form of a reference to a variable
@@ -729,7 +733,19 @@ normalize_atom (tree t, tree args, norm_info info)
   /* Build a new info object for the atom.  */
   tree ci = build_tree_list (t, info.context);
 
-  return build1 (ATOMIC_CONSTR, ci, map);
+  tree atom = build1 (ATOMIC_CONSTR, ci, map);
+  if (!info.generate_diagnostics ())
+    {
+      /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal
+	 later can cheaply compare two atoms using just pointer equality.  */
+      if (!atom_cache)
+	atom_cache = hash_table<atom_hasher>::create_ggc (31);
+      tree *slot = atom_cache->find_slot (atom, INSERT);
+      if (*slot)
+	return *slot;
+      *slot = atom;
+    }
+  return atom;
 }
 
 /* Returns the normal form of an expression. */
@@ -2294,13 +2310,18 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
 {
   static hashval_t hash (sat_entry *e)
   {
-    hashval_t value = hash_atomic_constraint (e->constr);
+    /* 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.  */
+    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)
   {
-    if (!atomic_constraints_identical_p (e1->constr, e2->constr))
+    /* As in sat_hasher::hash.  */
+    if (e1->constr != e2->constr)
       return false;
     return template_args_equal (e1->args, e2->args);
   }
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 26852f6f2e3..eda4c56b406 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -7835,6 +7835,21 @@ extern hashval_t iterative_hash_constraint      (tree, hashval_t);
 extern hashval_t hash_atomic_constraint         (tree);
 extern void diagnose_constraints                (location_t, tree, tree);
 
+/* A structural hasher for ATOMIC_CONSTRs.  */
+
+struct atom_hasher : default_hash_traits<tree>
+{
+  static hashval_t hash (tree t)
+  {
+    return hash_atomic_constraint (t);
+  }
+
+  static bool equal (tree t1, tree t2)
+  {
+    return atomic_constraints_identical_p (t1, t2);
+  }
+};
+
 /* in logic.cc */
 extern bool subsumes                            (tree, tree);
 
diff --git a/gcc/cp/logic.cc b/gcc/cp/logic.cc
index 194b743192d..6701488bc1c 100644
--- a/gcc/cp/logic.cc
+++ b/gcc/cp/logic.cc
@@ -47,21 +47,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "toplev.h"
 #include "type-utils.h"
 
-/* Hash functions for atomic constrains.  */
-
-struct constraint_hash : default_hash_traits<tree>
-{
-  static hashval_t hash (tree t)
-  {
-    return hash_atomic_constraint (t);
-  }
-
-  static bool equal (tree t1, tree t2)
-  {
-    return atomic_constraints_identical_p (t1, t2);
-  }
-};
-
 /* A conjunctive or disjunctive clause.
 
    Each clause maintains an iterator that refers to the current
@@ -219,7 +204,7 @@ struct clause
   }
 
   std::list<tree> m_terms; /* The list of terms.  */
-  hash_set<tree, false, constraint_hash> m_set; /* The set of atomic constraints.  */
+  hash_set<tree, false, atom_hasher> m_set; /* The set of atomic constraints.  */
   iterator m_current; /* The current term.  */
 };
 
-- 
2.29.2.154.g7f7ebe054a

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

[Patrick Palka]

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

Re: [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))
> 

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

[Patrick Palka]

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)
+      /* 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)
+      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>(); }
-- 
2.29.2.154.g7f7ebe054a

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

[Jason Merrill]

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

Re: [PATCH 1/4] c++: Fix ICE with variadic concepts and aliases [PR93907]

[Jason Merrill]

On 11/5/20 8:40 PM, Patrick Palka wrote:
> This patch (naively) extends the PR93907 fix to also apply to variadic
> concepts invoked with a type argument pack.  Without this, we ICE on
> the below testcase (a variadic version of concepts-using2.C) in the same
> manner as we used to on concepts-using2.C before r10-7133.
> 
> Patch series bootstrapped and regtested on x86_64-pc-linux-gnu,
> and also tested against cmcstl2 and range-v3.
> 
> gcc/cp/ChangeLog:
> 
> 	PR c++/93907
> 	* constraint.cc (tsubst_parameter_mapping): Also canonicalize
> 	the type arguments of a TYPE_ARGUMENT_PACk.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR c++/93907
> 	* g++.dg/cpp2a/concepts-using3.C: New test, based off of
> 	concepts-using2.C.
> ---
>   gcc/cp/constraint.cc                         | 10 ++++
>   gcc/testsuite/g++.dg/cpp2a/concepts-using3.C | 52 ++++++++++++++++++++
>   2 files changed, 62 insertions(+)
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> 
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index b6f6f0d02a5..c871a8ab86a 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -2252,6 +2252,16 @@ tsubst_parameter_mapping (tree map, tree args, subst_info info)

Hmm, the

 >       else if (ARGUMENT_PACK_P (arg))
 >         new_arg = tsubst_argument_pack (arg, args, complain, in_decl);

just above this seems redundant, since tsubst_template_arg handles packs 
just fine.  In fact, I wonder why tsubst_argument_pack is used 
specifically anywhere?  It seems to get some edge cases better than the 
code in tsubst, but the solution to that would seem to be replacing the 
code in tsubst with a call to tsubst_argument_pack; then we can remove 
all the other calls to the function.

>   	  new_arg = tsubst_template_arg (arg, args, complain, in_decl);
>   	  if (TYPE_P (new_arg))
>   	    new_arg = canonicalize_type_argument (new_arg, complain);
> +	  if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK)
> +	    {
> +	      tree pack_args = ARGUMENT_PACK_ARGS (new_arg);
> +	      for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++)
> +		{
> +		  tree& pack_arg = TREE_VEC_ELT (pack_args, i);
> +		  if (TYPE_P (pack_arg))
> +		    pack_arg = canonicalize_type_argument (pack_arg, complain);

Do we need the TYPE_P here, since we already know we're in a 
TYPE_ARGUMENT_PACK?  That is, can an element of a TYPE_ARGUMENT_PACK be 
an invalid argument to canonicalize_type_argument?

OTOH, I wonder if we need to canonicalize non-type arguments here as well?

I wonder if tsubst_template_arg should canonicalize rather than leave 
that up to the caller?  I suppose that could do a bit more work when the 
result is going to end up in convert_template_argument and get 
canonicalized again; I don't know if that would be significant.

>   	}
>         if (new_arg == error_mark_node)
>   	return error_mark_node;
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> new file mode 100644
> index 00000000000..2c8ad40d104
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> @@ -0,0 +1,52 @@
> +// PR c++/93907
> +// { dg-options -std=gnu++20 }
> +
> +// This testcase is a variadic version of concepts-using2.C; the only
> +// difference is that 'cd' and 'ce' are now variadic concepts.
> +
> +template <int a> struct c {
> +  static constexpr int d = a;
> +  typedef c e;
> +};
> +template <typename> struct f;
> +template <typename b> using g = typename f<b>::e;
> +struct b;
> +template <typename b> struct f { using e = b; };
> +template <typename ai> struct m { typedef g<ai> aj; };
> +template <typename b> struct n { typedef typename m<b>::aj e; };
> +template <typename b> using an = typename n<b>::e;
> +template <typename> constexpr bool ao = c<true>::d;
> +template <typename> constexpr bool i = c<1>::d;
> +template <typename> concept bb = i<b>;
> +#ifdef __SIZEOF_INT128__
> +using cc = __int128;
> +#else
> +using cc = long long;
> +#endif
> +template <typename...> concept cd = bb<cc>;
> +template <typename... bt> concept ce = requires { requires cd<bt...>; };
> +template <typename bt> concept h = ce<bt>;
> +template <typename bt> concept l = h<bt>;
> +template <typename> concept cl = ao<b>;
> +template <typename b> concept cp = requires(b j) {
> +  requires h<an<decltype(j.begin())>>;
> +};
> +struct o {
> +  template <cl b> requires cp<b> auto operator()(b) {}
> +};
> +template <typename b> using cm = decltype(o{}(b()));
> +template <typename bt> concept ct = l<bt>;
> +template <typename da> concept dd = ct<cm<da>>;
> +template <typename da> concept de = dd<da>;
> +struct {
> +  template <de da, typename b> void operator()(da, b);
> +} di;
> +struct p {
> +  void begin();
> +};
> +template <typename> using df = p;
> +template <int> void q() {
> +  df<int> k;
> +  int d;
> +  di(k, d);
> +}
> 

Re: [PATCH 1/4] c++: Fix ICE with variadic concepts and aliases [PR93907]

[Patrick Palka]

On Fri, 6 Nov 2020, Jason Merrill wrote:

> On 11/5/20 8:40 PM, Patrick Palka wrote:
> > This patch (naively) extends the PR93907 fix to also apply to variadic
> > concepts invoked with a type argument pack.  Without this, we ICE on
> > the below testcase (a variadic version of concepts-using2.C) in the same
> > manner as we used to on concepts-using2.C before r10-7133.
> > 
> > Patch series bootstrapped and regtested on x86_64-pc-linux-gnu,
> > and also tested against cmcstl2 and range-v3.
> > 
> > gcc/cp/ChangeLog:
> > 
> > 	PR c++/93907
> > 	* constraint.cc (tsubst_parameter_mapping): Also canonicalize
> > 	the type arguments of a TYPE_ARGUMENT_PACk.
> > 
> > gcc/testsuite/ChangeLog:
> > 
> > 	PR c++/93907
> > 	* g++.dg/cpp2a/concepts-using3.C: New test, based off of
> > 	concepts-using2.C.
> > ---
> >   gcc/cp/constraint.cc                         | 10 ++++
> >   gcc/testsuite/g++.dg/cpp2a/concepts-using3.C | 52 ++++++++++++++++++++
> >   2 files changed, 62 insertions(+)
> >   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> > 
> > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> > index b6f6f0d02a5..c871a8ab86a 100644
> > --- a/gcc/cp/constraint.cc
> > +++ b/gcc/cp/constraint.cc
> > @@ -2252,6 +2252,16 @@ tsubst_parameter_mapping (tree map, tree args,
> > subst_info info)
> 
> Hmm, the
> 
> >       else if (ARGUMENT_PACK_P (arg))
> >         new_arg = tsubst_argument_pack (arg, args, complain, in_decl);
> 
> just above this seems redundant, since tsubst_template_arg handles packs just
> fine.  In fact, I wonder why tsubst_argument_pack is used specifically
> anywhere?  It seems to get some edge cases better than the code in tsubst, but
> the solution to that would seem to be replacing the code in tsubst with a call
> to tsubst_argument_pack; then we can remove all the other calls to the
> function.

They seem interchangeable here wrt handling TYPE_ARGUMENT_PACKs, but not
NONTYPE_ARGUMENT_PACKs.  It looks like tsubst_template_arg ends up just
issuing an error from tsubst_expr if we try using it to substitute into
a NONTYPE_ARGUMENT_PACK.

> 
> >   	  new_arg = tsubst_template_arg (arg, args, complain, in_decl);
> >   	  if (TYPE_P (new_arg))
> >   	    new_arg = canonicalize_type_argument (new_arg, complain);
> > +	  if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK)
> > +	    {
> > +	      tree pack_args = ARGUMENT_PACK_ARGS (new_arg);
> > +	      for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++)
> > +		{
> > +		  tree& pack_arg = TREE_VEC_ELT (pack_args, i);
> > +		  if (TYPE_P (pack_arg))
> > +		    pack_arg = canonicalize_type_argument (pack_arg,
> > complain);
> 
> Do we need the TYPE_P here, since we already know we're in a
> TYPE_ARGUMENT_PACK?  That is, can an element of a TYPE_ARGUMENT_PACK be an
> invalid argument to canonicalize_type_argument?

With -fconcepts-ts, the elements of a TYPE_ARGUMENT_PACK here can be
TEMPLATE_DECLs, as in e.g. line 28 of concepts/template-parm3.C.

> 
> OTOH, I wonder if we need to canonicalize non-type arguments here as well?

Hmm, I'm not sure.  Not doing so should at worst result in a
satisfaction cache miss in release builds, and in checking builds should
get caught by the hash table sanitizer.  I haven't been able to come up
with a testcase that demonstrates it's necessary.

> 
> I wonder if tsubst_template_arg should canonicalize rather than leave that up
> to the caller?  I suppose that could do a bit more work when the result is
> going to end up in convert_template_argument and get canonicalized again; I
> don't know if that would be significant.

That seems like it works, based on some limited testing.  But there are
only two users of canonicalize_template_argument outside of
convert_template_argument itself, and the one use in unify is still
needed even with this change (or else we get many ICEs coming from
verify_unstripped_args if we try to remove it).  So the benefit of such
a change seems marginal at the moment.

> 
> >   	}
> >         if (new_arg == error_mark_node)
> >   	return error_mark_node;
> > diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> > b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> > new file mode 100644
> > index 00000000000..2c8ad40d104
> > --- /dev/null
> > +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
> > @@ -0,0 +1,52 @@
> > +// PR c++/93907
> > +// { dg-options -std=gnu++20 }
> > +
> > +// This testcase is a variadic version of concepts-using2.C; the only
> > +// difference is that 'cd' and 'ce' are now variadic concepts.
> > +
> > +template <int a> struct c {
> > +  static constexpr int d = a;
> > +  typedef c e;
> > +};
> > +template <typename> struct f;
> > +template <typename b> using g = typename f<b>::e;
> > +struct b;
> > +template <typename b> struct f { using e = b; };
> > +template <typename ai> struct m { typedef g<ai> aj; };
> > +template <typename b> struct n { typedef typename m<b>::aj e; };
> > +template <typename b> using an = typename n<b>::e;
> > +template <typename> constexpr bool ao = c<true>::d;
> > +template <typename> constexpr bool i = c<1>::d;
> > +template <typename> concept bb = i<b>;
> > +#ifdef __SIZEOF_INT128__
> > +using cc = __int128;
> > +#else
> > +using cc = long long;
> > +#endif
> > +template <typename...> concept cd = bb<cc>;
> > +template <typename... bt> concept ce = requires { requires cd<bt...>; };
> > +template <typename bt> concept h = ce<bt>;
> > +template <typename bt> concept l = h<bt>;
> > +template <typename> concept cl = ao<b>;
> > +template <typename b> concept cp = requires(b j) {
> > +  requires h<an<decltype(j.begin())>>;
> > +};
> > +struct o {
> > +  template <cl b> requires cp<b> auto operator()(b) {}
> > +};
> > +template <typename b> using cm = decltype(o{}(b()));
> > +template <typename bt> concept ct = l<bt>;
> > +template <typename da> concept dd = ct<cm<da>>;
> > +template <typename da> concept de = dd<da>;
> > +struct {
> > +  template <de da, typename b> void operator()(da, b);
> > +} di;
> > +struct p {
> > +  void begin();
> > +};
> > +template <typename> using df = p;
> > +template <int> void q() {
> > +  df<int> k;
> > +  int d;
> > +  di(k, d);
> > +}
> > 
> 
> 

Re: [PATCH 1/4] c++: Fix ICE with variadic concepts and aliases [PR93907]

[Jason Merrill]

On 11/7/20 10:59 AM, Patrick Palka wrote:
> On Fri, 6 Nov 2020, Jason Merrill wrote:
> 
>> On 11/5/20 8:40 PM, Patrick Palka wrote:
>>> This patch (naively) extends the PR93907 fix to also apply to variadic
>>> concepts invoked with a type argument pack.  Without this, we ICE on
>>> the below testcase (a variadic version of concepts-using2.C) in the same
>>> manner as we used to on concepts-using2.C before r10-7133.
>>>
>>> Patch series bootstrapped and regtested on x86_64-pc-linux-gnu,
>>> and also tested against cmcstl2 and range-v3.
>>>
>>> gcc/cp/ChangeLog:
>>>
>>> 	PR c++/93907
>>> 	* constraint.cc (tsubst_parameter_mapping): Also canonicalize
>>> 	the type arguments of a TYPE_ARGUMENT_PACk.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>> 	PR c++/93907
>>> 	* g++.dg/cpp2a/concepts-using3.C: New test, based off of
>>> 	concepts-using2.C.
>>> ---
>>>    gcc/cp/constraint.cc                         | 10 ++++
>>>    gcc/testsuite/g++.dg/cpp2a/concepts-using3.C | 52 ++++++++++++++++++++
>>>    2 files changed, 62 insertions(+)
>>>    create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
>>>
>>> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
>>> index b6f6f0d02a5..c871a8ab86a 100644
>>> --- a/gcc/cp/constraint.cc
>>> +++ b/gcc/cp/constraint.cc
>>> @@ -2252,6 +2252,16 @@ tsubst_parameter_mapping (tree map, tree args,
>>> subst_info info)
>>
>> Hmm, the
>>
>>>        else if (ARGUMENT_PACK_P (arg))
>>>          new_arg = tsubst_argument_pack (arg, args, complain, in_decl);
>>
>> just above this seems redundant, since tsubst_template_arg handles packs just
>> fine.  In fact, I wonder why tsubst_argument_pack is used specifically
>> anywhere?  It seems to get some edge cases better than the code in tsubst, but
>> the solution to that would seem to be replacing the code in tsubst with a call
>> to tsubst_argument_pack; then we can remove all the other calls to the
>> function.
> 
> They seem interchangeable here wrt handling TYPE_ARGUMENT_PACKs, but not
> NONTYPE_ARGUMENT_PACKs.  It looks like tsubst_template_arg ends up just
> issuing an error from tsubst_expr if we try using it to substitute into
> a NONTYPE_ARGUMENT_PACK.
> 
>>
>>>    	  new_arg = tsubst_template_arg (arg, args, complain, in_decl);
>>>    	  if (TYPE_P (new_arg))
>>>    	    new_arg = canonicalize_type_argument (new_arg, complain);
>>> +	  if (TREE_CODE (new_arg) == TYPE_ARGUMENT_PACK)
>>> +	    {
>>> +	      tree pack_args = ARGUMENT_PACK_ARGS (new_arg);
>>> +	      for (int i = 0; i < TREE_VEC_LENGTH (pack_args); i++)
>>> +		{
>>> +		  tree& pack_arg = TREE_VEC_ELT (pack_args, i);
>>> +		  if (TYPE_P (pack_arg))
>>> +		    pack_arg = canonicalize_type_argument (pack_arg,
>>> complain);
>>
>> Do we need the TYPE_P here, since we already know we're in a
>> TYPE_ARGUMENT_PACK?  That is, can an element of a TYPE_ARGUMENT_PACK be an
>> invalid argument to canonicalize_type_argument?
> 
> With -fconcepts-ts, the elements of a TYPE_ARGUMENT_PACK here can be
> TEMPLATE_DECLs, as in e.g. line 28 of concepts/template-parm3.C.
> 
>>
>> OTOH, I wonder if we need to canonicalize non-type arguments here as well?
> 
> Hmm, I'm not sure.  Not doing so should at worst result in a
> satisfaction cache miss in release builds, and in checking builds should
> get caught by the hash table sanitizer.  I haven't been able to come up
> with a testcase that demonstrates it's necessary.
> 
>>
>> I wonder if tsubst_template_arg should canonicalize rather than leave that up
>> to the caller?  I suppose that could do a bit more work when the result is
>> going to end up in convert_template_argument and get canonicalized again; I
>> don't know if that would be significant.
> 
> That seems like it works, based on some limited testing.  But there are
> only two users of canonicalize_template_argument outside of
> convert_template_argument itself, and the one use in unify is still
> needed even with this change (or else we get many ICEs coming from
> verify_unstripped_args if we try to remove it).  So the benefit of such
> a change seems marginal at the moment.

Then the patch is OK as is.

>>>    	}
>>>          if (new_arg == error_mark_node)
>>>    	return error_mark_node;
>>> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
>>> b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
>>> new file mode 100644
>>> index 00000000000..2c8ad40d104
>>> --- /dev/null
>>> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-using3.C
>>> @@ -0,0 +1,52 @@
>>> +// PR c++/93907
>>> +// { dg-options -std=gnu++20 }
>>> +
>>> +// This testcase is a variadic version of concepts-using2.C; the only
>>> +// difference is that 'cd' and 'ce' are now variadic concepts.
>>> +
>>> +template <int a> struct c {
>>> +  static constexpr int d = a;
>>> +  typedef c e;
>>> +};
>>> +template <typename> struct f;
>>> +template <typename b> using g = typename f<b>::e;
>>> +struct b;
>>> +template <typename b> struct f { using e = b; };
>>> +template <typename ai> struct m { typedef g<ai> aj; };
>>> +template <typename b> struct n { typedef typename m<b>::aj e; };
>>> +template <typename b> using an = typename n<b>::e;
>>> +template <typename> constexpr bool ao = c<true>::d;
>>> +template <typename> constexpr bool i = c<1>::d;
>>> +template <typename> concept bb = i<b>;
>>> +#ifdef __SIZEOF_INT128__
>>> +using cc = __int128;
>>> +#else
>>> +using cc = long long;
>>> +#endif
>>> +template <typename...> concept cd = bb<cc>;
>>> +template <typename... bt> concept ce = requires { requires cd<bt...>; };
>>> +template <typename bt> concept h = ce<bt>;
>>> +template <typename bt> concept l = h<bt>;
>>> +template <typename> concept cl = ao<b>;
>>> +template <typename b> concept cp = requires(b j) {
>>> +  requires h<an<decltype(j.begin())>>;
>>> +};
>>> +struct o {
>>> +  template <cl b> requires cp<b> auto operator()(b) {}
>>> +};
>>> +template <typename b> using cm = decltype(o{}(b()));
>>> +template <typename bt> concept ct = l<bt>;
>>> +template <typename da> concept dd = ct<cm<da>>;
>>> +template <typename da> concept de = dd<da>;
>>> +struct {
>>> +  template <de da, typename b> void operator()(da, b);
>>> +} di;
>>> +struct p {
>>> +  void begin();
>>> +};
>>> +template <typename> using df = p;
>>> +template <int> void q() {
>>> +  df<int> k;
>>> +  int d;
>>> +  di(k, d);
>>> +}
>>>
>>
>>
>