https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128277
--- Comment #3 from Lvfan Yang <lyfanyang at smail dot nju.edu.cn> ---
At -O1 and above, early CCP (ccp1) spends most of the compile time on a
while (1) { switch (state) ... } dispatch loop where every case jumps
straight back to the loop header, so the header has one latch edge per case
and one PHI per local the loop modifies. This is the same input shape as
PR 128082 (there it was fre1 at -O2); in comment #2 of that PR tree CCP showed
up at 40% after the FRE fix, and this report is about that part.
The attached ccp-hog.c (2414 lines, generated with the attached gen_fre.py,
"gen_fre.py -V 400 -N 1600") has 400 unsigned locals and 1600 cases. It is
clean under -fsanitize=address,undefined and prints the same checksum at
-O0 through -O3.
-O1 -c, -ftime-report, release-checking compilers:
tree CCP TOTAL
9.4.0 0.55 s 3.13 s
9.4.0 -fdisable-tree-ccp1 0.29 s 2.84 s
16.2.0 13.40 s 17.08 s
16.2.0 -fdisable-tree-ccp1 0.56 s 4.17 s
So ccp1 goes from about 0.3 s to about 12.8 s. Trunk 20261018 (with the
PR 128082 fix, --enable-checking=yes) shows the same: tree CCP 17.5 s of
29.3 s total at -O1, and 17.1 s of 38.1 s at -O2.
The attached ccp-hog-single.c differs in one line only: the iteration
counter check moves from before the switch to after it, so all cases join
after the switch and the loop has a single latch. With 16.2.0 at -O1 it takes
tree CCP 1.12 s (total 5.17 s), against 14.62 s (total 18.26 s) for
ccp-hog.c in the same run. 9.4.0 takes about 0.6 s for both.
Cause: r13-5102-g445a48a226ffd5 (PR tree-optimization/108353, "copyprop
iteration order") removed the cfg_blocks_back / ssa_edge_worklist_back
worklists from tree-ssa-propagate.cc. Before, the propagator finished the
current RPO iteration before processing backedge destinations; now
backedge destinations are processed first. With N latch edges into the
loop header, the header PHIs (N arguments each) are re-simulated after each
latch value change instead of once per iteration.
ccp1 statistics from -fdump-tree-ccp1-details at -O1 on fre-hog.c, the
smaller testcase from PR 128082 (attachment 65919, gen_fre.py -V 100 -N 800,
1014 lines):
PHI visits stmt visits lattice changes
9.4.0 687 4529 4125
16.2.0 32983 4674 5523
trunk 20261018 32983 4674 5523
trunk, r13-5102 reverted 687 4538 4134
(tree CCP at -O1 on fre-hog.c: 0.04 s with 9.4.0, 0.54 s with 16.2.0.)
To check the cause we reverted r13-5102 on trunk 20261018 (with the
PR 128082 fix; the revert also needs the curr_order variable that later
cleanup removed) and rebuilt cc1. On ccp-hog.c at -O1, same machine, same
time, --enable-checking=yes:
tree CCP TOTAL
trunk 20261018 18.81 s 31.20 s
trunk, r13-5102 reverted 2.19 s 14.41 s
We know r13-5102 was a deliberate change for PR 108353 (iterate cycles first
so that optimistic constants from cycles that do not exit are not used).
With the revert, ccp2 on a mid-size variant (gen_fre.py -V 200 -N 400)
visited somewhat more PHIs (4184 -> 6274) while ccp1 went from 70283 to 6013,
so the old order is not better everywhere; the problem is the cost on loop
headers with many latch edges.
A profile of 16.2.0 on a larger input (cc1 sampled under gdb) shows the time
in ccp_propagate::visit_phi -> ccp_lattice_meet, much of it copying and
combining the widest_int masks of the lattice values, so each of the extra PHI
visits is also more expensive than in 9.4.
We found this with C code transformed by a source obfuscator (control-flow
flattening, as in PR 128082). On one such file (2 MB, flattened dispatch with
computed gotos) 16.2.0 takes 259 s at -O1 with tree CCP 233 s, against 21 s
with 9.4.0; -fdisable-tree-ccp1 brings 16.2.0 down to 33 s.
```
