From: "Martin Liška" <mliska@suse.cz>
To: Steven Bosscher <stevenb.gcc@gmail.com>
Cc: GCC Patches <gcc-patches@gcc.gnu.org>,
Jan Hubicka <hubicka@ucw.cz>, Martin Jambor <mjambor@suse.cz>
Subject: Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.
Date: Fri, 04 Aug 2017 11:19:00 -0000 [thread overview]
Message-ID: <241a1724-73c9-a20f-4e83-f5edc84ef5bc@suse.cz> (raw)
In-Reply-To: <CABu31nN=Y9Y_KBzgoqKgcGcMb_8wPUt74YSK2pDkYetTHoq7EQ@mail.gmail.com>
On 08/03/2017 02:52 PM, Steven Bosscher 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! :-)
Hi.
Yes, it's very interesting topic to work on. Well, if you have sparse time, help will be
highly appreciated ;)
>
> 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.
>
>
>> 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:
Yes, I read that.
>
> 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.
I've also considered to play with jump tables and their sizes. Thanks for the article.
>
> 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.
I'll take a look at LLVM as I'm unable to find PDF of the Kannan's article :/
>
> 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.
Exactly, that's why I started with porting of the balanced decision tree to tree level
and I've been collecting statistics. That should help us what would be beneficial and
what's more nice-to-have stuff.
Martin
>
> Ciao!
> Steven
>
prev parent reply other threads:[~2017-08-04 11:19 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-02 11:20 Martin Liška
2017-08-02 11:51 ` Richard Biener
2017-08-02 12:49 ` Martin Liška
2017-08-03 9:02 ` Jan Hubicka
2017-08-03 16:11 ` Jeff Law
2017-08-03 12:22 ` Steven Bosscher
2017-08-10 8:54 ` Martin Liška
2017-08-14 9:26 ` Richard Biener
2017-08-15 12:50 ` Martin Liška
2017-08-18 10:29 ` Richard Biener
2017-08-18 11:05 ` Martin Liška
2017-08-24 17:21 ` Martin Liška
2017-08-29 12:58 ` Richard Biener
2017-08-29 15:11 ` Martin Liška
2017-08-30 9:18 ` Rainer Orth
2017-08-30 12:29 ` Martin Liška
2018-03-25 10:12 ` [testsuite, committed] Make scan pattern more precise in vrp104.c Tom de Vries
2017-08-02 13:38 ` [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level David Malcolm
2017-08-03 12:52 ` Steven Bosscher
2017-08-03 12:56 ` Richard Biener
2017-08-03 13:20 ` Jan Hubicka
2017-08-03 13:28 ` Steven Bosscher
2017-08-04 11:19 ` Martin Liška
2017-08-04 11:19 ` Martin Liška [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=241a1724-73c9-a20f-4e83-f5edc84ef5bc@suse.cz \
--to=mliska@suse.cz \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=mjambor@suse.cz \
--cc=stevenb.gcc@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).