https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128082
Bug ID: 128082
Summary: Compile-time hog in fre1 at -O2 on a loop header with
many latch edges (switch dispatch loop)
Product: gcc
Version: 17.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: lyfanyang at smail dot nju.edu.cn
Target Milestone: ---
Created attachment 65919
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65919&action=edit
`fre-hog.c`: testcase (V=100, N=800)
## Description
At -O2 and -O3, early FRE (fre1) takes a long time on a `while (1) { switch
(state) ... }` dispatch loop where every case jumps directly back to the loop
header. The loop header then has one incoming edge per case, and one PHI per
local that the loop modifies. At -O1 the same pass is fast.
The attached `fre-hog.c` (1014 lines, generated) has 100 `unsigned` locals and
800 cases. Each case does one copy, constant store, or simple arithmetic on the
locals, then sets `state`. The program has no undefined behavior (it is clean
under `-fsanitize=address,undefined`) and prints the same checksum at -O0
through -O3.
```
$ gcc -O1 -c fre-hog.c # 2.5 s
$ gcc -O2 -c fre-hog.c # 36.1 s
$ gcc -O3 -c fre-hog.c # 36.5 s
$ gcc -O2 -fno-tree-fre -c fre-hog.c # 3.7 s
$ gcc -O2 -fdisable-tree-fre1 -c fre-hog.c # 3.5 s
```
(trunk 20261018 configured with `--enable-checking=yes`.)
`-ftime-report` at -O2:
```
tree FRE : 32.47 ( 93%)
TOTAL : 35.07
```
## The latch shape is what triggers it
The attached `fre-hog-single.c` differs from `fre-hog.c` in one line only. The
iteration counter check moves from before the switch to after it:
```c
/* fre-hog.c: every case's break goes straight to the loop header (800 latches)
*/
while (1) {
if (++cnt == 100000u) break;
switch (state) { case 0: ...; break; ... }
}
/* fre-hog-single.c: cases join after the switch, one latch */
while (1) {
switch (state) { case 0: ...; break; ... }
if (++cnt == 100000u) break;
}
```
`fre-hog-single.c` compiles at -O2 in 3.1 s on trunk, with FRE at about 0.2 s.
## FRE statistics (`-fdump-statistics-stats`, trunk)
| | RPO blocks | RPO blocks visited | visits per block |
|---|---|---|---|
| fre1, -O1 | 1205 | 1205 | 1.0 |
| fre1, -O2 | 1205 | 18138 | 15.0 |
At -O2, fre1 iterates (`iterate_p = may_iterate && (optimize > 1)` in
`pass_fre::execute`). Each visit of the loop header re-processes every header
PHI, and each PHI has one argument per case. Sampling cc1 with gdb on a larger
input shows almost all of the time in `visit_phi` (called from `do_rpo_vn_1`)
on the loop header PHIs.
## Scaling
The attached `gen_fre.py` generates the testcase. `-V` is the number of locals,
`-N` the number of cases, and `--latch single` gives the single-latch variant
(`fre-hog.c` is `gen_fre.py -V 100 -N 800`).
Below is the `tree FRE` time in seconds at -O2 on trunk 20261018:
| V \ N | 100 | 200 | 400 | 800 |
|---|---|---|---|---|
| 50 | 0.3 | 1.0 | 3.6 | 7.7 |
| 100 | 0.5 | 5.6 | 15.6 | 45 |
| 200 | 0.6 | 6.8 | 51 | 214 |
| 400 | 0.8 | 11 | 105 | 729 |
A least-squares fit over the points of at least 1 s gives roughly **V^1.7 ·
N^2.2**. The fits for 9.4.0 (V^1.77 · N^2.21) and 16.2.0 (V^1.78 · N^2.28) are
similar. For V=400, N=800:
| | -O1 total | -O2 total | -O2 FRE | -O2, single latch |
|---|---|---|---|---|
| 9.4.0 | 2.2 s | 399 s | 395 s | 4.5 s |
| 16.2.0 | 8.9 s | 590 s | 581 s | 5.1 s |
| trunk | 14.4 s | 742 s | 729 s | 9.1 s |
## Where this shows up
We found this while compiling C code that a source obfuscator had transformed:
functions were inlined into `main`, then control-flow flattening turned `main`
into a single dispatch loop. In one 1 MB file the loop header has 1434 incoming
edges and thousands of PHIs. Six such files take 20–58 minutes each at -O2 with
16.2.0 and trunk, 97–98% of it in FRE. For one of them, -O1 takes 21 s (16.2.0)
and 32 s (trunk). In fre1, blocks were visited 134 times on average (331 at
most).
