Patchwork [tree-optimization,2/2] : Branch-cost optimizations

login
register
mail settings
Submitter Kai Tietz
Date Nov. 6, 2011, 10:17 p.m.
Message ID <038a3161-065e-47c3-8222-8e8815bca853@zmail14.collab.prod.int.phx2.redhat.com>
Download mbox | patch
Permalink /patch/123977/
State New
Headers show

Comments

Kai Tietz - Nov. 6, 2011, 10:17 p.m.
Hello,

the second patch extends the tree-ssa-ifcombine pass so, that it chains up simple if-and/or-if patterns via associative bitwise-and/or operations.  This allows for example optimization for cases like:

if (c == 0) return 2;
if (c == 1) return 2;
if (c == 2) return 2;
...

as now reassociation-pass can optimize on them.

ChangeLog

2011-11-06  Kai Tietz  <ktietz@redhat.com>

        * tree-ssa-ifcombine.c (remove_stmt_chain): New helper.
        (update_gimple_cond_condtion_from_tree): Likewise.
        (stmt_no_side_effects_p): Likewise.
        (bb_no_side_effects_p): Use stmt_no_side_effects_p.
        (bb_no_side_effects_p_2): New helper function.
        (same_phi_args_p_2): Likewise.
        (recognize_single_bit_test): Allow equal and not-equal
        comparison handling.
        (ifcombine_ifandif): Handle equal and not-equal
        (X & CST) !=/== 0 optimization.
        (ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb.
        (ifcombine_iforif_merge): Likewise.
        (ifcombine_iforif): Simplify routine.
        (tree_ssa_ifmerge_bb): New helper for doing if-branch merging.
        (tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif
        and ifandif.
        (tree_ssa_ifcombine): Add if-branch merging and allow
        multiple folding for if-combining.

ChangeLog  testsuite

2011-11-06  Kai Tietz  <ktietz@redhat.com>

        * gcc.dg/tree-ssa/phi-opt-2.c: Adjust test.
        * gcc.dg/tree-ssa/ifcombine-8.c: New test.
        * gcc.dg/tree-ssa/ifcombine-9.c: New test.
        * gcc.dg/tree-ssa/ifcombine-10.c: New test.
        * gcc.dg/tree-ssa/ifcombine-11.c: New test.
        * gcc.dg/tree-ssa/ifcombine-12.c: New test.


Bootstrapped and regression-tested for x86_64-unknown-linux-gnu for all languages (include Ada and Obj-C++).  Ok for apply?

Regards,
Kai
ChangeLog

2011-11-06  Kai Tietz  <ktietz@redhat.com>

	* tree-ssa-ifcombine.c (remove_stmt_chain): New helper.
	(update_gimple_cond_condtion_from_tree): Likewise.
	(stmt_no_side_effects_p): Likewise.
	(bb_no_side_effects_p): Use stmt_no_side_effects_p.
	(bb_no_side_effects_p_2): New helper function.
	(same_phi_args_p_2): Likewise.
	(recognize_single_bit_test): Allow equal and not-equal
	comparison handling.
	(ifcombine_ifandif): Handle equal and not-equal
	(X & CST) !=/== 0 optimization.
	(ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb.
	(ifcombine_iforif_merge): Likewise.
	(ifcombine_iforif): Simplify routine.
	(tree_ssa_ifmerge_bb): New helper for doing if-branch merging.
	(tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif
	and ifandif.
	(tree_ssa_ifcombine): Add if-branch merging and allow
	multiple folding for if-combining.

ChangeLog  testsuite

2011-11-06  Kai Tietz  <ktietz@redhat.com>

	* gcc.dg/tree-ssa/phi-opt-2.c: Adjust test.
	* gcc.dg/tree-ssa/ifcombine-8.c: New test.
	* gcc.dg/tree-ssa/ifcombine-9.c: New test.
	* gcc.dg/tree-ssa/ifcombine-10.c: New test.
	* gcc.dg/tree-ssa/ifcombine-11.c: New test.
	* gcc.dg/tree-ssa/ifcombine-12.c: New test.
Richard Guenther - Nov. 7, 2011, 2:42 p.m.
On Sun, Nov 6, 2011 at 11:17 PM, Kai Tietz <ktietz@redhat.com> wrote:
> Hello,
>
> the second patch extends the tree-ssa-ifcombine pass so, that it chains up simple if-and/or-if patterns via associative bitwise-and/or operations.  This allows for example optimization for cases like:
>
> if (c == 0) return 2;
> if (c == 1) return 2;
> if (c == 2) return 2;
> ...
>
> as now reassociation-pass can optimize on them.

err ... tree-ssa-ifcombine does exactly if "merging", why are you now
adding a "merging" part!?  The above description does not shed any
light on this either.  In fact the above example is something
that should be optimized by phiopt.

Richard.

> ChangeLog
>
> 2011-11-06  Kai Tietz  <ktietz@redhat.com>
>
>        * tree-ssa-ifcombine.c (remove_stmt_chain): New helper.
>        (update_gimple_cond_condtion_from_tree): Likewise.
>        (stmt_no_side_effects_p): Likewise.
>        (bb_no_side_effects_p): Use stmt_no_side_effects_p.
>        (bb_no_side_effects_p_2): New helper function.
>        (same_phi_args_p_2): Likewise.
>        (recognize_single_bit_test): Allow equal and not-equal
>        comparison handling.
>        (ifcombine_ifandif): Handle equal and not-equal
>        (X & CST) !=/== 0 optimization.
>        (ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb.
>        (ifcombine_iforif_merge): Likewise.
>        (ifcombine_iforif): Simplify routine.
>        (tree_ssa_ifmerge_bb): New helper for doing if-branch merging.
>        (tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif
>        and ifandif.
>        (tree_ssa_ifcombine): Add if-branch merging and allow
>        multiple folding for if-combining.
>
> ChangeLog  testsuite
>
> 2011-11-06  Kai Tietz  <ktietz@redhat.com>
>
>        * gcc.dg/tree-ssa/phi-opt-2.c: Adjust test.
>        * gcc.dg/tree-ssa/ifcombine-8.c: New test.
>        * gcc.dg/tree-ssa/ifcombine-9.c: New test.
>        * gcc.dg/tree-ssa/ifcombine-10.c: New test.
>        * gcc.dg/tree-ssa/ifcombine-11.c: New test.
>        * gcc.dg/tree-ssa/ifcombine-12.c: New test.
>
>
> Bootstrapped and regression-tested for x86_64-unknown-linux-gnu for all languages (include Ada and Obj-C++).  Ok for apply?
>
> Regards,
> Kai
>
Kai Tietz - Nov. 7, 2011, 4:07 p.m.
2011/11/7 Richard Guenther <richard.guenther@gmail.com>:
> On Sun, Nov 6, 2011 at 11:17 PM, Kai Tietz <ktietz@redhat.com> wrote:
>> Hello,
>>
>> the second patch extends the tree-ssa-ifcombine pass so, that it chains up simple if-and/or-if patterns via associative bitwise-and/or operations.  This allows for example optimization for cases like:
>>
>> if (c == 0) return 2;
>> if (c == 1) return 2;
>> if (c == 2) return 2;
>> ...
>>
>> as now reassociation-pass can optimize on them.
>
> err ... tree-ssa-ifcombine does exactly if "merging", why are you now
> adding a "merging" part!?  The above description does not shed any
> light on this either.  In fact the above example is something
> that should be optimized by phiopt.
>
> Richard.

Well, the example I provided might be not the best, as indeed phiopt
should handle this.  But if such if-and/or-if chains have for example
the kind
if (a == 0)
   return doo ();
if (a == 1)
  return doo ();

etc.  phiopt won't do much here.  The point why the joining of simple
if-and/or-if conditions via truth-bitwise operation is profitable in
general, is that range-analysis and other stanard reassoc-patterns
getting catched up by reassoc, without the need to duplicate all the
code all over each pass (what we actually doing right now).
The classical ifcombine pass itself has only one point it might be
more profitable over the reassoc pass. and this is if the conditions
might trap, as here indeed we can't transform to associative
bitwise-binary tree.

I put the ifjoining within this pass, as the joining and the merging
passes are sharing some code about pattern-matching for simple
if-and/or-if.  But well, it is easy to factor out here a separate
pass. An additional if-if joining pass might be even profitable after
loop-optimization, and after current first reassociation pass.

This current patch shows already on tests a significant reduction of #
branches.  Together with the BC code in cfgexpand it leads to a fair
reduction in instructions, and even lowers the amount of executed
instructions on extra dynamic condition significant

Regards,
Kai
Richard Guenther - Nov. 7, 2011, 4:15 p.m.
On Mon, Nov 7, 2011 at 5:07 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/11/7 Richard Guenther <richard.guenther@gmail.com>:
>> On Sun, Nov 6, 2011 at 11:17 PM, Kai Tietz <ktietz@redhat.com> wrote:
>>> Hello,
>>>
>>> the second patch extends the tree-ssa-ifcombine pass so, that it chains up simple if-and/or-if patterns via associative bitwise-and/or operations.  This allows for example optimization for cases like:
>>>
>>> if (c == 0) return 2;
>>> if (c == 1) return 2;
>>> if (c == 2) return 2;
>>> ...
>>>
>>> as now reassociation-pass can optimize on them.
>>
>> err ... tree-ssa-ifcombine does exactly if "merging", why are you now
>> adding a "merging" part!?  The above description does not shed any
>> light on this either.  In fact the above example is something
>> that should be optimized by phiopt.
>>
>> Richard.
>
> Well, the example I provided might be not the best, as indeed phiopt
> should handle this.  But if such if-and/or-if chains have for example
> the kind
> if (a == 0)
>   return doo ();
> if (a == 1)
>  return doo ();
>
> etc.  phiopt won't do much here.

tailmerge should change the above to

 if (a == 0 || a == 1)
   return doo ();

Richard.

Patch

Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
===================================================================
--- gcc-trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
@@ -10,7 +10,7 @@  _Bool f1(_Bool a, _Bool b)
      else
       return 0;
    }
-  return 0;
+  return 2;
 }
 
 
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) == 0)
+    if ((x & 8) != 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 8" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) != 0)
+    if ((x & 8) == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 4" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) != 0)
+    return 2;
+  if ((x & 8) != 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "!= 0" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
@@ -0,0 +1,15 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int foo (int x, int a, int b)
+{
+  int c = 1 << a;
+  if ((x & c) == 0)
+    if ((x & (1 << b))  == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\|" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
@@ -0,0 +1,14 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+  if ((x & 4) == 0)
+    if ((x & 8) == 0)
+      /* returning 1 causes phiopt to trigger in */
+      return 2;
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/tree-ssa-ifcombine.c
===================================================================
--- gcc-trunk.orig/gcc/tree-ssa-ifcombine.c
+++ gcc-trunk/gcc/tree-ssa-ifcombine.c
@@ -49,6 +49,65 @@  along with GCC; see the file COPYING3.  
    To simplify this pass, removing basic blocks and dead code
    is left to CFG cleanup and DCE.  */
 
+/* Remove def stmt of VAR if VAR has zero uses and recurse
+   on rhs1, rhs2, and rhs3 operand if so.  */
+
+static void
+remove_stmt_chain (tree var)
+{
+  gimple stmt;
+  gimple_stmt_iterator gsi;
+  tree var2, var3;
+
+  while (1)
+    {
+      if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
+	return;
+      stmt = SSA_NAME_DEF_STMT (var);
+      if (!stmt || !is_gimple_assign (stmt))
+	return;
+      var = gimple_assign_rhs1 (stmt);
+      var2 = var3 = NULL_TREE;
+
+      switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
+        {
+	case  GIMPLE_TERNARY_RHS:
+	  var3 = gimple_assign_rhs3 (stmt);
+	  /* Fall through.  */
+	case GIMPLE_BINARY_RHS:
+	  var2 = gimple_assign_rhs2 (stmt);
+	  break;
+	default:
+	  break;
+	}
+      gsi = gsi_for_stmt (stmt);
+      gsi_remove (&gsi, true);
+      release_defs (stmt);
+      /* Recurse on optional second and third operand,
+         if those arguments are of kind SSA_NAME.  */
+      if (var2 && TREE_CODE (var2) == SSA_NAME)
+        remove_stmt_chain (var2);
+      if (var3 && TREE_CODE (var3) == SSA_NAME)
+        remove_stmt_chain (var3);
+    }
+}
+
+/* Helper to update a gimple_cond condition by tree
+   and remove use-chains of old condition.  */
+
+static void
+update_gimple_cond_condition_from_tree (gimple cond, tree t)
+{
+  tree l, r;
+  l = gimple_cond_lhs (cond);
+  r = gimple_cond_rhs (cond);
+  gimple_cond_set_condition_from_tree (cond, t);
+  update_stmt (cond);
+  if (l)
+    remove_stmt_chain (l);
+  if (r)
+    remove_stmt_chain (r);
+}
 
 /* Recognize a if-then-else CFG pattern starting to match with the
    COND_BB basic-block containing the COND_EXPR.  The recognized
@@ -95,6 +154,25 @@  recognize_if_then_else (basic_block cond
   return true;
 }
 
+/* Check that a statement STMT doesn't have sider-effect.
+   and it doesn't have VUSE.
+   If CHECK_TRAP is true, then additional STMT gets checked
+   for trapping.  */
+
+static bool
+stmt_no_side_effects_p (gimple stmt, bool check_trap)
+{
+  if (!stmt)
+    return true;
+  if (gimple_code (stmt) == GIMPLE_LABEL)
+    return false;
+  if (gimple_has_side_effects (stmt)
+      || (check_trap && gimple_could_trap_p (stmt))
+      || gimple_vuse (stmt))
+    return false;
+  return true;
+}
+
 /* Verify if the basic block BB does not have side-effects.  Return
    true in this case, else false.  */
 
@@ -105,16 +183,31 @@  bb_no_side_effects_p (basic_block bb)
 
   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     {
-      gimple stmt = gsi_stmt (gsi);
-
-      if (gimple_has_side_effects (stmt)
-	  || gimple_vuse (stmt))
+      if (!stmt_no_side_effects_p (gsi_stmt (gsi), false))
 	return false;
     }
 
   return true;
 }
 
+/* Verify if the basic block BB does not have side-effects, or trapping.
+   Return true in this case, else false.  */
+
+static bool
+bb_no_side_effects_p_2 (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      if (!stmt_no_side_effects_p (gsi_stmt (gsi), true))
+        return false;
+    }
+
+  return true;
+}
+
+
 /* Verify if all PHI node arguments in DEST for edges from BB1 or
    BB2 to DEST are the same.  This makes the CFG merge point
    free from side-effects.  Return true in this case, else false.  */
@@ -138,6 +231,59 @@  same_phi_args_p (basic_block bb1, basic_
   return true;
 }
 
+/* Verify if all PHI node arguments in DEST1 for edges from BB1, BB2
+   or DEST2 to DEST1 are the same.  This makes the CFG merge point
+   free from side-effects.  Return true in this case, else false.
+   If DEST1 is not equal to DEST2, then DEST2 has to have a PHI node
+   in DEST1 and DEST2 has not hold statements or its own PHI node.
+   In contrast to same_phi_args_p, function returns for no-PHI valued
+   branches FALSE.  */
+
+static bool
+same_phi_args_p_2 (basic_block bb1, basic_block bb2, basic_block dest1, basic_block dest2)
+{
+  edge e1 = find_edge (bb1, dest1);
+  edge e2 = find_edge (bb2, dest2);
+  gimple_stmt_iterator gsi1;
+  gimple_stmt_iterator gsi2;
+  gimple phi;
+
+  gsi1 = gsi_start_phis (dest1);
+  if (gsi_end_p (gsi1))
+    {
+      gsi2 = gsi_start_phis (dest2);
+      return false;
+    }
+
+  /* See if we can't find a PHI in DEST2 and that we find
+     a PHI edge in DEST1 for DEST2.  */
+  gsi2 = gsi_start_phis (dest2);
+  if (gsi_end_p (gsi2))
+    {
+      /* If DEST2 has no PHI, then it also has not to contain
+         any statements.  */
+      if (last_stmt (dest2) != NULL)
+        return false;
+      gsi2 = gsi1;
+      /* See if we can find DEST2 within PHI of DEST1.  */
+      e2 = find_edge (dest2, dest1);
+      if (!e2)
+        return false;
+    }
+  else if (dest1 != dest2)
+    return false;
+
+  for (; !gsi_end_p (gsi1); gsi_next (&gsi1))
+    {
+      phi = gsi_stmt (gsi1);
+      if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
+			    PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
+	return false;
+    }
+
+  return true;
+}
+
 /* Return the best representative SSA name for CANDIDATE which is used
    in a bit test.  */
 
@@ -165,15 +311,19 @@  get_name_for_bit_test (tree candidate)
 /* Recognize a single bit test pattern in GIMPLE_COND and its defining
    statements.  Store the name being tested in *NAME and the bit
    in *BIT.  The GIMPLE_COND computes *NAME & (1 << *BIT).
+   The GIMPLE_COND code is either NE_EXPR or EQ_EXPR.
+   IS_CMPEQ will be set to true, if comparison is EQ_EXPR, otherwise
+   to false.
    Returns true if the pattern matched, false otherwise.  */
 
 static bool
-recognize_single_bit_test (gimple cond, tree *name, tree *bit)
+recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool *is_cmpeq)
 {
   gimple stmt;
 
   /* Get at the definition of the result of the bit test.  */
-  if (gimple_cond_code (cond) != NE_EXPR
+  if ((gimple_cond_code (cond) != NE_EXPR
+       && gimple_cond_code (cond) != EQ_EXPR)
       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
       || !integer_zerop (gimple_cond_rhs (cond)))
     return false;
@@ -181,6 +331,8 @@  recognize_single_bit_test (gimple cond, 
   if (!is_gimple_assign (stmt))
     return false;
 
+  *is_cmpeq = (gimple_cond_code (cond) == EQ_EXPR);
+
   /* Look at which bit is tested.  One form to recognize is
      D.1985_5 = state_3(D) >> control1_4(D);
      D.1986_6 = (int) D.1985_5;
@@ -306,62 +458,82 @@  ifcombine_ifandif (basic_block inner_con
   gimple_stmt_iterator gsi;
   gimple inner_cond, outer_cond;
   tree name1, name2, bit1, bit2;
+  bool is_cmpeq1, is_cmpeq2;
 
   inner_cond = last_stmt (inner_cond_bb);
-  if (!inner_cond
-      || gimple_code (inner_cond) != GIMPLE_COND)
-    return false;
-
   outer_cond = last_stmt (outer_cond_bb);
-  if (!outer_cond
-      || gimple_code (outer_cond) != GIMPLE_COND)
-    return false;
 
   /* See if we test a single bit of the same name in both tests.  In
      that case remove the outer test, merging both else edges,
      and change the inner one to test for
      name & (bit1 | bit2) == (bit1 | bit2).  */
-  if (recognize_single_bit_test (inner_cond, &name1, &bit1)
-      && recognize_single_bit_test (outer_cond, &name2, &bit2)
+  if (recognize_single_bit_test (inner_cond, &name1, &bit1, &is_cmpeq1)
+      && recognize_single_bit_test (outer_cond, &name2, &bit2, &is_cmpeq2)
       && name1 == name2)
     {
-      tree t, t2;
+      tree t, t1, t2;
 
       /* Do it.  */
       gsi = gsi_for_stmt (inner_cond);
-      t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
+      t1 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 		       build_int_cst (TREE_TYPE (name1), 1), bit1);
       t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
 		        build_int_cst (TREE_TYPE (name1), 1), bit2);
-      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
+      t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t1, t2);
       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 				    true, GSI_SAME_STMT);
+      if (!is_cmpeq1 && !is_cmpeq2)
+        t1 = t;
+      else if (is_cmpeq1 && is_cmpeq2)
+        t1 = build_int_cst (TREE_TYPE (name1), 0);
+      else if (!is_cmpeq1)
+       {
+	 t1 = force_gimple_operand_gsi (&gsi, t1, true, NULL_TREE,
+				        true, GSI_SAME_STMT);
+       }
+     else if (!is_cmpeq2)
+       {
+	 t1 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
+				        true, GSI_SAME_STMT);
+       }
+
       t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
       t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
 				     true, GSI_SAME_STMT);
-      t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
-      t = canonicalize_cond_expr_cond (t);
-      if (!t)
-	return false;
-      gimple_cond_set_condition_from_tree (inner_cond, t);
-      update_stmt (inner_cond);
-
-      /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
-      update_stmt (outer_cond);
-
-      if (dump_file)
-	{
-	  fprintf (dump_file, "optimizing double bit test to ");
-	  print_generic_expr (dump_file, name1, 0);
-	  fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
-	  print_generic_expr (dump_file, bit1, 0);
-	  fprintf (dump_file, ") | (1 << ");
-	  print_generic_expr (dump_file, bit2, 0);
-	  fprintf (dump_file, ")\n");
+      t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1);
+      
+      if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE)
+        {
+	  update_gimple_cond_condition_from_tree (inner_cond, t);
+
+	  /* Leave CFG optimization to cfg_cleanup.  */
+	  update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node);
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "optimizing double bit test to ");
+	      print_generic_expr (dump_file, name1, 0);
+	      fprintf (dump_file, " & T == %s\n",
+		       (!is_cmpeq1 && !is_cmpeq2 ? "T"
+						 : (is_cmpeq1 == is_cmpeq2
+						    ? "0" : "Q")));
+	      fprintf (dump_file, "with temporary T = (1 << ");
+	      print_generic_expr (dump_file, bit1, 0);
+	      fprintf (dump_file, ") | (1 << ");
+	      print_generic_expr (dump_file, bit2, 0);
+	      fprintf (dump_file, ")\n");
+	      if (is_cmpeq1 != is_cmpeq2)
+		{
+		  fprintf (dump_file, "with temporary Q = (1 << ");
+		  if (!is_cmpeq1)
+		    print_generic_expr (dump_file, bit1, 0);
+		  else
+		    print_generic_expr (dump_file, bit2, 0);
+		  fprintf (dump_file, ")\n");
+		}
+	    }
+	  return true;
 	}
-
-      return true;
     }
 
   /* See if we have two comparisons that we can merge into one.  */
@@ -370,27 +542,96 @@  ifcombine_ifandif (basic_block inner_con
     {
       tree t;
 
-      if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
-					    gimple_cond_lhs (inner_cond),
-					    gimple_cond_rhs (inner_cond),
-					    gimple_cond_code (outer_cond),
-					    gimple_cond_lhs (outer_cond),
-					    gimple_cond_rhs (outer_cond))))
-	return false;
-      t = canonicalize_cond_expr_cond (t);
-      if (!t)
-	return false;
-      gimple_cond_set_condition_from_tree (inner_cond, t);
+      if ((t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
+					   gimple_cond_lhs (inner_cond),
+					   gimple_cond_rhs (inner_cond),
+					   gimple_cond_code (outer_cond),
+					   gimple_cond_lhs (outer_cond),
+					   gimple_cond_rhs (outer_cond)))
+	   != NULL
+	  && (t = canonicalize_cond_expr_cond (t)) != NULL)
+        {
+	  update_gimple_cond_condition_from_tree (inner_cond, t);
+
+	  /* Leave CFG optimization to cfg_cleanup.  */
+	  update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node);
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "optimizing two comparisons to ");
+	      print_generic_expr (dump_file, t, 0);
+	      fprintf (dump_file, "\n");
+	    }
+
+	  return true;
+	}
+    }
+
+  return false;
+}
+
+/* If-convert on a and pattern with a common else block.  The inner
+   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+   Returns true if the edges to the common else basic-block were merged
+   via binary-and.  */
+
+static bool
+ifcombine_ifandif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb)
+{
+  gimple_stmt_iterator gsi;
+  gimple inner_cond, outer_cond;
+
+  inner_cond = last_stmt (inner_cond_bb);
+  outer_cond = last_stmt (outer_cond_bb);
+
+  if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+      && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
+    {
+      tree t_l, t_r, t, l, r;
+      location_t loc;
+
+      loc = gimple_location (outer_cond);
+      t_l = fold_build2_loc (loc,
+			     gimple_cond_code (outer_cond),
+			     boolean_type_node,
+			     gimple_cond_lhs (outer_cond),
+			     gimple_cond_rhs (outer_cond));
+      if (tree_could_trap_p (t_l))
+        return false;
+      loc = gimple_location (inner_cond);
+      t_r = fold_build2_loc (loc,
+			     gimple_cond_code (inner_cond),
+			     boolean_type_node,
+			     gimple_cond_lhs (inner_cond),
+			     gimple_cond_rhs (inner_cond));
+
+      if (tree_could_trap_p (t_r))
+        return false;
+      gsi = gsi_for_stmt (inner_cond);
+      t = fold_build2 (BIT_AND_EXPR, boolean_type_node,
+      		       t_l, t_r);
+      t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
+				    true, GSI_SAME_STMT);
+
+      gsi = gsi_for_stmt (inner_cond);
+
+      l = gimple_cond_lhs (inner_cond);
+      r = gimple_cond_rhs (inner_cond);
+      gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node);
       update_stmt (inner_cond);
+      remove_stmt_chain (l);
+      if (r)
+        remove_stmt_chain (r);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
-      update_stmt (outer_cond);
+      update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node);
 
       if (dump_file)
 	{
-	  fprintf (dump_file, "optimizing two comparisons to ");
-	  print_generic_expr (dump_file, t, 0);
+	  fprintf (dump_file, "branching if.and.if to ");
+	  print_generic_expr (dump_file, t_l, 0);
+	  fprintf (dump_file, " & ");
+	  print_generic_expr (dump_file, t_r, 0);
 	  fprintf (dump_file, "\n");
 	}
 
@@ -408,18 +649,12 @@  ifcombine_ifandif (basic_block inner_con
 static bool
 ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
 {
+  gimple_stmt_iterator gsi;
   gimple inner_cond, outer_cond;
   tree name1, name2, bits1, bits2;
 
   inner_cond = last_stmt (inner_cond_bb);
-  if (!inner_cond
-      || gimple_code (inner_cond) != GIMPLE_COND)
-    return false;
-
   outer_cond = last_stmt (outer_cond_bb);
-  if (!outer_cond
-      || gimple_code (outer_cond) != GIMPLE_COND)
-    return false;
 
   /* See if we have two bit tests of the same name in both tests.
      In that case remove the outer test and change the inner one to
@@ -427,7 +662,6 @@  ifcombine_iforif (basic_block inner_cond
   if (recognize_bits_test (inner_cond, &name1, &bits1)
       && recognize_bits_test (outer_cond, &name2, &bits2))
     {
-      gimple_stmt_iterator gsi;
       tree t;
 
       /* Find the common name which is bit-tested.  */
@@ -486,28 +720,26 @@  ifcombine_iforif (basic_block inner_cond
 				    true, GSI_SAME_STMT);
       t = fold_build2 (NE_EXPR, boolean_type_node, t,
 		       build_int_cst (TREE_TYPE (t), 0));
-      t = canonicalize_cond_expr_cond (t);
-      if (!t)
-	return false;
-      gimple_cond_set_condition_from_tree (inner_cond, t);
-      update_stmt (inner_cond);
-
-      /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
-      update_stmt (outer_cond);
+      if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE)
+        {
+	  update_gimple_cond_condition_from_tree (inner_cond, t);
+
+	  /* Leave CFG optimization to cfg_cleanup.  */
+	  update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node);
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "optimizing bits or bits test to ");
+	      print_generic_expr (dump_file, name1, 0);
+	      fprintf (dump_file, " & T != 0\nwith temporary T = ");
+	      print_generic_expr (dump_file, bits1, 0);
+	      fprintf (dump_file, " | ");
+	      print_generic_expr (dump_file, bits2, 0);
+	      fprintf (dump_file, "\n");
+	    }
 
-      if (dump_file)
-	{
-	  fprintf (dump_file, "optimizing bits or bits test to ");
-	  print_generic_expr (dump_file, name1, 0);
-	  fprintf (dump_file, " & T != 0\nwith temporary T = ");
-	  print_generic_expr (dump_file, bits1, 0);
-	  fprintf (dump_file, " | ");
-	  print_generic_expr (dump_file, bits2, 0);
-	  fprintf (dump_file, "\n");
+	  return true;
 	}
-
-      return true;
     }
 
   /* See if we have two comparisons that we can merge into one.
@@ -518,27 +750,97 @@  ifcombine_iforif (basic_block inner_cond
     {
       tree t;
 
-      if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
-					   gimple_cond_lhs (inner_cond),
-					   gimple_cond_rhs (inner_cond),
-					   gimple_cond_code (outer_cond),
-					   gimple_cond_lhs (outer_cond),
-					   gimple_cond_rhs (outer_cond))))
-	return false;
-      t = canonicalize_cond_expr_cond (t);
-      if (!t)
-	return false;
-      gimple_cond_set_condition_from_tree (inner_cond, t);
+      if ((t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
+					  gimple_cond_lhs (inner_cond),
+					  gimple_cond_rhs (inner_cond),
+					  gimple_cond_code (outer_cond),
+					  gimple_cond_lhs (outer_cond),
+					  gimple_cond_rhs (outer_cond)))
+	  != NULL
+	  && (t = canonicalize_cond_expr_cond (t)) != NULL)
+	{
+	  update_gimple_cond_condition_from_tree (inner_cond, t);
+
+	  /* Leave CFG optimization to cfg_cleanup.  */
+	  update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node);
+
+	  if (dump_file)
+	    {
+	      fprintf (dump_file, "optimizing two comparisons to ");
+	      print_generic_expr (dump_file, t, 0);
+	      fprintf (dump_file, "\n");
+	    }
+
+	  return true;
+	}
+    }
+
+  return false;
+}
+
+/* If-convert on a or pattern with a common then block.  The inner
+   if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+   Returns true, if the edges leading to the common then basic-block
+   were merged via binary-or.  */
+
+static bool
+ifcombine_iforif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb)
+{
+  gimple_stmt_iterator gsi;
+  gimple inner_cond, outer_cond;
+
+  inner_cond = last_stmt (inner_cond_bb);
+  outer_cond = last_stmt (outer_cond_bb);
+
+  if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+      && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
+    {
+      tree t_l, t_r, t, l, r;
+      location_t loc;
+
+      loc = gimple_location (outer_cond);
+      t_l = fold_build2_loc (loc,
+      			     gimple_cond_code (outer_cond),
+      			     boolean_type_node,
+      			     gimple_cond_lhs (outer_cond),
+      			     gimple_cond_rhs (outer_cond));
+
+      if (tree_could_trap_p (t_l))
+        return false;
+      loc = gimple_location (inner_cond);
+      t_r = fold_build2_loc (loc,
+      			     gimple_cond_code (inner_cond),
+      			     boolean_type_node,
+      			     gimple_cond_lhs (inner_cond),
+      			     gimple_cond_rhs (inner_cond));
+
+      if (tree_could_trap_p (t_r))
+        return false;
+      gsi = gsi_for_stmt (inner_cond);
+      t = fold_build2 (BIT_IOR_EXPR, boolean_type_node,
+      		       t_l, t_r);
+      t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
+				    true, GSI_SAME_STMT);
+
+      gsi = gsi_for_stmt (inner_cond);
+      l = gimple_cond_lhs (inner_cond);
+      r = gimple_cond_rhs (inner_cond);
+      gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node);
       update_stmt (inner_cond);
+      if (l)
+        remove_stmt_chain (l);
+      if (r)
+        remove_stmt_chain (r);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
-      update_stmt (outer_cond);
+      update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node);
 
       if (dump_file)
 	{
-	  fprintf (dump_file, "optimizing two comparisons to ");
-	  print_generic_expr (dump_file, t, 0);
+	  fprintf (dump_file, "branching if.or.if to ");
+	  print_generic_expr (dump_file, t_l, 0);
+	  fprintf (dump_file, " | ");
+	  print_generic_expr (dump_file, t_r, 0);
 	  fprintf (dump_file, "\n");
 	}
 
@@ -549,68 +851,326 @@  ifcombine_iforif (basic_block inner_cond
 }
 
 /* Recognize a CFG pattern and dispatch to the appropriate
+   if-combine helper.  We start with BB as the innermost
+   worker basic-block.  Returns true if a transformation was done.  */
+
+/* Recognize a CFG pattern and dispatch to the appropriate
    if-conversion helper.  We start with BB as the innermost
    worker basic-block.  Returns true if a transformation was done.  */
 
 static bool
+tree_ssa_ifmerge_bb (basic_block inner_cond_bb)
+{
+  basic_block outer_cond_bb, outer_else_bb, outer_then_bb;
+  basic_block then_bb = NULL, else_bb = NULL;
+  basic_block last_inner_cond_bb;
+  gimple excond;
+  bool cfg_changed = false, in_and_seq = false, in_or_seq = false;
+
+  if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
+    return false;
+
+  /* Has inner bb side-effects?  */
+  if (!bb_no_side_effects_p_2 (inner_cond_bb))
+    return false;
+  last_inner_cond_bb = inner_cond_bb;
+
+  do
+    {
+      /* Recognize && and || of two conditions with a common
+	 then/else block which entry edges we can merge.  That is:
+	   if (a || b)
+	     ;
+	 and
+	   if (a && b)
+	     ;
+	 This requires a single predecessor of the inner cond_bb.  */
+      if (!single_pred_p (last_inner_cond_bb))
+	return cfg_changed;
+
+      outer_cond_bb = single_pred (last_inner_cond_bb);
+      outer_else_bb = NULL;
+      outer_then_bb = NULL;
+
+      if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+				   &outer_else_bb))
+	return cfg_changed;
+
+      /* Check that last_inner_cond_bb doesn't have side-effects.  */
+      if (last_inner_cond_bb != inner_cond_bb
+          && !bb_no_side_effects_p_2 (last_inner_cond_bb))
+	return cfg_changed;
+
+      if (!bb_no_side_effects_p_2 (outer_cond_bb))
+        return cfg_changed;
+
+      /* The && form is characterized by a common else_bb with
+	 the two edges leading to it mergable.  The latter is
+	 guaranteed by matching PHI arguments in the else_bb and
+	 the inner cond_bb having no side-effects.  */
+      if (last_inner_cond_bb == outer_then_bb
+	  && ((else_bb == outer_else_bb
+	       && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb))
+	      || (outer_else_bb == then_bb
+		  && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					 outer_else_bb, then_bb)
+		  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					outer_else_bb, else_bb)))
+	  && bb_no_side_effects_p_2 (inner_cond_bb))
+	{
+	  excond = last_stmt (inner_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND
+	      || gimple_cond_true_p (excond)
+	      || gimple_cond_false_p (excond))
+	    return cfg_changed;
+
+	  excond = last_stmt (outer_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND)
+	    return cfg_changed;
+
+	  if (gimple_cond_true_p (excond))
+	    {
+	      last_inner_cond_bb = outer_cond_bb;
+	      continue;
+	    }
+	  else if (gimple_cond_false_p (excond))
+	    return cfg_changed;
+
+	  if (in_or_seq)
+	    return cfg_changed;
+
+	  /* We have
+	       <outer_cond_bb>
+		 if (q) goto inner_cond_bb; else goto outer_else_bb;
+	       <inner_cond_bb>
+		 if (p) goto ...; else goto else_bb;
+		 ...
+	       <else_bb>
+	       <outer_else_bb>
+		 ...
+	     If the else_bb,is not equal to outer_else_bb, then the
+	     else_bb needs to be empty (no PHIs, no statments) and
+	     and the PHI in outer_else_bb for else_bb has to be the
+	     same value as PHI value for outer_else_bb.  */
+
+	  if (!ifcombine_ifandif_merge (inner_cond_bb, outer_cond_bb))
+	    return cfg_changed;
+
+	  cfg_changed = true;
+	  in_and_seq = true;
+	  last_inner_cond_bb = outer_cond_bb;
+	  continue;
+	}
+
+      /* The || form is characterized by a common then_bb with the
+	 two edges leading to it mergable.  The latter is guaranteed
+	 by matching PHI arguments in the then_bb and the inner cond_bb
+	 having no side-effects.  */
+      if (last_inner_cond_bb == outer_else_bb
+	  && ((then_bb == outer_then_bb
+	       && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb))
+	      || (outer_then_bb == else_bb
+		  && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					 outer_then_bb, else_bb)
+		  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					outer_then_bb, then_bb)))
+	  && bb_no_side_effects_p_2 (inner_cond_bb))
+	{
+	  excond = last_stmt (inner_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND
+	      || gimple_cond_false_p (excond)
+	      || gimple_cond_true_p (excond))
+	    return cfg_changed;
+
+	  excond = last_stmt (outer_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND)
+	    return cfg_changed;
+
+	  if (gimple_cond_false_p (excond))
+	    {
+	      last_inner_cond_bb = outer_cond_bb;
+	      continue;
+	    }
+	  else if (gimple_cond_true_p (excond))
+	    return cfg_changed;
+
+	  if (in_and_seq)
+	    return cfg_changed;
+
+	  /* We have
+	       <outer_cond_bb>
+		 if (q) goto outer_then_bb; else goto inner_cond_bb;
+	       <inner_cond_bb>
+		 if (q) goto then_bb; else goto ...;
+	       <then_bb>
+	       <outer-then_bb>
+		 ...
+	     If the then_bb,is not equal to outer_then_bb, then the
+	     then_bb needs to be empty (no PHIs, no statments) and
+	     the PHI in outer_then_bb for then_bb has to be the same value
+	     as PHI value for outer_then_bb.  */
+	  if (!ifcombine_iforif_merge (inner_cond_bb, outer_cond_bb))
+	    return cfg_changed;
+
+	  cfg_changed = true;
+	  in_or_seq = true;
+	  last_inner_cond_bb = outer_cond_bb;
+	  continue;
+	}
+    }
+  while (0);
+
+  return cfg_changed;
+}
+
+static bool
 tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 {
+  basic_block outer_cond_bb, outer_else_bb, outer_then_bb;
   basic_block then_bb = NULL, else_bb = NULL;
+  basic_block last_inner_cond_bb;
+  gimple excond;
+  bool in_and_seq = false, in_or_seq = false;
 
   if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
     return false;
 
-  /* Recognize && and || of two conditions with a common
-     then/else block which entry edges we can merge.  That is:
-       if (a || b)
-	 ;
-     and
-       if (a && b)
-	 ;
-     This requires a single predecessor of the inner cond_bb.  */
-  if (single_pred_p (inner_cond_bb))
+  last_inner_cond_bb = inner_cond_bb;
+  do
     {
-      basic_block outer_cond_bb = single_pred (inner_cond_bb);
+      /* Recognize && and || of two conditions with a common
+	 then/else block which entry edges we can merge.  That is:
+	   if (a || b)
+	     ;
+	 and
+	   if (a && b)
+	     ;
+	 This requires a single predecessor of the inner cond_bb.  */
+      if (!single_pred_p (last_inner_cond_bb))
+	return false;
+
+      outer_cond_bb = single_pred (last_inner_cond_bb);
+      outer_else_bb = NULL;
+      outer_then_bb = NULL;
+
+      if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+				   &outer_else_bb))
+	return false;
+
+      /* Check that last_inner_cond_bb doesn't have side-effects.  */
+      if (last_inner_cond_bb != inner_cond_bb
+          && !bb_no_side_effects_p (last_inner_cond_bb))
+	return false;
 
       /* The && form is characterized by a common else_bb with
 	 the two edges leading to it mergable.  The latter is
 	 guaranteed by matching PHI arguments in the else_bb and
 	 the inner cond_bb having no side-effects.  */
-      if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
-	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
+      if (last_inner_cond_bb == outer_then_bb
+	  && ((else_bb == outer_else_bb
+	       && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb))
+	      || (outer_else_bb == then_bb
+		  && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					 outer_else_bb, then_bb)
+		  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					outer_else_bb, else_bb)))
 	  && bb_no_side_effects_p (inner_cond_bb))
 	{
+	  excond = last_stmt (inner_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND
+	      || gimple_cond_true_p (excond))
+	    return false;
+
+	  excond = last_stmt (outer_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND)
+	    return false;
+
+	  if (gimple_cond_true_p (excond))
+	    {
+	      last_inner_cond_bb = outer_cond_bb;
+	      continue;
+	    }
+	  else if (gimple_cond_false_p (excond))
+	    return false;
+
+	  if (in_or_seq)
+	    return false;
+
 	  /* We have
 	       <outer_cond_bb>
-		 if (q) goto inner_cond_bb; else goto else_bb;
+		 if (q) goto inner_cond_bb; else goto outer_else_bb;
 	       <inner_cond_bb>
 		 if (p) goto ...; else goto else_bb;
 		 ...
 	       <else_bb>
+	       <outer_else_bb>
 		 ...
-	   */
-	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+	     If the else_bb,is not equal to outer_else_bb, then the
+	     else_bb needs to be empty (no PHIs, no statments) and
+	     and the PHI in outer_else_bb for else_bb has to be the
+	     same value as PHI value for outer_else_bb.  */
+	  if (ifcombine_ifandif (inner_cond_bb, outer_cond_bb))
+	    return true;
+	  in_and_seq = true;
+	  last_inner_cond_bb = outer_cond_bb;
+	  continue;
 	}
 
       /* The || form is characterized by a common then_bb with the
 	 two edges leading to it mergable.  The latter is guaranteed
-         by matching PHI arguments in the then_bb and the inner cond_bb
+	 by matching PHI arguments in the then_bb and the inner cond_bb
 	 having no side-effects.  */
-      if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
-	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
+      if (last_inner_cond_bb == outer_else_bb
+	  && ((then_bb == outer_then_bb
+	       && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb))
+	      || (outer_then_bb == else_bb
+		  && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					 outer_then_bb, else_bb)
+		  && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+					outer_then_bb, then_bb)))
 	  && bb_no_side_effects_p (inner_cond_bb))
 	{
+	  excond = last_stmt (inner_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND
+	      || gimple_cond_false_p (excond))
+	    return false;
+
+	  excond = last_stmt (outer_cond_bb);
+	  if (!excond || gimple_code (excond) != GIMPLE_COND)
+	    return false;
+
+	  if (gimple_cond_false_p (excond))
+	    {
+	      last_inner_cond_bb = outer_cond_bb;
+	      continue;
+	    }
+	  else if (gimple_cond_true_p (excond))
+	    return false;
+
+	  if (in_and_seq)
+	    return false;
+
 	  /* We have
 	       <outer_cond_bb>
-		 if (q) goto then_bb; else goto inner_cond_bb;
+		 if (q) goto outer_then_bb; else goto inner_cond_bb;
 	       <inner_cond_bb>
 		 if (q) goto then_bb; else goto ...;
 	       <then_bb>
+	       <outer-then_bb>
 		 ...
-	   */
-	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
+	     If the then_bb,is not equal to outer_then_bb, then the
+	     then_bb needs to be empty (no PHIs, no statments) and
+	     the PHI in outer_then_bb for then_bb has to be the same value
+	     as PHI value for outer_then_bb.  */
+	  if (ifcombine_iforif (inner_cond_bb, outer_cond_bb))
+	    return true;
+
+	  in_or_seq = true;
+	  last_inner_cond_bb = outer_cond_bb;
+	  continue;
 	}
     }
+  while (0);
 
   return false;
 }
@@ -627,6 +1187,7 @@  tree_ssa_ifcombine (void)
   bbs = blocks_in_phiopt_order ();
   calculate_dominance_info (CDI_DOMINATORS);
 
+  /* Try to optimize if.and/or.if conditions.  */
   for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
     {
       basic_block bb = bbs[i];
@@ -634,7 +1195,27 @@  tree_ssa_ifcombine (void)
 
       if (stmt
 	  && gimple_code (stmt) == GIMPLE_COND)
-	cfg_changed |= tree_ssa_ifcombine_bb (bb);
+	{
+	  if (tree_ssa_ifcombine_bb (bb))
+	    {
+	      cfg_changed = true;
+	      --i;
+	    }
+	}
+    }
+
+  /* Try to merge if.and/or.if chains.  */
+  for (i = n_basic_blocks - NUM_FIXED_BLOCKS; i > 0; --i)
+    {
+      basic_block bb = bbs[i-1];
+      gimple stmt = last_stmt (bb);
+
+      if (stmt
+	  && gimple_code (stmt) == GIMPLE_COND)
+	{
+	  if (tree_ssa_ifmerge_bb (bb))
+	    cfg_changed = true;
+	}
     }
 
   free (bbs);