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

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);