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

["Martin Liška" <mliska@suse.cz>]

On 08/02/2017 01:51 PM, Richard Biener wrote:
> On Wed, Aug 2, 2017 at 1:20 PM, Martin Liška <mliska@suse.cz> 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.
>>
>> 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.
>>
>> 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).

Hello.

Agree! Eventually we should merge both files into a single one. I would prefer to start
with new generic name of file (gimple-switch-low.c), which will eventually eat content
of tree-switch-conversion.c. Is it acceptable approach?

As Jeff already accepted the patch, I will install it as soon as an agreement in the question
will be done.

Martin

> 
> 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
>>
>>