public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Jason Merrill <jason@redhat.com>
To: gcc-patches List <gcc-patches@gcc.gnu.org>
Subject: C++ PATCH to add __integer_pack built-in for std::make_integer_sequence (c++/80396)
Date: Tue, 23 May 2017 20:27:00 -0000	[thread overview]
Message-ID: <CADzB+2mZwSaHLOXUGAdf06dfck2af9cg1Vp7-6nCGsHVMDJ=Fg@mail.gmail.com> (raw)

[-- 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" }

             reply	other threads:[~2017-05-23 20:14 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-05-23 20:27 Jason Merrill [this message]
2017-05-24 14:18 ` Andreas Schwab
2017-05-24 15:17   ` Jakub Jelinek
2017-05-24 18:50     ` Jason Merrill
2017-05-24 19:13       ` Jakub Jelinek

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CADzB+2mZwSaHLOXUGAdf06dfck2af9cg1Vp7-6nCGsHVMDJ=Fg@mail.gmail.com' \
    --to=jason@redhat.com \
    --cc=gcc-patches@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).