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. */
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. */
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. */
#define EXECUTE_IF_CONTROL_DEPENDENT(N, EDGE_NUMBER, CODE) \
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
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)))
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) ; )
{
}
}
\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);
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. */
}
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 ();
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 */
};