re PR tree-optimization/51938 (missed optimization: 2 comparisons)

2012-08-06 Marc Glisse <marc.glisse@inria.fr>

gcc/
	PR tree-optimization/51938
	PR tree-optimization/52005
	* tree-ssa-ifcombine.c (ifcombine_ifandif): New parameters for
	inverted conditions.
	(ifcombine_iforif): Remove, merge code into ifcombine_ifandif.
	(tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b
	and !a||b patterns.

gcc/testsuite/
	PR tree-optimization/51938
	PR tree-optimization/52005
	* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
	* gcc.dg/tree-ssa/ssa-ifcombine-9.c: Likewise.
	* gcc.dg/tree-ssa/ssa-ifcombine-10.c: Likewise.
	* gcc.dg/tree-ssa/ssa-ifcombine-11.c: Likewise.

From-SVN: r190184

7 files changed, 193 insertions, 84 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ce6b4e9..26e3e0f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2012-08-06  Marc Glisse  <marc.glisse@inria.fr>
+
+	PR tree-optimization/51938
+	PR tree-optimization/52005
+	* tree-ssa-ifcombine.c (ifcombine_ifandif): New parameters for
+	inverted conditions.
+	(ifcombine_iforif): Remove, merge code into ifcombine_ifandif.
+	(tree_ssa_ifcombine_bb): Update calls to the above. Detect !a&&b
+	and !a||b patterns.
+
 2012-08-06  Olivier Hainque  <hainque@adacore.com>
 
 	* tree-emutls.c (new_emutls_decl): When a var_section is requested by
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index cca64c4..ff22fbf 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,12 @@
+2012-08-06  Marc Glisse  <marc.glisse@inria.fr>
+
+	PR tree-optimization/51938
+	PR tree-optimization/52005
+	* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New testcase.
+	* gcc.dg/tree-ssa/ssa-ifcombine-9.c: Likewise.
+	* gcc.dg/tree-ssa/ssa-ifcombine-10.c: Likewise.
+	* gcc.dg/tree-ssa/ssa-ifcombine-11.c: Likewise.
+
 2012-08-06  Dodji Seketeli  <dodji@redhat.com>
 
 	Avoid crashing on erroneous static_assert usage
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
new file mode 100644
index 0000000..c2b1c19
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+/* Testcase for PR31657.  */
+
+int f(int x, int a, int b)
+{
+  int t = 0;
+  int c = 1 << a;
+  if (!(x & 1))
+    t = 0;
+  else
+    if (x & (1 << 2))
+      t = 3;
+    else
+      t = 0;
+  return t;
+}
+/* { dg-final { scan-tree-dump "& 5" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
new file mode 100644
index 0000000..d024df8
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+/* Testcase for PR31657.  */
+int g(void);
+int f(int x, int a, int b)
+{
+  int t = 0;
+  int c = 1 << a;
+  if (!(x & 1))
+    t = 0;
+  else
+    if (x & (1 << 2))
+      t = g();
+    else
+      t = 0;
+  return t;
+}
+
+/* { dg-final { scan-tree-dump "& 5" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
new file mode 100644
index 0000000..a6c4282
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fno-trapping-math -fdump-tree-ifcombine" } */
+
+double test1 (double i, double j)
+{
+  if (i >= j)
+    if (i <= j)
+      goto plif;
+    else
+      goto plouf;
+  else
+    goto plif;
+
+plif:
+  return 0;
+plouf:
+  return -1;
+}
+
+/* The above should be optimized to a i > j test by ifcombine.
+   The transformation would also be legal with -ftrapping-math.
+   Instead we get u<=, which is acceptable with -fno-trapping-math.  */
+
+/* { dg-final { scan-tree-dump " u<= " "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
new file mode 100644
index 0000000..cb57502
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-trapping-math -fdump-tree-ifcombine" } */
+
+void f ();
+enum Sign { NEG=-1, ZERO, POS };
+
+static inline enum Sign sign (double x)
+{
+  if (x > 0) return POS;
+  if (x < 0) return NEG;
+  return ZERO;
+}
+void g (double x)
+{
+  if (sign (x) == NEG) f();
+}
+
+/* The above should be optimized to x < 0 by ifcombine.
+   The transformation would also be legal with -ftrapping-math.  */
+
+/* { dg-final { scan-tree-dump "optimizing.* < " "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
diff --git a/gcc/tree-ssa-ifcombine.c b/gcc/tree-ssa-ifcombine.c
index f769d02..5c61f7f 100644
--- a/gcc/tree-ssa-ifcombine.c
+++ b/gcc/tree-ssa-ifcombine.c
@@ -166,12 +166,12 @@ get_name_for_bit_test (tree candidate)
    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 inv)
 {
   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) != (inv ? EQ_EXPR : NE_EXPR)
       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
       || !integer_zerop (gimple_cond_rhs (cond)))
     return false;
@@ -274,12 +274,12 @@ recognize_single_bit_test (gimple cond, tree *name, tree *bit)
    Returns true if the pattern matched, false otherwise.  */
 
 static bool
-recognize_bits_test (gimple cond, tree *name, tree *bits)
+recognize_bits_test (gimple cond, tree *name, tree *bits, bool inv)
 {
   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) != (inv ? EQ_EXPR : NE_EXPR)
       || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
       || !integer_zerop (gimple_cond_rhs (cond)))
     return false;
@@ -296,14 +296,17 @@ recognize_bits_test (gimple cond, tree *name, tree *bits)
 
 /* 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.
+   inner_inv, outer_inv and result_inv indicate whether the conditions
+   are inverted.
    Returns true if the edges to the common else basic-block were merged.  */
 
 static bool
-ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
+ifcombine_ifandif (basic_block inner_cond_bb, bool inner_inv,
+		   basic_block outer_cond_bb, bool outer_inv, bool result_inv)
 {
   gimple_stmt_iterator gsi;
   gimple inner_cond, outer_cond;
-  tree name1, name2, bit1, bit2;
+  tree name1, name2, bit1, bit2, bits1, bits2;
 
   inner_cond = last_stmt (inner_cond_bb);
   if (!inner_cond
@@ -319,8 +322,8 @@ ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
      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, inner_inv)
+      && recognize_single_bit_test (outer_cond, &name2, &bit2, outer_inv)
       && name1 == name2)
     {
       tree t, t2;
@@ -337,7 +340,8 @@ ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       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 = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR,
+		       boolean_type_node, t2, t);
       t = canonicalize_cond_expr_cond (t);
       if (!t)
 	return false;
@@ -345,7 +349,8 @@ ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       update_stmt (inner_cond);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
+      gimple_cond_set_condition_from_tree (outer_cond,
+	outer_inv ? boolean_false_node : boolean_true_node);
       update_stmt (outer_cond);
 
       if (dump_file)
@@ -362,68 +367,11 @@ ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       return true;
     }
 
-  /* See if we have two comparisons that we can merge into one.  */
-  else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
-	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
-    {
-      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);
-      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 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.  */
-
-static bool
-ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
-{
-  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
      test for name & (bits1 | bits2) != 0.  */
-  if (recognize_bits_test (inner_cond, &name1, &bits1)
-      && recognize_bits_test (outer_cond, &name2, &bits2))
+  else if (recognize_bits_test (inner_cond, &name1, &bits1, !inner_inv)
+      && recognize_bits_test (outer_cond, &name2, &bits2, !outer_inv))
     {
       gimple_stmt_iterator gsi;
       tree t;
@@ -482,7 +430,7 @@ ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
       t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
 				    true, GSI_SAME_STMT);
-      t = fold_build2 (NE_EXPR, boolean_type_node, t,
+      t = fold_build2 (result_inv ? NE_EXPR : EQ_EXPR, boolean_type_node, t,
 		       build_int_cst (TREE_TYPE (t), 0));
       t = canonicalize_cond_expr_cond (t);
       if (!t)
@@ -491,7 +439,8 @@ ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       update_stmt (inner_cond);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
+      gimple_cond_set_condition_from_tree (outer_cond,
+	outer_inv ? boolean_false_node : boolean_true_node);
       update_stmt (outer_cond);
 
       if (dump_file)
@@ -508,21 +457,36 @@ ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       return true;
     }
 
-  /* See if we have two comparisons that we can merge into one.
-     This happens for C++ operator overloading where for example
-     GE_EXPR is implemented as GT_EXPR || EQ_EXPR.  */
-    else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+  /* See if we have two comparisons that we can merge into one.  */
+  else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
 	   && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
     {
       tree t;
+      enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
+      enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
+
+      /* Invert comparisons if necessary (and possible).  */
+      if (inner_inv)
+	inner_cond_code = invert_tree_comparison (inner_cond_code,
+	  HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (inner_cond)))));
+      if (inner_cond_code == ERROR_MARK)
+	return false;
+      if (outer_inv)
+	outer_cond_code = invert_tree_comparison (outer_cond_code,
+	  HONOR_NANS (TYPE_MODE (TREE_TYPE (gimple_cond_lhs (outer_cond)))));
+      if (outer_cond_code == ERROR_MARK)
+	return false;
+      /* Don't return false so fast, try maybe_fold_or_comparisons?  */
 
-      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))))
+      if (!(t = maybe_fold_and_comparisons (inner_cond_code,
+					    gimple_cond_lhs (inner_cond),
+					    gimple_cond_rhs (inner_cond),
+					    outer_cond_code,
+					    gimple_cond_lhs (outer_cond),
+					    gimple_cond_rhs (outer_cond))))
 	return false;
+      if (result_inv)
+	t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
       t = canonicalize_cond_expr_cond (t);
       if (!t)
 	return false;
@@ -530,7 +494,8 @@ ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
       update_stmt (inner_cond);
 
       /* Leave CFG optimization to cfg_cleanup.  */
-      gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
+      gimple_cond_set_condition_from_tree (outer_cond,
+	outer_inv ? boolean_false_node : boolean_true_node);
       update_stmt (outer_cond);
 
       if (dump_file)
@@ -587,7 +552,26 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 	       <else_bb>
 		 ...
 	   */
-	  return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+	  return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false,
+				    false);
+	}
+
+      /* And a version where the outer condition is negated.  */
+      if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
+	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
+	  && bb_no_side_effects_p (inner_cond_bb))
+	{
+	  /* We have
+	       <outer_cond_bb>
+		 if (q) goto else_bb; else goto inner_cond_bb;
+	       <inner_cond_bb>
+		 if (p) goto ...; else goto else_bb;
+		 ...
+	       <else_bb>
+		 ...
+	   */
+	  return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true,
+				    false);
 	}
 
       /* The || form is characterized by a common then_bb with the
@@ -606,7 +590,25 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
 	       <then_bb>
 		 ...
 	   */
-	  return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
+	  return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true,
+				    true);
+	}
+
+      /* And a version where the outer condition is negated.  */
+      if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
+	  && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
+	  && bb_no_side_effects_p (inner_cond_bb))
+	{
+	  /* We have
+	       <outer_cond_bb>
+		 if (q) goto inner_cond_bb; else goto then_bb;
+	       <inner_cond_bb>
+		 if (q) goto then_bb; else goto ...;
+	       <then_bb>
+		 ...
+	   */
+	  return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false,
+				    true);
 	}
     }