c - 我如何指示 MSVC 编译器使用 64 位/32 位除法而不是较慢的 128 位/64 位除法？

Question

如何告诉 MSVC 编译器使用 64 位/32 位除法运算为 x86-64 目标计算以下函数的结果:

#include <stdint.h> 

uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
  if (a > b)
        return ((uint64_t)b<<32) / a;   //Yes, this must be casted because the result of b<<32 is undefined
  else
        return uint32_t(-1);
}

我希望代码在 if 语句为真时编译为使用 64 位/32 位除法运算，例如像这样:

; Assume arguments on entry are: Dividend in EDX, Divisor in ECX
mov edx, edx  ;A dummy instruction to indicate that the dividend is already where it is supposed to be
xor eax,eax
div ecx   ; EAX = EDX:EAX / ECX

...然而x64 MSVC编译器坚持使用128bit/64bit的div指令，例如:

mov     eax, edx
xor     edx, edx
shl     rax, 32                             ; Scale up the dividend
mov     ecx, ecx
div rcx   ;RAX = RDX:RAX / RCX

参见:https://www.godbolt.org/z/VBK4R7 1

根据this question的回答，128 位/64 位 div 指令并不比 64 位/32 位 div 指令快。

这是一个问题，因为它不必要地减慢了我的 DSP 算法，该算法进行了数百万个这样的缩放除法。

我通过修补可执行文件以使用 64 位/32 位 div 指令来测试此优化:根据 rdtsc 指令产生的两个时间戳，性能提高了 28%。

(编者注:大概在最近的一些 Intel CPU 上。AMD CPU 不需要这种微优化，如链接的问答中所述。)

Answer 1

当前的编译器 (gcc/clang/ICC/MSVC) 不会从可移植的 ISO C 源代码进行这种优化，即使您让它们证明 b < a所以商将适合 32 位。 (例如 GNU C if(b>=a) __builtin_unreachable(); on Godbolt )。这是一个错过的优化；在解决这个问题之前，您必须使用内部函数或内联 asm 来解决它。

(或者改用 GPU 或 SIMD；如果您对许多元素有相同的除数，请参阅 https://libdivide.com/ SIMD 计算一次乘法逆并重复应用它。)

---

_udiv64 is available从 Visual Studio 2019 RTM 开始。

在 C 模式 ( -TC ) 中，它显然总是被定义的。在 C++ 模式下，您需要 #include <immintrin.h> ，根据 Microsoft 文档。或 intrin.h .

https://godbolt.org/z/vVZ25L (或者 on Godbolt.ms 因为 Godbolt 主站点上最近的 MSVC 不工作¹。)

#include <stdint.h>
#include <immintrin.h>       // defines the prototype

// pre-condition: a > b else 64/32-bit division overflows
uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
    uint32_t remainder;
    uint64_t d = ((uint64_t) b) << 32;
    return _udiv64(d, a, &remainder);
}

int main() {
    uint32_t c = ScaledDiv(5, 4);
    return c;
}

_udiv64 将产生 64/32 格。左右两个移位是一个遗漏的优化。

;; MSVC 19.20 -O2 -TC
a$ = 8
b$ = 16
ScaledDiv PROC                                      ; COMDAT
        mov     edx, edx
        shl     rdx, 32                             ; 00000020H
        mov     rax, rdx
        shr     rdx, 32                             ; 00000020H
        div     ecx
        ret     0
ScaledDiv ENDP

main    PROC                                            ; COMDAT
        xor     eax, eax
        mov     edx, 4
        mov     ecx, 5
        div     ecx
        ret     0
main    ENDP

所以我们可以看到 MSVC 不会通过 _udiv64 进行持续传播, 即使在这种情况下它没有溢出并且它可能已经编译了 main只是mov eax, 0ccccccccH/ret .

---

更新#2 https://godbolt.org/z/n3Dyp-添加了英特尔 C++ 编译器的解决方案，但这效率较低，并且会破坏常量传播，因为它是内联 asm。

#include <stdio.h>
#include <stdint.h>

__declspec(regcall, naked) uint32_t ScaledDiv(uint32_t a, uint32_t b) 
{
    __asm mov edx, eax
    __asm xor eax, eax
    __asm div ecx
    __asm ret
    // implicit return of EAX is supported by MSVC, and hopefully ICC
    // even when inlining + optimizing
}

int main()
{
    uint32_t a = 3 , b = 4, c = ScaledDiv(a, b);
    printf( "(%u << 32) / %u = %u\n", a, b, c);
    uint32_t d = ((uint64_t)a << 32) / b;
    printf( "(%u << 32) / %u = %u\n", a, b, d);
    return c != d;
}

---

脚注 1:Matt Godbolt 的主要站点的非 WINE MSVC 编译器暂时(？)消失了。微软运行https://www.godbolt.ms/在真正的 Windows 上托管最近的 MSVC 编译器，并且通常主要的 Godbolt.org 站点中继到 MSVC。)

godbolt.ms 似乎会生成短链接，但不会再次扩展它们!无论如何，完整链接更好，因为它们可以抵抗链接失效。