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. As a nice bonus, this change also reduces compile time for the libstdc++ testcase 20_util/variant/87619.cc by about 15%, even though our <variant> uses right folds instead of left folds. Likewise for the testcase in the PR, for which compile time is reduced by 30%. Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for trunk? PR c++/102780 gcc/cp/ChangeLog: * constexpr.c (potential_constant_expression_1) <case TRUTH_*_EXPR>: Only recurse into the first operand, and ignore the second. gcc/testsuite/ChangeLog: * g++.dg/cpp1z/fold13.C: New test. --- gcc/cp/constexpr.c | 21 +++------------------ gcc/testsuite/g++.dg/cpp1z/fold13.C | 29 +++++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 18 deletions(-) create mode 100644 gcc/testsuite/g++.dg/cpp1z/fold13.C diff --git a/gcc/cp/constexpr.c b/gcc/cp/constexpr.c index 6f83d303cdd..9fd2c403afb 100644 --- a/gcc/cp/constexpr.c +++ b/gcc/cp/constexpr.c @@ -8880,28 +8880,13 @@ potential_constant_expression_1 (tree t, bool want_rval, bool strict, bool now, goto binary; } - /* If the first operand is the non-short-circuit constant, look at - the second operand; otherwise we only care about the first one for - potentiality. */ case TRUTH_AND_EXPR: case TRUTH_ANDIF_EXPR: - tmp = boolean_true_node; - goto truth; case TRUTH_OR_EXPR: case TRUTH_ORIF_EXPR: - tmp = boolean_false_node; - truth: - { - tree op = TREE_OPERAND (t, 0); - if (!RECUR (op, rval)) - return false; - 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); - else - return true; - } + /* Only look at the first operand for potentiality since the second + operand may be irrelevant if the first short circuits. */ + return RECUR (TREE_OPERAND (t, 0), rval); case PLUS_EXPR: case MULT_EXPR: diff --git a/gcc/testsuite/g++.dg/cpp1z/fold13.C b/gcc/testsuite/g++.dg/cpp1z/fold13.C new file mode 100644 index 00000000000..b2b8c954be9 --- /dev/null +++ b/gcc/testsuite/g++.dg/cpp1z/fold13.C @@ -0,0 +1,29 @@ +// { dg-do compile { target c++17 } } +// Verify constexpr evaluation of a large left fold logical expression +// isn't quadratic in the size of the expanded expression. + +template<int> struct S { static constexpr bool value = true; }; + +template<typename T, T...> struct integer_sequence { }; + +template<typename T, T N> + using make_integer_sequence +#if __has_builtin(__make_integer_seq) + = __make_integer_seq<integer_sequence, T, N>; +#else + = integer_sequence<T, __integer_pack(N)...>; +#endif + +template<int... Is> +constexpr bool f_impl(integer_sequence<int, Is...>) { + return (... && S<Is>::value); +} + +static_assert(f_impl(make_integer_sequence<int, 1024>())); + +template<int... Is> +constexpr bool g_impl(integer_sequence<int, Is...>) { + return (... || !S<Is>::value); +} + +static_assert(!g_impl(make_integer_sequence<int, 1024>())); -- 2.33.1.711.g9d530dc002