[Bug c/96433] New: Failed to optimize (A / N) * N <= A

[Bug c/96433] New: Failed to optimize (A / N) * N <= A

[david.bolvansky at gmail dot com]

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

            Bug ID: 96433
           Summary: Failed to optimize (A / N) * N <= A
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: david.bolvansky at gmail dot com
  Target Milestone: ---

const __SIZE_TYPE__ N = 3;

int foo(__SIZE_TYPE__ len) {
        __SIZE_TYPE__ newlen = (len / N) * N;
        return newlen <= len;
}

[Bug c/96433] Failed to optimize (A / N) * N <= A

[david.bolvansky at gmail dot com]

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

--- Comment #1 from Dávid Bolvanský <david.bolvansky at gmail dot com> ---
Codegen:
https://godbolt.org/z/7EvYj9

foo:
        movabs  rdx, -6148914691236517205
        mov     rax, rdi
        mul     rdx
        mov     rax, rdx
        and     rdx, -2
        shr     rax
        add     rdx, rax
        xor     eax, eax
        cmp     rdi, rdx
        setnb   al
        ret
N:
        .quad   3

Can be optimized to return true

[Bug tree-optimization/96433] Failed to optimize (A / N) * N <= A

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |tree-optimization
   Last reconfirmed|                            |2020-08-03
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
            Version|tree-ssa                    |11.0

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
Replacing (A/B)*B with A-A%B makes the transformation a bit simpler (and the
signed variants with ceil/floor), but we probably don't want to do that
transformation all the time (?). Which leaves the rather specialized (A/B)*B
cmp A...

[Bug tree-optimization/96433] Failed to optimize (A / N) * N <= A

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Or handle that during VRP with symbolic ranges.  But am not sure to what extent
symbolic ranges are going to stay.

[Bug tree-optimization/96433] Failed to optimize (A / N) * N <= A

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jmuizelaar at mozilla dot com

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

[Bug tree-optimization/96433] Failed to optimize (A / N) * N <= A

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Maybe we can just pattern match this simple cases which seems like what clang
does:
(simplify
 (le:c @0 (mult:c (div @0 @1) @1)
 ( { true_value; } ))
(simplify
 (gt:c @0 (mult:c (div @0 @1) @1)
 ( { false_value; } ))

That is these are all optimized:
//const __SIZE_TYPE__ N = 3;

int foo(__SIZE_TYPE__ len, __SIZE_TYPE__ N) {
        __SIZE_TYPE__ newlen = (len / N) * N;
        return newlen <= len;
}
int foo0(__SIZE_TYPE__ len, __SIZE_TYPE__ N) {
        __SIZE_TYPE__ newlen = (len / N) * N;
        return newlen > len;
}
int foo1(__SIZE_TYPE__ len, __SIZE_TYPE__ N) {
        __SIZE_TYPE__ newlen = (len / N) * N;
        return !(len >= newlen);
}

[Bug tree-optimization/96433] Failed to optimize (A / N) * N <= A

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note what LLVM detects/matches is exactly:

 (for unsigned types)
(A % B) <= A -> true
(A % B) > A -> true