[Bug tree-optimization/96696] New: Failure to optimize div+mul to mod+sub

[Bug tree-optimization/96696] New: Failure to optimize div+mul to mod+sub

[gabravier at gmail dot com]

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

            Bug ID: 96696
           Summary: Failure to optimize div+mul to mod+sub
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(int x, int y)
{
    return (x / y) * y;
}

This can be optimized to `return x - (x % y);`. This transformation is done by
LLVM, but not by GCC.

[Bug tree-optimization/96696] Failure to optimize div+mul to mod+sub

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-08-25

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  We have

/* Simplify (unsigned t / 2) * 2 -> unsigned t & ~1.  */
(simplify
 (mult (trunc_div @0 integer_pow2p@1) @1)
 (if (TYPE_UNSIGNED (TREE_TYPE (@0)))
  (bit_and @0 (negate @1))))

[Bug tree-optimization/96696] Failure to optimize div+mul to mod+sub

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Do we want to do it in match.pd though, perhaps with :s or single_use check?
For GIMPLE it is 2 operations to 2 operations transformation, although
multiplication might often be more expensive than subtraction.
Or in backends only based on costs?  I mean, x - (x % y) is actually longer so
might not the best idea e.g. for -Os.
But I'm more worried about the CSE possibilities if some code around does x /
y.

[Bug tree-optimization/96696] Failure to optimize div+mul to mod+sub

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'd say doing sth at RTL expansion.  For GIMPLE we should consider the cases

int g1, g2;
int f(int x, int y)
{
    g1 = x / y;
    return x - (x % y);
}

int g(int x, int y)
{
    g2 = x % y;
    return (x / y) * y;
}

in terms of CSE.

[Bug tree-optimization/96696] Failure to optimize div+mul to mod+sub

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49982
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49982&action=edit
gcc11-pr96696.patch

Untested fix.

[Bug tree-optimization/96696] Failure to optimize div+mul to mod+sub

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:3dcd1334b4f522352b80814513fdca902fc2a207

commit r12-150-g3dcd1334b4f522352b80814513fdca902fc2a207
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Apr 27 14:45:45 2021 +0200

    expand: Expand x / y * y as x - x % y if the latter is cheaper [PR96696]

    The following patch tests both x / y * y and x - x % y expansion for the
    former GIMPLE code and chooses the cheaper of those sequences.

    2021-04-27  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/96696
            * expr.c (expand_expr_divmod): New function.
            (expand_expr_real_2) <case TRUNC_DIV_EXPR>: Use it for truncations
and
            divisions.  Formatting fixes.
            <case MULT_EXPR>: Optimize x / y * y as x - x % y if the latter is
            cheaper.

            * gcc.target/i386/pr96696.c: New test.