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

[Jason Merrill <jason@redhat.com>]

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