c++ - 在c++中使用x86 DIV的asm block 有什么用？

Question

有人可以帮助我了解使用 asm block 进行unsigned long long 乘法在性能方面的好处吗？它与竞争性编程优化有关。我猜它会使乘法更快，但我实际上无法理解代码。

const int md = 998244353;
inline int mul(int a, int b)
{
#if !defined(_WIN32) || defined(_WIN64)
    return (int) ((long long) a * b % md);
#endif
    unsigned long long x = (long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm(
            "divl %4; \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (md)
    );
    return m;
}

Answer 1

这段代码实际上是 32 位的加速(其中 64x64 => 128 乘法不可用，因此编译器使用实际除法，但在 64 位上损失惨重，编译器确实使用乘法逆来完全避免缓慢的硬件除法. Why does GCC use multiplication by a strange number in implementing integer division?

此外，它确实应该使用 __builtin_constant_p仅在内联和常量传播之后任一输入不是编译时常量时才使用内联 asm。

---

但无论如何，x86's div instruction确实EDX:EAX / (src) => 商(EAX) 和除数(EDX)。请参阅When and why do we sign extend and use cdq with mul/div?

"a"和"d"约束要求 EAX 和 EDX 中的 64 位乘积的低半部分和高半部分分别作为输入。

来自Godbolt compiler explorer :

const int md = 998244353;
int mul(int a, int b)
{
#ifdef __x86_64__ // FIXME: just use the asm if defined(i386) to exclude all others
    return (int) ((long long) a * b % md);
#else
    if(__builtin_constant_p(a) && __builtin_constant_p(b))
        return (int) ((long long) a * b % md);
      // clang's builtin_constant_p is evaled before inlining, derp

    unsigned long long x = (long long) a * b;
    unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
    asm(
            "divl %4; \n\t"
            : "=a" (d), "=d" (m)
            : "d" (xh), "a" (xl), "r" (md)
    );
    return m;
#endif
}

int main() {
    return mul(1,2);
}

编译如下 gcc8.2 -O3 -m32 :

mul(int, int):
    mov     eax, DWORD PTR [esp+8]
    mov     ecx, 998244353
    imul    DWORD PTR [esp+4]     # one-operand imul does EDX:EAX = EAX * src
    divl ecx;                     # EDX:EAX / ecx => EAX and EDX

    mov     eax, edx              # return the remainder
    ret

main:
    mov     eax, 2     # builtin_constant_p used the pure C, allowing constant-propagation
    ret

请注意 div是无符号除法，所以这与C不匹配。C正在执行有符号乘法和有符号除法。这可能应该使用idiv ，或将输入转换为无符号。或者也许他们确实想要由于某种奇怪的原因而产生负面输入的奇怪结果。

那么为什么编译器不能在没有内联汇编的情况下自己发出这个？因为如果商溢出目标寄存器 (al/ax/eax/rax)，则会出现 #DE(除法异常)错误，而不是像所有其他整数指令一样默默地截断。

仅当您知道除数对于可能的除数而言足够大时，64 位/32 位 => 32 位除法才是安全的。 (但即使是这样，gcc仍然不知道寻找这种优化。例如，如果使用单个 a * 7ULL / 9 和 mul 完成， div 不可能导致 #DE ，如果 a 是 32 -bit 类型。但是 gcc 仍然会发出对 libgcc 辅助函数的调用。)