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

[Richard Henderson]

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.


r~