[Bug tree-optimization/98334] New: Failure to optimally optimize add loop to mul

[Bug tree-optimization/98334] New: Failure to optimally optimize add loop to mul

[gabravier at gmail dot com]

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

            Bug ID: 98334
           Summary: Failure to optimally optimize add loop to mul
           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 i, unsigned int n) {
    int result = 0;
    while (n > 0) {
        result += i;
        n -= 1;
    }
    return result;
}

GCC optimizes this function to code that effectively does `return (n == 0) ? 0
: (i - 1) * n + n;`. It could instead emit the more optimal `return (n == 0) ?
0 : i * n;`, or just `return i * n;` on platforms where multiplication is fast.
This transformation is done by LLVM, but not by GCC.

[Bug tree-optimization/98334] Failure to optimally optimize add loop to mul

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
This boils down to:
int
bar (int x, int y)
{
  return (int) (y - 1U) * x + x;
}

int
baz (int x, int y)
{
  return (y - 1) * x + x;
}

We do optimize the latter, but don't optimize the former into y * x.
For non-wrapping operation in bar that would be an invalid optimization,
as (int) (y - 1U) * x + x is well defined for y == INT_MIN and x == -1:
it is INT_MAX * -1 + -1, i.e. INT_MIN without overflow, but INT_MIN * -1
does overflow.
But we perhaps could and should turn that into just (int) ((y - 1U) * x),
i.e. unsigned multiplication.
We shouldn't do this until very late though, because turning signed arithmetics
into unsigned may disable other optimizations as it has no UB.

Or we could optimize this on RTL, combiner attempts:
Trying 7, 8 -> 9:
    7: {r90:SI=r93:SI-0x1;clobber flags:CC;}
      REG_DEAD r93:SI
      REG_UNUSED flags:CC
    8: {r91:SI=r90:SI*r92:SI;clobber flags:CC;}
      REG_UNUSED flags:CC
      REG_DEAD r90:SI
    9: r89:SI=r91:SI+r92:SI
      REG_DEAD r92:SI
      REG_DEAD r91:SI
Failed to match this instruction:
(set (reg:SI 89)
    (plus:SI (mult:SI (plus:SI (reg:SI 93)
                (const_int -1 [0xffffffffffffffff]))
            (reg:SI 92))
        (reg:SI 92)))
so if we hack up simplify-rtx.c to optimize that to (mult:SI (reg:SI 93)
(reg:SI 92)), it should work.

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
   Last reconfirmed|                            |2020-12-17
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED

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

Untested fix.

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think turning (int) (y - 1U) * x + x into unsigned mult is OK even early.

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[cvs-commit at gcc dot gnu.org]

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

--- Comment #4 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:4615cde5d7ef281d4b554df411f82ad707f0a54d

commit r11-6456-g4615cde5d7ef281d4b554df411f82ad707f0a54d
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Tue Jan 5 10:57:52 2021 +0100

    simplify-rtx: Optimize (x - 1) * y + y [PR98334]

    We don't try to optimize for signed x, y (int) (x - 1U) * y + y
    into x * y, we can't do that with signed x * y, because the former
    is well defined for INT_MIN and -1, while the latter is not.
    We could perhaps optimize it during isel or some very late optimization
    where we'd turn magically flag_wrapv, but we don't do that yet.

    This patch optimizes it in simplify-rtx.c, such that we can optimize
    it during combine.

    2021-01-05  Jakub Jelinek  <jakub@redhat.com>

            PR rtl-optimization/98334
            * simplify-rtx.c (simplify_context::simplify_binary_operation_1):
            Optimize (X - 1) * Y + Y to X * Y or (X + 1) * Y - Y to X * Y.

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

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed at the RTL level, keeping open for the GIMPLE optimization.

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[roger at nextmovesoftware dot com]

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

Roger Sayle <roger at nextmovesoftware dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |roger at nextmovesoftware dot com
         Resolution|---                         |FIXED

--- Comment #6 from Roger Sayle <roger at nextmovesoftware dot com> ---
This is now fully optimized at the tree level too.
int f (int i, unsigned int n)
{
  int result;
  int _1;

  <bb 2> [local count: 118111600]:
  _1 = (int) n_3(D);
  result_2 = _1 * i_6(D);
  return result_2;

}

[Bug rtl-optimization/98334] Failure to optimally optimize add loop to mul

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #5)
> Fixed at the RTL level, keeping open for the GIMPLE optimization.

For the testcase in comment #1 this is recorded as PR 94782.

For the original testcase in comment #0, I don't know when it was fixed on the
trunk but in sccp we get now:

final value replacement:
  result_2 = PHI <result_7(3)>
 with expr: (int) n_4(D) * i_6(D)
 final stmt:
  result_2 = _1 * i_6(D);

instead of:

final value replacement:
  result_2 = PHI <result_7(3)>
 with expr: (int) (n_3(D) + 4294967295) * i_6(D) + i_6(D)
 final stmt:
  result_2 = _9 + i_6(D);