[Bug tree-optimization/103216] New: missed optimization, phiopt/vrp?

[Bug tree-optimization/103216] New: missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

            Bug ID: 103216
           Summary: missed optimization, phiopt/vrp?
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: pinskia at gcc dot gnu.org
  Target Milestone: ---

signed char f(unsigned char a)
{
  unsigned char b;
  signed char c, d, v;
  b = a & 127;
  c = (signed char) b;
  d = (signed char) a;
  v = c;
  if (d < 0)
    v = c | -128;
  return v;
}

This should just be optimized to return (signed char)a;

Reduced from the testcase provided by
https://twitter.com/__phantomderp/status/1459247957904080901 .

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For x86_64 we might be able to solve this at the RTL level during combine:
(set (reg/v:QI 84 [ <retval> ])
    (if_then_else:QI (lt (subreg:QI (reg:SI 86 [ a ]) 0)
            (const_int 0 [0]))
        (ior:QI (subreg:QI (reg:SI 86 [ a ]) 0)
            (const_int -128 [0xffffffffffffff80]))
        (reg/v:QI 84 [ <retval> ])))

That is optimize:
(a < 0) ? a | signbit : b
to
(a < 0) ? a : b


And I suspect we need after that)
(a < 0) ? a : a & ~signbit
into:
a

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)
> For x86_64 we might be able to solve this at the RTL level during combine:
> (set (reg/v:QI 84 [ <retval> ])
>     (if_then_else:QI (lt (subreg:QI (reg:SI 86 [ a ]) 0)
>             (const_int 0 [0]))
>         (ior:QI (subreg:QI (reg:SI 86 [ a ]) 0)
>             (const_int -128 [0xffffffffffffff80]))
>         (reg/v:QI 84 [ <retval> ])))
> 
> That is optimize:
> (a < 0) ? a | signbit : b
> to
> (a < 0) ? a : b

That didn't work either because combine could put back into place the lt.

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-11-13
             Status|UNCONFIRMED                 |NEW
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  b_3 = a_2(D) & 127;
  c_4 = (signed char) b_3;
  d_5 = (signed char) a_2(D);
  if (d_5 < 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  v_7 = c_4 | -128;

  <bb 4> :
  # v_1 = PHI <c_4(2), v_7(3)>


  (d<0) ? (c | -128) : c ->
      c | ((d<0) ? -128 : 0) ->
      c | ((d<0) << 7) ->
      c | (d & -128) ->
      (c|d) & c|-128 ->
      ((signed char)(b | a)) & ((singed char)a|128) ->
      ((signed char)((a&128) | a)) & ((singed char)a|128) ->
      ((signed char)a) & ((singed char)a|128) ->
      (signed char)(a & (a|128))-> 
      (signed char)a

Hopefully I did this right.

I am going to implement this.  I think I only need the first conversion (and
making sure cond goes away which leads to the second one) which should lead to
the rest (after having fixed PR 103218 which I am doing first which is needed
to get the 4th line).

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3) 
> I am going to implement this.  I think I only need the first conversion (and
> making sure cond goes away which leads to the second one) which should lead
> to the rest (after having fixed PR 103218 which I am doing first which is
> needed to get the 4th line).

I was right and wrong. I still need to debug match-and-simplify for why ! does
not work in one case, I thought it would.

Also the last 5 steps did not happen either on the gimple level, I filed PR
103220 for that.

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> (In reply to Andrew Pinski from comment #3) 
> > I am going to implement this.  I think I only need the first conversion (and
> > making sure cond goes away which leads to the second one) which should lead
> > to the rest (after having fixed PR 103218 which I am doing first which is
> > needed to get the 4th line).
> 
> I was right and wrong. I still need to debug match-and-simplify for why !
> does not work in one case, I thought it would.

Because it does not produce a leaf node, I needed to add a new flag ^ which is
like ! but only checks to make sure not producing the same code again.

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 51786
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51786&action=edit
Patch which I am testing

I still need to add testcases (there are many) and finish up the changelog.

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |103218
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2021-Novembe
                   |                            |r/584411.html
           Keywords|                            |patch

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
With PR 103218 patch and the one which I submited here:
https://gcc.gnu.org/pipermail/gcc-patches/2021-November/584411.html

This is basically fixed (we run into PR 103220 but that is a gimple level
missed optimization which should not matter really).


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103218
[Bug 103218] (a < 0) << signbit is not always optimized to a & signbitmask at
the gimple level

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103216
Bug 103216 depends on bug 103218, which changed state.

Bug 103218 Summary: (a < 0) << signbit is not always optimized to a & signbitmask at the gimple level
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=103218

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

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[mcccs at gmx dot com]

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

mcccs at gmx dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mcccs at gmx dot com

--- Comment #8 from mcccs at gmx dot com ---
*** Bug 86604 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|https://gcc.gnu.org/piperma |
                   |il/gcc-patches/2021-Novembe |
                   |r/584411.html               |
           Keywords|patch                       |

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So to fix this in a better way I propose to extend the:
`/* (zero_one == 0) ? y : z <op> y -> ((typeof(y))zero_one * z) <op> y */`
patterns to handle not only zero_one but rather popcount(nz) == 1. 
also treat `signed < 0` as `(signed>>signbit)&1`.

I will do that over the weekend.

[Bug tree-optimization/103216] missed optimization, phiopt/vrp?

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |TREE

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So this is almost fixed on the trunk at -O2:
  d_4 = (signed char) a_2(D);
  if (d_4 < 0)
    goto <bb 4>; [41.00%]
  else
    goto <bb 3>; [59.00%]

  <bb 3> [local count: 633507680]:
  _6 = (signed char) a_2(D);

  <bb 4> [local count: 1073741824]:
  # prephitmp_8 = PHI <_6(3), d_4(2)>

The only thing missing is seeing that d_4 and _6 are the same ...

Maybe factor_out_conditional_operation could detect this ...

  d_4 = (signed char) a_2(D);
  if (d_4 < 0)
    goto <bb 4>; [41.00%]
  else
    goto <bb 3>; [59.00%]

  <bb 3> [local count: 633507680]:
  _6 = (signed char) a_2(D);

  <bb 4> [local count: 1073741824]:
  # prephitmp_8 = PHI <_6(3), d_4(2)>

factor_out_conditional_operation could factor out the cast to the definition of
d_4 ...

Anyways the original code is now optimized (via RTL level) so maybe it is not
as important.