Re: [ast-optimizer-branch] Goto/Break/Continue/Switch elimination

[Daniel Berlin <dberlin at dberlin dot org>]

On 2 May 2002, Diego Novillo wrote:

> On Thu, 2002-05-02 at 14:16, Richard Henderson wrote:
> 
> > I wonder if there's some way to write the tree optimizations such that
> > they use an abstract cfg.  If goto elimination was "easy", then we use
> > a set of cfg routines that sort-of generate the cfg on the fly as we
> > examine it.  Otherwise we do the full graph thing.
> > 
> The usage I've seen advertised for goto/break elimination passes is
> things like parallelizing loops.  We already have a generic CFG builder
> that deals with anything you throw at it.
> 
> I don't think we should always apply this transformation.

I think there might actually be simple heuristics to determine when to 
apply at least goto elimination.

1.  Any loops where we can determine the number of iterations, and it's < 
some number,  that contain non-computed gotos (exclusively)  should be  
goto-eliminated (we might be able to unswitch the generated conditions anyway).
2. Any loops containing computed gotos should have no goto elimination 
performed at all (even if we *could* eliminate some of them).
We won't be able to parallelize them anyway, most likely, because of the 
computed goto.  They are also probably written specifically that way to 
increase speed or something, so we probably don't want to mess with them.
3.  Outside of loops, some heuristic that takes into account number of 
gotos vs function size or something (the applicable heuristic escapes me) 
so we don't increase code size too much.
4. Inside loops where we can't determine the number of iterations at 
compile time, we should use some heuristic.


> However, it
> may happen that for some transformations we want/need to deal with a
> simpler CFG.  
Particularly, loop optimizations.
> In those cases we can call the goto elimination pass.  As
> usual, we should try to balance the code bloat vs performance vs
> compilation speed.
> 
> 
> Diego.
>