On Tue, Jun 09, 2015 at 09:53:21AM +0200, Richard Biener wrote:
> >> +/* (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 {
> >> + unsigned int cand = wi::ctz (@2) - wi::ctz (@0); }
> >> + (if (!integer_zerop (@2)
> >
> >
> > You can probably use directly wi::ne_p (@2, 0) here. Shouldn't this be
> > indented one space more?
>
> Yes, one space more. I suppose using integer_zerop might in theory
> allow for handling vector shifts at some point ...?
Fixed the formatting. But I kept the integer_zerop.
> >> + && wi::eq_p (wi::lshift (@0, cand), @2))
> >> + (cmp @1 { build_int_cst (TREE_TYPE (@1), cand); })))))
> >
> >
> > Making 'cand' signed, you could return 0 when cand<0, like (2<<x)==1. You
> > could also return 0 when the candidate turns out not to work: (3<<x)==4.
>
> Sounds like a good improvement.
Yeah, it makes sense to do that while I'm on this. Done, and a new
test added.
> Otherwise the patch looks ok to me as well - mind doing the improvement above?
Thank you both. How does this look now?
Bootstrapped/regtested on x86_64-linux, ok for trunk?
2015-06-09 Marek Polacek <pola...@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.
* gcc.dg/pr66299-1.c: New test.
* gcc.dg/pr66299-2.c: New test.
* gcc.dg/pr66299-3.c: New test.
diff --git gcc/match.pd gcc/match.pd
index abd7851..560b218 100644
--- gcc/match.pd
+++ gcc/match.pd
@@ -676,6 +676,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 gcc/testsuite/gcc.dg/pr66299-1.c gcc/testsuite/gcc.dg/pr66299-1.c
index e69de29..e75146b 100644
--- gcc/testsuite/gcc.dg/pr66299-1.c
+++ 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 gcc/testsuite/gcc.dg/pr66299-2.c gcc/testsuite/gcc.dg/pr66299-2.c
index e69de29..45e9218 100644
--- gcc/testsuite/gcc.dg/pr66299-2.c
+++ 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 gcc/testsuite/gcc.dg/pr66299-3.c gcc/testsuite/gcc.dg/pr66299-3.c
index e69de29..ffee049 100644
--- gcc/testsuite/gcc.dg/pr66299-3.c
+++ 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" } } */
Marek
