[Issue 9920] [Optimizer] Use mul/imul for integer division by constant

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=9920



--- Comment #5 from Dmitry Olshansky <dmitry.olsh at gmail.com> 2013-04-11 12:33:09 PDT ---
Another data point taken from issue 5607 on div/mod heavy program seems to
confirm my estimate of 3x+ speed difference with mul-trick applied.

The program is bound on div/mul operaiton so other differences of GCC vs DMC
codegen has little effect.

---------------------------------

Timings, n = 100_000_000:
  GCC:  3.13 s
  DMD: 11.69 s


dmd -O -release -inline testd.d
gcc -O3 -s testc.c -o testc.exe

32 bit
GCC 4.5.2
DMD 2.052beta

---------------------------------

// D2 code
import std.c.stdio: printf;

int main() {
    uint total = 0;
    uint i;
    for (i = 0; i < 100000000; i++) {
        uint n = i;
        uint res = n % 10;
        n /= 10;
        while (n != 0) {
            res = (n % 10) + (10 * res);
            n /= 10;
        }
        total += res;
    }
    printf("%u\n", total); // 461784529
    return 0;
}

---------------------------------

// C code
#include "stdio.h"
typedef unsigned long uint;

int main() {
    uint total = 0;
    uint i;
    for (i = 0; i < 100000000; i++) {
        uint n = i;
        uint res = n % 10;
        n /= 10;
        while (n != 0) {
            res = (n % 10) + (10 * res);
            n /= 10;
        }
        total += res;
    }
    printf("%u\n", total); // 461784529
    return 0;
}

---------------------------------

DMD inner loop:

L1C:    lea    EBX,[EBX*4][EBX]
        mov    EAX,ESI
        mov    ECX,0Ah
        xor    EDX,EDX
        add    EBX,EBX
        div    ECX
        add    EBX,EDX
        test EAX,EAX
        mov    ESI,EAX
        jne    L1C

---------------------------------

GCC inner loop:

L7:
    movl    %ecx, %eax
    mull    %esi
    leal    (%ebx,%ebx,4), %ebx
    shrl    $3, %edx
    leal    (%edx,%edx,4), %eax
    addl    %eax, %eax
    subl    %eax, %ecx
    testl    %edx, %edx
    leal    (%ecx,%ebx,2), %ebx
    movl    %edx, %ecx
    jne    L7

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------