/* Dead code elimination pass for the GNU compiler.
- Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2002, 2003, 2004, 2005, 2006 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 "tree-pass.h"
#include "timevar.h"
#include "flags.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.h"
\f
static struct stmt_stats
{
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. */
-sbitmap visited_control_parents;
-
-/* Execute CODE for each edge (given number EDGE_NUMBER within the CODE)
- for which the block with index N is control dependent. */
-#define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE) \
- { \
- bitmap_iterator bi; \
- \
- EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[N], 0, EDGE_NUMBER, bi) \
- { \
- CODE; \
- } \
- }
+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 that follows the macro for each edge (given number
+ EDGE_NUMBER within the CODE) for which the block with index N is
+ control dependent. */
+#define EXECUTE_IF_CONTROL_DEPENDENT(BI, N, EDGE_NUMBER) \
+ EXECUTE_IF_SET_IN_BITMAP (control_dependence_map[(N)], 0, \
+ (EDGE_NUMBER), (BI))
/* Local function prototypes. */
static inline void set_control_dependence_map_bit (basic_block, int);
}
/* Clear all control dependences for block BB. */
-static inline
-void clear_control_dependence_bitmap (basic_block bb)
+static inline void
+clear_control_dependence_bitmap (basic_block bb)
{
bitmap_clear (control_dependence_map[bb->index]);
}
gcc_assert (INDEX_EDGE_PRED_BB (el, edge_index) != EXIT_BLOCK_PTR);
if (INDEX_EDGE_PRED_BB (el, edge_index) == ENTRY_BLOCK_PTR)
- ending_block = ENTRY_BLOCK_PTR->next_bb;
+ ending_block = single_succ (ENTRY_BLOCK_PTR);
else
ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
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
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;
+ tree op;
+
+ /* 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
return;
}
- get_stmt_operands (stmt);
-
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- {
- if (is_global_var (SSA_NAME_VAR (def)))
- {
- mark_stmt_necessary (stmt, true);
- 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;
static void
mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
{
+ bitmap_iterator bi;
unsigned edge_number;
gcc_assert (bb != EXIT_BLOCK_PTR);
if (bb == ENTRY_BLOCK_PTR)
return;
- EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
+ EXECUTE_IF_CONTROL_DEPENDENT (bi, bb->index, edge_number)
{
tree t;
basic_block cd_bb = INDEX_EDGE_PRED_BB (el, edge_number);
t = last_stmt (cd_bb);
if (t && is_ctrl_stmt (t))
mark_stmt_necessary (t, true);
- });
+ }
}
\f
/* Propagate necessity using the operands of necessary statements. Process
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))
{
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 cleanup_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. */
post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
- /* Some blocks don't have an immediate post dominator. This can happen
- for example with infinite loops. Removing an infinite loop is an
- inappropriate transformation anyway... */
- if (! post_dom_bb)
+
+ /* There are three particularly problematical cases.
+
+ 1. Blocks that do not have an immediate post dominator. This
+ can happen with infinite loops.
+
+ 2. Blocks that are only post dominated by the exit block. These
+ can also happen for infinite loops as we create fake edges
+ in the dominator tree.
+
+ 3. If the post dominator has PHI nodes we may be able to compute
+ the right PHI args for them.
+
+
+ In each of these cases we must remove the control statement
+ as it may reference SSA_NAMEs which are going to be removed and
+ we remove all but one outgoing edge from the block. */
+ if (! post_dom_bb
+ || post_dom_bb == EXIT_BLOCK_PTR
+ || phi_nodes (post_dom_bb))
+ ;
+ else
{
- bsi_next (i);
- 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;
}
-
- /* 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;
not have TRUE/FALSE flags. */
EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
- /* If the edge reaches any block other than the exit, then it is a
- fallthru edge; if it reaches the exit, then it is not a fallthru
- edge. */
- if (post_dom_bb != EXIT_BLOCK_PTR)
- EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
- else
- EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
+ /* The lone outgoing edge from BB will be a fallthru edge. */
+ 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);
+ bsi_remove (i, true);
release_defs (t);
}
\f
{
int i;
- control_dependence_map
- = xmalloc (last_basic_block * sizeof (bitmap));
+ control_dependence_map = XNEWVEC (bitmap, last_basic_block);
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 (processed);
+
+ VEC_free (tree, heap, worklist);
}
\f
/* Main routine to eliminate dead code.
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 ();
}
/* Pass entry points. */
-static void
+static unsigned int
tree_ssa_dce (void)
{
perform_tree_ssa_dce (/*aggressive=*/false);
+ return 0;
}
-static void
+static unsigned int
+tree_ssa_dce_loop (void)
+{
+ perform_tree_ssa_dce (/*aggressive=*/false);
+ free_numbers_of_iterations_estimates (current_loops);
+ scev_reset ();
+ return 0;
+}
+
+static unsigned int
tree_ssa_cd_dce (void)
{
perform_tree_ssa_dce (/*aggressive=*/optimize >= 2);
+ return 0;
}
static bool
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
+ | TODO_cleanup_cfg
+ | TODO_ggc_collect
+ | TODO_verify_ssa
+ | TODO_remove_unused_locals, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+struct tree_opt_pass pass_dce_loop =
+{
+ "dceloop", /* name */
+ gate_dce, /* gate */
+ tree_ssa_dce_loop, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_DCE, /* tv_id */
+ PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func
+ | TODO_update_ssa
+ | TODO_cleanup_cfg
+ | 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
+ | TODO_cleanup_cfg
+ | TODO_ggc_collect
+ | TODO_verify_ssa
+ | TODO_verify_flow, /* todo_flags_finish */
0 /* letter */
};
-