为什么 imul 用于乘以无符号数？
Why is imul used for multiplying unsigned numbers?
我编译了以下程序：
#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使用呢？
/编辑：使用 uint64_t 时，程序集类似：
0: 48 0f af ff imul rdi,rdi
4: 48 89 f8 mov rax,rdi
7: c3 ret
#include <stdint.h>
uint64_t fun0 ( uint32_t x )
{
return (uint64_t)x * (uint64_t)x;
}
uint64_t fun1 ( uint32_t x )
{
return ((uint64_t)x) * ((uint64_t)x);
}
uint64_t fun2 ( uint64_t x )
{
return (x * x);
}
0000000000000000 <fun0>:
0: 89 f8 mov %edi,%eax
2: 48 0f af c0 imul %rax,%rax
6: c3 retq
7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
e: 00 00
0000000000000010 <fun1>:
10: 89 f8 mov %edi,%eax
12: 48 0f af c0 imul %rax,%rax
16: c3 retq
17: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
1e: 00 00
0000000000000020 <fun2>:
20: 48 89 f8 mov %rdi,%rax
23: 48 0f af c7 imul %rdi,%rax
27: c3 retq
编辑
即使您指定所有 64 位无符号它也会生成相同的结果
0x00FF * 0x00FF = 0xFE01
0xFFFF * 0xFFFF = 0xFFFE0001
so
0xFF * 0xFF = 0x01
符号扩展对于低 64 位无关紧要，因此您可以将 imul 用于 8、16、32 和 64 位有符号或无符号操作数。
TL:DR：因为当我们不关心高半部分（即输出仅与 2 个输入一样宽）时，这是获得正确结果的更快方法。更灵活的寄存器分配，而不是强制使用 RAX 和 RDX。
如果它不能用于此，英特尔可能也会添加 mul 的双操作数版本。但这不是必需的，正如这个答案所解释的那样。
WARNING This answer is long!
...它充满了不必要的解释 - 但我一直想写一些关于乘法的更冗长的东西。
一点理论
当两个数 a 和 b 的长度相乘时 n 的结果是长度2 n† 最重要的是，第 k 位仅取决于 lowest k 位数（证明见附录A）.
x86 imul的两种形式
x86 乘法指令imul有两种形式：完整形式和部分形式。
第一种形式是n×n→2n，意思是它产生的结果是操作数大小的两倍——我们从理论上知道为什么这是有道理的。
例如
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 vs mul
无论使用何种形式，处理器总是计算结果的大小是操作数的两倍（即像第一种形式）。
为了能够做到这一点，操作数首先从它们的大小 n 转换为大小 2 n （例如从 64 位到 128 位） .
有关详细信息，请参阅附录 B。
乘法完成，全部或部分结果存储在目标中。
imul 和 mul 的区别在于操作数的转换方式。
由于大小被扩展，这种特殊类型的转换称为 extension.
mul 指令简单地用零填充上部 - 它零扩展。
imul 指令复制高位（左起第一个位）——这称为符号扩展，它具有有趣的 属性 转换 two's complement 符号 数量的 n 位变成一个 signed 数量的 2 n 位符号和模数（即它做了正确的事情，它留给 reader 来找到零扩展情况的反例）。
How mul extends How imul extends
an operand an 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 最多可以写入 1 个寄存器。）一个操作数 imul r32 在 Intel CPU 上是 3 uops：大概一个用于乘法，另一个用于将 64 位乘积分成两半并写入低一半，另一个对高一半做同样的事情。 imul r64 是 2 微指令；大概 128 位结果来自已经分成 64 位两半的乘法器。
mul 仍然只存在于非常古老的单操作数形式中，固定寄存器作为接口的一部分。
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> 是必需的，但这会产生 完整 结果！完整的 signed 结果通常不等于完整的 unsigned 结果。
事实上，编译器恢复为 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 (b j·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不能为负！
第二种情况类似，留给reader.
附录 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
此外，符号扩展可能也是概念上的。
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.
†长度为n的二进制数在2n的数量级，因此两个这样的数相乘的数量级为2n · 2n = 2n+n = 22n。就像一个长度为2的数n.
我编译了以下程序：
#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使用呢？
/编辑：使用 uint64_t 时，程序集类似：
0: 48 0f af ff imul rdi,rdi
4: 48 89 f8 mov rax,rdi
7: c3 ret
#include <stdint.h>
uint64_t fun0 ( uint32_t x )
{
return (uint64_t)x * (uint64_t)x;
}
uint64_t fun1 ( uint32_t x )
{
return ((uint64_t)x) * ((uint64_t)x);
}
uint64_t fun2 ( uint64_t x )
{
return (x * x);
}
0000000000000000 <fun0>:
0: 89 f8 mov %edi,%eax
2: 48 0f af c0 imul %rax,%rax
6: c3 retq
7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
e: 00 00
0000000000000010 <fun1>:
10: 89 f8 mov %edi,%eax
12: 48 0f af c0 imul %rax,%rax
16: c3 retq
17: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
1e: 00 00
0000000000000020 <fun2>:
20: 48 89 f8 mov %rdi,%rax
23: 48 0f af c7 imul %rdi,%rax
27: c3 retq
编辑
即使您指定所有 64 位无符号它也会生成相同的结果
0x00FF * 0x00FF = 0xFE01
0xFFFF * 0xFFFF = 0xFFFE0001
so
0xFF * 0xFF = 0x01
符号扩展对于低 64 位无关紧要，因此您可以将 imul 用于 8、16、32 和 64 位有符号或无符号操作数。
TL:DR：因为当我们不关心高半部分（即输出仅与 2 个输入一样宽）时，这是获得正确结果的更快方法。更灵活的寄存器分配，而不是强制使用 RAX 和 RDX。
如果它不能用于此，英特尔可能也会添加 mul 的双操作数版本。但这不是必需的，正如这个答案所解释的那样。
WARNING This answer is long!
...它充满了不必要的解释 - 但我一直想写一些关于乘法的更冗长的东西。
一点理论
当两个数 a 和 b 的长度相乘时 n 的结果是长度2 n† 最重要的是，第 k 位仅取决于 lowest k 位数（证明见附录A）.
x86 imul的两种形式
x86 乘法指令imul有两种形式：完整形式和部分形式。
第一种形式是n×n→2n，意思是它产生的结果是操作数大小的两倍——我们从理论上知道为什么这是有道理的。
例如
imul ax ;16x16->32, Result is dx:ax
imul rax ;64x64->128, Result is rdx:rax
第二种形式是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 vs mul
无论使用何种形式，处理器总是计算结果的大小是操作数的两倍（即像第一种形式）。
为了能够做到这一点，操作数首先从它们的大小 n 转换为大小 2 n （例如从 64 位到 128 位） .
有关详细信息，请参阅附录 B。
乘法完成，全部或部分结果存储在目标中。
imul 和 mul 的区别在于操作数的转换方式。
由于大小被扩展，这种特殊类型的转换称为 extension.
mul 指令简单地用零填充上部 - 它零扩展。
imul 指令复制高位（左起第一个位）——这称为符号扩展，它具有有趣的 属性 转换 two's complement 符号 数量的 n 位变成一个 signed 数量的 2 n 位符号和模数（即它做了正确的事情，它留给 reader 来找到零扩展情况的反例）。
How mul extends How imul extends
an operand an 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 最多可以写入 1 个寄存器。）一个操作数 imul r32 在 Intel CPU 上是 3 uops：大概一个用于乘法，另一个用于将 64 位乘积分成两半并写入低一半，另一个对高一半做同样的事情。 imul r64 是 2 微指令；大概 128 位结果来自已经分成 64 位两半的乘法器。
mul 仍然只存在于非常古老的单操作数形式中，固定寄存器作为接口的一部分。
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> 是必需的，但这会产生 完整 结果！完整的 signed 结果通常不等于完整的 unsigned 结果。
事实上，编译器恢复为 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 (b j·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不能为负！
第二种情况类似，留给reader.
附录 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
此外，符号扩展可能也是概念上的。
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.
†长度为n的二进制数在2n的数量级，因此两个这样的数相乘的数量级为2n · 2n = 2n+n = 22n。就像一个长度为2的数n.