tree-ssa-reassoc.c: Include rtl.h and tm_p.h.

	* tree-ssa-reassoc.c: Include rtl.h and tm_p.h.
	(optimize_range_tests_1): New function,
	extracted from optimize_range_tests.
	(optimize_range_tests_xor): Similarly.
	(optimize_range_tests_diff): New function.
	(optimize_range_tests): Use optimize_range_tests_1.

	* gcc.dg/tree-ssa/reassoc-32.c: New test case.
	* gcc.dg/tree-ssa/reassoc-33.c: New test case.
	* gcc.dg/tree-ssa/reassoc-34.c: New test case.
	* gcc.dg/tree-ssa/reassoc-35.c: New test case.
	* gcc.dg/tree-ssa/reassoc-36.c: New test case.

From-SVN: r203627

8 files changed, 301 insertions, 69 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7a7033a..dd10a5f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2013-10-15  Zhenqiang Chen  <zhenqiang.chen@arm.com>
+
+	* tree-ssa-reassoc.c: Include rtl.h and tm_p.h.
+	(optimize_range_tests_1): New function,
+	extracted from optimize_range_tests.
+	(optimize_range_tests_xor): Similarly.
+	(optimize_range_tests_diff): New function.
+	(optimize_range_tests): Use optimize_range_tests_1.
+
 2013-10-15  Cong Hou  <congh@google.com>
 
 	* tree-vect-loop.c (vect_is_simple_reduction_1): Relax the 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index eb5eea2..d59cc4f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,11 @@
+2013-10-15  Zhenqiang Chen  <zhenqiang.chen@arm.com>
+
+	* gcc.dg/tree-ssa/reassoc-32.c: New test case.
+	* gcc.dg/tree-ssa/reassoc-33.c: New test case.
+	* gcc.dg/tree-ssa/reassoc-34.c: New test case.
+	* gcc.dg/tree-ssa/reassoc-35.c: New test case.
+	* gcc.dg/tree-ssa/reassoc-36.c: New test case.
+
 2013-10-15  Cong Hou  <congh@google.com>
 
 	* gcc.dg/vect/vect-reduc-pattern-3.c: New test.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
new file mode 100644
index 0000000..303b3f3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -0,0 +1,29 @@
+/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+
+int test (int a, int b, int c)
+{
+  if ( a == 10 || a == 12 || a == 26)
+    return b;
+  else
+    return c;
+}
+
+int main ()
+{
+  if (test (10, 20, 30) != 20)
+    __builtin_abort ();
+  if (test (12, 20, 30) != 20)
+    __builtin_abort ();
+  if (test (26, 20, 30) != 20)
+    __builtin_abort ();
+  if (test (30, 20, 30) != 30)
+    __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests .* 26" 1 "reassoc1"} }*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
new file mode 100644
index 0000000..bb27daa
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-33.c
@@ -0,0 +1,27 @@
+/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int test (int a, int b, int c)
+{
+  if (a == 43 || a == 75 || a == 44 || a == 78
+      || a == 77 || a == 46 || a == 76 || a == 45)
+    return b;
+  else
+    return c;
+}
+
+int
+main ()
+{
+  volatile int n43, n47, n75, n79;
+  n43 = 43; n47 = n43 + 4; n75 = 75; n79 = n75 + 4;
+  int i;
+  for (i = -10; i <= 100; i++)
+    if (test (i, 2, 3) != 3 - ((i >= n43 && i < n47) || (i >= n75 && i < n79)))
+      __builtin_abort ();
+  return 0;
+}
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 3 "reassoc1"} }*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c
new file mode 100644
index 0000000..156e182
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-34.c
@@ -0,0 +1,24 @@
+/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int test (int a, int b, int c)
+{
+  if (a == 10 || a == 12)
+    return b;
+  else
+    return c;
+}
+int main ()
+{
+  if (test (10, 20, 30) != 20)
+    __builtin_abort ();
+  if (test (12, 20, 30) != 20)
+    __builtin_abort ();
+  if (test (26, 20, 30) != 30)
+    __builtin_abort ();
+  return 0;
+}
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 1 "reassoc1"} }*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c
new file mode 100644
index 0000000..c486b78
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-35.c
@@ -0,0 +1,26 @@
+/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int test (unsigned int a, int b, int c)
+{
+  if ((a - 43) <= 3 || (a - 75) <= 3)
+    return b;
+  else
+    return c;
+}
+int
+main ()
+{
+  volatile int n43, n47, n75, n79;
+  n43 = 43; n47 = n43 + 4; n75 = 75; n79 = n75 + 4;
+  int i;
+  for (i = -10; i <= 100; i++)
+    if (test (i, 2, 3) != 3 - ((i >= n43 && i < n47) || (i >= n75 && i < n79)))
+      __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 1 "reassoc1"} }*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-36.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-36.c
new file mode 100644
index 0000000..930dbe2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-36.c
@@ -0,0 +1,25 @@
+/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* mep*-*-* bfin*-*-* v850*-*-* picochip*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
+
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details" } */
+/* { dg-additional-options "-mbranch-cost=2" { target avr-*-* } } */
+
+int test (int a, int b, int c)
+{
+  if (a != 10 && a != 12)
+    return b;
+  else
+    return c;
+}
+int main ()
+{
+  if (test (10, 20, 30) != 30)
+    __builtin_abort ();
+  if (test (12, 20, 30) != 30)
+    __builtin_abort ();
+  if (test (26, 20, 30) != 20)
+    __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests" 1 "reassoc1"} }*/
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 6859518..17541c6 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -23,6 +23,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "hash-table.h"
 #include "tm.h"
+#include "rtl.h"
+#include "tm_p.h"
 #include "tree.h"
 #include "basic-block.h"
 #include "gimple-pretty-print.h"
@@ -2131,6 +2133,152 @@ update_range_test (struct range_entry *range, struct range_entry *otherrange,
   return true;
 }
 
+/* Optimize X == CST1 || X == CST2
+   if popcount (CST1 ^ CST2) == 1 into
+   (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
+   Similarly for ranges.  E.g.
+   X != 2 && X != 3 && X != 10 && X != 11
+   will be transformed by the previous optimization into
+   !((X - 2U) <= 1U || (X - 10U) <= 1U)
+   and this loop can transform that into
+   !(((X & ~8) - 2U) <= 1U).  */
+
+static bool
+optimize_range_tests_xor (enum tree_code opcode, tree type,
+			  tree lowi, tree lowj, tree highi, tree highj,
+			  vec<operand_entry_t> *ops,
+			  struct range_entry *rangei,
+			  struct range_entry *rangej)
+{
+  tree lowxor, highxor, tem, exp;
+  /* Check highi ^ lowi == highj ^ lowj and
+     popcount (highi ^ lowi) == 1.  */
+  lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
+  if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
+    return false;
+  if (tree_log2 (lowxor) < 0)
+    return false;
+  highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj);
+  if (!tree_int_cst_equal (lowxor, highxor))
+    return false;
+
+  tem = fold_build1 (BIT_NOT_EXPR, type, lowxor);
+  exp = fold_build2 (BIT_AND_EXPR, type, rangei->exp, tem);
+  lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
+  highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
+  if (update_range_test (rangei, rangej, 1, opcode, ops, exp,
+			 rangei->in_p, lowj, highj,
+			 rangei->strict_overflow_p
+			 || rangej->strict_overflow_p))
+    return true;
+  return false;
+}
+
+/* Optimize X == CST1 || X == CST2
+   if popcount (CST2 - CST1) == 1 into
+   ((X - CST1) & ~(CST2 - CST1)) == 0.
+   Similarly for ranges.  E.g.
+   X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X == 46
+   || X == 75 || X == 45
+   will be transformed by the previous optimization into
+   (X - 43U) <= 3U || (X - 75U) <= 3U
+   and this loop can transform that into
+   ((X - 43U) & ~(75U - 43U)) <= 3U.  */
+static bool
+optimize_range_tests_diff (enum tree_code opcode, tree type,
+			    tree lowi, tree lowj, tree highi, tree highj,
+			    vec<operand_entry_t> *ops,
+			    struct range_entry *rangei,
+			    struct range_entry *rangej)
+{
+  tree tem1, tem2, mask;
+  /* Check highi - lowi == highj - lowj.  */
+  tem1 = fold_binary (MINUS_EXPR, type, highi, lowi);
+  if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
+    return false;
+  tem2 = fold_binary (MINUS_EXPR, type, highj, lowj);
+  if (!tree_int_cst_equal (tem1, tem2))
+    return false;
+  /* Check popcount (lowj - lowi) == 1.  */
+  tem1 = fold_binary (MINUS_EXPR, type, lowj, lowi);
+  if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
+    return false;
+  if (tree_log2 (tem1) < 0)
+    return false;
+
+  mask = fold_build1 (BIT_NOT_EXPR, type, tem1);
+  tem1 = fold_binary (MINUS_EXPR, type, rangei->exp, lowi);
+  tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
+  lowj = build_int_cst (type, 0);
+  if (update_range_test (rangei, rangej, 1, opcode, ops, tem1,
+			 rangei->in_p, lowj, tem2,
+			 rangei->strict_overflow_p
+			 || rangej->strict_overflow_p))
+    return true;
+  return false;
+}
+
+/* It does some common checks for function optimize_range_tests_xor and
+   optimize_range_tests_diff.
+   If OPTIMIZE_XOR is TRUE, it calls optimize_range_tests_xor.
+   Else it calls optimize_range_tests_diff.  */
+
+static bool
+optimize_range_tests_1 (enum tree_code opcode, int first, int length,
+			bool optimize_xor, vec<operand_entry_t> *ops,
+			struct range_entry *ranges)
+{
+  int i, j;
+  bool any_changes = false;
+  for (i = first; i < length; i++)
+    {
+      tree lowi, highi, lowj, highj, type, tem;
+
+      if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
+	continue;
+      type = TREE_TYPE (ranges[i].exp);
+      if (!INTEGRAL_TYPE_P (type))
+	continue;
+      lowi = ranges[i].low;
+      if (lowi == NULL_TREE)
+	lowi = TYPE_MIN_VALUE (type);
+      highi = ranges[i].high;
+      if (highi == NULL_TREE)
+	continue;
+      for (j = i + 1; j < length && j < i + 64; j++)
+	{
+	  bool changes;
+	  if (ranges[i].exp != ranges[j].exp || ranges[j].in_p)
+	    continue;
+	  lowj = ranges[j].low;
+	  if (lowj == NULL_TREE)
+	    continue;
+	  highj = ranges[j].high;
+	  if (highj == NULL_TREE)
+	    highj = TYPE_MAX_VALUE (type);
+	  /* Check lowj > highi.  */
+	  tem = fold_binary (GT_EXPR, boolean_type_node,
+			     lowj, highi);
+	  if (tem == NULL_TREE || !integer_onep (tem))
+	    continue;
+	  if (optimize_xor)
+	    changes = optimize_range_tests_xor (opcode, type, lowi, lowj,
+						highi, highj, ops,
+						ranges + i, ranges + j);
+	  else
+	    changes = optimize_range_tests_diff (opcode, type, lowi, lowj,
+						 highi, highj, ops,
+						 ranges + i, ranges + j);
+	  if (changes)
+	    {
+	      any_changes = true;
+	      break;
+	    }
+	}
+    }
+  return any_changes;
+}
+
 /* Optimize range tests, similarly how fold_range_test optimizes
    it on trees.  The tree code for the binary
    operation between all the operands is OPCODE.
@@ -2208,76 +2356,12 @@ optimize_range_tests (enum tree_code opcode,
 	++update_fail_count;
     }
 
-  /* Optimize X == CST1 || X == CST2
-     if popcount (CST1 ^ CST2) == 1 into
-     (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
-     Similarly for ranges.  E.g.
-     X != 2 && X != 3 && X != 10 && X != 11
-     will be transformed by the above loop into
-     (X - 2U) <= 1U && (X - 10U) <= 1U
-     and this loop can transform that into
-     ((X & ~8) - 2U) <= 1U.  */
-  for (i = first; i < length; i++)
-    {
-      tree lowi, highi, lowj, highj, type, lowxor, highxor, tem, exp;
+  any_changes |= optimize_range_tests_1 (opcode, first, length, true,
+					 ops, ranges);
 
-      if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
-	continue;
-      type = TREE_TYPE (ranges[i].exp);
-      if (!INTEGRAL_TYPE_P (type))
-	continue;
-      lowi = ranges[i].low;
-      if (lowi == NULL_TREE)
-	lowi = TYPE_MIN_VALUE (type);
-      highi = ranges[i].high;
-      if (highi == NULL_TREE)
-	continue;
-      for (j = i + 1; j < length && j < i + 64; j++)
-	{
-	  if (ranges[j].exp == NULL_TREE)
-	    continue;
-	  if (ranges[i].exp != ranges[j].exp)
-	    break;
-	  if (ranges[j].in_p)
-	    continue;
-	  lowj = ranges[j].low;
-	  if (lowj == NULL_TREE)
-	    continue;
-	  highj = ranges[j].high;
-	  if (highj == NULL_TREE)
-	    highj = TYPE_MAX_VALUE (type);
-	  tem = fold_binary (GT_EXPR, boolean_type_node,
-			     lowj, highi);
-	  if (tem == NULL_TREE || !integer_onep (tem))
-	    continue;
-	  lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
-	  if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
-	    continue;
-	  gcc_checking_assert (!integer_zerop (lowxor));
-	  tem = fold_binary (MINUS_EXPR, type, lowxor,
-			     build_int_cst (type, 1));
-	  if (tem == NULL_TREE)
-	    continue;
-	  tem = fold_binary (BIT_AND_EXPR, type, lowxor, tem);
-	  if (tem == NULL_TREE || !integer_zerop (tem))
-	    continue;
-	  highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj);
-	  if (!tree_int_cst_equal (lowxor, highxor))
-	    continue;
-	  tem = fold_build1 (BIT_NOT_EXPR, type, lowxor);
-	  exp = fold_build2 (BIT_AND_EXPR, type, ranges[i].exp, tem);
-	  lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
-	  highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
-	  if (update_range_test (ranges + i, ranges + j, 1, opcode, ops, exp,
-				 ranges[i].in_p, lowj, highj,
-				 ranges[i].strict_overflow_p
-				 || ranges[j].strict_overflow_p))
-	    {
-	      any_changes = true;
-	      break;
-	    }
-	}
-    }
+  if (BRANCH_COST (optimize_function_for_speed_p (cfun), false) >= 2)
+    any_changes |= optimize_range_tests_1 (opcode, first, length, false,
+					   ops, ranges);
 
   if (any_changes && opcode != ERROR_MARK)
     {