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

[Richard Biener]

On Thu, Aug 10, 2017 at 9:50 AM, Martin Liška <mliska@suse.cz> wrote:
> 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?

Hmm, but the existing "lowering" part is called from the
switch-conversion pass.  So
I'm not sure a new file is good.

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