Re: [PATCH 1/3] tree-ssa-tail-merge: add IPA ICF infrastructure.

[Martin LiÅka <mliska at suse dot cz>]

On 08/03/2015 07:38 PM, Jeff Law wrote:
> On 07/16/2015 05:03 AM, Martin Liška wrote:
>>> So a general question.  We're passing in STRICT to several routines, which is fine.  But then we're also checking M_TAIL_MERGE_MODE.  What's the difference between the two?  Can they be unified?
>>
>> Hello.
>>
>> I would say that STRICT is a bit generic mechanism that was introduced some time before. It's e.g. used for checking of THIS arguments for methods and make checking
>> more sensitive in situations that are somehow special.
>>
>> The newly added state is orthogonal to the previous one.
> Fair enough.  There's some cases where we've documented STRICT, and others where we haven't.
> 
>   If STRICT flag is true, version must match strictly
> Appears as documentation for STRICT.  It seems like it'd be better to describe what "strictly" means here.
> 
> Elsewhere we have comments like:
> 
>   Be strict in case of tail-merge optimization
> 
> Which tends to confuse things a bit.  Perhaps something more like:
> 
>   In the case of tail merge optimization, XYZ must match
> 
> It seems like a nit, but to someone else reading the code I don't think the distinctions are all that clear right now, so if we can improve things, it'd be good.

Hello Jeff.

I decided to come up a bit different approach (I hope it's much saner). Instead of passing a new argument (called strict),
I have rewritten func_checker class to work with a new inner state (m_comparing_sensitive_rhs), which is turned on in cases
where we compare a RHS operand. Usage of the flag is placed to the corresponding part of func_checker.

> 
> 
>>
>>>
>>> I didn't find this comment particularly useful in understanding what this function does.  AFAICT the function looks as the uses of the LHS of STMT and verifies they're all in the same block as STMT, right?
>>>
>>> It also verifies that the none of the operands within STMT are part of SSA_NAMES_SET.
>>>
>>> What role do those properties play in the meaning of "local definition"?
>>
>> I tried to explain it more deeply what's the purpose of this function.
> Thanks.  It's much clearer now.   We've actually got similar code in a couple places (ifcvt).  I wonder if we could unify those implementations as a follow-up cleanup.

Good point, I'm going to write it to my TODO list.

> 
> 
>>
>>>
>>>
>>>
>>>
>>>> @@ -1037,4 +1205,60 @@ func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
>>>>      return true;
>>>>    }
>>>>
>>>> +void
>>>> +ssa_names_set::build (basic_block bb)
>>> Needs a function comment.  What are the "important" names we're collecting here?
>>>
>>> Is a single forward and backward pass really sufficient to find all the important names?
>>>
>>> In the backward pass, do you have to consider things like ASMs?  I guess it's difficult to understand what you need to look at because it's not entirely clear the set of SSA_NAMEs you're building.
> These questions and lack of function comment don't seem to have been addressed yet.

Fixed.

> 
> 
> 
>> > +
>> > +using namespace ipa_icf;
>> > +using namespace ipa_icf_gimple;
>>> Is this wise?  Does it significantly help with conciseness within the tail merging pass where it wants things ipa-icf and ipa-icf-gimple?
>>>
>>> I'm not objecting at this point, I want to hear your thoughts.
>>
>> I must agree with you, as I've started using both namespaces in tree-tail merge pass,
>> it makes not much sense anymore. I suggest to come up with a namespace that will
>> encapsulate 'identical code folding'-related stuff. What about:
>>
>> namespace icf
> Sure if it helps and is clean.  GCC does not have a policy against "using namespace", but other codebases do (google for example) as it does introduce some long term maintenance issues.
> 
> So when I see a "using namespace" of that nature, I'm naturally going to question if it really helps in a significant way.  If it does, then I won't object.  If it's not helping in a significant way, then I'm likely to object.
> 
> I think the updated version is fine WRT namespaces.

Sound good!

> 
> 
>>
>> ?
>>
>>>
>>>
>>>>
>>>>    /* Describes a group of bbs with the same successors.  The successor bbs are
>>>>       cached in succs, and the successor edge flags are cached in succ_flags.
>>>> @@ -1220,17 +1231,48 @@ gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
>>>>        }
>>>>    }
>>>>
>>>> +static bool
>>>> +check_edges_correspondence (basic_block bb1, basic_block bb2)
>>> Needs a function comment.
> Still needs function comment.
> 
> 
> I think we're pretty close here.  Most of the issues are comments -- I still haven't looked *real* close at ssa_names_set::build.  With a function comment I ought to be able to look at it more closely in the next (and hopefully final) iteration.

Comment in this part was enhanced.

The patch can boostrap on x86_64-linux-gnu, ppcl64-linux-gnu and survives regression tests on x86_64-linux-gnu.

Thanks,
Martin


> 
> 
> Jeff

>From f72d05044f9d8a77b0d2c3df68eba4f88824d08b Mon Sep 17 00:00:00 2001
From: mliska <mliska@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  <mliska@suse.cz>

	* dbgcnt.def: Add new debug counter.
	* ipa-icf-gimple.c (func_checker::compare_ssa_name): Use newly added
	state flag.
	(func_checker::compare_memory_operand): Likewise.
	(func_checker::compare_cst_or_decl): Handle if we are in
	tail_merge_mode.
	(func_checker::reset_preferences): New function.
	(func_checker::set_comparing_sensitive_rhs): Likewise.
	(func_checker::stmt_local_def): New function.
	(func_checker::compare_phi_node): Move from sem_function class.
	(func_checker::compare_bb_tail_merge): New function.
	(func_checker::compare_bb): Improve STMT iteration.
	(func_checker::compare_gimple_call): Return false in case of
	an UBSAN function.
	(func_checker::compare_gimple_assign): Likewise.
	(func_checker::compare_gimple_label): Remove unused flag.
	(ssa_names_set): New class.
	(ssa_names_set::build): New function.
	* ipa-icf-gimple.h (func_checker::gsi_next_nonlocal): New
	function.
	(ssa_names_set::contains): New function.
	(ssa_names_set::add): Likewise.
	* ipa-icf.c (sem_function::equals_private): Use transformed
	function.
	(sem_function::compare_phi_node): Move to func_checker class.
	(make_pass_ipa_icf): Change namespace.
	* ipa-icf.h: Add new declarations and rename namespace.
	* tree-ssa-tail-merge.c (check_edges_correspondence): New
	function.
	(find_duplicate): Add usage of IPA ICF gimple infrastructure.
	(find_clusters_1): Pass new sem_function argument.
	(find_clusters): Likewise.
	(tail_merge_optimize): Call IPA ICF comparison machinery.
	(gvn_uses_equal): Remove.
	(gimple_equal_p): Likewise.
	(gsi_advance_bw_nondebug_nonlocal): Likewise.
	(find_duplicate): Remove unused argument.
	(make_pass_tail_merge): New function.
	(pass_tail_merge::execute): Likewise.
	(equal_ssa_uses): New function.
	(same_succ_hash): Skip hashing of call arguments.
	(same_succ_hash): Handle NULL value which can occur.
	(gimple_operand_equal_value_p): Remove.
	(same_phi_alternatives): Use newly added function equal_ssa_uses.
	(same_phi_alternatives_1): Pass a new argument.
	* passes.def: Add new pass.
	* tree-pass.h: Likewise.
	* tree-ssa-pre.c (pass_pre::execute): Remove connection to tail-merge
	pass.
---
 gcc/dbgcnt.def            |   1 +
 gcc/ipa-icf-gimple.c      | 314 ++++++++++++++++++++++++++++++++++++---
 gcc/ipa-icf-gimple.h      | 101 +++++++++++--
 gcc/ipa-icf.c             |  75 +---------
 gcc/ipa-icf.h             |  24 +--
 gcc/passes.def            |   1 +
 gcc/tree-pass.h           |   2 +-
 gcc/tree-ssa-pre.c        |   9 --
 gcc/tree-ssa-tail-merge.c | 366 +++++++++++++++++++---------------------------
 9 files changed, 556 insertions(+), 337 deletions(-)

diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index 95f6b06..79d99d9 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -187,6 +187,7 @@ DEBUG_COUNTER (sms_sched_loop)
 DEBUG_COUNTER (split_for_sched2)
 DEBUG_COUNTER (store_motion)
 DEBUG_COUNTER (tail_call)
+DEBUG_COUNTER (tail_merge)
 DEBUG_COUNTER (treepre_insert)
 DEBUG_COUNTER (tree_sra)
 DEBUG_COUNTER (vect_loop)
diff --git a/gcc/ipa-icf-gimple.c b/gcc/ipa-icf-gimple.c
index e727693..6413984 100644
--- a/gcc/ipa-icf-gimple.c
+++ b/gcc/ipa-icf-gimple.c
@@ -54,11 +54,12 @@ along with GCC; see the file COPYING3.  If not see
 #include <list>
 #include "tree-eh.h"
 #include "builtins.h"
+#include "trans-mem.h"
 
 #include "ipa-icf-gimple.h"
 #include "ipa-icf.h"
 
-namespace ipa_icf_gimple {
+namespace icf {
 
 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
    TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
@@ -69,14 +70,14 @@ namespace ipa_icf_gimple {
 
 func_checker::func_checker (tree source_func_decl, tree target_func_decl,
 			    bool compare_polymorphic,
-			    bool ignore_labels,
+			    bool tail_merge_mode,
 			    hash_set<symtab_node *> *ignored_source_nodes,
 			    hash_set<symtab_node *> *ignored_target_nodes)
   : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
     m_ignored_source_nodes (ignored_source_nodes),
     m_ignored_target_nodes (ignored_target_nodes),
     m_compare_polymorphic (compare_polymorphic),
-    m_ignore_labels (ignore_labels)
+    m_tail_merge_mode (tail_merge_mode)
 {
   function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
   function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
@@ -102,7 +103,8 @@ func_checker::~func_checker ()
   m_target_ssa_names.release();
 }
 
-/* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
+/* Verifies that trees T1 and T2 are equivalent from
+   identical code perspective.  */
 
 bool
 func_checker::compare_ssa_name (tree t1, tree t2)
@@ -113,6 +115,10 @@ func_checker::compare_ssa_name (tree t1, tree t2)
   unsigned i1 = SSA_NAME_VERSION (t1);
   unsigned i2 = SSA_NAME_VERSION (t2);
 
+  if (m_comparing_sensitive_rhs && m_tail_merge_mode)
+    return t1 == t2 ||
+      (m_source_ssa_names[i1] != -1 && m_source_ssa_names[i1] == (int) i2);
+
   if (m_source_ssa_names[i1] == -1)
     m_source_ssa_names[i1] = i2;
   else if (m_source_ssa_names[i1] != (int) i2)
@@ -237,7 +243,10 @@ func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
   return true;
 }
 
-/* Return true if types are compatible from perspective of ICF.  */
+/* Return true if types are compatible from identical code perspective.
+   FIRST_ARGUMENT indicates if the comparison is called for
+   first parameter of a function.  */
+
 bool
 func_checker::compatible_types_p (tree t1, tree t2)
 {
@@ -256,7 +265,8 @@ func_checker::compatible_types_p (tree t1, tree t2)
   return true;
 }
 
-/* Function compare for equality given memory operands T1 and T2.  */
+/* Function compare for equality given memory operands T1 and T2.
+   If STRICT flag is true, versions must match strictly.  */
 
 bool
 func_checker::compare_memory_operand (tree t1, tree t2)
@@ -351,11 +361,18 @@ func_checker::compare_cst_or_decl (tree t1, tree t2)
 	return return_with_debug (ret);
       }
     case FUNCTION_DECL:
-      /* All function decls are in the symbol table and known to match
+      /* If we are called within an invocation of IPA ICF,
+	 all function decls are in the symbol table and known to match
 	 before we start comparing bodies.  */
-      return true;
+      return m_tail_merge_mode ? t1 == t2 : true;
     case VAR_DECL:
-      return return_with_debug (compare_variable_decl (t1, t2));
+      {
+	  /* Be strict in case of tail-merge optimization.  */
+	  if (m_tail_merge_mode)
+	    return t1 == t2;
+
+	  return return_with_debug (compare_variable_decl (t1, t2));
+	}
     case FIELD_DECL:
       {
 	tree offset1 = DECL_FIELD_OFFSET (t1);
@@ -371,6 +388,10 @@ func_checker::compare_cst_or_decl (tree t1, tree t2)
       }
     case LABEL_DECL:
       {
+	/* Be strict in case of tail-merge optimization.  */
+	if (m_tail_merge_mode)
+	  return t1 == t2;
+
 	int *bb1 = m_label_bb_map.get (t1);
 	int *bb2 = m_label_bb_map.get (t2);
 
@@ -380,6 +401,9 @@ func_checker::compare_cst_or_decl (tree t1, tree t2)
     case RESULT_DECL:
     case CONST_DECL:
       {
+	if (m_tail_merge_mode)
+	  return t1 == t2;
+
 	ret = compare_decl (t1, t2);
 	return return_with_debug (ret);
       }
@@ -604,6 +628,21 @@ func_checker::compare_variable_decl (tree t1, tree t2)
   return return_with_debug (ret);
 }
 
+/* Reset checker preferences.  */
+
+void
+func_checker::reset_preferences ()
+{
+  m_comparing_sensitive_rhs = false;
+}
+
+/* Set flag that we compare sensitive RHS of a gimple statement.  */
+
+void
+func_checker::set_comparing_sensitive_rhs ()
+{
+  m_comparing_sensitive_rhs = true;
+}
 
 /* Function visits all gimple labels and creates corresponding
    mapping between basic blocks and labels.  */
@@ -626,6 +665,138 @@ func_checker::parse_labels (sem_bb *bb)
     }
 }
 
+/* Return true if gimple STMT is just a local definition in a
+   basic block.  Local definition in this context means that a product
+   of the statement (transitively) does not escape the basic block.
+   Used SSA names are contained in SSA_NAMES_SET.  */
+
+bool
+func_checker::stmt_local_def (gimple stmt, ssa_names_set *ssa_names_set)
+{
+  basic_block bb, def_bb;
+  imm_use_iterator iter;
+  use_operand_p use_p;
+  tree val;
+  def_operand_p def_p;
+
+  if (gimple_vdef (stmt) != NULL_TREE
+      || gimple_has_side_effects (stmt)
+      || gimple_could_trap_p_1 (stmt, false, false)
+      || gimple_vuse (stmt) != NULL_TREE)
+    return false;
+
+  def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
+  if (def_p == NULL)
+    return false;
+
+  val = DEF_FROM_PTR (def_p);
+  if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
+    return false;
+
+  def_bb = gimple_bb (stmt);
+
+  FOR_EACH_IMM_USE_FAST (use_p, iter, val)
+    {
+      gimple use_stmt = USE_STMT (use_p);
+      if (is_gimple_debug (use_stmt))
+	continue;
+      bb = gimple_bb (use_stmt);
+      if (bb == def_bb)
+	continue;
+
+      if (gimple_code (use_stmt) != GIMPLE_PHI)
+	continue;
+
+      return false;
+    }
+
+  for (unsigned i = 0; i < gimple_num_ops (stmt); i++)
+    if (ssa_names_set && ssa_names_set->contains (gimple_op (stmt, i)))
+      return false;
+
+  return true;
+}
+
+/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
+   return true if phi nodes are semantically equivalent in these blocks.  */
+
+bool
+func_checker::compare_phi_node (sem_bb *sem_bb1, sem_bb *sem_bb2)
+{
+  gphi_iterator si1, si2;
+  gphi *phi1, *phi2;
+  unsigned size1, size2, i;
+  tree t1, t2;
+  edge e1, e2;
+
+  basic_block bb1 = sem_bb1->bb;
+  basic_block bb2 = sem_bb2->bb;
+
+  gcc_assert (bb1 != NULL);
+  gcc_assert (bb2 != NULL);
+
+  si2 = gsi_start_phis (bb2);
+  for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
+       gsi_next (&si1))
+    {
+      gsi_next_nonvirtual_phi (&si1);
+      gsi_next_nonvirtual_phi (&si2);
+
+      if (gsi_end_p (si1) && gsi_end_p (si2))
+	break;
+
+      if (gsi_end_p (si1) || gsi_end_p (si2))
+	return return_false ();
+
+      phi1 = si1.phi ();
+      phi2 = si2.phi ();
+
+      tree phi_result1 = gimple_phi_result (phi1);
+      tree phi_result2 = gimple_phi_result (phi2);
+
+      if (!compare_operand (phi_result1, phi_result2))
+	return return_false_with_msg ("PHI results are different");
+
+      size1 = gimple_phi_num_args (phi1);
+      size2 = gimple_phi_num_args (phi2);
+
+      if (size1 != size2)
+	return return_false ();
+
+      for (i = 0; i < size1; ++i)
+	{
+	  t1 = gimple_phi_arg (phi1, i)->def;
+	  t2 = gimple_phi_arg (phi2, i)->def;
+
+	  if (!compare_operand (t1, t2))
+	    return return_false ();
+
+	  e1 = gimple_phi_arg_edge (phi1, i);
+	  e2 = gimple_phi_arg_edge (phi2, i);
+
+	  if (!compare_edge (e1, e2))
+	    return return_false ();
+	}
+
+      gsi_next (&si2);
+    }
+
+  return true;
+}
+
+
+bool
+func_checker::compare_bb_tail_merge (sem_bb *bb1, sem_bb *bb2)
+{
+  if (!compare_bb (bb1, bb2))
+    return return_false_with_msg ("BB are different");
+
+  if (!compare_phi_node (bb1, bb2))
+    return return_false_with_msg ("PHI nodes are different");
+
+  return true;
+}
+
 /* Basic block equivalence comparison function that returns true if
    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 
@@ -642,25 +813,47 @@ func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
   gsi1 = gsi_start_bb_nondebug (bb1->bb);
   gsi2 = gsi_start_bb_nondebug (bb2->bb);
 
-  while (!gsi_end_p (gsi1))
+  ssa_names_set ssa_names_set1;
+  ssa_names_set ssa_names_set2;
+
+  ssa_names_set1.build (bb1->bb);
+  ssa_names_set2.build (bb2->bb);
+
+  while (true)
     {
-      if (gsi_end_p (gsi2))
-	return return_false ();
+      if (m_tail_merge_mode)
+	{
+	  gsi_next_nonlocal (&gsi1, &ssa_names_set1);
+	  gsi_next_nonlocal (&gsi2, &ssa_names_set2);
+	}
+
+      if (gsi_end_p (gsi1) || gsi_end_p (gsi2))
+	break;
 
       s1 = gsi_stmt (gsi1);
       s2 = gsi_stmt (gsi2);
 
+      /* What could be better than to this this here is to blacklist the bb
+	 containing the stmt, when encountering the stmt f.i. in
+	 same_succ_hash.  */
+      if (is_tm_ending (s1)
+	  || is_tm_ending (s2))
+	return return_false_with_msg ("TM endings are different");
+
       int eh1 = lookup_stmt_eh_lp_fn
 		(DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
       int eh2 = lookup_stmt_eh_lp_fn
 		(DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 
-      if (eh1 != eh2)
+      if (eh1 != eh2 && !m_tail_merge_mode)
 	return return_false_with_msg ("EH regions are different");
 
       if (gimple_code (s1) != gimple_code (s2))
 	return return_false_with_msg ("gimple codes are different");
 
+      /* Reset inner state of the checker.  */
+      reset_preferences ();
+
       switch (gimple_code (s1))
 	{
 	case GIMPLE_CALL:
@@ -723,7 +916,7 @@ func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
       gsi_next_nondebug (&gsi2);
     }
 
-  if (!gsi_end_p (gsi2))
+  if (!gsi_end_p (gsi1) || !gsi_end_p (gsi2))
     return return_false ();
 
   return true;
@@ -776,6 +969,8 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
     return return_false_with_msg ("static call chains are different");
 
   /* Checking of argument.  */
+  set_comparing_sensitive_rhs ();
+
   for (i = 0; i < gimple_call_num_args (s1); ++i)
     {
       t1 = gimple_call_arg (s1, i);
@@ -785,10 +980,29 @@ func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 	return return_false_with_msg ("memory operands are different");
     }
 
+  /* Reset preferences after we compare all arguments.  */
+  reset_preferences ();
+
   /* Return value checking.  */
   t1 = gimple_get_lhs (s1);
   t2 = gimple_get_lhs (s2);
 
+  /* In case of tail merge mode, ignore all UBSAN_* internal functions.  */
+  if (gimple_call_internal_p (s1))
+    switch (gimple_call_internal_fn (s1))
+      {
+	case IFN_UBSAN_NULL:
+	case IFN_UBSAN_BOUNDS:
+	case IFN_UBSAN_VPTR:
+	case IFN_UBSAN_CHECK_ADD:
+	case IFN_UBSAN_CHECK_SUB:
+	case IFN_UBSAN_CHECK_MUL:
+	case IFN_UBSAN_OBJECT_SIZE:
+	  return false;
+	default:
+	  break;
+      }
+
   return compare_memory_operand (t1, t2);
 }
 
@@ -820,6 +1034,10 @@ func_checker::compare_gimple_assign (gimple s1, gimple s2)
       arg1 = gimple_op (s1, i);
       arg2 = gimple_op (s2, i);
 
+      /* Set indication that we're going to compare RHS of a gimple assign.  */
+      if (i != 0)
+	set_comparing_sensitive_rhs ();
+
       if (!compare_memory_operand (arg1, arg2))
 	return return_false_with_msg ("memory operands are different");
     }
@@ -869,9 +1087,6 @@ func_checker::compare_tree_ssa_label (tree t1, tree t2)
 bool
 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 {
-  if (m_ignore_labels)
-    return true;
-
   tree t1 = gimple_label_label (g1);
   tree t2 = gimple_label_label (g2);
 
@@ -1037,4 +1252,67 @@ func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
   return true;
 }
 
-} // ipa_icf_gimple namespace
+void
+ssa_names_set::build (basic_block bb)
+{
+  tree var;
+  ssa_op_iter iter;
+
+  /* Build default set of important SSA names.  */
+  gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
+
+  /* In the first phase, we iterate all non-local statements and
+     we extract all SSA names that are used in these statements.  */
+  while (!gsi_end_p (gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+      if (!func_checker::stmt_local_def (stmt, NULL))
+	for (unsigned i = 0; i < gimple_num_ops (stmt); i++)
+	  add (gimple_op (stmt, i));
+
+      gsi_next_nondebug (&gsi);
+    }
+
+  gsi = gsi_last_nondebug_bb (bb);
+
+  /* In the second phase, we process reverse run through all statements
+     and we add all SSA names whose values is based on a SSA name already
+     belonging to set.  The set was created in previous step and
+     is incrementally expanded.  At the end of this phase, we will have
+     all SSA names that not used just locally.  */
+  while (!gsi_end_p (gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+
+      switch (gimple_code (stmt))
+	{
+	  case GIMPLE_ASSIGN:
+	    {
+	      tree lhs = gimple_assign_lhs (stmt);
+	      if (contains (lhs))
+		{
+		  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+		    add (var);
+		}
+	      break;
+	    }
+	  case GIMPLE_COND:
+	  case GIMPLE_SWITCH:
+	  case GIMPLE_CALL:
+	  case GIMPLE_RETURN:
+	  case GIMPLE_ASM:
+	    {
+	      FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
+		add (var);
+
+	      break;
+	    }
+	  default:
+	    break;
+	}
+
+      gsi_prev_nondebug (&gsi);
+    }
+}
+
+} // icf namespace
diff --git a/gcc/ipa-icf-gimple.h b/gcc/ipa-icf-gimple.h
index 6a9cbed..3e8db52 100644
--- a/gcc/ipa-icf-gimple.h
+++ b/gcc/ipa-icf-gimple.h
@@ -106,13 +106,14 @@ return_different_stmts_1 (gimple s1, gimple s2, const char *code,
 #define return_different_stmts(s1, s2, code) \
   return_different_stmts_1 (s1, s2, code, __func__, __LINE__)
 
-namespace ipa_icf_gimple {
+namespace icf {
 
 /* Basic block struct for semantic equality pass.  */
 class sem_bb
 {
 public:
-  sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
+  sem_bb (basic_block bb_, unsigned nondbg_stmt_count_ = 0,
+	  unsigned edge_count_ = 0):
     bb (bb_), nondbg_stmt_count (nondbg_stmt_count_), edge_count (edge_count_) {}
 
   /* Basic block the structure belongs to.  */
@@ -125,6 +126,9 @@ public:
   unsigned edge_count;
 };
 
+/* Forward declaration.  */
+class ssa_names_set;
+
 /* A class aggregating all connections and semantic equivalents
    for a given pair of semantic function candidates.  */
 class func_checker
@@ -138,7 +142,7 @@ public:
      of declarations that can be skipped.  */
   func_checker (tree source_func_decl, tree target_func_decl,
 		bool compare_polymorphic,
-		bool ignore_labels = false,
+		bool tail_merge_mode = false,
 		hash_set<symtab_node *> *ignored_source_nodes = NULL,
 		hash_set<symtab_node *> *ignored_target_nodes = NULL);
 
@@ -149,11 +153,20 @@ public:
      mapping between basic blocks and labels.  */
   void parse_labels (sem_bb *bb);
 
+  /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
+     true value is returned if phi nodes are semantically
+     equivalent in these blocks.  */
+  bool compare_phi_node (sem_bb *sem_bb1, sem_bb *sem_bb2);
+
+  /* Run tail-merge comparison for basic blocks BB1 and BB2.  */
+  bool compare_bb_tail_merge (sem_bb *bb1, sem_bb *bb2);
+
   /* Basic block equivalence comparison function that returns true if
      basic blocks BB1 and BB2 correspond.  */
   bool compare_bb (sem_bb *bb1, sem_bb *bb2);
 
-  /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
+  /* Verifies that trees T1 and T2 are equivalent from
+     identical code perspective.  */
   bool compare_ssa_name (tree t1, tree t2);
 
   /* Verification function for edges E1 and E2.  */
@@ -219,24 +232,35 @@ public:
      two trees are semantically equivalent.  */
   bool compare_tree_list_operand (tree t1, tree t2);
 
-  /* Verifies that trees T1 and T2, representing function declarations
-     are equivalent from perspective of ICF.  */
-  bool compare_function_decl (tree t1, tree t2);
-
   /* Verifies that trees T1 and T2 do correspond.  */
   bool compare_variable_decl (tree t1, tree t2);
 
+  /* Reset checker preferences.  */
+  void reset_preferences ();
+
+  /* Set flag that we compare sensitive RHS of a gimple statement.  */
+  void set_comparing_sensitive_rhs ();
+
   /* Return true if types are compatible for polymorphic call analysis.
      COMPARE_PTR indicates if polymorphic type comparsion should be
      done for pointers, too.  */
   static bool compatible_polymorphic_types_p (tree t1, tree t2,
 					      bool compare_ptr);
 
-  /* Return true if types are compatible from perspective of ICF.
+  /* Return true if types are compatible from identical code perspective.
      FIRST_ARGUMENT indicates if the comparison is called for
      first parameter of a function.  */
   static bool compatible_types_p (tree t1, tree t2);
 
+  /* Return true if gimple STMT is just a local definition in a
+     basic block.  Local definition in this context means that a product
+     of the statement (transitively) does not escape the basic block.
+     Used SSA names are contained in SSA_NAMES_SET.  */
+  static bool stmt_local_def (gimple stmt, ssa_names_set *ssa_names_set);
+
+  /* Advance the iterator to the next non-local gimple statement.  */
+  static void gsi_next_nonlocal (gimple_stmt_iterator *i,
+			  ssa_names_set *ssa_names_set);
 
 private:
   /* Vector mapping source SSA names to target ones.  */
@@ -271,8 +295,61 @@ private:
   /* Flag if polymorphic comparison should be executed.  */
   bool m_compare_polymorphic;
 
-  /* Flag if ignore labels in comparison.  */
-  bool m_ignore_labels;
+  /* Flag which changes behavior for tree-ssa-tail-merge pass.  */
+  bool m_tail_merge_mode;
+
+  /* Flag which indicates that we compare a sensitve RHS operand.  */
+  bool m_comparing_sensitive_rhs;
 };
 
-} // ipa_icf_gimple namespace
+/* SSA NAMES set.  */
+class ssa_names_set
+{
+public:
+  /* Return true if SSA_NAME is in the set.  */
+  bool contains (tree ssa_name);
+
+  /* Add a new SSA_NAME to the set.  */
+  void add (tree ssa_name);
+
+  /* Build the set for given basic block BB.  In the first phase, we collect
+     all SSA names that are not used not just in the basic block.  After that,
+     having this set of SSA names, we can efficiently mark all statements
+     in the basic block that must be compared for equality.  The rest can be
+     just skipped.  Very similar operation was processed
+     in original implementation of tree-ssa-tail merge pass.  */
+  void build (basic_block bb);
+
+private:
+  hash_set <tree> m_set;
+};
+
+inline void
+func_checker::gsi_next_nonlocal (gimple_stmt_iterator *i,
+				 ssa_names_set *ssa_names_set)
+{
+  while (!gsi_end_p (*i) &&
+	 (is_gimple_debug (gsi_stmt (*i))
+	  || func_checker::stmt_local_def (gsi_stmt (*i), ssa_names_set)))
+    gsi_next (i);
+}
+
+inline bool
+ssa_names_set::contains (tree ssa_name)
+{
+  if (ssa_name == NULL || TREE_CODE (ssa_name) != SSA_NAME)
+    return false;
+
+  return m_set.contains (ssa_name);
+}
+
+inline void
+ssa_names_set::add (tree ssa_name)
+{
+  if (ssa_name == NULL || TREE_CODE (ssa_name) != SSA_NAME)
+    return;
+
+  m_set.add (ssa_name);
+}
+
+} // icf namespace
diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 3597b3a1..ca4f1e9 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -97,9 +97,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "stor-layout.h"
 #include "dbgcnt.h"
 
-using namespace ipa_icf_gimple;
-
-namespace ipa_icf {
+namespace icf {
 
 /* Initialization and computation of symtab node hash, there data
    are propagated later on.  */
@@ -995,7 +993,8 @@ sem_function::equals_private (sem_item *item)
 
   /* Basic block PHI nodes comparison.  */
   for (unsigned i = 0; i < bb_sorted.length (); i++)
-    if (!compare_phi_node (bb_sorted[i]->bb, m_compared_func->bb_sorted[i]->bb))
+    if (!m_checker->compare_phi_node (bb_sorted[i],
+				      m_compared_func->bb_sorted[i]))
       return return_false_with_msg ("PHI node comparison returns false");
 
   return result;
@@ -1707,70 +1706,6 @@ sem_function::parse (cgraph_node *node, bitmap_obstack *stack)
   return f;
 }
 
-/* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
-   return true if phi nodes are semantically equivalent in these blocks .  */
-
-bool
-sem_function::compare_phi_node (basic_block bb1, basic_block bb2)
-{
-  gphi_iterator si1, si2;
-  gphi *phi1, *phi2;
-  unsigned size1, size2, i;
-  tree t1, t2;
-  edge e1, e2;
-
-  gcc_assert (bb1 != NULL);
-  gcc_assert (bb2 != NULL);
-
-  si2 = gsi_start_phis (bb2);
-  for (si1 = gsi_start_phis (bb1); !gsi_end_p (si1);
-       gsi_next (&si1))
-    {
-      gsi_next_nonvirtual_phi (&si1);
-      gsi_next_nonvirtual_phi (&si2);
-
-      if (gsi_end_p (si1) && gsi_end_p (si2))
-	break;
-
-      if (gsi_end_p (si1) || gsi_end_p (si2))
-	return return_false();
-
-      phi1 = si1.phi ();
-      phi2 = si2.phi ();
-
-      tree phi_result1 = gimple_phi_result (phi1);
-      tree phi_result2 = gimple_phi_result (phi2);
-
-      if (!m_checker->compare_operand (phi_result1, phi_result2))
-	return return_false_with_msg ("PHI results are different");
-
-      size1 = gimple_phi_num_args (phi1);
-      size2 = gimple_phi_num_args (phi2);
-
-      if (size1 != size2)
-	return return_false ();
-
-      for (i = 0; i < size1; ++i)
-	{
-	  t1 = gimple_phi_arg (phi1, i)->def;
-	  t2 = gimple_phi_arg (phi2, i)->def;
-
-	  if (!m_checker->compare_operand (t1, t2))
-	    return return_false ();
-
-	  e1 = gimple_phi_arg_edge (phi1, i);
-	  e2 = gimple_phi_arg_edge (phi2, i);
-
-	  if (!m_checker->compare_edge (e1, e2))
-	    return return_false ();
-	}
-
-      gsi_next (&si2);
-    }
-
-  return true;
-}
-
 /* Returns true if tree T can be compared as a handled component.  */
 
 bool
@@ -3553,10 +3488,10 @@ public:
   }
 }; // class pass_ipa_icf
 
-} // ipa_icf namespace
+} // icf namespace
 
 ipa_opt_pass_d *
 make_pass_ipa_icf (gcc::context *ctxt)
 {
-  return new ipa_icf::pass_ipa_icf (ctxt);
+  return new icf::pass_ipa_icf (ctxt);
 }
diff --git a/gcc/ipa-icf.h b/gcc/ipa-icf.h
index 6428f25..0cc9c98 100644
--- a/gcc/ipa-icf.h
+++ b/gcc/ipa-icf.h
@@ -19,7 +19,7 @@ You should have received a copy of the GNU General Public License
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
-namespace ipa_icf {
+namespace icf {
 class sem_item;
 
 /* Congruence class encompasses a collection of either functions or
@@ -350,19 +350,23 @@ public:
   unsigned ssa_names_size;
 
   /* Array of structures for all basic blocks.  */
-  vec <ipa_icf_gimple::sem_bb *> bb_sorted;
+  vec <sem_bb *> bb_sorted;
 
   /* Return true if parameter I may be used.  */
   bool param_used_p (unsigned int i);
 
+  /* Set a new function checker.  */
+  void set_checker (func_checker *checker)
+  {
+    if (m_checker)
+      delete m_checker;
+
+    m_checker = checker;
+  }
+
 private:
   /* Calculates hash value based on a BASIC_BLOCK.  */
-  hashval_t get_bb_hash (const ipa_icf_gimple::sem_bb *basic_block);
-
-  /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
-     true value is returned if phi nodes are semantically
-     equivalent in these blocks .  */
-  bool compare_phi_node (basic_block bb1, basic_block bb2);
+  hashval_t get_bb_hash (const sem_bb *basic_block);
 
   /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
      corresponds to TARGET.  */
@@ -379,7 +383,7 @@ private:
   static bool icf_handled_component_p (tree t);
 
   /* Function checker stores binding between functions.   */
-  ipa_icf_gimple::func_checker *m_checker;
+  func_checker *m_checker;
 
   /* COMPARED_FUNC is a function that we compare to.  */
   sem_function *m_compared_func;
@@ -627,4 +631,4 @@ private:
   bitmap_obstack m_bmstack;
 }; // class sem_item_optimizer
 
-} // ipa_icf namespace
+} // icf namespace
diff --git a/gcc/passes.def b/gcc/passes.def
index 6b66f8f..c20357d 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -216,6 +216,7 @@ along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_laddress);
       NEXT_PASS (pass_split_crit_edges);
       NEXT_PASS (pass_pre);
+      NEXT_PASS (pass_tail_merge);
       NEXT_PASS (pass_sink_code);
       NEXT_PASS (pass_asan);
       NEXT_PASS (pass_tsan);
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 7b66a1c..9b8e4a9 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -395,7 +395,7 @@ extern gimple_opt_pass *make_pass_merge_phi (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_split_crit_edges (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_laddress (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_pre (gcc::context *ctxt);
-extern unsigned int tail_merge_optimize (unsigned int);
+extern gimple_opt_pass *make_pass_tail_merge (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_profile (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index 041cb78..8f56881 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -4869,15 +4869,6 @@ pass_pre::execute (function *fun)
   todo |= fini_eliminate ();
   loop_optimizer_finalize ();
 
-  /* TODO: tail_merge_optimize may merge all predecessors of a block, in which
-     case we can merge the block with the remaining predecessor of the block.
-     It should either:
-     - call merge_blocks after each tail merge iteration
-     - call merge_blocks after all tail merge iterations
-     - mark TODO_cleanup_cfg when necessary
-     - share the cfg cleanup with fini_pre.  */
-  todo |= tail_merge_optimize (todo);
-
   free_scc_vn ();
 
   /* Tail merging invalidates the virtual SSA web, together with
diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c
index 88a3032..8c9a1cb 100644
--- a/gcc/tree-ssa-tail-merge.c
+++ b/gcc/tree-ssa-tail-merge.c
@@ -1,6 +1,7 @@
 /* Tail merging for gimple.
    Copyright (C) 2011-2015 Free Software Foundation, Inc.
    Contributed by Tom de Vries (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,24 +345,29 @@ gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
     }
 }
 
-/* VAL1 and VAL2 are either:
-   - uses in BB1 and BB2, or
-   - phi alternatives for BB1 and BB2.
-   Return true if the uses have the same gvn value.  */
+/* Return true if either VAL1 and VAL2 are constant values and are equal,
+   or if both values are SSA names.  In this case we conditionally return true
+   and ICF machinery will verify that these SSA names are really equivalent
+   in basic blocks we compare.  */
 
 static bool
-gvn_uses_equal (tree val1, tree val2)
+equal_ssa_uses (tree val1, tree val2,
+		auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
 {
   gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
 
   if (val1 == val2)
     return true;
 
-  if (vn_valueize (val1) != vn_valueize (val2))
+  if (CONSTANT_CLASS_P (val1) && CONSTANT_CLASS_P (val2))
+    return operand_equal_p (val1, val2, OEP_ONLY_CONST);
+  else if (TREE_CODE (val1) == SSA_NAME && TREE_CODE (val2) == SSA_NAME)
+    {
+      ssa_phi_pairs->safe_push (std::make_pair (val1, val2));
+      return true;
+    }
+  else
     return false;
-
-  return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
-	  && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
 }
 
 /* Prints E to FILE.  */
@@ -454,7 +444,6 @@ same_succ_hash (const_same_succ e)
   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
   int size = 0;
   gimple stmt;
-  tree arg;
   unsigned int s;
   bitmap_iterator bs;
 
@@ -480,12 +469,6 @@ same_succ_hash (const_same_succ e)
 	  if (gimple_call_chain (stmt))
 	    inchash::add_expr (gimple_call_chain (stmt), hstate);
 	}
-      for (i = 0; i < gimple_call_num_args (stmt); i++)
-	{
-	  arg = gimple_call_arg (stmt, i);
-	  arg = vn_valueize (arg);
-	  inchash::add_expr (arg, hstate);
-	}
     }
 
   hstate.add_int (size);
@@ -818,6 +801,10 @@ static void
 same_succ_flush_bb (basic_block bb)
 {
   same_succ same = BB_SAME_SUCC (bb);
+
+  if (same == NULL)
+    return;
+
   BB_SAME_SUCC (bb) = NULL;
   if (bitmap_single_bit_set_p (same->bbs))
     same_succ_htab->remove_elt_with_hash (same, same->hashval);
@@ -1083,201 +1070,94 @@ set_cluster (basic_block bb1, basic_block bb2)
     gcc_unreachable ();
 }
 
-/* Return true if gimple operands T1 and T2 have the same value.  */
-
-static bool
-gimple_operand_equal_value_p (tree t1, tree t2)
-{
-  if (t1 == t2)
-    return true;
-
-  if (t1 == NULL_TREE
-      || t2 == NULL_TREE)
-    return false;
-
-  if (operand_equal_p (t1, t2, 0))
-    return true;
-
-  return gvn_uses_equal (t1, t2);
-}
-
-/* Return true if gimple statements S1 and S2 are equal.  Gimple_bb (s1) and
-   gimple_bb (s2) are members of SAME_SUCC.  */
+/* Make sure that all edges coming from basic block BB1 and BB2 have
+   the same destination index, and make sure that true/false edge values
+   are equal.  */
 
 static bool
-gimple_equal_p (same_succ same_succ, gimple s1, gimple s2)
+check_edges_correspondence (basic_block bb1, basic_block bb2)
 {
-  unsigned int i;
-  tree lhs1, lhs2;
-  basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
-  tree t1, t2;
-  bool inv_cond;
-  enum tree_code code1, code2;
-
-  if (gimple_code (s1) != gimple_code (s2))
-    return false;
+  edge e1, e2;
+  edge_iterator ei2 = ei_start (bb2->succs);
 
-  switch (gimple_code (s1))
+  for (edge_iterator ei1 = ei_start (bb1->succs); ei_cond (ei1, &e1);
+       ei_next (&ei1))
     {
-    case GIMPLE_CALL:
-      if (!gimple_call_same_target_p (s1, s2))
-	return false;
-
-      t1 = gimple_call_chain (s1);
-      t2 = gimple_call_chain (s2);
-      if (!gimple_operand_equal_value_p (t1, t2))
-	return false;
-
-      if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
-	return false;
-
-      for (i = 0; i < gimple_call_num_args (s1); ++i)
-	{
-	  t1 = gimple_call_arg (s1, i);
-	  t2 = gimple_call_arg (s2, i);
-	  if (!gimple_operand_equal_value_p (t1, t2))
-	    return false;
-	}
-
-      lhs1 = gimple_get_lhs (s1);
-      lhs2 = gimple_get_lhs (s2);
-      if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
-	return true;
-      if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
-	return false;
-      if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
-	return vn_valueize (lhs1) == vn_valueize (lhs2);
-      return operand_equal_p (lhs1, lhs2, 0);
-
-    case GIMPLE_ASSIGN:
-      lhs1 = gimple_get_lhs (s1);
-      lhs2 = gimple_get_lhs (s2);
-      if (TREE_CODE (lhs1) != SSA_NAME
-	  && TREE_CODE (lhs2) != SSA_NAME)
-	return (operand_equal_p (lhs1, lhs2, 0)
-		&& gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
-						 gimple_assign_rhs1 (s2)));
-      else if (TREE_CODE (lhs1) == SSA_NAME
-	       && TREE_CODE (lhs2) == SSA_NAME)
-	return operand_equal_p (gimple_assign_rhs1 (s1),
-				gimple_assign_rhs1 (s2), 0);
-      return false;
-
-    case GIMPLE_COND:
-      t1 = gimple_cond_lhs (s1);
-      t2 = gimple_cond_lhs (s2);
-      if (!gimple_operand_equal_value_p (t1, t2))
-	return false;
+      ei_cond (ei2, &e2);
 
-      t1 = gimple_cond_rhs (s1);
-      t2 = gimple_cond_rhs (s2);
-      if (!gimple_operand_equal_value_p (t1, t2))
+      if (e1->dest->index != e2->dest->index
+	  || (e1->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
+	    != (e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
 	return false;
 
-      code1 = gimple_expr_code (s1);
-      code2 = gimple_expr_code (s2);
-      inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
-		  != bitmap_bit_p (same_succ->inverse, bb2->index));
-      if (inv_cond)
-	{
-	  bool honor_nans = HONOR_NANS (t1);
-	  code2 = invert_tree_comparison (code2, honor_nans);
-	}
-      return code1 == code2;
-
-    default:
-      return false;
+      ei_next (&ei2);
     }
-}
-
-/* Let GSI skip backwards over local defs.  Return the earliest vuse in VUSE.
-   Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
-   processed statements.  */
-
-static void
-gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
-				  bool *vuse_escaped)
-{
-  gimple stmt;
-  tree lvuse;
-
-  while (true)
-    {
-      if (gsi_end_p (*gsi))
-	return;
-      stmt = gsi_stmt (*gsi);
 
-      lvuse = gimple_vuse (stmt);
-      if (lvuse != NULL_TREE)
-	{
-	  *vuse = lvuse;
-	  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
-	    *vuse_escaped = true;
-	}
-
-      if (!stmt_local_def (stmt))
-	return;
-      gsi_prev_nondebug (gsi);
-    }
+  return true;
 }
 
 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates.  If so,
    clusters them.  */
 
 static void
-find_duplicate (same_succ same_succ, basic_block bb1, basic_block bb2)
+find_duplicate (basic_block bb1, basic_block bb2, sem_function &f,
+		auto_vec<std::pair<tree, tree> > &ssa_phi_pairs)
 {
-  gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
-  gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
-  tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
-  bool vuse_escaped = false;
+  sem_bb sem_bb1 = sem_bb (bb1);
+  sem_bb sem_bb2 = sem_bb (bb2);
+
+  func_checker *checker = new func_checker (f.decl, f.decl, true, true);
+  f.set_checker (checker);
+  bool icf_result = checker->compare_bb_tail_merge (&sem_bb1, &sem_bb2);
 
-  gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
-  gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
+  if (!icf_result || !check_edges_correspondence (bb1, bb2))
+    return;
 
-  while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
+  for (unsigned i = 0; i < ssa_phi_pairs.length (); i++)
     {
-      gimple stmt1 = gsi_stmt (gsi1);
-      gimple stmt2 = gsi_stmt (gsi2);
-
-      /* What could be better than this here is to blacklist the bb
-	 containing the stmt, when encountering the stmt f.i. in
-	 same_succ_hash.  */
-      if (is_tm_ending (stmt1)
-	  || is_tm_ending (stmt2))
-	return;
+      std::pair<tree, tree> v = ssa_phi_pairs[i];
 
-      if (!gimple_equal_p (same_succ, stmt1, stmt2))
-	return;
+      /* If one of definitions does not belong the function we consider
+	 for equation, SSA names must be a same pointer.  */
+      gimple def1 = SSA_NAME_DEF_STMT (v.first);
+      gimple def2 = SSA_NAME_DEF_STMT (v.second);
 
-      gsi_prev_nondebug (&gsi1);
-      gsi_prev_nondebug (&gsi2);
-      gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
-      gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
-    }
+      basic_block bbdef1 = gimple_bb (def1);
+      basic_block bbdef2 = gimple_bb (def2);
 
-  if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
-    return;
+      if (bb1 != bbdef1 || bb2 != bbdef2)
+	if (v.first != v.second)
+	  return;
 
-  /* If the incoming vuses are not the same, and the vuse escaped into an
-     SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
-     which potentially means the semantics of one of the blocks will be changed.
-     TODO: make this check more precise.  */
-  if (vuse_escaped && vuse1 != vuse2)
-    return;
+      if (!checker->compare_ssa_name (v.first, v.second))
+	return;
+    }
 
   if (dump_file)
+    {
     fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
 	     bb1->index, bb2->index);
 
-  set_cluster (bb1, bb2);
+    }
+
+  if (dbg_cnt (tail_merge))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  dump_bb (dump_file, bb1, 0, TDF_DETAILS);
+	  dump_bb (dump_file, bb2, 0, TDF_DETAILS);
+	}
+
+      set_cluster (bb1, bb2);
+    }
 }
 
 /* Returns whether for all phis in DEST the phi alternatives for E1 and
    E2 are equal.  */
 
 static bool
-same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
+same_phi_alternatives_1 (basic_block dest, edge e1, edge e2,
+			 auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
 {
   int n1 = e1->dest_idx, n2 = e2->dest_idx;
   gphi_iterator gsi;
@@ -1294,7 +1174,8 @@ same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
 
       if (operand_equal_for_phi_arg_p (val1, val2))
 	continue;
-      if (gvn_uses_equal (val1, val2))
+
+      if (equal_ssa_uses (val1, val2, ssa_phi_pairs))
 	continue;
 
       return false;
@@ -1307,7 +1188,8 @@ same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
    phi alternatives for BB1 and BB2 are equal.  */
 
 static bool
-same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
+same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2,
+		       auto_vec<std::pair<tree, tree> > *ssa_phi_pairs)
 {
   unsigned int s;
   bitmap_iterator bs;
@@ -1325,7 +1207,7 @@ same_phi_alternatives (same_succ same_succ, basic_block bb1, basic_block bb2)
 
       /* For all phis in bb, the phi alternatives for e1 and e2 need to have
 	 the same value.  */
-      if (!same_phi_alternatives_1 (succ, e1, e2))
+      if (!same_phi_alternatives_1 (succ, e1, e2, ssa_phi_pairs))
 	return false;
     }
 
@@ -1392,7 +1274,7 @@ deps_ok_for_redirect (basic_block bb1, basic_block bb2)
 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged.  */
 
 static void
-find_clusters_1 (same_succ same_succ)
+find_clusters_1 (same_succ same_succ, sem_function &f)
 {
   basic_block bb1, bb2;
   unsigned int i, j;
@@ -1431,10 +1313,12 @@ find_clusters_1 (same_succ same_succ)
 	  if (!deps_ok_for_redirect (bb1, bb2))
 	    continue;
 
-	  if (!(same_phi_alternatives (same_succ, bb1, bb2)))
+	  auto_vec<std::pair<tree, tree> > ssa_phi_pairs;
+
+	  if (!(same_phi_alternatives (same_succ, bb1, bb2, &ssa_phi_pairs)))
 	    continue;
 
-	  find_duplicate (same_succ, bb1, bb2);
+	  find_duplicate (bb1, bb2, f, ssa_phi_pairs);
 	}
     }
 }
@@ -1442,7 +1326,7 @@ find_clusters_1 (same_succ same_succ)
 /* Find clusters of bbs which can be merged.  */
 
 static void
-find_clusters (void)
+find_clusters (sem_function &f)
 {
   same_succ same;
 
@@ -1455,7 +1339,7 @@ find_clusters (void)
 	  fprintf (dump_file, "processing worklist entry\n");
 	  same_succ_print (dump_file, same);
 	}
-      find_clusters_1 (same);
+      find_clusters_1 (same, f);
     }
 }
 
@@ -1637,9 +1521,10 @@ update_debug_stmts (void)
 
 /* Runs tail merge optimization.  */
 
-unsigned int
-tail_merge_optimize (unsigned int todo)
+static unsigned int
+tail_merge_optimize ()
 {
+  unsigned todo = 0;
   int nr_bbs_removed_total = 0;
   int nr_bbs_removed;
   bool loop_entered = false;
@@ -1660,6 +1545,10 @@ tail_merge_optimize (unsigned int todo)
     }
   init_worklist ();
 
+  bitmap_obstack b;
+  bitmap_obstack_initialize (&b);
+  cgraph_node *node = cgraph_node::get (cfun->decl);
+
   while (!worklist.is_empty ())
     {
       if (!loop_entered)
@@ -1675,7 +1564,8 @@ tail_merge_optimize (unsigned int todo)
       if (dump_file && (dump_flags & TDF_DETAILS))
 	fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
 
-      find_clusters ();
+      sem_function f (node, 0, &b);
+      find_clusters (f);
       gcc_assert (worklist.is_empty ());
       if (all_clusters.is_empty ())
 	break;
@@ -1726,3 +1616,45 @@ tail_merge_optimize (unsigned int todo)
 
   return todo;
 }
+
+namespace {
+
+const pass_data pass_data_tail_merge =
+{
+  GIMPLE_PASS, /* type */
+  "tail-merge", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_TAIL_MERGE, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_update_ssa_only_virtuals, /* todo_flags_finish */
+};
+
+class pass_tail_merge : public gimple_opt_pass
+{
+public:
+  pass_tail_merge (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_tail_merge, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return flag_tree_tail_merge != 0; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_tail_merge
+
+} // anon namespace
+
+unsigned int
+pass_tail_merge::execute (function *)
+{
+  return tail_merge_optimize ();
+}
+
+gimple_opt_pass *
+make_pass_tail_merge (gcc::context *ctxt)
+{
+  return new pass_tail_merge (ctxt);
+}
-- 
2.4.6