This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Removal of dead labels
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 1 May 2007 00:30:35 +0200
- Subject: [patch] Removal of dead labels
Hello,
with http://gcc.gnu.org/ml/gcc-patches/2007-04/msg01840.html, most of
the tree labels are unused once cfg is built. This patch makes us
remove those dead labels (we still keep user labels even if they are not
referenced, for debug info). This saves some peak memory, and the
optimization passes that traverse all statements are a bit faster, as
they do not need to skip the labels.
Additionally, the patch makes cfgexpand avoid creating new tree labels.
A few changes to code that did not handle empty blocks
(apply_return_prediction) or blocks not starting with a label
(rewrite_use_nonlinear_expr, vect_create_epilog_for_reduction)
were necessary.
The timings for combine.i compilation (-O2, with checking enabled)
without and with the patch:
TOTAL : 25.42 0.57 26.00 43480 kB
TOTAL : 24.48 0.43 25.21 42528 kB
Compilation of preprocessed gcc sources (-O2, checking disabled) is
faster by about 2-3% with the patch, on all architectures where I tested
it. Bootstrapped & regtested on i686, x86_64, ia64 and ppc64-linux.
Zdenek
* tree-ssa-loop-ivopts.c (rewrite_use_nonlinear_expr): Use
bsi_after_labels. Always insert statements before bsi.
* tree-vect-transform.c (vect_create_epilog_for_reduction): Ditto.
* predict.c (apply_return_prediction): Check for empty blocks.
* cfgexpand.c (lab_rtx_for_bb): New variable.
(label_rtx_for_bb): Do not create new tree labels.
(expand_gimple_basic_block): Add labels recorded in lab_rtx_for_bb.
(tree_expand_cfg): Initialize lab_rtx_for_bb.
* tree-cfg.c (build_tree_cfg): Call cleanup_dead_labels after
creating edges.
(label_for_bb): Add field used.
(update_eh_label, main_block_label): Mark the label used.
(cleanup_dead_labels): Remove unused labels.
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c (revision 124295)
--- tree-ssa-loop-ivopts.c (working copy)
*************** rewrite_use_nonlinear_expr (struct ivopt
*** 4866,4872 ****
{
tree comp;
tree op, stmts, tgt, ass;
! block_stmt_iterator bsi, pbsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
--- 4866,4872 ----
{
tree comp;
tree op, stmts, tgt, ass;
! block_stmt_iterator bsi;
/* An important special case -- if we are asked to express value of
the original iv by itself, just exit; there is no need to
*************** rewrite_use_nonlinear_expr (struct ivopt
*** 4937,4949 ****
if (name_info (data, tgt)->preserve_biv)
return;
! pbsi = bsi = bsi_start (bb_for_stmt (use->stmt));
! while (!bsi_end_p (pbsi)
! && TREE_CODE (bsi_stmt (pbsi)) == LABEL_EXPR)
! {
! bsi = pbsi;
! bsi_next (&pbsi);
! }
break;
case GIMPLE_MODIFY_STMT:
--- 4937,4943 ----
if (name_info (data, tgt)->preserve_biv)
return;
! bsi = bsi_after_labels (bb_for_stmt (use->stmt));
break;
case GIMPLE_MODIFY_STMT:
*************** rewrite_use_nonlinear_expr (struct ivopt
*** 4956,4977 ****
}
op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
if (TREE_CODE (use->stmt) == PHI_NODE)
{
- if (stmts)
- bsi_insert_after (&bsi, stmts, BSI_CONTINUE_LINKING);
ass = build_gimple_modify_stmt (tgt, op);
! bsi_insert_after (&bsi, ass, BSI_NEW_STMT);
remove_statement (use->stmt, false);
SSA_NAME_DEF_STMT (tgt) = ass;
}
else
! {
! if (stmts)
! bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
! GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
! }
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
--- 4950,4967 ----
}
op = force_gimple_operand (comp, &stmts, false, SSA_NAME_VAR (tgt));
+ if (stmts)
+ bsi_insert_before (&bsi, stmts, BSI_SAME_STMT);
if (TREE_CODE (use->stmt) == PHI_NODE)
{
ass = build_gimple_modify_stmt (tgt, op);
! bsi_insert_before (&bsi, ass, BSI_SAME_STMT);
remove_statement (use->stmt, false);
SSA_NAME_DEF_STMT (tgt) = ass;
}
else
! GIMPLE_STMT_OPERAND (use->stmt, 1) = op;
}
/* Replaces ssa name in index IDX by its basic variable. Callback for
Index: predict.c
===================================================================
*** predict.c (revision 124295)
--- predict.c (working copy)
*************** apply_return_prediction (int *heads)
*** 1240,1246 ****
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
return_stmt = last_stmt (e->src);
! if (TREE_CODE (return_stmt) == RETURN_EXPR)
break;
}
if (!e)
--- 1240,1247 ----
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
{
return_stmt = last_stmt (e->src);
! if (return_stmt
! && TREE_CODE (return_stmt) == RETURN_EXPR)
break;
}
if (!e)
Index: cfgexpand.c
===================================================================
*** cfgexpand.c (revision 124295)
--- cfgexpand.c (working copy)
*************** maybe_dump_rtl_for_tree_stmt (tree stmt,
*** 1244,1249 ****
--- 1244,1253 ----
}
}
+ /* Maps the blocks that do not contain tree labels to rtx labels. */
+
+ static struct pointer_map_t *lab_rtx_for_bb;
+
/* Returns the label_rtx expression for a label starting basic block BB. */
static rtx
*************** label_rtx_for_bb (basic_block bb)
*** 1251,1262 ****
{
tree_stmt_iterator tsi;
tree lab, lab_stmt;
if (bb->flags & BB_RTL)
return block_label (bb);
! /* We cannot use tree_block_label, as we no longer have stmt annotations.
! TODO -- avoid creating the new tree labels. */
for (tsi = tsi_start (bb_stmt_list (bb)); !tsi_end_p (tsi); tsi_next (&tsi))
{
lab_stmt = tsi_stmt (tsi);
--- 1255,1271 ----
{
tree_stmt_iterator tsi;
tree lab, lab_stmt;
+ void **elt;
if (bb->flags & BB_RTL)
return block_label (bb);
! elt = pointer_map_contains (lab_rtx_for_bb, bb);
! if (elt)
! return *elt;
!
! /* Find the tree label if it is present. */
!
for (tsi = tsi_start (bb_stmt_list (bb)); !tsi_end_p (tsi); tsi_next (&tsi))
{
lab_stmt = tsi_stmt (tsi);
*************** label_rtx_for_bb (basic_block bb)
*** 1270,1279 ****
return label_rtx (lab);
}
! lab = create_artificial_label ();
! lab_stmt = build1 (LABEL_EXPR, void_type_node, lab);
! tsi_link_before (&tsi, lab_stmt, TSI_NEW_STMT);
! return label_rtx (lab);
}
/* A subroutine of expand_gimple_basic_block. Expand one COND_EXPR.
--- 1279,1287 ----
return label_rtx (lab);
}
! elt = pointer_map_insert (lab_rtx_for_bb, bb);
! *elt = gen_label_rtx ();
! return *elt;
}
/* A subroutine of expand_gimple_basic_block. Expand one COND_EXPR.
*************** expand_gimple_basic_block (basic_block b
*** 1477,1482 ****
--- 1485,1491 ----
rtx note, last;
edge e;
edge_iterator ei;
+ void **elt;
if (dump_file)
{
*************** expand_gimple_basic_block (basic_block b
*** 1510,1529 ****
tsi = tsi_start (stmts);
if (!tsi_end_p (tsi))
! stmt = tsi_stmt (tsi);
! if (stmt && TREE_CODE (stmt) == LABEL_EXPR)
{
last = get_last_insn ();
! expand_expr_stmt (stmt);
/* Java emits line number notes in the top of labels.
??? Make this go away once line number notes are obsoleted. */
BB_HEAD (bb) = NEXT_INSN (last);
if (NOTE_P (BB_HEAD (bb)))
BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
- tsi_next (&tsi);
note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
maybe_dump_rtl_for_tree_stmt (stmt, last);
--- 1519,1550 ----
tsi = tsi_start (stmts);
if (!tsi_end_p (tsi))
! {
! stmt = tsi_stmt (tsi);
! if (TREE_CODE (stmt) != LABEL_EXPR)
! stmt = NULL_TREE;
! }
! elt = pointer_map_contains (lab_rtx_for_bb, bb);
!
! if (stmt || elt)
{
last = get_last_insn ();
! if (stmt)
! {
! expand_expr_stmt (stmt);
! tsi_next (&tsi);
! }
!
! if (elt)
! emit_label (*elt);
/* Java emits line number notes in the top of labels.
??? Make this go away once line number notes are obsoleted. */
BB_HEAD (bb) = NEXT_INSN (last);
if (NOTE_P (BB_HEAD (bb)))
BB_HEAD (bb) = NEXT_INSN (BB_HEAD (bb));
note = emit_note_after (NOTE_INSN_BASIC_BLOCK, BB_HEAD (bb));
maybe_dump_rtl_for_tree_stmt (stmt, last);
*************** tree_expand_cfg (void)
*** 1896,1903 ****
--- 1917,1926 ----
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
e->flags &= ~EDGE_EXECUTABLE;
+ lab_rtx_for_bb = pointer_map_create ();
FOR_BB_BETWEEN (bb, init_block->next_bb, EXIT_BLOCK_PTR, next_bb)
bb = expand_gimple_basic_block (bb);
+ pointer_map_destroy (lab_rtx_for_bb);
construct_exit_block ();
set_curr_insn_block (DECL_INITIAL (current_function_decl));
Index: tree-vect-transform.c
===================================================================
*** tree-vect-transform.c (revision 124295)
--- tree-vect-transform.c (working copy)
*************** vect_create_epilog_for_reduction (tree v
*** 1174,1180 ****
exit_bb = single_exit (loop)->dest;
new_phi = create_phi_node (SSA_NAME_VAR (vect_def), exit_bb);
SET_PHI_ARG_DEF (new_phi, single_exit (loop)->dest_idx, vect_def);
! exit_bsi = bsi_start (exit_bb);
/* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
(i.e. when reduc_code is not available) and in the final adjustment
--- 1174,1180 ----
exit_bb = single_exit (loop)->dest;
new_phi = create_phi_node (SSA_NAME_VAR (vect_def), exit_bb);
SET_PHI_ARG_DEF (new_phi, single_exit (loop)->dest_idx, vect_def);
! exit_bsi = bsi_after_labels (exit_bb);
/* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
(i.e. when reduc_code is not available) and in the final adjustment
*************** vect_create_epilog_for_reduction (tree v
*** 1223,1229 ****
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_temp = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
extract_scalar_result = true;
}
--- 1223,1229 ----
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_temp = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
extract_scalar_result = true;
}
*************** vect_create_epilog_for_reduction (tree v
*** 1280,1292 ****
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_name = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
tmp = build2 (code, vectype, new_name, new_temp);
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_temp = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
}
extract_scalar_result = true;
--- 1280,1292 ----
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_name = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
tmp = build2 (code, vectype, new_name, new_temp);
epilog_stmt = build_gimple_modify_stmt (vec_dest, tmp);
new_temp = make_ssa_name (vec_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
}
extract_scalar_result = true;
*************** vect_create_epilog_for_reduction (tree v
*** 1316,1322 ****
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
for (bit_offset = element_bitsize;
bit_offset < vec_size_in_bits;
--- 1316,1322 ----
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
for (bit_offset = element_bitsize;
bit_offset < vec_size_in_bits;
*************** vect_create_epilog_for_reduction (tree v
*** 1331,1343 ****
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
tmp = build2 (code, scalar_type, new_name, new_temp);
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, tmp);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
}
extract_scalar_result = false;
--- 1331,1343 ----
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_name;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
tmp = build2 (code, scalar_type, new_name, new_temp);
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, tmp);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
}
extract_scalar_result = false;
*************** vect_create_epilog_for_reduction (tree v
*** 1366,1372 ****
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
}
/* 2.4 Adjust the final result by the initial value of the reduction
--- 1366,1372 ----
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, rhs);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
}
/* 2.4 Adjust the final result by the initial value of the reduction
*************** vect_create_epilog_for_reduction (tree v
*** 1382,1388 ****
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, tmp);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
}
/* 2.6 Replace uses of s_out0 with uses of s_out3 */
--- 1382,1388 ----
epilog_stmt = build_gimple_modify_stmt (new_scalar_dest, tmp);
new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
GIMPLE_STMT_OPERAND (epilog_stmt, 0) = new_temp;
! bsi_insert_before (&exit_bsi, epilog_stmt, BSI_SAME_STMT);
}
/* 2.6 Replace uses of s_out0 with uses of s_out3 */
Index: tree-cfg.c
===================================================================
*** tree-cfg.c (revision 124295)
--- tree-cfg.c (working copy)
*************** build_tree_cfg (tree *tp)
*** 181,186 ****
--- 181,187 ----
/* Create the edges of the flowgraph. */
make_edges ();
+ cleanup_dead_labels ();
/* Debugging dumps. */
*************** make_goto_expr_edges (basic_block bb)
*** 830,840 ****
to do early because it allows us to group case labels before creating
the edges for the CFG, and it speeds up block statement iterators in
all passes later on.
! We only run this pass once, running it more than once is probably not
! profitable. */
/* A map from basic block index to the leading label of that block. */
! static tree *label_for_bb;
/* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
static void
--- 831,849 ----
to do early because it allows us to group case labels before creating
the edges for the CFG, and it speeds up block statement iterators in
all passes later on.
! We rerun this pass after CFG is created, to get rid of the labels that
! are no longer referenced. After then we do not run it any more, since
! (almost) no new labels should be created. */
/* A map from basic block index to the leading label of that block. */
! static struct label_record
! {
! /* The label. */
! tree label;
!
! /* True if the label is referenced from somewhere. */
! bool used;
! } *label_for_bb;
/* Callback for for_each_eh_region. Helper for cleanup_dead_labels. */
static void
*************** update_eh_label (struct eh_region *regio
*** 852,858 ****
if (! bb)
return;
! new_label = label_for_bb[bb->index];
set_eh_region_tree_label (region, new_label);
}
}
--- 861,868 ----
if (! bb)
return;
! new_label = label_for_bb[bb->index].label;
! label_for_bb[bb->index].used = true;
set_eh_region_tree_label (region, new_label);
}
}
*************** static tree
*** 862,872 ****
main_block_label (tree label)
{
basic_block bb = label_to_block (label);
/* label_to_block possibly inserted undefined label into the chain. */
! if (!label_for_bb[bb->index])
! label_for_bb[bb->index] = label;
! return label_for_bb[bb->index];
}
/* Cleanup redundant labels. This is a three-step process:
--- 872,888 ----
main_block_label (tree label)
{
basic_block bb = label_to_block (label);
+ tree main_label = label_for_bb[bb->index].label;
/* label_to_block possibly inserted undefined label into the chain. */
! if (!main_label)
! {
! label_for_bb[bb->index].label = label;
! main_label = label;
! }
!
! label_for_bb[bb->index].used = true;
! return main_label;
}
/* Cleanup redundant labels. This is a three-step process:
*************** void
*** 878,884 ****
cleanup_dead_labels (void)
{
basic_block bb;
! label_for_bb = XCNEWVEC (tree, last_basic_block);
/* Find a suitable label for each block. We use the first user-defined
label if there is one, or otherwise just the first label we see. */
--- 894,900 ----
cleanup_dead_labels (void)
{
basic_block bb;
! label_for_bb = XCNEWVEC (struct label_record, last_basic_block);
/* Find a suitable label for each block. We use the first user-defined
label if there is one, or otherwise just the first label we see. */
*************** cleanup_dead_labels (void)
*** 897,915 ****
/* If we have not yet seen a label for the current block,
remember this one and see if there are more labels. */
! if (! label_for_bb[bb->index])
{
! label_for_bb[bb->index] = label;
continue;
}
/* If we did see a label for the current block already, but it
is an artificially created label, replace it if the current
label is a user defined label. */
! if (! DECL_ARTIFICIAL (label)
! && DECL_ARTIFICIAL (label_for_bb[bb->index]))
{
! label_for_bb[bb->index] = label;
break;
}
}
--- 913,931 ----
/* If we have not yet seen a label for the current block,
remember this one and see if there are more labels. */
! if (!label_for_bb[bb->index].label)
{
! label_for_bb[bb->index].label = label;
continue;
}
/* If we did see a label for the current block already, but it
is an artificially created label, replace it if the current
label is a user defined label. */
! if (!DECL_ARTIFICIAL (label)
! && DECL_ARTIFICIAL (label_for_bb[bb->index].label))
{
! label_for_bb[bb->index].label = label;
break;
}
}
*************** cleanup_dead_labels (void)
*** 981,991 ****
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
! tree label_for_this_bb = label_for_bb[bb->index];
! if (! label_for_this_bb)
continue;
for (i = bsi_start (bb); !bsi_end_p (i); )
{
tree label, stmt = bsi_stmt (i);
--- 997,1011 ----
FOR_EACH_BB (bb)
{
block_stmt_iterator i;
! tree label_for_this_bb = label_for_bb[bb->index].label;
! if (!label_for_this_bb)
continue;
+ /* If the main label of the block is unused, we may still remove it. */
+ if (!label_for_bb[bb->index].used)
+ label_for_this_bb = NULL;
+
for (i = bsi_start (bb); !bsi_end_p (i); )
{
tree label, stmt = bsi_stmt (i);