re PR tree-optimization/66299 (more optimize opportunity)

	PR tree-optimization/66299
	* match.pd ((CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
	((CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)): New
	patterns.

	* gcc.dg/pr66299-1.c: New test.
	* gcc.dg/pr66299-2.c: New test.
	* gcc.dg/pr66299-3.c: New test.

From-SVN: r224283

6 files changed, 222 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4eed107..b1788a0 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2015-06-09  Marek Polacek  <polacek@redhat.com>
+
+	PR tree-optimization/66299
+	* match.pd ((CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
+	((CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)): New
+	patterns.
+
 2015-06-09  Richard Biener  <rguenther@suse.de>
 
 	* tree-vect-slp.c (vect_build_slp_tree_1): Remove bailout on gaps.
diff --git a/gcc/match.pd b/gcc/match.pd
index 48a3047..48358a8 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -677,6 +677,21 @@ along with GCC; see the file COPYING3.  If not see
   (cmp (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
   (icmp @0 { build_zero_cst (TREE_TYPE (@0)); })))
 
+/* (CST1 << A) == CST2 -> A == ctz (CST2) - ctz (CST1)
+   (CST1 << A) != CST2 -> A != ctz (CST2) - ctz (CST1)
+   if CST2 != 0.  */
+(for cmp (ne eq)
+ (simplify
+  (cmp (lshift INTEGER_CST@0 @1) INTEGER_CST@2)
+  (with { int cand = wi::ctz (@2) - wi::ctz (@0); }
+   (if (cand < 0
+	|| (!integer_zerop (@2)
+	    && wi::ne_p (wi::lshift (@0, cand), @2)))
+    { constant_boolean_node (cmp == NE_EXPR, type); })
+   (if (!integer_zerop (@2)
+	&& wi::eq_p (wi::lshift (@0, cand), @2))
+    (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); })))))
+
 /* Simplifications of conversions.  */
 
 /* Basic strip-useless-type-conversions / strip_nops.  */
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 2f91430..737dfad 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2015-06-09  Marek Polacek  <polacek@redhat.com>
+
+	PR tree-optimization/66299
+	* gcc.dg/pr66299-1.c: New test.
+	* gcc.dg/pr66299-2.c: New test.
+	* gcc.dg/pr66299-3.c: New test.
+
 2015-06-09  James Greenhalgh  <james.greenhalgh@arm.com>
 
 	* g++.dg/ext/pr57735.C: Do not override -mfloat-abi directives
diff --git a/gcc/testsuite/gcc.dg/pr66299-1.c b/gcc/testsuite/gcc.dg/pr66299-1.c
new file mode 100644
index 0000000..e75146b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr66299-1.c
@@ -0,0 +1,92 @@
+/* PR tree-optimization/66299 */
+/* { dg-do run } */
+/* { dg-options "-fdump-tree-original" } */
+
+void
+test1 (int x)
+{
+  if ((0 << x) != 0
+      || (1 << x) != 2
+      || (2 << x) != 4
+      || (3 << x) != 6
+      || (4 << x) != 8
+      || (5 << x) != 10
+      || (6 << x) != 12
+      || (7 << x) != 14
+      || (8 << x) != 16
+      || (9 << x) != 18
+      || (10 << x) != 20)
+    __builtin_abort ();
+}
+
+void
+test2 (int x)
+{
+  if (!((0 << x) == 0
+	&& (1 << x) == 4
+	&& (2 << x) == 8
+	&& (3 << x) == 12
+	&& (4 << x) == 16
+	&& (5 << x) == 20
+	&& (6 << x) == 24
+	&& (7 << x) == 28
+	&& (8 << x) == 32
+	&& (9 << x) == 36
+	&& (10 << x) == 40))
+    __builtin_abort ();
+}
+
+void
+test3 (unsigned int x)
+{
+  if ((0U << x) != 0U
+      || (1U << x) != 16U
+      || (2U << x) != 32U
+      || (3U << x) != 48U
+      || (4U << x) != 64U
+      || (5U << x) != 80U
+      || (6U << x) != 96U
+      || (7U << x) != 112U
+      || (8U << x) != 128U
+      || (9U << x) != 144U
+      || (10U << x) != 160U)
+    __builtin_abort ();
+}
+
+void
+test4 (unsigned int x)
+{
+  if (!((0U << x) == 0U
+	|| (1U << x) == 8U
+	|| (2U << x) == 16U
+	|| (3U << x) == 24U
+	|| (4U << x) == 32U
+	|| (5U << x) == 40U
+	|| (6U << x) == 48U
+	|| (7U << x) == 56U
+	|| (8U << x) == 64U
+	|| (9U << x) == 72U
+	|| (10U << x) == 80U))
+    __builtin_abort ();
+}
+
+void
+test5 (int x)
+{
+  if ((0 << x) == 1
+      || (0 << x) != 0
+      || (0x8001U << x) != 0x20000U)
+    __builtin_abort ();
+}
+
+int
+main (void)
+{
+  test1 (1);
+  test2 (2);
+  test3 (4U);
+  test4 (3U);
+  test5 (17);
+}
+
+/* { dg-final { scan-tree-dump-not "<<" "original" } } */
diff --git a/gcc/testsuite/gcc.dg/pr66299-2.c b/gcc/testsuite/gcc.dg/pr66299-2.c
new file mode 100644
index 0000000..45e9218
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr66299-2.c
@@ -0,0 +1,33 @@
+/* PR tree-optimization/66299 */
+/* { dg-do run } */
+/* { dg-options "-fdump-tree-optimized -O" } */
+
+void
+test1 (int x, unsigned u)
+{
+  if ((1U << x) != 64
+      || (2 << x) != u
+      || (x << x) != 384
+      || (3 << x) == 9
+      || (x << 14) != 98304U
+      || (1 << x) == 14
+      || (3 << 2) != 12)
+    __builtin_abort ();
+}
+
+void
+test2 (int x)
+{
+  unsigned int t = ((unsigned int) 1U << x);
+  if (t != 2U)
+    __builtin_abort ();
+}
+
+int
+main (void)
+{
+  test1 (6, 128U);
+  test2 (1);
+}
+
+/* { dg-final { scan-tree-dump-not "<<" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/pr66299-3.c b/gcc/testsuite/gcc.dg/pr66299-3.c
new file mode 100644
index 0000000..ffee049
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr66299-3.c
@@ -0,0 +1,68 @@
+/* PR tree-optimization/66299 */
+/* { dg-do run } */
+/* { dg-options "-fdump-tree-original" } */
+
+void __attribute__ ((noinline, noclone))
+test1 (int x)
+{
+  if ((2 << x) == 1
+      || (8 << x) == 1
+      || (8 << x) == 2
+      || (3072 << x) == 3
+      || (294912 << x) == 9
+      || (45056 << x) == 11
+      || (2176 << x) == 17)
+    __builtin_abort ();
+}
+
+void __attribute__ ((noinline, noclone))
+test2 (int x)
+{
+  if ((2 << x) != 1
+      && (8 << x) != 1
+      && (8 << x) != 2
+      && (3072 << x) != 3
+      && (294912 << x) != 9
+      && (45056 << x) != 11
+      && (2176 << x) != 17)
+    ;
+  else
+    __builtin_abort ();
+}
+
+void __attribute__ ((noinline, noclone))
+test3 (int x)
+{
+  if ((3 << x) == 4
+      || (1 << x) == 12
+      || (40 << x) == 1024
+      || (2 << x) == 84
+      || (3 << x) == 16384
+      || (10 << x) == 6144)
+    __builtin_abort ();
+}
+
+void __attribute__ ((noinline, noclone))
+test4 (int x)
+{
+  if ((3 << x) != 4
+      && (1 << x) != 12
+      && (40 << x) != 1024
+      && (2 << x) != 84
+      && (3 << x) != 16384
+      && (10 << x) != 6144)
+    ;
+  else
+    __builtin_abort ();
+}
+
+int
+main (void)
+{
+  test1 (0);
+  test2 (1);
+  test3 (1);
+  test4 (2);
+}
+
+/* { dg-final { scan-tree-dump-not "(<<|==|!=)" "original" } } */