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
