This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Timing information for CFG manipulations
- To: Brad Lucier <lucier at math dot purdue dot edu>, gcc-patches at gcc dot gnu dot org, rth at cygnus dot com
- Subject: Re: Timing information for CFG manipulations
- From: Jan Hubicka <jh at suse dot cz>
- Date: Tue, 16 Oct 2001 17:01:37 +0200
- Cc: jh at suse dot cz, gcc at gcc dot gnu dot org
- References: <200110140332.f9E3W6I16651@banach.math.purdue.edu>
Hi,
this patch should track down the second problem:
> flow 2 : 267.66 (34%) usr 251.44 (98%) sys 519.08 (49%) wall
> 32.36 602.16 253.66 9556 26.54 26.54 sbitmap_vector_alloc
It makes find_sub_basic_blocks to operate at bitmap of blocks, instead of just
one and thus it avoids multiple initializations of edge cache structure.
The possible problem is that I now need to benerate bitmap when calling from
recog.c. I hope it won't cause perofrmance regression as the bitmap is
relativly small (compared to edge cache). If it will, I can use bitmap,
instead of sbitmap, that will add some overhead at split_all_insns side.
I don't have time to finish bootstrap, but the patch appears to work.
OK assuming the bootstrapping/regtesting i386 passes fluently?
Honza
Tue Oct 16 16:56:33 CEST 2001 Jan Hubicka <jh@suse.cz>
* basic-block.h (find_sub_basic_blocks): Use sbitmap parameter.
* cfgbuild.c (find_bb_boundaries): Break out from ...
(find_sub_basic_blocks): ... here; reorganize to handle multiple
basic blocks at once.
* cfgrtl.c (commite_one_edge_insertion): Create an bitmap to pass
to find_sub_basic_blocks.
* recog.c (split_all_insns): Update find_sub_basic_blocks call.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.123
diff -c -3 -p -r1.123 basic-block.h
*** basic-block.h 2001/10/11 12:43:38 1.123
--- basic-block.h 2001/10/16 14:54:27
*************** extern rtx block_label PARAMS ((basic_
*** 639,645 ****
extern bool forwarder_block_p PARAMS ((basic_block));
extern bool purge_all_dead_edges PARAMS ((void));
extern bool purge_dead_edges PARAMS ((basic_block));
! extern void find_sub_basic_blocks PARAMS ((basic_block));
extern bool can_fallthru PARAMS ((basic_block, basic_block));
extern void flow_nodes_print PARAMS ((const char *, const sbitmap,
FILE *));
--- 639,645 ----
extern bool forwarder_block_p PARAMS ((basic_block));
extern bool purge_all_dead_edges PARAMS ((void));
extern bool purge_dead_edges PARAMS ((basic_block));
! extern void find_sub_basic_blocks PARAMS ((sbitmap));
extern bool can_fallthru PARAMS ((basic_block, basic_block));
extern void flow_nodes_print PARAMS ((const char *, const sbitmap,
FILE *));
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgbuild.c,v
retrieving revision 1.7
diff -c -3 -p -r1.7 cfgbuild.c
*** cfgbuild.c 2001/10/11 03:15:24 1.7
--- cfgbuild.c 2001/10/16 14:54:28
*************** static void make_edges PARAMS ((rtx, i
*** 55,60 ****
--- 55,61 ----
static void make_label_edge PARAMS ((sbitmap *, basic_block,
rtx, int));
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
+ static void find_bb_boundaries PARAMS ((basic_block));
/* Count the basic blocks of the function. */
*************** make_edges (label_value_list, min, max,
*** 246,252 ****
}
/* By nature of the way these get numbered, block 0 is always the entry. */
! cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
for (i = min; i <= max; ++i)
{
--- 247,254 ----
}
/* By nature of the way these get numbered, block 0 is always the entry. */
! if (min == 0)
! cached_make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
for (i = min; i <= max; ++i)
{
*************** find_basic_blocks (f, nregs, file)
*** 663,680 ****
timevar_pop (TV_CFG);
}
! /* Assume that someone emitted code with control flow instructions to the
! basic block. Update the data structure. */
! void
! find_sub_basic_blocks (bb)
basic_block bb;
{
rtx insn = bb->head;
rtx end = bb->end;
rtx flow_transfer_insn = NULL_RTX;
edge fallthru = NULL;
- basic_block first_bb = bb;
- int i;
if (insn == bb->end)
return;
--- 665,691 ----
timevar_pop (TV_CFG);
}
! /* State of basic block as seen by find_sub_basic_blocks. */
! enum state
! {
! BLOCK_NEW = 0,
! BLOCK_ORIGINAL,
! BLOCK_TO_SPLIT
! };
! #define STATE(bb) (enum state)(size_t)(bb)->aux
! #define SET_STATE(bb, state) (bb)->aux = (void *)(state)
!
! /* Scan basic block BB for possible BB boundaries inside the block
! and create new basic blocks in the progress. */
!
! static void
! find_bb_boundaries (bb)
basic_block bb;
{
rtx insn = bb->head;
rtx end = bb->end;
rtx flow_transfer_insn = NULL_RTX;
edge fallthru = NULL;
if (insn == bb->end)
return;
*************** find_sub_basic_blocks (bb)
*** 694,700 ****
abort ();
break;
! /* On code label, split current basic block. */
case CODE_LABEL:
fallthru = split_block (bb, PREV_INSN (insn));
if (flow_transfer_insn)
--- 705,711 ----
abort ();
break;
! /* On code label, split current basic block. */
case CODE_LABEL:
fallthru = split_block (bb, PREV_INSN (insn));
if (flow_transfer_insn)
*************** find_sub_basic_blocks (bb)
*** 725,731 ****
{
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
! abort();
flow_transfer_insn = insn;
}
else if (code == CALL_INSN)
--- 736,742 ----
{
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
! abort ();
flow_transfer_insn = insn;
}
else if (code == CALL_INSN)
*************** find_sub_basic_blocks (bb)
*** 764,781 ****
followed by cleanup at fallthru edge, so the outgoing edges may
be dead. */
purge_dead_edges (bb);
/* Now re-scan and wire in all edges. This expect simple (conditional)
jumps at the end of each new basic blocks. */
! make_edges (NULL, first_bb->index, bb->index, 1);
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
! for (i = first_bb->index; i <= bb->index; i++)
{
edge e,f;
basic_block b = BASIC_BLOCK (i);
! if (b != first_bb)
{
b->count = 0;
b->frequency = 0;
--- 775,828 ----
followed by cleanup at fallthru edge, so the outgoing edges may
be dead. */
purge_dead_edges (bb);
+ }
+
+ /* Assume that someone emitted code with control flow instructions to the
+ basic block. Update the data structure. */
+ void
+ find_sub_basic_blocks (blocks)
+ sbitmap blocks;
+ {
+ int i;
+ int min, max;
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ SET_STATE (BASIC_BLOCK (i),
+ TEST_BIT (blocks, i)
+ ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
+ }
+
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ basic_block bb = BASIC_BLOCK (i);
+ if (STATE (bb) == BLOCK_TO_SPLIT)
+ find_bb_boundaries (bb);
+ }
+
+ for (i = 0; i < n_basic_blocks; i++)
+ if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
+ break;
+ min = max = i;
+ for (; i < n_basic_blocks; i++)
+ if (STATE (BASIC_BLOCK (i)) != BLOCK_ORIGINAL)
+ max = i;
+
/* Now re-scan and wire in all edges. This expect simple (conditional)
jumps at the end of each new basic blocks. */
! make_edges (NULL, min, max, 1);
/* Update branch probabilities. Expect only (un)conditional jumps
to be created with only the forward edges. */
! for (i = min; i <= max; i++)
{
edge e,f;
basic_block b = BASIC_BLOCK (i);
!
! if (STATE (b) == BLOCK_ORIGINAL)
! continue;
! if (STATE (b) == BLOCK_NEW)
{
b->count = 0;
b->frequency = 0;
*************** find_sub_basic_blocks (bb)
*** 810,813 ****
--- 857,862 ----
e->count = b->count;
}
}
+ for (i = 0; i < n_basic_blocks; i++)
+ SET_STATE (BASIC_BLOCK (i), 0);
}
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgrtl.c,v
retrieving revision 1.4
diff -c -3 -p -r1.4 cfgrtl.c
*** cfgrtl.c 2001/10/11 03:15:24 1.4
--- cfgrtl.c 2001/10/16 14:54:28
*************** commit_one_edge_insertion (e)
*** 1221,1226 ****
--- 1221,1227 ----
{
rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
basic_block bb;
+ sbitmap b;
/* Pull the insns off the edge now since the edge might go away. */
insns = e->insns;
*************** commit_one_edge_insertion (e)
*** 1314,1320 ****
}
else if (GET_CODE (last) == JUMP_INSN)
abort ();
! find_sub_basic_blocks (bb);
}
/* Update the CFG for all queued instructions. */
--- 1315,1325 ----
}
else if (GET_CODE (last) == JUMP_INSN)
abort ();
!
! b = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (b);
! SET_BIT (b, bb->index);
! find_sub_basic_blocks (b);
}
/* Update the CFG for all queued instructions. */
Index: recog.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/recog.c,v
retrieving revision 1.128
diff -c -3 -p -r1.128 recog.c
*** recog.c 2001/10/16 04:19:26 1.128
--- recog.c 2001/10/16 14:54:31
*************** split_all_insns (upd_life)
*** 2778,2785 ****
if (changed)
{
! for (i = 0; i < n_basic_blocks; i++)
! find_sub_basic_blocks (BASIC_BLOCK (i));
}
if (changed && upd_life)
--- 2778,2784 ----
if (changed)
{
! find_sub_basic_blocks (blocks);
}
if (changed && upd_life)