#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"
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) |
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) |
Referenced by deps_ok_for_redirect(), find_clusters_1(), reset_cluster_vectors(), and set_cluster().
◆ BB_DEP_BB
| #define BB_DEP_BB | ( | bb | ) | (((struct aux_bb_info *)bb->aux)->dep_bb) |
Referenced by deps_ok_for_redirect_from_bb_to_bb(), update_dep_bb(), and update_rep_bb().
◆ BB_SAME_SUCC
| #define BB_SAME_SUCC | ( | bb | ) | (((struct aux_bb_info *)bb->aux)->bb_same_succ) |
Referenced by find_same_succ_bb(), and same_succ_flush_bb().
◆ 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 |
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()
Adds SAME to worklist.
References bitmap_count_bits(), ggc_alloc(), and worklist.
Referenced by find_same_succ_bb(), and mark_stmt_necessary().
◆ alloc_cluster_vectors()
Allocate all cluster vectors.
References all_clusters, cfun, and n_basic_blocks_for_fn.
Referenced by tail_merge_optimize().
◆ apply_clusters()
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, ggc_alloc(), i, NULL, bb_cluster::rep_bb, replace_block_by(), and update_bbs.
Referenced by tail_merge_optimize().
◆ 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(), NULL, phi_nodes(), phis, and virtual_operand_p().
Referenced by find_clusters_1().
◆ debug_cluster()
|
extern |
Prints cluster C to stderr.
References ggc_alloc(), and print_cluster().
◆ debug_same_succ()
|
extern |
Prints same_succ_htab to stderr.
References ggc_alloc(), same_succ_htab, and ssa_same_succ_print_traverse().
◆ delete_cluster()
|
static |
Delete clusters.
References bb_cluster::bbs, BITMAP_FREE, ggc_alloc(), NULL, and bb_cluster::preds.
Referenced by delete_cluster_vectors(), reset_cluster_vectors(), and set_cluster().
◆ delete_cluster_vectors()
Delete all cluster vectors.
References all_clusters, delete_cluster(), and i.
Referenced by tail_merge_optimize().
◆ delete_worklist()
Deletes worklist administration.
References BITMAP_FREE, deleted_bb_preds, deleted_bbs, free_aux_for_blocks(), ggc_alloc(), NULL, same_succ_edge_flags, same_succ_htab, and worklist.
Referenced by tail_merge_optimize().
◆ 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 BB_CLUSTER, deps_ok_for_redirect_from_bb_to_bb(), ggc_alloc(), and NULL.
Referenced by find_clusters_1().
◆ 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 BB_DEP_BB, BITMAP_ALLOC, BITMAP_FREE, bitmap_set_bit, cd, CDI_DOMINATORS, dominated_by_p(), FOR_EACH_EDGE, ggc_alloc(), nearest_common_dominator_for_set(), NULL, and basic_block_def::preds.
Referenced by deps_ok_for_redirect().
◆ find_clusters()
Find clusters of bbs which can be merged.
References dump_file, dump_flags, find_clusters_1(), ggc_alloc(), same_succ_print(), TDF_DETAILS, and worklist.
Referenced by tail_merge_optimize().
◆ find_clusters_1()
Within SAME_SUCC->bbs, find clusters of bbs which can be merged.
References BASIC_BLOCK_FOR_FN, BB_CLUSTER, bb_has_abnormal_pred(), bb_has_eh_pred(), bb_has_non_vop_phi(), same_succ::bbs, cfun, deps_ok_for_redirect(), EXECUTE_IF_SET_IN_BITMAP, find_duplicate(), ggc_alloc(), i, NULL, and same_phi_alternatives().
Referenced by find_clusters().
◆ find_duplicate()
|
static |
Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so, clusters them.
References DECL_NONLOCAL, dump_file, FORCED_LABEL, ggc_alloc(), gimple_equal_p(), gimple_label_label(), gsi_advance_bw_nondebug_nonlocal(), gsi_end_p(), gsi_last_nondebug_bb(), gsi_prev(), gsi_prev_nondebug(), gsi_stmt(), merge_stmts_p(), NULL_TREE, and set_cluster().
Referenced by find_clusters_1().
◆ find_same_succ()
Find bbs with same successors.
References cfun, find_same_succ_bb(), FOR_EACH_BB_FN, ggc_alloc(), NULL, same_succ::remove(), and same_succ_alloc().
Referenced by init_worklist().
◆ find_same_succ_bb()
|
static |
Add BB to same_succ_htab.
References add_to_worklist(), BB_SAME_SUCC, bitmap_set_bit, EXECUTE_IF_SET_IN_BITMAP, FOR_EACH_EDGE, ggc_alloc(), basic_block_def::index, inverse_flags(), NULL, same_succ_edge_flags, same_succ_hash(), same_succ_htab, same_succ_reset(), and basic_block_def::succs.
Referenced by find_same_succ(), and update_worklist().
◆ 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.
References bitmap_bit_p, gcc_checking_assert, ggc_alloc(), gimple_arg(), gimple_assign_rhs1(), gimple_assign_rhs_code(), gimple_bb(), gimple_call_arg(), gimple_call_chain(), gimple_call_num_args(), gimple_call_same_target_p(), gimple_cond_code(), gimple_cond_lhs(), gimple_cond_rhs(), gimple_get_lhs(), gimple_num_args(), gimple_operand_equal_value_p(), HONOR_NANS(), i, same_succ::inverse, invert_tree_comparison(), NULL_TREE, operand_equal_p(), tail_merge_valueize(), and TREE_CODE.
Referenced by find_duplicate().
◆ gimple_operand_equal_value_p()
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 |
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 ggc_alloc(), 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 |
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()
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, ggc_alloc(), NULL_TREE, tail_merge_valueize(), and TREE_CODE.
Referenced by gimple_operand_equal_value_p(), and same_phi_alternatives_1().
◆ init_worklist()
Initializes worklist administration.
References alloc_aux_for_blocks(), BITMAP_ALLOC, cfun, deleted_bb_preds, deleted_bbs, dump_file, dump_flags, find_same_succ(), ggc_alloc(), last_basic_block_for_fn, n_basic_blocks_for_fn, NULL, print_worklist(), same_succ_edge_flags, same_succ_htab, TDF_DETAILS, and worklist.
Referenced by tail_merge_optimize().
◆ 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.
References ggc_alloc(), and same_succ::succ_flags.
Referenced by same_succ::equal(), and find_same_succ_bb().
◆ mark_basic_block_deleted()
|
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 |
Merge cluster C2 into C1.
References bitmap_ior_into(), and ggc_alloc().
Referenced by set_cluster().
◆ merge_stmts_p()
Return true if equal (in the sense of gimple_equal_p) statements STMT1 and STMT2 are allowed to be merged.
References cfun, ggc_alloc(), 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 |
Allocate and init new cluster.
References bb_cluster::bbs, BITMAP_ALLOC, ggc_alloc(), NULL, bb_cluster::preds, and bb_cluster::rep_bb.
Referenced by set_cluster().
◆ print_cluster()
|
static |
Prints cluster C to FILE.
References bb_cluster::bbs, bitmap_print(), NULL, and bb_cluster::preds.
Referenced by debug_cluster().
◆ print_worklist()
Prints worklist to FILE.
References i, same_succ_print(), and worklist.
Referenced by init_worklist().
◆ 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(), i, mark_virtual_operand_for_renaming(), mark_virtual_phi_result_for_renaming(), NULL_TREE, and virtual_operand_p().
Referenced by replace_block_by().
◆ replace_block_by()
|
static |
Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed.
References add_phi_arg(), DECL_ARTIFICIAL, DECL_NONLOCAL, delete_basic_block(), EDGE_COUNT, EDGE_PRED, find_edge(), FOR_EACH_EDGE, FORCED_LABEL, gcc_assert, ggc_alloc(), gimple_label_label(), gimple_phi_result(), gsi_after_labels(), gsi_end_p(), gsi_move_before(), gsi_next(), gsi_start_bb(), gsi_stmt(), i, mark_basic_block_deleted(), NULL, redirect_edge_and_branch(), release_last_vdef(), reset_flow_sensitive_info_in_bb(), same_succ_flush_bb(), SSA_NAME_VAR, UNKNOWN_LOCATION, and vop_phi().
Referenced by apply_clusters().
◆ reset_cluster_vectors()
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 |
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(), ggc_alloc(), same_phi_alternatives_1(), and same_succ::succs.
Referenced by find_clusters_1().
◆ same_phi_alternatives_1()
|
static |
Returns whether for all phis in DEST the phi alternatives for E1 and E2 are equal.
References ggc_alloc(), 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()
Alloc and init a new SAME_SUCC.
References BITMAP_ALLOC, ggc_alloc(), and NULL.
Referenced by find_same_succ(), and update_worklist().
◆ same_succ_flush_bb()
|
static |
Removes BB from its corresponding same_succ.
References BB_SAME_SUCC, bitmap_clear_bit(), bitmap_single_bit_set_p(), ggc_alloc(), basic_block_def::index, NULL, and same_succ_htab.
Referenced by replace_block_by(), and same_succ_flush_bbs().
◆ same_succ_flush_bbs()
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()
Calculates hash value for same_succ VE.
References inchash::add_expr(), BASIC_BLOCK_FOR_FN, BB_SIZE, same_succ::bbs, bitmap_first_set_bit(), bitmap_hash(), cfun, EXECUTE_IF_SET_IN_BITMAP, find_edge(), ggc_alloc(), gimple_assign_rhs_code(), gimple_call_arg(), gimple_call_chain(), 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(), i, is_gimple_assign(), is_gimple_call(), is_gimple_debug(), basic_block_def::loop_father, loop::num, stmt_local_def(), stmt_update_dep_bb(), same_succ::succ_flags, same_succ::succs, tail_merge_valueize(), update_dep_bb(), and virtual_operand_p().
Referenced by find_same_succ_bb().
◆ same_succ_print()
Prints E to FILE.
References same_succ::bbs, bitmap_print(), ggc_alloc(), i, same_succ::inverse, same_succ::succ_flags, and same_succ::succs.
Referenced by find_clusters(), print_worklist(), and ssa_same_succ_print_traverse().
◆ same_succ_reset()
Reset same_succ SAME.
References bitmap_clear(), and ggc_alloc().
Referenced by find_same_succ_bb().
◆ 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(), all_clusters, BASIC_BLOCK_FOR_FN, BB_CLUSTER, bb_cluster::bbs, cfun, delete_cluster(), EXECUTE_IF_SET_IN_BITMAP, gcc_unreachable, ggc_alloc(), 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()
◆ stmt_local_def()
Returns true if the only effect a statement STMT has, is to define locally used SSA_NAMEs.
References DEF_FROM_PTR, EDGE_PRED, FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), gimple_could_trap_p_1(), gimple_has_side_effects(), gimple_vdef(), gimple_vuse(), is_gimple_call(), is_gimple_debug(), NULL, NULL_TREE, PHI_ARG_INDEX_FROM_USE, SINGLE_SSA_DEF_OPERAND, SSA_OP_DEF, TREE_CODE, and USE_STMT.
Referenced by gsi_advance_bw_nondebug_nonlocal(), gsi_advance_fw_nondebug_nonlocal(), and same_succ_hash().
◆ stmt_update_dep_bb()
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()
Runs tail merge optimization.
References all_clusters, alloc_cluster_vectors(), apply_clusters(), BITMAP_ALLOC, BITMAP_FREE, calculate_dominance_info(), CDI_DOMINATORS, cfun, 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(), gcc_assert, ggc_alloc(), init_worklist(), mark_virtual_operands_for_renaming(), MAY_HAVE_DEBUG_BIND_STMTS, NULL, reset_cluster_vectors(), same_succ_htab, split_edges_for_insertion(), TDF_DETAILS, timevar_pop(), timevar_push(), update_bbs, update_debug_stmts(), update_worklist(), and worklist.
◆ tail_merge_valueize()
Valueization helper querying the VN lattice.
References ggc_alloc(), 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()
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, ggc_alloc(), 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()
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 |
Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB.
References BB_DEP_BB, CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), 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 |
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()
For deleted_bb_preds, find bbs with same successors.
References BASIC_BLOCK_FOR_FN, bitmap_and_compl_into(), bitmap_clear(), bitmap_clear_bit(), cfun, deleted_bb_preds, deleted_bbs, ENTRY_BLOCK, EXECUTE_IF_SET_IN_BITMAP, find_same_succ_bb(), gcc_assert, ggc_alloc(), i, NULL, same_succ::remove(), same_succ_alloc(), and same_succ_flush_bbs().
Referenced by tail_merge_optimize().
◆ vop_phi()
|
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
|
static |
Array that contains all clusters.
Referenced by alloc_cluster_vectors(), apply_clusters(), delete_cluster_vectors(), reset_cluster_vectors(), set_cluster(), and tail_merge_optimize().
◆ 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
|
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
|
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
|
static |
Referenced by debug_same_succ(), delete_worklist(), find_same_succ_bb(), init_worklist(), same_succ_flush_bb(), and tail_merge_optimize().
◆ 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
Vector of bbs to process.
Referenced by add_to_worklist(), delete_worklist(), find_clusters(), init_worklist(), print_worklist(), and tail_merge_optimize().
