[Bug tree-optimization/15524] [4.0 Regression] jump threading on trees is slow with switch statements with large # of cases
Jeffrey A Law
law@redhat.com
Mon Nov 22 17:52:00 GMT 2004
It's clearly getting more difficult to find compile-time improvements
for 15524. But that doesn't mean we're done :-)
As it turns out we've got more code which is just inlined versions
of find_edge, but without the ability to select which list (src->succ
or dest->pred) to walk depending on their lengths.
This patch replaces those inlined instances of find_edge with calls
to find_edge. The big winner is tree CFG construction which goes
from .40 seconds to around .04 seconds. There are other wins
scattered throughout the various passes. In all we go from 11.63
seconds of total time to 10.97 seconds of total time -- a net
improvement of around 5%.
[ Please don't close this PR. I still think there's another 4-5%
that we'll be able to get without major surgery. ]
Bootstrapped and regression tested on i686-pc-linux-gnu.
-------------- next part --------------
* cfg.c (cached_make_edge): Use find_edge rather than an inlined
variant.
* cfgbuild.c (make_edges): Likewise.
* cfghooks.c (can_duplicate_block_p): Likewise.
* cfgloop.c (loop_latch_edge): Likewise.
* cfgloopmanip.c (force_single_succ_latches): Likewise.
* cfgrtl.c (rtl_flow_call_edges_add): Likewise.
* predict.c (predict_loops, propagate_freq): Likewise.
* tracer.c (tail_duplicate): Likewise.
* tree-cfg.c (disband_implicit_edges): Likewise.
(tree_forwarder_block_p, tree_flow_call_edges_add): Likewise.
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.76
diff -c -p -r1.76 cfg.c
*** cfg.c 22 Nov 2004 12:23:43 -0000 1.76
--- cfg.c 22 Nov 2004 16:57:55 -0000
*************** cached_make_edge (sbitmap *edge_cache, b
*** 288,294 ****
{
int use_edge_cache;
edge e;
- edge_iterator ei;
/* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
many edges to them, or we didn't allocate memory for it. */
--- 288,293 ----
*************** cached_make_edge (sbitmap *edge_cache, b
*** 309,320 ****
/* Fall through. */
case 0:
! FOR_EACH_EDGE (e, ei, src->succs)
! if (e->dest == dst)
! {
! e->flags |= flags;
! return NULL;
! }
break;
}
--- 308,319 ----
/* Fall through. */
case 0:
! e = find_edge (src, dst);
! if (e)
! {
! e->flags |= flags;
! return NULL;
! }
break;
}
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgbuild.c,v
retrieving revision 1.55
diff -c -p -r1.55 cfgbuild.c
*** cfgbuild.c 28 Sep 2004 07:59:42 -0000 1.55
--- cfgbuild.c 22 Nov 2004 16:57:55 -0000
*************** make_edges (basic_block min, basic_block
*** 271,277 ****
enum rtx_code code;
int force_fallthru = 0;
edge e;
- edge_iterator ei;
if (LABEL_P (BB_HEAD (bb))
&& LABEL_ALT_ENTRY_P (BB_HEAD (bb)))
--- 271,276 ----
*************** make_edges (basic_block min, basic_block
*** 390,401 ****
/* Find out if we can drop through to the next block. */
insn = NEXT_INSN (insn);
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU)
! {
! insn = 0;
! break;
! }
while (insn
&& NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
--- 389,398 ----
/* Find out if we can drop through to the next block. */
insn = NEXT_INSN (insn);
! e = find_edge (bb, EXIT_BLOCK_PTR);
! if (e && e->flags & EDGE_FALLTHRU)
! insn = NULL;
!
while (insn
&& NOTE_P (insn)
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK)
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.19
diff -c -p -r1.19 cfghooks.c
*** cfghooks.c 20 Nov 2004 05:02:28 -0000 1.19
--- cfghooks.c 22 Nov 2004 16:57:55 -0000
*************** bool
*** 675,681 ****
can_duplicate_block_p (basic_block bb)
{
edge e;
- edge_iterator ei;
if (!cfg_hooks->can_duplicate_block_p)
internal_error ("%s does not support can_duplicate_block_p.",
--- 675,680 ----
*************** can_duplicate_block_p (basic_block bb)
*** 686,694 ****
/* Duplicating fallthru block to exit would require adding a jump
and splitting the real last BB. */
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == EXIT_BLOCK_PTR && e->flags & EDGE_FALLTHRU)
! return false;
return cfg_hooks->can_duplicate_block_p (bb);
}
--- 685,693 ----
/* Duplicating fallthru block to exit would require adding a jump
and splitting the real last BB. */
! e = find_edge (bb, EXIT_BLOCK_PTR);
! if (e && (e->flags & EDGE_FALLTHRU))
! return false;
return cfg_hooks->can_duplicate_block_p (bb);
}
Index: cfgloop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloop.c,v
retrieving revision 1.43
diff -c -p -r1.43 cfgloop.c
*** cfgloop.c 22 Nov 2004 12:23:44 -0000 1.43
--- cfgloop.c 22 Nov 2004 16:57:56 -0000
*************** verify_loop_structure (struct loops *loo
*** 1499,1512 ****
edge
loop_latch_edge (const struct loop *loop)
{
! edge e;
! edge_iterator ei;
!
! FOR_EACH_EDGE (e, ei, loop->header->preds)
! if (e->src == loop->latch)
! break;
!
! return e;
}
/* Returns preheader edge of LOOP. */
--- 1499,1505 ----
edge
loop_latch_edge (const struct loop *loop)
{
! return find_edge (loop->latch, loop->header);
}
/* Returns preheader edge of LOOP. */
Index: cfgloopmanip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgloopmanip.c,v
retrieving revision 1.37
diff -c -p -r1.37 cfgloopmanip.c
*** cfgloopmanip.c 22 Nov 2004 12:23:45 -0000 1.37
--- cfgloopmanip.c 22 Nov 2004 16:57:56 -0000
*************** force_single_succ_latches (struct loops
*** 1221,1234 ****
for (i = 1; i < loops->num; i++)
{
- edge_iterator ei;
loop = loops->parray[i];
if (loop->latch != loop->header && EDGE_COUNT (loop->latch->succs) == 1)
continue;
! FOR_EACH_EDGE (e, ei, loop->header->preds)
! if (e->src == loop->latch)
! break;
loop_split_edge_with (e, NULL_RTX);
}
--- 1221,1231 ----
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop->latch != loop->header && EDGE_COUNT (loop->latch->succs) == 1)
continue;
! e = find_edge (loop->latch, loop->header);
loop_split_edge_with (e, NULL_RTX);
}
Index: cfgrtl.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgrtl.c,v
retrieving revision 1.147
diff -c -p -r1.147 cfgrtl.c
*** cfgrtl.c 22 Nov 2004 12:23:45 -0000 1.147
--- cfgrtl.c 22 Nov 2004 16:57:57 -0000
*************** rtl_flow_call_edges_add (sbitmap blocks)
*** 2972,2986 ****
if (need_fake_edge_p (insn))
{
edge e;
- edge_iterator ei;
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == EXIT_BLOCK_PTR)
! {
! insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
! commit_edge_insertions ();
! break;
! }
}
}
--- 2972,2984 ----
if (need_fake_edge_p (insn))
{
edge e;
! e = find_edge (bb, EXIT_BLOCK_PTR);
! if (e)
! {
! insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
! commit_edge_insertions ();
! }
}
}
*************** rtl_flow_call_edges_add (sbitmap blocks)
*** 3023,3031 ****
#ifdef ENABLE_CHECKING
if (split_at_insn == BB_END (bb))
{
! edge_iterator ei;
! FOR_EACH_EDGE (e, ei, bb->succs)
! gcc_assert (e->dest != EXIT_BLOCK_PTR);
}
#endif
--- 3021,3028 ----
#ifdef ENABLE_CHECKING
if (split_at_insn == BB_END (bb))
{
! e = find_edge (bb, EXIT_BLOCK_PTR);
! gcc_assert (e == NULL);
}
#endif
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.134
diff -c -p -r1.134 predict.c
*** predict.c 19 Nov 2004 00:03:14 -0000 1.134
--- predict.c 22 Nov 2004 16:57:58 -0000
*************** predict_loops (struct loops *loops_info,
*** 669,681 ****
/* Loop branch heuristics - predict an edge back to a
loop's head as taken. */
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == loop->header
! && e->src == loop->latch)
! {
! header_found = 1;
! predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
! }
/* Loop exit heuristics - predict an edge exiting the loop if the
conditional has no loop header successors as not taken. */
--- 669,683 ----
/* Loop branch heuristics - predict an edge back to a
loop's head as taken. */
! if (bb == loop->latch)
! {
! e = find_edge (loop->latch, loop->header);
! if (e)
! {
! header_found = 1;
! predict_edge_def (e, PRED_LOOP_BRANCH, TAKEN);
! }
! }
/* Loop exit heuristics - predict an edge exiting the loop if the
conditional has no loop header successors as not taken. */
*************** propagate_freq (struct loop *loop, bitma
*** 1660,1680 ****
bitmap_clear_bit (tovisit, bb->index);
! /* Compute back edge frequencies. */
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == head)
! {
! sreal tmp;
! /* EDGE_INFO (e)->back_edge_prob
! = ((e->probability * BLOCK_INFO (bb)->frequency)
! / REG_BR_PROB_BASE); */
! sreal_init (&tmp, e->probability, 0);
! sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
! sreal_mul (&EDGE_INFO (e)->back_edge_prob,
! &tmp, &real_inv_br_prob_base);
! }
/* Propagate to successor blocks. */
FOR_EACH_EDGE (e, ei, bb->succs)
--- 1662,1681 ----
bitmap_clear_bit (tovisit, bb->index);
! e = find_edge (bb, head);
! if (e)
! {
! sreal tmp;
! /* EDGE_INFO (e)->back_edge_prob
! = ((e->probability * BLOCK_INFO (bb)->frequency)
! / REG_BR_PROB_BASE); */
! sreal_init (&tmp, e->probability, 0);
! sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
! sreal_mul (&EDGE_INFO (e)->back_edge_prob,
! &tmp, &real_inv_br_prob_base);
! }
/* Propagate to successor blocks. */
FOR_EACH_EDGE (e, ei, bb->succs)
Index: tracer.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tracer.c,v
retrieving revision 1.22
diff -c -p -r1.22 tracer.c
*** tracer.c 28 Sep 2004 07:59:50 -0000 1.22
--- tracer.c 22 Nov 2004 16:57:58 -0000
*************** tail_duplicate (void)
*** 275,286 ****
&& can_duplicate_block_p (bb2))
{
edge e;
- edge_iterator ei;
basic_block old = bb2;
! FOR_EACH_EDGE (e, ei, bb2->preds)
! if (e->src == bb)
! break;
nduplicated += counts [bb2->index];
bb2 = duplicate_block (bb2, e);
--- 275,283 ----
&& can_duplicate_block_p (bb2))
{
edge e;
basic_block old = bb2;
! e = find_edge (bb, bb2);
nduplicated += counts [bb2->index];
bb2 = duplicate_block (bb2, e);
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.112
diff -c -p -r2.112 tree-cfg.c
*** tree-cfg.c 19 Nov 2004 22:14:35 -0000 2.112
--- tree-cfg.c 22 Nov 2004 16:57:59 -0000
*************** disband_implicit_edges (void)
*** 2649,2659 ****
from cfg_remove_useless_stmts here since it violates the
invariants for tree--cfg correspondence and thus fits better
here where we do it anyway. */
! FOR_EACH_EDGE (e, ei, bb->succs)
{
- if (e->dest != bb->next_bb)
- continue;
-
if (e->flags & EDGE_TRUE_VALUE)
COND_EXPR_THEN (stmt) = build_empty_stmt ();
else if (e->flags & EDGE_FALSE_VALUE)
--- 2649,2657 ----
from cfg_remove_useless_stmts here since it violates the
invariants for tree--cfg correspondence and thus fits better
here where we do it anyway. */
! e = find_edge (bb, bb->next_bb);
! if (e)
{
if (e->flags & EDGE_TRUE_VALUE)
COND_EXPR_THEN (stmt) = build_empty_stmt ();
else if (e->flags & EDGE_FALSE_VALUE)
*************** static bool
*** 3892,3899 ****
tree_forwarder_block_p (basic_block bb)
{
block_stmt_iterator bsi;
- edge e;
- edge_iterator ei;
/* BB must have a single outgoing edge. */
if (EDGE_COUNT (bb->succs) != 1
--- 3890,3895 ----
*************** tree_forwarder_block_p (basic_block bb)
*** 3911,3920 ****
gcc_assert (bb != ENTRY_BLOCK_PTR);
#endif
! /* Successors of the entry block are not forwarders. */
! FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
! if (e->dest == bb)
! return false;
/* Now walk through the statements. We can ignore labels, anything else
means this is not a forwarder block. */
--- 3907,3914 ----
gcc_assert (bb != ENTRY_BLOCK_PTR);
#endif
! if (find_edge (ENTRY_BLOCK_PTR, bb))
! return false;
/* Now walk through the statements. We can ignore labels, anything else
means this is not a forwarder block. */
*************** tree_flow_call_edges_add (sbitmap blocks
*** 5206,5212 ****
Handle this by adding a dummy instruction in a new last basic block. */
if (check_last_block)
{
- edge_iterator ei;
basic_block bb = EXIT_BLOCK_PTR->prev_bb;
block_stmt_iterator bsi = bsi_last (bb);
tree t = NULL_TREE;
--- 5200,5205 ----
*************** tree_flow_call_edges_add (sbitmap blocks
*** 5217,5229 ****
{
edge e;
! FOR_EACH_EDGE (e, ei, bb->succs)
! if (e->dest == EXIT_BLOCK_PTR)
! {
! bsi_insert_on_edge (e, build_empty_stmt ());
! bsi_commit_edge_inserts ();
! break;
! }
}
}
--- 5210,5221 ----
{
edge e;
! e = find_edge (bb, EXIT_BLOCK_PTR);
! if (e)
! {
! bsi_insert_on_edge (e, build_empty_stmt ());
! bsi_commit_edge_inserts ();
! }
}
}
*************** tree_flow_call_edges_add (sbitmap blocks
*** 5260,5268 ****
#ifdef ENABLE_CHECKING
if (stmt == last_stmt)
{
! edge_iterator ei;
! FOR_EACH_EDGE (e, ei, bb->succs)
! gcc_assert (e->dest != EXIT_BLOCK_PTR);
}
#endif
--- 5252,5259 ----
#ifdef ENABLE_CHECKING
if (stmt == last_stmt)
{
! e = find_edge (bb, EXIT_BLOCK_PTR);
! gcc_assert (e == NULL);
}
#endif
More information about the Gcc-patches
mailing list