This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[tuples][patch] Tuplifying dce
- From: "Oleg Ryjkov" <olegr at google dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: "Diego Novillo" <dnovillo at google dot com>, "Jakub Staszak" <kuba at et dot pl>
- Date: Thu, 20 Mar 2008 16:16:03 -0700
- Subject: [tuples][patch] Tuplifying dce
Hi,
This is a patch from Jakub Staszak, with a minor bug fix. It tuplifies pass_dce.
Tested on i686-linux, no new regressions, several test cases fixed.
Oleg
2008-03-20 Jakub Staszak <kuba@et.pl>
Oleg Ryjkov <olegr@google.com>
* tree-ssa-sink.c (is_hidden_global_store): Tuplified.
* tree-ssa-dce.c (mark_stmt_necessary, mark_operand_necessary,
mark_stmt_if_obviously_necessary,
mark_control_dependent_edges_necessary,
find_obviously_necessary_stmts, propagate_necessity,
remove_dead_phis, eliminate_unnecessary_stmts, tree_dce_init,
tree_dce_done): Tuplified.
* tree-flow.h (is_hidden_global_store): Tuplified the declaration.
* passes.c (init_optimization_passes): Enabled pass_dce and
pass_cd_dce.
Index: tree-ssa-sink.c
===================================================================
--- tree-ssa-sink.c (revision 133397)
+++ tree-ssa-sink.c (working copy)
@@ -131,21 +131,23 @@ all_immediate_uses_same_place (tree stmt
return true;
}
+#endif
/* Some global stores don't necessarily have VDEF's of global variables,
but we still must avoid moving them around. */
bool
-is_hidden_global_store (tree stmt)
+is_hidden_global_store (gimple stmt)
{
/* Check virtual definitions. If we get here, the only virtual
- definitions we should see are those generated by assignment
+ definitions we should see are those generated by assignment or call
statements. */
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
{
tree lhs;
- gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
+ gcc_assert (gimple_code (stmt) == GIMPLE_ASSIGN
+ || gimple_code (stmt) == GIMPLE_CALL);
/* Note that we must not check the individual virtual operands
here. In particular, if this is an aliased store, we could
@@ -172,7 +174,8 @@ is_hidden_global_store (tree stmt)
address is a pointer, we check if its name tag or symbol tag is
a global variable. Otherwise, we check if the base variable
is a global. */
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ lhs = gimple_get_lhs (stmt);
+
if (REFERENCE_CLASS_P (lhs))
lhs = get_base_address (lhs);
@@ -212,6 +215,7 @@ is_hidden_global_store (tree stmt)
return false;
}
+#if 0
/* Find the nearest common dominator of all of the immediate uses in IMM. */
static basic_block
Index: ChangeLog.tuples
===================================================================
--- ChangeLog.tuples (revision 133397)
+++ ChangeLog.tuples (working copy)
@@ -1,3 +1,17 @@
+2008-03-20 Jakub Staszak <kuba@et.pl>
+ Oleg Ryjkov <olegr@google.com>
+
+ * tree-ssa-sink.c (is_hidden_global_store): Tuplified.
+ * tree-ssa-dce.c (mark_stmt_necessary, mark_operand_necessary,
+ mark_stmt_if_obviously_necessary,
+ mark_control_dependent_edges_necessary,
+ find_obviously_necessary_stmts, propagate_necessity,
+ remove_dead_phis, eliminate_unnecessary_stmts, tree_dce_init,
+ tree_dce_done): Tuplified.
+ * tree-flow.h (is_hidden_global_store): Tuplified the declaration.
+ * passes.c (init_optimization_passes): Enabled pass_dce and
+ pass_cd_dce.
+
2008-03-20 Oleg Ryjkov <olegr@google.com>
* tree-complex.c (init_dont_simulate_again, complex_visit_stmt,
Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c (revision 133397)
+++ tree-ssa-dce.c (working copy)
@@ -66,9 +66,7 @@ along with GCC; see the file COPYING3.
#include "flags.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
-
-/* FIXME tuples. */
-#if 0
+
static struct stmt_stats
{
int total;
@@ -77,7 +75,9 @@ static struct stmt_stats
int removed_phis;
} stats;
-static VEC(tree,heap) *worklist;
+#define STMT_NECESSARY GF_PLF_1
+
+static VEC(gimple,heap) *worklist;
/* Vector indicating an SSA name has already been processed and marked
as necessary. */
@@ -198,30 +198,26 @@ find_all_control_dependences (struct edg
find_control_dependence (el, i);
}
-
-#define NECESSARY(stmt) stmt->base.asm_written_flag
-
/* If STMT is not already marked necessary, mark it, and add it to the
worklist if ADD_TO_WORKLIST is true. */
static inline void
-mark_stmt_necessary (tree stmt, bool add_to_worklist)
+mark_stmt_necessary (gimple stmt, bool add_to_worklist)
{
gcc_assert (stmt);
- gcc_assert (!DECL_P (stmt));
- if (NECESSARY (stmt))
+ if (gimple_plf (stmt, STMT_NECESSARY))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Marking useful stmt: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
- NECESSARY (stmt) = 1;
+ gimple_set_plf (stmt, STMT_NECESSARY, true);
if (add_to_worklist)
- VEC_safe_push (tree, heap, worklist, stmt);
+ VEC_safe_push (gimple, heap, worklist, stmt);
}
@@ -230,7 +226,7 @@ mark_stmt_necessary (tree stmt, bool add
static inline void
mark_operand_necessary (tree op)
{
- tree stmt;
+ gimple stmt;
int ver;
gcc_assert (op);
@@ -243,11 +239,11 @@ mark_operand_necessary (tree op)
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (stmt);
- if (NECESSARY (stmt) || IS_EMPTY_STMT (stmt))
+ if (gimple_plf (stmt, STMT_NECESSARY) || gimple_nop_p (stmt))
return;
- NECESSARY (stmt) = 1;
- VEC_safe_push (tree, heap, worklist, stmt);
+ gimple_set_plf (stmt, STMT_NECESSARY, true);
+ VEC_safe_push (gimple, heap, worklist, stmt);
}
@@ -258,15 +254,13 @@ mark_operand_necessary (tree op)
necessary. */
static void
-mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
+mark_stmt_if_obviously_necessary (gimple stmt, bool aggressive)
{
- stmt_ann_t ann;
- tree op;
-
+ tree lhs = NULL_TREE;
/* With non-call exceptions, we have to assume that all statements could
throw. If a statement may throw, it is inherently necessary. */
if (flag_non_call_exceptions
- && tree_could_throw_p (stmt))
+ && stmt_could_throw_p (stmt))
{
mark_stmt_necessary (stmt, true);
return;
@@ -277,58 +271,58 @@ mark_stmt_if_obviously_necessary (tree s
they are control flow, and we have no way of knowing whether they can be
removed. DCE can eliminate all the other statements in a block, and CFG
can then remove the block and labels. */
- switch (TREE_CODE (stmt))
+ switch (gimple_code (stmt))
{
- case BIND_EXPR:
- case LABEL_EXPR:
- case CASE_LABEL_EXPR:
+ case GIMPLE_BIND:
+ case GIMPLE_LABEL:
mark_stmt_necessary (stmt, false);
return;
- case ASM_EXPR:
- case RESX_EXPR:
- case RETURN_EXPR:
- case CHANGE_DYNAMIC_TYPE_EXPR:
+ case GIMPLE_ASM:
+ case GIMPLE_RESX:
+ case GIMPLE_RETURN:
+ case GIMPLE_CHANGE_DYNAMIC_TYPE:
mark_stmt_necessary (stmt, true);
return;
- case CALL_EXPR:
+ case GIMPLE_CALL:
/* Most, but not all function calls are required. Function calls that
produce no result and have no side effects (i.e. const pure
functions) are unnecessary. */
- if (TREE_SIDE_EFFECTS (stmt))
- mark_stmt_necessary (stmt, true);
- return;
-
- case GIMPLE_MODIFY_STMT:
- op = get_call_expr_in (stmt);
- if (op && TREE_SIDE_EFFECTS (op))
+ if (gimple_has_side_effects (stmt))
{
mark_stmt_necessary (stmt, true);
return;
}
+ if (!gimple_call_lhs (stmt))
+ return;
+ lhs = gimple_call_lhs (stmt);
+ /* Fall through */
+ case GIMPLE_ASSIGN:
+ if (!lhs)
+ lhs = gimple_assign_lhs (stmt);
/* These values are mildly magic bits of the EH runtime. We can't
see the entire lifetime of these values until landing pads are
generated. */
- if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == EXC_PTR_EXPR
- || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == FILTER_EXPR)
+ if (TREE_CODE (lhs) == EXC_PTR_EXPR
+ || TREE_CODE (lhs) == FILTER_EXPR)
{
mark_stmt_necessary (stmt, true);
return;
}
break;
- case GOTO_EXPR:
+ case GIMPLE_GOTO:
gcc_assert (!simple_goto_p (stmt));
mark_stmt_necessary (stmt, true);
return;
- case COND_EXPR:
+ case GIMPLE_COND:
gcc_assert (EDGE_COUNT (gimple_bb (stmt)->succs) == 2);
/* Fall through. */
- case SWITCH_EXPR:
+ case GIMPLE_SWITCH:
if (! aggressive)
mark_stmt_necessary (stmt, true);
break;
@@ -337,12 +331,10 @@ mark_stmt_if_obviously_necessary (tree s
break;
}
- ann = stmt_ann (stmt);
-
/* If the statement has volatile operands, it needs to be preserved.
Same for statements that can alter control flow in unpredictable
ways. */
- if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
+ if (gimple_has_volatile_ops (stmt) || is_ctrl_altering_stmt (stmt))
{
mark_stmt_necessary (stmt, true);
return;
@@ -374,16 +366,16 @@ mark_control_dependent_edges_necessary (
EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
{
- tree t;
+ gimple stmt;
basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
if (TEST_BIT (last_stmt_necessary, cd_bb->index))
continue;
SET_BIT (last_stmt_necessary, cd_bb->index);
- t = last_stmt (cd_bb);
- if (t && is_ctrl_stmt (t))
- mark_stmt_necessary (t, true);
+ stmt = last_stmt (cd_bb);
+ if (stmt && is_ctrl_stmt (stmt))
+ mark_stmt_necessary (stmt, true);
}
}
@@ -399,22 +391,27 @@ static void
find_obviously_necessary_stmts (struct edge_list *el)
{
basic_block bb;
- block_stmt_iterator i;
+ gimple_stmt_iterator gsi;
edge e;
+ gimple_seq phis;
+ gimple phi, stmt;
FOR_EACH_BB (bb)
{
- tree phi;
-
+ phis = phi_nodes (bb);
/* PHI nodes are never inherently necessary. */
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- NECESSARY (phi) = 0;
+
+ for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ phi = gsi_stmt (gsi);
+ gimple_set_plf (phi, STMT_NECESSARY, false);
+ }
/* Check all statements in the block. */
- for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- tree stmt = bsi_stmt (i);
- NECESSARY (stmt) = 0;
+ stmt = gsi_stmt (gsi);
+ gimple_set_plf (stmt, STMT_NECESSARY, false);
mark_stmt_if_obviously_necessary (stmt, el != NULL);
}
}
@@ -444,21 +441,21 @@ find_obviously_necessary_stmts (struct e
static void
propagate_necessity (struct edge_list *el)
{
- tree stmt;
+ gimple stmt;
bool aggressive = (el ? true : false);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nProcessing worklist:\n");
- while (VEC_length (tree, worklist) > 0)
+ while (VEC_length (gimple, worklist) > 0)
{
/* Take STMT from worklist. */
- stmt = VEC_pop (tree, worklist);
+ stmt = VEC_pop (gimple, worklist);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "processing: ");
- print_generic_stmt (dump_file, stmt, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
@@ -476,7 +473,7 @@ propagate_necessity (struct edge_list *e
}
}
- if (TREE_CODE (stmt) == PHI_NODE)
+ if (gimple_code (stmt) == GIMPLE_PHI)
{
/* PHI nodes are somewhat special in that each PHI alternative has
data and control dependencies. All the statements feeding the
@@ -484,9 +481,9 @@ propagate_necessity (struct edge_list *e
we also consider the control dependent edges leading to the
predecessor block associated with each PHI alternative as
necessary. */
- int k;
+ size_t k;
- for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
+ for (k = 0; k < gimple_phi_num_args (stmt); k++)
{
tree arg = PHI_ARG_DEF (stmt, k);
if (TREE_CODE (arg) == SSA_NAME)
@@ -495,9 +492,9 @@ propagate_necessity (struct edge_list *e
if (aggressive)
{
- for (k = 0; k < PHI_NUM_ARGS (stmt); k++)
+ for (k = 0; k < gimple_phi_num_args (stmt); k++)
{
- basic_block arg_bb = PHI_ARG_EDGE (stmt, k)->src;
+ basic_block arg_bb = gimple_phi_arg_edge (stmt, k)->src;
if (arg_bb != ENTRY_BLOCK_PTR
&& ! TEST_BIT (visited_control_parents, arg_bb->index))
{
@@ -531,35 +528,33 @@ propagate_necessity (struct edge_list *e
static bool
remove_dead_phis (basic_block bb)
{
- tree prev, phi;
bool something_changed = false;
+ gimple_seq phis;
+ gimple phi;
+ gimple_stmt_iterator gsi;
+ phis = phi_nodes (bb);
- prev = NULL_TREE;
- phi = phi_nodes (bb);
- while (phi)
+ for (gsi = gsi_start (phis); !gsi_end_p (gsi);)
{
stats.total_phis++;
+ phi = gsi_stmt (gsi);
- if (! NECESSARY (phi))
+ if (!gimple_plf (phi, STMT_NECESSARY))
{
- tree next = PHI_CHAIN (phi);
-
something_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Deleting : ");
- print_generic_stmt (dump_file, phi, TDF_SLIM);
+ print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
- remove_phi_node (phi, prev, true);
+ remove_phi_node (&gsi, true);
stats.removed_phis++;
- phi = next;
}
else
{
- prev = phi;
- phi = PHI_CHAIN (phi);
+ gsi_next (&gsi);
}
}
return something_changed;
@@ -570,14 +565,14 @@ remove_dead_phis (basic_block bb)
containing I so that we don't have to look it up. */
static void
-remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
+remove_dead_stmt (gimple_stmt_iterator *i, basic_block bb)
{
- tree t = bsi_stmt (*i);
+ gimple stmt = gsi_stmt (*i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Deleting : ");
- print_generic_stmt (dump_file, t, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
@@ -589,7 +584,7 @@ remove_dead_stmt (block_stmt_iterator *i
immediate post-dominator. The blocks we are circumventing will be
removed by cleanup_tree_cfg if this change in the flow graph makes them
unreachable. */
- if (is_ctrl_stmt (t))
+ if (is_ctrl_stmt (stmt))
{
basic_block post_dom_bb;
@@ -651,8 +646,8 @@ remove_dead_stmt (block_stmt_iterator *i
}
}
- bsi_remove (i, true);
- release_defs (t);
+ gsi_remove (i, true);
+ release_defs (stmt);
}
@@ -664,7 +659,9 @@ eliminate_unnecessary_stmts (void)
{
bool something_changed = false;
basic_block bb;
- block_stmt_iterator i;
+ gimple_stmt_iterator gsi;
+ gimple stmt;
+ tree call;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nEliminating unnecessary statements:\n");
@@ -679,51 +676,56 @@ eliminate_unnecessary_stmts (void)
FOR_EACH_BB (bb)
{
/* Remove dead statements. */
- for (i = bsi_start (bb); ! bsi_end_p (i) ; )
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
{
- tree t = bsi_stmt (i);
+ stmt = gsi_stmt (gsi);
stats.total++;
- /* If `i' is not necessary then remove it. */
- if (! NECESSARY (t))
+ /* If GSI is not necessary then remove it. */
+ if (!gimple_plf (stmt, STMT_NECESSARY))
{
- remove_dead_stmt (&i, bb);
+ remove_dead_stmt (&gsi, bb);
something_changed = true;
}
- else
+ else if (gimple_code (stmt) == GIMPLE_CALL)
{
- tree call = get_call_expr_in (t);
+ call = gimple_call_fndecl (stmt);
if (call)
{
tree name;
+ gimple g;
/* When LHS of var = call (); is dead, simplify it into
call (); saving one operand. */
- if (TREE_CODE (t) == GIMPLE_MODIFY_STMT
- && (TREE_CODE ((name = GIMPLE_STMT_OPERAND (t, 0)))
- == SSA_NAME)
- && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
+ name = gimple_call_lhs (stmt);
+ if (name && TREE_CODE (name) == SSA_NAME
+ && !TEST_BIT (processed, SSA_NAME_VERSION (name)))
{
- tree oldlhs = GIMPLE_STMT_OPERAND (t, 0);
something_changed = true;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Deleting LHS of call: ");
- print_generic_stmt (dump_file, t, TDF_SLIM);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
fprintf (dump_file, "\n");
}
- push_stmt_changes (bsi_stmt_ptr (i));
- TREE_BLOCK (call) = TREE_BLOCK (t);
- bsi_replace (&i, call, false);
- maybe_clean_or_replace_eh_stmt (t, call);
- mark_symbols_for_renaming (call);
- pop_stmt_changes (bsi_stmt_ptr (i));
- release_ssa_name (oldlhs);
+
+ push_stmt_changes (gsi_stmt_ptr (&gsi));
+ g = gimple_copy (stmt);
+ gimple_call_set_lhs (g, NULL_TREE);
+ gsi_replace (&gsi, g, false);
+ maybe_clean_or_replace_eh_stmt (stmt, g);
+ mark_symbols_for_renaming (g);
+ pop_stmt_changes (gsi_stmt_ptr (&gsi));
+ release_ssa_name (name);
}
- notice_special_calls (call);
+ notice_special_calls (stmt);
}
- bsi_next (&i);
+ gsi_next (&gsi);
+ }
+ else
+ {
+ gsi_next (&gsi);
}
}
}
@@ -754,7 +756,7 @@ print_stats (void)
stats.removed_phis, stats.total_phis, (int) percg);
}
}
-
+
/* Initialization for this pass. Set up the used data structures. */
static void
@@ -777,7 +779,7 @@ tree_dce_init (bool aggressive)
processed = sbitmap_alloc (num_ssa_names + 1);
sbitmap_zero (processed);
- worklist = VEC_alloc (tree, heap, 64);
+ worklist = VEC_alloc (gimple, heap, 64);
cfg_altered = false;
}
@@ -800,9 +802,9 @@ tree_dce_done (bool aggressive)
sbitmap_free (processed);
- VEC_free (tree, heap, worklist);
+ VEC_free (gimple, heap, worklist);
}
-
+
/* Main routine to eliminate dead code.
AGGRESSIVE controls the aggressiveness of the algorithm.
@@ -954,4 +956,3 @@ struct tree_opt_pass pass_cd_dce =
| TODO_verify_flow, /* todo_flags_finish */
0 /* letter */
};
-#endif
Index: tree-flow.h
===================================================================
--- tree-flow.h (revision 133397)
+++ tree-flow.h (working copy)
@@ -1087,7 +1087,7 @@ tree vn_lookup (tree);
tree vn_lookup_with_vuses (tree, VEC (tree, gc) *);
/* In tree-ssa-sink.c */
-bool is_hidden_global_store (tree);
+bool is_hidden_global_store (gimple);
/* In tree-sra.c */
void insert_edge_copies (tree, basic_block);
Index: passes.c
===================================================================
--- passes.c (revision 133397)
+++ passes.c (working copy)
@@ -545,8 +545,8 @@ init_optimization_passes (void)
NEXT_PASS (pass_sra_early);
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_merge_phi);
- NEXT_PASS (pass_dce);
#endif
+ NEXT_PASS (pass_dce);
NEXT_PASS (pass_update_address_taken);
/* FIXME tuples. */
#if 0
@@ -605,12 +605,16 @@ init_optimization_passes (void)
#if 0
NEXT_PASS (pass_phiprop);
NEXT_PASS (pass_fre);
+#endif
NEXT_PASS (pass_dce);
+#if 0
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_copy_prop);
NEXT_PASS (pass_merge_phi);
NEXT_PASS (pass_vrp);
+#endif
NEXT_PASS (pass_dce);
+#if 0
NEXT_PASS (pass_cselim);
NEXT_PASS (pass_dominator);
/* The only const/copy propagation opportunities left after
@@ -640,9 +644,10 @@ init_optimization_passes (void)
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
-
NEXT_PASS (pass_reassoc);
+#endif
NEXT_PASS (pass_dce);
+#if 0
NEXT_PASS (pass_dse);
NEXT_PASS (pass_forwprop);
NEXT_PASS (pass_phiopt);
@@ -711,8 +716,9 @@ init_optimization_passes (void)
only examines PHIs to discover const/copy propagation
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
-
+#endif
NEXT_PASS (pass_cd_dce);
+#if 0
NEXT_PASS (pass_tracer);
/* FIXME: If DCE is not run before checking for uninitialized uses,