Hello.
This is v2 of following patch series:
https://gcc.gnu.org/ml/gcc-patches/2017-10/msg00347.html
I've done some adjustments:
- patch series is split:
* 1/4 - factoring out of switch conversion algorithm
* 2/4 - jump table and bit test use clustering data structures, but operate
on all cases
* 3/4 - clustering is enabled for both algorithms
* 4/4 - param change which makes reasonable sizes on binaries
- jump table density threshold has been changed to align with current trunk
- most of David's comments were resolved
I decided to change way how to calculate jump table and bit test benefit.
It uses the same calculation as we use now. Still I believe it's too high
number, factor of 10 basically means that expected grown would be 10x compared
to balanced tree expansion. It's caused by fact that cmp & tmp instruction
takes roughly 8B, which is size of one element in jump table.
There are statistics for parameter equal to 8.
1) GCC (-O2):
bloaty ./objdir2/gcc/cc1plus -- ./objdir3/gcc/cc1plus
VM SIZE FILE SIZE
++++++++++++++ GROWING ++++++++++++++
+0.1% +11.3Ki .text +11.3Ki +0.1%
[ = ] 0 .debug_info +4.00Ki +0.0%
[ = ] 0 .debug_loc +3.69Ki +0.0%
+0.1% +1.95Ki .eh_frame +1.95Ki +0.1%
-------------- SHRINKING --------------
-2.6% -195Ki .rodata -195Ki -2.6%
[ = ] 0 .debug_line -8.29Ki -0.0%
[ = ] 0 [Unmapped] -2.11Ki -54.8%
[ = ] 0 .debug_ranges -2.08Ki -0.0%
[ = ] 0 .strtab -691 -0.0%
[ = ] 0 .symtab -360 -0.0%
[ = ] 0 .debug_abbrev -167 -0.0%
-0.0% -80 .eh_frame_hdr -80 -0.0%
[ = ] 0 .debug_aranges -16 -0.0%
-0.6% -181Ki TOTAL -187Ki -0.1%
Thus shrinks by 0.6%.
2) SPEC 2006 benchmarks (-O2): numbers are presented only if there's a change:
BENCHMARK: /tmp/before/astar_peak.amd64-m64-mine
BENCHMARK: /tmp/before/bwaves_peak.amd64-m64-mine
BENCHMARK: /tmp/before/bzip2_peak.amd64-m64-mine
BENCHMARK: /tmp/before/cactusADM_peak.amd64-m64-mine
+0.0% +16 .text +16 +0.0%
-0.4% -320 .rodata -320 -0.4%
-0.0% -312 TOTAL -4.17Ki -0.1%
BENCHMARK: /tmp/before/calculix_peak.amd64-m64-mine
+0.1% +184 .rodata +184 +0.1%
-0.0% -16 .text -16 -0.0%
+0.0% +112 TOTAL +1.06Ki +0.0%
BENCHMARK: /tmp/before/dealII_peak.amd64-m64-mine
[ = ] 0 TOTAL +16 +0.0%
BENCHMARK: /tmp/before/gamess_peak.amd64-m64-mine
+0.0% +480 .rodata +480 +0.0%
-0.0% -112 .text -112 -0.0%
+0.0% +352 TOTAL -160 -0.0%
BENCHMARK: /tmp/before/gcc_peak.amd64-m64-mine
-1.2% -9.78Ki .rodata -9.78Ki -1.2%
-0.1% -1.44Ki .text -1.44Ki -0.1%
-0.3% -11.3Ki TOTAL +264 +0.0%
BENCHMARK: /tmp/before/GemsFDTD_peak.amd64-m64-mine
BENCHMARK: /tmp/before/gobmk_peak.amd64-m64-mine
+0.0% +64 .rodata +64 +0.0%
-0.0% -16 .text -16 -0.0%
+0.0% +64 TOTAL -48 -0.0%
BENCHMARK: /tmp/before/gromacs_peak.amd64-m64-mine
+0.0% +80 .text +80 +0.0%
-0.6% -512 .rodata -512 -0.6%
-0.0% -384 TOTAL +432 +0.0%
BENCHMARK: /tmp/before/h264ref_peak.amd64-m64-mine
+0.5% +384 .rodata +384 +0.5%
-0.0% -96 .text -96 -0.0%
+0.0% +288 TOTAL -16 -0.0%
BENCHMARK: /tmp/before/hmmer_peak.amd64-m64-mine
+2.6% +704 .rodata +704 +2.6%
-0.1% -288 .text -288 -0.1%
+0.1% +416 TOTAL +80 +0.0%
BENCHMARK: /tmp/before/lbm_peak.amd64-m64-mine
BENCHMARK: /tmp/before/leslie3d_peak.amd64-m64-mine
BENCHMARK: /tmp/before/libquantum_peak.amd64-m64-mine
+26% +336 .rodata +336 +26%
+0.6% +176 .text +176 +0.6%
+1.2% +512 TOTAL -256 -0.1%
BENCHMARK: /tmp/before/mcf_peak.amd64-m64-mine
BENCHMARK: /tmp/before/milc_peak.amd64-m64-mine
BENCHMARK: /tmp/before/namd_peak.amd64-m64-mine
BENCHMARK: /tmp/before/omnetpp_peak.amd64-m64-mine
BENCHMARK: /tmp/before/perlbench_peak.amd64-m64-mine
+4.5% +5.25Ki .rodata +5.25Ki +4.5%
-0.2% -1.70Ki .text -1.70Ki -0.2%
+0.3% +3.50Ki TOTAL +2.41Ki +0.0%
BENCHMARK: /tmp/before/povray_peak.amd64-m64-mine
+20% +21.1Ki .rodata +21.1Ki +20%
-0.8% -5.84Ki .text -5.84Ki -0.8%
+1.4% +15.4Ki TOTAL +19.6Ki +0.3%
BENCHMARK: /tmp/before/sjeng_peak.amd64-m64-mine
+0.7% +192 .rodata +192 +0.7%
-0.1% -80 .text -80 -0.1%
+0.0% +128 TOTAL -64 -0.0%
BENCHMARK: /tmp/before/soplex_peak.amd64-m64-mine
+2.5% +464 .rodata +464 +2.5%
-0.0% -32 .text -32 -0.0%
+0.1% +444 TOTAL -224 -0.0%
BENCHMARK: /tmp/before/specrand_peak.amd64-m64-mine
BENCHMARK: /tmp/before/sphinx_livepretend_peak.amd64-m64-mine
+0.0% +32 .text +32 +0.0%
-0.3% -64 .rodata -64 -0.3%
-0.0% -32 TOTAL -48 -0.0%
BENCHMARK: /tmp/before/tonto_peak.amd64-m64-mine
+0.2% +928 .rodata +928 +0.2%
-0.0% -176 .text -176 -0.0%
+0.0% +760 TOTAL +832 +0.0%
BENCHMARK: /tmp/before/wrf_peak.amd64-m64-mine
+0.2% +608 .rodata +608 +0.2%
-0.0% -608 .text -608 -0.0%
+0.0% +24 TOTAL -272 -0.0%
BENCHMARK: /tmp/before/Xalan_peak.amd64-m64-mine
+0.3% +2.06Ki .rodata +2.06Ki +0.3%
-0.0% -496 .text -496 -0.0%
+0.0% +1.60Ki TOTAL +1.11Ki +0.0%
BENCHMARK: /tmp/before/zeusmp_peak.amd64-m64-mine
Which gives us very similar numbers.
3) http://natsys-lab.blogspot.com/
https://github.com/natsys/blog
It's a HTTP request parser benchmark. There are some nice new jump tables
created:
http_ngx.c.167t.switchlower1:;; GIMPLE switch case clusters: 0 10 13 JT:97-105
which is a switch that handles 'a' - 'z', plus 0, 10, 13. JT is created for
alphabet characters. I can also measure benchmark changes:
+--------------------------------+--------+--------+---------+
| https://github.com/natsys/blog | base | Gcc 9 | ratio |
+--------------------------------+--------+--------+---------+
| goto_big_header_line | 244.22 | 202.62 | 82.97% |
| goto_header_line | 119.06 | 118.58 | 99.60% |
| goto_opt_request_line | 172.97 | 156.39 | 90.41% |
| goto_request_line | 201.47 | 159.29 | 79.06% |
| hsm_header_line | 283.14 | 282.16 | 99.65% |
| ngx_big_header_line | 755.11 | 683.98 | 90.58% |
| ngx_header_line | 84.85 | 84.46 | 99.54% |
| ngx_lw_header_line | 96.61 | 95.98 | 99.35% |
| ngx_request_line | 141.9 | 184.47 | 130.00% |
| tbl_big_header_line | 414.59 | 359.58 | 86.73% |
| tbl_header_line | 206.87 | 205.71 | 99.44% |
+--------------------------------+--------+--------+---------+
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
Thoughts?
Martin
marxin (4):
Transform switch_conversion into a class.
Switch other switch expansion methods into classes.
Enable clustering for switch statements.
Change default for jump_table expansion ratio to 8.
gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 2 +-
gcc/tree-switch-conversion.c | 2518 +++++++++++-------------
gcc/tree-switch-conversion.h | 845 ++++++++
3 files changed, 1941 insertions(+), 1424 deletions(-)
create mode 100644 gcc/tree-switch-conversion.h
--
2.17.0
