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) <case TRUTH_*_EXPR>:
> > 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);
> > + 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
>
>
