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 delete_cluster().

Referenced by delete_cluster().

static void add_to_worklist ( )

static

   Adds SAME to worklist.

static void alloc_cluster_vectors ( )

static

   Allocate all cluster vectors.

static int apply_clusters ( )

static

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

static bool bb_has_non_vop_phi ( )

static

   Return true if BB has non-vop phis.

void debug_cluster ( bb_cluster )

   Prints cluster C to stderr.

DEBUG_FUNCTION void debug_cluster ( )

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

DEBUG_FUNCTION void debug_same_succ ( void )

   Prints same_succ_htab to stderr.

static void delete_cluster ( )

static

   Delete clusters.

References add_bb_to_cluster(), bb_cluster_def::index, and new_cluster().

Referenced by add_bb_to_cluster().

static void delete_cluster_vectors ( )

static

   Delete all cluster vectors.

static void delete_worklist ( )

static

   Deletes worklist administration.

References gimple_vdef(), gsi_end_p(), gsi_last_bb(), gsi_prev_nondebug(), gsi_stmt(), and mark_virtual_operand_for_renaming().

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 gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), and virtual_operand_p().

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.

static void find_clusters ( )

static

   Find clusters of bbs which can be merged.

References edge_def::count, and edge_def::probability.

static void find_clusters_1 ( )

static

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

         TODO: handle blocks with phi-nodes.  We'll have to find corresponding
         phi-nodes in bb1 and bb2, with the same alternatives for the same
         preds.

             Limit quadratic behaviour.

             This is a conservative dependency check.  We could test more
             precise for allowed replacement direction.

References add_phi_arg(), edge_def::count, basic_block_def::count, edge_def::dest, find_edge(), basic_block_def::frequency, gimple_phi_result(), mark_basic_block_deleted(), basic_block_def::preds, redirect_edge_and_branch(), basic_block_def::succs, and vop_phi().

static void find_duplicate ( )

static

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

     If the incoming vuses are not the same, and the vuse escaped into an
     SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
     which potentially means the semantics of one of the blocks will be changed.
     TODO: make this check more precise.

static void find_same_succ ( )

static

   Find bbs with same successors.

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

static void find_same_succ_bb ( )

static

   Add BB to same_succ_htab.

         Be conservative with loop structure.  It's not evident that this test
         is sufficient.  Before tail-merge, we've just called
         loop_optimizer_finalize, and LOOPS_MAY_HAVE_MULTIPLE_LATCHES is now
         set, so there's no guarantee that the loop->latch value is still valid.
         But we assume that, since we've forced LOOPS_HAVE_SIMPLE_LATCHES at the
         start of pre, we've kept that property intact throughout pre, and are
         keeping it throughout tail-merge using this test.

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.

         Eventually, we'll significantly complicate the CFG by adding
         back edges to properly model the effects of transaction restart.
         For the bulk of optimization this does not matter, but what we
         cannot recover from is tail merging blocks between two separate
         transactions.  Avoid that by making commit not match.

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.

static void gsi_advance_fw_nondebug_nonlocal ( )

static

   Let GSI skip forwards over local defs.

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.

static void init_worklist ( )

static

   Initializes worklist administration.

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.

static void mark_basic_block_deleted ( )

static

   Mark BB as deleted, and mark its predecessors.

Referenced by find_clusters_1().

static void merge_clusters ( )

static

   Merge cluster C2 into C1.

static bb_cluster new_cluster ( )

static

   Allocate and init new cluster.

Referenced by delete_cluster().

static void print_cluster ( )

static

   Prints cluster C to FILE.

static void print_worklist ( )

static

   Prints worklist to FILE.

References bitmap_set_bit(), edge_def::dest, edge_def::flags, basic_block_def::index, and same_succ_def::succs.

static void release_last_vdef ( )

static

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

static void replace_block_by ( )

static

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

     Mark the basic block as deleted.

     Redirect the incoming edges of bb1 to bb2.

         The phi might have run out of capacity when the redirect added an
         argument, which means it could have been replaced.  Refresh it.

     Merge the outgoing edge counts from bb1 onto bb2.

     Recompute the edge probabilities from the new merged edge count.
     Use the sum of the new merged edge counts computed above instead
     of bb2's merged count, in case there are profile count insanities
     making the bb count inconsistent with the edge weights.

     Do updates that use bb1, before deleting bb1.

static void reset_cluster_vectors ( )

static

   Reset all cluster vectors.

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.

         For all phis in bb, the phi alternatives for e1 and e2 need to have
         the same value.

static bool same_phi_alternatives_1 ( )

static

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

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

static same_succ same_succ_alloc ( )

static

   Alloc and init a new SAME_SUCC.

static void same_succ_flush_bb ( )

static

   Removes BB from its corresponding same_succ.

References bitmap_and_compl_into(), bitmap_clear(), and bitmap_clear_bit().

static void same_succ_flush_bbs ( )

static

   Removes all bbs in BBS from their corresponding same_succ.

static hashval_t same_succ_hash ( )

static

   Calculates hash value for same_succ VE.

static void same_succ_print ( )

static

   Prints E to FILE.

Referenced by same_succ_reset().

static void same_succ_reset ( )

static

   Reset same_succ SAME.

References same_succ_print().

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.

int ssa_same_succ_print_traverse ( )

inline

   Prints same_succ VE to VFILE.

static bool stmt_local_def ( )

static

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

Referenced by update_dep_bb().

static void stmt_update_dep_bb ( )

static

   Update BB_DEP_BB, given the dependencies in STMT.

Referenced by update_dep_bb().

unsigned int tail_merge_optimize ( )

   Runs tail merge optimization.

         We try to be conservative with respect to loop structure, since:
         - the cases where tail-merging could both affect loop structure and be
           beneficial are rare,
         - it prevents us from having to fixup the loops using
           loops_state_set (LOOPS_NEED_FIXUP), and
         - keeping loop structure may allow us to simplify the pass.
         In order to be conservative, we need loop information.  In rare cases
         (about 7 test-cases in the g++ testsuite) there is none (because
         loop_optimizer_finalize has been called before tail-merge, and
         PROP_loops is not set), so we bail out.

         PRE can leave us with unreachable blocks, remove them now.

static void update_debug_stmt ( )

static

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

static void update_debug_stmts ( )

static

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

static void update_dep_bb ( )

static

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

     Not a dep.

     Skip use of global def.

     Skip use of local def.

References bitmap_first_set_bit(), bitmap_hash(), first, gsi_end_p(), gsi_next_nondebug(), gsi_start_nondebug_bb(), gsi_stmt(), stmt_local_def(), and stmt_update_dep_bb().

static void update_rep_bb ( )

static

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

     Initial.

     Current needs no deps, keep it.

     Bb needs no deps, change rep_bb.

     Bb needs last deps earlier than current, change rep_bb.  A potential
     problem with this, is that the first deps might also be earlier, which
     would mean we prefer longer lifetimes for the deps.  To be able to check
     for this, we would have to trace BB_FIRST_DEP_BB as well, besides
     BB_DEP_BB, which is really BB_LAST_DEP_BB.
     The benefit of choosing the bb with last deps earlier, is that it can
     potentially be used as replacement for more bbs.

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

static void update_worklist ( )

static

   For deleted_bb_preds, find bbs with same successors.

static gimple vop_phi ( )

static

   Returns the vop phi of BB, if any.

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

Referenced by find_clusters_1().

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.

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.

Data Structures

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation