This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.
- From: Martin Liška <mliska at suse dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 16 Jul 2015 13:03:41 +0200
- Subject: Re: [PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.
- Authentication-results: sourceware.org; auth=none
- References: <cover dot 1436450591 dot git dot mliska at suse dot cz> <e5926353149121a294214d67494d6fe437eb3348 dot 1436450591 dot git dot mliska at suse dot cz> <559EA033 dot 60601 at redhat dot com>
On 07/09/2015 06:24 PM, Jeff Law wrote:
> On 07/09/2015 07:56 AM, mliska wrote:
>> 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.
> 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.
>
>
>>
>> -/* 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)
> This (and other) functions would seem to be used more than just ICF at this point. A pass over the comments to update them as appropriate would be appreciated.
>
>> @@ -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. */
> s/difinition/definition/
Thanks.
>
> 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.
>
>
>
>
>> @@ -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.
>
>
>
>> @@ -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);
> Presumably in the case of tail merging, FUNC1 and FUNC will be the same :-)
Yes, the function is not called from tail-merge pass.
>
>
>> /* 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);
> Is the default value for the parameter really needed in these methods? Why not go ahead and update the callers, I don't think we have that many right now.
I've just grepped errors and it's more than 20 occurrences, so I hope it clarifies
the usage of implicit value of the function.
>
>>
>> /* 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);
> s/difinition/definition/
> As with the implementation, I think the comment needs some clarification.
>
>> +/* SSA NAMES set. */
>> +class ssa_names_set
> So what names are in this set? Ie, what is the ::build method searching for?
>
>
>> 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"
> I think Andrew has defined an ordering for the initial include files. I think you've #included <list> in the wrong place. Can it be moved down?
Sure.
>
>> +
>> +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
?
>
>
>>
>> /* 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.
>
>
>> +{
>> + 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;
> Formatting looks wrong in that conditional.
>
>> @@ -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);
> So I realize this goes away in the #2 patch. But I'm curious how often it triggered and if there were any interesting patterns when the old tail merging triggered by the version utilizing ICF didn't or vice-versa.
>
> You mentioned posting some before/after results, but I haven't seen them yet.
>
> I'd like to do another pass over these changes, so if you could repost after the cleanups noted above, it'd be appreciated.
>
> Jeff
>
>
I decided to come up with a single patch, mainly because Richi pointed out that we should create a new tree pass and
it makes sense to do it in a single commit. In last patch of the previous series, I modified some UBSAN tests, but proper
fix would be to ignore merging of UBSAN_* calls (as suggested in corresponding emails).
Following patch can survive bootstrap on x86_64-linux-pc and ppc64le-linux-pc and regression tests.
There are sizes of binaries before and after the patch:
INKSCAPE:
before: 15626296 B
after: 15622200 B
Firefox:
before: 130390352 B
after: 130379744 B
diff: 10608 B
Thanks,
Martin
>From a7e09b5d534ba66391f6244ae7cc6e715010f8a3 Mon Sep 17 00:00:00 2001
From: mliska <mliska@suse.cz>
Date: Thu, 9 Jul 2015 15:56:34 +0200
Subject: [PATCH] tree-ssa-tail-merge: replace engine with IPA ICF
infrastructure.
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.
(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.
* 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 | 299 ++++++++++++++++++++++++++++++++++++++----
gcc/ipa-icf-gimple.h | 98 +++++++++++---
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 | 325 ++++++++++++++--------------------------------
9 files changed, 472 insertions(+), 362 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..3b678f3 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,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
+ identical code perspective. */
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)
@@ -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,10 +265,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 +337,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 +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);
}
@@ -393,7 +417,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 +489,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 +510,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 +555,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 +651,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)
+ {
+ 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 +799,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 +899,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 +965,23 @@ 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);
+ /* 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, false);
}
@@ -820,7 +1012,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 +1061,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 +1226,60 @@ 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);
+
+ 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);
+ }
+}
+
+} // icf namespace
diff --git a/gcc/ipa-icf-gimple.h b/gcc/ipa-icf-gimple.h
index 6a9cbed..406641f 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,12 +153,21 @@ 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);
+ /* Verifies that trees T1 and T2 are equivalent from
+ identical code perspective. */
+ 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 +217,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,16 +226,12 @@ 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. */
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);
@@ -232,11 +241,20 @@ public:
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 +289,58 @@ 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. 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;
};
-} // ipa_icf_gimple namespace
+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 13a9320..08fdb00 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -98,9 +98,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. */
@@ -996,7 +994,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;
@@ -1708,70 +1707,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
@@ -3554,10 +3489,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 5cd07ae..f7ff7e3 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 c47b22e..3cb6bee 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 5210eed..473c73d 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..c98e7b8 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 (tom@codesourcery.com)
+ and Martin Liska (mliska@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,26 +345,6 @@ 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. */
-
-static bool
-gvn_uses_equal (tree val1, tree val2)
-{
- gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
-
- if (val1 == val2)
- return true;
-
- if (vn_valueize (val1) != vn_valueize (val2))
- 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. */
static void
@@ -454,7 +419,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 +444,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 +776,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,194 +1045,51 @@ 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)
+check_edges_correspondence (basic_block bb1, basic_block bb2)
{
- 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. */
-
-static bool
-gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
-{
- 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;
+ ei_cond (ei2, &e2);
- t1 = gimple_call_chain (s1);
- t2 = gimple_call_chain (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;
- 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;
-
- t1 = gimple_cond_rhs (s1);
- t2 = gimple_cond_rhs (s2);
- if (!gimple_operand_equal_value_p (t1, t2))
- 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)
{
- 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);
- gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
- gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
-
- while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
- {
- 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;
+ 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);
- if (!gimple_equal_p (same_succ, stmt1, stmt2))
- return;
-
- 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);
- }
-
- if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
- 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)
+ if (!icf_result || !check_edges_correspondence (bb1, bb2))
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))
+ set_cluster (bb1, bb2);
}
/* Returns whether for all phis in DEST the phi alternatives for E1 and
@@ -1294,8 +1113,6 @@ 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))
- continue;
return false;
}
@@ -1392,7 +1209,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;
@@ -1434,7 +1251,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 (bb1, bb2, f);
}
}
}
@@ -1442,7 +1259,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 +1272,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 +1454,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 +1478,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 +1497,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 +1549,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_pre != 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.5