[Bug target/100045] New: Precomputing division

[Bug target/100045] New: Precomputing division

[tkoenig at gcc dot gnu.org]

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

            Bug ID: 100045
           Summary: Precomputing division
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

Created attachment 50567
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=50567&action=edit
Test case

We use the method given in "Division by Invariant Integers using
Multiplication"
by Granlund and Montgomery for optimizing division by divisors known to
be constant at compile time.

There can also be an advantage if many numbers are divided by the
same numbers; in this case, the invariant inverse can be moved out of
the loop.  This is target-dependent.

The attached test case performs 10000000 unsigned divisions of uint32_t
values read in randomly by a constant randomly chosen to be 12345678

- using the method from figure 4.1 from the publication cited above
  (timing in seconds given as pre_divide)

- using a simple loop with divisions (timing in seconcs given as divide).

On a AMD Ryzen 7 1700X, the timings are

pre_divide: t = 0.013330 s
divide    : t = 0.052511 s

OTOH, on POWER (gcc135), the difference is so small so that is very probably
not worth the bother:

pre_divide: t = 0.015183 s
divide    : t = 0.017454 s

[Bug middle-end/100045] Precomputing division

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64-*-* i?86-*-*
          Component|target                      |middle-end
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2021-04-12
     Ever confirmed|0                           |1
            Version|unknown                     |11.0

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  This would be RTL expansion-time at the moment but we can of course
do such optimizations elsewhere (we have the recip pass which could be seen
doing similar things).  Rather than relying on invariant motion I'd say we
want to do LCM placement of the invariant parts though.

And indeed costing is target dependent.

[Bug middle-end/100045] Precomputing division

[cafxx+gcc.gnu.org at strayorange dot com]

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

cafxx+gcc.gnu.org at strayorange dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |cafxx+gcc.gnu.org@strayoran
                   |                            |ge.com

--- Comment #2 from cafxx+gcc.gnu.org at strayorange dot com ---
Related LLVM bug: https://github.com/llvm/llvm-project/issues/53332