[PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299)
Richard Biener
rguenther@suse.de
Tue Jun 9 14:11:00 GMT 2015
On Tue, 9 Jun 2015, Marek Polacek wrote:
> 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?
Ok.
Thanks,
Richard.
> 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.
>
> * 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
>
>
--
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Dilip Upmanyu, Graham Norton, HRB 21284 (AG Nuernberg)
More information about the Gcc-patches
mailing list