This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[3.3/mainline] cfg_cleanup speedup
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org, rth at redhat dot com
- Date: Sun, 9 Mar 2003 17:53:37 +0100
- Subject: [3.3/mainline] cfg_cleanup speedup
Hi,
While investigating the reason of compiler slowdown caused by
-funit-at-a-time on GCC bootstrap, I noticed that it all appears to come
from single file -insn-recog.c.
Most of it is quadratic time complexity of compute_transp in gcse, but
18% is also spent in cfg_cleanup by reducing number of iterations over
the function from 10 to 2 in the first pass. This patch cuts it to 7%.
The problem is that merging blocks moves the current block to forward
making the iteration to skip most of the changes.
(still same trick should be possible for crossjumping where we do 9
iterations, will try it later)
Honza
Sun Mar 9 17:51:39 CET 2003 Jan Hubicka <jh at suse dot cz>
* cfgcleanup.c (merge_blocks): Return where to iterate next.
(try_optimize_cfg): Use return value of merge_blocks
Index: cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.74
diff -c -3 -p -r1.74 cfgcleanup.c
*** cfgcleanup.c 22 Feb 2003 10:02:29 -0000 1.74
--- cfgcleanup.c 9 Mar 2003 16:33:27 -0000
*************** static void merge_blocks_move_predecesso
*** 81,87 ****
basic_block));
static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
basic_block));
! static bool merge_blocks PARAMS ((edge,basic_block,basic_block,
int));
static bool try_optimize_cfg PARAMS ((int));
static bool try_simplify_condjump PARAMS ((basic_block));
--- 81,87 ----
basic_block));
static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
basic_block));
! static basic_block merge_blocks PARAMS ((edge,basic_block,basic_block,
int));
static bool try_optimize_cfg PARAMS ((int));
static bool try_simplify_condjump PARAMS ((basic_block));
*************** merge_blocks_move_successor_nojumps (a,
*** 788,801 ****
}
/* Attempt to merge basic blocks that are potentially non-adjacent.
! Return true iff the attempt succeeded. */
! static bool
merge_blocks (e, b, c, mode)
edge e;
basic_block b, c;
int mode;
{
/* If C has a tail recursion label, do not merge. There is no
edge recorded from the call_placeholder back to this label, as
that would make optimize_sibling_and_tail_recursive_calls more
--- 788,811 ----
}
/* Attempt to merge basic blocks that are potentially non-adjacent.
! Return NULL iff the attempt failed, otherwise return basic block
! where cleanup_cfg should continue. Because the merging commonly
! moves basic block away or introduces another optimization
! possiblity, return basic block just before B so cleanup_cfg don't
! need to iterate.
!
! It may be good idea to return basic block before C in the case
! C has been moved after B and originally appeared earlier in the
! insn seqeunce, but we have no infromation available about the
! relative ordering of these two. Hopefully it is not too common. */
! static basic_block
merge_blocks (e, b, c, mode)
edge e;
basic_block b, c;
int mode;
{
+ basic_block next;
/* If C has a tail recursion label, do not merge. There is no
edge recorded from the call_placeholder back to this label, as
that would make optimize_sibling_and_tail_recursive_calls more
*************** merge_blocks (e, b, c, mode)
*** 803,809 ****
if ((mode & CLEANUP_PRE_SIBCALL)
&& GET_CODE (c->head) == CODE_LABEL
&& tail_recursion_label_p (c->head))
! return false;
/* If B has a fallthru edge to C, no need to move anything. */
if (e->flags & EDGE_FALLTHRU)
--- 813,819 ----
if ((mode & CLEANUP_PRE_SIBCALL)
&& GET_CODE (c->head) == CODE_LABEL
&& tail_recursion_label_p (c->head))
! return NULL;
/* If B has a fallthru edge to C, no need to move anything. */
if (e->flags & EDGE_FALLTHRU)
*************** merge_blocks (e, b, c, mode)
*** 816,822 ****
fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
b_index, c_index);
! return true;
}
/* Otherwise we will need to move code around. Do that only if expensive
--- 826,832 ----
fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
b_index, c_index);
! return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
}
/* Otherwise we will need to move code around. Do that only if expensive
*************** merge_blocks (e, b, c, mode)
*** 832,838 ****
been if B is a forwarder block and C has no fallthru edge, but
that should be cleaned up by bb-reorder instead. */
if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
! return false;
/* We must make sure to not munge nesting of lexical blocks,
and loop notes. This is done by squeezing out all the notes
--- 842,848 ----
been if B is a forwarder block and C has no fallthru edge, but
that should be cleaned up by bb-reorder instead. */
if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
! return NULL;
/* We must make sure to not munge nesting of lexical blocks,
and loop notes. This is done by squeezing out all the notes
*************** merge_blocks (e, b, c, mode)
*** 850,855 ****
--- 860,866 ----
b_has_incoming_fallthru = (tmp_edge != NULL);
b_fallthru_edge = tmp_edge;
+ next = b->prev_bb;
/* Otherwise, we're going to try to move C after B. If C does
not have an outgoing fallthru, then it can be moved
*************** merge_blocks (e, b, c, mode)
*** 857,863 ****
if (! c_has_outgoing_fallthru)
{
merge_blocks_move_successor_nojumps (b, c);
! return true;
}
/* If B does not have an incoming fallthru, then it can be moved
--- 868,874 ----
if (! c_has_outgoing_fallthru)
{
merge_blocks_move_successor_nojumps (b, c);
! return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
}
/* If B does not have an incoming fallthru, then it can be moved
*************** merge_blocks (e, b, c, mode)
*** 870,883 ****
basic_block bb;
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
! return false;
bb = force_nonfallthru (b_fallthru_edge);
if (bb)
notice_new_block (bb);
}
merge_blocks_move_predecessor_nojumps (b, c);
! return true;
}
return false;
--- 881,894 ----
basic_block bb;
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
! return NULL;
bb = force_nonfallthru (b_fallthru_edge);
if (bb)
notice_new_block (bb);
}
merge_blocks_move_predecessor_nojumps (b, c);
! return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
}
return false;
*************** try_optimize_cfg (mode)
*** 1560,1566 ****
bool changed_overall = false;
bool changed;
int iterations = 0;
! basic_block bb, b;
if (mode & CLEANUP_CROSSJUMP)
add_noreturn_fake_exit_edges ();
--- 1571,1577 ----
bool changed_overall = false;
bool changed;
int iterations = 0;
! basic_block bb, b, next;
if (mode & CLEANUP_CROSSJUMP)
add_noreturn_fake_exit_edges ();
*************** try_optimize_cfg (mode)
*** 1668,1675 ****
we can't kill the edge. */
&& (GET_CODE (b->end) != JUMP_INSN
|| simplejump_p (b->end))
! && merge_blocks (s, b, c, mode))
! changed_here = true;
/* Simplify branch over branch. */
if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
--- 1679,1689 ----
we can't kill the edge. */
&& (GET_CODE (b->end) != JUMP_INSN
|| simplejump_p (b->end))
! && (next = merge_blocks (s, b, c, mode)))
! {
! b = next;
! changed_here = true;
! }
/* Simplify branch over branch. */
if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))