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]

[patch] cfgrtl.c: Speed up try_redirect_by_replacing_jump.


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.

Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.151
diff -c -d -p -r1.151 cfgrtl.c
*** cfgrtl.c	25 Nov 2004 09:30:00 -0000	1.151
--- cfgrtl.c	25 Nov 2004 09:43:22 -0000
*************** try_redirect_by_replacing_jump (edge e, 
*** 662,671 ****
  {
    basic_block src = e->src;
    rtx insn = BB_END (src), kill_from;
-   edge tmp;
    rtx set;
    int fallthru = 0;
-   edge_iterator ei;
  
    /* If we are partitioning hot/cold basic blocks, we don't want to
       mess up unconditional or indirect jumps that cross between hot
--- 662,669 ----
*************** try_redirect_by_replacing_jump (edge e, 
*** 682,693 ****
  	  || BB_PARTITION (src) != BB_PARTITION (target)))
      return NULL;
  
!   /* Verify that all targets will be TARGET.  */
!   FOR_EACH_EDGE (tmp, ei, src->succs)
!     if (tmp->dest != target && tmp != e)
!       break;
  
!   if (tmp || !onlyjump_p (insn))
      return NULL;
    if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
      return NULL;
--- 680,696 ----
  	  || BB_PARTITION (src) != BB_PARTITION (target)))
      return NULL;
  
!   /* We can replace or remove a complex jump only when we have exactly
!      two edges.  Also, if we have exactly one outgoing edge, we can
!      redirect that.  */
!   if (EDGE_COUNT (src->succs) >= 3
!       /* Verify that all targets will be TARGET.  Specifically, the
! 	 edge that is not E must also go to TARGET.  */
!       || (EDGE_COUNT (src->succs) == 2
! 	  && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
!     return NULL;
  
!   if (!onlyjump_p (insn))
      return NULL;
    if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
      return NULL;


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