Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Mon, 1 Nov 2021, Patrick Palka wrote:
> On Fri, 29 Oct 2021, Jakub Jelinek wrote:
>
> > On Thu, Oct 28, 2021 at 03:35:20PM -0400, Patrick Palka wrote:
> > > > Is there a reason to turn this mode of evaluating everything twice if an
> > > > error should be diagnosed all the time, rather than only if we actually
> > > > see
> > > > a TRUTH_*_EXPR we want to handle this way?
> > > > If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
> > > > the first operand is already a constant, that seems like a waste of
> > > > time.
> > >
> > > Hmm yeah, at the very least it wouldn't hurt to check
> > > processing_template_decl before doing the tf_error shenanigans. I'm not
> > > sure if we would gain anything by first looking for TRUTH_*_EXPR since
> > > that'd involve walking the entire expression anyway IIUC.
> >
> > I meant actually something like:
> > --- gcc/cp/constexpr.c.jj 2021-10-28 20:07:48.566193259 +0200
> > +++ gcc/cp/constexpr.c 2021-10-29 13:47:48.824026156 +0200
> > @@ -8789,7 +8789,7 @@ potential_constant_expression_1 (tree t,
> > return false;
> > }
> > else if (!check_for_uninitialized_const_var
> > - (tmp, /*constexpr_context_p=*/true, flags))
> > + (tmp, /*constexpr_context_p=*/true, flags & ~(1 << 30)))
> > return false;
> > }
> >return RECUR (tmp, want_rval);
> > @@ -8896,14 +8896,36 @@ potential_constant_expression_1 (tree t,
> > tree op1 = TREE_OPERAND (t, 1);
> > if (!RECUR (op0, rval))
> > return false;
> > - if (!(flags & tf_error) && RECUR (op1, rval))
> > - /* When quiet, try to avoid expensive trial evaluation by first
> > -checking potentiality of the second operand. */
> > - return true;
> > - if (!processing_template_decl)
> > - op0 = cxx_eval_outermost_constant_expr (op0, true);
> > + if (TREE_CODE (op0) != INTEGER_CST && !processing_template_decl)
> > + {
> > + /* If op0 is not a constant, we can either
> > + cxx_eval_outermost_constant_expr first, or RECUR (op1, rval)
> > + first. If quiet, perform the latter first, if not quiet
> > + and it is the outermost such TRUTH_*_EXPR, perform the
> > + latter first in quiet mode, followed by the former and
> > + retry with the latter in non-quiet mode. */
> > + if ((flags & (1 << 30)) != 0)
> > + op0 = cxx_eval_outermost_constant_expr (op0, true);
> > + else if ((flags & tf_error) != 0)
> > + {
> > + flags &= ~tf_error;
> > + if (RECUR (op1, rval))
> > + return true;
> > + op0 = cxx_eval_outermost_constant_expr (op0, true);
> > + flags |= tf_error | (1 << 30);
> > + }
> > + else
> > + {
> > + if (RECUR (op1, rval))
> > + return true;
> > + op0 = cxx_eval_outermost_constant_expr (op0, true);
> > + if (tree_int_cst_equal (op0, tmp))
> > + return false;
> > + return true;
> > + }
> > + }
> > if (tree_int_cst_equal (op0, tmp))
> > - return (flags & tf_error) ? RECUR (op1, rval) : false;
> > + return RECUR (op1, rval);
> > else
> > return true;
> >}
> > @@ -9112,17 +9134,6 @@ bool
> > potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool
> > now,
> > tsubst_flags_t flags)
> > {
> > - if (flags & tf_error)
> > -{
> > - /* Check potentiality quietly first, as that could be performed more
> > -efficiently in some cases (currently only for TRUTH_*_EXPR). If
> > -that fails, replay the check noisily to give errors. */
> > - flags &= ~tf_error;
> > - if (potential_constant_expression_1 (t, want_rval, strict, now,
> > flags))
> > - return true;
> > - flags |= tf_error;
> > -}
> > -
> >tree target = NULL_TREE;
> >return potential_constant_expression_1 (t, want_rval, strict, now,
> > flags, &target);
> >
> > (perhaps with naming the 1 << 30 as tf_something or using different bit for
> > that). So no doubling of potential_constant_expression_1 evaluation
> > for tf_error unless a TRUTH_*_EXPR is seen outside of template with
> > potentially constant first operand other than INTEGER_CST, but similarly to
> > what you did, make sure that there are at most two calls and not more.
>
> That makes sense, though it's somewhat unfortunate that we'd have to
> use/add an adhoc tsubst_flags_t flag with this approach :/
>
> >
> > > > As I said, another possibility is something like:
> > > > /* Try to quietly evaluate T to constant, but don't try too hard. */
> > > >
> > > > static tree
> > > > potential_constant_expression_eval (tree t)
> > > > {
> > > > auto o = make_temp_override (constexpr_ops_limit,
> > > >MIN (constexpr_ops_limit, 100));
> > > > return cxx_eval_outermost_const
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Fri, 29 Oct 2021, Jakub Jelinek wrote:
> On Thu, Oct 28, 2021 at 03:35:20PM -0400, Patrick Palka wrote:
> > > Is there a reason to turn this mode of evaluating everything twice if an
> > > error should be diagnosed all the time, rather than only if we actually
> > > see
> > > a TRUTH_*_EXPR we want to handle this way?
> > > If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
> > > the first operand is already a constant, that seems like a waste of time.
> >
> > Hmm yeah, at the very least it wouldn't hurt to check
> > processing_template_decl before doing the tf_error shenanigans. I'm not
> > sure if we would gain anything by first looking for TRUTH_*_EXPR since
> > that'd involve walking the entire expression anyway IIUC.
>
> I meant actually something like:
> --- gcc/cp/constexpr.c.jj 2021-10-28 20:07:48.566193259 +0200
> +++ gcc/cp/constexpr.c2021-10-29 13:47:48.824026156 +0200
> @@ -8789,7 +8789,7 @@ potential_constant_expression_1 (tree t,
> return false;
> }
> else if (!check_for_uninitialized_const_var
> -(tmp, /*constexpr_context_p=*/true, flags))
> +(tmp, /*constexpr_context_p=*/true, flags & ~(1 << 30)))
> return false;
> }
>return RECUR (tmp, want_rval);
> @@ -8896,14 +8896,36 @@ potential_constant_expression_1 (tree t,
> tree op1 = TREE_OPERAND (t, 1);
> if (!RECUR (op0, rval))
> return false;
> - if (!(flags & tf_error) && RECUR (op1, rval))
> - /* When quiet, try to avoid expensive trial evaluation by first
> - checking potentiality of the second operand. */
> - return true;
> - if (!processing_template_decl)
> - op0 = cxx_eval_outermost_constant_expr (op0, true);
> + if (TREE_CODE (op0) != INTEGER_CST && !processing_template_decl)
> + {
> + /* If op0 is not a constant, we can either
> +cxx_eval_outermost_constant_expr first, or RECUR (op1, rval)
> +first. If quiet, perform the latter first, if not quiet
> +and it is the outermost such TRUTH_*_EXPR, perform the
> +latter first in quiet mode, followed by the former and
> +retry with the latter in non-quiet mode. */
> + if ((flags & (1 << 30)) != 0)
> + op0 = cxx_eval_outermost_constant_expr (op0, true);
> + else if ((flags & tf_error) != 0)
> + {
> + flags &= ~tf_error;
> + if (RECUR (op1, rval))
> + return true;
> + op0 = cxx_eval_outermost_constant_expr (op0, true);
> + flags |= tf_error | (1 << 30);
> + }
> + else
> + {
> + if (RECUR (op1, rval))
> + return true;
> + op0 = cxx_eval_outermost_constant_expr (op0, true);
> + if (tree_int_cst_equal (op0, tmp))
> + return false;
> + return true;
> + }
> + }
> if (tree_int_cst_equal (op0, tmp))
> - return (flags & tf_error) ? RECUR (op1, rval) : false;
> + return RECUR (op1, rval);
> else
> return true;
>}
> @@ -9112,17 +9134,6 @@ bool
> potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool
> now,
>tsubst_flags_t flags)
> {
> - if (flags & tf_error)
> -{
> - /* Check potentiality quietly first, as that could be performed more
> - efficiently in some cases (currently only for TRUTH_*_EXPR). If
> - that fails, replay the check noisily to give errors. */
> - flags &= ~tf_error;
> - if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
> - return true;
> - flags |= tf_error;
> -}
> -
>tree target = NULL_TREE;
>return potential_constant_expression_1 (t, want_rval, strict, now,
> flags, &target);
>
> (perhaps with naming the 1 << 30 as tf_something or using different bit for
> that). So no doubling of potential_constant_expression_1 evaluation
> for tf_error unless a TRUTH_*_EXPR is seen outside of template with
> potentially constant first operand other than INTEGER_CST, but similarly to
> what you did, make sure that there are at most two calls and not more.
That makes sense, though it's somewhat unfortunate that we'd have to
use/add an adhoc tsubst_flags_t flag with this approach :/
>
> > > As I said, another possibility is something like:
> > > /* Try to quietly evaluate T to constant, but don't try too hard. */
> > >
> > > static tree
> > > potential_constant_expression_eval (tree t)
> > > {
> > > auto o = make_temp_override (constexpr_ops_limit,
> > > MIN (constexpr_ops_limit, 100));
> > > return cxx_eval_outermost_constant_expr (t, true);
> > > }
> > > and using this new function instead of cxx_eval_outermost_constant_expr
> > > (op, true);
> > > everywhere in potential_constant_expres
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Thu, Oct 28, 2021 at 03:35:20PM -0400, Patrick Palka wrote:
> > Is there a reason to turn this mode of evaluating everything twice if an
> > error should be diagnosed all the time, rather than only if we actually see
> > a TRUTH_*_EXPR we want to handle this way?
> > If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
> > the first operand is already a constant, that seems like a waste of time.
>
> Hmm yeah, at the very least it wouldn't hurt to check
> processing_template_decl before doing the tf_error shenanigans. I'm not
> sure if we would gain anything by first looking for TRUTH_*_EXPR since
> that'd involve walking the entire expression anyway IIUC.
I meant actually something like:
--- gcc/cp/constexpr.c.jj 2021-10-28 20:07:48.566193259 +0200
+++ gcc/cp/constexpr.c 2021-10-29 13:47:48.824026156 +0200
@@ -8789,7 +8789,7 @@ potential_constant_expression_1 (tree t,
return false;
}
else if (!check_for_uninitialized_const_var
- (tmp, /*constexpr_context_p=*/true, flags))
+ (tmp, /*constexpr_context_p=*/true, flags & ~(1 << 30)))
return false;
}
return RECUR (tmp, want_rval);
@@ -8896,14 +8896,36 @@ potential_constant_expression_1 (tree t,
tree op1 = TREE_OPERAND (t, 1);
if (!RECUR (op0, rval))
return false;
- if (!(flags & tf_error) && RECUR (op1, rval))
- /* When quiet, try to avoid expensive trial evaluation by first
-checking potentiality of the second operand. */
- return true;
- if (!processing_template_decl)
- op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (TREE_CODE (op0) != INTEGER_CST && !processing_template_decl)
+ {
+ /* If op0 is not a constant, we can either
+ cxx_eval_outermost_constant_expr first, or RECUR (op1, rval)
+ first. If quiet, perform the latter first, if not quiet
+ and it is the outermost such TRUTH_*_EXPR, perform the
+ latter first in quiet mode, followed by the former and
+ retry with the latter in non-quiet mode. */
+ if ((flags & (1 << 30)) != 0)
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ else if ((flags & tf_error) != 0)
+ {
+ flags &= ~tf_error;
+ if (RECUR (op1, rval))
+ return true;
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ flags |= tf_error | (1 << 30);
+ }
+ else
+ {
+ if (RECUR (op1, rval))
+ return true;
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (tree_int_cst_equal (op0, tmp))
+ return false;
+ return true;
+ }
+ }
if (tree_int_cst_equal (op0, tmp))
- return (flags & tf_error) ? RECUR (op1, rval) : false;
+ return RECUR (op1, rval);
else
return true;
}
@@ -9112,17 +9134,6 @@ bool
potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
tsubst_flags_t flags)
{
- if (flags & tf_error)
-{
- /* Check potentiality quietly first, as that could be performed more
-efficiently in some cases (currently only for TRUTH_*_EXPR). If
-that fails, replay the check noisily to give errors. */
- flags &= ~tf_error;
- if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
- return true;
- flags |= tf_error;
-}
-
tree target = NULL_TREE;
return potential_constant_expression_1 (t, want_rval, strict, now,
flags, &target);
(perhaps with naming the 1 << 30 as tf_something or using different bit for
that). So no doubling of potential_constant_expression_1 evaluation
for tf_error unless a TRUTH_*_EXPR is seen outside of template with
potentially constant first operand other than INTEGER_CST, but similarly to
what you did, make sure that there are at most two calls and not more.
> > As I said, another possibility is something like:
> > /* Try to quietly evaluate T to constant, but don't try too hard. */
> >
> > static tree
> > potential_constant_expression_eval (tree t)
> > {
> > auto o = make_temp_override (constexpr_ops_limit,
> >MIN (constexpr_ops_limit, 100));
> > return cxx_eval_outermost_constant_expr (t, true);
> > }
> > and using this new function instead of cxx_eval_outermost_constant_expr
> > (op, true);
> > everywhere in potential_constant_expression_1 should fix the quadraticness
> > too.
>
> This would technically fix the quadraticness but wouldn't it still mean
> that a huge left-associated constant logical expression is quite a bit
> slower to check than an equivalent right-associated one (depending on
> what we set constexp
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Thu, 28 Oct 2021, Jakub Jelinek wrote:
> On Thu, Oct 28, 2021 at 12:40:02PM -0400, Patrick Palka wrote:
> > PR c++/102780
> >
> > gcc/cp/ChangeLog:
> >
> > * constexpr.c (potential_constant_expression_1) :
> > When tf_error isn't set, preemptively check potentiality of the
> > second operand before performing trial evaluation of the first
> > operand.
> > (potential_constant_expression_1): When tf_error is set, first check
> > potentiality quietly and return true if successful, otherwise
> > proceed noisily to give errors.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * g++.dg/cpp1z/fold13.C: New test.
> > ---
> > gcc/cp/constexpr.c | 26 +-
> > gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +
> > 2 files changed, 50 insertions(+), 5 deletions(-)
> > create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C
>
> Is there a reason to turn this mode of evaluating everything twice if an
> error should be diagnosed all the time, rather than only if we actually see
> a TRUTH_*_EXPR we want to handle this way?
> If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
> the first operand is already a constant, that seems like a waste of time.
Hmm yeah, at the very least it wouldn't hurt to check
processing_template_decl before doing the tf_error shenanigans. I'm not
sure if we would gain anything by first looking for TRUTH_*_EXPR since
that'd involve walking the entire expression anyway IIUC.
>
> So, can't we instead drop the second hunk, if processing_template_decl or
> TREE_CODE (op0) == INTEGER_CST do what the code did before, and just
> otherwise if flag & tf_error temporarily clear it, RECUR on op1 first, then
> cxx_eval_outermost_constant_expr and if tree_int_cst_equal RECUR on op1
> the second time with tf_error and some extra flag (1 << 30?) that will mean
> not to
> RECUR on op1 twice in recursive invocations (to avoid bad compile time
> complexity on
> (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x &&
> y
> etc. if x constant evaluates to true and y is not potential constant
> expression.
I considered this approach but I wasn't sure it was worth the added
complexity just to speed up the error case. And the current approach is
already how constraint satisfaction works (it always proceeds quietly
first, and replays the whole thing noisily upon error if tf_error was
set) so there's also a precedence I suppose..
>
> Though, I'm not sure that doing the RECUR (op1, rval) instead of
> cxx_eval_outermost_constant_expr must be generally a win for compile time,
> it can be if op0 is very large expression, but it can be a pessimization if
> op1 is huge and op0 is simple and doesn't constexpr evaluate to tmp.
True, it's not always a win but it seems to me that checking potentiality
of both operands first before doing the trial evaluation gives the most
consistent performance, at least for constant logical expressions.
Recursing on both operands takes time proportional to the size of the
operands, whereas trial evaluation can take arbitrarily long.
>
> As I said, another possibility is something like:
> /* Try to quietly evaluate T to constant, but don't try too hard. */
>
> static tree
> potential_constant_expression_eval (tree t)
> {
> auto o = make_temp_override (constexpr_ops_limit,
> MIN (constexpr_ops_limit, 100));
> return cxx_eval_outermost_constant_expr (t, true);
> }
> and using this new function instead of cxx_eval_outermost_constant_expr (op,
> true);
> everywhere in potential_constant_expression_1 should fix the quadraticness
> too.
This would technically fix the quadraticness but wouldn't it still mean
that a huge left-associated constant logical expression is quite a bit
slower to check than an equivalent right-associated one (depending on
what we set constexpr_ops_limit to)? We should probably do this anyway
anyway but it doesn't seem sufficient on its own to make equivalent
left/right-associated logical expressions have the same performance
behavior IMHO.
>
> > --- a/gcc/cp/constexpr.c
> > +++ b/gcc/cp/constexpr.c
> > @@ -8892,13 +8892,18 @@ potential_constant_expression_1 (tree t, bool
> > want_rval, bool strict, bool now,
> >tmp = boolean_false_node;
> > truth:
> >{
> > - tree op = TREE_OPERAND (t, 0);
> > - if (!RECUR (op, rval))
> > + tree op0 = TREE_OPERAND (t, 0);
> > + tree op1 = TREE_OPERAND (t, 1);
> > + if (!RECUR (op0, rval))
> > return false;
> > + if (!(flags & tf_error) && RECUR (op1, rval))
> > + /* When quiet, try to avoid expensive trial evaluation by first
> > +checking potentiality of the second operand. */
> > + return true;
> > if (!processing_template_decl)
> > - op = cxx_eval_outermost_constant_expr (op, true);
> > - if (tree_int_cst_equal (op, tmp))
> > - return RECUR (TREE_OPERAND (t, 1), rval);
> > +
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Thu, Oct 28, 2021 at 12:40:02PM -0400, Patrick Palka wrote:
> PR c++/102780
>
> gcc/cp/ChangeLog:
>
> * constexpr.c (potential_constant_expression_1) :
> When tf_error isn't set, preemptively check potentiality of the
> second operand before performing trial evaluation of the first
> operand.
> (potential_constant_expression_1): When tf_error is set, first check
> potentiality quietly and return true if successful, otherwise
> proceed noisily to give errors.
>
> gcc/testsuite/ChangeLog:
>
> * g++.dg/cpp1z/fold13.C: New test.
> ---
> gcc/cp/constexpr.c | 26 +-
> gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +
> 2 files changed, 50 insertions(+), 5 deletions(-)
> create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C
Is there a reason to turn this mode of evaluating everything twice if an
error should be diagnosed all the time, rather than only if we actually see
a TRUTH_*_EXPR we want to handle this way?
If we don't see any TRUTH_*_EXPR, or if processing_template_decl, or if
the first operand is already a constant, that seems like a waste of time.
So, can't we instead drop the second hunk, if processing_template_decl or
TREE_CODE (op0) == INTEGER_CST do what the code did before, and just
otherwise if flag & tf_error temporarily clear it, RECUR on op1 first, then
cxx_eval_outermost_constant_expr and if tree_int_cst_equal RECUR on op1
the second time with tf_error and some extra flag (1 << 30?) that will mean not
to
RECUR on op1 twice in recursive invocations (to avoid bad compile time
complexity on
(x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x && (x &&
y
etc. if x constant evaluates to true and y is not potential constant
expression.
Though, I'm not sure that doing the RECUR (op1, rval) instead of
cxx_eval_outermost_constant_expr must be generally a win for compile time,
it can be if op0 is very large expression, but it can be a pessimization if
op1 is huge and op0 is simple and doesn't constexpr evaluate to tmp.
As I said, another possibility is something like:
/* Try to quietly evaluate T to constant, but don't try too hard. */
static tree
potential_constant_expression_eval (tree t)
{
auto o = make_temp_override (constexpr_ops_limit,
MIN (constexpr_ops_limit, 100));
return cxx_eval_outermost_constant_expr (t, true);
}
and using this new function instead of cxx_eval_outermost_constant_expr (op,
true);
everywhere in potential_constant_expression_1 should fix the quadraticness
too.
> --- a/gcc/cp/constexpr.c
> +++ b/gcc/cp/constexpr.c
> @@ -8892,13 +8892,18 @@ potential_constant_expression_1 (tree t, bool
> want_rval, bool strict, bool now,
>tmp = boolean_false_node;
> truth:
>{
> - tree op = TREE_OPERAND (t, 0);
> - if (!RECUR (op, rval))
> + tree op0 = TREE_OPERAND (t, 0);
> + tree op1 = TREE_OPERAND (t, 1);
> + if (!RECUR (op0, rval))
> return false;
> + if (!(flags & tf_error) && RECUR (op1, rval))
> + /* When quiet, try to avoid expensive trial evaluation by first
> + checking potentiality of the second operand. */
> + return true;
> if (!processing_template_decl)
> - op = cxx_eval_outermost_constant_expr (op, true);
> - if (tree_int_cst_equal (op, tmp))
> - return RECUR (TREE_OPERAND (t, 1), rval);
> + op0 = cxx_eval_outermost_constant_expr (op0, true);
> + if (tree_int_cst_equal (op0, tmp))
> + return (flags & tf_error) ? RECUR (op1, rval) : false;
> else
> return true;
>}
> @@ -9107,6 +9112,17 @@ bool
> potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool
> now,
>tsubst_flags_t flags)
> {
> + if (flags & tf_error)
> +{
> + /* Check potentiality quietly first, as that could be performed more
> + efficiently in some cases (currently only for TRUTH_*_EXPR). If
> + that fails, replay the check noisily to give errors. */
> + flags &= ~tf_error;
> + if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
> + return true;
> + flags |= tf_error;
> +}
> +
>tree target = NULL_TREE;
>return potential_constant_expression_1 (t, want_rval, strict, now,
> flags, &target);
Jakub
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
> On 10/27/21 17:10, Patrick Palka wrote: > > On Wed, 27 Oct 2021, Jason Merrill wrote: > > > > > On 10/27/21 14:54, Patrick Palka wrote: > > > > On Tue, 26 Oct 2021, Jakub Jelinek wrote: > > > > > > > > > On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote: > > > > > > The performance impact of the other calls to > > > > > > cxx_eval_outermost_const_expr > > > > > > from p_c_e_1 is probably already mostly mitigated by the constexpr > > > > > > call > > > > > > cache and the fact that we try to evaluate all calls to constexpr > > > > > > functions during cp_fold_function anyway (at least with -O). So > > > > > > trial > > > > > > > > > > constexpr function bodies don't go through cp_fold_function > > > > > (intentionally, > > > > > so that we don't optimize away UB), the bodies are copied before the > > > > > trees > > > > > of the > > > > > normal copy are folded. > > > > > > > > Ah right, I had forgotten about that.. > > > > > > > > Here's another approach that doesn't need to remove trial evaluation for > > > > &&/||. The idea is to first quietly check if the second operand is > > > > potentially constant _before_ performing trial evaluation of the first > > > > operand. This speeds up the case we care about (both operands are > > > > potentially constant) without regressing any diagnostics. We have to be > > > > careful about emitting bogus diagnostics when tf_error is set, hence the > > > > first hunk below which makes p_c_e_1 always proceed quietly first, and > > > > replay noisily in case of error (similar to how satisfaction works). > > > > > > > > Would something like this be preferable? > > > > > > Seems plausible, though doubling the number of stack frames is a downside. > > > > Whoops, good point.. The noisy -> quiet adjustment only needs to > > be performed during the outermost call to p_c_e_1, and not also during > > each recursive call. The revised diff below fixes this thinko, and so > > only a single extra stack frame is needed AFAICT. > > > > > What did you think of Jakub's suggestion of linearizing the terms? > > > > IIUC that would fix the quadraticness, but it wouldn't address that > > we end up evaluating the entire expression twice, once during the trial > > evaluation of each term from p_c_e_1 and again during the proper > > evaluation of the entire expression. It'd be nice if we could somehow > > avoid the double evaluation, as in the approach below (or in the first > > patch). > > OK with more comments to explain the tf_error hijinks. Thanks a lot, here's the complete committed patch for the record: -- >8 -- Subject: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780] In the testcase below the two left fold expressions each expand into a constant logical expression with 1024 terms, for which potential_const_expr takes more than a minute to return true. This happens because p_c_e_1 performs trial evaluation of the first operand of a &&/|| in order to determine whether to consider the potentiality of the second operand. And because the expanded expression is left-associated, this trial evaluation causes p_c_e_1 to be quadratic in the number of terms of the expression. This patch fixes this quadratic behavior by making p_c_e_1 preemptively compute potentiality of the second operand of a &&/||, and perform trial evaluation of the first operand only if the second operand isn't potentially constant. We must be careful to avoid emitting bogus diagnostics during the preemptive computation; to that end, we perform this shortcut only when tf_error is cleared, and when tf_error is set we now first check potentiality of the whole expression quietly and replay the check noisily for diagnostics. Apart from fixing the quadraticness for left-associated logical exprs, this change also reduces compile time for the libstdc++ testcase 20_util/variant/87619.cc by about 15% even though our uses right folds instead of left folds. Likewise for the testcase in the PR, for which compile time is reduced by 30%. The reason for these speedups is that p_c_e_1 no longer performs expensive trial evaluation of each term of large constant logical expressions when determining their potentiality. PR c++/102780 gcc/cp/ChangeLog: * constexpr.c (potential_constant_expression_1) : When tf_error isn't set, preemptively check potentiality of the second operand before performing trial evaluation of the first operand. (potential_constant_expression_1): When tf_error is set, first check potentiality quietly and return true if successful, otherwise proceed noisily to give errors. gcc/testsuite/ChangeLog: * g++.dg/cpp1z/fold13.C: New test. --- gcc/cp/constexpr.c | 26 +- gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 + 2 files changed, 50 insertions(+), 5 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On 10/27/21 17:10, Patrick Palka wrote:
On Wed, 27 Oct 2021, Jason Merrill wrote:
On 10/27/21 14:54, Patrick Palka wrote:
On Tue, 26 Oct 2021, Jakub Jelinek wrote:
On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
The performance impact of the other calls to
cxx_eval_outermost_const_expr
from p_c_e_1 is probably already mostly mitigated by the constexpr call
cache and the fact that we try to evaluate all calls to constexpr
functions during cp_fold_function anyway (at least with -O). So trial
constexpr function bodies don't go through cp_fold_function
(intentionally,
so that we don't optimize away UB), the bodies are copied before the trees
of the
normal copy are folded.
Ah right, I had forgotten about that..
Here's another approach that doesn't need to remove trial evaluation for
&&/||. The idea is to first quietly check if the second operand is
potentially constant _before_ performing trial evaluation of the first
operand. This speeds up the case we care about (both operands are
potentially constant) without regressing any diagnostics. We have to be
careful about emitting bogus diagnostics when tf_error is set, hence the
first hunk below which makes p_c_e_1 always proceed quietly first, and
replay noisily in case of error (similar to how satisfaction works).
Would something like this be preferable?
Seems plausible, though doubling the number of stack frames is a downside.
Whoops, good point.. The noisy -> quiet adjustment only needs to
be performed during the outermost call to p_c_e_1, and not also during
each recursive call. The revised diff below fixes this thinko, and so
only a single extra stack frame is needed AFAICT.
What did you think of Jakub's suggestion of linearizing the terms?
IIUC that would fix the quadraticness, but it wouldn't address that
we end up evaluating the entire expression twice, once during the trial
evaluation of each term from p_c_e_1 and again during the proper
evaluation of the entire expression. It'd be nice if we could somehow
avoid the double evaluation, as in the approach below (or in the first
patch).
OK with more comments to explain the tf_error hijinks.
-- >8 --
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1): When tf_error is
set, proceed quietly first and return true if successful.
: When tf_error is not set, check potentiality
of the second operand before performing trial evaluation of the
first operand rather than after.
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..7855a948baf 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8892,13 +8892,16 @@ potential_constant_expression_1 (tree t, bool
want_rval, bool strict, bool now,
tmp = boolean_false_node;
truth:
{
- tree op = TREE_OPERAND (t, 0);
- if (!RECUR (op, rval))
+ tree op0 = TREE_OPERAND (t, 0);
+ tree op1 = TREE_OPERAND (t, 1);
+ if (!RECUR (op0, rval))
return false;
+ if (!(flags & tf_error) && RECUR (op1, rval))
+ return true;
if (!processing_template_decl)
- op = cxx_eval_outermost_constant_expr (op, true);
- if (tree_int_cst_equal (op, tmp))
- return RECUR (TREE_OPERAND (t, 1), rval);
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (tree_int_cst_equal (op0, tmp))
+ return (flags & tf_error) ? RECUR (op1, rval) : false;
else
return true;
}
@@ -9107,6 +9110,14 @@ bool
potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool
now,
tsubst_flags_t flags)
{
+ if (flags & tf_error)
+{
+ flags &= ~tf_error;
+ if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
+ return true;
+ flags |= tf_error;
+}
+
tree target = NULL_TREE;
return potential_constant_expression_1 (t, want_rval, strict, now,
flags, &target);
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Wed, 27 Oct 2021, Jason Merrill wrote:
> On 10/27/21 14:54, Patrick Palka wrote:
> > On Tue, 26 Oct 2021, Jakub Jelinek wrote:
> >
> > > On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> > > > The performance impact of the other calls to
> > > > cxx_eval_outermost_const_expr
> > > > from p_c_e_1 is probably already mostly mitigated by the constexpr call
> > > > cache and the fact that we try to evaluate all calls to constexpr
> > > > functions during cp_fold_function anyway (at least with -O). So trial
> > >
> > > constexpr function bodies don't go through cp_fold_function
> > > (intentionally,
> > > so that we don't optimize away UB), the bodies are copied before the trees
> > > of the
> > > normal copy are folded.
> >
> > Ah right, I had forgotten about that..
> >
> > Here's another approach that doesn't need to remove trial evaluation for
> > &&/||. The idea is to first quietly check if the second operand is
> > potentially constant _before_ performing trial evaluation of the first
> > operand. This speeds up the case we care about (both operands are
> > potentially constant) without regressing any diagnostics. We have to be
> > careful about emitting bogus diagnostics when tf_error is set, hence the
> > first hunk below which makes p_c_e_1 always proceed quietly first, and
> > replay noisily in case of error (similar to how satisfaction works).
> >
> > Would something like this be preferable?
>
> Seems plausible, though doubling the number of stack frames is a downside.
Whoops, good point.. The noisy -> quiet adjustment only needs to
be performed during the outermost call to p_c_e_1, and not also during
each recursive call. The revised diff below fixes this thinko, and so
only a single extra stack frame is needed AFAICT.
>
> What did you think of Jakub's suggestion of linearizing the terms?
IIUC that would fix the quadraticness, but it wouldn't address that
we end up evaluating the entire expression twice, once during the trial
evaluation of each term from p_c_e_1 and again during the proper
evaluation of the entire expression. It'd be nice if we could somehow
avoid the double evaluation, as in the approach below (or in the first
patch).
-- >8 --
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1): When tf_error is
set, proceed quietly first and return true if successful.
: When tf_error is not set, check potentiality
of the second operand before performing trial evaluation of the
first operand rather than after.
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..7855a948baf 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8892,13 +8892,16 @@ potential_constant_expression_1 (tree t, bool
want_rval, bool strict, bool now,
tmp = boolean_false_node;
truth:
{
- tree op = TREE_OPERAND (t, 0);
- if (!RECUR (op, rval))
+ tree op0 = TREE_OPERAND (t, 0);
+ tree op1 = TREE_OPERAND (t, 1);
+ if (!RECUR (op0, rval))
return false;
+ if (!(flags & tf_error) && RECUR (op1, rval))
+ return true;
if (!processing_template_decl)
- op = cxx_eval_outermost_constant_expr (op, true);
- if (tree_int_cst_equal (op, tmp))
- return RECUR (TREE_OPERAND (t, 1), rval);
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (tree_int_cst_equal (op0, tmp))
+ return (flags & tf_error) ? RECUR (op1, rval) : false;
else
return true;
}
@@ -9107,6 +9110,14 @@ bool
potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now,
tsubst_flags_t flags)
{
+ if (flags & tf_error)
+{
+ flags &= ~tf_error;
+ if (potential_constant_expression_1 (t, want_rval, strict, now, flags))
+ return true;
+ flags |= tf_error;
+}
+
tree target = NULL_TREE;
return potential_constant_expression_1 (t, want_rval, strict, now,
flags, &target);
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On 10/27/21 14:54, Patrick Palka wrote:
On Tue, 26 Oct 2021, Jakub Jelinek wrote:
On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
The performance impact of the other calls to cxx_eval_outermost_const_expr
from p_c_e_1 is probably already mostly mitigated by the constexpr call
cache and the fact that we try to evaluate all calls to constexpr
functions during cp_fold_function anyway (at least with -O). So trial
constexpr function bodies don't go through cp_fold_function (intentionally,
so that we don't optimize away UB), the bodies are copied before the trees of
the
normal copy are folded.
Ah right, I had forgotten about that..
Here's another approach that doesn't need to remove trial evaluation for
&&/||. The idea is to first quietly check if the second operand is
potentially constant _before_ performing trial evaluation of the first
operand. This speeds up the case we care about (both operands are
potentially constant) without regressing any diagnostics. We have to be
careful about emitting bogus diagnostics when tf_error is set, hence the
first hunk below which makes p_c_e_1 always proceed quietly first, and
replay noisily in case of error (similar to how satisfaction works).
Would something like this be preferable?
Seems plausible, though doubling the number of stack frames is a downside.
What did you think of Jakub's suggestion of linearizing the terms?
-- >8 --
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1): When tf_error is
set, proceed quietly first and return true if successful.
: When tf_error is not set, check potentiality
of the second operand before performing trial evaluation of the
first operand rather than after.
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..821bd41d994 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8056,6 +8056,14 @@ potential_constant_expression_1 (tree t, bool want_rval,
bool strict, bool now,
#define RECUR(T,RV) \
potential_constant_expression_1 ((T), (RV), strict, now, flags, jump_target)
+ if (flags & tf_error)
+{
+ flags &= ~tf_error;
+ if (RECUR (t, want_rval))
+ return true;
+ flags |= tf_error;
+}
+
enum { any = false, rval = true };
int i;
tree tmp;
@@ -8892,13 +8900,16 @@ potential_constant_expression_1 (tree t, bool
want_rval, bool strict, bool now,
tmp = boolean_false_node;
truth:
{
- tree op = TREE_OPERAND (t, 0);
- if (!RECUR (op, rval))
+ tree op0 = TREE_OPERAND (t, 0);
+ tree op1 = TREE_OPERAND (t, 1);
+ if (!RECUR (op0, rval))
return false;
+ if (!(flags & tf_error) && RECUR (op1, rval))
+ return true;
if (!processing_template_decl)
- op = cxx_eval_outermost_constant_expr (op, true);
- if (tree_int_cst_equal (op, tmp))
- return RECUR (TREE_OPERAND (t, 1), rval);
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (tree_int_cst_equal (op0, tmp))
+ return (flags & tf_error) ? RECUR (op1, rval) : false;
else
return true;
}
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, 26 Oct 2021, Jakub Jelinek wrote:
> On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote:
> > The performance impact of the other calls to cxx_eval_outermost_const_expr
> > from p_c_e_1 is probably already mostly mitigated by the constexpr call
> > cache and the fact that we try to evaluate all calls to constexpr
> > functions during cp_fold_function anyway (at least with -O). So trial
>
> constexpr function bodies don't go through cp_fold_function (intentionally,
> so that we don't optimize away UB), the bodies are copied before the trees of
> the
> normal copy are folded.
Ah right, I had forgotten about that..
Here's another approach that doesn't need to remove trial evaluation for
&&/||. The idea is to first quietly check if the second operand is
potentially constant _before_ performing trial evaluation of the first
operand. This speeds up the case we care about (both operands are
potentially constant) without regressing any diagnostics. We have to be
careful about emitting bogus diagnostics when tf_error is set, hence the
first hunk below which makes p_c_e_1 always proceed quietly first, and
replay noisily in case of error (similar to how satisfaction works).
Would something like this be preferable?
-- >8 --
gcc/cp/ChangeLog:
* constexpr.c (potential_constant_expression_1): When tf_error is
set, proceed quietly first and return true if successful.
: When tf_error is not set, check potentiality
of the second operand before performing trial evaluation of the
first operand rather than after.
diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c
index 6f83d303cdd..821bd41d994 100644
--- a/gcc/cp/constexpr.c
+++ b/gcc/cp/constexpr.c
@@ -8056,6 +8056,14 @@ potential_constant_expression_1 (tree t, bool want_rval,
bool strict, bool now,
#define RECUR(T,RV) \
potential_constant_expression_1 ((T), (RV), strict, now, flags, jump_target)
+ if (flags & tf_error)
+{
+ flags &= ~tf_error;
+ if (RECUR (t, want_rval))
+ return true;
+ flags |= tf_error;
+}
+
enum { any = false, rval = true };
int i;
tree tmp;
@@ -8892,13 +8900,16 @@ potential_constant_expression_1 (tree t, bool
want_rval, bool strict, bool now,
tmp = boolean_false_node;
truth:
{
- tree op = TREE_OPERAND (t, 0);
- if (!RECUR (op, rval))
+ tree op0 = TREE_OPERAND (t, 0);
+ tree op1 = TREE_OPERAND (t, 1);
+ if (!RECUR (op0, rval))
return false;
+ if (!(flags & tf_error) && RECUR (op1, rval))
+ return true;
if (!processing_template_decl)
- op = cxx_eval_outermost_constant_expr (op, true);
- if (tree_int_cst_equal (op, tmp))
- return RECUR (TREE_OPERAND (t, 1), rval);
+ op0 = cxx_eval_outermost_constant_expr (op0, true);
+ if (tree_int_cst_equal (op0, tmp))
+ return (flags & tf_error) ? RECUR (op1, rval) : false;
else
return true;
}
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, Oct 26, 2021 at 05:07:43PM -0400, Patrick Palka wrote: > The performance impact of the other calls to cxx_eval_outermost_const_expr > from p_c_e_1 is probably already mostly mitigated by the constexpr call > cache and the fact that we try to evaluate all calls to constexpr > functions during cp_fold_function anyway (at least with -O). So trial constexpr function bodies don't go through cp_fold_function (intentionally, so that we don't optimize away UB), the bodies are copied before the trees of the normal copy are folded. Jakub
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, 26 Oct 2021, Jason Merrill wrote: > On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches > wrote: > On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches > wrote: > > In the testcase below the two left fold expressions each expand into a > > logical expression with 1024 terms, for which potential_const_expr_1 > > takes more than a minute to return true. This is because p_c_e_1 > > performs trial evaluation of the first operand of a &&/|| in order to > > determine whether to consider its second operand. And because the > > expanded expression is left-associated, this trial evaluation causes > > p_c_e_1 to be quadratic in the number of terms of the expression. > > > > This patch fixes this quadratic behavior by making p_c_e_1 recurse > only > > into the first operand of a &&/|| when checking for potentiality. > This > > means we'll consider more non-constant expressions as potentially > > constant compared to the trial evaluation approach, but that should be > > harmless as later constexpr evaluation of the expression will deem it > > non-constant anyway. > > > Fair, especially now that it seems that C++23 is removing the diagnostic for > a constexpr function that can't produce a constant expression. And as more > functions become constexpr, the trial evaluation gets > more expensive to get to the point of failure. I wonder if we want to stop > calling cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only > check whether the operand is already constant. The performance impact of the other calls to cxx_eval_outermost_const_expr from p_c_e_1 is probably already mostly mitigated by the constexpr call cache and the fact that we try to evaluate all calls to constexpr functions during cp_fold_function anyway (at least with -O). So trial evaluation of e.g. the condition of a for/while loop that contains an expensive constexpr call shouldn't cause the compiler to perform more work overall IIUC. > > For very large && or || expressions (but not mixed or with ! etc.) > another > possibility would be to check if the lhs or rhs have the same code and > if > so, linearize the trees and recurse only on the leafs (trees with other > TREE_CODE) and stop when first expression isn't equal to tmp. > > > This would be good if we wanted to keep the evaluation. > > Jason > >
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, Oct 26, 2021 at 03:29:02PM -0400, Jason Merrill wrote: > On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches < > gcc-patches@gcc.gnu.org> wrote: > > > On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches > > wrote: > > > In the testcase below the two left fold expressions each expand into a > > > logical expression with 1024 terms, for which potential_const_expr_1 > > > takes more than a minute to return true. This is because p_c_e_1 > > > performs trial evaluation of the first operand of a &&/|| in order to > > > determine whether to consider its second operand. And because the > > > expanded expression is left-associated, this trial evaluation causes > > > p_c_e_1 to be quadratic in the number of terms of the expression. > > > > > > This patch fixes this quadratic behavior by making p_c_e_1 recurse only > > > into the first operand of a &&/|| when checking for potentiality. This > > > means we'll consider more non-constant expressions as potentially > > > constant compared to the trial evaluation approach, but that should be > > > harmless as later constexpr evaluation of the expression will deem it > > > non-constant anyway. > > > > Fair, especially now that it seems that C++23 is removing the diagnostic > for a constexpr function that can't produce a constant expression. And as > more functions become constexpr, the trial evaluation gets more expensive > to get to the point of failure. I wonder if we want to stop calling > cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check > whether the operand is already constant. That would make p_c_e_1 surely much faster, but on the other side we would stop diagnosing some functions that can't be valid constant expressions no matter with what arguments they are called. Another option would be to do these cxx_eval_outermost_constant_expression calls from p_c_e_1 only in a cheap mode, i.e. with constexpr_ops_limit temporarily lowered to something very small, 100-ish or 1000-ish or so, so it would handle small expressions like before, but would quietly punt on large expressions. Jakub
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, Oct 26, 2021 at 2:46 PM Jakub Jelinek via Gcc-patches < gcc-patches@gcc.gnu.org> wrote: > On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches > wrote: > > In the testcase below the two left fold expressions each expand into a > > logical expression with 1024 terms, for which potential_const_expr_1 > > takes more than a minute to return true. This is because p_c_e_1 > > performs trial evaluation of the first operand of a &&/|| in order to > > determine whether to consider its second operand. And because the > > expanded expression is left-associated, this trial evaluation causes > > p_c_e_1 to be quadratic in the number of terms of the expression. > > > > This patch fixes this quadratic behavior by making p_c_e_1 recurse only > > into the first operand of a &&/|| when checking for potentiality. This > > means we'll consider more non-constant expressions as potentially > > constant compared to the trial evaluation approach, but that should be > > harmless as later constexpr evaluation of the expression will deem it > > non-constant anyway. > Fair, especially now that it seems that C++23 is removing the diagnostic for a constexpr function that can't produce a constant expression. And as more functions become constexpr, the trial evaluation gets more expensive to get to the point of failure. I wonder if we want to stop calling cxx_eval_outermost_constant_expression from pot_c_e_1 entirely, only check whether the operand is already constant. For very large && or || expressions (but not mixed or with ! etc.) another > possibility would be to check if the lhs or rhs have the same code and if > so, linearize the trees and recurse only on the leafs (trees with other > TREE_CODE) and stop when first expression isn't equal to tmp. > This would be good if we wanted to keep the evaluation. Jason
Re: [PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]
On Tue, Oct 26, 2021 at 01:44:18PM -0400, Patrick Palka via Gcc-patches wrote: > In the testcase below the two left fold expressions each expand into a > logical expression with 1024 terms, for which potential_const_expr_1 > takes more than a minute to return true. This is because p_c_e_1 > performs trial evaluation of the first operand of a &&/|| in order to > determine whether to consider its second operand. And because the > expanded expression is left-associated, this trial evaluation causes > p_c_e_1 to be quadratic in the number of terms of the expression. > > This patch fixes this quadratic behavior by making p_c_e_1 recurse only > into the first operand of a &&/|| when checking for potentiality. This > means we'll consider more non-constant expressions as potentially > constant compared to the trial evaluation approach, but that should be > harmless as later constexpr evaluation of the expression will deem it > non-constant anyway. For very large && or || expressions (but not mixed or with ! etc.) another possibility would be to check if the lhs or rhs have the same code and if so, linearize the trees and recurse only on the leafs (trees with other TREE_CODE) and stop when first expression isn't equal to tmp. For mixed &&/|| or with ! that could still be expensive though. Jakub
