[PATCH] c++: Improve RANGE_EXPR optimization in cxx_eval_vec_init

[Patrick Palka]

This patch eliminates an exponential dependence in cxx_eval_vec_init on
the array dimension of a VEC_INIT_EXPR when the RANGE_EXPR optimization
applies.  This is achieved by using a single constructor_elt (with index
RANGE_EXPR 0...max-1) per dimension instead of two constructor_elts
(with index 0 and RANGE_EXPR 1...max-1 respectively).  In doing so, we
can also get rid of the call to unshare_constructor since the element
initializer now gets used in exactly one spot.

The patch also removes the 'eltinit = new_ctx.ctor' assignment within the
RANGE_EXPR optimization since eltinit should already always be equal to
new_ctx.ctor here (modulo encountering an error when computing eltinit).
This was verified by running the testsuite against an appropriate assert.

Finally, this patch reverses the sense of the ctx->quiet test that
controls whether to short-circuit evaluation upon seeing an error.  This
should speed up speculative evaluation of non-constant VEC_INIT_EXPRs
(since ctx->quiet is true then).  I'm not sure why we were testing
!ctx->quiet originally; it's inconsistent with how we short-circuit in
other spots.  I contrived the testcase array60.C below which verifies
that we now short-circuit quickly.

Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK to
commit?

gcc/cp/ChangeLog:

	* constexpr.c (cxx_eval_vec_init_1): Move the i == 0 test to the
	if statement that guards the RANGE_EXPR optimization.  Invert
	the ctx->quiet test. Apply the RANGE_EXPR optimization before we
	append the first element initializer.  Truncate ctx->ctor when
	performing the RANGE_EXPR optimization.  Make the built
	RANGE_EXPR start at index 0 instead of 1.  Don't call
	unshare_constructor.

gcc/testsuite/ChangeLog:

	* g++.dg/cpp0x/constexpr-array28.C: New test.
	* g++.dg/init/array60.C: New test.
---
 gcc/cp/constexpr.c                            | 34 ++++++++++---------
 .../g++.dg/cpp0x/constexpr-array28.C          | 14 ++++++++
 gcc/testsuite/g++.dg/init/array60.C           | 13 +++++++
 3 files changed, 45 insertions(+), 16 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
 create mode 100644 gcc/testsuite/g++.dg/init/array60.C

diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index ab747a58fa0..e67ce5da355 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -4205,7 +4205,7 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
 	  if (value_init || init == NULL_TREE)
 	    {
 	      eltinit = NULL_TREE;
-	      reuse = i == 0;
+	      reuse = true;
 	    }
 	  else
 	    eltinit = cp_build_array_ref (input_location, init, idx, complain);
@@ -4222,7 +4222,7 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
 	    return ctx->ctor;
 	  eltinit = cxx_eval_constant_expression (&new_ctx, init, lval,
 						  non_constant_p, overflow_p);
-	  reuse = i == 0;
+	  reuse = true;
 	}
       else
 	{
@@ -4236,35 +4236,37 @@ cxx_eval_vec_init_1 (const constexpr_ctx *ctx, tree atype, tree init,
 	  eltinit = cxx_eval_constant_expression (&new_ctx, eltinit, lval,
 						  non_constant_p, overflow_p);
 	}
-      if (*non_constant_p && !ctx->quiet)
+      if (*non_constant_p && ctx->quiet)
 	break;
-      if (new_ctx.ctor != ctx->ctor)
-	{
-	  /* We appended this element above; update the value.  */
-	  gcc_assert ((*p)->last().index == idx);
-	  (*p)->last().value = eltinit;
-	}
-      else
-	CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
+
       /* Reuse the result of cxx_eval_constant_expression call
 	 from the first iteration to all others if it is a constant
 	 initializer that doesn't require relocations.  */
-      if (reuse
+      if (i == 0
+	  && reuse
 	  && max > 1
 	  && (eltinit == NULL_TREE
 	      || (initializer_constant_valid_p (eltinit, TREE_TYPE (eltinit))
 		  == null_pointer_node)))
 	{
-	  if (new_ctx.ctor != ctx->ctor)
-	    eltinit = new_ctx.ctor;
 	  tree range = build2 (RANGE_EXPR, size_type_node,
-			       build_int_cst (size_type_node, 1),
+			       build_int_cst (size_type_node, 0),
 			       build_int_cst (size_type_node, max - 1));
-	  CONSTRUCTOR_APPEND_ELT (*p, range, unshare_constructor (eltinit));
+	  vec_safe_truncate (*p, 0);
+	  CONSTRUCTOR_APPEND_ELT (*p, range, eltinit);
 	  break;
 	}
       else if (i == 0)
 	vec_safe_reserve (*p, max);
+
+      if (new_ctx.ctor != ctx->ctor)
+	{
+	  /* We appended this element above; update the value.  */
+	  gcc_assert ((*p)->last().index == idx);
+	  (*p)->last().value = eltinit;
+	}
+      else
+	CONSTRUCTOR_APPEND_ELT (*p, idx, eltinit);
     }
 
   if (!*non_constant_p)
diff --git a/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C b/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
new file mode 100644
index 00000000000..f844926e32b
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp0x/constexpr-array28.C
@@ -0,0 +1,14 @@
+// { dg-do compile { target c++11 } }
+
+struct A { int i = 42; };
+
+struct B
+{
+  A a[2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2][2];
+};
+
+void f() {
+  // Verify default initialization here does not scale exponentially
+  // with the number of array dimensions.
+  constexpr B b;
+}
diff --git a/gcc/testsuite/g++.dg/init/array60.C b/gcc/testsuite/g++.dg/init/array60.C
new file mode 100644
index 00000000000..22bd750f8e6
--- /dev/null
+++ b/gcc/testsuite/g++.dg/init/array60.C
@@ -0,0 +1,13 @@
+struct A { int i; };
+
+struct B
+{
+  virtual void f();
+  A a[10000000];
+};
+
+extern B b;
+
+// Verify that speculative constexpr evaluation of this non-constant
+// initializer does not scale with the size of the array member 'a'.
+B b2 (b);
-- 
2.28.0.97.gdc04167d37