[Bug rtl-optimization/15242] pessimization of "goto *"

["anton at mips dot complang dot tuwien dot ac dot at" <gcc-bugzilla at gcc dot gnu dot org>]

------- Additional Comments From anton at mips dot complang dot tuwien dot ac dot at  2004-07-16 08:17 -------
Subject: Re:  pessimization of "goto *"

zlomj9am at artax dot karlin dot mff dot cuni dot cz wrote:
> > > The optimization is enabled at -O2
> > Not as far as I can tell (tried it on i386 with patched versions of
> > gcc-3.5-20040704 and gcc-3.5-20040523).
> 
> Yes, it is enabled by the patch. The patch duplicates block with computed goto
> to place where a uncond jump to the conputed goto block is if the block is
> small enough.
> The computed jump in the small testcase is not duplicated, because the uncond
> jumps from other places do not jump to a basic block which contains the
> computed jump but to other block:
...

Thanks for opening my eyes.

> > We would like to use -fno-reorder-blocks with
> > duplicate_computed_gotos, either through an extra option, or by just
> > having duplicate_computed_gotos all the time (at least for our code
> > these gotos were duplicated already in the source code, so duplicating
> > them again in the back end is closer to the idea of
> > -fno-reorder-blocks than not duplicating them).
> 
> Adding an new flag is possible. However, I do not see why you explicitelly want
> to disable reorder-blocks.

We need it for the dynamic superinstruction optimization (aka
selective inlining, PLDI'98 p. 291) in Gforth and further
optimizations building on that (other people working on efficient
interpreters/dynamic code generators have the same problem; e.g., I
recently talked to Etienne Gagnon (http://sablevm.org/) about this;
qemu also uses -fno-reorder-blocks).

For dynamic superinstructions we need to ensure that the machine code
corresponding to source code between two labels is between the
addresses that gcc produces for the labels.  The flag
-fno-reorder-blocks almost gives us that (but the sharing of the
"goto *"s breaks that).

Even for just plain interpreters (without dynamic superinstructions),
the sharing of the "goto *"s resulting from the merging of code after
conditional jumps (as shown in the simplified testcase) will often
reduce performance significantly through lower BTB accuracy.  So for
performance one probably wants to use -fno-reorder-blocks there,
unless this results in merging the "goto *"s, as it does now.

> > One other thing I noticed is that apparently there is no combining
> > pass (or its tree-ssa equivalent) after duplicate_computed_gotos,
> > resulting in compiling code like
> > 
> >     goto *a[i];
> > 
> > into
> > 
> >         movl    a.0(,%ebx,4), %eax
> >         jmp     *%eax
> > 
> > instead of
> > 
> > 	jmp	*a.0(,%ebx,4)
> 
> The combiner should have already combined these insns before the duplication of
> computed gotos is run. This pass just duplicates some insns.

My guess is that the combiner does not combine these insns before
duplication, because they are in different basic blocks before
duplication.  Without duplication the code would look like:

         movl    a.0(,%ebx,4), %eax
         jmp     .L9
         ...
.L9:
         jmp     *%eax

- anton


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=15242