This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.
- From: Richard Biener <richard dot guenther at gmail dot com>
- To: Martin Liška <mliska at suse dot cz>
- Cc: GCC Patches <gcc-patches at gcc dot gnu dot org>, Jan Hubicka <hubicka at ucw dot cz>, Martin Jambor <mjambor at suse dot cz>
- Date: Mon, 14 Aug 2017 10:32:34 +0200
- Subject: Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.
- Authentication-results: sourceware.org; auth=none
- References: <b9bed4ff-cbb3-4d33-f54f-0f5a45b421e9@suse.cz> <CAFiYyc04cS6qBcReZqx77_=sLw99gfYEPC7YFMsYpOoRRrZxWQ@mail.gmail.com> <b128c77b-16d3-d73d-fa6d-f517171ffff4@suse.cz>
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
>>>
>>>
>