This is the mail archive of the
mailing list for the GCC project.
Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: Richard Biener <richard dot guenther at gmail dot com>
- Cc: Steven Bosscher <stevenb dot gcc at gmail dot com>, Martin Liška <mliska at suse dot cz>, GCC Patches <gcc-patches at gcc dot gnu dot org>, Martin Jambor <mjambor at suse dot cz>
- Date: Thu, 3 Aug 2017 15:20:13 +0200
- Subject: Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.
- Authentication-results: sourceware.org; auth=none
- References: <email@example.com> <CABu31nN=Y9Y_KBzgoqKgcGcMb_8wPUt74YSK2pDkYetTHoq7EQ@mail.gmail.com> <CAFiYyc0cEYehTs_s4b2SoaaTdqRizo0Z2UDS_Fy=PW6XUS=jFQ@mail.gmail.com>
> On Thu, Aug 3, 2017 at 2:52 PM, Steven Bosscher <firstname.lastname@example.org> 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 ;))
Also later in optimization you have better idea of value ranges and you can
shape the decision tree better for given context. In theory at least ;)
One thing that would benefit from earlier expansion is code size/runtime estimation
for inlining. But perhaps we could just run the algorithm to see how hard the
switch is when we decide on its size (what is there right now is bit lame)