assembly - 为什么 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 时 assembly 是类似的:

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

Answer 1

TL:DR:因为当我们不关心上半部分(即输出仅与 2 个输入一样宽)时，这是获得正确结果的更快方法。更灵活的寄存器分配，而不是强制使用 RAX 和 RDX。

如果它不能用于此，英特尔可能会添加 mul 的两个操作数版本。以及。但这不是必需的，正如这个答案所解释的那样。

WARNING This answer is long!

... and it's full of unneeded explanations - but I have always wanted to write something more lengthy about the multiplication.

一点理论

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

x86 imul 的两种形式

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 

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

(还有一个 3 操作数形式， imul r64, r/m64, imm8/32 ，它允许您在一条指令中复制并乘以一个常量。它没有隐式操作数，并且同样不会在任何地方写入高半，所以我们可以处理它等同于 imul r64, r/m64 dst *= src 形式。)

两条指令: imul对比 mul

无论使用哪种形式，处理器总是以两倍于操作数的大小计算结果(即与第一种形式一样)。
为了能够做到这一点，操作数首先从它们的大小 n 转换为大小 2 n(例如，从 64 位到 128 位)。
有关这方面的更多信息，请参见附录 B。

乘法完成，完整或部分结果存储在目标中。
imul的区别和 mul在于操作数的转换方式。
由于大小被扩展，这种特殊类型的转换被称为 extension .
mul指令只是用零填充上部 - 它零扩展。 imul指令复制高位(左起第一个) - 这称为符号扩展，它具有转换 two's complement 的有趣特性。将 n 位的有符号数转换为具有相同符号和模数的 2 n 位有符号数(即它做正确的事情，留给读者找到零扩展情况的反例)。

     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 位部分会有所不同。

这很容易看出，因为两个指令的低 n 位是相同的，正如我们从理论中知道的，结果的前 n 位仅取决于操作数的前 n 位。

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

那为什么imul退出？

原始 8086 只有 mul 的单操作数版本和 imul . x86 的更高版本添加了更灵活的二和三操作数版本 imul仅适用于您不想要双宽结果的常见用例。

他们只写一个输出寄存器，这对于现代 x86 意味着他们可以解码为单个 uop: https://agner.org/optimize/ . (在现代 x86 微体系结构中，每个 uop 最多可以写入寄存器。)一个操作数 imul r32在英特尔 CPU 上是 3 个 uops:大概是一个乘法，另一个将 64 位产品分成两半并写入低半部分，另一个对高半部分做同样的事情。 imul r64是 2 uop；大概 128 位结果来自已经分成 64 位一半的乘法器。
mul仍然只以非常古老的单操作数形式存在，固定寄存器作为接口(interface)的一部分。
imul根据有符号乘法设置标志 - 如果部分结果丢弃了任何重要信息(技术条件是:部分结果的符号扩展与完整结果不同)，则设置 CF 和 OF，例如在溢出的情况下。
这也是为什么不叫二操作数和三操作数形式 mul的原因。 ，否则这将是一个非常合适的名称。

实践

为了在实践中测试所有这些，我们可以询问编译器[ live ] 用于汇编以下程序

#include <stdint.h>

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

虽然我们知道对于 64 位目标，生成的代码使用 imul因为一个 unint64_t适合一个寄存器，因此 64×64→64 乘法可用作 imul <reg64>, <reg64>

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

在 32 位代码中，没有使用 imul 的这种乘法。 . imul <reg32>或 imul <reg32>, <reg32>, <reg32>是必要的，但这会产生完整的结果!并且完整的有符号结果通常不等于完整的无符号结果。
事实上，编译器恢复到 mul :

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

附录 A

不失一般性，我们可以假设基数为 2 并且数字的长度为 n + 1 位(因此索引从 0 到 n) - 那么

c = a·b = ∑i=0..n (ai·2i) · ∑j=0..n(bj·2j) =
∑i=0..n [ai·∑j=0..n (bj·2i+j)](由分配性质)

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

ck = ∑i,j=0..n; i+j=k ai·bj·2i+j + Ck

术语 Ck 是进位，当它向高位传播时，它只取决于低位。
第二项不能有 ai 或 bj，其中 i 或 j > k 就好像第一项为真那么 i = k + e，对于正的非空 e，因此 j = k - i = k - k -e = -e
但是 j 不能为负!
第二种情况类似，留给读者。

附录 B

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

You probably means that this is only a way of thinking about it, conceptually. The processor does not necessarily do a full 128-bit multiplication when you use the 64x64 -> 64 form. Indeed, the truncated form takes only 1 uop on recent Intel, but the full form takes 2 uops, so some extra work is being done

Comment from BeeOnRope

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

Similarly the sign extension may happens "conceptually", but probably not in hardware. They won't have the extra wires and transistors just to do the sign or zero extension, which would add a lot of bulk to an already huge multiplier, but will use some other tricks to do the multiplication "as if" that had happened.

Comment from BeeOnRope

† 长度为 n 的二进制数的数量级为 2n，因此两个这样的数字相乘的数量级为 2n · 2n = 2n+n = 22 n。就像一个长度为 2 n 的数字。