On Thu, May 28, 2015 at 2:15 PM, Marek Polacek <pola...@redhat.com> wrote:
> This PR points out that we weren't able to optimize 1 << x == 2 to just
> x == 1. This is my attempt to fix that: if we see (CST1 << A) == CST2
> and CST2 is a multiple of CST1, use log2 to get rid of the shift, but
> only if the result of the shift is a natural number (including zero).
>
> If CST2 is not a multiple of CST1, then the whole expression can be
> discarded, but I'd like to do that as a follow-up.
> (It would help if our current match.pd grammar allowed us to use "else",
> any plans on doing that?)
>
> Bootstrapped/regtested on x86_64-linux, ok for trunk?
>
> 2015-05-28 Marek Polacek <pola...@redhat.com>
>
> PR tree-optimization/66299
> * match.pd ((CST1 << A) == CST2 -> A == log2 (CST2 / CST1),
> (CST1 << A) != CST2 -> A != log2 (CST2 / CST1)): New
> patterns.
>
> * gcc.dg/pr66299-1.c: New test.
> * gcc.dg/pr66299-2.c: New test.
>
> diff --git gcc/match.pd gcc/match.pd
> index abd7851..5d07a70 100644
> --- gcc/match.pd
> +++ gcc/match.pd
> @@ -676,6 +676,19 @@ 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 == log2 (CST2 / CST1)
> + (CST1 << A) != CST2 -> A != log2 (CST2 / CST1)
> + if CST2 is a multiple of CST1. */
> +(for cmp (ne eq)
> + (simplify
> + (cmp (lshift@3 INTEGER_CST@0 @1) INTEGER_CST@2)
> + (if ((TREE_CODE (@3) != SSA_NAME || has_single_use (@3))
I think we have the single_use (@3) helper now. Not sure why you
restrict this here though - we are only creating new constants.
Ok with dropping the single-use check.
> + && wi::multiple_of_p (@2, @0, TYPE_SIGN (type)))
> + (with {
> + int shift = wi::exact_log2 (wi::div_trunc (@2, @0, TYPE_SIGN (type))); }
> + (if (shift != -1)
> + (cmp @1 { build_int_cst (TREE_TYPE (@1), shift); }))))))
so with else you mean
(if (shift != -1)
...
(else-expr ...))
? Sure that's possible. Today you can write
(if (shift != -1)
...)
(if (shift == -1)
...)
or
(if (shift != -1)
....)
(else-expr)
which is equivalent if the if is the only one at the nesting level and
the then-expr
doesn't contain any further ones. That is, it is equivalent to
if () ...;
else-expr;
thus the fall-thru
So (if ...) would get an optional else-expr, yes, that sounds useful.
I think we
already have some (if A ..) (if !A ..) in match.pd.
Thanks,
Richard.
> +
> /* 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..9d41275 100644
> --- gcc/testsuite/gcc.dg/pr66299-1.c
> +++ gcc/testsuite/gcc.dg/pr66299-1.c
> @@ -0,0 +1,83 @@
> +/* 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 ();
> +}
> +
> +int
> +main (void)
> +{
> + test1 (1);
> + test2 (2);
> + test3 (4U);
> + test4 (3U);
> +}
> +
> +/* { dg-final { scan-tree-dump-not "<<" "original" } } */
> +/* { dg-final { cleanup-tree-dump "original" } } */
> diff --git gcc/testsuite/gcc.dg/pr66299-2.c gcc/testsuite/gcc.dg/pr66299-2.c
> index e69de29..dde0549 100644
> --- gcc/testsuite/gcc.dg/pr66299-2.c
> +++ gcc/testsuite/gcc.dg/pr66299-2.c
> @@ -0,0 +1,34 @@
> +/* 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" } } */
> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>
> Marek
