This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
cfg_cleanup speedup
> cfg cleanup : 33.59 (21%) usr 0.01 ( 0%) sys 33.69 (20%) wall
Hope that the attached patch will capture large portion of this time.
It avoids exploring of RTL stream by remembering what blocks are forwarders and
what not. It also adds code to update life info, so I will be able to
integrate better jump threading, we can avoidlife recomputation after combine
and perhaps we can remove the interaction between life propagation and
cfg_cleanup done in flow.c
Bootstrapped/regtested athlon.
Thu Oct 18 00:36:11 CEST 2001 Jan Hubicka <jh@suse.cz>
* toplev.c (rest_of_compilation): Use CLEANUP_UPDATE_LIFE
to avoid update_life_info call.
* basic-block.h (CLEANUP_UPATE_LIFE): Define.
* cfgcleanup.c (bb_flags): New enum.
(BB_FLAGS, BB_SET_FLAG, BB_CLEAR_FLAG, FORWARDER_BLOCK_P): New macros.
(notice_new_block, update_forwarder_flag): New functions.
(try_simplify_condjump): Use FORWARDER_BLOCK_P.
(try_forward_edges): Likewise; update flags.
(merge_blocks): Likewise.
(outgoing_edges_match): Likewise.
(try_crossjump_to_edge): Likewise.
(try_optimize_cfg): Likewise; initialize and clear the flags;
recompute life info if needed.
(cleanup_cfg): No need to clear aux pointers.
*** toplev.c.oldo Thu Oct 18 00:04:19 2001
--- toplev.c Thu Oct 18 00:04:21 2001
*************** rest_of_compilation (decl)
*** 3332,3351 ****
rebuild_jump_labels (insns);
timevar_pop (TV_JUMP);
! timevar_push (TV_FLOW);
! cleanup_cfg (CLEANUP_EXPENSIVE);
!
! /* Blimey. We've got to have the CFG up to date for the call to
! if_convert below. However, the random deletion of blocks
! without updating life info can wind up with Wierd Stuff in
! global_live_at_end. We then run sched1, which updates things
! properly, discovers the wierdness and aborts. */
! allocate_bb_life_data ();
! update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
! PROP_DEATH_NOTES | PROP_KILL_DEAD_CODE
! | PROP_SCAN_DEAD_CODE);
!
! timevar_pop (TV_FLOW);
}
close_dump_file (DFI_combine, print_rtl_with_bb, insns);
--- 3332,3338 ----
rebuild_jump_labels (insns);
timevar_pop (TV_JUMP);
! cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE);
}
close_dump_file (DFI_combine, print_rtl_with_bb, insns);
*** cfgcleanup.c.old Wed Oct 17 22:55:20 2001
--- cfgcleanup.c Thu Oct 18 00:09:42 2001
*************** Software Foundation, 59 Temple Place - S
*** 45,50 ****
--- 45,67 ----
#include "obstack.h"
+ /* cleanup_cfg maitains following flags for each basic block. */
+ enum bb_flags {
+ /* Set if life info needs to be recomputed for given BB. */
+ BB_UPDATE_LIFE = 1,
+ /* Set if BB is the forwarder block to avoid too many
+ forwarder_block_p calls. */
+ BB_FORWARDER_BLOCK = 2
+ };
+
+ #define BB_FLAGS(bb) (enum bb_flags)(bb)->aux
+ #define BB_SET_FLAG(bb,flag) \
+ (bb)->aux = (void *)((enum bb_flags)(bb)->aux | (flag))
+ #define BB_CLEAR_FLAG(bb,flag) \
+ (bb)->aux = (void *)((enum bb_flags)(bb)->aux & ~(flag))
+
+ #define FORWARDER_BLOCK_P(bb) (BB_FLAGS(bb) & BB_FORWARDER_BLOCK)
+
static bool try_crossjump_to_edge PARAMS ((int, edge, edge));
static bool try_crossjump_bb PARAMS ((int, basic_block));
static bool outgoing_edges_match PARAMS ((basic_block, basic_block));
*************** static bool merge_blocks PARAMS ((edge,
*** 62,67 ****
--- 79,111 ----
static bool try_optimize_cfg PARAMS ((int));
static bool try_simplify_condjump PARAMS ((basic_block));
static bool try_forward_edges PARAMS ((int, basic_block));
+ static void notice_new_block PARAMS ((basic_block));
+ static void update_forwarder_flag PARAMS ((basic_block));
+
+ /* Set flags for newly created block. */
+
+ static void
+ notice_new_block (bb)
+ basic_block bb;
+ {
+ if (!bb)
+ return;
+ BB_SET_FLAG (bb, BB_UPDATE_LIFE);
+ if (forwarder_block_p (bb))
+ BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
+ }
+
+ /* Recompute forwarder flag after block has been modified. */
+
+ static void
+ update_forwarder_flag (bb)
+ basic_block bb;
+ {
+ if (forwarder_block_p (bb))
+ BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
+ else
+ BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
+ }
/* Simplify a conditional jump around an unconditional jump.
Return true if something changed. */
*************** try_simplify_condjump (cbranch_block)
*** 95,101 ****
jump_block = cbranch_fallthru_edge->dest;
if (jump_block->pred->pred_next
|| jump_block->index == n_basic_blocks - 1
! || !forwarder_block_p (jump_block))
return false;
jump_dest_block = jump_block->succ->dest;
--- 139,145 ----
jump_block = cbranch_fallthru_edge->dest;
if (jump_block->pred->pred_next
|| jump_block->index == n_basic_blocks - 1
! || !FORWARDER_BLOCK_P (jump_block))
return false;
jump_dest_block = jump_block->succ->dest;
*************** try_forward_edges (mode, b)
*** 163,169 ****
/* Look for the real destination of the jump.
Avoid inifinite loop in the infinite empty loop by counting
up to n_basic_blocks. */
! while (forwarder_block_p (target)
&& target->succ->dest != EXIT_BLOCK_PTR
&& counter < n_basic_blocks)
{
--- 207,213 ----
/* Look for the real destination of the jump.
Avoid inifinite loop in the infinite empty loop by counting
up to n_basic_blocks. */
! while (FORWARDER_BLOCK_P (target)
&& target->succ->dest != EXIT_BLOCK_PTR
&& counter < n_basic_blocks)
{
*************** try_forward_edges (mode, b)
*** 220,225 ****
--- 264,273 ----
+ REG_BR_PROB_BASE / 2)
/ REG_BR_PROB_BASE);
+ if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
+ BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
+ BB_SET_FLAG (b, BB_UPDATE_LIFE);
+
do
{
first->count -= edge_count;
*************** merge_blocks (e, b, c, mode)
*** 384,389 ****
--- 432,438 ----
if (e->flags & EDGE_FALLTHRU)
{
merge_blocks_nomove (b, c);
+ update_forwarder_flag (b);
if (rtl_dump_file)
{
*************** merge_blocks (e, b, c, mode)
*** 405,411 ****
eliminated by edge redirection instead. One exception might have
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,
--- 454,460 ----
eliminated by edge redirection instead. One exception might have
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,
*************** merge_blocks (e, b, c, mode)
*** 441,447 ****
{
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
return false;
! force_nonfallthru (b_fallthru_edge);
}
merge_blocks_move_predecessor_nojumps (b, c);
return true;
--- 490,497 ----
{
if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
return false;
! BB_SET_FLAG (b_fallthru_edge, BB_UPDATE_LIFE);
! notice_new_block (force_nonfallthru (b_fallthru_edge));
}
merge_blocks_move_predecessor_nojumps (b, c);
return true;
*************** outgoing_edges_match (bb1, bb2)
*** 681,698 ****
/* Get around possible forwarders on fallthru edges. Other cases
should be optimized out already. */
! if (forwarder_block_p (f1->dest))
f1 = f1->dest->succ;
! if (forwarder_block_p (f2->dest))
f2 = f2->dest->succ;
/* To simplify use of this function, return false if there are
unneeded forwarder blocks. These will get eliminated later
during cleanup_cfg. */
! if (forwarder_block_p (f1->dest)
! || forwarder_block_p (f2->dest)
! || forwarder_block_p (b1->dest)
! || forwarder_block_p (b2->dest))
return false;
if (f1->dest == f2->dest && b1->dest == b2->dest)
--- 731,748 ----
/* Get around possible forwarders on fallthru edges. Other cases
should be optimized out already. */
! if (FORWARDER_BLOCK_P (f1->dest))
f1 = f1->dest->succ;
! if (FORWARDER_BLOCK_P (f2->dest))
f2 = f2->dest->succ;
/* To simplify use of this function, return false if there are
unneeded forwarder blocks. These will get eliminated later
during cleanup_cfg. */
! if (FORWARDER_BLOCK_P (f1->dest)
! || FORWARDER_BLOCK_P (f2->dest)
! || FORWARDER_BLOCK_P (b1->dest)
! || FORWARDER_BLOCK_P (b2->dest))
return false;
if (f1->dest == f2->dest && b1->dest == b2->dest)
*************** try_crossjump_to_edge (mode, e1, e2)
*** 795,808 ****
conditional jump that is required due to the current CFG shape. */
if (src1->pred
&& !src1->pred->pred_next
! && forwarder_block_p (src1))
{
e1 = src1->pred;
src1 = e1->src;
}
if (src2->pred
&& !src2->pred->pred_next
! && forwarder_block_p (src2))
{
e2 = src2->pred;
src2 = e2->src;
--- 845,858 ----
conditional jump that is required due to the current CFG shape. */
if (src1->pred
&& !src1->pred->pred_next
! && FORWARDER_BLOCK_P (src1))
{
e1 = src1->pred;
src1 = e1->src;
}
if (src2->pred
&& !src2->pred->pred_next
! && FORWARDER_BLOCK_P (src2))
{
e2 = src2->pred;
src2 = e2->src;
*************** try_crossjump_to_edge (mode, e1, e2)
*** 815,825 ****
return false;
/* Seeing more than 1 forwarder blocks would confuse us later... */
! if (forwarder_block_p (e1->dest)
! && forwarder_block_p (e1->dest->succ->dest))
return false;
! if (forwarder_block_p (e2->dest)
! && forwarder_block_p (e2->dest->succ->dest))
return false;
/* Likewise with dead code (possibly newly created by the other optimizations
--- 865,875 ----
return false;
/* Seeing more than 1 forwarder blocks would confuse us later... */
! if (FORWARDER_BLOCK_P (e1->dest)
! && FORWARDER_BLOCK_P (e1->dest->succ->dest))
return false;
! if (FORWARDER_BLOCK_P (e2->dest)
! && FORWARDER_BLOCK_P (e2->dest->succ->dest))
return false;
/* Likewise with dead code (possibly newly created by the other optimizations
*************** try_crossjump_to_edge (mode, e1, e2)
*** 867,878 ****
edge s2;
basic_block d = s->dest;
! if (forwarder_block_p (d))
d = d->succ->dest;
for (s2 = src1->succ; ; s2 = s2->succ_next)
{
basic_block d2 = s2->dest;
! if (forwarder_block_p (d2))
d2 = d2->succ->dest;
if (d == d2)
break;
--- 917,928 ----
edge s2;
basic_block d = s->dest;
! if (FORWARDER_BLOCK_P (d))
d = d->succ->dest;
for (s2 = src1->succ; ; s2 = s2->succ_next)
{
basic_block d2 = s2->dest;
! if (FORWARDER_BLOCK_P (d2))
d2 = d2->succ->dest;
if (d == d2)
break;
*************** try_crossjump_to_edge (mode, e1, e2)
*** 882,894 ****
/* Take care to update possible forwarder blocks. We verified
that there is no more than one in the chain, so we can't run
into infinite loop. */
! if (forwarder_block_p (s->dest))
{
s->dest->succ->count += s2->count;
s->dest->count += s2->count;
s->dest->frequency += EDGE_FREQUENCY (s);
}
! if (forwarder_block_p (s2->dest))
{
s2->dest->succ->count -= s2->count;
s2->dest->count -= s2->count;
--- 932,944 ----
/* Take care to update possible forwarder blocks. We verified
that there is no more than one in the chain, so we can't run
into infinite loop. */
! if (FORWARDER_BLOCK_P (s->dest))
{
s->dest->succ->count += s2->count;
s->dest->count += s2->count;
s->dest->frequency += EDGE_FREQUENCY (s);
}
! if (FORWARDER_BLOCK_P (s2->dest))
{
s2->dest->succ->count -= s2->count;
s2->dest->count -= s2->count;
*************** try_crossjump_to_edge (mode, e1, e2)
*** 935,940 ****
--- 985,993 ----
remove_edge (src1->succ);
make_single_succ_edge (src1, redirect_to, 0);
+ BB_SET_FLAG (src1, BB_UPDATE_LIFE);
+ update_forwarder_flag (src1);
+
return true;
}
*************** try_optimize_cfg (mode)
*** 1048,1057 ****
--- 1101,1114 ----
bool changed_overall = false;
bool changed;
int iterations = 0;
+ sbitmap blocks;
if (mode & CLEANUP_CROSSJUMP)
add_noreturn_fake_exit_edges ();
+ for (i = 0; i < n_basic_blocks; i++)
+ update_forwarder_flag (BASIC_BLOCK (i));
+
/* Attempt to merge blocks as made possible by edge removal. If a block
has only one successor, and the successor has only one predecessor,
they may be combined. */
*************** try_optimize_cfg (mode)
*** 1108,1114 ****
if (b->pred->pred_next == NULL
&& (b->pred->flags & EDGE_FALLTHRU)
&& GET_CODE (b->head) != CODE_LABEL
! && forwarder_block_p (b)
/* Note that forwarder_block_p true ensures that there
is a successor for this block. */
&& (b->succ->flags & EDGE_FALLTHRU)
--- 1165,1171 ----
if (b->pred->pred_next == NULL
&& (b->pred->flags & EDGE_FALLTHRU)
&& GET_CODE (b->head) != CODE_LABEL
! && FORWARDER_BLOCK_P (b)
/* Note that forwarder_block_p true ensures that there
is a successor for this block. */
&& (b->succ->flags & EDGE_FALLTHRU)
*************** try_optimize_cfg (mode)
*** 1151,1157 ****
&& b->succ->dest != EXIT_BLOCK_PTR
&& onlyjump_p (b->end)
&& redirect_edge_and_branch (b->succ, b->succ->dest))
! changed_here = true;
/* Simplify branch to branch. */
if (try_forward_edges (mode, b))
--- 1208,1218 ----
&& b->succ->dest != EXIT_BLOCK_PTR
&& onlyjump_p (b->end)
&& redirect_edge_and_branch (b->succ, b->succ->dest))
! {
! BB_SET_FLAG (b, BB_UPDATE_LIFE);
! update_forwarder_flag (b);
! changed_here = true;
! }
/* Simplify branch to branch. */
if (try_forward_edges (mode, b))
*************** try_optimize_cfg (mode)
*** 1186,1191 ****
--- 1247,1271 ----
if (mode & CLEANUP_CROSSJUMP)
remove_fake_edges ();
+ if ((mode & CLEANUP_UPDATE_LIFE) & changed_overall)
+ {
+ bool found = 0;
+ blocks = sbitmap_alloc (n_basic_blocks);
+ for (i = 0; i < n_basic_blocks; i++)
+ if (BB_FLAGS (BASIC_BLOCK (i)) & BB_UPDATE_LIFE)
+ {
+ found = 1;
+ SET_BIT (blocks, i);
+ }
+ if (found)
+ update_life_info (blocks, UPDATE_LIFE_GLOBAL,
+ PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
+ | PROP_KILL_DEAD_CODE);
+ sbitmap_free (blocks);
+ }
+ for (i = 0; i < n_basic_blocks; i++)
+ BASIC_BLOCK (i)->aux = NULL;
+
return changed_overall;
}
*************** cleanup_cfg (mode)
*** 1235,1242 ****
free_EXPR_LIST_list (&tail_recursion_label_list);
timevar_pop (TV_CLEANUP_CFG);
- /* Clear bb->aux on all basic blocks. */
- for (i = 0; i < n_basic_blocks; ++i)
- BASIC_BLOCK (i)->aux = NULL;
return changed;
}
--- 1315,1319 ----
*** basic-block.h Thu Oct 18 00:35:25 2001
--- basic-block.h.old Thu Oct 18 00:35:15 2001
*************** enum update_life_extent
*** 574,579 ****
--- 574,580 ----
inside call_placeholders.. */
#define CLEANUP_PRE_LOOP 16 /* Take care to preserve syntactic loop
notes. */
+ #define CLEANUP_UPDATE_LIFE 32 /* Update life info. */
/* Flags for loop discovery. */