[Bug middle-end/54571] New: Missed optimization converting between bit sets

[Bug middle-end/54571] New: Missed optimization converting between bit sets

[rth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54571

             Bug #: 54571
           Summary: Missed optimization converting between bit sets
    Classification: Unclassified
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rth@gcc.gnu.org


When converting a bit set from one domain to another,code such as

  if (old & OLD_X) new |= NEW_X;
  if (old & OLD_Y) new |= NEW_Y;

is common.  If OLD_X and NEW_X are single bits, then this conversion
need not include any conditional code.  One can mask out OLD_X and
shift it left or right to become NEW_X.  Or, vice versa, shift left
or right and then mask out NEW_X.

Indeed, it's probably preferable to perform the mask with the smaller
of OLD_X and NEW_X in order to maximize the possibility of having a
valid immediate operand to the logical insn.

A test case that would seem to cover the all the cases, including 
converting logical not to bitwise not, would seem to be

int f1(int x, int y) { if (x & 1) y |= 1; return y; }
int f2(int x, int y) { if (x & 1) y |= 2; return y; }
int f3(int x, int y) { if (x & 2) y |= 1; return y; }
int g1(int x, int y) { if (!(x & 1)) y |= 1; return y; }
int g2(int x, int y) { if (!(x & 1)) y |= 2; return y; }
int g3(int x, int y) { if (!(x & 2)) y |= 1; return y; }

I'll also note that on the (presumably) preferred alternatives:

int h1(int x, int y) { return (x & 1) | y; }
int h2(int x, int y) { return ((x & 1) << 1) | y; }
int h3(int x, int y) { return ((x & 2) >> 1) | y; }
int k1(int x, int y) { return (~x & 1) | y; }
int k2(int x, int y) { return ((~x & 1) << 1) | y; }
int k3(int x, int y) { return ((~x >> 1) & 1) | y; }

there's some less-than-optimial code generated for k1 and k2.

[Bug middle-end/54571] Missed optimization converting between bit sets

[rth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54571

Richard Henderson <rth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

[Bug middle-end/54571] Missed optimization converting between bit sets

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54571

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-09-14
            Version|unknown                     |4.8.0
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-09-14 08:39:42 UTC ---
Confirmed.  The natural place to optimize this is the tree level phiopt pass.

  <bb 2>:
  _3 = x_2(D) & 2;
  if (_3 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  y_5 = y_4(D) | 1;

  <bb 4>:
  # y_1 = PHI <y_4(D)(2), y_5(3)>

where we should handle

int f1(int x, int y, int d) { int tem; if ((tem = x & d)) y |= tem; return y; }

as well.  Yes, that's just y |= x & d, but it falls out naturally if the
transform is implemented in a generic enough way.

[Bug middle-end/54571] Missed optimization converting between bit sets

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #1)
> Confirmed.  The natural place to optimize this is the tree level phiopt pass.
> 
>   <bb 2>:
>   _3 = x_2(D) & 2;
>   if (_3 != 0)
>     goto <bb 3>;
>   else
>     goto <bb 4>;
> 
>   <bb 3>:
>   y_5 = y_4(D) | 1;
> 
>   <bb 4>:
>   # y_1 = PHI <y_4(D)(2), y_5(3)>
> 
> where we should handle
> 
> int f1(int x, int y, int d) { int tem; if ((tem = x & d)) y |= tem; return
> y; }
> 
> as well.  Yes, that's just y |= x & d, but it falls out naturally if the
> transform is implemented in a generic enough way.


This one should be easy to add to match.pd:

(simplify
 (cond @1 (ior @2 INTEGER_CST@3) @2)
 (ior @2 (bit_and (negate (convert @1)) @3)))


(bit_and (negate (convert thurth_value@1)) integer_onep)
should be just converted to:
@1
Which is not done right now, I fill that as a bug.

[Bug middle-end/54571] Missed optimization converting between bit sets

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dhowells at redhat dot com

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 78317 has been marked as a duplicate of this bug. ***

[Bug middle-end/54571] Missed optimization converting between bit sets

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
             Status|NEW                         |ASSIGNED
         Depends on|                            |103216

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This is fixed mostly by the patch which fixes PR 103216.
We still have stuff like:
  _1 = x_3(D) & 1;
  _7 = _1 != 0;
  _8 = (int) _7;
  _9 = y_4(D) | _8;

and:
  _1 = x_3(D) & 2;
  _7 = _1 != 0;
  _8 = (int) _7;
  _9 = y_4(D) | _8;

and
   _1 = x_3(D) & 2;
  _7 = _1 != 0;
  _8 = (int) _7;
  _9 = _8 << 1;
  _10 = y_4(D) | _9;

Which we produce things like:
        xorl    %eax, %eax
        andl    $2, %edi
        sete    %al
        orl     %esi, %eax

Where the sete/xor could be reproduced with shift for an example.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103216
[Bug 103216] missed optimization, phiopt/vrp?

[Bug middle-end/54571] Missed optimization converting between bit sets

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The `popcount(nz) == 1` comment part of PR 103216 will fix this issue.