Re: [PATCH] Optimize (CST1 << A) == CST2 (PR tree-optimization/66299)

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, May 28, 2015 at 2:15 PM, Marek Polacek <polacek@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  <polacek@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