[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