[Bug tree-optimization/97711] New: Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[Bug tree-optimization/97711] New: Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[rsandifo at gcc dot gnu.org]

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

            Bug ID: 97711
           Summary: Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rsandifo at gcc dot gnu.org
  Target Milestone: ---

GCC doesn't optimise the expression:

  int f (int x) { return x & 1 ? x - 1 : x; }

to x & -2 (but clang does).  The original motivation was actually:

  char *g (char *x) { return (__UINTPTR_TYPE__) x & 1 ? x - 1 : x; }

which I guess might require a different pattern.

(And the reason for writing g that way was to do all pointer
arithmetic on pointers rather than converting to a uintptr_t,
doing arithmetic, and converting back.)

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2020-11-04

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  Guess another value-replacement for phiopt and/or a match.pd
pattern
(and maybe make phiopt do a match simplify query with a "fake" COND_EXPR in
pieces to avoid duplicating things)

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So GCC already converts the following two functions at the gimple level:
  int f1 (int x) { return x - (x & 1); }
  char *g1 (char *x) { return x - ((__UINTPTR_TYPE__) x & 1); }
----- CUT ----
Even on the RTL level too, I Noticed that because the original testcase does
the correct thing for aarch64, why it is not done for x86_64 I don't know.


Anyways what we could do is take:
  if (_2 != 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
  iftmp.1_5 = x_4(D) + 18446744073709551615;

  <bb 4> [local count: 1073741824]:
  # iftmp.1_3 = PHI <iftmp.1_5(3), x_4(D)(2)>

And convert that too:
iftmp.1_3 = x - (type)(_2 != 0)

So something simple as:
(simplify
 (cond @0 (plus @1 integer_all_onesp@2) @1)
 (minus @1 (convert @0)))


If you want to handle case where @2 is a power of 2 instead so you can use
shift, that is another option.

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

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
         Depends on|                            |103216
             Status|NEW                         |ASSIGNED

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine, the patch which fixes PR 103216 fixes this too.


Referenced Bugs:

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

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> Mine, the patch which fixes PR 103216 fixes this too.

Note it does not fix it fullly on the gimple level, we are left with:
  _1 = x_3(D) & 1;
  _7 = _1 != 0;
  _6 = (int) _7;
  _9 = x_3(D) - _6;


But the RTL level does optimize it to:
        movl    %edi, %eax
        andl    $-2, %eax

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

--- 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)
> > Mine, the patch which fixes PR 103216 fixes this too.
> 
> Note it does not fix it fully on the gimple level, we are left with:
>   _1 = x_3(D) & 1;
>   _7 = _1 != 0;
>   _6 = (int) _7;
>   _9 = x_3(D) - _6;

So this is optimized because VRP is able to figure out _1 has a range of [0,1]
a and then able to change _1 != 0 to (bool) _1.
That will be for GCC 13 to fix this fully on the gimple level.

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jengelh at inai dot de

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

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|103216                      |110155

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I have a better patch for this one, PR 110155.


Referenced Bugs:

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

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Well the patch for PR 110155 will fix f but not g. I will add the POINTER_PLUS
pattern this weekend.

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch
                URL|                            |https://gcc.gnu.org/piperma
                   |                            |il/gcc-patches/2023-June/62
                   |                            |0985.html

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch posted:
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/620985.html

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:55fcaa9a8bd9c8ce97ca929fc902c88cf92786a0

commit r14-1656-g55fcaa9a8bd9c8ce97ca929fc902c88cf92786a0
Author: Andrew Pinski <apinski@marvell.com>
Date:   Wed Jun 7 09:05:15 2023 -0700

    Add Plus to the op list of `(zero_one == 0) ? y : z <op> y` pattern

    This adds plus to the op list of `(zero_one == 0) ? y : z <op> y` patterns
    which currently has bit_ior and bit_xor.
    This shows up now in GCC after the boolization work that Uroš has been
doing.

    OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

            PR tree-optimization/97711
            PR tree-optimization/110155

    gcc/ChangeLog:

            * match.pd ((zero_one == 0) ? y : z <op> y): Add plus to the op.
            ((zero_one != 0) ? z <op> y : y): Likewise.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/branchless-cond-add-2.c: New test.
            * gcc.dg/tree-ssa/branchless-cond-add.c: New test.

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

Bug 110155 Summary: Missing if conversion
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110155

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

[Bug tree-optimization/97711] Failure to optimise "x & 1 ? x - 1 : x" to "x & -2"

[pinskia at gcc dot gnu.org]

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

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note the committed patch only fixes f in comment #1. g (Pointer plus) will need
another change.