#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tm_p.h"
#include "basic-block.h"
#include "flags.h"
#include "function.h"
#include "gimple.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
#include "tree-into-ssa.h"
#include "tree-ssa-alias.h"
#include "params.h"
#include "hash-table.h"
#include "gimple-pretty-print.h"
#include "tree-ssa-sccvn.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-pass.h"

Include dependency graph for tree-ssa-tail-merge.c:

Data Structures
struct	same_succ_def
struct	bb_cluster_def
struct	aux_bb_info

Macros
#define	BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
#define	BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
#define	BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
#define	BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
#define	BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)

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

Macro Definition Documentation

#define BB_CLUSTER ( bb ) (((struct aux_bb_info *)bb->aux)->cluster)

Referenced by delete_cluster().

#define BB_DEP_BB ( bb ) (((struct aux_bb_info *)bb->aux)->dep_bb)

Referenced by same_phi_alternatives_1().

#define BB_SAME_SUCC ( bb ) (((struct aux_bb_info *)bb->aux)->bb_same_succ)

Referenced by add_to_worklist().

#define BB_SIZE ( bb ) (((struct aux_bb_info *)bb->aux)->size)

Macros to access the fields of struct aux_bb_info.

#define BB_VOP_AT_EXIT ( bb ) (((struct aux_bb_info *)bb->aux)->vop_at_exit)

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.

References BB_SAME_SUCC, and NULL.

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, BITMAP_ALLOC, NULL, 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, 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(), mark_virtual_operand_for_renaming(), and NULL_TREE.

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(), NULL, 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, GCOV_COMPUTE_SCALE, 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(), BB_FREQ_MAX, edge_def::count, basic_block_def::count, edge_def::dest, EDGE_COUNT, EDGE_PRED, find_edge(), FOR_EACH_EDGE, basic_block_def::frequency, gcc_assert, gimple_phi_result(), mark_basic_block_deleted(), basic_block_def::preds, redirect_edge_and_branch(), SSA_NAME_VAR, basic_block_def::succs, UNKNOWN_LOCATION, 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, FOR_EACH_EDGE, 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 BB_DEP_BB, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, cd, CDI_DOMINATORS, dominated_by_p(), FOR_EACH_EDGE, 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(), bitmap_clear_bit(), and ENTRY_BLOCK.

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 BASIC_BLOCK, 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, BITMAP_FREE, NULL, 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, EXECUTE_IF_SET_IN_BITMAP, 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

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation