[Bug tree-optimization/98299] New: Failure to optimize sub loop into modulo-based pattern

[Bug tree-optimization/98299] New: Failure to optimize sub loop into modulo-based pattern

[gabravier at gmail dot com]

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

            Bug ID: 98299
           Summary: Failure to optimize sub loop into modulo-based pattern
           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 f1(int n)
{
    while (n >= 45)
        n -= 45;

    return n;
}

This can be optimized into a modulo-based pattern, for example this :

int f2(int n)
{
    int tmp = n > 44 ? n : 44;
    return ((tmp % 45) - tmp) + n;
}

This transformation is done by LLVM, but not by GCC.

[Bug tree-optimization/98299] Failure to optimize sub loop into modulo-based pattern

[jakub at gcc dot gnu.org]

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

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> ---
The big question is if it is an optimization or not.
Perhaps the user wrote it that way because n is always or most of the time
small that it will be faster than doing modulo.

[Bug tree-optimization/98299] Failure to optimize sub loop into modulo-based pattern

[gabravier at gmail dot com]

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

--- Comment #2 from Gabriel Ravier <gabravier at gmail dot com> ---
At the very least, it seems like a worthwhile pattern to recognize in -O3, even
if only to avoid vectorizing it, i.e. have similar effects to what happens if
you add `if (n >= 1000) __builtin_unreachable();` to the start of f1.

Altogether, though, it seems unlikely that the modulo would be costlier than
the loop except in very narrow cases, since it is optimized into a
multiplication and a few other operations with little cost.

Also, the transformation into a modulo seems to occur in the vectorized version
too, though it is weirdly optimized.

[Bug tree-optimization/98299] Failure to optimize sub loop into modulo-based pattern

[gabravier at gmail dot com]

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

--- Comment #3 from Gabriel Ravier <gabravier at gmail dot com> ---
PS: The optimization seems to already occur for simpler cases such as powers of
2, e.g. :

int f1(int n)
{
    while (n >= 64)
        n -= 64;

    return n;
}

is optimized into `return (n <= 63) ? n : (n & 63);`.

[Bug tree-optimization/98299] Failure to optimize sub loop into modulo-based pattern

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-01-04
     Ever confirmed|0                           |1

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw for the similar division pattern kernel folks once complained ;)  But yes,
confirmed.  SCCP is doing such transform usually but we don't do it because
we consider the replacement

(n_2(D) + -45) + (int) (((unsigned int) n_2(D) + 4294967251) / 45) * -45

too expensive (guess the cast makes recognizing this as modulo not valid).