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] regrename.c: Speed up copyprop_hardreg_forward.


Hi,

Attached is a patch to speed up copyprop_hardreg_forward.

In copyprop_hardreg_forward, given a basic block bb, we try to find
its sole predecessor by following the prev_bb chain.  If we find it
this way, that means we have processed BB's sole predecessor because
we process basic blocks by following the next_bb chain.

The problem is that a testcase with a large jump table exposes a
quadratic behavior in copyprop_hardreg_forward because we have to
follow the prev_bb chain main times to get to the basic block with the
jump table from one of the switch cases.

The patch fixes the problem by putting BB_VISITED flag on basic blocks
as we process them.  This way we can tell if we have processed a given
basic block in constant time.

Here is timing for 10 runs of "pr18599.c".

      original patched
real:   98.530  95.857 (2.712% down)
user:   96.814  91.696 (5.286% down)

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

p.s.
I thought about using bb->index as follows.  If BB's sole predecessor
has a smaller index, then consider that to be processed.  I dropped
this idea because I didn't know if bb's index is guaranteed to be
monotonically increasing.  I also thought about calling
compact_blocks, but I didn't do so because I didn't know if it was OK.

Alternatively, we could use a queue to do something like breadth first
search on CFG.  This approach is immune to the ordering of basic
blocks in the next_bb chain, but I could end up optimizing more cases,
which is probably not appropriate for stage 3, so I dropped the idea.

Kazu Hirata

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

	PR rtl-optimization/18599
	* regrename.c (copyprop_hardreg_forward): Speed up by putting
	BB_VISITED flags on basic blocks as we process them.

Index: regrename.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/regrename.c,v
retrieving revision 1.91
diff -c -d -p -r1.91 regrename.c
*** regrename.c	20 Nov 2004 20:18:49 -0000	1.91
--- regrename.c	21 Nov 2004 17:33:17 -0000
*************** copyprop_hardreg_forward (void)
*** 1745,1768 ****
  {
    struct value_data *all_vd;
    bool need_refresh;
!   basic_block bb, bbp = 0;
  
    need_refresh = false;
  
    all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
  
    FOR_EACH_BB (bb)
      {
        /* If a block has a single predecessor, that we've already
  	 processed, begin with the value data that was live at
  	 the end of the predecessor block.  */
        /* ??? Ought to use more intelligent queuing of blocks.  */
-       if (EDGE_COUNT (bb->preds) == 1)
- 	for (bbp = bb; bbp && bbp != EDGE_PRED (bb, 0)->src; bbp = bbp->prev_bb);
        if (EDGE_COUNT (bb->preds) == 1
! 	  && ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
! 	  && EDGE_PRED (bb, 0)->src != ENTRY_BLOCK_PTR
! 	  && bbp)
  	all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
        else
  	init_value_data (all_vd + bb->index);
--- 1745,1775 ----
  {
    struct value_data *all_vd;
    bool need_refresh;
!   basic_block bb;
  
    need_refresh = false;
  
    all_vd = xmalloc (sizeof (struct value_data) * last_basic_block);
  
+   /* Clear all BB_VISITED flags.  We use BB_VISITED flags to indicate
+      whether we have processed a given basic block or not.  Note that
+      we never put BB_VISITED flag on ENTRY_BLOCK_PTR throughout this
+      function because we want to call init_value_data for all
+      successors of ENTRY_BLOCK_PTR.  */
+   FOR_ALL_BB (bb)
+     bb->flags &= ~BB_VISITED;
+ 
    FOR_EACH_BB (bb)
      {
+       bb->flags |= BB_VISITED;
+ 
        /* If a block has a single predecessor, that we've already
  	 processed, begin with the value data that was live at
  	 the end of the predecessor block.  */
        /* ??? Ought to use more intelligent queuing of blocks.  */
        if (EDGE_COUNT (bb->preds) == 1
! 	  && ((EDGE_PRED (bb, 0)->src->flags & BB_VISITED) != 0)
! 	  && ! (EDGE_PRED (bb, 0)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
  	all_vd[bb->index] = all_vd[EDGE_PRED (bb, 0)->src->index];
        else
  	init_value_data (all_vd + bb->index);
*************** copyprop_hardreg_forward (void)
*** 1771,1776 ****
--- 1778,1789 ----
  	need_refresh = true;
      }
  
+   /* Clear BB_VISITED flag on each basic block.  We do not need to
+      clear the one on ENTRY_BLOCK_PTR because it's already cleared
+      above.  */
+   FOR_EACH_BB (bb)
+     bb->flags &= ~BB_VISITED;
+ 
    if (need_refresh)
      {
        if (dump_file)


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