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

[Patrick Palka]

On Tue, 26 Oct 2021, 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.

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
> 
>