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_split_edge.


Hi,

Attached is a patch to speed up tree_split_edge.

Consider the following loop in tree_split_edge.

  FOR_EACH_EDGE (e, ei, dest->preds)
    if (e->src->next_bb == dest)
      break;

Note that this is equivalent to

  FOR_EACH_EDGE (e, ei, dest->preds)
    if (e->src == dest->prev_bb)
      break;

Then we can simply use find_edge like so

  if (dest->prev_bb)
    e = find_edge (dest->prev_bb, dest);
  else
    e = 0;

which we can combine with the "if" statement that immediately follows.
We get

  if (dest->prev_bb && find_edge (dest->prev_bb, dest))
    after_bb = edge_in->src;
  else
    after_bb = dest->prev_bb;

The moral of the story is that if DEST's in-degree is high, we would
be wasting a lot of time in FOR_EACH_EDGE.

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

      original patched
real:  194.622 193.835 (0.406% down)
user:  190.982 190.234 (0.393% down)

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

Kazu Hirata

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

	* tree-cfg.c (tree_split_edge): Speed up by using find_edge.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.121
diff -c -d -p -r2.121 tree-cfg.c
*** tree-cfg.c	25 Nov 2004 13:31:47 -0000	2.121
--- tree-cfg.c	25 Nov 2004 16:14:05 -0000
*************** tree_split_edge (edge edge_in)
*** 3144,3150 ****
  {
    basic_block new_bb, after_bb, dest, src;
    edge new_edge, e;
-   edge_iterator ei;
  
    /* Abnormal edges cannot be split.  */
    gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
--- 3144,3149 ----
*************** tree_split_edge (edge edge_in)
*** 3155,3167 ****
    /* Place the new block in the block list.  Try to keep the new block
       near its "logical" location.  This is of most help to humans looking
       at debugging dumps.  */
!   FOR_EACH_EDGE (e, ei, dest->preds)
!     if (e->src->next_bb == dest)
!       break;
!   if (!e)
!     after_bb = dest->prev_bb;
!   else
      after_bb = edge_in->src;
  
    new_bb = create_empty_bb (after_bb);
    new_bb->frequency = EDGE_FREQUENCY (edge_in);
--- 3154,3163 ----
    /* Place the new block in the block list.  Try to keep the new block
       near its "logical" location.  This is of most help to humans looking
       at debugging dumps.  */
!   if (dest->prev_bb && find_edge (dest->prev_bb, dest))
      after_bb = edge_in->src;
+   else
+     after_bb = dest->prev_bb;
  
    new_bb = create_empty_bb (after_bb);
    new_bb->frequency = EDGE_FREQUENCY (edge_in);


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