Emit DIV instruction, instead of __udivti3

user_1037407 0
Viewed 630

Consider the following code:

unsigned long long div(unsigned long long a, unsigned long long b, unsigned long long c) {
    unsigned __int128 d = (unsigned __int128)a*(unsigned __int128)b;
    return d/c;
}

When compiled with x86-64 gcc 10 or clang 10, both with -O3, it emits __udivti3, instead of DIVQ instruction:

div:
    mov     rax, rdi
    mov     r8, rdx
    sub     rsp, 8
    xor     ecx, ecx
    mul     rsi
    mov     r9, rax
    mov     rsi, rdx
    mov     rdx, r8
    mov     rdi, r9
    call    __udivti3
    add     rsp, 8
    ret

At least in my testing, the former is much slower than the (already) slow later, hence the question: is there a way to make a modern compiler emit DIVQ for the above code?

Edit: Let's assume the quotient fits into 64-bits register.

x86-64 clang gcc optimization c
1 Answers

div will fault if the quotient doesn't fit in 64 bits. Doing (a*b) / c with mul + a single div isn't safe in the general case (doesn't implement the abstract-machine semantics for every possible input), therefore a compiler can't generate asm that way for x86-64.

Even if you do give the compiler enough info to figure out that the division can't overflow (i.e. that high_half < divisor), unfortunately gcc/clang still won't ever optimize it to single a div with a non-zero high-half dividend (RDX).

You need an intrinsic or inline asm to explicitly do 128 / 64-bit => 64-bit division. e.g. Intrinsics for 128 multiplication and division has GNU C inline asm that looks right for low/high halves separately.

Unfortunately GNU C doesn't have an intrinsic for this. MSVC does, though: Unsigned 128-bit division on 64-bit machine has links.

user_2241320
Related