This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
flow speed regression [Re: How long should -O1 compiles take?]
- To: Brad Lucier <lucier at math dot purdue dot edu>
- Subject: flow speed regression [Re: How long should -O1 compiles take?]
- From: Richard Henderson <rth at cygnus dot com>
- Date: Tue, 5 Oct 1999 12:13:44 -0700
- Cc: law at cygnus dot com, gcc at gcc dot gnu dot org, hosking at cs dot purdue dot edu, feeley at iro dot umontreal dot ca, gcc-patches at gcc dot gnu dot org
- References: <199910050159.UAA24316@polya.math.purdue.edu>
On Mon, Oct 04, 1999 at 08:59:01PM -0500, Brad Lucier wrote:
> flow: 176.880000 177.050000 38.220000
> flow2: 177.160000 176.380000 N/A
I hadn't been previously aware of this sort of regression.
Brad provided me with the test case -- it turns out to be
really very simple.
The test case is what appears to be a threaded state machine,
i.e. extremely heavy use of computed goto. This results in
a CFG that is nearly fully connected. A profile showed that
we were spending fully half of the runtime of the entire
program in make_edge, walking the list of existing edges
looking for duplicates.
The following patch introduces a 2D bitmap to cache edge
existance. I only create the cache when there's label values
floating about, since that's the only time I can imagine that
we could get into the kind of trouble we do above. In other
cases the bitmap should be so sparse as to be useless.
Anyway, I now get
time in flow: 39.160000 (12%)
time in flow2: 39.740000 (13%)
on one of our ultras.
r~
* flow.c (make_edge): Accept an optional 2D bitmap in which
to cache edge existence. Update all callers.
(make_label_edge, make_eh_edge): Pass through the edge cache.
(make_edges): Provide the cache.
Index: flow.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/flow.c,v
retrieving revision 1.163
diff -c -p -d -r1.163 flow.c
*** flow.c 1999/10/05 04:12:33 1.163
--- flow.c 1999/10/05 19:00:04
*************** static rtx find_basic_blocks_1 PROTO((r
*** 280,289 ****
static void create_basic_block PROTO((int, rtx, rtx, rtx));
static void clear_edges PROTO((void));
static void make_edges PROTO((rtx));
! static void make_edge PROTO((basic_block, basic_block, int));
! static void make_label_edge PROTO((basic_block, rtx, int));
! static void make_eh_edge PROTO((eh_nesting_info *, basic_block,
rtx, int));
static void mark_critical_edges PROTO((void));
static void move_stray_eh_region_notes PROTO((void));
static void record_active_eh_regions PROTO((rtx));
--- 280,291 ----
static void create_basic_block PROTO((int, rtx, rtx, rtx));
static void clear_edges PROTO((void));
static void make_edges PROTO((rtx));
! static void make_edge PROTO((sbitmap *, basic_block,
! basic_block, int));
! static void make_label_edge PROTO((sbitmap *, basic_block,
rtx, int));
+ static void make_eh_edge PROTO((sbitmap *, eh_nesting_info *,
+ basic_block, rtx, int));
static void mark_critical_edges PROTO((void));
static void move_stray_eh_region_notes PROTO((void));
static void record_active_eh_regions PROTO((rtx));
*************** make_edges (label_value_list)
*** 879,890 ****
{
int i;
eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
/* Assume no computed jump; revise as we create edges. */
current_function_has_computed_jump = 0;
/* By nature of the way these get numbered, block 0 is always the entry. */
! make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
for (i = 0; i < n_basic_blocks; ++i)
{
--- 881,902 ----
{
int i;
eh_nesting_info *eh_nest_info = init_eh_nesting_info ();
+ sbitmap *edge_cache = NULL;
/* Assume no computed jump; revise as we create edges. */
current_function_has_computed_jump = 0;
+ /* Heavy use of computed goto in machine-generated code can lead to
+ nearly fully-connected CFGs. In that case we spend a significant
+ amount of time searching the edge lists for duplicates. */
+ if (forced_labels || label_value_list)
+ {
+ edge_cache = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ sbitmap_vector_zero (edge_cache, n_basic_blocks);
+ }
+
/* By nature of the way these get numbered, block 0 is always the entry. */
! make_edge (edge_cache, ENTRY_BLOCK_PTR, BASIC_BLOCK (0), EDGE_FALLTHRU);
for (i = 0; i < n_basic_blocks; ++i)
{
*************** make_edges (label_value_list)
*** 920,926 ****
vec = XVEC (PATTERN (tmp), 1);
for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
! make_label_edge (bb, XEXP (RTVEC_ELT (vec, j), 0), 0);
/* Some targets (eg, ARM) emit a conditional jump that also
contains the out-of-range target. Scan for these and
--- 932,939 ----
vec = XVEC (PATTERN (tmp), 1);
for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
! make_label_edge (edge_cache, bb,
! XEXP (RTVEC_ELT (vec, j), 0), 0);
/* Some targets (eg, ARM) emit a conditional jump that also
contains the out-of-range target. Scan for these and
*************** make_edges (label_value_list)
*** 929,935 ****
&& SET_DEST (tmp) == pc_rtx
&& GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
&& GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
! make_label_edge (bb, XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
#ifdef CASE_DROPS_THROUGH
/* Silly VAXen. The ADDR_VEC is going to be in the way of
--- 942,949 ----
&& SET_DEST (tmp) == pc_rtx
&& GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
&& GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
! make_label_edge (edge_cache, bb,
! XEXP (XEXP (SET_SRC (tmp), 2), 0), 0);
#ifdef CASE_DROPS_THROUGH
/* Silly VAXen. The ADDR_VEC is going to be in the way of
*************** make_edges (label_value_list)
*** 945,966 ****
current_function_has_computed_jump = 1;
for (x = label_value_list; x; x = XEXP (x, 1))
! make_label_edge (bb, XEXP (x, 0), EDGE_ABNORMAL);
for (x = forced_labels; x; x = XEXP (x, 1))
! make_label_edge (bb, XEXP (x, 0), EDGE_ABNORMAL);
}
/* Returns create an exit out. */
else if (returnjump_p (insn))
! make_edge (bb, EXIT_BLOCK_PTR, 0);
/* Otherwise, we have a plain conditional or unconditional jump. */
else
{
if (! JUMP_LABEL (insn))
abort ();
! make_label_edge (bb, JUMP_LABEL (insn), 0);
}
}
--- 959,980 ----
current_function_has_computed_jump = 1;
for (x = label_value_list; x; x = XEXP (x, 1))
! make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
for (x = forced_labels; x; x = XEXP (x, 1))
! make_label_edge (edge_cache, bb, XEXP (x, 0), EDGE_ABNORMAL);
}
/* Returns create an exit out. */
else if (returnjump_p (insn))
! make_edge (edge_cache, bb, EXIT_BLOCK_PTR, 0);
/* Otherwise, we have a plain conditional or unconditional jump. */
else
{
if (! JUMP_LABEL (insn))
abort ();
! make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
}
}
*************** make_edges (label_value_list)
*** 975,981 ****
/* If there's an EH region active at the end of a block,
add the appropriate edges. */
if (bb->eh_end >= 0)
! make_eh_edge (eh_nest_info, bb, insn, bb->eh_end);
/* If we have asynchronous exceptions, do the same for *all*
exception regions active in the block. */
--- 989,995 ----
/* If there's an EH region active at the end of a block,
add the appropriate edges. */
if (bb->eh_end >= 0)
! make_eh_edge (edge_cache, eh_nest_info, bb, insn, bb->eh_end);
/* If we have asynchronous exceptions, do the same for *all*
exception regions active in the block. */
*************** make_edges (label_value_list)
*** 983,989 ****
&& bb->eh_beg != bb->eh_end)
{
if (bb->eh_beg >= 0)
! make_eh_edge (eh_nest_info, bb, NULL_RTX, bb->eh_beg);
for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
if (GET_CODE (x) == NOTE
--- 997,1004 ----
&& bb->eh_beg != bb->eh_end)
{
if (bb->eh_beg >= 0)
! make_eh_edge (edge_cache, eh_nest_info, bb,
! NULL_RTX, bb->eh_beg);
for (x = bb->head; x != bb->end; x = NEXT_INSN (x))
if (GET_CODE (x) == NOTE
*************** make_edges (label_value_list)
*** 991,997 ****
|| NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
{
int region = NOTE_EH_HANDLER (x);
! make_eh_edge (eh_nest_info, bb, NULL_RTX, region);
}
}
--- 1006,1013 ----
|| NOTE_LINE_NUMBER (x) == NOTE_INSN_EH_REGION_END))
{
int region = NOTE_EH_HANDLER (x);
! make_eh_edge (edge_cache, eh_nest_info, bb,
! NULL_RTX, region);
}
}
*************** make_edges (label_value_list)
*** 1009,1015 ****
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
if (!note || XINT (XEXP (note, 0), 0) >= 0)
for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
! make_label_edge (bb, XEXP (x, 0),
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
}
}
--- 1025,1031 ----
rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
if (!note || XINT (XEXP (note, 0), 0) >= 0)
for (x = nonlocal_goto_handler_labels; x ; x = XEXP (x, 1))
! make_label_edge (edge_cache, bb, XEXP (x, 0),
EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
}
}
*************** make_edges (label_value_list)
*** 1020,1061 ****
returns to one of the eh_stub labels within it. So we have to
make additional edges in the flow graph. */
if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
! make_label_edge (bb, eh_return_stub_label, EDGE_EH);
/* Find out if we can drop through to the next block. */
insn = next_nonnote_insn (insn);
if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
! make_edge (bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
else if (i + 1 < n_basic_blocks)
{
rtx tmp = BLOCK_HEAD (i + 1);
if (GET_CODE (tmp) == NOTE)
tmp = next_nonnote_insn (tmp);
if (force_fallthru || insn == tmp)
! make_edge (bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
}
}
free_eh_nesting_info (eh_nest_info);
}
/* Create an edge between two basic blocks. FLAGS are auxiliary information
about the edge that is accumulated between calls. */
static void
! make_edge (src, dst, flags)
basic_block src, dst;
int flags;
{
edge e;
! /* Make sure we don't add duplicate edges. */
! for (e = src->succ; e ; e = e->succ_next)
! if (e->dest == dst)
! {
! e->flags |= flags;
! return;
! }
e = (edge) xcalloc (1, sizeof (*e));
--- 1036,1088 ----
returns to one of the eh_stub labels within it. So we have to
make additional edges in the flow graph. */
if (i + 1 == n_basic_blocks && eh_return_stub_label != 0)
! make_label_edge (edge_cache, bb, eh_return_stub_label, EDGE_EH);
/* Find out if we can drop through to the next block. */
insn = next_nonnote_insn (insn);
if (!insn || (i + 1 == n_basic_blocks && force_fallthru))
! make_edge (edge_cache, bb, EXIT_BLOCK_PTR, EDGE_FALLTHRU);
else if (i + 1 < n_basic_blocks)
{
rtx tmp = BLOCK_HEAD (i + 1);
if (GET_CODE (tmp) == NOTE)
tmp = next_nonnote_insn (tmp);
if (force_fallthru || insn == tmp)
! make_edge (edge_cache, bb, BASIC_BLOCK (i + 1), EDGE_FALLTHRU);
}
}
+
free_eh_nesting_info (eh_nest_info);
+ if (edge_cache)
+ sbitmap_vector_free (edge_cache);
}
/* Create an edge between two basic blocks. FLAGS are auxiliary information
about the edge that is accumulated between calls. */
static void
! make_edge (edge_cache, src, dst, flags)
! sbitmap *edge_cache;
basic_block src, dst;
int flags;
{
+ int use_edge_cache;
edge e;
! /* Don't bother with edge cache for ENTRY or EXIT; there aren't that
! many edges to them, and we didn't allocate memory for it. */
! use_edge_cache = (edge_cache
! && src != ENTRY_BLOCK_PTR
! && dst != EXIT_BLOCK_PTR);
! /* Make sure we don't add duplicate edges. */
! if (! use_edge_cache || TEST_BIT (edge_cache[src->index], dst->index))
! for (e = src->succ; e ; e = e->succ_next)
! if (e->dest == dst)
! {
! e->flags |= flags;
! return;
! }
e = (edge) xcalloc (1, sizeof (*e));
*************** make_edge (src, dst, flags)
*** 1067,1078 ****
src->succ = e;
dst->pred = e;
}
/* Create an edge from a basic block to a label. */
static void
! make_label_edge (src, label, flags)
basic_block src;
rtx label;
int flags;
--- 1094,1109 ----
src->succ = e;
dst->pred = e;
+
+ if (use_edge_cache)
+ SET_BIT (edge_cache[src->index], dst->index);
}
/* Create an edge from a basic block to a label. */
static void
! make_label_edge (edge_cache, src, label, flags)
! sbitmap *edge_cache;
basic_block src;
rtx label;
int flags;
*************** make_label_edge (src, label, flags)
*** 1088,1100 ****
if (INSN_UID (label) == 0)
return;
! make_edge (src, BLOCK_FOR_INSN (label), flags);
}
/* Create the edges generated by INSN in REGION. */
static void
! make_eh_edge (eh_nest_info, src, insn, region)
eh_nesting_info *eh_nest_info;
basic_block src;
rtx insn;
--- 1119,1132 ----
if (INSN_UID (label) == 0)
return;
! make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
}
/* Create the edges generated by INSN in REGION. */
static void
! make_eh_edge (edge_cache, eh_nest_info, src, insn, region)
! sbitmap *edge_cache;
eh_nesting_info *eh_nest_info;
basic_block src;
rtx insn;
*************** make_eh_edge (eh_nest_info, src, insn, r
*** 1107,1113 ****
num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
while (--num >= 0)
{
! make_label_edge (src, handler_list[num]->handler_label,
EDGE_ABNORMAL | EDGE_EH | is_call);
}
}
--- 1139,1145 ----
num = reachable_handlers (region, eh_nest_info, insn, &handler_list);
while (--num >= 0)
{
! make_label_edge (edge_cache, src, handler_list[num]->handler_label,
EDGE_ABNORMAL | EDGE_EH | is_call);
}
}
*************** add_noreturn_fake_exit_edges ()
*** 6989,6993 ****
for (x = 0; x < n_basic_blocks; x++)
if (BASIC_BLOCK (x)->succ == NULL)
! make_edge (BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
}
--- 7021,7025 ----
for (x = 0; x < n_basic_blocks; x++)
if (BASIC_BLOCK (x)->succ == NULL)
! make_edge (NULL, BASIC_BLOCK (x), EXIT_BLOCK_PTR, EDGE_FAKE);
}