[PATCH] c++: quadratic constexpr behavior for left-assoc logical exprs [PR102780]

[Jason Merrill]

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.
> 	<case TRUTH_*_EXPR>: 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;
>         }
>