[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 --- Comment #7 from GCC Commits --- The master branch has been updated by Patrick Palka : https://gcc.gnu.org/g:e71c0157478e49188cd754693dcc2059d63573e9 commit r16-1187-ge71c0157478e49188cd754693dcc2059d63573e9 Author: Patrick Palka Date: Thu Jun 5 11:06:04 2025 -0400 c++: quadratic constexpr folding of arith expr [PR118340] Here the PR's testcase demonstrates that the cp_fully_fold calls in cp_build_binary_op (for diagnosing arithmetic overflow) lead to quadratic behavior when building up a large arithmetic constant expression. The problem is ultimately that maybe_constant_value's caching doesn't reuse intermediate values, unlike cp_fold. (And unfortunately we can't leverage the cp_fold cache in this call site because here we want to evaluate constexpr calls even in -O0, which cp_fold avoids.) This patch fixes this by making maybe_constant_value look up each operand of the given expression to see if we've previously reduced it, and if so, rebuild the expression using the (presumably) reduced operands and evaluate that. After this patch each version of the testcase from the PR compiles in ~0.1s on my machine. PR c++/118340 gcc/cp/ChangeLog: * constexpr.cc (maybe_constant_value): First try looking up each operand in the cv_cache and reusing the result. Reviewed-by: Jason Merrill
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 Patrick Palka changed: What|Removed |Added Resolution|--- |FIXED Status|ASSIGNED|RESOLVED --- Comment #8 from Patrick Palka --- Should be fixed for GCC 16, thanks for the bug report.
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 Patrick Palka changed: What|Removed |Added Assignee|unassigned at gcc dot gnu.org |ppalka at gcc dot gnu.org Status|NEW |ASSIGNED Target Milestone|--- |16.0
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 --- Comment #6 from Jason Merrill --- (In reply to Patrick Palka from comment #5) > FWIW disabling the block containing the cp_fully_fold calls breaks > g++.dg/cpp0x/warn-ovl2.C and g++.dg/warn/multiple-overflow-warn-3.C, > unsurprisingly. > > We can't leverage the fold_cache here because cp_fold only evaluates > constexpr calls if !flag_no_inline, but here we want to evaluate calls even > at -O0. And we can't leverage the cv_cache either because it's not > recursive. Perhaps cv_cache should cache intermediate values that are themselves constant-expressions, or at least look up intermediate values that might have previously been passed to maybe_constant_value, as in this case. Incidentally, it seems like some of those cp_fully_fold calls should instead be fold_for_warn?
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 --- Comment #5 from Patrick Palka --- FWIW disabling the block containing the cp_fully_fold calls breaks g++.dg/cpp0x/warn-ovl2.C and g++.dg/warn/multiple-overflow-warn-3.C, unsurprisingly. We can't leverage the fold_cache here because cp_fold only evaluates constexpr calls if !flag_no_inline, but here we want to evaluate calls even at -O0. And we can't leverage the cv_cache either because it's not recursive.
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 Patrick Palka changed: What|Removed |Added CC||jason at gcc dot gnu.org --- Comment #4 from Patrick Palka --- Unlike the PR102780 ||/&& quadraticness fix, which was during potential_constant_expression checking, the quadraticness in this case seems to happen during building up the expression from cp_build_binary_op which near the end calls cp_fully_fold on both operands (for sake of overflow checking?), which is >=linear in the size of each operand, so >=quadratic overall. Not sure how to fix this safely.
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 Richard Biener changed: What|Removed |Added CC||ppalka at gcc dot gnu.org --- Comment #3 from Richard Biener --- CCing author of || fix
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340
Andrew Pinski changed:
What|Removed |Added
Status|UNCONFIRMED |NEW
Ever confirmed|0 |1
Last reconfirmed||2025-01-08
--- Comment #2 from Andrew Pinski ---
Reduced to (this assumes the front-end in testing has either __integer_pack or
__make_integer_seq):
```
template struct integer_sequence { };
template
using make_integer_sequence
#if __has_builtin(__make_integer_seq)
= __make_integer_seq;
#else
= integer_sequence;
#endif
#ifdef FAST
template
static constexpr int v1 = ((i != 0) || ...); // fast
#else
template
static constexpr int v1 = ((i != 0) | ...); // slow
#endif
template
constexpr int foo(integer_sequence)
{
return v1;
}
int main()
{
static_assert(1 == foo(make_integer_sequence{}));
}
```
Confirmed. What is interesting if we use `||` instead of `|`, it is fast. This
makes sense since PR 102780 fixed the `||` case but not the |, +, extra cases.
[Bug c++/118340] fold expression is very slow to compile when used to initialize a variable
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118340 --- Comment #1 from Andrew Pinski --- Time variable usr sys wall GGC phase setup: 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 1911k ( 18%) phase parsing : 4.22 (100%) 0.09 (100%) 4.38 ( 99%) 6886k ( 65%) phase opt and generate : 0.02 ( 0%) 0.00 ( 0%) 0.02 ( 0%) 1830k ( 17%) |name lookup : 0.01 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 421k ( 4%) |overload resolution : 4.14 ( 98%) 0.05 ( 56%) 4.27 ( 97%) 1608k ( 15%) callgraph construction : 0.01 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 1775k ( 17%) preprocessing : 0.02 ( 0%) 0.02 ( 22%) 0.02 ( 0%) 499k ( 5%) parser (global): 0.03 ( 1%) 0.00 ( 0%) 0.03 ( 1%) 1470k ( 14%) parser struct body : 0.01 ( 0%) 0.02 ( 22%) 0.03 ( 1%) 1209k ( 11%) template instantiation : 0.55 ( 13%) 0.00 ( 0%) 0.60 ( 14%) 2898k ( 27%) constant expression evaluation : 3.61 ( 85%) 0.05 ( 56%) 3.69 ( 84%) 259k ( 2%) symout : 0.00 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 280k ( 3%) initialize rtl : 0.01 ( 0%) 0.00 ( 0%) 0.01 ( 0%) 12k ( 0%) TOTAL : 4.24 0.09 4.41 10M Compiler returned: 0
