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