[PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.
mliska
mliska@suse.cz
Thu Jul 9 14:10:00 GMT 2015
gcc/ChangeLog:
2015-07-09 Martin Liska <mliska@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
More information about the Gcc-patches
mailing list