From e2559c3945a09521ffe4f59669bc4d902ae77adb Mon Sep 17 00:00:00 2001
From: Jakub Jelinek <jakub@redhat.com>
Date: Sat, 16 Jan 2021 09:21:52 +0100
Subject: [PATCH] match.pd: Optimize ((cst << x) & 1) [PR96669]

While we had a ((1 << x) & 1) != 0 to x == 0 optimization already,
this patch adds ((cst << x) & 1) optimization too, this time the
second constant must be 1 though, not some power of two, but the first
one can be any constant.  If it is even, the result is false, if it is
odd, the result is x == 0.

2021-01-16  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/96669
	* match.pd ((CST << x) & 1 -> x == 0): New simplification.

	* gcc.dg/tree-ssa/pr96669-1.c: Adjust regexp.
	* gcc.dg/tree-ssa/pr96669-2.c: New test.
---
 gcc/match.pd                              |  7 ++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr96669-1.c |  2 +-
 gcc/testsuite/gcc.dg/tree-ssa/pr96669-2.c | 30 +++++++++++++++++++++++
 3 files changed, 38 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr96669-2.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 84c4ee66a79..7158e983d21 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -3117,6 +3117,13 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
       (op @0 { build_int_cst (TREE_TYPE (@1), low); })))))))
 
 
+/* Simplify (CST << x) & 1 to 0 if CST is even or to x == 0 if it is odd.  */
+(simplify
+ (bit_and (lshift INTEGER_CST@1 @0) integer_onep)
+  (if ((wi::to_wide (@1) & 1) != 0)
+   (convert (eq:boolean_type_node @0 { build_zero_cst (TREE_TYPE (@0)); }))
+   { build_zero_cst (type); }))
+
 /* Simplify ((C << x) & D) != 0 where C and D are power of two constants,
    either to false if D is smaller (unsigned comparison) than C, or to
    x == log2 (D) - log2 (C).  Similarly for right shifts.  */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr96669-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr96669-1.c
index a1efba76770..6a95a6ba8c1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr96669-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr96669-1.c
@@ -1,7 +1,7 @@
 /* PR tree-optimization/96669 */
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-original" } */
-/* { dg-final { scan-tree-dump "return a == 0;" "original" } } */
+/* { dg-final { scan-tree-dump "a == 0" "original" } } */
 /* { dg-final { scan-tree-dump "return 1;" "original" } } */
 /* { dg-final { scan-tree-dump "return c == 3;" "original" } } */
 /* { dg-final { scan-tree-dump "return d != 1;" "original" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr96669-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr96669-2.c
new file mode 100644
index 00000000000..47b885f769f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr96669-2.c
@@ -0,0 +1,30 @@
+/* PR tree-optimization/96669 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-original" } */
+/* { dg-final { scan-tree-dump "a == 0" "original" } } */
+/* { dg-final { scan-tree-dump-times "return 0;" 2 "original" } } */
+/* { dg-final { scan-tree-dump "c == 0" "original" } } */
+
+int
+f1 (int a)
+{
+  return ((1 << a) & 1);
+}
+
+int
+f2 (int b)
+{
+  return ((2 << b) & 1);
+}
+
+int
+f3 (int c)
+{
+  return ((35 << c) & 1);
+}
+
+int
+f4 (int d)
+{
+  return ((42 << d) & 1);
+}
-- 
2.30.2