On 07/16/2015 01:03 PM, Martin Liška wrote:
> 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 <mli...@suse.cz>
>>>
>>> * dbgcnt.def: Add new debug counter.
>>> * ipa-icf-gimple.c (func_checker::compare_ssa_name): Add flag
>>> for strict mode.
>>> (func_checker::compare_memory_operand): Likewise.
>>> (func_checker::compare_cst_or_decl): Handle if we are in
>>> tail_merge_mode.
>>> (func_checker::compare_operand): Pass strict flag properly.
>>> (func_checker::stmt_local_def): New function.
>>> (func_checker::compare_phi_node): Move from sem_function class.
>>> (func_checker::compare_bb_tail_merge): New function.
>>> (func_checker::compare_bb): Improve STMT iteration.
>>> (func_checker::compare_gimple_call): Pass strict flag.
>>> (func_checker::compare_gimple_assign): Likewise.
>>> (func_checker::compare_gimple_label): Remove unused flag.
>>> (ssa_names_set): New class.
>>> (ssa_names_set::build): New function.
>>> * ipa-icf-gimple.h (func_checker::gsi_next_nonlocal): New
>>> function.
>>> (ssa_names_set::contains): New function.
>>> (ssa_names_set::add): Likewise.
>>> * ipa-icf.c (sem_function::equals_private): Use transformed
>>> function.
>>> (sem_function::compare_phi_node): Move to func_checker class.
>>> * ipa-icf.h: Add new declarations.
>>> * tree-ssa-tail-merge.c (check_edges_correspondence): New
>>> function.
>>> (find_duplicate): Add usage of IPA ICF gimple infrastructure.
>>> (find_clusters_1): Pass new sem_function argument.
>>> (find_clusters): Likewise.
>>> (tail_merge_optimize): Call IPA ICF comparison machinery.
>> 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
>
>
Hello.
This is v3 of the patch sent last week. I've noticed couple of regressions that
are fixed in the patch,
updated numbers are as follows:
INKSCAPE:
after_v3: 15618104 B (8192B smaller than original)
FIREFOX:
after_v3: 130368208 B (22144B smaller than original)
Thanks for review,
Martin
>From 96a8f624f47b57dfba5a8c52700034809cc031dc 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): 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.
(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 | 313 ++++++++++++++++++++++++++++++++++-----
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 | 363 +++++++++++++++++++---------------------------
9 files changed, 530 insertions(+), 356 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..c5d7cf4 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;
@@ -424,7 +448,7 @@ func_checker::compare_operand (tree t1, tree t2)
for (unsigned i = 0; i < length1; i++)
if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
- CONSTRUCTOR_ELT (t2, i)->value))
+ CONSTRUCTOR_ELT (t2, i)->value), strict)
return return_false();
return true;
@@ -444,9 +468,9 @@ func_checker::compare_operand (tree t1, tree t2)
array_ref_element_size (t2)))
return return_false_with_msg ("");
- if (!compare_operand (x1, x2))
+ if (!compare_operand (x1, x2, strict))
return return_false_with_msg ("");
- return compare_operand (y1, y2);
+ return compare_operand (y1, y2, strict);
case MEM_REF:
{
x1 = TREE_OPERAND (t1, 0);
@@ -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. */
@@ -478,7 +502,7 @@ func_checker::compare_operand (tree t1, tree t2)
y1 = TREE_OPERAND (t1, 1);
y2 = TREE_OPERAND (t2, 1);
- ret = compare_operand (x1, x2)
+ ret = compare_operand (x1, x2, strict)
&& compare_cst_or_decl (y1, y2);
return return_with_debug (ret);
@@ -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))
@@ -498,7 +523,7 @@ func_checker::compare_operand (tree t1, tree t2)
obj_type_ref_class (t2)))
return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
- OBJ_TYPE_REF_OBJECT (t2)))
+ OBJ_TYPE_REF_OBJECT (t2), strict))
return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
}
@@ -511,7 +536,7 @@ func_checker::compare_operand (tree t1, tree t2)
x1 = TREE_OPERAND (t1, 0);
x2 = TREE_OPERAND (t2, 0);
- ret = compare_operand (x1, x2);
+ ret = compare_operand (x1, x2, strict);
return return_with_debug (ret);
}
case BIT_FIELD_REF:
@@ -523,14 +548,14 @@ func_checker::compare_operand (tree t1, tree t2)
z1 = TREE_OPERAND (t1, 2);
z2 = TREE_OPERAND (t2, 2);
- ret = compare_operand (x1, x2)
+ ret = compare_operand (x1, x2, strict)
&& compare_cst_or_decl (y1, y2)
&& compare_cst_or_decl (z1, z2);
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)
+ {
+ 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,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..d564818 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,91 @@ 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. */
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, false))
+ 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 +1171,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 +1185,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 +1204,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 +1271,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 +1310,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 +1323,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 +1336,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 +1518,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 +1542,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 +1561,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 +1613,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.5
