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] tree-cfg.c: Speed up tree_try_redirect_by_replacing_jump.


Hi,

Attached is a patch to speed up tree_try_redirect_by_replacing_jump.

tree_try_redirect_by_replacing_jump tries to redirect a conditional
jump like COND_EXPR or SWITCH_PEXR by replacing it with an
unconditonal jump, which is actually represented implicitly.

Note that we can remove a conditoinal jump only when we have exactly
two outgoing edges.  If we have exactly one outgoing edge, we don't
have any COND_EXPR or SWITCH_EXPR in the first place.  If we have
three or more outgoing edges, redirecting one of them will give you at
least two unique edges, meaning that we cannot still remove
SWITCH_EXPR.

If we have exactly two outgoing edges, then the edge that we are not
redirecting must have the same destination as the one we want to
redirect an edge to.

The patch implements the idea above.

Note that the original implementation of the check "leaks" a case with
only one outgoing edge, in which case TMP is NULL.  In other words,
"if (tmp)" cannot catch this case, letting the control fall through
even though we know we have to return NULL at the end.

Here is a timing in seconds for three runs of "./cc1 -quiet -O2
-fomit-frame-pointer -o /dev/null insn-attrtab.i".

      original patched
real:  135.841 134.840 (0.736% down)
user:  133.496 132.788 (0.530% down)

Tested on i686-pc-linux-gnu.  OK to apply?

p.s.
I could do the same on cfgrtl.c:try_redirect_by_replacing_jump, but
doing so actually generated different assembly code, so I didn't mix
that into this patch.

Kazu Hirata

2004-11-23  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-cfg.c (tree_try_redirect_by_replacing_jump): Speed up
	by restricting to the case with two outgoing edges.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.117
diff -c -d -p -r2.117 tree-cfg.c
*** tree-cfg.c	23 Nov 2004 05:25:10 -0000	2.117
--- tree-cfg.c	23 Nov 2004 17:47:04 -0000
*************** static edge
*** 4247,4263 ****
  tree_try_redirect_by_replacing_jump (edge e, basic_block target)
  {
    basic_block src = e->src;
-   edge tmp;
    block_stmt_iterator b;
    tree stmt;
-   edge_iterator ei;
- 
-   /* 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;
  
    b = bsi_last (src);
--- 4247,4261 ----
  tree_try_redirect_by_replacing_jump (edge e, basic_block target)
  {
    basic_block src = e->src;
    block_stmt_iterator b;
    tree stmt;
  
!   /* We can replace or remove a complex jump only when we have exactly
!      two edges.  */
!   if (EDGE_COUNT (src->succs) != 2
!       /* Verify that all targets will be TARGET.  Specifically, the
! 	 edge that is not E must also go to TARGET.  */
!       || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target)
      return NULL;
  
    b = bsi_last (src);


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