#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "errors.h"
#include "ggc.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "tree.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-gimple.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "timevar.h"
#include "flags.h"
#include "function.h"
static struct stmt_stats
{
int total;
int total_phis;
int removed;
int removed_phis;
} stats;
static varray_type worklist;
static sbitmap processed;
static sbitmap last_stmt_necessary;
bitmap *control_dependence_map;
#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 inline void set_control_dependence_map_bit (basic_block, int);
static inline void clear_control_dependence_bitmap (basic_block);
static void find_all_control_dependences (struct edge_list *);
static void find_control_dependence (struct edge_list *, int);
static inline basic_block find_pdom (basic_block);
static inline void mark_stmt_necessary (tree, bool);
static inline void mark_operand_necessary (tree, bool);
static void mark_stmt_if_obviously_necessary (tree, bool);
static void find_obviously_necessary_stmts (struct edge_list *);
static void mark_control_dependent_edges_necessary (basic_block, struct edge_list *);
static void propagate_necessity (struct edge_list *);
static void eliminate_unnecessary_stmts (void);
static void remove_dead_phis (basic_block);
static void remove_dead_stmt (block_stmt_iterator *, basic_block);
static void print_stats (void);
static void tree_dce_init (bool);
static void tree_dce_done (bool);
static inline void
set_control_dependence_map_bit (basic_block bb, int edge_index)
{
if (bb == ENTRY_BLOCK_PTR)
return;
gcc_assert (bb != EXIT_BLOCK_PTR);
bitmap_set_bit (control_dependence_map[bb->index], edge_index);
}
static inline
void clear_control_dependence_bitmap (basic_block bb)
{
bitmap_clear (control_dependence_map[bb->index]);
}
static void
find_all_control_dependences (struct edge_list *el)
{
int i;
for (i = 0; i < NUM_EDGES (el); ++i)
find_control_dependence (el, i);
}
static void
find_control_dependence (struct edge_list *el, int edge_index)
{
basic_block current_block;
basic_block ending_block;
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;
else
ending_block = find_pdom (INDEX_EDGE_PRED_BB (el, edge_index));
for (current_block = INDEX_EDGE_SUCC_BB (el, edge_index);
current_block != ending_block && current_block != EXIT_BLOCK_PTR;
current_block = find_pdom (current_block))
{
edge e = INDEX_EDGE (el, edge_index);
if (e->flags & EDGE_ABNORMAL)
continue;
set_control_dependence_map_bit (current_block, edge_index);
}
}
static inline basic_block
find_pdom (basic_block block)
{
gcc_assert (block != ENTRY_BLOCK_PTR);
if (block == EXIT_BLOCK_PTR)
return EXIT_BLOCK_PTR;
else
{
basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
if (! bb)
return EXIT_BLOCK_PTR;
return bb;
}
}
#define NECESSARY(stmt) stmt->common.asm_written_flag
static inline void
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))
return;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Marking useful stmt: ");
print_generic_stmt (dump_file, stmt, TDF_SLIM);
fprintf (dump_file, "\n");
}
NECESSARY (stmt) = 1;
if (add_to_worklist)
VARRAY_PUSH_TREE (worklist, stmt);
}
static inline void
mark_operand_necessary (tree op, bool phionly)
{
tree stmt;
int ver;
gcc_assert (op);
ver = SSA_NAME_VERSION (op);
if (TEST_BIT (processed, ver))
return;
SET_BIT (processed, ver);
stmt = SSA_NAME_DEF_STMT (op);
gcc_assert (stmt);
if (NECESSARY (stmt)
|| IS_EMPTY_STMT (stmt)
|| (phionly && TREE_CODE (stmt) != PHI_NODE))
return;
NECESSARY (stmt) = 1;
VARRAY_PUSH_TREE (worklist, stmt);
}
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;
switch (TREE_CODE (stmt))
{
case BIND_EXPR:
case LABEL_EXPR:
case CASE_LABEL_EXPR:
mark_stmt_necessary (stmt, false);
return;
case ASM_EXPR:
case RESX_EXPR:
case RETURN_EXPR:
mark_stmt_necessary (stmt, true);
return;
case CALL_EXPR:
if (TREE_SIDE_EFFECTS (stmt))
mark_stmt_necessary (stmt, true);
return;
case MODIFY_EXPR:
op = get_call_expr_in (stmt);
if (op && TREE_SIDE_EFFECTS (op))
{
mark_stmt_necessary (stmt, true);
return;
}
if (TREE_CODE (TREE_OPERAND (stmt, 0)) == EXC_PTR_EXPR
|| TREE_CODE (TREE_OPERAND (stmt, 0)) == FILTER_EXPR)
{
mark_stmt_necessary (stmt, true);
return;
}
break;
case GOTO_EXPR:
if (! simple_goto_p (stmt))
mark_stmt_necessary (stmt, true);
return;
case COND_EXPR:
if (GOTO_DESTINATION (COND_EXPR_THEN (stmt))
== GOTO_DESTINATION (COND_EXPR_ELSE (stmt)))
{
COND_EXPR_COND (stmt) = integer_zero_node;
modify_stmt (stmt);
return;
}
case SWITCH_EXPR:
if (! aggressive)
mark_stmt_necessary (stmt, true);
break;
default:
break;
}
ann = stmt_ann (stmt);
if (ann->has_volatile_ops || is_ctrl_altering_stmt (stmt))
{
mark_stmt_necessary (stmt, true);
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;
}
}
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)
{
tree lhs;
gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
lhs = TREE_OPERAND (stmt, 0);
if (REFERENCE_CLASS_P (lhs))
lhs = get_base_address (lhs);
if (lhs == NULL_TREE)
{
mark_stmt_necessary (stmt, true);
}
else if (DECL_P (lhs))
{
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 ((nmt && is_global_var (nmt))
|| (tmt && is_global_var (tmt)))
{
mark_stmt_necessary (stmt, true);
return;
}
}
else
gcc_unreachable ();
}
return;
}
static void
find_obviously_necessary_stmts (struct edge_list *el)
{
basic_block bb;
block_stmt_iterator i;
edge e;
FOR_EACH_BB (bb)
{
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
NECESSARY (phi) = 0;
if (is_gimple_reg (PHI_RESULT (phi))
&& is_global_var (SSA_NAME_VAR (PHI_RESULT (phi))))
mark_stmt_necessary (phi, true);
}
for (i = bsi_start (bb); ! bsi_end_p (i); bsi_next (&i))
{
tree stmt = bsi_stmt (i);
NECESSARY (stmt) = 0;
mark_stmt_if_obviously_necessary (stmt, el != NULL);
}
bb->flags &= ~BB_VISITED;
}
if (el && !cfun->marked_maybe_inf_loops)
{
mark_dfs_back_edges ();
FOR_EACH_BB (bb)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_DFS_BACK)
mark_control_dependent_edges_necessary (e->dest, el);
}
}
}
static void
mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el)
{
int edge_number;
gcc_assert (bb != EXIT_BLOCK_PTR);
if (bb == ENTRY_BLOCK_PTR)
return;
EXECUTE_IF_CONTROL_DEPENDENT (bb->index, edge_number,
{
tree t;
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);
});
}
static void
propagate_necessity (struct edge_list *el)
{
tree i;
bool aggressive = (el ? true : false);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nProcessing worklist:\n");
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
i = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "processing: ");
print_generic_stmt (dump_file, i, TDF_SLIM);
fprintf (dump_file, "\n");
}
if (aggressive)
{
basic_block bb = bb_for_stmt (i);
if (! (bb->flags & BB_VISITED))
{
bb->flags |= BB_VISITED;
mark_control_dependent_edges_necessary (bb, el);
}
}
if (TREE_CODE (i) == PHI_NODE)
{
int k;
for (k = 0; k < PHI_NUM_ARGS (i); k++)
{
tree arg = PHI_ARG_DEF (i, k);
if (TREE_CODE (arg) == SSA_NAME)
mark_operand_necessary (arg, false);
}
if (aggressive)
{
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))
{
arg_bb->flags |= BB_VISITED;
mark_control_dependent_edges_necessary (arg_bb, el);
}
}
}
}
else
{
ssa_op_iter iter;
tree use;
get_stmt_operands (i);
FOR_EACH_SSA_TREE_OPERAND (use, i, iter, SSA_OP_ALL_USES)
mark_operand_necessary (use, false);
}
}
}
static void
mark_really_necessary_kill_operand_phis (void)
{
basic_block bb;
int i;
FOR_EACH_BB (bb)
{
block_stmt_iterator bsi;
tree phi;
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
if (!is_gimple_reg (PHI_RESULT (phi)) && NECESSARY (phi))
{
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
mark_operand_necessary (PHI_ARG_DEF (phi, i), true);
}
}
for (bsi = bsi_last (bb); !bsi_end_p (bsi); bsi_prev (&bsi))
{
tree stmt = bsi_stmt (bsi);
if (NECESSARY (stmt))
{
use_operand_p use_p;
ssa_op_iter iter;
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
{
tree use = USE_FROM_PTR (use_p);
mark_operand_necessary (use, true);
}
}
}
}
while (VARRAY_ACTIVE_SIZE (worklist) > 0)
{
tree use = VARRAY_TOP_TREE (worklist);
VARRAY_POP (worklist);
for (i = 0; i < PHI_NUM_ARGS (use); i++)
mark_operand_necessary (PHI_ARG_DEF (use, i), true);
}
}
static void
eliminate_unnecessary_stmts (void)
{
basic_block bb;
block_stmt_iterator i;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "\nEliminating unnecessary statements:\n");
clear_special_calls ();
FOR_EACH_BB (bb)
{
remove_dead_phis (bb);
for (i = bsi_start (bb); ! bsi_end_p (i) ; )
{
tree t = bsi_stmt (i);
stats.total++;
if (! NECESSARY (t))
remove_dead_stmt (&i, bb);
else
{
tree call = get_call_expr_in (t);
if (call)
notice_special_calls (call);
bsi_next (&i);
}
}
}
}
static void
remove_dead_phis (basic_block bb)
{
tree prev, phi;
prev = NULL_TREE;
phi = phi_nodes (bb);
while (phi)
{
stats.total_phis++;
if (! NECESSARY (phi))
{
tree next = PHI_CHAIN (phi);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Deleting : ");
print_generic_stmt (dump_file, phi, TDF_SLIM);
fprintf (dump_file, "\n");
}
remove_phi_node (phi, prev, bb);
stats.removed_phis++;
phi = next;
}
else
{
prev = phi;
phi = PHI_CHAIN (phi);
}
}
}
static void
remove_dead_stmt (block_stmt_iterator *i, basic_block bb)
{
tree t = bsi_stmt (*i);
def_operand_p def_p;
ssa_op_iter iter;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Deleting : ");
print_generic_stmt (dump_file, t, TDF_SLIM);
fprintf (dump_file, "\n");
}
stats.removed++;
if (is_ctrl_stmt (t))
{
basic_block post_dom_bb;
gcc_assert (dom_computed[CDI_POST_DOMINATORS] == DOM_OK);
post_dom_bb = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
if (! post_dom_bb)
{
bsi_next (i);
return;
}
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;
free_dominance_info (CDI_DOMINATORS);
EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
if (post_dom_bb != EXIT_BLOCK_PTR)
EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
else
EDGE_SUCC (bb, 0)->flags &= ~EDGE_FALLTHRU;
while (EDGE_COUNT (bb->succs) != 1)
remove_edge (EDGE_SUCC (bb, 1));
}
FOR_EACH_SSA_DEF_OPERAND (def_p, t, iter,
SSA_OP_VIRTUAL_DEFS | SSA_OP_VIRTUAL_KILLS)
{
tree def = DEF_FROM_PTR (def_p);
bitmap_set_bit (vars_to_rename,
var_ann (SSA_NAME_VAR (def))->uid);
}
bsi_remove (i);
release_defs (t);
}
static void
print_stats (void)
{
if (dump_file && (dump_flags & (TDF_STATS|TDF_DETAILS)))
{
float percg;
percg = ((float) stats.removed / (float) stats.total) * 100;
fprintf (dump_file, "Removed %d of %d statements (%d%%)\n",
stats.removed, stats.total, (int) percg);
if (stats.total_phis == 0)
percg = 0;
else
percg = ((float) stats.removed_phis / (float) stats.total_phis) * 100;
fprintf (dump_file, "Removed %d of %d PHI nodes (%d%%)\n",
stats.removed_phis, stats.total_phis, (int) percg);
}
}
static void
tree_dce_init (bool aggressive)
{
memset ((void *) &stats, 0, sizeof (stats));
if (aggressive)
{
int i;
control_dependence_map
= xmalloc (last_basic_block * sizeof (bitmap));
for (i = 0; i < last_basic_block; ++i)
control_dependence_map[i] = BITMAP_XMALLOC ();
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");
}
static void
tree_dce_done (bool aggressive)
{
if (aggressive)
{
int i;
for (i = 0; i < last_basic_block; ++i)
BITMAP_XFREE (control_dependence_map[i]);
free (control_dependence_map);
sbitmap_free (last_stmt_necessary);
}
sbitmap_free (processed);
}
static void
perform_tree_ssa_dce (bool aggressive, bool no_cfg_changes)
{
struct edge_list *el = NULL;
if (no_cfg_changes && aggressive)
abort ();
tree_dce_init (aggressive);
if (aggressive)
{
timevar_push (TV_CONTROL_DEPENDENCES);
calculate_dominance_info (CDI_POST_DOMINATORS);
el = create_edge_list ();
find_all_control_dependences (el);
timevar_pop (TV_CONTROL_DEPENDENCES);
}
find_obviously_necessary_stmts (el);
propagate_necessity (el);
mark_really_necessary_kill_operand_phis ();
eliminate_unnecessary_stmts ();
if (aggressive)
free_dominance_info (CDI_POST_DOMINATORS);
if (!no_cfg_changes)
cleanup_tree_cfg ();
if (dump_file)
print_stats ();
tree_dce_done (aggressive);
free_edge_list (el);
}
void
tree_ssa_dce_no_cfg_changes (void)
{
perform_tree_ssa_dce (false, true);
}
static void
tree_ssa_dce (void)
{
perform_tree_ssa_dce (false, false);
}
static void
tree_ssa_cd_dce (void)
{
perform_tree_ssa_dce (optimize >= 2, false);
}
static bool
gate_dce (void)
{
return flag_tree_dce != 0;
}
struct tree_opt_pass pass_dce =
{
"dce",
gate_dce,
tree_ssa_dce,
NULL,
NULL,
0,
TV_TREE_DCE,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa,
0
};
struct tree_opt_pass pass_cd_dce =
{
"cddce",
gate_dce,
tree_ssa_cd_dce,
NULL,
NULL,
0,
TV_TREE_CD_DCE,
PROP_cfg | PROP_ssa | PROP_alias,
0,
0,
0,
TODO_dump_func | TODO_fix_def_def_chains | TODO_cleanup_cfg | TODO_ggc_collect | TODO_verify_ssa | TODO_verify_flow,
0
};