/* Dead code elimination pass for the GNU compiler.
- Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
Contributed by Ben Elliston <bje@redhat.com>
and Andrew MacLeod <amacleod@redhat.com>
Adapted to use control dependence by Steven Bosscher, SUSE Labs.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* Dead code elimination.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
/* These RTL headers are needed for basic-block.h. */
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#include "basic-block.h"
#include "tree.h"
int removed_phis;
} stats;
-static varray_type worklist;
+static VEC(tree,heap) *worklist;
/* Vector indicating an SSA name has already been processed and marked
as necessary. */
use a bitmap for each block recording its edges. An array holds the
bitmap. The Ith bit in the bitmap is set if that block is dependent
on the Ith edge. */
-bitmap *control_dependence_map;
+static bitmap *control_dependence_map;
+
+/* Vector indicating that a basic block has already had all the edges
+ processed that it is control dependent on. */
+static sbitmap visited_control_parents;
+
+/* TRUE if this pass alters the CFG (by removing control statements).
+ FALSE otherwise.
+
+ If this pass alters the CFG, then it will arrange for the dominators
+ to be recomputed. */
+static bool cfg_altered;
/* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
for which the block with index N is control dependent. */
mark_stmt_necessary (tree stmt, bool add_to_worklist)
{
gcc_assert (stmt);
- gcc_assert (stmt != error_mark_node);
gcc_assert (!DECL_P (stmt));
if (NECESSARY (stmt))
NECESSARY (stmt) = 1;
if (add_to_worklist)
- VARRAY_PUSH_TREE (worklist, stmt);
+ VEC_safe_push (tree, heap, worklist, stmt);
}
/* Mark the statement defining operand OP as necessary. PHIONLY is true
return;
NECESSARY (stmt) = 1;
- VARRAY_PUSH_TREE (worklist, stmt);
+ VEC_safe_push (tree, heap, worklist, stmt);
}
\f
-/* Mark STMT as necessary if it is obviously is. Add it to the worklist if
+/* Mark STMT as necessary if it obviously is. Add it to the worklist if
it can make other statements necessary.
If AGGRESSIVE is false, control statements are conservatively marked as
static void
mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
{
- v_may_def_optype v_may_defs;
- v_must_def_optype v_must_defs;
stmt_ann_t ann;
tree op, def;
ssa_op_iter iter;
+ /* 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))
+ {
+ mark_stmt_necessary (stmt, true);
+ return;
+ }
+
/* Statements that are implicitly live. Most function calls, asm and return
statements are required. Labels and BIND_EXPR nodes are kept because
they are control flow, and we have no way of knowing whether they can be
return;
}
- get_stmt_operands (stmt);
-
FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
{
if (is_global_var (SSA_NAME_VAR (def)))
return;
}
}
-
- /* Check virtual definitions. If we get here, the only virtual
- definitions we should see are those generated by assignment
- statements. */
- v_may_defs = V_MAY_DEF_OPS (ann);
- v_must_defs = V_MUST_DEF_OPS (ann);
- if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
+ if (is_hidden_global_store (stmt))
{
- tree lhs;
-
- gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
-
- /* Note that we must not check the individual virtual operands
- here. In particular, if this is an aliased store, we could
- end up with something like the following (SSA notation
- redacted for brevity):
-
- foo (int *p, int i)
- {
- int x;
- p_1 = (i_2 > 3) ? &x : p_1;
-
- # x_4 = V_MAY_DEF <x_3>
- *p_1 = 5;
-
- return 2;
- }
-
- Notice that the store to '*p_1' should be preserved, if we
- were to check the virtual definitions in that store, we would
- not mark it needed. This is because 'x' is not a global
- variable.
-
- Therefore, we check the base address of the LHS. If the
- address is a pointer, we check if its name tag or type tag is
- a global variable. Otherwise, we check if the base variable
- is a global. */
- lhs = TREE_OPERAND (stmt, 0);
- if (REFERENCE_CLASS_P (lhs))
- lhs = get_base_address (lhs);
-
- if (lhs == NULL_TREE)
- {
- /* If LHS is NULL, it means that we couldn't get the base
- address of the reference. In which case, we should not
- remove this store. */
- mark_stmt_necessary (stmt, true);
- }
- else if (DECL_P (lhs))
- {
- /* If the store is to a global symbol, we need to keep it. */
- if (is_global_var (lhs))
- mark_stmt_necessary (stmt, true);
- }
- else if (INDIRECT_REF_P (lhs))
- {
- tree ptr = TREE_OPERAND (lhs, 0);
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
- tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
-
- /* If either the name tag or the type tag for PTR is a
- global variable, then the store is necessary. */
- if ((nmt && is_global_var (nmt))
- || (tmt && is_global_var (tmt)))
- {
- mark_stmt_necessary (stmt, true);
- return;
- }
- }
- else
- gcc_unreachable ();
+ mark_stmt_necessary (stmt, true);
+ return;
}
return;
NECESSARY (stmt) = 0;
mark_stmt_if_obviously_necessary (stmt, el != NULL);
}
-
- /* Mark this basic block as `not visited'. A block will be marked
- visited when the edges that it is control dependent on have been
- marked. */
- bb->flags &= ~BB_VISITED;
}
if (el)
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nProcessing worklist:\n");
- while (VARRAY_ACTIVE_SIZE (worklist) > 0)
+ while (VEC_length (tree, worklist) > 0)
{
/* Take `i' from worklist. */
- i = VARRAY_TOP_TREE (worklist);
- VARRAY_POP (worklist);
+ i = VEC_pop (tree, worklist);
if (dump_file && (dump_flags & TDF_DETAILS))
{
containing `i' is control dependent on, but only if we haven't
already done so. */
basic_block bb = bb_for_stmt (i);
- if (! (bb->flags & BB_VISITED))
+ if (bb != ENTRY_BLOCK_PTR
+ && ! TEST_BIT (visited_control_parents, bb->index))
{
- bb->flags |= BB_VISITED;
+ SET_BIT (visited_control_parents, bb->index);
mark_control_dependent_edges_necessary (bb, el);
}
}
for (k = 0; k < PHI_NUM_ARGS (i); k++)
{
basic_block arg_bb = PHI_ARG_EDGE (i, k)->src;
- if (! (arg_bb->flags & BB_VISITED))
+ if (arg_bb != ENTRY_BLOCK_PTR
+ && ! TEST_BIT (visited_control_parents, arg_bb->index))
{
- arg_bb->flags |= BB_VISITED;
+ SET_BIT (visited_control_parents, arg_bb->index);
mark_control_dependent_edges_necessary (arg_bb, el);
}
}
ssa_op_iter iter;
tree use;
- get_stmt_operands (i);
-
/* The operands of V_MAY_DEF expressions are also needed as they
represent potential definitions that may reach this
statement (V_MAY_DEF operands allow us to follow def-def
/* Mark all virtual phis still in use as necessary, and all of their
arguments that are phis as necessary. */
- while (VARRAY_ACTIVE_SIZE (worklist) > 0)
+ while (VEC_length (tree, worklist) > 0)
{
- tree use = VARRAY_TOP_TREE (worklist);
- VARRAY_POP (worklist);
+ tree use = VEC_pop (tree, worklist);
for (i = 0; i < PHI_NUM_ARGS (use); i++)
mark_operand_necessary (PHI_ARG_DEF (use, i), true);
{
/* Remove dead PHI nodes. */
remove_dead_phis (bb);
+ }
+ FOR_EACH_BB (bb)
+ {
/* Remove dead statements. */
for (i = bsi_start (bb); ! bsi_end_p (i) ; )
{
fprintf (dump_file, "\n");
}
- remove_phi_node (phi, prev, bb);
+ remove_phi_node (phi, prev);
stats.removed_phis++;
phi = next;
}
}
}
\f
-/* Remove dead statement pointed by iterator I. Receives the basic block BB
+/* Remove dead statement pointed to by iterator I. Receives the basic block BB
containing I so that we don't have to look it up. */
static void
nothing to the program, then we not only remove it, but we also change
the flow graph so that the current block will simply fall-thru to its
immediate post-dominator. The blocks we are circumventing will be
- removed by cleaup_cfg if this change in the flow graph makes them
+ removed by cleaup_tree_cfg if this change in the flow graph makes them
unreachable. */
if (is_ctrl_stmt (t))
{
basic_block post_dom_bb;
+
/* The post dominance info has to be up-to-date. */
gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
/* Get the immediate post dominator of bb. */
return;
}
- /* Redirect the first edge out of BB to reach POST_DOM_BB. */
- redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
- PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+ /* If the post dominator block has PHI nodes, we might be unable
+ to compute the right PHI args for them. Since the control
+ statement is unnecessary, all edges can be regarded as
+ equivalent, but we have to get rid of the condition, since it
+ might reference a variable that was determined to be
+ unnecessary and thus removed. */
+ if (phi_nodes (post_dom_bb))
+ post_dom_bb = EDGE_SUCC (bb, 0)->dest;
+ else
+ {
+ /* Redirect the first edge out of BB to reach POST_DOM_BB. */
+ redirect_edge_and_branch (EDGE_SUCC (bb, 0), post_dom_bb);
+ PENDING_STMT (EDGE_SUCC (bb, 0)) = NULL;
+ }
EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
EDGE_SUCC (bb, 0)->count = bb->count;
EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
/* Remove the remaining the outgoing edges. */
- while (EDGE_COUNT (bb->succs) != 1)
- remove_edge (EDGE_SUCC (bb, 1));
+ while (!single_succ_p (bb))
+ {
+ /* FIXME. When we remove the edge, we modify the CFG, which
+ in turn modifies the dominator and post-dominator tree.
+ Is it safe to postpone recomputing the dominator and
+ post-dominator tree until the end of this pass given that
+ the post-dominators are used above? */
+ cfg_altered = true;
+ remove_edge (EDGE_SUCC (bb, 1));
+ }
}
- FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter,
- SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS)
+ FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter, SSA_OP_VIRTUAL_DEFS)
{
tree def = DEF_FROM_PTR (def_p);
- bitmap_set_bit (vars_to_rename,
- var_ann (SSA_NAME_VAR (def))->uid);
+ mark_sym_for_renaming (SSA_NAME_VAR (def));
}
bsi_remove (i);
release_defs (t);
control_dependence_map
= xmalloc (last_basic_block * sizeof (bitmap));
for (i = 0; i < last_basic_block; ++i)
- control_dependence_map[i] = BITMAP_XMALLOC ();
+ control_dependence_map[i] = BITMAP_ALLOC (NULL);
last_stmt_necessary = sbitmap_alloc (last_basic_block);
sbitmap_zero (last_stmt_necessary);
processed = sbitmap_alloc (num_ssa_names + 1);
sbitmap_zero (processed);
- VARRAY_TREE_INIT (worklist, 64, "work list");
+ worklist = VEC_alloc (tree, heap, 64);
+ cfg_altered = false;
}
/* Cleanup after this pass. */
int i;
for (i = 0; i < last_basic_block; ++i)
- BITMAP_XFREE (control_dependence_map[i]);
+ BITMAP_FREE (control_dependence_map[i]);
free (control_dependence_map);
+ sbitmap_free (visited_control_parents);
sbitmap_free (last_stmt_necessary);
}
sbitmap_free (processed);
+
+ VEC_free (tree, heap, worklist);
}
\f
/* Main routine to eliminate dead code.
find_all_control_dependences (el);
timevar_pop (TV_CONTROL_DEPENDENCES);
+ visited_control_parents = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (visited_control_parents);
+
mark_dfs_back_edges ();
}
if (aggressive)
free_dominance_info (CDI_POST_DOMINATORS);
+ /* If we removed paths in the CFG, then we need to update
+ dominators as well. I haven't investigated the possibility
+ of incrementally updating dominators. */
+ if (cfg_altered)
+ free_dominance_info (CDI_DOMINATORS);
+
/* Debugging dumps. */
if (dump_file)
print_stats ();
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
+ TODO_dump_func
+ | TODO_update_ssa_no_phi
+ | TODO_cleanup_cfg
+ | TODO_ggc_collect
+ | TODO_verify_ssa, /* todo_flags_finish */
0 /* letter */
};
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
- /* todo_flags_finish */
+ TODO_dump_func
+ | TODO_update_ssa_no_phi
+ | TODO_cleanup_cfg
+ | TODO_ggc_collect
+ | TODO_verify_ssa
+ | TODO_verify_flow, /* todo_flags_finish */
0 /* letter */
};