This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [patch] cfgrtl.c: Speed up try_redirect_by_replacing_jump.


On Thu, 2004-11-25 at 23:44 -0500, Kazu Hirata wrote:
> Hi,
> 
> 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)
>       break;
>   if (tmp)
>     return NULL;
> 
> We can do this without a loop.  First, let me list out all
> possibilities.
> 
> 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"
>   statement.
> 
> 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  <kazu@cs.umass.edu>
> 
> 	* cfgrtl.c (try_redirect_by_replacing_jump): Speed up the
> 	check that tests if all edges go to the same destination.
OK.

Jeff



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]