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

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Aug 3, 2017 at 2:52 PM, Steven Bosscher <stevenb.gcc@gmail.com> 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! :-)
>
> The end of the gimple optimizations is seems late for the lowering.
> Before there were gimple optimizations, switch lowering was part of
> the first compiler pass (to generate RTL from the front end) *before*
> all code transformation passes ("optimizations" ;-). Because the
> lowering of switch statements was rewritten as a gimple lowering pass,
> it now runs *after* optimizations. But to be honest, I can't think of
> any optimization opportunities exposed by lowering earlier than at the
> end of gimple optimizations. Years ago there was some RTL jump
> threading still done after lowering of small switch statements, but I
> can't find the related PRs anymore.

I think the main reason for not doing it early is the benefit is small
(unless it is GIMPLE optimizations triggering) and we can't get rid of
switches completely because we eventually have to support casei RTL expansion.
(and no, computed goto with an array of label addresses at GIMPLE is really
too ugly ;))

Richard.

>
>> 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:
>
> http://llvm.org/devmtg/2017-02-04/Efficient-clustering-of-case-statements-for-indirect-branch-prediction.pdf
> About adjusting the size of jump tables to the capabilities of the CPU
> branch predictor. Mixed results but something to consider.
>
> Kannan & Proebsting, "CORRECTION TO ‘PRODUCING GOOD CODE FOR THE CASE
> STATEMENT’"
> About finding "clusers" of given density within the target values of
> the switch statement. The clustering algorithm as presented is N^2 in
> the number of case labels, but the idea is interesting and a
> simplified, cheaper approach may be possible. This is already used in
> LLVM, it seems.
>
> The real challenge will be to figure out how to pick from all these
> different approaches the right ones to lower a single switch
> statement.
>
> Ciao!
> Steven