[patch] tree-into-ssa.c: Speed up find_idf.

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

Attached is a patch to speed up find_idf.

find_idf puts pointers to basic blocks into work_stack.  It turns out
that all we need from this work_stack is the indexes of basic blocks,
not pointers to basic blocks.  When we take an item out of work_stack,
we do

  basic_block bb = VEC_pop (basic_block, work_stack);
  bb_index = bb->index;

When we want to put an item to work_stack, we do

  bb = BASIC_BLOCK (bb_index);
  VEC_safe_push (basic_block, work_stack, bb);

The patch removes this extra redirection and puts the indexes of basic
blocks into work_stack.

Here is a timing in seconds for five runs of ./cc1 -quiet -O2
-fomit-frame-pointer -o /dev/null.

              original patched   diff%
c-common.i      13.848  13.813 -0.252%
combine.i       16.884  16.842 -0.248%
fold-const.i    18.403  18.346 -0.309%
reload1.i       11.974  11.954 -0.167%
reload.i        11.895  11.849 -0.386%
insn-attrtab.i 205.229 200.687 -2.213%

I guess the reason why we get so much speed up on insn-attrtab.i is
because access to bb->index is killing data cache, and we know that
insn-attrtab.i has a lot of basic blocks.

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

Kazu Hirata

2005-03-13  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-into-ssa.c (find_idf): Speed up by putting the indexes
	of basic blocks into work_stack.

Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.43
diff -u -d -p -r2.43 tree-into-ssa.c
--- tree-into-ssa.c	9 Mar 2005 11:33:22 -0000	2.43
+++ tree-into-ssa.c	12 Mar 2005 20:02:17 -0000
@@ -111,7 +111,7 @@ static htab_t def_blocks;
 static VEC(tree_on_heap) *block_defs_stack;
 
 /* Basic block vectors used in this file ought to be allocated in the heap.  */
-DEF_VEC_MALLOC_P(basic_block);
+DEF_VEC_MALLOC_P(int);
 
 /* Global data to attach to the main dominator walk structure.  */
 struct mark_def_sites_global_data
@@ -503,40 +503,37 @@ find_idf (bitmap def_blocks, bitmap *dfs
 {
   bitmap_iterator bi;
   unsigned bb_index;
-  VEC(basic_block) *work_stack;
+  VEC(int) *work_stack;
   bitmap phi_insertion_points;
 
-  work_stack = VEC_alloc (basic_block, n_basic_blocks);
+  work_stack = VEC_alloc (int, n_basic_blocks);
   phi_insertion_points = BITMAP_ALLOC (NULL);
 
   /* Seed the work list with all the blocks in DEF_BLOCKS.  */
   EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
-    VEC_safe_push (basic_block, work_stack, BASIC_BLOCK (bb_index));
+    VEC_safe_push (int, work_stack, bb_index);
 
   /* Pop a block off the worklist, add every block that appears in
      the original block's DF that we have not already processed to
      the worklist.  Iterate until the worklist is empty.   Blocks
      which are added to the worklist are potential sites for
      PHI nodes.  */
-  while (VEC_length (basic_block, work_stack) > 0)
+  while (VEC_length (int, work_stack) > 0)
     {
-      basic_block bb = VEC_pop (basic_block, work_stack);
-      bb_index = bb->index;
+      bb_index = VEC_pop (int, work_stack);
       
       EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
 				      0, bb_index, bi)
 	{
-	  bb = BASIC_BLOCK (bb_index);
-
 	  /* Use a safe push because if there is a definition of VAR
 	     in every basic block, then WORK_STACK may eventually have
 	     more than N_BASIC_BLOCK entries.  */
-	  VEC_safe_push (basic_block, work_stack, bb);
+	  VEC_safe_push (int, work_stack, bb_index);
 	  bitmap_set_bit (phi_insertion_points, bb_index);
 	}
     }
 
-  VEC_free (basic_block, work_stack);
+  VEC_free (int, work_stack);
 
   return phi_insertion_points;
 }