* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
@ 2014-12-15 11:45 ` mpolacek at gcc dot gnu.org
2014-12-15 13:23 ` mpolacek at gcc dot gnu.org
` (12 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-15 11:45 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
2014-12-15 11:45 ` [Bug middle-end/64309] " mpolacek at gcc dot gnu.org
@ 2014-12-15 13:23 ` mpolacek at gcc dot gnu.org
2014-12-15 19:08 ` olegendo at gcc dot gnu.org
` (11 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-15 13:23 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
2014-12-15 11:45 ` [Bug middle-end/64309] " mpolacek at gcc dot gnu.org
2014-12-15 13:23 ` mpolacek at gcc dot gnu.org
@ 2014-12-15 19:08 ` olegendo at gcc dot gnu.org
2014-12-15 19:22 ` mpolacek at gcc dot gnu.org
` (10 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: olegendo at gcc dot gnu.org @ 2014-12-15 19:08 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (2 preceding siblings ...)
2014-12-15 19:08 ` olegendo at gcc dot gnu.org
@ 2014-12-15 19:22 ` mpolacek at gcc dot gnu.org
2014-12-15 20:19 ` glisse at gcc dot gnu.org
` (9 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-15 19:22 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (3 preceding siblings ...)
2014-12-15 19:22 ` mpolacek at gcc dot gnu.org
@ 2014-12-15 20:19 ` glisse at gcc dot gnu.org
2014-12-15 20:41 ` olegendo at gcc dot gnu.org
` (8 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-12-15 20:19 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (4 preceding siblings ...)
2014-12-15 20:19 ` glisse at gcc dot gnu.org
@ 2014-12-15 20:41 ` olegendo at gcc dot gnu.org
2014-12-15 20:46 ` mpolacek at gcc dot gnu.org
` (7 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: olegendo at gcc dot gnu.org @ 2014-12-15 20:41 UTC (permalink / raw)
To: gcc-bugs
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)
...
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (5 preceding siblings ...)
2014-12-15 20:41 ` olegendo at gcc dot gnu.org
@ 2014-12-15 20:46 ` mpolacek at gcc dot gnu.org
2014-12-15 20:46 ` jakub at gcc dot gnu.org
` (6 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-15 20:46 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (6 preceding siblings ...)
2014-12-15 20:46 ` mpolacek at gcc dot gnu.org
@ 2014-12-15 20:46 ` jakub at gcc dot gnu.org
2014-12-15 20:49 ` mpolacek at gcc dot gnu.org
` (5 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: jakub at gcc dot gnu.org @ 2014-12-15 20:46 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (7 preceding siblings ...)
2014-12-15 20:46 ` jakub at gcc dot gnu.org
@ 2014-12-15 20:49 ` mpolacek at gcc dot gnu.org
2014-12-15 21:06 ` glisse at gcc dot gnu.org
` (4 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-15 20:49 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (8 preceding siblings ...)
2014-12-15 20:49 ` mpolacek at gcc dot gnu.org
@ 2014-12-15 21:06 ` glisse at gcc dot gnu.org
2014-12-15 21:11 ` glisse at gcc dot gnu.org
` (3 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-12-15 21:06 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (9 preceding siblings ...)
2014-12-15 21:06 ` glisse at gcc dot gnu.org
@ 2014-12-15 21:11 ` glisse at gcc dot gnu.org
2014-12-16 8:54 ` rguenther at suse dot de
` (2 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: glisse at gcc dot gnu.org @ 2014-12-15 21:11 UTC (permalink / raw)
To: gcc-bugs
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)
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (10 preceding siblings ...)
2014-12-15 21:11 ` glisse at gcc dot gnu.org
@ 2014-12-16 8:54 ` rguenther at suse dot de
2014-12-16 18:29 ` mpolacek at gcc dot gnu.org
2014-12-16 18:30 ` mpolacek at gcc dot gnu.org
13 siblings, 0 replies; 15+ messages in thread
From: rguenther at suse dot de @ 2014-12-16 8:54 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (11 preceding siblings ...)
2014-12-16 8:54 ` rguenther at suse dot de
@ 2014-12-16 18:29 ` mpolacek at gcc dot gnu.org
2014-12-16 18:30 ` mpolacek at gcc dot gnu.org
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-16 18:29 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 15+ messages in thread
* [Bug middle-end/64309] if (1 & (1 << n)) not simplified to if (n == 0)
2014-12-15 2:49 [Bug rtl-optimization/64309] New: if (1 & (1 << n)) not simplified to if (n == 0) olegendo at gcc dot gnu.org
` (12 preceding siblings ...)
2014-12-16 18:29 ` mpolacek at gcc dot gnu.org
@ 2014-12-16 18:30 ` mpolacek at gcc dot gnu.org
13 siblings, 0 replies; 15+ messages in thread
From: mpolacek at gcc dot gnu.org @ 2014-12-16 18:30 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 15+ messages in thread