clang-cl does not support MSVC x86(64) div intrinsics

[davidben]

MSVC has intrinsics corresponding to the x86 DIV instruction:
https://learn.microsoft.com/en-us/cpp/intrinsics/udiv64?view=msvc-170
https://learn.microsoft.com/en-us/cpp/intrinsics/udiv128?view=msvc-170
https://learn.microsoft.com/en-us/cpp/intrinsics/div64?view=msvc-170
https://learn.microsoft.com/en-us/cpp/intrinsics/div128?view=msvc-170

These operations (well, the unsigned ones) are useful in implementing big integer arithmetic. Sadly, clang-cl does not seem to support them. (I'm having to special-case clang-cl from MSVC in some code right now.)

Even with a clang-cl special case, these are not easily accessible from LLVM without inline asm, from what I can tell, because the x86 instructions trap when the quotient doesn't fit in a single word. A priori, trying to divide, say, uint128_t by uint64_t may give a 128-bit result.

[johnplatts]

Here is how the MSVC div intrinsics can be implemented as static inline functions for Clang:

static __inline__ int __DEFAULT_FN_ATTRS _div64(int highDividend,
                                                int lowDividend, int divisor,
                                                int *remainder) {
  unsigned __int64 dividend =
      (unsigned __int64)(((unsigned __int64)((unsigned int)highDividend)
                          << 32) |
                         (unsigned __int64)((unsigned int)lowDividend));
  unsigned __int64 q = dividend / (unsigned __int64)divisor;
  __builtin_assume(q >= -0x80000000LL && q <= 0x7FFFFFFFLL);
  *remainder = dividend % (unsigned __int64)divisor;
  return (int)q;
}

static __inline__ unsigned int __DEFAULT_FN_ATTRS
_udiv64(unsigned int highDividend, unsigned int lowDividend,
        unsigned int divisor, unsigned int *remainder) {
  unsigned __int64 dividend =
      ((unsigned __int64)highDividend << 32) | (unsigned __int64)lowDividend;
  unsigned __int64 q = dividend / (unsigned __int64)divisor;
  __builtin_assume(q <= (unsigned __int64)0xFFFFFFFFULL);
  *remainder = dividend % (unsigned __int64)divisor;
  return (int)q;
}

#if defined(__SIZEOF_INT128__)
static __inline__ unsigned __int64 __DEFAULT_FN_ATTRS
_div128(unsigned __int64 highDividend, unsigned __int64 lowDividend,
        unsigned __int64 divisor, unsigned __int64 *remainder) {
  __int128_t dividend =
      (__int128_t)(((__uint128_t)((unsigned __int64)highDividend) << 64) |
                   (__uint128_t)((unsigned __int64)lowDividend));
  __int128_t q = dividend / (__int128_t)divisor;
  __builtin_assume(q >= (__int128_t)((unsigned __int64)0x8000000000000000ULL) &&
                   q <= (__int128_t)0x7FFFFFFFFFFFFFFFULL);
  *remainder = dividend % (__int128_t)divisor;
  return (unsigned __int64)q;
}

static __inline__ unsigned __int64 __DEFAULT_FN_ATTRS
_udiv128(unsigned __int64 highDividend, unsigned __int64 lowDividend,
         unsigned __int64 divisor, unsigned __int64 *remainder) {
  __uint128_t dividend =
      ((__uint128_t)highDividend << 64) | (__uint128_t)lowDividend;
  __uint128_t q = dividend / (__uint128_t)divisor;
  __builtin_assume(q <= (__uint128_t)0xFFFFFFFFFFFFFFFFULL);
  *remainder = dividend % (__uint128_t)divisor;
  return (unsigned __int64)q;
}
#endif

There is suboptimal code being generated for the above division routines with Clang according to a snippet over at https://godbolt.org/z/K999bnbEr.

Here is the assembly code that is expected to be generated from the snippet at https://godbolt.org/z/K999bnbEr (due to the assumptions made through __llvm_assume calls in the snippet at https://godbolt.org/z/K999bnbEr) on Linux on x86_64 (taken from an equivalent snippet at https://godbolt.org/z/Tq8YPabYY):

Msvc_div64:
        mov     r8d, edx
        mov     eax, esi
        mov     edx, edi
        idiv    r8d
        mov     dword ptr [rcx], edx
        ret

Msvc_udiv64:
        mov     r8d, edx
        mov     eax, esi
        mov     edx, edi
        div     r8d
        mov     dword ptr [rcx], edx
        ret

Msvc_div128:
        mov     r8, rdx
        mov     rax, rsi
        mov     rdx, rdi
        idiv    r8
        mov     qword ptr [rcx], rdx
        ret

Msvc_udiv128:
        mov     r8, rdx
        mov     rax, rsi
        mov     rdx, rdi
        div     r8
        mov     qword ptr [rcx], rdx
        ret