Re: [PATCH] PR/7344, O(n^2) branch prediction

[Jan Hubicka <jh at suse dot cz>]

> On Wed, Sep 11, 2002 at 06:24:27PM -0700, tm wrote:
> > I'm guessing we need to handle computed gotos better; maybe we can mark it
> > as reaching "everything" without having to create thousands of edges?
> > Maybe a special edge type or something?
> 
> The best way I can think to handle computed gotos is to fold them while
> generating initial rtl (or during simplification on the tree-ssa branch).
> 
> The very first time we expand a computed goto, we do:
> 
> 	(set (indirect_jump_reg) (address))
> 	(code_label indirect_jump_label)
> 	(set (pc) (indirect_jump_reg))
> 
> and remember both indirect_jump_reg and indirect_jump_label.  All other
> times we emit
> 
> 	(set (indirect_jump_reg) (address))
> 	(set (pc) (indirect_jump_label))
> 
> such that there is only ever one computed goto in the rtl.  Now instead
> of having n_branches*n_labels edges, we have n_branches+n_labels edges.
> 
> By itself, this would largely negate the advantage of using computed
> gotos at all.  The trick to avoid this is that we recognize that the
> 
>         (code_label indirect_jump_label) 
>         (set (pc) (indirect_jump_reg))
> 
> basic block is small, and duplicate it at every jump site during 
> bb-reorder.  I believe code to do this exists on cfg-branch, to be
> merged into gcc 3.4.

It is not implemented yet, but this has been my plan too.  I can
implement it soon after returning from the Japan at 29th.

Honza
> 
> 
> r~