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.
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.
For mixed &&/|| or with ! that could still be expensive though.
Jakub
