On Fri, 7 Aug 2020, Jason Merrill wrote:
> 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?
FWIW, the assert was
gcc_assert (*non_constant_p || eltinit == new_ctx->ctor);
and apparently it survives the testsuite when added to either the
RANGE_EXPR or non-RANGE_EXPR code paths in cxx_eval_vec_init.
I then tried adding an analogous assert to cxx_eval_bare_aggregate, but
this assert triggers for lots of our testcases, in particular when (but
not only when) an elt initializer is already a reduced constant
CONSTRUCTOR (since then cxx_eval_constant_expression just returns this
already-reduced CONSTRUCTOR without updating ctx->ctor).
I'm not sure why the assert should necessarily hold in cxx_eval_vec_init
but not in cxx_eval_bare_aggregate. I guess we never see a
VEC_INIT_EXPR whose elt initializer is a reduced constant CONSTRUCTOR or
similar?
>
> > 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?
Hmm, good point. I should take back saying that eltinit must already
equal new_ctx.ctor here, because I'm not convinced that/why it's true
(besides the experimental evidence) :)
It still seems surprising that we prefer the value of new_ctx.ctor over
the return value of cxx_eval_constant_expression in the RANGE_EXPR code
path after evaluating a sub-agregate initializer, but not in the
non-RANGE_EXPR path and also not in cxx_eval_bare_aggregate. But I
guess if it ain't broke, don't fix it, so maybe the patch should just
leave alone the 'eltinit = new_ctx.ctor' assignment?
>
> > + }
> > + 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);
> >
>
>
