This is the mail archive of the
mailing list for the GCC project.
Re: [patch] cfgrtl.c: Speed up try_redirect_by_replacing_jump.
- From: Jeffrey A Law <law at redhat dot com>
- To: Kazu Hirata <kazu at cs dot umass dot edu>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Thu, 25 Nov 2004 23:46:10 -0700
- Subject: Re: [patch] cfgrtl.c: Speed up try_redirect_by_replacing_jump.
- Organization: Red Hat, Inc
- References: <firstname.lastname@example.org>
- Reply-to: law at redhat dot com
On Thu, 2004-11-25 at 23:44 -0500, Kazu Hirata wrote:
> Attached is a patch to speed up try_redirect_by_replacing_jump.
> try_redirect_by_replacing_jump tries to redirect a conditional jump by
> replacing it with an unconditonal jump or a fall through.
> The problem is that the following loop is a little slow.
> /* Verify that all targets will be TARGET. */
> FOR_EACH_EDGE (tmp, ei, src->succs)
> if (tmp->dest != target && tmp != e)
> if (tmp)
> return NULL;
> We can do this without a loop. First, let me list out all
> EDGE_COUNT == 0
> The loop completes without hitting the break, so tmp == NULL. That
> is, we fall through the "if" statement. (We probably don't have
> this case anyway.)
> EDGE_COUNT == 1
> We must have EDGE_SUCC (src, 0) == e, so again the loop completes
> without hitting the break. That is, we fall through the "if"
> EDGE_COUNT == 2
> This is the interesting case. If the edge that is not E goes to the
> same destination as the one we are redirecting E to, then tmp ==
> NULL, in which case we fall through the "if" statement. Otherwise,
> we return NULL.
> EDGE_COUNT >= 3
> There is no way to have tmp == NULL. If you exclude an edge E from
> the edge vector src->succs, we still have two edges at least. Since
> edges are unique, the loop terminates in the middle, hitting the
> break. That is, tmp != NULL.
> The patch implements the above without using a loop.
> Here is a timing on five runs of "./cc1 -quiet -O2
> -fomit-frame-pointer -o /dev/null insn-attrtab.i"
> original patched
> real: 195.248 193.852 (0.720% down)
> user: 191.642 190.377 (0.664% down)
> The improvement seems to be a little too good to be true, but we are
> not regressing any way.
> Tested on i686-pc-linux-gnu. OK to apply?
> Kazu Hirata
> 2004-11-26 Kazu Hirata <email@example.com>
> * cfgrtl.c (try_redirect_by_replacing_jump): Speed up the
> check that tests if all edges go to the same destination.