C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

[Jason Merrill]

[-- Attachment #1: Type: text/plain, Size: 594 bytes --]

make_integer_sequence currently uses template metaprogramming to
generate a sequence of integers, which is fairly expensive at compile
time: PR 80396 asked for some built-in to speed it up.  This patch
introduces __integer_pack as a magic function taking a single integer
argument; a call to this function as the pattern of a pack expansion
produces a list of integers which can be used as arguments to a
template (or a function, but that's not the goal).

Rather than introduce a new keyword, I decided to use a FUNCTION_DECL,
which works fine.

Tested x86_64-pc-linux-gnu, applying to trunk.

[-- Attachment #2: integer-pack4.diff --]
[-- Type: text/plain, Size: 10455 bytes --]

commit a5681fc17f5d79e443062d7fc652d45ba81cda0f
Author: Jason Merrill <jason@redhat.com>
Date:   Fri May 12 07:45:02 2017 -0400

            PR c++/80396 - built-in for make_integer_sequence.
    
            * pt.c (builtin_pack_fn_p, builtin_pack_call_p)
            (expand_integer_pack, expand_builtin_pack_call): New.
            (find_parameter_packs_r): Check builtin_pack_call_p.
            (check_for_bare_parameter_packs): Handle it.
            (tsubst_pack_expansion): Call expand_builtin_pack_call.
            (declare_integer_pack): New.
            (init_template_processing): Call it.
            * decl2.c (mark_used): Check builtin_pack_fn_p.

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 0064222..3f9bb6b 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -6372,6 +6372,7 @@ extern bool always_instantiate_p		(tree);
 extern void maybe_instantiate_noexcept		(tree);
 extern tree instantiate_decl			(tree, bool, bool);
 extern int comp_template_parms			(const_tree, const_tree);
+extern bool builtin_pack_fn_p			(tree);
 extern bool uses_parameter_packs                (tree);
 extern bool template_parameter_pack_p           (const_tree);
 extern bool function_parameter_pack_p		(const_tree);
diff --git a/gcc/cp/decl2.c b/gcc/cp/decl2.c
index 7247b0f..85310e0 100644
--- a/gcc/cp/decl2.c
+++ b/gcc/cp/decl2.c
@@ -5109,6 +5109,13 @@ mark_used (tree decl, tsubst_flags_t complain)
   if (!require_deduced_type (decl, complain))
     return false;
 
+  if (builtin_pack_fn_p (decl))
+    {
+      error ("use of built-in parameter pack %qD outside of a template",
+	     DECL_NAME (decl));
+      return false;
+    }
+
   /* If we don't need a value, then we don't need to synthesize DECL.  */
   if (cp_unevaluated_operand || in_discarded_stmt)
     return true;
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index cdde7a0..e11c601 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -15096,7 +15096,7 @@ cp_parser_template_parameter (cp_parser* parser, bool *is_non_type,
   *is_parameter_pack = false;
   /* Peek at the next token.  */
   token = cp_lexer_peek_token (parser->lexer);
-  /* If it is `class' or `template', we have a type-parameter.  */
+  /* If it is `template', we have a type-parameter.  */
   if (token->keyword == RID_TEMPLATE)
     return cp_parser_type_parameter (parser, is_parameter_pack);
   /* If it is `class' or `typename' we do not know yet whether it is a
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index f9980fe..93874cd 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -215,6 +215,7 @@ static tree instantiate_alias_template (tree, tree, tsubst_flags_t);
 static bool complex_alias_template_p (const_tree tmpl);
 static tree tsubst_attributes (tree, tree, tsubst_flags_t, tree);
 static tree canonicalize_expr_argument (tree, tsubst_flags_t);
+static tree make_argument_pack (tree);
 
 /* Make the current scope suitable for access checking when we are
    processing T.  T can be FUNCTION_DECL for instantiated function
@@ -3414,6 +3415,101 @@ get_template_argument_pack_elems (const_tree t)
   return ARGUMENT_PACK_ARGS (t);
 }
 
+/* True iff FN is a function representing a built-in variadic parameter
+   pack.  */
+
+bool
+builtin_pack_fn_p (tree fn)
+{
+  if (!fn
+      || TREE_CODE (fn) != FUNCTION_DECL
+      || !DECL_IS_BUILTIN (fn))
+    return false;
+
+  if (strcmp (IDENTIFIER_POINTER (DECL_NAME (fn)), "__integer_pack") == 0)
+    return true;
+
+  return false;
+}
+
+/* True iff CALL is a call to a function representing a built-in variadic
+   parameter pack.  */
+
+static bool
+builtin_pack_call_p (tree call)
+{
+  if (TREE_CODE (call) != CALL_EXPR)
+    return false;
+  return builtin_pack_fn_p (CALL_EXPR_FN (call));
+}
+
+/* Return a TREE_VEC for the expansion of __integer_pack(HI).  */
+
+static tree
+expand_integer_pack (tree call, tree args, tsubst_flags_t complain,
+		     tree in_decl)
+{
+  tree ohi = CALL_EXPR_ARG (call, 0);
+  tree hi = tsubst_copy_and_build (ohi, args, complain, in_decl,
+				   false/*fn*/, true/*int_cst*/);
+
+  if (value_dependent_expression_p (hi))
+    {
+      if (hi != ohi)
+	{
+	  call = copy_node (call);
+	  CALL_EXPR_ARG (call, 0) = hi;
+	}
+      tree ex = make_pack_expansion (call);
+      tree vec = make_tree_vec (1);
+      TREE_VEC_ELT (vec, 0) = ex;
+      return vec;
+    }
+  else
+    {
+      hi = cxx_constant_value (hi);
+      int len = valid_constant_size_p (hi) ? tree_to_shwi (hi) : -1;
+
+      /* Calculate the largest value of len that won't make the size of the vec
+	 overflow an int.  The compiler will exceed resource limits long before
+	 this, but it seems a decent place to diagnose.  */
+      int max = ((INT_MAX - sizeof (tree_vec)) / sizeof (tree)) + 1;
+
+      if (len < 0 || len > max)
+	{
+	  if ((complain & tf_error)
+	      && hi != error_mark_node)
+	    error ("argument to __integer_pack must be between 0 and %d", max);
+	  return error_mark_node;
+	}
+
+      tree vec = make_tree_vec (len);
+
+      for (int i = 0; i < len; ++i)
+	TREE_VEC_ELT (vec, i) = size_int (i);
+
+      return vec;
+    }
+}
+
+/* Return a TREE_VEC for the expansion of built-in template parameter pack
+   CALL.  */
+
+static tree
+expand_builtin_pack_call (tree call, tree args, tsubst_flags_t complain,
+			  tree in_decl)
+{
+  if (!builtin_pack_call_p (call))
+    return NULL_TREE;
+
+  tree fn = CALL_EXPR_FN (call);
+
+  if (strcmp (IDENTIFIER_POINTER (DECL_NAME (fn)), "__integer_pack") == 0)
+    return expand_integer_pack (call, args, complain, in_decl);
+
+  return NULL_TREE;
+}
+
 /* Structure used to track the progress of find_parameter_packs_r.  */
 struct find_parameter_pack_data 
 {
@@ -3503,6 +3599,11 @@ find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
 	}
       break;
 
+    case CALL_EXPR:
+      if (builtin_pack_call_p (t))
+	parameter_pack_p = true;
+      break;
+
     case BASES:
       parameter_pack_p = true;
       break;
@@ -3801,6 +3902,8 @@ check_for_bare_parameter_packs (tree t)
             name = TYPE_NAME (pack);
           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
+	  else if (TREE_CODE (pack) == CALL_EXPR)
+	    name = DECL_NAME (CALL_EXPR_FN (pack));
           else
             name = DECL_NAME (pack);
 
@@ -11286,6 +11389,7 @@ tsubst_pack_expansion (tree t, tree args, tsubst_flags_t complain,
 
       if (TREE_CODE (parm_pack) == BASES)
        {
+	 gcc_assert (parm_pack == pattern);
          if (BASES_DIRECT (parm_pack))
            return calculate_direct_bases (tsubst_expr (BASES_TYPE (parm_pack),
                                                         args, complain, in_decl, false));
@@ -11293,7 +11397,14 @@ tsubst_pack_expansion (tree t, tree args, tsubst_flags_t complain,
            return calculate_bases (tsubst_expr (BASES_TYPE (parm_pack),
                                                  args, complain, in_decl, false));
        }
-      if (TREE_CODE (parm_pack) == PARM_DECL)
+      else if (builtin_pack_call_p (parm_pack))
+	{
+	  /* ??? Support use in other patterns.  */
+	  gcc_assert (parm_pack == pattern);
+	  return expand_builtin_pack_call (parm_pack, args,
+					   complain, in_decl);
+	}
+      else if (TREE_CODE (parm_pack) == PARM_DECL)
 	{
 	  /* We know we have correct local_specializations if this
 	     expansion is at function scope, or if we're dealing with a
@@ -26007,6 +26118,21 @@ init_constraint_processing (void)
   subsumption_table = hash_table<subsumption_hasher>::create_ggc(37);
 }
 
+/* __integer_pack(N) in a pack expansion expands to a sequence of numbers from
+   0..N-1.  */
+
+void
+declare_integer_pack (void)
+{
+  tree ipfn = push_library_fn (get_identifier ("__integer_pack"),
+			       build_function_type_list (integer_type_node,
+							 integer_type_node,
+							 NULL_TREE),
+			       NULL_TREE, ECF_CONST);
+  DECL_DECLARED_CONSTEXPR_P (ipfn) = true;
+  DECL_BUILT_IN_CLASS (ipfn) = BUILT_IN_FRONTEND;
+}
+
 /* Set up the hash tables for template instantiations.  */
 
 void
@@ -26014,6 +26140,9 @@ init_template_processing (void)
 {
   decl_specializations = hash_table<spec_hasher>::create_ggc (37);
   type_specializations = hash_table<spec_hasher>::create_ggc (37);
+
+  if (cxx_dialect >= cxx11)
+    declare_integer_pack ();
 }
 
 /* Print stats about the template hash tables for -fstats.  */
diff --git a/gcc/doc/extend.texi b/gcc/doc/extend.texi
index 3511d25..6cc95a8 100644
--- a/gcc/doc/extend.texi
+++ b/gcc/doc/extend.texi
@@ -22645,6 +22645,12 @@ true, else it is false.
 The underlying type of @code{type}.  Requires: @code{type} shall be
 an enumeration type ([dcl.enum]).
 
+@item __integer_pack (length)
+When used as the pattern of a pack expansion within a template
+definition, expands to a template argument pack containing integers
+from @code{0} to @code{length-1}.  This is provided for efficient
+implementation of @code{std::make_integer_sequence}.
+
 @end table
 
 
diff --git a/gcc/testsuite/g++.dg/ext/integer-pack1.C b/gcc/testsuite/g++.dg/ext/integer-pack1.C
new file mode 100644
index 0000000..cc54f50
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ext/integer-pack1.C
@@ -0,0 +1,22 @@
+// { dg-do compile { target c++11 } }
+
+template <int... I> struct A { };
+
+template <int N>
+using TS = A<__integer_pack(N)...>;
+
+TS<4> t = 1;			// { dg-error "A<0, 1, 2, 3>" }
+
+template <int N>
+using TS2 = A<__integer_pack(N)...>; // { dg-error "argument" }
+
+TS2<-1> t2;
+
+template <int N>
+using TS2 = A<__integer_pack(N)>; // { dg-error "not expanded" }
+
+template <int N>
+using TS3 = A<__integer_pack>; // { dg-error "" }
+
+int i = __integer_pack(2);	// { dg-error "__integer_pack" }
+int j = __integer_pack(2)...;	// { dg-error "__integer_pack" }
diff --git a/gcc/testsuite/g++.dg/ext/integer-pack2.C b/gcc/testsuite/g++.dg/ext/integer-pack2.C
new file mode 100644
index 0000000..370dbeb
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ext/integer-pack2.C
@@ -0,0 +1,12 @@
+// { dg-do compile { target c++11 } }
+// { dg-options -w }
+
+#include <limits.h>
+
+template<typename T, T...> struct integer_sequence { };
+template<typename T, T num>
+ using make_integer_sequence = integer_sequence<T, __integer_pack(num)...>; // { dg-error "argument" }
+
+make_integer_sequence<int, -9223372036854775808> w;
+make_integer_sequence<int, INT_MAX> x;	   // { dg-message "required" }
+make_integer_sequence<int, -2147483650> y; // { dg-message "required" }

Re: C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

[Andreas Schwab]

FAIL: g++.dg/ext/integer-pack2.C  -std=gnu++11 (test for excess errors)
Excess errors:
/daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
/daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

[Jakub Jelinek]

On Wed, May 24, 2017 at 04:16:30PM +0200, Andreas Schwab wrote:
> FAIL: g++.dg/ext/integer-pack2.C  -std=gnu++11 (test for excess errors)
> Excess errors:
> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]

To be precise, it fails only on 32-bit targets.

If we at that point want some wider integer that when cast to int
is 0 (or small enough positive number?), shall we use something like
this, or say 1LL << (sizeof (int) * __CHAR_BIT__), or 2LL * INT_MIN,
something else?  Do we need to include <limits.h>?  Or can we replace
INT_MAX with __INT_MAX__?
Not sure about that -2147483650 for 16-bit int targets (perhaps the test can
be guarded with int32 effective target).

2017-05-24  Jakub Jelinek  <jakub@redhat.com>

	* g++.dg/ext/integer-pack2.C (w): Use -9223372036854775807LL - 1
	instead of -9223372036854775808.

--- gcc/testsuite/g++.dg/ext/integer-pack2.C.jj	2017-05-24 11:59:01.000000000 +0200
+++ gcc/testsuite/g++.dg/ext/integer-pack2.C	2017-05-24 16:24:18.341421124 +0200
@@ -7,6 +7,6 @@ template<typename T, T...> struct intege
 template<typename T, T num>
  using make_integer_sequence = integer_sequence<T, __integer_pack(num)...>; // { dg-error "argument" }
 
-make_integer_sequence<int, -9223372036854775808> w;
+make_integer_sequence<int, -9223372036854775807LL - 1> w;
 make_integer_sequence<int, INT_MAX> x;	   // { dg-message "required" }
 make_integer_sequence<int, -2147483650> y; // { dg-message "required" }


	Jakub

Re: C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

[Jason Merrill]

On Wed, May 24, 2017 at 11:08 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> On Wed, May 24, 2017 at 04:16:30PM +0200, Andreas Schwab wrote:
>> FAIL: g++.dg/ext/integer-pack2.C  -std=gnu++11 (test for excess errors)
>> Excess errors:
>> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
>> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
>
> To be precise, it fails only on 32-bit targets.

> If we at that point want some wider integer that when cast to int
> is 0 (or small enough positive number?), shall we use something like
> this, or say 1LL << (sizeof (int) * __CHAR_BIT__), or 2LL * INT_MIN,
> something else?

This is fine.

> Do we need to include <limits.h>?  Or can we replace
> INT_MAX with __INT_MAX__?

__INT_MAX__ sounds good.

> Not sure about that -2147483650 for 16-bit int targets (perhaps the test can
> be guarded with int32 effective target).

Yes, restricting the test to int32 seems like the easiest fix.

Jason

Re: C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)

[Jakub Jelinek]

On Wed, May 24, 2017 at 02:47:08PM -0400, Jason Merrill wrote:
> On Wed, May 24, 2017 at 11:08 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> > On Wed, May 24, 2017 at 04:16:30PM +0200, Andreas Schwab wrote:
> >> FAIL: g++.dg/ext/integer-pack2.C  -std=gnu++11 (test for excess errors)
> >> Excess errors:
> >> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
> >> /daten/aranym/gcc/gcc-20170524/gcc/testsuite/g++.dg/ext/integer-pack2.C:10:48: error: overflow in constant expression [-fpermissive]
> >
> > To be precise, it fails only on 32-bit targets.
> 
> > If we at that point want some wider integer that when cast to int
> > is 0 (or small enough positive number?), shall we use something like
> > this, or say 1LL << (sizeof (int) * __CHAR_BIT__), or 2LL * INT_MIN,
> > something else?
> 
> This is fine.
> 
> > Do we need to include <limits.h>?  Or can we replace
> > INT_MAX with __INT_MAX__?
> 
> __INT_MAX__ sounds good.
> 
> > Not sure about that -2147483650 for 16-bit int targets (perhaps the test can
> > be guarded with int32 effective target).
> 
> Yes, restricting the test to int32 seems like the easiest fix.

Ok, I've committed this (also add something to avoid failing on hypothetical
64-bit int 64-bit long long target).  Tested for both -m32 and -m64 on
x86_64-linux.

2017-05-24  Jakub Jelinek  <jakub@redhat.com>

	* g++.dg/ext/integer-pack2.C: Require int32 effective target.
	Don't include limits.h.
	(w): Conditionalize on long long wider than int.  Use
	1LL << (__SIZEOF_INT__ * __CHAR_BIT__) instead of
	-9223372036854775808.
	(x): Use __INT_MAX__ instead of INT_MAX.

--- gcc/testsuite/g++.dg/ext/integer-pack2.C.jj	2017-05-24 11:59:01.000000000 +0200
+++ gcc/testsuite/g++.dg/ext/integer-pack2.C	2017-05-24 21:07:02.000000000 +0200
@@ -1,12 +1,12 @@
-// { dg-do compile { target c++11 } }
+// { dg-do compile { target { c++11 && int32 } } }
 // { dg-options -w }
 
-#include <limits.h>
-
 template<typename T, T...> struct integer_sequence { };
 template<typename T, T num>
  using make_integer_sequence = integer_sequence<T, __integer_pack(num)...>; // { dg-error "argument" }
 
-make_integer_sequence<int, -9223372036854775808> w;
-make_integer_sequence<int, INT_MAX> x;	   // { dg-message "required" }
+#if __SIZEOF_LONG_LONG__ > __SIZEOF_INT__
+make_integer_sequence<int, 1LL << (__SIZEOF_INT__ * __CHAR_BIT__)> w;
+#endif
+make_integer_sequence<int, __INT_MAX__> x; // { dg-message "required" }
 make_integer_sequence<int, -2147483650> y; // { dg-message "required" }


	Jakub