gcc/ChangeLog: 2015-07-09 Martin Liska <mli...@suse.cz>
* dbgcnt.def: Add new debug counter. * ipa-icf-gimple.c (func_checker::compare_ssa_name): Add flag for strict mode. (func_checker::compare_memory_operand): Likewise. (func_checker::compare_cst_or_decl): Handle if we are in tail_merge_mode. (func_checker::compare_operand): Pass strict flag properly. (func_checker::stmt_local_def): New function. (func_checker::compare_phi_node): Move from sem_function class. (func_checker::compare_bb_tail_merge): New function. (func_checker::compare_bb): Improve STMT iteration. (func_checker::compare_gimple_call): Pass strict flag. (func_checker::compare_gimple_assign): Likewise. (func_checker::compare_gimple_label): Remove unused flag. (ssa_names_set): New class. (ssa_names_set::build): New function. * ipa-icf-gimple.h (func_checker::gsi_next_nonlocal): New function. (ssa_names_set::contains): New function. (ssa_names_set::add): Likewise. * ipa-icf.c (sem_function::equals_private): Use transformed function. (sem_function::compare_phi_node): Move to func_checker class. * ipa-icf.h: Add new declarations. * tree-ssa-tail-merge.c (check_edges_correspondence): New function. (find_duplicate): Add usage of IPA ICF gimple infrastructure. (find_clusters_1): Pass new sem_function argument. (find_clusters): Likewise. (tail_merge_optimize): Call IPA ICF comparison machinery. --- gcc/dbgcnt.def | 1 + gcc/ipa-icf-gimple.c | 272 ++++++++++++++++++++++++++++++++++++++++++---- gcc/ipa-icf-gimple.h | 78 +++++++++++-- gcc/ipa-icf.c | 67 +----------- gcc/ipa-icf.h | 14 ++- gcc/tree-ssa-tail-merge.c | 87 +++++++++++++-- 6 files changed, 407 insertions(+), 112 deletions(-) diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def index 95f6b06..79d99d9 100644 --- a/gcc/dbgcnt.def +++ b/gcc/dbgcnt.def @@ -187,6 +187,7 @@ DEBUG_COUNTER (sms_sched_loop) DEBUG_COUNTER (split_for_sched2) DEBUG_COUNTER (store_motion) DEBUG_COUNTER (tail_call) +DEBUG_COUNTER (tail_merge) DEBUG_COUNTER (treepre_insert) DEBUG_COUNTER (tree_sra) DEBUG_COUNTER (vect_loop) diff --git a/gcc/ipa-icf-gimple.c b/gcc/ipa-icf-gimple.c index e727693..df99c0d 100644 --- a/gcc/ipa-icf-gimple.c +++ b/gcc/ipa-icf-gimple.c @@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see #include <list> #include "tree-eh.h" #include "builtins.h" +#include "trans-mem.h" #include "ipa-icf-gimple.h" #include "ipa-icf.h" @@ -69,14 +70,14 @@ namespace ipa_icf_gimple { func_checker::func_checker (tree source_func_decl, tree target_func_decl, bool compare_polymorphic, - bool ignore_labels, + bool tail_merge_mode, hash_set<symtab_node *> *ignored_source_nodes, hash_set<symtab_node *> *ignored_target_nodes) : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl), m_ignored_source_nodes (ignored_source_nodes), m_ignored_target_nodes (ignored_target_nodes), m_compare_polymorphic (compare_polymorphic), - m_ignore_labels (ignore_labels) + m_tail_merge_mode (tail_merge_mode) { function *source_func = DECL_STRUCT_FUNCTION (source_func_decl); function *target_func = DECL_STRUCT_FUNCTION (target_func_decl); @@ -102,10 +103,11 @@ func_checker::~func_checker () m_target_ssa_names.release(); } -/* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */ +/* Verifies that trees T1 and T2 are equivalent from perspective of ICF. + If STRICT flag is true, versions must match strictly. */ bool -func_checker::compare_ssa_name (tree t1, tree t2) +func_checker::compare_ssa_name (tree t1, tree t2, bool strict) { gcc_assert (TREE_CODE (t1) == SSA_NAME); gcc_assert (TREE_CODE (t2) == SSA_NAME); @@ -113,6 +115,10 @@ func_checker::compare_ssa_name (tree t1, tree t2) unsigned i1 = SSA_NAME_VERSION (t1); unsigned i2 = SSA_NAME_VERSION (t2); + if (strict && m_tail_merge_mode) + return t1 == t2 || + (m_source_ssa_names[i1] != -1 && m_source_ssa_names[i1] == (int) i2); + if (m_source_ssa_names[i1] == -1) m_source_ssa_names[i1] = i2; else if (m_source_ssa_names[i1] != (int) i2) @@ -256,10 +262,11 @@ func_checker::compatible_types_p (tree t1, tree t2) return true; } -/* Function compare for equality given memory operands T1 and T2. */ +/* Function compare for equality given memory operands T1 and T2. + If STRICT flag is true, versions must match strictly. */ bool -func_checker::compare_memory_operand (tree t1, tree t2) +func_checker::compare_memory_operand (tree t1, tree t2, bool strict) { if (!t1 && !t2) return true; @@ -327,7 +334,7 @@ func_checker::compare_memory_operand (tree t1, tree t2) return return_false_with_msg ("different dependence info"); } - return compare_operand (t1, t2); + return compare_operand (t1, t2, strict); } /* Function compare for equality given trees T1 and T2 which @@ -351,11 +358,18 @@ func_checker::compare_cst_or_decl (tree t1, tree t2) return return_with_debug (ret); } case FUNCTION_DECL: - /* All function decls are in the symbol table and known to match + /* If we are called within an invocation of IPA ICF, + all function decls are in the symbol table and known to match before we start comparing bodies. */ - return true; + return m_tail_merge_mode ? t1 == t2 : true; case VAR_DECL: - return return_with_debug (compare_variable_decl (t1, t2)); + { + /* Be strict in case of tail-merge optimization. */ + if (m_tail_merge_mode) + return t1 == t2; + + return return_with_debug (compare_variable_decl (t1, t2)); + } case FIELD_DECL: { tree offset1 = DECL_FIELD_OFFSET (t1); @@ -371,6 +385,10 @@ func_checker::compare_cst_or_decl (tree t1, tree t2) } case LABEL_DECL: { + /* Be strict in case of tail-merge optimization. */ + if (m_tail_merge_mode) + return t1 == t2; + int *bb1 = m_label_bb_map.get (t1); int *bb2 = m_label_bb_map.get (t2); @@ -380,6 +398,9 @@ func_checker::compare_cst_or_decl (tree t1, tree t2) case RESULT_DECL: case CONST_DECL: { + if (m_tail_merge_mode) + return t1 == t2; + ret = compare_decl (t1, t2); return return_with_debug (ret); } @@ -393,7 +414,7 @@ func_checker::compare_cst_or_decl (tree t1, tree t2) is returned. */ bool -func_checker::compare_operand (tree t1, tree t2) +func_checker::compare_operand (tree t1, tree t2, bool strict) { tree x1, x2, y1, y2, z1, z2; bool ret; @@ -465,7 +486,7 @@ func_checker::compare_operand (tree t1, tree t2) if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2))) return return_false (); - if (!compare_operand (x1, x2)) + if (!compare_operand (x1, x2, strict)) return return_false_with_msg (""); /* Type of the offset on MEM_REF does not matter. */ @@ -486,7 +507,8 @@ func_checker::compare_operand (tree t1, tree t2) /* Virtual table call. */ case OBJ_TYPE_REF: { - if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2))) + if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2), + strict)) return return_false (); if (opt_for_fn (m_source_func_decl, flag_devirtualize) && virtual_method_call_p (t1)) @@ -530,7 +552,7 @@ func_checker::compare_operand (tree t1, tree t2) return return_with_debug (ret); } case SSA_NAME: - return compare_ssa_name (t1, t2); + return compare_ssa_name (t1, t2, strict); case INTEGER_CST: case COMPLEX_CST: case VECTOR_CST: @@ -626,6 +648,136 @@ func_checker::parse_labels (sem_bb *bb) } } +/* Return true if gimple STMT is just a local difinition in a + basic block. Used SSA names are contained in SSA_NAMES_SET. */ + +bool +func_checker::stmt_local_def (gimple stmt, ssa_names_set *ssa_names_set) +{ + basic_block bb, def_bb; + imm_use_iterator iter; + use_operand_p use_p; + tree val; + def_operand_p def_p; + + if (gimple_vdef (stmt) != NULL_TREE + || gimple_has_side_effects (stmt) + || gimple_could_trap_p_1 (stmt, false, false) + || gimple_vuse (stmt) != NULL_TREE) + return false; + + def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); + if (def_p == NULL) + return false; + + val = DEF_FROM_PTR (def_p); + if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME) + return false; + + def_bb = gimple_bb (stmt); + + FOR_EACH_IMM_USE_FAST (use_p, iter, val) + { + if (is_gimple_debug (USE_STMT (use_p))) + continue; + bb = gimple_bb (USE_STMT (use_p)); + if (bb == def_bb) + continue; + + if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI + && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb) + continue; + + return false; + } + + for (unsigned i = 0; i < gimple_num_ops (stmt); i++) + if (ssa_names_set && ssa_names_set->contains (gimple_op (stmt, i))) + return false; + + return true; +} + +/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC), + return true if phi nodes are semantically equivalent in these blocks. */ + +bool +func_checker::compare_phi_node (sem_bb *sem_bb1, sem_bb *sem_bb2) +{ + gphi_iterator si1, si2; + gphi *phi1, *phi2; + unsigned size1, size2, i; + tree t1, t2; + edge e1, e2; + + basic_block bb1 = sem_bb1->bb; + basic_block bb2 = sem_bb2->bb; + + gcc_assert (bb1 != NULL); + gcc_assert (bb2 != NULL); + + si2 = gsi_start_phis (bb2); + for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1); + gsi_next (&si1)) + { + gsi_next_nonvirtual_phi (&si1); + gsi_next_nonvirtual_phi (&si2); + + if (gsi_end_p (si1) && gsi_end_p (si2)) + break; + + if (gsi_end_p (si1) || gsi_end_p (si2)) + return return_false (); + + phi1 = si1.phi (); + phi2 = si2.phi (); + + tree phi_result1 = gimple_phi_result (phi1); + tree phi_result2 = gimple_phi_result (phi2); + + if (!compare_operand (phi_result1, phi_result2)) + return return_false_with_msg ("PHI results are different"); + + size1 = gimple_phi_num_args (phi1); + size2 = gimple_phi_num_args (phi2); + + if (size1 != size2) + return return_false (); + + for (i = 0; i < size1; ++i) + { + t1 = gimple_phi_arg (phi1, i)->def; + t2 = gimple_phi_arg (phi2, i)->def; + + if (!compare_operand (t1, t2)) + return return_false (); + + e1 = gimple_phi_arg_edge (phi1, i); + e2 = gimple_phi_arg_edge (phi2, i); + + if (!compare_edge (e1, e2)) + return return_false (); + } + + gsi_next (&si2); + } + + return true; +} + + +bool +func_checker::compare_bb_tail_merge (sem_bb *bb1, sem_bb *bb2) +{ + if (!compare_bb (bb1, bb2)) + return return_false_with_msg ("BB are different"); + + if (!compare_phi_node (bb1, bb2)) + return return_false_with_msg ("PHI nodes are different"); + + return true; +} + /* Basic block equivalence comparison function that returns true if basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond. @@ -642,20 +794,39 @@ func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2) gsi1 = gsi_start_bb_nondebug (bb1->bb); gsi2 = gsi_start_bb_nondebug (bb2->bb); - while (!gsi_end_p (gsi1)) + ssa_names_set ssa_names_set1; + ssa_names_set ssa_names_set2; + + ssa_names_set1.build (bb1->bb); + ssa_names_set2.build (bb2->bb); + + while (true) { - if (gsi_end_p (gsi2)) - return return_false (); + if (m_tail_merge_mode) + { + gsi_next_nonlocal (&gsi1, &ssa_names_set1); + gsi_next_nonlocal (&gsi2, &ssa_names_set2); + } + + if (gsi_end_p (gsi1) || gsi_end_p (gsi2)) + break; s1 = gsi_stmt (gsi1); s2 = gsi_stmt (gsi2); + /* What could be better than to this this here is to blacklist the bb + containing the stmt, when encountering the stmt f.i. in + same_succ_hash. */ + if (is_tm_ending (s1) + || is_tm_ending (s2)) + return return_false_with_msg ("TM endings are different"); + int eh1 = lookup_stmt_eh_lp_fn (DECL_STRUCT_FUNCTION (m_source_func_decl), s1); int eh2 = lookup_stmt_eh_lp_fn (DECL_STRUCT_FUNCTION (m_target_func_decl), s2); - if (eh1 != eh2) + if (eh1 != eh2 && !m_tail_merge_mode) return return_false_with_msg ("EH regions are different"); if (gimple_code (s1) != gimple_code (s2)) @@ -723,7 +894,7 @@ func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2) gsi_next_nondebug (&gsi2); } - if (!gsi_end_p (gsi2)) + if (!gsi_end_p (gsi1) || !gsi_end_p (gsi2)) return return_false (); return true; @@ -789,7 +960,7 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2) t1 = gimple_get_lhs (s1); t2 = gimple_get_lhs (s2); - return compare_memory_operand (t1, t2); + return compare_memory_operand (t1, t2, false); } @@ -820,7 +991,7 @@ func_checker::compare_gimple_assign (gimple s1, gimple s2) arg1 = gimple_op (s1, i); arg2 = gimple_op (s2, i); - if (!compare_memory_operand (arg1, arg2)) + if (!compare_memory_operand (arg1, arg2, i != 0)) return return_false_with_msg ("memory operands are different"); } @@ -869,9 +1040,6 @@ func_checker::compare_tree_ssa_label (tree t1, tree t2) bool func_checker::compare_gimple_label (const glabel *g1, const glabel *g2) { - if (m_ignore_labels) - return true; - tree t1 = gimple_label_label (g1); tree t2 = gimple_label_label (g2); @@ -1037,4 +1205,60 @@ func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2) return true; } +void +ssa_names_set::build (basic_block bb) +{ + tree var; + ssa_op_iter iter; + + /* Build default set of important SSA names. */ + gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb); + + while (!gsi_end_p (gsi)) + { + gimple stmt = gsi_stmt (gsi); + if (!func_checker::stmt_local_def (stmt, NULL)) + for (unsigned i = 0; i < gimple_num_ops (stmt); i++) + add (gimple_op (stmt, i)); + + gsi_next_nondebug (&gsi); + } + + /* Process reverse run. */ + gsi = gsi_last_nondebug_bb (bb); + + while (!gsi_end_p (gsi)) + { + gimple stmt = gsi_stmt (gsi); + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + { + tree lhs = gimple_assign_lhs (stmt); + if (contains (lhs)) + { + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) + add (var); + } + break; + } + case GIMPLE_COND: + case GIMPLE_SWITCH: + case GIMPLE_CALL: + case GIMPLE_RETURN: + { + FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) + add (var); + + break; + } + default: + break; + } + + gsi_prev_nondebug (&gsi); + } +} + } // ipa_icf_gimple namespace diff --git a/gcc/ipa-icf-gimple.h b/gcc/ipa-icf-gimple.h index 6a9cbed..674e95d 100644 --- a/gcc/ipa-icf-gimple.h +++ b/gcc/ipa-icf-gimple.h @@ -112,7 +112,8 @@ namespace ipa_icf_gimple { class sem_bb { public: - sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_): + sem_bb (basic_block bb_, unsigned nondbg_stmt_count_ = 0, + unsigned edge_count_ = 0): bb (bb_), nondbg_stmt_count (nondbg_stmt_count_), edge_count (edge_count_) {} /* Basic block the structure belongs to. */ @@ -125,6 +126,9 @@ public: unsigned edge_count; }; +/* Forward declaration. */ +class ssa_names_set; + /* A class aggregating all connections and semantic equivalents for a given pair of semantic function candidates. */ class func_checker @@ -138,7 +142,7 @@ public: of declarations that can be skipped. */ func_checker (tree source_func_decl, tree target_func_decl, bool compare_polymorphic, - bool ignore_labels = false, + bool tail_merge_mode = false, hash_set<symtab_node *> *ignored_source_nodes = NULL, hash_set<symtab_node *> *ignored_target_nodes = NULL); @@ -149,12 +153,20 @@ public: mapping between basic blocks and labels. */ void parse_labels (sem_bb *bb); + /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC), + true value is returned if phi nodes are semantically + equivalent in these blocks. */ + bool compare_phi_node (sem_bb *sem_bb1, sem_bb *sem_bb2); + + /* Run tail-merge comparison for basic blocks BB1 and BB2. */ + bool compare_bb_tail_merge (sem_bb *bb1, sem_bb *bb2); + /* Basic block equivalence comparison function that returns true if basic blocks BB1 and BB2 correspond. */ bool compare_bb (sem_bb *bb1, sem_bb *bb2); /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */ - bool compare_ssa_name (tree t1, tree t2); + bool compare_ssa_name (tree t1, tree t2, bool strict = true); /* Verification function for edges E1 and E2. */ bool compare_edge (edge e1, edge e2); @@ -204,7 +216,7 @@ public: bool compare_tree_ssa_label (tree t1, tree t2); /* Function compare for equality given memory operands T1 and T2. */ - bool compare_memory_operand (tree t1, tree t2); + bool compare_memory_operand (tree t1, tree t2, bool strict = true); /* Function compare for equality given trees T1 and T2 which can be either a constant or a declaration type. */ @@ -213,7 +225,7 @@ public: /* Function responsible for comparison of various operands T1 and T2. If these components, from functions FUNC1 and FUNC2, are equal, true is returned. */ - bool compare_operand (tree t1, tree t2); + bool compare_operand (tree t1, tree t2, bool strict = false); /* Compares two tree list operands T1 and T2 and returns true if these two trees are semantically equivalent. */ @@ -237,6 +249,13 @@ public: first parameter of a function. */ static bool compatible_types_p (tree t1, tree t2); + /* Return true if gimple STMT is just a local difinition in a + basic block. Used SSA names are contained in SSA_NAMES_SET. */ + static bool stmt_local_def (gimple stmt, ssa_names_set *ssa_names_set); + + /* Advance the iterator to the next non-local gimple statement. */ + static void gsi_next_nonlocal (gimple_stmt_iterator *i, + ssa_names_set *ssa_names_set); private: /* Vector mapping source SSA names to target ones. */ @@ -271,8 +290,53 @@ private: /* Flag if polymorphic comparison should be executed. */ bool m_compare_polymorphic; - /* Flag if ignore labels in comparison. */ - bool m_ignore_labels; + /* Flag which changes behavior for tree-ssa-tail-merge pass. */ + bool m_tail_merge_mode; +}; + +/* SSA NAMES set. */ +class ssa_names_set +{ +public: + /* Return true if SSA_NAME is in the set. */ + bool contains (tree ssa_name); + + /* Add a new SSA_NAME to the set. */ + void add (tree ssa_name); + + /* Build the set for given basic block BB. */ + void build (basic_block bb); + +private: + hash_set <tree> m_set; }; +inline void +func_checker::gsi_next_nonlocal (gimple_stmt_iterator *i, + ssa_names_set *ssa_names_set) +{ + while (!gsi_end_p (*i) && + (is_gimple_debug (gsi_stmt (*i)) + || func_checker::stmt_local_def (gsi_stmt (*i), ssa_names_set))) + gsi_next (i); +} + +inline bool +ssa_names_set::contains (tree ssa_name) +{ + if (ssa_name == NULL || TREE_CODE (ssa_name) != SSA_NAME) + return false; + + return m_set.contains (ssa_name); +} + +inline void +ssa_names_set::add (tree ssa_name) +{ + if (ssa_name == NULL || TREE_CODE (ssa_name) != SSA_NAME) + return; + + m_set.add (ssa_name); +} + } // ipa_icf_gimple namespace diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c index c4386c0..7e65bce 100644 --- a/gcc/ipa-icf.c +++ b/gcc/ipa-icf.c @@ -995,7 +995,8 @@ sem_function::equals_private (sem_item *item) /* Basic block PHI nodes comparison. */ for (unsigned i = 0; i < bb_sorted.length (); i++) - if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb)) + if (!m_checker->compare_phi_node (bb_sorted[i], + m_compared_func->bb_sorted[i])) return return_false_with_msg ("PHI node comparison returns false"); return result; @@ -1707,70 +1708,6 @@ sem_function::parse (cgraph_node *node, bitmap_obstack *stack) return f; } -/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC), - return true if phi nodes are semantically equivalent in these blocks . */ - -bool -sem_function::compare_phi_node (basic_block bb1, basic_block bb2) -{ - gphi_iterator si1, si2; - gphi *phi1, *phi2; - unsigned size1, size2, i; - tree t1, t2; - edge e1, e2; - - gcc_assert (bb1 != NULL); - gcc_assert (bb2 != NULL); - - si2 = gsi_start_phis (bb2); - for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1); - gsi_next (&si1)) - { - gsi_next_nonvirtual_phi (&si1); - gsi_next_nonvirtual_phi (&si2); - - if (gsi_end_p (si1) && gsi_end_p (si2)) - break; - - if (gsi_end_p (si1) || gsi_end_p (si2)) - return return_false(); - - phi1 = si1.phi (); - phi2 = si2.phi (); - - tree phi_result1 = gimple_phi_result (phi1); - tree phi_result2 = gimple_phi_result (phi2); - - if (!m_checker->compare_operand (phi_result1, phi_result2)) - return return_false_with_msg ("PHI results are different"); - - size1 = gimple_phi_num_args (phi1); - size2 = gimple_phi_num_args (phi2); - - if (size1 != size2) - return return_false (); - - for (i = 0; i < size1; ++i) - { - t1 = gimple_phi_arg (phi1, i)->def; - t2 = gimple_phi_arg (phi2, i)->def; - - if (!m_checker->compare_operand (t1, t2)) - return return_false (); - - e1 = gimple_phi_arg_edge (phi1, i); - e2 = gimple_phi_arg_edge (phi2, i); - - if (!m_checker->compare_edge (e1, e2)) - return return_false (); - } - - gsi_next (&si2); - } - - return true; -} - /* Returns true if tree T can be compared as a handled component. */ bool diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h index 67d5bdc..6d67e52 100644 --- a/gcc/ipa-icf.h +++ b/gcc/ipa-icf.h @@ -355,15 +355,19 @@ public: /* Return true if parameter I may be used. */ bool param_used_p (unsigned int i); + /* Set a new function checker. */ + void set_checker (ipa_icf_gimple::func_checker *checker) + { + if (m_checker) + delete m_checker; + + m_checker = checker; + } + private: /* Calculates hash value based on a BASIC_BLOCK. */ hashval_t get_bb_hash (const ipa_icf_gimple::sem_bb *basic_block); - /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC), - true value is returned if phi nodes are semantically - equivalent in these blocks . */ - bool compare_phi_node (basic_block bb1, basic_block bb2); - /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB corresponds to TARGET. */ bool bb_dict_test (vec<int> *bb_dict, int source, int target); diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c index 018a966..b8632d7 100644 --- a/gcc/tree-ssa-tail-merge.c +++ b/gcc/tree-ssa-tail-merge.c @@ -187,6 +187,7 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" +#include <list> #include "coretypes.h" #include "backend.h" #include "tree.h" @@ -197,6 +198,7 @@ along with GCC; see the file COPYING3. If not see #include "fold-const.h" #include "stor-layout.h" #include "trans-mem.h" +#include "inchash.h" #include "tm_p.h" #include "cfganal.h" #include "cfgcleanup.h" @@ -213,6 +215,15 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-pass.h" #include "trans-mem.h" +#include "ipa-ref.h" +#include "lto-streamer.h" +#include "cgraph.h" +#include "ipa-icf-gimple.h" +#include "ipa-icf.h" +#include "dbgcnt.h" + +using namespace ipa_icf; +using namespace ipa_icf_gimple; /* Describes a group of bbs with the same successors. The successor bbs are cached in succs, and the successor edge flags are cached in succ_flags. @@ -1220,17 +1231,48 @@ gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse, } } +static bool +check_edges_correspondence (basic_block bb1, basic_block bb2) +{ + edge e1, e2; + edge_iterator ei2 = ei_start (bb2->succs); + + for (edge_iterator ei1 = ei_start (bb1->succs); ei_cond (ei1, &e1); + ei_next (&ei1)) + { + ei_cond (ei2, &e2); + + if (e1->dest->index != e2->dest->index || + (e1->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)) + != (e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) + return false; + + ei_next (&ei2); + } + + return true; +} + + /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so, clusters them. */ static void -find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2) +find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2, + sem_function &f) { gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1); gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2); tree vuse1 = NULL_TREE, vuse2 = NULL_TREE; bool vuse_escaped = false; + sem_bb sem_bb1 = sem_bb (bb1); + sem_bb sem_bb2 = sem_bb (bb2); + + func_checker *checker = new func_checker (f.decl, f.decl, true, true); + f.set_checker (checker); + bool icf_result = checker->compare_bb_tail_merge (&sem_bb1, &sem_bb2); + gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped); gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped); @@ -1244,10 +1286,10 @@ find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2) same_succ_hash. */ if (is_tm_ending (stmt1) || is_tm_ending (stmt2)) - return; + goto diff; if (!gimple_equal_p (same_succ, stmt1, stmt2)) - return; + goto diff; gsi_prev_nondebug (&gsi1); gsi_prev_nondebug (&gsi2); @@ -1265,11 +1307,29 @@ find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2) if (vuse_escaped && vuse1 != vuse2) return; - if (dump_file) - fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n", + if (!icf_result && dump_file) + fprintf (dump_file, + "missed merge optimization: <bb %d> duplicate of <bb %d>\n", bb1->index, bb2->index); - set_cluster (bb1, bb2); + if (dbg_cnt (tail_merge)) + set_cluster (bb1, bb2); + + return; + +diff: + if (!check_edges_correspondence (bb1, bb2)) + return; + + if (icf_result) + { + if (dump_file) + fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n", + bb1->index, bb2->index); + + if (dbg_cnt (tail_merge)) + set_cluster (bb1, bb2); + } } /* Returns whether for all phis in DEST the phi alternatives for E1 and @@ -1391,7 +1451,7 @@ deps_ok_for_redirect (basic_block bb1, basic_block bb2) /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */ static void -find_clusters_1 (same_succ same_succ) +find_clusters_1 (same_succ same_succ, sem_function &f) { basic_block bb1, bb2; unsigned int i, j; @@ -1433,7 +1493,7 @@ find_clusters_1 (same_succ same_succ) if (!(same_phi_alternatives (same_succ, bb1, bb2))) continue; - find_duplicate (same_succ, bb1, bb2); + find_duplicate (same_succ, bb1, bb2, f); } } } @@ -1441,7 +1501,7 @@ find_clusters_1 (same_succ same_succ) /* Find clusters of bbs which can be merged. */ static void -find_clusters (void) +find_clusters (sem_function &f) { same_succ same; @@ -1454,7 +1514,7 @@ find_clusters (void) fprintf (dump_file, "processing worklist entry\n"); same_succ_print (dump_file, same); } - find_clusters_1 (same); + find_clusters_1 (same, f); } } @@ -1659,6 +1719,10 @@ tail_merge_optimize (unsigned int todo) } init_worklist (); + bitmap_obstack b; + bitmap_obstack_initialize (&b); + cgraph_node *node = cgraph_node::get (cfun->decl); + while (!worklist.is_empty ()) { if (!loop_entered) @@ -1674,7 +1738,8 @@ tail_merge_optimize (unsigned int todo) if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "worklist iteration #%d\n", iteration_nr); - find_clusters (); + sem_function f (node, 0, &b); + find_clusters (f); gcc_assert (worklist.is_empty ()); if (all_clusters.is_empty ()) break; -- 2.4.5