On 08/03/2015 07:38 PM, Jeff Law wrote:
> On 07/16/2015 05:03 AM, Martin Liška wrote:
>>> So a general question. We're passing in STRICT to several routines, which
>>> is fine. But then we're also checking M_TAIL_MERGE_MODE. What's the
>>> difference between the two? Can they be unified?
>>
>> Hello.
>>
>> I would say that STRICT is a bit generic mechanism that was introduced some
>> time before. It's e.g. used for checking of THIS arguments for methods and
>> make checking
>> more sensitive in situations that are somehow special.
>>
>> The newly added state is orthogonal to the previous one.
> Fair enough. There's some cases where we've documented STRICT, and others
> where we haven't.
>
> If STRICT flag is true, version must match strictly
> Appears as documentation for STRICT. It seems like it'd be better to
> describe what "strictly" means here.
>
> Elsewhere we have comments like:
>
> Be strict in case of tail-merge optimization
>
> Which tends to confuse things a bit. Perhaps something more like:
>
> In the case of tail merge optimization, XYZ must match
>
> It seems like a nit, but to someone else reading the code I don't think the
> distinctions are all that clear right now, so if we can improve things, it'd
> be good.
Hello Jeff.
I decided to come up a bit different approach (I hope it's much saner). Instead
of passing a new argument (called strict),
I have rewritten func_checker class to work with a new inner state
(m_comparing_sensitive_rhs), which is turned on in cases
where we compare a RHS operand. Usage of the flag is placed to the
corresponding part of func_checker.
>
>
>>
>>>
>>> I didn't find this comment particularly useful in understanding what this
>>> function does. AFAICT the function looks as the uses of the LHS of STMT
>>> and verifies they're all in the same block as STMT, right?
>>>
>>> It also verifies that the none of the operands within STMT are part of
>>> SSA_NAMES_SET.
>>>
>>> What role do those properties play in the meaning of "local definition"?
>>
>> I tried to explain it more deeply what's the purpose of this function.
> Thanks. It's much clearer now. We've actually got similar code in a couple
> places (ifcvt). I wonder if we could unify those implementations as a
> follow-up cleanup.
Good point, I'm going to write it to my TODO list.
>
>
>>
>>>
>>>
>>>
>>>
>>>> @@ -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)
>>> Needs a function comment. What are the "important" names we're collecting
>>> here?
>>>
>>> Is a single forward and backward pass really sufficient to find all the
>>> important names?
>>>
>>> In the backward pass, do you have to consider things like ASMs? I guess
>>> it's difficult to understand what you need to look at because it's not
>>> entirely clear the set of SSA_NAMEs you're building.
> These questions and lack of function comment don't seem to have been
> addressed yet.
Fixed.
>
>
>
>> > +
>> > +using namespace ipa_icf;
>> > +using namespace ipa_icf_gimple;
>>> Is this wise? Does it significantly help with conciseness within the tail
>>> merging pass where it wants things ipa-icf and ipa-icf-gimple?
>>>
>>> I'm not objecting at this point, I want to hear your thoughts.
>>
>> I must agree with you, as I've started using both namespaces in tree-tail
>> merge pass,
>> it makes not much sense anymore. I suggest to come up with a namespace that
>> will
>> encapsulate 'identical code folding'-related stuff. What about:
>>
>> namespace icf
> Sure if it helps and is clean. GCC does not have a policy against "using
> namespace", but other codebases do (google for example) as it does introduce
> some long term maintenance issues.
>
> So when I see a "using namespace" of that nature, I'm naturally going to
> question if it really helps in a significant way. If it does, then I won't
> object. If it's not helping in a significant way, then I'm likely to object.
>
> I think the updated version is fine WRT namespaces.
Sound good!
>
>
>>
>> ?
>>
>>>
>>>
>>>>
>>>> /* 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)
>>> Needs a function comment.
> Still needs function comment.
>
>
> I think we're pretty close here. Most of the issues are comments -- I still
> haven't looked *real* close at ssa_names_set::build. With a function comment
> I ought to be able to look at it more closely in the next (and hopefully
> final) iteration.
Comment in this part was enhanced.
The patch can boostrap on x86_64-linux-gnu, ppcl64-linux-gnu and survives
regression tests on x86_64-linux-gnu.
Thanks,
Martin
>
>
> Jeff
>From f72d05044f9d8a77b0d2c3df68eba4f88824d08b Mon Sep 17 00:00:00 2001
From: mliska <mli...@suse.cz>
Date: Thu, 9 Jul 2015 15:56:34 +0200
Subject: [PATCH 1/2] tree-ssa-tail-merge: replace engine with IPA ICF
infrastructure.
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): Use newly added
state flag.
(func_checker::compare_memory_operand): Likewise.
(func_checker::compare_cst_or_decl): Handle if we are in
tail_merge_mode.
(func_checker::reset_preferences): New function.
(func_checker::set_comparing_sensitive_rhs): Likewise.
(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): Return false in case of
an UBSAN function.
(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.
(make_pass_ipa_icf): Change namespace.
* ipa-icf.h: Add new declarations and rename namespace.
* 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.
(gvn_uses_equal): Remove.
(gimple_equal_p): Likewise.
(gsi_advance_bw_nondebug_nonlocal): Likewise.
(find_duplicate): Remove unused argument.
(make_pass_tail_merge): New function.
(pass_tail_merge::execute): Likewise.
(equal_ssa_uses): New function.
(same_succ_hash): Skip hashing of call arguments.
(same_succ_hash): Handle NULL value which can occur.
(gimple_operand_equal_value_p): Remove.
(same_phi_alternatives): Use newly added function equal_ssa_uses.
(same_phi_alternatives_1): Pass a new argument.
* passes.def: Add new pass.
* tree-pass.h: Likewise.
* tree-ssa-pre.c (pass_pre::execute): Remove connection to tail-merge
pass.
---
gcc/dbgcnt.def | 1 +
gcc/ipa-icf-gimple.c | 314 ++++++++++++++++++++++++++++++++++++---
gcc/ipa-icf-gimple.h | 101 +++++++++++--
gcc/ipa-icf.c | 75 +---------
gcc/ipa-icf.h | 24 +--
gcc/passes.def | 1 +
gcc/tree-pass.h | 2 +-
gcc/tree-ssa-pre.c | 9 --
gcc/tree-ssa-tail-merge.c | 366 +++++++++++++++++++---------------------------
9 files changed, 556 insertions(+), 337 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..6413984 100644
--- a/gcc/ipa-icf-gimple.c
+++ b/gcc/ipa-icf-gimple.c
@@ -54,11 +54,12 @@ 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"
-namespace ipa_icf_gimple {
+namespace icf {
/* Initialize internal structures for a given SOURCE_FUNC_DECL and
TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
@@ -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,7 +103,8 @@ 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
+ identical code perspective. */
bool
func_checker::compare_ssa_name (tree t1, tree t2)
@@ -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 (m_comparing_sensitive_rhs && 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)
@@ -237,7 +243,10 @@ func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
return true;
}
-/* Return true if types are compatible from perspective of ICF. */
+/* Return true if types are compatible from identical code perspective.
+ FIRST_ARGUMENT indicates if the comparison is called for
+ first parameter of a function. */
+
bool
func_checker::compatible_types_p (tree t1, tree t2)
{
@@ -256,7 +265,8 @@ 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)
@@ -351,11 +361,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 +388,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 +401,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);
}
@@ -604,6 +628,21 @@ func_checker::compare_variable_decl (tree t1, tree t2)
return return_with_debug (ret);
}
+/* Reset checker preferences. */
+
+void
+func_checker::reset_preferences ()
+{
+ m_comparing_sensitive_rhs = false;
+}
+
+/* Set flag that we compare sensitive RHS of a gimple statement. */
+
+void
+func_checker::set_comparing_sensitive_rhs ()
+{
+ m_comparing_sensitive_rhs = true;
+}
/* Function visits all gimple labels and creates corresponding
mapping between basic blocks and labels. */
@@ -626,6 +665,138 @@ func_checker::parse_labels (sem_bb *bb)
}
}
+/* Return true if gimple STMT is just a local definition in a
+ basic block. Local definition in this context means that a product
+ of the statement (transitively) does not escape the 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)
+ {
+ gimple use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ bb = gimple_bb (use_stmt);
+ if (bb == def_bb)
+ continue;
+
+ if (gimple_code (use_stmt) != GIMPLE_PHI)
+ 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,25 +813,47 @@ 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))
return return_false_with_msg ("gimple codes are different");
+ /* Reset inner state of the checker. */
+ reset_preferences ();
+
switch (gimple_code (s1))
{
case GIMPLE_CALL:
@@ -723,7 +916,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;
@@ -776,6 +969,8 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
return return_false_with_msg ("static call chains are different");
/* Checking of argument. */
+ set_comparing_sensitive_rhs ();
+
for (i = 0; i < gimple_call_num_args (s1); ++i)
{
t1 = gimple_call_arg (s1, i);
@@ -785,10 +980,29 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
return return_false_with_msg ("memory operands are different");
}
+ /* Reset preferences after we compare all arguments. */
+ reset_preferences ();
+
/* Return value checking. */
t1 = gimple_get_lhs (s1);
t2 = gimple_get_lhs (s2);
+ /* In case of tail merge mode, ignore all UBSAN_* internal functions. */
+ if (gimple_call_internal_p (s1))
+ switch (gimple_call_internal_fn (s1))
+ {
+ case IFN_UBSAN_NULL:
+ case IFN_UBSAN_BOUNDS:
+ case IFN_UBSAN_VPTR:
+ case IFN_UBSAN_CHECK_ADD:
+ case IFN_UBSAN_CHECK_SUB:
+ case IFN_UBSAN_CHECK_MUL:
+ case IFN_UBSAN_OBJECT_SIZE:
+ return false;
+ default:
+ break;
+ }
+
return compare_memory_operand (t1, t2);
}
@@ -820,6 +1034,10 @@ func_checker::compare_gimple_assign (gimple s1, gimple s2)
arg1 = gimple_op (s1, i);
arg2 = gimple_op (s2, i);
+ /* Set indication that we're going to compare RHS of a gimple assign. */
+ if (i != 0)
+ set_comparing_sensitive_rhs ();
+
if (!compare_memory_operand (arg1, arg2))
return return_false_with_msg ("memory operands are different");
}
@@ -869,9 +1087,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 +1252,67 @@ func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
return true;
}
-} // ipa_icf_gimple namespace
+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);
+
+ /* In the first phase, we iterate all non-local statements and
+ we extract all SSA names that are used in these statements. */
+ 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);
+ }
+
+ gsi = gsi_last_nondebug_bb (bb);
+
+ /* In the second phase, we process reverse run through all statements
+ and we add all SSA names whose values is based on a SSA name already
+ belonging to set. The set was created in previous step and
+ is incrementally expanded. At the end of this phase, we will have
+ all SSA names that not used just locally. */
+ 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:
+ case GIMPLE_ASM:
+ {
+ FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+ add (var);
+
+ break;
+ }
+ default:
+ break;
+ }
+
+ gsi_prev_nondebug (&gsi);
+ }
+}
+
+} // icf namespace
diff --git a/gcc/ipa-icf-gimple.h b/gcc/ipa-icf-gimple.h
index 6a9cbed..3e8db52 100644
--- a/gcc/ipa-icf-gimple.h
+++ b/gcc/ipa-icf-gimple.h
@@ -106,13 +106,14 @@ return_different_stmts_1 (gimple s1, gimple s2, const char *code,
#define return_different_stmts(s1, s2, code) \
return_different_stmts_1 (s1, s2, code, __func__, __LINE__)
-namespace ipa_icf_gimple {
+namespace icf {
/* Basic block struct for semantic equality pass. */
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,11 +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. */
+ /* Verifies that trees T1 and T2 are equivalent from
+ identical code perspective. */
bool compare_ssa_name (tree t1, tree t2);
/* Verification function for edges E1 and E2. */
@@ -219,24 +232,35 @@ public:
two trees are semantically equivalent. */
bool compare_tree_list_operand (tree t1, tree t2);
- /* Verifies that trees T1 and T2, representing function declarations
- are equivalent from perspective of ICF. */
- bool compare_function_decl (tree t1, tree t2);
-
/* Verifies that trees T1 and T2 do correspond. */
bool compare_variable_decl (tree t1, tree t2);
+ /* Reset checker preferences. */
+ void reset_preferences ();
+
+ /* Set flag that we compare sensitive RHS of a gimple statement. */
+ void set_comparing_sensitive_rhs ();
+
/* Return true if types are compatible for polymorphic call analysis.
COMPARE_PTR indicates if polymorphic type comparsion should be
done for pointers, too. */
static bool compatible_polymorphic_types_p (tree t1, tree t2,
bool compare_ptr);
- /* Return true if types are compatible from perspective of ICF.
+ /* Return true if types are compatible from identical code perspective.
FIRST_ARGUMENT indicates if the comparison is called for
first parameter of a function. */
static bool compatible_types_p (tree t1, tree t2);
+ /* Return true if gimple STMT is just a local definition in a
+ basic block. Local definition in this context means that a product
+ of the statement (transitively) does not escape the 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 +295,61 @@ 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;
+
+ /* Flag which indicates that we compare a sensitve RHS operand. */
+ bool m_comparing_sensitive_rhs;
};
-} // ipa_icf_gimple namespace
+/* 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. In the first phase, we collect
+ all SSA names that are not used not just in the basic block. After that,
+ having this set of SSA names, we can efficiently mark all statements
+ in the basic block that must be compared for equality. The rest can be
+ just skipped. Very similar operation was processed
+ in original implementation of tree-ssa-tail merge pass. */
+ 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);
+}
+
+} // icf namespace
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 3597b3a1..ca4f1e9 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -97,9 +97,7 @@ along with GCC; see the file COPYING3. If not see
#include "stor-layout.h"
#include "dbgcnt.h"
-using namespace ipa_icf_gimple;
-
-namespace ipa_icf {
+namespace icf {
/* Initialization and computation of symtab node hash, there data
are propagated later on. */
@@ -995,7 +993,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 +1706,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
@@ -3553,10 +3488,10 @@ public:
}
}; // class pass_ipa_icf
-} // ipa_icf namespace
+} // icf namespace
ipa_opt_pass_d *
make_pass_ipa_icf (gcc::context *ctxt)
{
- return new ipa_icf::pass_ipa_icf (ctxt);
+ return new icf::pass_ipa_icf (ctxt);
}
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 6428f25..0cc9c98 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -19,7 +19,7 @@ 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/>. */
-namespace ipa_icf {
+namespace icf {
class sem_item;
/* Congruence class encompasses a collection of either functions or
@@ -350,19 +350,23 @@ public:
unsigned ssa_names_size;
/* Array of structures for all basic blocks. */
- vec <ipa_icf_gimple::sem_bb *> bb_sorted;
+ vec <sem_bb *> bb_sorted;
/* Return true if parameter I may be used. */
bool param_used_p (unsigned int i);
+ /* Set a new function checker. */
+ void set_checker (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);
+ hashval_t get_bb_hash (const sem_bb *basic_block);
/* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
corresponds to TARGET. */
@@ -379,7 +383,7 @@ private:
static bool icf_handled_component_p (tree t);
/* Function checker stores binding between functions. */
- ipa_icf_gimple::func_checker *m_checker;
+ func_checker *m_checker;
/* COMPARED_FUNC is a function that we compare to. */
sem_function *m_compared_func;
@@ -627,4 +631,4 @@ private:
bitmap_obstack m_bmstack;
}; // class sem_item_optimizer
-} // ipa_icf namespace
+} // icf namespace
diff --git a/gcc/passes.def b/gcc/passes.def
index 6b66f8f..c20357d 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -216,6 +216,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_laddress);
NEXT_PASS (pass_split_crit_edges);
NEXT_PASS (pass_pre);
+ NEXT_PASS (pass_tail_merge);
NEXT_PASS (pass_sink_code);
NEXT_PASS (pass_asan);
NEXT_PASS (pass_tsan);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 7b66a1c..9b8e4a9 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -395,7 +395,7 @@ extern gimple_opt_pass *make_pass_merge_phi (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_split_crit_edges (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_laddress (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_pre (gcc::context *ctxt);
-extern unsigned int tail_merge_optimize (unsigned int);
+extern gimple_opt_pass *make_pass_tail_merge (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_profile (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 041cb78..8f56881 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -4869,15 +4869,6 @@ pass_pre::execute (function *fun)
todo |= fini_eliminate ();
loop_optimizer_finalize ();
- /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
- case we can merge the block with the remaining predecessor of the block.
- It should either:
- - call merge_blocks after each tail merge iteration
- - call merge_blocks after all tail merge iterations
- - mark TODO_cleanup_cfg when necessary
- - share the cfg cleanup with fini_pre. */
- todo |= tail_merge_optimize (todo);
-
free_scc_vn ();
/* Tail merging invalidates the virtual SSA web, together with
diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 88a3032..8c9a1cb 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1,6 +1,7 @@
/* Tail merging for gimple.
Copyright (C) 2011-2015 Free Software Foundation, Inc.
Contributed by Tom de Vries (t...@codesourcery.com)
+ and Martin Liska (mli...@suse.cz)
This file is part of GCC.
@@ -124,35 +125,10 @@ along with GCC; see the file COPYING3. If not see
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.
-
+ Basic blocks are compared insn-by-insn by ICF infrastructure which was
+ originally used for IPA-ICF. Even though the pass is function base,
+ BB equality is subset of comparisons that are performed and can be reused
+ for this pass.
IMPLEMENTATION
@@ -198,6 +174,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"
@@ -209,11 +186,19 @@ along with GCC; see the file COPYING3. If not see
#include "tree-into-ssa.h"
#include "params.h"
#include "gimple-pretty-print.h"
-#include "tree-ssa-sccvn.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-pass.h"
#include "trans-mem.h"
+#include "ipa-ref.h"
+#include "lto-streamer.h"
+#include "cgraph.h"
+#include <list>
+#include "ipa-icf-gimple.h"
+#include "ipa-icf.h"
+#include "dbgcnt.h"
+
+using namespace icf;
/* 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.
@@ -360,24 +345,29 @@ gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
}
}
-/* 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. */
+/* Return true if either VAL1 and VAL2 are constant values and are equal,
+ or if both values are SSA names. In this case we conditionally return true
+ and ICF machinery will verify that these SSA names are really equivalent
+ in basic blocks we compare. */
static bool
-gvn_uses_equal (tree val1, tree val2)
+equal_ssa_uses (tree val1, tree val2,
+ auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
{
gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
if (val1 == val2)
return true;
- if (vn_valueize (val1) != vn_valueize (val2))
+ if (CONSTANT_CLASS_P (val1) && CONSTANT_CLASS_P (val2))
+ return operand_equal_p (val1, val2, OEP_ONLY_CONST);
+ else if (TREE_CODE (val1) == SSA_NAME && TREE_CODE (val2) == SSA_NAME)
+ {
+ ssa_phi_pairs->safe_push (std::make_pair (val1, val2));
+ return true;
+ }
+ else
return false;
-
- return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
- && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
}
/* Prints E to FILE. */
@@ -454,7 +444,6 @@ same_succ_hash (const_same_succ e)
basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
int size = 0;
gimple stmt;
- tree arg;
unsigned int s;
bitmap_iterator bs;
@@ -480,12 +469,6 @@ same_succ_hash (const_same_succ e)
if (gimple_call_chain (stmt))
inchash::add_expr (gimple_call_chain (stmt), hstate);
}
- for (i = 0; i < gimple_call_num_args (stmt); i++)
- {
- arg = gimple_call_arg (stmt, i);
- arg = vn_valueize (arg);
- inchash::add_expr (arg, hstate);
- }
}
hstate.add_int (size);
@@ -818,6 +801,10 @@ static void
same_succ_flush_bb (basic_block bb)
{
same_succ same = BB_SAME_SUCC (bb);
+
+ if (same == NULL)
+ return;
+
BB_SAME_SUCC (bb) = NULL;
if (bitmap_single_bit_set_p (same->bbs))
same_succ_htab->remove_elt_with_hash (same, same->hashval);
@@ -1083,201 +1070,94 @@ set_cluster (basic_block bb1, basic_block bb2)
gcc_unreachable ();
}
-/* Return true if gimple operands T1 and T2 have the same value. */
-
-static bool
-gimple_operand_equal_value_p (tree t1, tree t2)
-{
- if (t1 == t2)
- return true;
-
- if (t1 == NULL_TREE
- || t2 == NULL_TREE)
- return false;
-
- if (operand_equal_p (t1, t2, 0))
- return true;
-
- return gvn_uses_equal (t1, t2);
-}
-
-/* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
- gimple_bb (s2) are members of SAME_SUCC. */
+/* Make sure that all edges coming from basic block BB1 and BB2 have
+ the same destination index, and make sure that true/false edge values
+ are equal. */
static bool
-gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
+check_edges_correspondence (basic_block bb1, basic_block bb2)
{
- unsigned int i;
- tree lhs1, lhs2;
- basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
- tree t1, t2;
- bool inv_cond;
- enum tree_code code1, code2;
-
- if (gimple_code (s1) != gimple_code (s2))
- return false;
+ edge e1, e2;
+ edge_iterator ei2 = ei_start (bb2->succs);
- switch (gimple_code (s1))
+ for (edge_iterator ei1 = ei_start (bb1->succs); ei_cond (ei1, &e1);
+ ei_next (&ei1))
{
- case GIMPLE_CALL:
- if (!gimple_call_same_target_p (s1, s2))
- return false;
-
- t1 = gimple_call_chain (s1);
- t2 = gimple_call_chain (s2);
- if (!gimple_operand_equal_value_p (t1, t2))
- return false;
-
- if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
- return false;
-
- for (i = 0; i < gimple_call_num_args (s1); ++i)
- {
- t1 = gimple_call_arg (s1, i);
- t2 = gimple_call_arg (s2, i);
- if (!gimple_operand_equal_value_p (t1, t2))
- return false;
- }
-
- lhs1 = gimple_get_lhs (s1);
- lhs2 = gimple_get_lhs (s2);
- if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
- return true;
- if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
- return false;
- if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
- return vn_valueize (lhs1) == vn_valueize (lhs2);
- return operand_equal_p (lhs1, lhs2, 0);
-
- case GIMPLE_ASSIGN:
- lhs1 = gimple_get_lhs (s1);
- lhs2 = gimple_get_lhs (s2);
- if (TREE_CODE (lhs1) != SSA_NAME
- && TREE_CODE (lhs2) != SSA_NAME)
- return (operand_equal_p (lhs1, lhs2, 0)
- && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
- gimple_assign_rhs1 (s2)));
- else if (TREE_CODE (lhs1) == SSA_NAME
- && TREE_CODE (lhs2) == SSA_NAME)
- return operand_equal_p (gimple_assign_rhs1 (s1),
- gimple_assign_rhs1 (s2), 0);
- return false;
-
- case GIMPLE_COND:
- t1 = gimple_cond_lhs (s1);
- t2 = gimple_cond_lhs (s2);
- if (!gimple_operand_equal_value_p (t1, t2))
- return false;
+ ei_cond (ei2, &e2);
- t1 = gimple_cond_rhs (s1);
- t2 = gimple_cond_rhs (s2);
- if (!gimple_operand_equal_value_p (t1, t2))
+ 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;
- code1 = gimple_expr_code (s1);
- code2 = gimple_expr_code (s2);
- inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
- != bitmap_bit_p (same_succ->inverse, bb2->index));
- if (inv_cond)
- {
- bool honor_nans = HONOR_NANS (t1);
- code2 = invert_tree_comparison (code2, honor_nans);
- }
- return code1 == code2;
-
- default:
- return false;
+ ei_next (&ei2);
}
-}
-
-/* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
- Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
- processed statements. */
-
-static void
-gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
- bool *vuse_escaped)
-{
- gimple stmt;
- tree lvuse;
-
- while (true)
- {
- if (gsi_end_p (*gsi))
- return;
- stmt = gsi_stmt (*gsi);
- lvuse = gimple_vuse (stmt);
- if (lvuse != NULL_TREE)
- {
- *vuse = lvuse;
- if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
- *vuse_escaped = true;
- }
-
- if (!stmt_local_def (stmt))
- return;
- gsi_prev_nondebug (gsi);
- }
+ 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 (basic_block bb1, basic_block bb2, sem_function &f,
+ auto_vec<std::pair<tree, tree> > &ssa_phi_pairs)
{
- 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);
+ if (!icf_result || !check_edges_correspondence (bb1, bb2))
+ return;
- while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
+ for (unsigned i = 0; i < ssa_phi_pairs.length (); i++)
{
- gimple stmt1 = gsi_stmt (gsi1);
- gimple stmt2 = gsi_stmt (gsi2);
-
- /* What could be better than this here is to blacklist the bb
- containing the stmt, when encountering the stmt f.i. in
- same_succ_hash. */
- if (is_tm_ending (stmt1)
- || is_tm_ending (stmt2))
- return;
+ std::pair<tree, tree> v = ssa_phi_pairs[i];
- if (!gimple_equal_p (same_succ, stmt1, stmt2))
- return;
+ /* If one of definitions does not belong the function we consider
+ for equation, SSA names must be a same pointer. */
+ gimple def1 = SSA_NAME_DEF_STMT (v.first);
+ gimple def2 = SSA_NAME_DEF_STMT (v.second);
- gsi_prev_nondebug (&gsi1);
- gsi_prev_nondebug (&gsi2);
- gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
- gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
- }
+ basic_block bbdef1 = gimple_bb (def1);
+ basic_block bbdef2 = gimple_bb (def2);
- if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
- return;
+ if (bb1 != bbdef1 || bb2 != bbdef2)
+ if (v.first != v.second)
+ return;
- /* If the incoming vuses are not the same, and the vuse escaped into an
- SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
- which potentially means the semantics of one of the blocks will be changed.
- TODO: make this check more precise. */
- if (vuse_escaped && vuse1 != vuse2)
- return;
+ if (!checker->compare_ssa_name (v.first, v.second))
+ return;
+ }
if (dump_file)
+ {
fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
bb1->index, bb2->index);
- set_cluster (bb1, bb2);
+ }
+
+ if (dbg_cnt (tail_merge))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ dump_bb (dump_file, bb1, 0, TDF_DETAILS);
+ dump_bb (dump_file, bb2, 0, TDF_DETAILS);
+ }
+
+ set_cluster (bb1, bb2);
+ }
}
/* Returns whether for all phis in DEST the phi alternatives for E1 and
E2 are equal. */
static bool
-same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
+same_phi_alternatives_1 (basic_block dest, edge e1, edge e2,
+ auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
{
int n1 = e1->dest_idx, n2 = e2->dest_idx;
gphi_iterator gsi;
@@ -1294,7 +1174,8 @@ same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
if (operand_equal_for_phi_arg_p (val1, val2))
continue;
- if (gvn_uses_equal (val1, val2))
+
+ if (equal_ssa_uses (val1, val2, ssa_phi_pairs))
continue;
return false;
@@ -1307,7 +1188,8 @@ same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
phi alternatives for BB1 and BB2 are equal. */
static bool
-same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
+same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2,
+ auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
{
unsigned int s;
bitmap_iterator bs;
@@ -1325,7 +1207,7 @@ same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
/* For all phis in bb, the phi alternatives for e1 and e2 need to have
the same value. */
- if (!same_phi_alternatives_1 (succ, e1, e2))
+ if (!same_phi_alternatives_1 (succ, e1, e2, ssa_phi_pairs))
return false;
}
@@ -1392,7 +1274,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;
@@ -1431,10 +1313,12 @@ find_clusters_1 (same_succ same_succ)
if (!deps_ok_for_redirect (bb1, bb2))
continue;
- if (!(same_phi_alternatives (same_succ, bb1, bb2)))
+ auto_vec<std::pair<tree, tree> > ssa_phi_pairs;
+
+ if (!(same_phi_alternatives (same_succ, bb1, bb2, &ssa_phi_pairs)))
continue;
- find_duplicate (same_succ, bb1, bb2);
+ find_duplicate (bb1, bb2, f, ssa_phi_pairs);
}
}
}
@@ -1442,7 +1326,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;
@@ -1455,7 +1339,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);
}
}
@@ -1637,9 +1521,10 @@ update_debug_stmts (void)
/* Runs tail merge optimization. */
-unsigned int
-tail_merge_optimize (unsigned int todo)
+static unsigned int
+tail_merge_optimize ()
{
+ unsigned todo = 0;
int nr_bbs_removed_total = 0;
int nr_bbs_removed;
bool loop_entered = false;
@@ -1660,6 +1545,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)
@@ -1675,7 +1564,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;
@@ -1726,3 +1616,45 @@ tail_merge_optimize (unsigned int todo)
return todo;
}
+
+namespace {
+
+const pass_data pass_data_tail_merge =
+{
+ GIMPLE_PASS, /* type */
+ "tail-merge", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_TAIL_MERGE, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa_only_virtuals, /* todo_flags_finish */
+};
+
+class pass_tail_merge : public gimple_opt_pass
+{
+public:
+ pass_tail_merge (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_tail_merge, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_tail_merge != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_tail_merge
+
+} // anon namespace
+
+unsigned int
+pass_tail_merge::execute (function *)
+{
+ return tail_merge_optimize ();
+}
+
+gimple_opt_pass *
+make_pass_tail_merge (gcc::context *ctxt)
+{
+ return new pass_tail_merge (ctxt);
+}
--
2.4.6
