x86_64：IMUL比2x SHL + 2x ADD更快吗？

Question

在查看Visual Studio（2015U2）在/O2（发布）模式下生成的汇编代码时，我发现这段手动优化的C代码被转换回乘法操作。

int64_t calc(int64_t a) {
  return (a << 6) + (a << 16) - a;
}

汇编语言：

  imul        rdx,qword ptr [a],1003Fh  

我在想这是不是比按照现有的方式操作更快，像这样写的形式：

  mov         rbx,qword ptr [a]  
  mov         rax,rbx  
  shl         rax,6  
  mov         rcx,rbx  
  shl         rcx,10h  
  add         rax,rcx  
  sub         rax,rbx  

我一直认为乘法比几次位移和加法慢，但是在现代Intel x86_64处理器上是否不再是这样呢？

- rustyx

---

“IMUL” 指令通常具有 3-4 个时钟周期的延迟，每个时钟周期吞吐量为 1。所以它很可能更快。同时请注意，您最后的 3 条指令彼此依赖，这本身就会产生等效的依赖链。 - Jester

在旧时代，这将是很好的事情：8086 IMUL需要大约100个时钟周期，具体取决于寻址模式、寄存器大小等因素。 - Weather Vane

如果您假设从内存中加载数据是免费的（因为您无论如何都必须等待它），并且可以消除寄存器-寄存器mov，那么shl可以并行执行，那么理想情况下，移位代码的速度将与乘法相当快。但是，它会占用很多功能单元，并且更多地使用i-cache。 - EOF

@EOF: 延迟是的，吞吐量不是（因为移位版本在总uop吞吐量上存在瓶颈，如果不是在执行端口上）。有趣的一点是，由于零延迟mov和2个可以运行shift imm的执行端口，移位版本仍然只有3c的延迟。 - Peter Cordes

Answer 1

没错，现代x86 CPU（尤其是英特尔）具有非常高的性能倍增器。
在英特尔SnB家族和AMD Ryzen上，imul r, r/m和imul r, r/m, imm的延迟都为3个周期，吞吐量为每1个周期1次，即使对于64位操作数大小也是如此。

在AMD Bulldozer家族中，延迟为4个或6个周期，吞吐量为每2个周期或每4个周期1次。（64位操作数大小的速度较慢）。

数据来自Agner Fog的指令表。另请参见x86标签wiki中的其他内容。

---

现代CPU中晶体管预算非常庞大，这使得所需的硬件并行性足以在低延迟下进行64位乘法运算。由于受功率预算限制而非晶体管预算限制，因此拥有许多不同功能的专用硬件是可能的，只要它们不能同时开启（参见https://en.wikipedia.org/wiki/Dark_silicon）。例如，在Intel CPU上无法同时饱和pext/pdep单元、整数乘法器和向量FMA单元，因为它们中的许多都在同一执行端口上。想了解现代X86处理器如何计算乘法，请参考链接：How modern X86 processors actually compute multiplications?。需要很多加法器才能制作出一个大型快速乘法器，详情请参见链接It takes a lot of adders和large fast multiplier。

有趣的事实：imul r64也是3c，因此您可以在3个周期内获得完整的64*64 => 128b乘法结果。imul r32具有4个时钟周期的延迟和额外的uop。我猜测每个周期的额外uop将64位结果从常规的64位乘法器中分成两个32位半部分。

---

编译器通常会优化延迟，但通常不知道如何优化独立依赖链的短通量与长循环依赖链的延迟瓶颈。GCC和Clang3.8及更高版本使用最多两个LEA指令来代替imul r，r/m，imm。我认为如果另一种方法需要三个或更多指令（不包括mov），GCC将使用imul。这是一个合理的调整选择，因为3个指令dep链与Intel上的imul相同长度。使用两个1周期指令花费额外的uop以缩短1个周期的延迟。Clang3.7及更早版本倾向于使用imul，除了只需要单个LEA或移位的乘数。所以，Clang最近改变了优化小常数乘法的延迟而不是吞吐量的策略。(或者可能是出于其他原因，比如不与只在与乘法器相同端口上的其他东西竞争。)

例如：在Godbolt编译器浏览器上的此代码：

int foo (int a) { return a * 63; }
    # gcc 6.1 -O3 -march=haswell (and clang actually does the same here)
    mov     eax, edi  # tmp91, a
    sal     eax, 6    # tmp91,
    sub     eax, edi  # tmp92, a
    ret

clang3.8及更高版本使代码相同。

- Peter Cordes

---

那么这是否意味着，虽然imul更快，但潜在地比4个ALU操作消耗更多的能量（因为乘法器会激活更多的晶体管）？ - rustyx

@rustyx: 我不知道。在流水线中跟踪4个ALU uops并将它们的结果相互转发比跟踪一个更耗费能量，这可能比操作乘法器更昂贵！乱序执行是昂贵的。我希望我有一些数字，这样我就可以猜测答案了，但我没有进行任何功率优化（除了明显的事情，如在不需要结果的上128位时使用128位AVX向量操作）。 - Peter Cordes

顺便说一句，使用更少晶体管的高延迟乘法器仍可能具有类似每次乘法成本的能量消耗，因为它仍然必须添加所有部分和。 它只需要更多的周期。(这是极度简化的，并且可能是错误的。我不是逻辑门专家，并且没有详细阅读那些链接)。 低延迟乘法器使得更容易频繁使用它(e.g. 而不是两个“lea”指令来乘以10)。 - Peter Cordes

你有关于使用Wallace树作为乘法器的CPU的来源吗？ - Randomblue

@Randomblue：不，我通常不会深入了解硬件设计的细节。我不知道Bulldozer为什么有4c延迟/2c吞吐量乘法器，而Ryzen和英特尔只有3c延迟/1c吞吐量的 imul r32,r32，我只知道这些是性能数据。我不知道哪些微架构使用哪些技术。维基百科提到了一些其他选项，并提供了一些链接。 - Peter Cordes

@Randomblue: 现代X86处理器如何计算乘法？指出所有现代CPU ALU都使用Dadda树。 - Peter Cordes