为什么imul用于乘以无符号数？

Question

我编译了以下程序:

#include <stdint.h>

uint64_t usquare(uint32_t x) {
  return (uint64_t)x * (uint64_t)x;
}

这拆解为:

 0: 89 f8                   mov    eax,edi
 2: 48 0f af c0             imul   rax,rax
 6: c3                      ret  

但是imul用于乘以有符号数字的指令.那为什么用gcc呢？

/ edit:使用uint64_t程序集时类似:

0:  48 0f af ff             imul   rdi,rdi
4:  48 89 f8                mov    rax,rdi
7:  c3                      ret  

Answer 1

警告 这个答案很长!

......而且它充满了不必要的解释 - 但我一直想写一些关于乘法的更长的内容.

一点理论

当乘以两个长度为n的数字a和b时,结果的长度为2 n ^†,最重要的是,第k个数字仅取决于最低的k位数(附录A中给出了证明).

x86 mul的两种形式

x86乘法指令imul有两种形式:完整形式和部分形式.

第一种形式是n × n →2 n,这意味着它产生的结果是操作数的两倍 - 我们从理论中知道为什么这是有意义的.
例如

imul ax         ;16x16->32, Result is dx:ax
imul rax        ;64x64->128, Result is rdx:rax 

第二种形式是n × n → n,这必然会削减一些信息.
特别是,这种形式只占用结果的低 n 位.

imul ax, ax          ;16x16->16, Lower WORD of the result is ax
imul rax, rax        ;64x64->64, Lower QWORD of the result is rax 

只有单个操作数版本是第一种形式.

两条指令:imulvsimul r64, r/m64, imm8/32

无论使用何种形式,处理器总是以两倍于操作数的大小计算结果(即像第一种形式一样).
为了能够这样做,首先将操作数从它们的大小n转换为大小为2n(例如,从64到128位).
有关详细信息,请参阅附录B.

乘法完成,完整或部分结果存储在目标中.

imul r64, r/m64和之间的区别在于dst *= src操作数的转换方式.
由于大小已扩展,因此这种特殊类型的转换称为扩展.

该imul指令简单地用零填充上部-它零延伸.
该mul指令复制高阶位(左一) -这被称为符号扩展,并具有把一个有趣的财产补 签署的数ñ位转换成签订的2号Ñ位有相同的符号和模数(即它做正确的事情,留给读者找到零延伸情况的反例).

     How mul extends              How imul extends       
       and operand                  and operand

     +----+       +----+          +----+       +----+
     |0...|       |1...|          |0...|       |1...|
     +----+       +----+          +----+       +----+  

+----+----+  +----+----+     +----+----+  +----+----+
|0000|0...|  |0000|1...|     |0000|0...|  |1111|1...|
+----+----+  +----+----+     +----+----+  +----+----+

论文

imul和之间的差异mul仅从第(n + 1)位向前看.
对于32位操作数,这意味着只有完整结果的高32位部分最终会有所不同.

这是很容易看到作为下ñ位为两个指令一样,当我们从理论上知道的第一ñ结果的位只依赖于第一ñ操作数位.

因此论文:部分形式的结果mul与其相同imul.

那为什么imul退出？
因为它更灵活 - 它有两个或三个操作数,同时mul具有非常古老的界面.
因为它根据有符号乘法设置标志 - 如果部分结果丢弃了任何重要信息(技术条件是:部分结果的符号扩展与完整结果不同),则设置CF和OF,如果溢出.
这也是为什么不调用两个和三个操作数形式的原因imul,否则它们将是一个非常合适的名称.

实践

为了在实践中测试所有这些,我们可以请求编译器^{[ live ]}来组装以下程序

#include <stdint.h>

uint64_t foo(uint32_t a)
{
    return a*(uint64_t)a;
}

虽然我们知道对于64位目标,生成的代码使用mul是因为imul适合寄存器,因此可以使用64×64→64乘法mul

foo(unsigned int):
        mov     eax, edi        ;edi = a
        imul    rax, rax        ;64x64->64
        ret

在32位代码中没有使用这样的乘法imul.
A imul或imul r32必要但会产生完整的结果!完整的签名结果通常不等于完整的无符号结果.
事实上,编译器恢复为imul r64:

foo(unsigned int):
        mov     eax, DWORD PTR [esp+4]
        mul     eax
        ret

附录A.

不失一般性,我们可以假设基数2并且数字是n + 1位长(因此索引从0到n) - 然后

c = a·b =Σi _{= 0..n}(a _i ·2 ⁱ)·Σj _{= 0..n}(b _j ·2 ^j)=Σi _{= 0..n} [a _i ·Σj _{= 0..n}(b _j ·2 ^{i + j})](按分配属性)

我们看到结果的第k个数字是所有加数的总和,使得i + j = k加上最终的进位

c _k =Σi _{,j = 0..n; i + j = k} a _i ·b _j ·2 ^{i + j} + C _k

术语C _k是咖喱,并且当它向更高位传播时,它仅取决于较低位.
第二项不能有a _i或b _j与i或j > k,好像第一个为真,然后i = k + e,对于正,非零,e因此j = k - i = k - k - e = - e
但j不能为负!
第二种情况类似,留给读者.

附录B.

正如BeeOnRope在评论中指出的那样,如果仅需要部分结果,则处理器可能不会计算完整结果.

从概念上讲,这可能意味着这只是一种思考它的方式.使用64x64 - > 64表格时,处理器不一定要进行完整的128位乘法运算.实际上,截断形式在最近的英特尔上只占用了1个,但是完整形式需要2个uop,因此正在进行一些额外的工作

来自BeeOnRope的评论

此外,符号扩展可能在概念上也是如此

类似地,符号扩展可以"概念上"发生,但可能不在硬件中.他们不会有额外的电线和晶体管只是为了做符号或零延伸,这会给已经巨大的乘数增加很多体积,但是会使用其他一些技巧来进行乘法"仿佛".

来自BeeOnRope的评论

^†长度为n的二进制数的数量级为2 ⁿ,因此两个这样的数的乘积大小为2 ⁿ ·2 ⁿ = 2 ^{n + n} = 2 ^{2 n}.就像一些长度2 n.