[Bug rtl-optimization/48077] New: [Code Improvement] Use multiplication by magic number for integer division by constant

[Bug rtl-optimization/48077] New: [Code Improvement] Use multiplication by magic number for integer division by constant

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

           Summary: [Code Improvement] Use multiplication by magic number
                    for integer division by constant
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: bergner@gcc.gnu.org, pthaugen@gcc.gnu.org,
                    meissner@gcc.gnu.org, dje.gcc@gmail.com,
                    wschmidt@gcc.gnu.org
            Target: powerpc64-linux, others


We noticed a significant performance difference between gcc and xlc at all
optimization levels for a small application that repeatedly takes a value
modulo an integer constant.  Gcc expands division by a constant into a sequence
of shifts, adds, and subtracts.  Xlc converts division by a constant into
multiplication by a corresponding magic number.  See H.S. Warren's _Hacker's
Delight_ for details.  See http://www.hackersdelight.org/magic.htm for a magic
number calculator.

A small test case shows the difference:

-----------------------------------------
int *values;
int *hash_table;

int demonstrate (int i)
{
  return hash_table [values [i] % 1000];
}
-----------------------------------------

On powerpc64-linux, xlc -c -S -O3 -q32 test.c produces:

demonstrate:
    addis      r4,r0,values@ha
    rlwinm     r3,r3,2,0,29
    addis      r6,r0,hash_table@ha
    addis      r5,r0,4194
    addi       r0,r5,19923
    lwz        r4,values@l(r4)
    lwz        r5,hash_table@l(r6)
    lwzx       r3,r4,r3
    rlwinm     r4,r3,1,31,31
    mulhw      r0,r3,r0
    srawi      r0,r0,6
    add        r6,r0,r4
    rlwinm     r0,r6,10,0,21
    rlwinm     r4,r6,5,0,26
    subf       r0,r4,r0
    rlwinm     r6,r6,3,0,28
    add        r4,r0,r6
    subf       r0,r4,r3
    rlwinm     r3,r0,2,0,29
    lwzx       r3,r5,r3
    bclr       BO_ALWAYS,CR0_LT

Note the multiply by 274877907, built by:

    addis      r5,r0,4194
    addi       r0,r5,19923

If you plug 1000 into the magic number calculator at the website above, that's
the magic number produced.

By contrast, gcc -c -S -O3 -m32 test.c produces:

.L.demonstrate:
    addis 9,2,.LC0@toc@ha
    ld 9,.LC0@toc@l(9)
    sldi 3,3,2
    addis 11,2,.LC1@toc@ha
    ld 9,0(9)
    ld 10,.LC1@toc@l(11)
    lwzx 9,9,3
    extsw 0,9
    sldi 8,0,7
    sldi 11,0,9
    add 11,8,11
    subf 11,0,11
    sldi 11,11,3
    add 11,11,0
    sldi 8,11,2
    add 11,11,8
    sldi 11,11,2
    add 11,11,0
    sldi 11,11,3
    add 11,11,0
    sldi 8,11,3
    subf 11,11,8
    sldi 11,11,4
    add 0,11,0
    sldi 11,0,2
    subf 0,0,11
    srdi 0,0,32
    srawi 11,9,31
    srawi 0,0,6
    subf 0,11,0
    slwi 8,0,7
    slwi 11,0,2
    subf 11,11,8
    add 0,11,0
    ld 11,0(10)
    slwi 0,0,3
    subf 9,0,9
    extsw 9,9
    sldi 9,9,2
    lwax 3,11,9
    blr

Note the long string of dependencies in the gcc code; not only is the code
quite a bit larger, but there is very little ILP.

Consider converting integer division to multiplication by a magic number when
appropriate for the target machine.

[Bug rtl-optimization/48077] [Code Improvement] Use multiplication by magic number for integer division by constant

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-03-11 17:11:25 UTC ---
Actually GCC is expanding the division by a constant into a multiplication but
using shifts and adds to do the multiplication based on the cost.

[Bug rtl-optimization/48077] [Code Improvement] Use multiplication by magic number for integer division by constant

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

--- Comment #2 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-03-11 18:34:41 UTC ---
OK, interesting, thanks for the information.  It seems the analysis of the cost
is not particularly good here.  I'll dig into where the expansion is occurring.

[Bug target/48077] [Code Improvement] Poor expansion of multiply on powerpc64-linux

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|powerpc64-linux, others     |powerpc64-linux
          Component|rtl-optimization            |target
            Summary|[Code Improvement] Use      |[Code Improvement] Poor
                   |multiplication by magic     |expansion of multiply on
                   |number for integer division |powerpc64-linux
                   |by constant                 |

--- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-03-11 19:22:06 UTC ---
Changing this to a target issue.  Confirmed that gcc is producing the correct
magic number multiply, which survives till final assembly output, when the poor
expansion takes place.

[Bug target/48077] [Code Improvement] Poor expansion of multiply on powerpc64-linux

[meissner at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

--- Comment #4 from Michael Meissner <meissner at gcc dot gnu.org> 2011-03-11 20:43:20 UTC ---
It depends on what the default cpu is for the system.  If you say -mcpu=power4,
-mcpu=power5, or -mcpu=power7, it generates code similar to what XLC generates
with mulhw to get the recrip. and a mulli:

demonstrate:
        lis 9,values@ha
        slwi 3,3,2
        lwz 11,values@l(9)
        lis 0,0x1062
        ori 0,0,19923
        lwzx 9,11,3
        lis 11,hash_table@ha
        lwz 8,hash_table@l(11)
        mulhw 0,9,0
        srawi 10,9,31
        srawi 0,0,6
        subf 0,10,0
        mulli 0,0,1000
        subf 9,0,9
        slwi 9,9,2
        lwzx 3,8,9
        blr

If you say -mcpu=power6 the mulli is replaced by shifts and adds, similar to
what XLC generates.

demonstrate:
        lis 11,values@ha
        slwi 3,3,2
        lwz 9,values@l(11)
        lis 11,hash_table@ha
        add 9,9,3
        lwz 8,hash_table@l(11)
        lwz 10,0(9)
        lis 9,0x1062
        ori 9,9,19923
        mulhw 9,10,9
        srawi 0,10,31
        srawi 9,9,6
        subf 9,0,9
        slwi 11,9,2
        slwi 0,9,7
        subf 0,11,0
        add 0,0,9
        slwi 0,0,3
        subf 10,0,10
        slwi 10,10,2
        add 8,8,10
        lwz 3,0(8)
        blr

[Bug target/48077] [Code Improvement] Poor expansion of multiply on powerpc64-linux

[wschmidt at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

--- Comment #5 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-03-11 21:27:25 UTC ---
BTW, I mis-entered the optimization level before.  The code generation was at
-O2 when the mulhw was expanded into shifts/adds with the default P6 tuning. 
At -O3 and up, the mulhw is intact.

This is all explained by the default tuning model in place during testing,
since Power6 had a poorer performing integer multiply than the other machine
models.

[Bug target/48077] [Code Improvement] Poor expansion of multiply on powerpc64-linux

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48077

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-03-14 10:26:33 UTC ---
Thus, works fine.