[PATCH] c++: Improve RANGE_EXPR optimization in cxx_eval_vec_init
Patrick Palka
ppalka@redhat.com
Tue Aug 11 19:45:33 GMT 2020
On Tue, 11 Aug 2020, Jason Merrill wrote:
> On 8/10/20 9:21 AM, Patrick Palka wrote:
> > 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?
>
> That sounds like a plausible reason.
>
> > >
> > > > 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;
>
> The patch seems to replace checking i == 0 here with checking it in the
> condition below, which seems equivalent. Why?
Oops, I forgot to make note of this in the patch description, but this
part is (hopefully) just a drive-by simplification, no functionality
change intended. I'll add a remark to that effect in the ChangeLog.
>
> > > > }
> > > > 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?
>
> It would be good for this and cxx_eval_bare_aggregate to work more similarly.
> As you point out, b_a doesn't rely on new_ctx->ctor at all, which seems
> important for the cases you mention where adding the assert there failed. So
> I think removing the assignment is an improvement. Jakub, you don't happen to
Sounds good.
> remember why you added it, do you?
>
> > > > + }
> > > > + 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