This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] tree-into-ssa.c: Speed up find_idf (Part 2)
- From: Kazu Hirata <kazu at cs dot umass dot edu>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 18 Mar 2005 08:45:58 -0500 (EST)
- Subject: [patch] tree-into-ssa.c: Speed up find_idf (Part 2)
Hi,
Attached is a patch to speed up find_idf.
find_idf allocates a worklist called WORK_STACK with the initial
capacity N_BASIC_BLOCKS and then seeds WORK_STACK with indexes of
definition blocks for a given variable.
The problem is that when we seed WORK_STACK, we use VEC_safe_push to
put an item to WORK_STACK. We know that the number of definition
blocks is no greater than the number of basic blocks, so we can just
use VEC_quick_push.
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 14.545 14.526 -0.130%
combine.i 17.253 17.252 -0.005%
fold-const.i 18.527 18.395 -0.712%
reload1.i 12.249 12.199 -0.408%
reload.i 12.142 12.042 -0.823%
insn-attrtab.i 201.280 201.024 -0.127%
Tested on i686-pc-linux-gnu. OK to apply?
Kazu Hirata
2005-03-18 Kazu Hirata <kazu@cs.umass.edu>
* tree-into-ssa.c (find_idf): Use VEC_quick_push instead of
VEC_safe_push.
Index: tree-into-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-into-ssa.c,v
retrieving revision 2.44
diff -C5 -d -p -r2.44 tree-into-ssa.c
*** tree-into-ssa.c 13 Mar 2005 13:31:01 -0000 2.44
--- tree-into-ssa.c 18 Mar 2005 03:36:29 -0000
*************** find_idf (bitmap def_blocks, bitmap *dfs
*** 509,519 ****
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 (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
--- 509,523 ----
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)
! /* We use VEC_quick_push here for speed. This is safe because we
! know that the number of definition blocks is no greater than
! the number of basic blocks, which is the initial capacity of
! WORK_STACK. */
! VEC_quick_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