Tricks编译器用于编译128位整数的基本算术运算

Question

我玩GodBolt看x86-64 gcc(6.3)编译以下代码:

typedef __int128_t int128_t;
typedef __uint128_t uint128_t;

uint128_t mul_to_128(uint64_t x, uint64_t y) {
  return uint128_t(x)*uint128_t(y);
}
uint128_t mul(uint128_t x, uint128_t y) {
  return x*y;
}
uint128_t div(uint128_t x, uint128_t y) {
  return x/y;
}

我得到了:

mul_to_128(unsigned long, unsigned long):
        mov     rax, rdi
        mul     rsi
        ret
mul(unsigned __int128, unsigned __int128):
        imul    rsi, rdx
        mov     rax, rdi
        imul    rcx, rdi
        mul     rdx
        add     rcx, rsi
        add     rdx, rcx
        ret
div(unsigned __int128, unsigned __int128):
        sub     rsp, 8
        call    __udivti3 //what is this???
        add     rsp, 8
        ret

3个问题:

1. 第一个函数(铸造64-bituint 128-bit然后乘以它们)比2个128位uints(第二个函数)的乘法要简单得多.基本上只需1次乘法.如果你将2位最大值的64位uint相乘,它肯定会溢出64位寄存器...它如何通过1位64位64位乘法产生128位结果？
2. 我不能很好地阅读第二个结果...我的猜测是将64位数字分解为2个32位数字(比如说,hi更高的4个字节和lo更低的4个字节),并将结果组合起来 (hi1*hi2)<<64 + (hi1*lo2)<<32 + (hi2*lo1)<<32+(lo1*lo2).显然我错了...因为它只使用了3次乘法(其中2次甚至是imul......有符号乘法???为什么???).谁能告诉我gcc在想什么？它是最佳的？
3. 甚至无法理解分区的组装...推送堆栈 - >调用一些名为__udivti3pop pop的__udivti3东西......是什么大事？(比如查表？)以及gcc在调用之前尝试推送的内容是什么？

godbolt链接:https://godbolt.org/g/sIIaM3

Answer 1

你是对的,将两个无符号的64位值相乘可以产生128位的结果.有趣的是,硬件设计师也知道这一点.<g>因此,将两个64位值相乘可以将结果的下半部分存储在一个64位寄存器中,将结果的上半部分存储在另一个64位寄存器中,从而产生128位结果.编译器 - 写入器知道使用了哪些寄存器,并且在调用mul_to_128它时将在适当的寄存器中查找结果.

在第二个示例中,将值视为a1*2^64 + a0和b1*2^64 + b0(即将每个128位值拆分为两部分,即高64位和低64位).当你乘以那些时a1*b1*2^64*2^64 + a1*b0*2^64 + a0*b1*2^64 + a0*b0.这基本上就是汇编代码正在做的事情.溢出128位的结果部分将被忽略.

在第三个例子中,__udivti3是一个进行除法的函数.它并不简单,因此不会内联扩展.