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

Question

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

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位上输了很多,编译器确实使用乘法逆,以避免完全缓慢的硬件划分. 为什么GCC在实现整数除法时使用乘以一个奇数？

此外,__builtin_constant_p如果在内联和常量传播之后任一输入不是编译时常量,它应该真正用于仅使用内联asm.

但无论如何,x86的div指令确实EDX:EAX / (src)=>商(EAX)和除数(EDX).看我们何时以及为什么签署扩展并使用cdq与mul/div？

这些"a"和"d"约束分别要求EAX和EDX中64位产品的低半部分和高半部分作为输入.

来自Godbolt编译器资源管理器:

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或将输入转换为unsigned.或者也许他们真的想要一些奇怪的原因带有负面输入的奇怪结果.

那么为什么编译器不能在没有内联asm的情况下自行发出这个呢？因为如果商溢出目标寄存器(al/ax/eax/rax),它会出现#DE(Divide Exception)而不是像所有其他整数指令一样静默截断.

只有当你知道除数足够大才能获得可能的红利时,64位/ 32位=> 32位除法才是安全的.(但即使是这样,GCC仍然不知道找这种优化.例如,a * 7ULL / 9不可能引起#DE如果与单做mul和div,如果a是一个32位的类型.但GCC仍然会发出一个电话一个libgcc帮助函数.)