| Message ID | 20200806175006.3522650-1-ppalka@redhat.com |
|---|---|
| State | New |
| Headers | show |
| Series | c++: Improve RANGE_EXPR optimization in cxx_eval_vec_init | expand |
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); >
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); > > > >
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? >>> } >>> 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 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); >>> >> >> >
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); > > > > > > > > > > > > > >
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);