GCC Middle and Back End API Reference
tree-ssa-tail-merge.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "cfghooks.h"
#include "tree-pass.h"
#include "ssa.h"
#include "fold-const.h"
#include "trans-mem.h"
#include "cfganal.h"
#include "cfgcleanup.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-into-ssa.h"
#include "tree-ssa-sccvn.h"
#include "cfgloop.h"
#include "tree-eh.h"
#include "tree-cfgcleanup.h"
Include dependency graph for tree-ssa-tail-merge.cc:

Data Structures

struct  same_succ
 
struct  bb_cluster
 
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)
 

Functions

static tree tail_merge_valueize (tree name)
 
static bool stmt_local_def (gimple *stmt)
 
static void gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
 
static bool gvn_uses_equal (tree val1, tree val2)
 
static void same_succ_print (FILE *file, const same_succ *e)
 
int ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
 
static void update_dep_bb (basic_block use_bb, tree val)
 
static void stmt_update_dep_bb (gimple *stmt)
 
static hashval_t same_succ_hash (const same_succ *e)
 
static bool inverse_flags (const same_succ *e1, const same_succ *e2)
 
static same_succsame_succ_alloc (void)
 
static void same_succ_reset (same_succ *same)
 
void debug_same_succ (void)
 
static void print_worklist (FILE *file)
 
static void add_to_worklist (same_succ *same)
 
static void find_same_succ_bb (basic_block bb, same_succ **same_p)
 
static void find_same_succ (void)
 
static void init_worklist (void)
 
static void delete_worklist (void)
 
static void mark_basic_block_deleted (basic_block bb)
 
static void same_succ_flush_bb (basic_block bb)
 
static void same_succ_flush_bbs (bitmap bbs)
 
static void release_last_vdef (basic_block bb)
 
static void update_worklist (void)
 
static void print_cluster (FILE *file, bb_cluster *c)
 
void debug_cluster (bb_cluster *)
 
static void update_rep_bb (bb_cluster *c, basic_block bb)
 
static void add_bb_to_cluster (bb_cluster *c, basic_block bb)
 
static bb_clusternew_cluster (void)
 
static void delete_cluster (bb_cluster *c)
 
static void alloc_cluster_vectors (void)
 
static void reset_cluster_vectors (void)
 
static void delete_cluster_vectors (void)
 
static void merge_clusters (bb_cluster *c1, bb_cluster *c2)
 
static void set_cluster (basic_block bb1, basic_block bb2)
 
static bool gimple_operand_equal_value_p (tree t1, tree t2)
 
static bool gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
 
static void gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse, bool *vuse_escaped)
 
static bool merge_stmts_p (gimple *stmt1, gimple *stmt2)
 
static void find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
 
static bool same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
 
static bool same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
 
static bool bb_has_non_vop_phi (basic_block bb)
 
static bool deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
 
static bool deps_ok_for_redirect (basic_block bb1, basic_block bb2)
 
static void find_clusters_1 (same_succ *same_succ)
 
static void find_clusters (void)
 
static gphivop_phi (basic_block bb)
 
static void replace_block_by (basic_block bb1, basic_block bb2)
 
static int apply_clusters (void)
 
static void update_debug_stmt (gimple *stmt)
 
static void update_debug_stmts (void)
 
unsigned int tail_merge_optimize (bool need_crit_edge_split)
 

Variables

const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE
 
static hash_table< same_succ > * 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

◆ BB_CLUSTER

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

◆ BB_DEP_BB

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

◆ BB_SAME_SUCC

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

◆ BB_SIZE

#define BB_SIZE ( bb)    (((struct aux_bb_info *)bb->aux)->size)
Macros to access the fields of struct aux_bb_info.   

Referenced by same_succ::equal(), and same_succ_hash().

◆ BB_VOP_AT_EXIT

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

Function Documentation

◆ add_bb_to_cluster()

static void add_bb_to_cluster ( bb_cluster * c,
basic_block bb )
static
Add BB to cluster C.  Sets BB in C->bbs, and preds of BB in C->preds.   

References bb_cluster::bbs, bitmap_set_bit, FOR_EACH_EDGE, basic_block_def::index, basic_block_def::preds, bb_cluster::preds, and update_rep_bb().

Referenced by set_cluster().

◆ add_to_worklist()

static void add_to_worklist ( same_succ * same)
static
Adds SAME to worklist.   

References same_succ::bbs, bitmap_count_bits(), same_succ::in_worklist, and worklist.

Referenced by find_same_succ_bb(), and mark_stmt_necessary().

◆ alloc_cluster_vectors()

static void alloc_cluster_vectors ( void )
static
Allocate all cluster vectors.   

References all_clusters, cfun, and n_basic_blocks_for_fn.

Referenced by tail_merge_optimize().

◆ apply_clusters()

static int apply_clusters ( void )
static
For each cluster in all_clusters, merge all cluster->bbs.  Returns
number of bbs removed.   

References all_clusters, BASIC_BLOCK_FOR_FN, bb_cluster::bbs, bitmap_clear_bit(), bitmap_set_bit, cfun, EXECUTE_IF_SET_IN_BITMAP, i, basic_block_def::index, NULL, bb_cluster::rep_bb, replace_block_by(), and update_bbs.

Referenced by tail_merge_optimize().

◆ bb_has_non_vop_phi()

static bool bb_has_non_vop_phi ( basic_block bb)
static
Return true if BB has non-vop phis.   

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

Referenced by find_clusters_1().

◆ debug_cluster()

DEBUG_FUNCTION void debug_cluster ( bb_cluster * c)
extern
Prints cluster C to stderr.   

References print_cluster().

◆ debug_same_succ()

DEBUG_FUNCTION void debug_same_succ ( void )
extern
Prints same_succ_htab to stderr.   

References same_succ_htab, and ssa_same_succ_print_traverse().

◆ delete_cluster()

static void delete_cluster ( bb_cluster * c)
static

◆ delete_cluster_vectors()

static void delete_cluster_vectors ( void )
static
Delete all cluster vectors.   

References all_clusters, delete_cluster(), and i.

Referenced by tail_merge_optimize().

◆ delete_worklist()

static void delete_worklist ( void )
static

◆ deps_ok_for_redirect()

static bool deps_ok_for_redirect ( basic_block bb1,
basic_block bb2 )
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 BB_CLUSTER, deps_ok_for_redirect_from_bb_to_bb(), and NULL.

Referenced by find_clusters_1().

◆ deps_ok_for_redirect_from_bb_to_bb()

static bool deps_ok_for_redirect_from_bb_to_bb ( basic_block from,
basic_block to )
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 BB_DEP_BB, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, cd, CDI_DOMINATORS, dominated_by_p(), FOR_EACH_EDGE, nearest_common_dominator_for_set(), NULL, and basic_block_def::preds.

Referenced by deps_ok_for_redirect().

◆ find_clusters()

static void find_clusters ( void )
static
Find clusters of bbs which can be merged.   

References dump_file, dump_flags, find_clusters_1(), same_succ::in_worklist, same_succ_print(), TDF_DETAILS, and worklist.

Referenced by tail_merge_optimize().

◆ find_clusters_1()

static void find_clusters_1 ( same_succ * same_succ)
static

◆ find_duplicate()

static void find_duplicate ( same_succ * same_succ,
basic_block bb1,
basic_block bb2 )
static

◆ find_same_succ()

static void find_same_succ ( void )
static
Find bbs with same successors.   

References cfun, find_same_succ_bb(), FOR_EACH_BB_FN, NULL, same_succ::remove(), and same_succ_alloc().

Referenced by init_worklist().

◆ find_same_succ_bb()

◆ gimple_equal_p()

◆ gimple_operand_equal_value_p()

static bool gimple_operand_equal_value_p ( tree t1,
tree t2 )
static
Return true if gimple operands T1 and T2 have the same value.   

References gvn_uses_equal(), NULL_TREE, OEP_MATCH_SIDE_EFFECTS, and operand_equal_p().

Referenced by gimple_equal_p().

◆ gsi_advance_bw_nondebug_nonlocal()

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(), NULL_TREE, SSA_OP_DEF, stmt_local_def(), and ZERO_SSA_OPERANDS.

Referenced by find_duplicate().

◆ gsi_advance_fw_nondebug_nonlocal()

static void gsi_advance_fw_nondebug_nonlocal ( gimple_stmt_iterator * gsi)
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::equal().

◆ gvn_uses_equal()

static bool gvn_uses_equal ( tree val1,
tree val2 )
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 CONSTANT_CLASS_P, gcc_checking_assert, NULL_TREE, tail_merge_valueize(), and TREE_CODE.

Referenced by gimple_operand_equal_value_p(), and same_phi_alternatives_1().

◆ init_worklist()

◆ inverse_flags()

static bool inverse_flags ( const same_succ * e1,
const same_succ * e2 )
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::succ_flags.

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

◆ mark_basic_block_deleted()

static void mark_basic_block_deleted ( basic_block bb)
static
Mark BB as deleted, and mark its predecessors.   

References bitmap_set_bit, deleted_bb_preds, deleted_bbs, FOR_EACH_EDGE, basic_block_def::index, and basic_block_def::preds.

Referenced by replace_block_by().

◆ merge_clusters()

static void merge_clusters ( bb_cluster * c1,
bb_cluster * c2 )
static
Merge cluster C2 into C1.   

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

Referenced by set_cluster().

◆ merge_stmts_p()

static bool merge_stmts_p ( gimple * stmt1,
gimple * stmt2 )
static
Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
STMT2 are allowed to be merged.   

References cfun, gimple_call_internal_fn(), gimple_call_internal_p(), gimple_location(), is_gimple_call(), is_tm_ending(), and lookup_stmt_eh_lp_fn().

Referenced by find_duplicate().

◆ new_cluster()

static bb_cluster * new_cluster ( void )
static
Allocate and init new cluster.   

References bb_cluster::bbs, BITMAP_ALLOC, NULL, bb_cluster::preds, and bb_cluster::rep_bb.

Referenced by set_cluster().

◆ print_cluster()

static void print_cluster ( FILE * file,
bb_cluster * c )
static
Prints cluster C to FILE.   

References bb_cluster::bbs, bitmap_print(), NULL, and bb_cluster::preds.

Referenced by debug_cluster().

◆ print_worklist()

static void print_worklist ( FILE * file)
static
Prints worklist to FILE.   

References i, same_succ_print(), and worklist.

Referenced by init_worklist().

◆ release_last_vdef()

◆ replace_block_by()

◆ reset_cluster_vectors()

static void reset_cluster_vectors ( void )
static
Reset all cluster vectors.   

References all_clusters, BB_CLUSTER, cfun, delete_cluster(), FOR_EACH_BB_FN, i, and NULL.

Referenced by tail_merge_optimize().

◆ same_phi_alternatives()

static bool same_phi_alternatives ( same_succ * same_succ,
basic_block bb1,
basic_block bb2 )
static
Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
phi alternatives for BB1 and BB2 are equal.   

References BASIC_BLOCK_FOR_FN, cfun, EDGE_COMPLEX, EXECUTE_IF_SET_IN_BITMAP, find_edge(), same_phi_alternatives_1(), and same_succ::succs.

Referenced by find_clusters_1().

◆ same_phi_alternatives_1()

static bool same_phi_alternatives_1 ( basic_block dest,
edge e1,
edge e2 )
static
Returns whether for all phis in DEST the phi alternatives for E1 and
E2 are equal.   

References gimple_phi_arg_def(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gvn_uses_equal(), operand_equal_for_phi_arg_p(), gphi_iterator::phi(), and virtual_operand_p().

Referenced by same_phi_alternatives().

◆ same_succ_alloc()

static same_succ * same_succ_alloc ( void )
static

◆ same_succ_flush_bb()

static void same_succ_flush_bb ( basic_block bb)
static

◆ same_succ_flush_bbs()

static void same_succ_flush_bbs ( bitmap bbs)
static
Removes all bbs in BBS from their corresponding same_succ.   

References BASIC_BLOCK_FOR_FN, cfun, EXECUTE_IF_SET_IN_BITMAP, i, and same_succ_flush_bb().

Referenced by update_worklist().

◆ same_succ_hash()

◆ same_succ_print()

static void same_succ_print ( FILE * file,
const same_succ * e )
static

◆ same_succ_reset()

static void same_succ_reset ( same_succ * same)
static

◆ set_cluster()

static void set_cluster ( basic_block bb1,
basic_block bb2 )
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(), all_clusters, BASIC_BLOCK_FOR_FN, BB_CLUSTER, bb_cluster::bbs, cfun, delete_cluster(), EXECUTE_IF_SET_IN_BITMAP, gcc_unreachable, i, bb_cluster::index, merge_clusters(), new_cluster(), NULL, bb_cluster::rep_bb, and update_rep_bb().

Referenced by find_duplicate().

◆ ssa_same_succ_print_traverse()

int ssa_same_succ_print_traverse ( same_succ ** pe,
FILE * file )
inline
Prints same_succ VE to VFILE.   

References same_succ_print().

Referenced by debug_same_succ().

◆ stmt_local_def()

◆ stmt_update_dep_bb()

static void stmt_update_dep_bb ( gimple * stmt)
static
Update BB_DEP_BB, given the dependencies in STMT.   

References FOR_EACH_SSA_USE_OPERAND, gimple_bb(), SSA_OP_USE, update_dep_bb(), and USE_FROM_PTR.

Referenced by same_succ_hash().

◆ tail_merge_optimize()

◆ tail_merge_valueize()

static tree tail_merge_valueize ( tree name)
static
Valueization helper querying the VN lattice.   

References has_VN_INFO(), TREE_CODE, vn_ssa_aux::valnum, VN_INFO(), and VN_TOP.

Referenced by gimple_equal_p(), gvn_uses_equal(), and same_succ_hash().

◆ update_debug_stmt()

static void update_debug_stmt ( gimple * stmt)
static
Resets debug statement STMT if it has uses that are not dominated by their
defs.   

References CDI_DOMINATORS, dominated_by_p(), FOR_EACH_PHI_OR_STMT_USE, gimple_bb(), gimple_debug_bind_p(), gimple_debug_bind_reset_value(), NULL, SSA_NAME_DEF_STMT, SSA_OP_USE, update_stmt(), and USE_FROM_PTR.

Referenced by update_debug_stmts().

◆ update_debug_stmts()

static void update_debug_stmts ( void )
static
Resets all debug statements that have uses that are not
dominated by their defs.   

References BASIC_BLOCK_FOR_FN, cfun, EXECUTE_IF_SET_IN_BITMAP, gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, is_gimple_debug(), update_bbs, and update_debug_stmt().

Referenced by tail_merge_optimize().

◆ update_dep_bb()

static void update_dep_bb ( basic_block use_bb,
tree val )
static
Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB.   

References BB_DEP_BB, CDI_DOMINATORS, dominated_by_p(), gimple_bb(), NULL, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, and TREE_CODE.

Referenced by same_succ_hash(), and stmt_update_dep_bb().

◆ update_rep_bb()

static void update_rep_bb ( bb_cluster * c,
basic_block bb )
static
Update C->rep_bb, given that BB is added to the cluster.   

References BB_DEP_BB, CDI_DOMINATORS, dominated_by_p(), NULL, and bb_cluster::rep_bb.

Referenced by add_bb_to_cluster(), and set_cluster().

◆ update_worklist()

◆ vop_phi()

static gphi * vop_phi ( basic_block bb)
static
Returns the vop phi of BB, if any.   

References gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), NULL, gphi_iterator::phi(), and virtual_operand_p().

Referenced by replace_block_by().

Variable Documentation

◆ all_clusters

vec<bb_cluster *> all_clusters
static

◆ deleted_bb_preds

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

Referenced by delete_worklist(), init_worklist(), mark_basic_block_deleted(), and update_worklist().

◆ deleted_bbs

bitmap deleted_bbs
static
Bitmap that is used to mark bbs that are recently deleted.   

Referenced by delete_worklist(), init_worklist(), mark_basic_block_deleted(), and update_worklist().

◆ ignore_edge_flags

const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE
Tail merging for gimple.
   Copyright (C) 2011-2024 Free Software Foundation, Inc.
   Contributed by Tom de Vries (tom@codesourcery.com)

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3, or (at your option)
any later version.

GCC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.   
Pass overview.


MOTIVATIONAL EXAMPLE

gimple representation of gcc/testsuite/gcc.dg/pr43864.c at

hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
{
  struct FILED.1638 * fpD.2605;
  charD.1 fileNameD.2604[1000];
  intD.0 D.3915;
  const charD.1 * restrict outputFileName.0D.3914;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # PT = nonlocal { D.3926 } (restr)
  outputFileName.0D.3914_3
    = (const charD.1 * restrict) outputFileNameD.2600_2(D);
  # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
  # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
  if (D.3915_4 == 0)
    goto <bb 3>;
  else
    goto <bb 4>;
  # SUCC: 3 [10.0%]  (true,exec) 4 [90.0%]  (false,exec)

  # BLOCK 3 freq:1000
  # PRED: 2 [10.0%]  (true,exec)
  # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  freeD.898 (ctxD.2601_5(D));
  goto <bb 7>;
  # SUCC: 7 [100.0%]  (fallthru,exec)

  # BLOCK 4 freq:9000
  # PRED: 2 [90.0%]  (false,exec)
  # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
  # PT = nonlocal escaped
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
  if (fpD.2605_8 == 0B)
    goto <bb 5>;
  else
    goto <bb 6>;
  # SUCC: 5 [1.9%]  (true,exec) 6 [98.1%]  (false,exec)

  # BLOCK 5 freq:173
  # PRED: 4 [1.9%]  (true,exec)
  # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  freeD.898 (ctxD.2601_5(D));
  goto <bb 7>;
  # SUCC: 7 [100.0%]  (fallthru,exec)

  # BLOCK 6 freq:8827
  # PRED: 4 [98.1%]  (false,exec)
  # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
  # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
  # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
  fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
  # SUCC: 7 [100.0%]  (fallthru,exec)

  # BLOCK 7 freq:10000
  # PRED: 3 [100.0%]  (fallthru,exec) 5 [100.0%]  (fallthru,exec)
          6 [100.0%]  (fallthru,exec)
  # PT = nonlocal null

  # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
  # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
                    .MEMD.3923_18(6)>
  # VUSE <.MEMD.3923_11>
  return ctxD.2601_1;
  # SUCC: EXIT [100.0%]
}

bb 3 and bb 5 can be merged.  The blocks have different predecessors, but the
same successors, and the same operations.


CONTEXT

A technique called tail merging (or cross jumping) can fix the example
above.  For a block, we look for common code at the end (the tail) of the
predecessor blocks, and insert jumps from one block to the other.
The example is a special case for tail merging, in that 2 whole blocks
can be merged, rather than just the end parts of it.
We currently only focus on whole block merging, so in that sense
calling this pass tail merge is a bit of a misnomer.

We distinguish 2 kinds of situations in which blocks can be merged:
- same operations, same predecessors.  The successor edges coming from one
  block are redirected to come from the other block.
- same operations, same successors.  The predecessor edges entering one block
  are redirected to enter the other block.  Note that this operation might
  involve introducing phi operations.

For efficient implementation, we would like to value numbers the blocks, and
have a comparison operator that tells us whether the blocks are equal.
Besides being runtime efficient, block value numbering should also abstract
from irrelevant differences in order of operations, much like normal value
numbering abstracts from irrelevant order of operations.

For the first situation (same_operations, same predecessors), normal value
numbering fits well.  We can calculate a block value number based on the
value numbers of the defs and vdefs.

For the second situation (same operations, same successors), this approach
doesn't work so well.  We can illustrate this using the example.  The calls
to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
remain different in value numbering, since they represent different memory
states.  So the resulting vdefs of the frees will be different in value
numbering, so the block value numbers will be different.

The reason why we call the blocks equal is not because they define the same
values, but because uses in the blocks use (possibly different) defs in the
same way.  To be able to detect this efficiently, we need to do some kind of
reverse value numbering, meaning number the uses rather than the defs, and
calculate a block value number based on the value number of the uses.
Ideally, a block comparison operator will also indicate which phis are needed
to merge the blocks.

For the moment, we don't do block value numbering, but we do insn-by-insn
matching, using scc value numbers to match operations with results, and
structural comparison otherwise, while ignoring vop mismatches.


IMPLEMENTATION

1. The pass first determines all groups of blocks with the same successor
   blocks.
2. Within each group, it tries to determine clusters of equal basic blocks.
3. The clusters are applied.
4. The same successor groups are updated.
5. This process is repeated from 2 onwards, until no more changes.


LIMITATIONS/TODO

- block only
- handles only 'same operations, same successors'.
  It handles same predecessors as a special subcase though.
- does not implement the reverse value numbering and block value numbering.
- improve memory allocation: use garbage collected memory, obstacks,
  allocpools where appropriate.
- no insertion of gimple_reg phis,  We only introduce vop-phis.
- handle blocks with gimple_reg phi_nodes.


PASS PLACEMENT
This 'pass' is not a stand-alone gimple pass, but runs as part of
pass_pre, in order to share the value numbering.


SWITCHES

- ftree-tail-merge.  On at -O2.  We may have to enable it only at -Os.   

◆ same_succ_edge_flags

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

◆ same_succ_htab

◆ update_bbs

bitmap update_bbs
static
Bbs for which update_debug_stmt need to be called.   

Referenced by apply_clusters(), tail_merge_optimize(), and update_debug_stmts().

◆ worklist

vec<same_succ *> worklist
static