https://gcc.gnu.org/bugzilla/show_bug.cgi?id=126603
Bug ID: 126603
Summary: Compile time hog in cse reciprocals
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: ---
/* Compile-time hog: the occurrence-tree build in the "gimple CSE reciprocals"
pass is quadratic in the number of sibling blocks that divide by the same
SSA name.
gcc -O1 -freciprocal-math -ftime-report -S t.c
Compile with -DLOG4N=5 (1024 arms), -DLOG4N=6 (4096) or the default
-DLOG4N=7 (16384) to see the scaling.
Observed, reading the "gimple CSE reciprocals" line of -ftime-report:
LOG4N=5 0.01s 5% of a 0.26s compile
LOG4N=6 0.22s 17% of a 1.33s compile
LOG4N=7 3.97s 36% of a 10.94s compile
At LOG4N=7 it is the second-largest single entry in the report, behind RTL
CSE. A separate series with N = 1000/2000/4000/8000/16000 distinct case
arms shows 0.01 / 0.05 / 0.21 / 0.89 / 3.86s at -O2, i.e. exactly 4x per
doubling of N. Expected: linear, or at least not the fastest-growing term
in the compile.
Mechanism. register_division_in (tree-ssa-math-opts.cc:307) calls insert_bb
(:243) once per basic block that divides by DEF. insert_bb walks the entire
sibling list at the current dominator level and calls
nearest_common_dominator for every element before appending. When the N
division blocks are all immediate siblings under one dominator, as in a flat
switch, the k-th insertion walks k-1 siblings, so the build costs O(N^2)
nearest_common_dominator calls. There is no cap and no early exit. The
tree is also built before the profitability test at :831
(count + square_recip_count >= threshold), so unprofitable functions pay for
it too.
Attribution. perf on the LOG4N=7 compile names
nearest_common_dominator (1.80% of all cycles) and insert_bb (0.36%) and no
other recip symbol. Control experiment: replacing "1.0 / x" by
"1.0 / (x + <arm index>)", so that each divisor is a distinct SSA name with
a one-element occurrence list, makes the "gimple CSE reciprocals" line drop
below the -ftime-report threshold entirely at N=8000, where the shared
divisor costs 1.05s. */
#ifndef LOG4N
#define LOG4N 7
#endif
#define D1(i) case i: p[i] = 1.0 / x; break;
#define D4(i) D1(i) D1(i+1) D1(i+2) D1(i+3)
#define D16(i) D4(i) D4(i+4) D4(i+8) D4(i+12)
#define D64(i) D16(i) D16(i+16) D16(i+32) D16(i+48)
#define D256(i) D64(i) D64(i+64) D64(i+128) D64(i+192)
#define D1K(i) D256(i) D256(i+256) D256(i+512) D256(i+768)
#define D4K(i) D1K(i) D1K(i+1024) D1K(i+2048) D1K(i+3072)
#define D16K(i) D4K(i) D4K(i+4096) D4K(i+8192) D4K(i+12288)
#if LOG4N == 5
#define BODY D1K(0)
#elif LOG4N == 6
#define BODY D4K(0)
#else
#define BODY D16K(0)
#endif
double f (double x, int n, double *p)
{
switch (n)
{
BODY
default: break;
}
return x;
}
