与2008/2010年相比的x86 MUL指令

imul (签字)和 mul (无符号)都有一个单操作数形式 edx:eax = eax * src . 即32x32b=>64b全乘(或64x64b=>128b)。

286 added an imul dest(reg), src(reg/mem), immediate 表格,386添加了一个 imul r32, r/m32 形式,两者都只计算结果的下半部分。(链接自 x86 标记wiki)。

当将两个32位值相乘时,结果的最低有效32位是相同的,无论您认为这些值是有符号的还是无符号的。换句话说,只有当你看到结果的上半部分时,有符号乘法和无符号乘法的区别才变得明显,其中一个操作数 伊穆尔 / 穆尔 放入 edx 和两个或三个操作数 伊穆尔 无处可去。因此,多操作数形式 伊穆尔 可用于有符号值和无符号值,并且不需要Intel添加 穆尔 也。(他们可以做多个操作数 穆尔 的同义词 伊穆尔 ,但这会使反汇编输出与源不匹配。)

在C语言中,算术运算的结果与操作数具有相同的类型(在对窄整数类型进行整数提升之后)。如果你乘以二 int 一起,你会得到一个 int ,不是 long long :不保留“上半部分”。因此,C编译器只需要 伊穆尔 提供,并且自 伊穆尔 比 穆尔 ,C编译器使用 伊穆尔 为了避免需要 mov 数据进出说明 eax .

作为第二步,因为C编译器使用多操作数形式 伊穆尔 很多时候,英特尔和AMD都在努力使之尽可能快。它只写一个输出寄存器,而不是 e/rdx:e/rax 因此,CPU可以比单操作数形式更容易地对其进行优化。这使得 伊穆尔 更具吸引力。

单操作数形式 穆尔 / 伊穆尔 在实现大数运算时很有用。在C中,在32位模式下,您应该得到一些 穆尔 按倍数调用 unsigned long long 价值观在一起。但是,根据编译器和操作系统的不同, 穆尔 操作码可能隐藏在某些专用功能中,因此您不必看到它们。在64位模式下, 长-长 只有64位,而不是128位,编译器将简单地使用 伊穆尔 .

x86上有三种不同类型的乘法指令。第一个是 MUL reg ,它执行无符号乘法 EAX 并将(64位)结果放入 EDX:EAX . 第二个是 IMUL reg 与有符号乘法的情况相同。第三种是 IMUL reg1, reg2 (将reg1与reg2相乘,并将32位结果存储到reg1中)或 IMUL reg1, reg2, imm (将reg2乘以imm,并将32位结果存储到reg1中)。

由于在C语言中,两个32位值的乘法产生32位结果,编译器通常使用第三种类型(签名不重要,低32位在有符号和无符号32x32乘法之间一致)。VC++将生成 MUL / IMUL 如果实际使用完整的64位结果,例如:

unsigned long long prod(unsigned int a, unsigned int b)
{
  return (unsigned long long) a * b;
}

的2个操作数(和3个操作数)版本 伊穆尔 比单操作数版本更快,因为它们不会产生完整的64位结果。宽乘法器既大又慢;如果需要,可以更容易地构建较小的乘法器并使用微码合成长乘法器。此外,mul/imul写入两个寄存器,通常通过在内部将其分解为多个指令来解决这一问题——指令重新排序硬件更容易跟踪每个寄存器写入一个寄存器的两个相关指令(大多数x86指令看起来像Internally)而不是跟踪写入两条指令的一条指令。

根据 http://gmplib.org/~tege/x86-timing.pdf , the IMUL 指令具有较低的延迟和较高的吞吐量(如果我正确读取表)。也许vs只是使用更快的指令(假设 伊穆尔 和 MUL 总是产生相同的输出)。

我手边没有Visual Studio,所以我尝试用GCC来获取其他东西。我也经常得到一些变化 伊穆尔 .

这是:

unsigned int func(unsigned int a, unsigned int b)
{ 
    return a * b;
}

组装到此(使用-o2):

_func:
LFB2:
        pushq   %rbp
LCFI0:
        movq    %rsp, %rbp
LCFI1:
        movl    %esi, %eax
        imull   %edi, %eax
        movzbl  %al, %eax
        leave
        ret

我的直觉告诉我编译器选择了 IMUL 任意地(或两者中更快的一个),因为不管使用无符号,位都是相同的 MUL 或签署 伊穆尔 . 任何32位整数乘法都是跨越两个寄存器的64位, EDX:EAX . 溢出进入 EDX 因为我们只关心32位结果 EAX . 使用 伊穆尔 将签名扩展到 电子数据交换 如有必要,但我们不在乎,因为我们只对32位结果感兴趣。

在我研究了这个问题之后,我发现在划分时生成的代码中存在mulq。

完整的代码将一个大的二进制数转换成十亿个块,这样它就可以很容易地转换成字符串。

C++代码:

for_each(TempVec.rbegin(), TempVec.rend(), [&](Short & Num){
    Remainder <<= 32;
    Remainder += Num;
    Num = Remainder / 1000000000;
    Remainder %= 1000000000;//equivalent to Remainder %= DecimalConvert
});

优化生成的程序集

00007FF7715B18E8  lea         r9,[rsi-4]  
00007FF7715B18EC  mov         r13,12E0BE826D694B2Fh  
00007FF7715B18F6  nop         word ptr [rax+rax] 
00007FF7715B1900  shl         r8,20h  
00007FF7715B1904  mov         eax,dword ptr [r9]  
00007FF7715B1907  add         r8,rax  
00007FF7715B190A  mov         rax,r13  
00007FF7715B190D  mul         rax,r8  
00007FF7715B1910  mov         rcx,r8  
00007FF7715B1913  sub         rcx,rdx  
00007FF7715B1916  shr         rcx,1  
00007FF7715B1919  add         rcx,rdx  
00007FF7715B191C  shr         rcx,1Dh  
00007FF7715B1920  imul        rax,rcx,3B9ACA00h  
00007FF7715B1927  sub         r8,rax  
00007FF7715B192A  mov         dword ptr [r9],ecx  
00007FF7715B192D  lea         r9,[r9-4]  
00007FF7715B1931  lea         rax,[r9+4]  
00007FF7715B1935  cmp         rax,r14  
00007FF7715B1938  jne         NumToString+0D0h (07FF7715B1900h)  

注意下面的MUL指令5行。 我知道,这个生成的代码是非常无意义的,实际上它看起来和编译后的代码没什么两样,但是对于32位的DIV,DIV非常慢,大约25个周期,根据这个,大约75个周期。 chart 与mul或imul(大约3或4个周期)相比,在现代个人电脑上,即使必须添加各种额外的指令,也要设法去掉div。

我不完全理解这里的优化,但是如果您想看到一个关于使用编译时和乘法除常数的理性和数学解释,请看这个 paper .

这是一个例子,是编译器利用完整的64和64位的未截断乘法的性能和能力,而不显示C++编码器的任何符号。

正如已经解释过的,C/C++不做 word*word to double-word 操作是什么 mul 指导是最好的。但有些情况下你需要 单词*单词到双单词 所以你需要一个扩展到C/C++。

GCC、CLANG和ICC提供内置类型 __int128 你可以用它间接地得到 穆尔 说明。

通过MSVC,它提供了 _umul128 内在的(至少从2010年开始),它产生了 穆尔 说明。有了这个内在的 _addcarry_u64 内在的你可以建立自己的效率 _国际128 键入msvc。