tree-ssa-dce.c File Reference

Data Structures
struct	stmt_stats

Functions
static void	set_control_dependence_map_bit ()
static void	clear_control_dependence_bitmap ()
static basic_block	find_pdom ()
static void	find_control_dependence ()
static void	find_all_control_dependences ()
static void	mark_stmt_necessary ()
static void	mark_operand_necessary ()
static void	mark_stmt_if_obviously_necessary ()
static void	mark_last_stmt_necessary ()
static void	mark_control_dependent_edges_necessary (basic_block bb, struct edge_list *el, bool ignore_self)
static void	find_obviously_necessary_stmts ()
static bool	ref_may_be_aliased ()
static bool	mark_aliased_reaching_defs_necessary_1 ()
static void	mark_aliased_reaching_defs_necessary ()
static bool	mark_all_reaching_defs_necessary_1 (ao_ref *ref, tree vdef, void *data)
static void	mark_all_reaching_defs_necessary ()
static bool	degenerate_phi_p ()
static void	propagate_necessity ()
void	mark_virtual_operand_for_renaming ()
void	mark_virtual_phi_result_for_renaming ()
static bool	remove_dead_phis ()
static edge	forward_edge_to_pdom ()
static void	remove_dead_stmt ()
static bool	eliminate_unnecessary_stmts ()
static void	print_stats ()
static void	tree_dce_init ()
static void	tree_dce_done ()
static unsigned int	perform_tree_ssa_dce ()
static unsigned int	tree_ssa_dce ()
static unsigned int	tree_ssa_dce_loop ()
static unsigned int	tree_ssa_cd_dce ()
static bool	gate_dce ()
gimple_opt_pass *	make_pass_dce ()
gimple_opt_pass *	make_pass_dce_loop ()
gimple_opt_pass *	make_pass_cd_dce ()

Variables
static struct stmt_stats	stats
static vec< gimple >	worklist
static sbitmap	processed
static sbitmap	last_stmt_necessary
static sbitmap	bb_contains_live_stmts
static bitmap *	control_dependence_map
static sbitmap	visited_control_parents
static bool	cfg_altered
static bitmap	visited = NULL
static unsigned int	longest_chain = 0
static unsigned int	total_chain = 0
static unsigned int	nr_walks = 0
static bool	chain_ovfl = false

---

Function Documentation

static void clear_control_dependence_bitmap ( )

inlinestatic

Clear all control dependences for block BB.   

References bitmap_clear(), and basic_block_def::index.

static bool degenerate_phi_p ( )

static

Return true for PHI nodes with one or identical arguments
   can be removed.   

References gimple_phi_arg_def(), and gimple_phi_num_args().

Referenced by forward_edge_to_pdom(), propagate_necessity(), and remove_dead_phis().

static bool eliminate_unnecessary_stmts ( )

static

Eliminate unnecessary statements. Any instruction not marked as necessary
   contributes nothing to the program, and can be deleted.   

References bitmap_bit_p(), BUILT_IN_NORMAL, CDI_DOMINATORS, cfg_altered, clear_special_calls(), delete_basic_block(), dom_info_available_p(), dump_file, dump_flags, find_unreachable_blocks(), first_dom_son(), basic_block_def::flags, get_all_dominated_blocks(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_lhs(), gimple_call_set_lhs(), gimple_phi_result(), gimple_plf(), gimple_set_plf(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_prev(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, is_gimple_call(), is_gimple_debug(), mark_virtual_phi_result_for_renaming(), maybe_clean_or_replace_eh_stmt(), notice_special_calls(), basic_block_def::prev_bb, print_gimple_stmt(), release_ssa_name(), remove_dead_phis(), remove_dead_stmt(), single_succ(), stats, stmt_stats::total, update_stmt(), and virtual_operand_p().

Referenced by perform_tree_ssa_dce().

static void find_all_control_dependences ( )

static

Record all blocks' control dependences on all edges in the edge
   list EL, ala Morgan, Section 3.6.   

References find_control_dependence().

Referenced by perform_tree_ssa_dce().

static void find_control_dependence ( )

static

Determine all blocks' control dependences on the given edge with edge_list
   EL index EDGE_INDEX, ala Morgan, Section 3.6.   

References current_block, find_pdom(), edge_def::flags, set_control_dependence_map_bit(), and single_succ().

Referenced by find_all_control_dependences().

static void find_obviously_necessary_stmts ( )

static

Find obviously necessary statements.  These are things like most function
   calls, and stores to file level variables.

   If EL is NULL, control statements are conservatively marked as
   necessary.  Otherwise it contains the list of edges used by control
   dependence analysis.   

References current_function_decl, edge_def::dest, dump_file, finite_loop_p(), edge_def::flags, flags_from_decl_or_type(), gimple_set_plf(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, loop::latch, mark_control_dependent_edges_necessary(), mark_irreducible_loops(), mark_stmt_if_obviously_necessary(), loop::num, scev_finalize(), scev_initialize(), edge_def::src, and basic_block_def::succs.

Referenced by perform_tree_ssa_dce().

static basic_block find_pdom ( )

inlinestatic

Find the immediate postdominator PDOM of the specified basic block BLOCK.
   This function is necessary because some blocks have negative numbers.   

References CDI_POST_DOMINATORS, and get_immediate_dominator().

Referenced by find_control_dependence().

static edge forward_edge_to_pdom ( )

static

Forward edge E to respective POST_DOM_BB and update PHIs.   

References add_phi_arg(), cfg_altered, degenerate_phi_p(), edge_def::dest, edge_def::dest_idx, dump_file, dump_flags, gimple_phi_arg_def(), gimple_phi_arg_location(), gimple_phi_result(), gimple_plf(), gimple_seq_empty_p(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), basic_block_def::index, mark_virtual_phi_result_for_renaming(), phi_nodes(), basic_block_def::preds, redirect_edge_and_branch(), remove_phi_node(), edge_def::src, and virtual_operand_p().

Referenced by remove_dead_stmt().

static bool gate_dce ( )

static

gimple_opt_pass* make_pass_cd_dce

(

)

gimple_opt_pass* make_pass_dce

(

)

gimple_opt_pass* make_pass_dce_loop

(

)

static void mark_aliased_reaching_defs_necessary ( )

static

References ao_ref_init(), chain_ovfl, gimple_vuse(), longest_chain, mark_aliased_reaching_defs_necessary_1(), nr_walks, total_chain, and walk_aliased_vdefs().

Referenced by propagate_necessity().

static bool mark_aliased_reaching_defs_necessary_1 ( )

static

Worker for the walker that marks reaching definitions of REF,
   which is based on a non-aliased decl, necessary.  It returns
   true whenever the defining statement of the current VDEF is
   a kill for REF, as no dominating may-defs are necessary for REF
   anymore.  DATA points to the basic-block that contains the
   stmt that refers to REF.   

References ao_ref_base(), ao_ref_s::base, CDI_DOMINATORS, dominated_by_p(), get_ref_base_and_extent(), gimple_get_lhs(), gimple_has_lhs(), HOST_WIDE_INT, mark_operand_necessary(), ao_ref_s::max_size, ao_ref_s::offset, offset, operand_equal_p(), ao_ref_s::ref, and stmt_can_throw_internal().

Referenced by mark_aliased_reaching_defs_necessary().

static void mark_all_reaching_defs_necessary ( )

static

References gimple_vuse(), mark_all_reaching_defs_necessary_1(), and walk_aliased_vdefs().

Referenced by propagate_necessity().

static bool mark_all_reaching_defs_necessary_1 ( ao_ref *  ref, tree  vdef, void *  data  )

static

Worker for the walker that marks reaching definitions of REF, which
   is not based on a non-aliased decl.  For simplicity we need to end
   up marking all may-defs necessary that are not based on a non-aliased
   decl.  The only job of this walker is to skip may-defs based on
   a non-aliased decl.   

References bitmap_bit_p(), BUILT_IN_NORMAL, chain_ovfl, gimple_assign_lhs(), gimple_assign_single_p(), gimple_call_fndecl(), gimple_nop_p(), gimple_plf(), is_gimple_call(), mark_operand_necessary(), and ref_may_be_aliased().

Referenced by mark_all_reaching_defs_necessary().

static void mark_control_dependent_edges_necessary ( basic_block  bb, struct edge_list *  el, bool  ignore_self  )

static

Mark control dependent edges of BB as necessary.  We have to do this only
   once for each basic block so we set the appropriate bit after we're done.

   When IGNORE_SELF is true, ignore BB in the list of control dependences.   

References bitmap_bit_p(), bitmap_set_bit(), basic_block_def::index, and mark_last_stmt_necessary().

Referenced by find_obviously_necessary_stmts(), and propagate_necessity().

static void mark_last_stmt_necessary ( )

static

Mark the last statement of BB as necessary.   

References bitmap_set_bit(), basic_block_def::index, is_ctrl_stmt(), last_stmt(), and mark_stmt_necessary().

Referenced by mark_control_dependent_edges_necessary(), and propagate_necessity().

static void mark_operand_necessary ( )

inlinestatic

Mark the statement defining operand OP as necessary.   

References bitmap_bit_p(), bitmap_set_bit(), dump_file, dump_flags, gimple_nop_p(), gimple_plf(), gimple_set_plf(), print_generic_expr(), and print_gimple_stmt().

Referenced by mark_aliased_reaching_defs_necessary_1(), mark_all_reaching_defs_necessary_1(), and propagate_necessity().

static void mark_stmt_if_obviously_necessary ( )

static

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
   necessary.   

References BUILT_IN_NORMAL, function::can_delete_dead_exceptions, function::can_throw_non_call_exceptions, cfun, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_call_fndecl(), gimple_call_lhs(), gimple_debug_bind_get_var(), gimple_debug_bind_has_value_p(), gimple_debug_bind_p(), gimple_has_side_effects(), gimple_has_volatile_ops(), is_ctrl_altering_stmt(), mark_stmt_necessary(), simple_goto_p(), stmt_could_throw_p(), and stmt_may_clobber_global_p().

Referenced by find_obviously_necessary_stmts().

static void mark_stmt_necessary ( )

inlinestatic

If STMT is not already marked necessary, mark it, and add it to the
   worklist if ADD_TO_WORKLIST is true.   

References bitmap_set_bit(), dump_file, dump_flags, gimple_plf(), gimple_set_plf(), is_gimple_debug(), and print_gimple_stmt().

Referenced by mark_last_stmt_necessary(), and mark_stmt_if_obviously_necessary().

void mark_virtual_operand_for_renaming

(

)

Replace all uses of NAME by underlying variable and mark it
   for renaming.  This assumes the defining statement of NAME is
   going to be removed.   

References cfun, and mark_virtual_operands_for_renaming().

void mark_virtual_phi_result_for_renaming

(

)

Replace all uses of the virtual PHI result by its underlying variable
   and mark it for renaming.  This assumes the PHI node is going to be
   removed.   

References dump_file, dump_flags, gimple_phi_result(), mark_virtual_operand_for_renaming(), and print_gimple_stmt().

static unsigned int perform_tree_ssa_dce ( )

static

Main routine to eliminate dead code.

   AGGRESSIVE controls the aggressiveness of the algorithm.
   In conservative mode, we ignore control dependence and simply declare
   all but the most trivially dead branches necessary.  This mode is fast.
   In aggressive mode, control dependences are taken into account, which
   results in more dead code elimination, but at the cost of some time.

   FIXME: Aggressive mode before PRE doesn't work currently because
          the dominance info is not invalidated after DCE1.  This is
          not an issue right now because we only run aggressive DCE
          as the last tree SSA pass, but keep this in mind when you
          start experimenting with pass ordering.   

References bitmap_clear(), calculate_dominance_info(), CDI_DOMINATORS, CDI_POST_DOMINATORS, cfg_altered, cfun, chain_ovfl, create_edge_list(), dump_file, dump_flags, eliminate_unnecessary_stmts(), find_all_control_dependences(), find_obviously_necessary_stmts(), free_dominance_info(), free_edge_list(), longest_chain, loop_optimizer_finalize(), loop_optimizer_init(), LOOPS_HAVE_RECORDED_EXITS, mark_dfs_back_edges(), nr_walks, print_stats(), propagate_necessity(), stmt_stats::removed, stmt_stats::removed_phis, sbitmap_alloc(), statistics_counter_event(), stats, timevar_pop(), timevar_push(), total_chain, tree_dce_done(), and tree_dce_init().

Referenced by tree_ssa_cd_dce(), tree_ssa_dce(), and tree_ssa_dce_loop().

static void print_stats ( )

static

Print out removed statement statistics.   

References dump_file, stmt_stats::removed, stmt_stats::removed_phis, stats, stmt_stats::total, and stmt_stats::total_phis.

Referenced by perform_tree_ssa_dce().

static void propagate_necessity ( )

static

Propagate necessity using the operands of necessary statements.
   Process the uses on each statement in the worklist, and add all
   feeding statements which contribute to the calculation of this
   value to the worklist.

   In conservative mode, EL is NULL.   

References bitmap_bit_p(), bitmap_clear(), BUILT_IN_NORMAL, CDI_POST_DOMINATORS, chain_ovfl, degenerate_phi_p(), dump_file, dump_flags, get_immediate_dominator(), gimple_asm_input_op(), gimple_asm_ninputs(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_bb(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_fndecl(), gimple_call_num_args(), gimple_phi_arg_edge(), gimple_phi_num_args(), gimple_phi_result(), gimple_return_retval(), gimple_vuse(), basic_block_def::index, is_gimple_call(), is_gimple_min_invariant(), longest_chain, mark_aliased_reaching_defs_necessary(), mark_all_reaching_defs_necessary(), mark_control_dependent_edges_necessary(), mark_last_stmt_necessary(), mark_operand_necessary(), nr_walks, print_gimple_stmt(), ref_may_be_aliased(), edge_def::src, total_chain, and virtual_operand_p().

Referenced by perform_tree_ssa_dce().

static bool ref_may_be_aliased ( )

static

Return true if REF is based on an aliased base, otherwise false.   

References handled_component_p(), and may_be_aliased().

Referenced by mark_all_reaching_defs_necessary_1(), and propagate_necessity().

static bool remove_dead_phis ( )

static

Remove dead PHI nodes from block BB.   

References degenerate_phi_p(), dump_file, dump_flags, gimple_phi_arg_def(), gimple_phi_result(), gimple_plf(), gimple_set_plf(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), print_gimple_stmt(), remove_phi_node(), stmt_stats::removed_phis, stats, stmt_stats::total_phis, and virtual_operand_p().

Referenced by eliminate_unnecessary_stmts().

static void remove_dead_stmt ( )

static

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.   

References CDI_POST_DOMINATORS, cfg_altered, edge_def::count, basic_block_def::count, dump_file, dump_flags, ei_next(), ei_safe_edge(), find_edge(), edge_def::flags, forward_edge_to_pdom(), get_immediate_dominator(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_single_p(), gsi_insert_after(), gsi_remove(), GSI_SAME_STMT, gsi_stmt(), is_ctrl_stmt(), is_gimple_reg_type(), is_gimple_val(), is_global_var(), print_gimple_stmt(), edge_def::probability, release_defs(), remove_edge(), stmt_stats::removed, stats, basic_block_def::succs, unlink_stmt_vdef(), and unshare_expr().

Referenced by eliminate_unnecessary_stmts().

static void set_control_dependence_map_bit ( )

inlinestatic

Indicate block BB is control dependent on an edge with index EDGE_INDEX.   

References bitmap_set_bit(), and basic_block_def::index.

Referenced by find_control_dependence().

static void tree_dce_done ( )

static

Cleanup after this pass.   

References free(), and sbitmap_free().

Referenced by perform_tree_ssa_dce().

static void tree_dce_init ( )

static

Initialization for this pass.  Set up the used data structures.   

References bitmap_clear(), cfg_altered, memset(), sbitmap_alloc(), and stats.

Referenced by perform_tree_ssa_dce().

static unsigned int tree_ssa_cd_dce ( )

static

References perform_tree_ssa_dce().

static unsigned int tree_ssa_dce ( )

static

Pass entry points.   

References perform_tree_ssa_dce().

static unsigned int tree_ssa_dce_loop ( )

static

References free_numbers_of_iterations_estimates(), perform_tree_ssa_dce(), and scev_reset().

---

Variable Documentation

sbitmap bb_contains_live_stmts

static

Vector indicating that BB contains statements that are live.   

bool cfg_altered

static

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.   

Referenced by convert_regs(), convert_regs_1(), convert_regs_2(), eliminate_unnecessary_stmts(), forward_edge_to_pdom(), perform_tree_ssa_dce(), remove_dead_stmt(), and tree_dce_init().

bool chain_ovfl = false

static

Referenced by mark_aliased_reaching_defs_necessary(), mark_all_reaching_defs_necessary_1(), perform_tree_ssa_dce(), and propagate_necessity().

bitmap* control_dependence_map

static

Before we can determine whether a control branch is dead, we need to
   compute which blocks are control dependent on which edges.

   We expect each block to be control dependent on very few edges so we
   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.   

sbitmap last_stmt_necessary

static

Vector indicating that the last statement of a basic block has already
   been marked as necessary.   

unsigned int longest_chain = 0

static

Referenced by mark_aliased_reaching_defs_necessary(), perform_tree_ssa_dce(), and propagate_necessity().

unsigned int nr_walks = 0

static

Referenced by mark_aliased_reaching_defs_necessary(), perform_tree_ssa_dce(), and propagate_necessity().

sbitmap processed

static

Vector indicating an SSA name has already been processed and marked
   as necessary.   

Referenced by build_rdg_partition_for_component(), estimate_shadow_tick(), fast_dce(), fix_inter_tick(), and ldist_gen().

struct stmt_stats stats

static

Referenced by eliminate_unnecessary_stmts(), perform_tree_ssa_dce(), print_stats(), remove_dead_phis(), remove_dead_stmt(), and tree_dce_init().

unsigned int total_chain = 0

static

Referenced by mark_aliased_reaching_defs_necessary(), perform_tree_ssa_dce(), and propagate_necessity().

bitmap visited = NULL

static

Referenced by analyze_modified_params(), blocks_in_phiopt_order(), build_scop_bbs(), compute_trg_info(), copy_gimple_seq_and_replace_locals(), copyprop_hardreg_forward(), DFS(), dfs_enumerate_from(), dfs_find_deadend(), draw_cfg_nodes_no_loops(), find_comparison_args(), get_loop_body_in_bfs_order(), get_loop_body_in_if_conv_order(), get_loop_hot_path(), gimple_fold_builtin(), insert_clobbers_for_var(), inverted_post_order_compute(), live_worklist(), mark_dfs_back_edges(), maybe_lower_iteration_bound(), post_order_compute(), pre_and_rev_post_order_compute(), pre_expr_reaches_here_p(), predict_paths_leading_to(), predict_paths_leading_to_edge(), reachable_at_most_once(), remove_reachable_equiv_notes(), run_scc_vn(), strlen_enter_block(), thread_across_edge(), translate_vuse_through_block(), tree_predict_by_opcode(), unshare_body(), update_alias_info_with_stack_vars(), verify_eh_throw_stmt_node(), verify_gimple_in_cfg(), verify_loop_structure(), verify_node_sharing_1(), visit_hist(), vt_find_locations(), vt_stack_adjustments(), walk_aliased_vdefs_1(), walk_non_aliased_vuses(), and walk_use_def_chains().

sbitmap visited_control_parents

static

Vector indicating that a basic block has already had all the edges
   processed that it is control dependent on.   

vec<gimple> worklist

static