[0/4,v2] Implement smart multiple switch expansion algorithms

Message ID cover.1528462860.git.mliska@suse.cz
Headers show
Series
  • Implement smart multiple switch expansion algorithms
Related show

Message

Martin Liška June 8, 2018, 1:01 p.m.
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