This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] PR/7344, O(n^2) branch prediction
- From: Richard Henderson <rth at redhat dot com>
- To: tm <tm at mail dot kloo dot net>
- Cc: Brad Lucier <lucier at math dot purdue dot edu>, Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>, Daniel Berlin <dberlin at dberlin dot org>, jh at suse dot cz, gcc-patches at gcc dot gnu dot org
- Date: Wed, 11 Sep 2002 18:52:12 -0700
- Subject: Re: [PATCH] PR/7344, O(n^2) branch prediction
- References: <200209080345.g883jnN23834@banach.math.purdue.edu> <Pine.LNX.4.21.0209111821240.4518-100000@mail.kloo.net>
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~