C++ PATCH for c++/68422 (sizeof... slow to evaluate)

[Jason Merrill <jason at redhat dot com>]

This turns out to be because we represent sizeof... as a sizeof a pack 
expansion internally, and we generated a full new pack expansion one 
element at a time rather than just look at how many elements there were 
in the argument pack.

We already had an optimization in tsubst_parameter_pack to recognize 
when the pack expansion we're asking for will be the same as one of the 
argument packs, but we weren't doing it for expressions because we might 
need to convert_from_reference the elements.  This patch improves the 
optimization to recognize when we won't need to worry about that, and 
therefore handle more expression pack expansions, which fixes the 
quadratic behavior on the testcase.

But we'd like sizeof... to be fast for packs of references as well, so I 
added a flag to EXPR_PACK_EXPANSION for sizeof... so we can always just 
return the argument pack.  Surprisingly, this provided a small but 
consistent further speedup for the testcase.

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

commit 3d0560f2a78158cf6a3165d5cd8f1b6eda0d9fc8
Author: Jason Merrill <jason@redhat.com>
Date:   Thu Nov 19 15:36:50 2015 -0500

    	PR c++/68422
    
    	* cp-tree.h (PACK_EXPANSION_SIZEOF_P): New.
    	* parser.c (cp_parser_sizeof_pack): Set it.
    	* pt.c 	(tsubst_copy) [SIZEOF_EXPR]: Likewise.
    	(tsubst_pack_expansion): Improve T... shortcut for expression packs.

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 160bf1e..14ea119 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -98,6 +98,7 @@ c-common.h, not after.
       DECLTYPE_FOR_INIT_CAPTURE (in DECLTYPE_TYPE)
       CONSTRUCTOR_NO_IMPLICIT_ZERO (in CONSTRUCTOR)
       TINFO_USED_TEMPLATE_ID (in TEMPLATE_INFO)
+      PACK_EXPANSION_SIZEOF_P (in *_PACK_EXPANSION)
    2: IDENTIFIER_OPNAME_P (in IDENTIFIER_NODE)
       ICS_THIS_FLAG (in _CONV)
       DECL_INITIALIZED_BY_CONSTANT_EXPRESSION_P (in VAR_DECL)
@@ -3200,6 +3201,9 @@ extern void decl_shadowed_for_var_insert (tree, tree);
 /* True iff this pack expansion is within a function context.  */
 #define PACK_EXPANSION_LOCAL_P(NODE) TREE_LANG_FLAG_0 (NODE)
 
+/* True iff this pack expansion is for sizeof....  */
+#define PACK_EXPANSION_SIZEOF_P(NODE) TREE_LANG_FLAG_1 (NODE)
+
 /* True iff the wildcard can match a template parameter pack.  */
 #define WILDCARD_PACK_P(NODE) TREE_LANG_FLAG_0 (NODE)
 
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 30cde0b..24ed404 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -25868,6 +25868,7 @@ cp_parser_sizeof_pack (cp_parser *parser)
   else if (TREE_CODE (expr) == CONST_DECL)
     expr = DECL_INITIAL (expr);
   expr = make_pack_expansion (expr);
+  PACK_EXPANSION_SIZEOF_P (expr) = true;
 
   if (paren)
     cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN);
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index b4a5e71..5868be2 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -10868,14 +10868,26 @@ tsubst_pack_expansion (tree t, tree args, tsubst_flags_t complain,
 	}
     }
 
-  /* If the expansion is just T..., return the matching argument pack.  */
+  /* If the expansion is just T..., return the matching argument pack, unless
+     we need to call convert_from_reference on all the elements.  This is an
+     important optimization; see c++/68422.  */
   if (!unsubstituted_packs
       && TREE_PURPOSE (packs) == pattern)
     {
       tree args = ARGUMENT_PACK_ARGS (TREE_VALUE (packs));
+      /* Types need no adjustment, nor does sizeof..., and if we still have
+	 some pack expansion args we won't do anything yet.  */
       if (TREE_CODE (t) == TYPE_PACK_EXPANSION
+	  || PACK_EXPANSION_SIZEOF_P (t)
 	  || pack_expansion_args_count (args))
 	return args;
+      /* Also optimize expression pack expansions if we can tell that the
+	 elements won't have reference type.  */
+      tree type = TREE_TYPE (pattern);
+      if (type && TREE_CODE (type) != REFERENCE_TYPE
+	  && !PACK_EXPANSION_P (type)
+	  && !WILDCARD_TYPE_P (type))
+	return args;
       /* Otherwise use the normal path so we get convert_from_reference.  */
     }
 
@@ -13940,7 +13952,6 @@ tsubst_copy (tree t, tree args, tsubst_flags_t complain, tree in_decl)
     case SIZEOF_EXPR:
       if (PACK_EXPANSION_P (TREE_OPERAND (t, 0)))
         {
-
           tree expanded, op = TREE_OPERAND (t, 0);
 	  int len = 0;
 
@@ -13966,6 +13977,8 @@ tsubst_copy (tree t, tree args, tsubst_flags_t complain, tree in_decl)
 	    {
 	      if (TREE_CODE (expanded) == TREE_VEC)
 		expanded = TREE_VEC_ELT (expanded, len - 1);
+	      else
+		PACK_EXPANSION_SIZEOF_P (expanded) = true;
 
 	      if (TYPE_P (expanded))
 		return cxx_sizeof_or_alignof_type (expanded, SIZEOF_EXPR,