Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Wed, Aug 2, 2017 at 1:51 PM, Richard Biener wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška wrote:
>> Hello.
>>
>> After some discussions with Honza, I've decided to convert current code in stmt.c that
>> is responsible for switch expansion. More precisely, I would like to convert the code
>> to expand gswitch statements on tree level. Currently the newly created pass is executed
>> at the end of tree optimizations.

Hah, something I promissed myself (and others) to do years ago! Thanks
thanks thanks! :-)


>> My plan for future is to inspire in [1] and come up with some more sophisticated switch
>> expansions. For that I've been working on a paper where I'll summarize statistics based
>> on what I've collected in openSUSE distribution with specially instrumented GCC. If I'll be
>> happy I can also fit in to schedule of this year's Cauldron with a talk.

Sayle's paper is a good starting point. Also interesting:



>> Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.
>>
>> Thoughts?
>
> First of all thanks.
>
> I think part of switch expansion moved to switch-conversion some time ago
> (emit_case_bit_tests).  So maybe the full lowering should be in at least
> the same source file and it should maybe applied earlier for a subset of
> cases (very low number of cases for example).
>
> Did you base the code on the RTL expansion code or did you re-write it from
> scratch?
>
> No further comments sofar.
>
> Richard.
>
>> Martin
>>
>> [1] https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf
>>
>> gcc/ChangeLog:
>>
>> 2017-07-31  Martin Liska  <mliska@suse.cz>
>>
>>         * Makefile.in: Add gimple-switch-low.o.
>>         * passes.def: Include pass_lower_switch.
>>         * stmt.c (dump_case_nodes): Remove and move to
>>         gimple-switch-low.c.
>>         (case_values_threshold): Likewise.
>>         (expand_switch_as_decision_tree_p): Likewise.
>>         (emit_case_decision_tree): Likewise.
>>         (expand_case): Likewise.
>>         (balance_case_nodes): Likewise.
>>         (node_has_low_bound): Likewise.
>>         (node_has_high_bound): Likewise.
>>         (node_is_bounded): Likewise.
>>         (emit_case_nodes): Likewise.
>>         * timevar.def: Add TV_TREE_SWITCH_LOWERING.
>>         * tree-pass.h: Add make_pass_lower_switch.
>>         * gimple-switch-low.c: New file.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 2017-07-31  Martin Liska  <mliska@suse.cz>
>>
>>         * gcc.dg/tree-prof/update-loopch.c: Scan patterns in
>>         switchlower.
>>         * gcc.dg/tree-ssa/vrp104.c: Likewise.
>> ---
>>  gcc/Makefile.in                                |    1 +
>>  gcc/gimple-switch-low.c                        | 1226 ++++++++++++++++++++++++
>>  gcc/passes.def                                 |    1 +
>>  gcc/stmt.c                                     |  861 -----------------
>>  gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
>>  gcc/testsuite/gcc.dg/tree-ssa/vrp104.c         |    2 +-
>>  gcc/timevar.def                                |    1 +
>>  gcc/tree-pass.h                                |    1 +
>>  8 files changed, 1236 insertions(+), 867 deletions(-)
>>  create mode 100644 gcc/gimple-switch-low.c
>>
>>