[Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0)

[Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0)

[olegendo at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

            Bug ID: 64309
           Summary: if (1 & (1 << n)) not simplified to if (n == 0)
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: olegendo at gcc dot gnu.org
            Target: sh*-*-*

The SH specific test case gcc/testsuite/gcc.target/sh/pr51244-8.c has been
failing for a while now.  Originally I've added some combine patterns to handle
the special case
  if (1 & (1 << n)) -> if (n == 0)

I could fix this by modifying the SH combine patterns so that they match again.
 However, it would fail to handle all the other cases such as
  if ((1 << 1) & (1 << n)) -> if (n == 1)
  if ((1 << 2) & (1 << n)) -> if (n == 2)
  if ((3 << 0) & (3 << n)) -> if (n == 0)
  etc

I think it should be handled in a target independent way either at the tree
level or by combine, but I'm not sure what is easier/makes more sense.


Taking it a bit further...
On SH it's better to avoid dynamic shifts (e.g. on SH2 dynamic shifts are
library calls).  Thus, in cases of something like

int test (int n)
{
  return ((1 << 1) & (1 << n));
}

it's often better to do a comparison and a cstore instead.  Here again, I could
add SH specific patterns, but maybe it makes more sense to do it in a target
independent way at tree level or in combine.  RTX costs can/should be used to
check whether a 'shift,and' is more expensive than a 'cmp,cstore'.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Surely can we transform if ((3 << 0) & (3 << n)) -> if (n == 0)?  For n == 1
that is true as well.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |mpolacek at gcc dot gnu.org
   Target Milestone|---                         |5.0

--- Comment #3 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Let me try sth.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[olegendo at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #4 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> Confirmed.  Sth like
> 
>  (simplify
>   (ne (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
>   (eq @0 { build_zero_cst (TREE_TYPE (@0)); })
> 
> with eventually also covering if ((1 & (1<< n)) == 0) -> if (n & 1 == 0)
> 
> You can extend this to cover the other cases you mention.

I thought you might suggest something like this. :)
While the transform for the if (...) is probably going to be beneficial for all
the targets, I'm not so sure about the 'return ((1 << 1) & (1 << n));' variant,
though.  On some targets a shift+and might be cheaper than cmp+cstore.  Is
there any way to get that information during tree optimization?  If not, it
might be better to do that transformation on the RTL.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #5 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
(In reply to Oleg Endo from comment #4)
> (In reply to Richard Biener from comment #1)
> > Confirmed.  Sth like
> > 
> >  (simplify
> >   (ne (bit_and (lshift integer_onep @0) integer_onep) integer_zerop)
> >   (eq @0 { build_zero_cst (TREE_TYPE (@0)); })
> > 
> > with eventually also covering if ((1 & (1<< n)) == 0) -> if (n & 1 == 0)
> > 
> > You can extend this to cover the other cases you mention.
> 
> I thought you might suggest something like this. :)

Note that this transformation doesn't work.

> While the transform for the if (...) is probably going to be beneficial for
> all the targets, I'm not so sure about the 'return ((1 << 1) & (1 << n));'
> variant, though.  On some targets a shift+and might be cheaper than
> cmp+cstore.  Is there any way to get that information during tree
> optimization?  If not, it might be better to do that transformation on the
> RTL.

I don't think so.  I tried to come up with a more general transformation that
would simplify ((CST << n) & CST) != 0, but I haven't found anything yet.  So
maybe just this?
((1 << n) & 1) != 0 -> n == 0
((1 << n) & 1) == 0 -> n != 0

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #6 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #5)
> I don't think so.  I tried to come up with a more general transformation
> that would simplify ((CST << n) & CST) != 0, but I haven't found anything

If both CST are (possibly different) powers of 2 it works. ((c<<n)&c)==c also
works. ((pow2<<p)&(pow2<<n))!=0.

> yet.  So maybe just this?
> ((1 << n) & 1) != 0 -> n == 0

That looks like what richi posted. For scalars, != 0 is useless and this could
just be:
(1<<n)&1 -> n==0

> ((1 << n) & 1) == 0 -> n != 0

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[olegendo at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #7 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Marek Polacek from comment #5)
> 
> I don't think so.  I tried to come up with a more general transformation
> that would simplify ((CST << n) & CST) != 0, but I haven't found anything
> yet.  So maybe just this?
> ((1 << n) & 1) != 0 -> n == 0
> ((1 << n) & 1) == 0 -> n != 0

If I'm not mistaken...

(1 << n) & 2 != 0 -> n == 1
(1 << n) & 3 != 0 -> n < 2 (unsigned)
(1 << n) & 4 != 0 -> n == 2
(1 << n) & 5 != 0 -> n == 0 || n == 2 (not beneficial)
(1 << n) & 6 != 0 -> n > 0 && n < 3 (not beneficial)
(1 << n) & 7 != 0 -> n < 3 (unsigned)
...

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #8 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #6)
> (In reply to Marek Polacek from comment #5)
> > I don't think so.  I tried to come up with a more general transformation
> > that would simplify ((CST << n) & CST) != 0, but I haven't found anything
> 
> If both CST are (possibly different) powers of 2 it works.

Yes, but I'm not sure if it's worth it (doing it for 1, 2, 4, 8, ... instead of
just for 1).

> ((c<<n)&c)==c also works. ((pow2<<p)&(pow2<<n))!=0.

I don't see how's that a simplification.

> > yet.  So maybe just this?
> > ((1 << n) & 1) != 0 -> n == 0
> 
> That looks like what richi posted. For scalars, != 0 is useless and this
> could just be:
> (1<<n)&1 -> n==0

Yeah, it's what richi posted.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
 (1 << n) & 5 != 0 -> n == 0 || n == 2 (not beneficial)

Not only that, we actually emit similar comparisons as a bit test intentionally
even if you write it in a switch or series of ifs that way, so undoing that
optimization would be a bad idea.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #10 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
(In reply to Oleg Endo from comment #7)
> (In reply to Marek Polacek from comment #5)
> > 
> > I don't think so.  I tried to come up with a more general transformation
> > that would simplify ((CST << n) & CST) != 0, but I haven't found anything
> > yet.  So maybe just this?
> > ((1 << n) & 1) != 0 -> n == 0
> > ((1 << n) & 1) == 0 -> n != 0
> 
> If I'm not mistaken...
> 
> (1 << n) & 2 != 0 -> n == 1
> (1 << n) & 3 != 0 -> n < 2 (unsigned)
> (1 << n) & 4 != 0 -> n == 2
> (1 << n) & 5 != 0 -> n == 0 || n == 2 (not beneficial)
> (1 << n) & 6 != 0 -> n > 0 && n < 3 (not beneficial)
> (1 << n) & 7 != 0 -> n < 3 (unsigned)
> ...

Right - but to me only the first one seems like a win.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #11 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Oleg Endo from comment #7)
> (1 << n) & 6 != 0 -> n > 0 && n < 3 (not beneficial)

We usually spell it (unsigned)n-1<2 (still not that great).

(In reply to Marek Polacek from comment #8)
> > > I don't think so.  I tried to come up with a more general transformation
> > > that would simplify ((CST << n) & CST) != 0, but I haven't found anything
> > 
> > If both CST are (possibly different) powers of 2 it works.
> 
> Yes, but I'm not sure if it's worth it (doing it for 1, 2, 4, 8, ... instead
> of just for 1).

I am not sure why 1 is so much more important than the others...

> > ((c<<n)&c)==c also works. ((pow2<<p)&(pow2<<n))!=0.
> 
> I don't see how's that a simplification.

((c<<n)&c)==c -> n==0
((pow2<<p)&(pow2<<n))!=0 -> p==n

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[glisse at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #12 from Marc Glisse <glisse at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #11)
> ((pow2<<p)&(pow2<<n))!=0 -> p==n

Oups, it wasn't supposed to be the same power of 2, so:
(((1<<k)<<p)&((1<<l)<<n))!=0 -> p==n+(l-k)
(k and l are constants)

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #13 from rguenther at suse dot de <rguenther at suse dot de> ---
On December 15, 2014 10:11:13 PM CET, "glisse at gcc dot gnu.org"
<gcc-bugzilla@gcc.gnu.org> wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309
>
>--- Comment #12 from Marc Glisse <glisse at gcc dot gnu.org> ---
>(In reply to Marc Glisse from comment #11)
>> ((pow2<<p)&(pow2<<n))!=0 -> p==n
>
>Oups, it wasn't supposed to be the same power of 2, so:
>(((1<<k)<<p)&((1<<l)<<n))!=0 -> p==n+(l-k)
>(k and l are constants)

As others noted the transforms are only generally beneficial if they feed
comparisons.  Otherwise we may of course want to find a canonical form, but
possibly that shouldn't be a comparison unless expansion knows how to undo this
and rewrite them as bit operation.

Richard.

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

--- Comment #14 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Author: mpolacek
Date: Tue Dec 16 18:29:01 2014
New Revision: 218787

URL: https://gcc.gnu.org/viewcvs?rev=218787&root=gcc&view=rev
Log:
    PR middle-end/64309
    * match.pd: Add ((1 << A) & 1) != 0 -> A == 0 and
    ((1 << A) & 1) == 0 -> A != 0.

    * gcc.dg/pr64309.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr64309.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/match.pd
    trunk/gcc/testsuite/ChangeLog

[Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64309

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #15 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Fixed, up to some point.