GCC Middle and Back End API Reference
tree-ssa-tail-merge.c File Reference

Data Structures

struct  same_succ_def
struct  bb_cluster_def
struct  aux_bb_info


typedef struct same_succ_defsame_succ
typedef struct same_succ_defconst_same_succ
typedef struct bb_cluster_defbb_cluster
typedef struct bb_cluster_defconst_bb_cluster


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


static hash_table< same_succ_defsame_succ_htab
static int * same_succ_edge_flags
static bitmap deleted_bbs
static bitmap deleted_bb_preds
static vec< same_succworklist
static vec< bb_clusterall_clusters
static bitmap update_bbs

Typedef Documentation

typedef struct bb_cluster_def* 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 ( )
   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 ( )
   Adds SAME to worklist.  
static void alloc_cluster_vectors ( )
   Allocate all cluster vectors.  
static int apply_clusters ( )
   For each cluster in all_clusters, merge all cluster->bbs.  Returns
   number of bbs removed.  
static bool bb_has_non_vop_phi ( )
   Return true if BB has non-vop phis.  
void debug_cluster ( bb_cluster  )
   Prints cluster C to stderr.  
DEBUG_FUNCTION void debug_cluster ( )
DEBUG_FUNCTION void debug_same_succ ( void  )
   Prints same_succ_htab to stderr.  
static void delete_cluster ( )
   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 ( )
   Delete all cluster vectors.  
static void delete_worklist ( )
static bool deps_ok_for_redirect ( )
   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 ( )
   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 ( )
   Find clusters of bbs which can be merged.  

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

static void find_clusters_1 ( )
   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
             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 ( )
   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 ( )
   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 ( )
   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 ( )
   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 
   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 ( )
   Let GSI skip forwards over local defs.  

Referenced by same_succ_def::equal().

static bool gvn_uses_equal ( )
   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 ( )
   Initializes worklist administration.  
static bool inverse_flags ( )
   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 ( )
   Mark BB as deleted, and mark its predecessors.  

Referenced by find_clusters_1().

static void merge_clusters ( )
   Merge cluster C2 into C1.  
static bb_cluster new_cluster ( )
   Allocate and init new cluster.  

Referenced by delete_cluster().

static void print_cluster ( )
   Prints cluster C to FILE.  
static void print_worklist ( )
static void release_last_vdef ( )
   Release the last vdef in BB, either normal or phi result.  
static void replace_block_by ( )
   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 ( )
   Reset all cluster vectors.  
static bool same_phi_alternatives ( )
   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 ( )
   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 ( )
   Alloc and init a new SAME_SUCC.  
static void same_succ_flush_bb ( )
   Removes BB from its corresponding same_succ.  

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

static void same_succ_flush_bbs ( )
   Removes all bbs in BBS from their corresponding same_succ.  
static hashval_t same_succ_hash ( )
   Calculates hash value for same_succ VE.  
static void same_succ_print ( )
   Prints E to FILE.  

Referenced by same_succ_reset().

static void same_succ_reset ( )
   Reset same_succ SAME.  

References same_succ_print().

static void set_cluster ( )
   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 ( )
   Prints same_succ VE to VFILE.  
static bool stmt_local_def ( )
   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 ( )
   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 ( )
   Resets debug statement STMT if it has uses that are not dominated by their
static void update_debug_stmts ( )
   Resets all debug statements that have uses that are not
   dominated by their defs.  
static void update_dep_bb ( )
   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 ( )
   Update C->rep_bb, given that BB is added to the cluster.  
     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 ( )
   For deleted_bb_preds, find bbs with same successors.  
static gimple vop_phi ( )
   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
   Array that contains all clusters.  
bitmap deleted_bb_preds
   Bitmap that is used to mark predecessors of bbs that are
bitmap deleted_bbs
   Bitmap that is used to mark bbs that are recently deleted.  
int* same_succ_edge_flags
   Array that is used to store the edge flags for a successor.  
hash_table<same_succ_def> same_succ_htab
bitmap update_bbs
   Bbs for which update_debug_stmt need to be called.  
vec<same_succ> worklist
   Vector of bbs to process.