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

Jason Merrill jason@redhat.com
Fri Aug 7 20:12:02 GMT 2020


On 8/6/20 1:50 PM, Patrick Palka wrote:
> 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.

Maybe keep that 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.

Good question.  That code seems to go back to the initial implementation 
of constexpr.

   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;

So if eltinit already == new_ctx.ctor, this doesn't change anything?

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



More information about the Gcc-patches mailing list