https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126538
Bug ID: 126538
Summary: Compile time hog with gimple-range-phi and bitint
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Keywords: compile-time-hog
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: ktkachov at gcc dot gnu.org
Target Milestone: ---
/* Entry point: phi_group::calculate_using_modifier,
gcc/gimple-range-phi.cc:167
num_iter = TYPE_PRECISION (m_vr.type ()) + 1;
This is NOT a wrong-code case: the range that comes out is correct. It is a
compile-time explosion. The iteration budget is the precision of the group
type, and each iteration folds the modifier over an int_range_max of that
same precision, so the cost is cubic in the precision. _BitInt allows
65535 bits, and this ten-line function then needs about 41000 iterations of
a 65535-bit multiply.
gcc -O2 -c phigrp-02-bitint-iteration-hog.c 167 s
gcc -O1 -c ... 0.02 s (no ranger
vrp)
gcc -O2 -fno-tree-vrp -c ... 0.8 s
x = x + 3 instead of x * 3, -O2 0.44 s (PLUS skips
the iteration)
Scaling of the -O2 time with the precision, one function per file:
512 0.02 1024 0.04 2048 0.08 4096 0.18 8192 0.63
16384 3.5 32768 22.8 65535 167.
Dump evidence, at precision 16384 so the dump is quick:
PHI ANALYZER : New PHI GROUP < x_1 > : range : [irange] T [1, 1][3, +INF]
Modifier : x_8 = x_1 * 3;
Initial range was [irange] T [1, 1] */
typedef _BitInt(65535) T;
__attribute__((noipa)) T
f (int n)
{
T x = 1;
for (int i = 0; i < n; i++)
x = x * 3;
return x;
}
int
main (void)
{
return (int) f (2) - 9;
}
