tree-ssa-tail-merge.c File Reference

Data Structures
struct	same_succ_def
struct	bb_cluster_def
struct	aux_bb_info

Typedefs
typedef struct same_succ_def *	same_succ
typedef struct same_succ_def *	const_same_succ
typedef struct bb_cluster_def *	bb_cluster
typedef struct bb_cluster_def *	const_bb_cluster

Functions
static bool	stmt_local_def ()
static void	gsi_advance_fw_nondebug_nonlocal ()
static bool	gvn_uses_equal ()
static void	same_succ_print ()
int	ssa_same_succ_print_traverse ()
static void	update_dep_bb ()
static void	stmt_update_dep_bb ()
static hashval_t	same_succ_hash ()
static bool	inverse_flags ()
static same_succ	same_succ_alloc ()
static void	same_succ_reset ()
void	debug_same_succ (void)
static void	print_worklist ()
static void	add_to_worklist ()
static void	find_same_succ_bb ()
static void	find_same_succ ()
static void	init_worklist ()
static void	delete_worklist ()
static void	mark_basic_block_deleted ()
static void	same_succ_flush_bb ()
static void	same_succ_flush_bbs ()
static void	release_last_vdef ()
static void	update_worklist ()
static void	print_cluster ()
void	debug_cluster (bb_cluster)
DEBUG_FUNCTION void	debug_cluster ()
static void	update_rep_bb ()
static void	add_bb_to_cluster ()
static bb_cluster	new_cluster ()
static void	delete_cluster ()
static void	alloc_cluster_vectors ()
static void	reset_cluster_vectors ()
static void	delete_cluster_vectors ()
static void	merge_clusters ()
static void	set_cluster ()
static bool	gimple_equal_p ()
static void	gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse, bool *vuse_escaped)
static void	find_duplicate ()
static bool	same_phi_alternatives_1 ()
static bool	same_phi_alternatives ()
static bool	bb_has_non_vop_phi ()
static bool	deps_ok_for_redirect_from_bb_to_bb ()
static bool	deps_ok_for_redirect ()
static void	find_clusters_1 ()
static void	find_clusters ()
static gimple	vop_phi ()
static void	replace_block_by ()
static int	apply_clusters ()
static void	update_debug_stmt ()
static void	update_debug_stmts ()
unsigned int	tail_merge_optimize ()

Variables
static hash_table< same_succ_def >	same_succ_htab
static int *	same_succ_edge_flags
static bitmap	deleted_bbs
static bitmap	deleted_bb_preds
static vec< same_succ >	worklist
static vec< bb_cluster >	all_clusters
static bitmap	update_bbs

---

Typedef Documentation

typedef struct bb_cluster_def* bb_cluster

typedef struct bb_cluster_def* const_bb_cluster

typedef struct same_succ_def* const_same_succ

typedef struct same_succ_def* same_succ

---

Function Documentation

static void add_bb_to_cluster ( )

static

Add BB to cluster C.  Sets BB in C->bbs, and preds of BB in C->preds.   

References bb_cluster_def::bbs, bitmap_set_bit(), basic_block_def::index, basic_block_def::preds, bb_cluster_def::preds, edge_def::src, and update_rep_bb().

Referenced by set_cluster().

static void add_to_worklist ( )

static

Adds SAME to worklist.   

References same_succ_def::bbs, bitmap_count_bits(), and same_succ_def::in_worklist.

Referenced by find_same_succ_bb().

static void alloc_cluster_vectors ( )

static

Allocate all cluster vectors.   

Referenced by tail_merge_optimize().

static int apply_clusters ( )

static

For each cluster in all_clusters, merge all cluster->bbs.  Returns
   number of bbs removed.   

References bb_cluster_def::bbs, bitmap_clear_bit(), bitmap_set_bit(), basic_block_def::index, bb_cluster_def::rep_bb, and replace_block_by().

Referenced by tail_merge_optimize().

static bool bb_has_non_vop_phi ( )

static

Return true if BB has non-vop phis.   

References gimple_phi_result(), gimple_seq_first_stmt(), gimple_seq_singleton_p(), phi_nodes(), phis, and virtual_operand_p().

Referenced by find_clusters_1().

void debug_cluster

(

bb_cluster

)

Prints cluster C to stderr.   

DEBUG_FUNCTION void debug_cluster

(

)

References print_cluster().

DEBUG_FUNCTION void debug_same_succ

(

void

)

Prints same_succ_htab to stderr.   

References ssa_same_succ_print_traverse(), and hash_table< Descriptor, Allocator >::traverse().

static void delete_cluster ( )

static

Delete clusters.   

References bb_cluster_def::bbs, and bb_cluster_def::preds.

Referenced by delete_cluster_vectors(), reset_cluster_vectors(), and set_cluster().

static void delete_cluster_vectors ( )

static

Delete all cluster vectors.   

References delete_cluster().

Referenced by tail_merge_optimize().

static void delete_worklist ( )

static

Deletes worklist administration.   

References hash_table< Descriptor, Allocator >::dispose(), free_aux_for_blocks(), and same_succ_edge_flags.

Referenced by tail_merge_optimize().

static bool deps_ok_for_redirect ( )

static

Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
   replacement bb) and vice versa maintains the invariant that uses in the
   replacement are dominates by their defs.   

References deps_ok_for_redirect_from_bb_to_bb().

Referenced by find_clusters_1().

static bool deps_ok_for_redirect_from_bb_to_bb ( )

static

Returns true if redirecting the incoming edges of FROM to TO maintains the
   invariant that uses in FROM are dominates by their defs.   

References bitmap_set_bit(), CDI_DOMINATORS, dominated_by_p(), basic_block_def::index, nearest_common_dominator_for_set(), basic_block_def::preds, and edge_def::src.

Referenced by deps_ok_for_redirect().

static void find_clusters ( )

static

Find clusters of bbs which can be merged.   

References dump_file, dump_flags, find_clusters_1(), same_succ_def::in_worklist, and same_succ_print().

Referenced by tail_merge_optimize().

static void find_clusters_1 ( )

static

Within SAME_SUCC->bbs, find clusters of bbs which can be merged.   

References bb_has_non_vop_phi(), same_succ_def::bbs, deps_ok_for_redirect(), find_duplicate(), and same_phi_alternatives().

Referenced by find_clusters().

static void find_duplicate ( )

static

Determines whether BB1 and BB2 (members of same_succ) are duplicates.  If so,
   clusters them.   

References dump_file, gimple_call_flags(), gimple_call_fndecl(), gimple_equal_p(), gsi_advance_bw_nondebug_nonlocal(), gsi_end_p(), gsi_last_nondebug_bb(), gsi_prev_nondebug(), gsi_stmt(), basic_block_def::index, is_gimple_call(), is_tm_ending_fndecl(), and set_cluster().

Referenced by find_clusters_1().

static void find_same_succ ( )

static

Find bbs with same successors.   

References find_same_succ_bb(), same_succ_def::remove(), and same_succ_alloc().

Referenced by init_worklist().

static void find_same_succ_bb ( )

static

Add BB to same_succ_htab.   

References add_to_worklist(), same_succ_def::bbs, bitmap_set_bit(), edge_def::dest, hash_table< Descriptor, Allocator >::find_slot_with_hash(), edge_def::flags, same_succ_def::hashval, basic_block_def::index, inverse_flags(), loop::latch, basic_block_def::loop_father, same_succ_edge_flags, same_succ_hash(), same_succ_reset(), same_succ_def::succ_flags, basic_block_def::succs, and same_succ_def::succs.

Referenced by find_same_succ(), and update_worklist().

static bool gimple_equal_p ( )

static

Return true if gimple statements S1 and S2 are equal.  Gimple_bb (s1) and
   gimple_bb (s2) are members of SAME_SUCC.   

References bitmap_bit_p(), gimple_bb(), gimple_call_arg(), gimple_call_builtin_p(), gimple_call_num_args(), gimple_call_same_target_p(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_expr_code(), gimple_get_lhs(), gimple_vdef(), gvn_uses_equal(), basic_block_def::index, same_succ_def::inverse, invert_tree_comparison(), operand_equal_p(), and vn_valueize().

Referenced by find_duplicate().

static void gsi_advance_bw_nondebug_nonlocal ( gimple_stmt_iterator *  gsi, tree *  vuse, bool *  vuse_escaped  )

static

Let GSI skip backwards over local defs.  Return the earliest vuse in VUSE.
   Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
   processed statements.   

References gimple_vuse(), gsi_end_p(), gsi_prev_nondebug(), gsi_stmt(), and stmt_local_def().

Referenced by find_duplicate().

static void gsi_advance_fw_nondebug_nonlocal ( )

static

Let GSI skip forwards over local defs.   

References gsi_end_p(), gsi_next_nondebug(), gsi_stmt(), and stmt_local_def().

Referenced by same_succ_def::equal().

static bool gvn_uses_equal ( )

static

VAL1 and VAL2 are either:
   - uses in BB1 and BB2, or
   - phi alternatives for BB1 and BB2.
   Return true if the uses have the same gvn value.   

References vn_valueize().

Referenced by gimple_equal_p(), and same_phi_alternatives_1().

static void init_worklist ( )

static

Initializes worklist administration.   

References alloc_aux_for_blocks(), hash_table< Descriptor, Allocator >::create(), dump_file, dump_flags, find_same_succ(), print_worklist(), and same_succ_edge_flags.

Referenced by tail_merge_optimize().

static bool inverse_flags ( )

static

Returns true if E1 and E2 have 2 successors, and if the successor flags
   are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
   the other edge flags.   

References same_succ_def::succ_flags.

Referenced by same_succ_def::equal(), and find_same_succ_bb().

static void mark_basic_block_deleted ( )

static

Mark BB as deleted, and mark its predecessors.   

References bitmap_set_bit(), basic_block_def::index, basic_block_def::preds, and edge_def::src.

Referenced by replace_block_by().

static void merge_clusters ( )

static

Merge cluster C2 into C1.   

References bb_cluster_def::bbs, bitmap_ior_into(), and bb_cluster_def::preds.

Referenced by set_cluster().

static bb_cluster new_cluster ( )

static

Allocate and init new cluster.   

References bb_cluster_def::bbs, bb_cluster_def::preds, and bb_cluster_def::rep_bb.

Referenced by set_cluster().

static void print_cluster ( )

static

Prints cluster C to FILE.   

References bb_cluster_def::bbs, bitmap_print(), and bb_cluster_def::preds.

Referenced by debug_cluster().

static void print_worklist ( )

static

Prints worklist to FILE.   

References same_succ_print().

Referenced by init_worklist().

static void release_last_vdef ( )

static

Release the last vdef in BB, either normal or phi result.   

References gimple_phi_result(), gimple_vdef(), gsi_end_p(), gsi_last_bb(), gsi_next(), gsi_prev_nondebug(), gsi_start_phis(), gsi_stmt(), mark_virtual_operand_for_renaming(), mark_virtual_phi_result_for_renaming(), and virtual_operand_p().

Referenced by replace_block_by().

static void replace_block_by ( )

static

Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed.   

References add_phi_arg(), basic_block_def::count, delete_basic_block(), basic_block_def::frequency, gimple_phi_result(), mark_basic_block_deleted(), basic_block_def::preds, redirect_edge_and_branch(), release_last_vdef(), same_succ_flush_bb(), and vop_phi().

Referenced by apply_clusters().

static void reset_cluster_vectors ( )

static

Reset all cluster vectors.   

References delete_cluster().

Referenced by tail_merge_optimize().

static bool same_phi_alternatives ( )

static

Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
   phi alternatives for BB1 and BB2 are equal.   

References find_edge(), edge_def::flags, same_phi_alternatives_1(), and same_succ_def::succs.

Referenced by find_clusters_1().

static bool same_phi_alternatives_1 ( )

static

Returns whether for all phis in DEST the phi alternatives for E1 and
   E2 are equal.   

References edge_def::dest_idx, gimple_phi_arg_def(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), gvn_uses_equal(), operand_equal_for_phi_arg_p(), and virtual_operand_p().

Referenced by same_phi_alternatives().

static same_succ same_succ_alloc ( )

static

Alloc and init a new SAME_SUCC.   

References same_succ_def::bbs, same_succ_def::in_worklist, same_succ_def::inverse, same_succ_def::succ_flags, and same_succ_def::succs.

Referenced by find_same_succ(), and update_worklist().

static void same_succ_flush_bb ( )

static

Removes BB from its corresponding same_succ.   

References same_succ_def::bbs, bitmap_clear_bit(), bitmap_single_bit_set_p(), same_succ_def::hashval, basic_block_def::index, and hash_table< Descriptor, Allocator >::remove_elt_with_hash().

Referenced by replace_block_by(), and same_succ_flush_bbs().

static void same_succ_flush_bbs ( )

static

Removes all bbs in BBS from their corresponding same_succ.   

References same_succ_flush_bb().

Referenced by update_worklist().

static hashval_t same_succ_hash ( )

static

Calculates hash value for same_succ VE.   

References same_succ_def::bbs, bitmap_first_set_bit(), bitmap_hash(), edge_def::dest_idx, find_edge(), first, gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_fn(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_call_num_args(), gimple_phi_arg_def(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_next_nondebug(), gsi_start_nondebug_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_assign(), is_gimple_call(), iterative_hash_expr(), iterative_hash_hashval_t(), stmt_local_def(), stmt_update_dep_bb(), same_succ_def::succ_flags, same_succ_def::succs, update_dep_bb(), virtual_operand_p(), and vn_valueize().

Referenced by find_same_succ_bb().

static void same_succ_print ( )

static

Prints E to FILE.   

References same_succ_def::bbs, bitmap_print(), same_succ_def::inverse, same_succ_def::succ_flags, and same_succ_def::succs.

Referenced by find_clusters(), print_worklist(), and ssa_same_succ_print_traverse().

static void same_succ_reset ( )

static

Reset same_succ SAME.   

References same_succ_def::bbs, bitmap_clear(), same_succ_def::inverse, same_succ_def::succ_flags, and same_succ_def::succs.

Referenced by find_same_succ_bb().

static void set_cluster ( )

static

Register equivalence of BB1 and BB2 (members of cluster C).  Store c in
   all_clusters, or merge c with existing cluster.   

References add_bb_to_cluster(), bb_cluster_def::bbs, delete_cluster(), bb_cluster_def::index, merge_clusters(), new_cluster(), bb_cluster_def::rep_bb, and update_rep_bb().

Referenced by find_duplicate().

int ssa_same_succ_print_traverse ( )

inline

Prints same_succ VE to VFILE.   

References same_succ_print().

Referenced by debug_same_succ().

static bool stmt_local_def ( )

static

Returns true if the only effect a statement STMT has, is to define locally
   used SSA_NAMEs.   

References gimple_bb(), gimple_has_side_effects(), and is_gimple_debug().

Referenced by gsi_advance_bw_nondebug_nonlocal(), gsi_advance_fw_nondebug_nonlocal(), and same_succ_hash().

static void stmt_update_dep_bb ( )

static

Update BB_DEP_BB, given the dependencies in STMT.   

References update_dep_bb().

Referenced by same_succ_hash().

unsigned int tail_merge_optimize

(

)

Runs tail merge optimization.   

References alloc_cluster_vectors(), apply_clusters(), calculate_dominance_info(), CDI_DOMINATORS, cfun, hash_table< Descriptor, Allocator >::collisions(), current_function_decl, delete_cluster_vectors(), delete_unreachable_blocks(), delete_worklist(), dom_info_available_p(), dump_file, dump_flags, dump_function_to_file(), find_clusters(), free_dominance_info(), init_worklist(), mark_virtual_operands_for_renaming(), reset_cluster_vectors(), timevar_pop(), timevar_push(), update_debug_stmts(), and update_worklist().

static void update_debug_stmt ( )

static

Resets debug statement STMT if it has uses that are not dominated by their
   defs.   

References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), gimple_debug_bind_p(), gimple_debug_bind_reset_value(), and update_stmt().

Referenced by update_debug_stmts().

static void update_debug_stmts ( )

static

Resets all debug statements that have uses that are not
   dominated by their defs.   

References gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), is_gimple_debug(), and update_debug_stmt().

Referenced by tail_merge_optimize().

static void update_dep_bb ( )

static

Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB.   

References CDI_DOMINATORS, dominated_by_p(), and gimple_bb().

Referenced by same_succ_hash(), and stmt_update_dep_bb().

static void update_rep_bb ( )

static

Update C->rep_bb, given that BB is added to the cluster.   

References CDI_DOMINATORS, dominated_by_p(), and bb_cluster_def::rep_bb.

Referenced by add_bb_to_cluster(), and set_cluster().

static void update_worklist ( )

static

For deleted_bb_preds, find bbs with same successors.   

References bitmap_and_compl_into(), bitmap_clear(), bitmap_clear_bit(), find_same_succ_bb(), same_succ_def::remove(), same_succ_alloc(), and same_succ_flush_bbs().

Referenced by tail_merge_optimize().

static gimple vop_phi ( )

static

Returns the vop phi of BB, if any.   

References gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), and virtual_operand_p().

Referenced by replace_block_by().

---

Variable Documentation

vec<bb_cluster> all_clusters

static

Array that contains all clusters.   

bitmap deleted_bb_preds

static

Bitmap that is used to mark predecessors of bbs that are
   deleted.   

bitmap deleted_bbs

static

Bitmap that is used to mark bbs that are recently deleted.   

int* same_succ_edge_flags

static

Array that is used to store the edge flags for a successor.   

Referenced by delete_worklist(), find_same_succ_bb(), and init_worklist().

hash_table<same_succ_def> same_succ_htab

static

bitmap update_bbs

static

Bbs for which update_debug_stmt need to be called.   

vec<same_succ> worklist

static

Vector of bbs to process.