assembly - 常量乘法 - imul 或 shl-add-combination

Question

这个问题是关于我们如何将一个整数与一个常数相乘。那么让我们看一个简单的函数:

int f(int x) {
    return 10*x;
}

如何才能最好地优化该函数，尤其是在内联到调用方时？

方法 1(由大多数优化编译器生成(例如 on Godbolt))

    lea    (%rdi,%rdi,4), %eax
    add    %eax, %eax

方法 2(使用 clang3.6 及更早版本生成，使用 -O3)

    imul   $10, %edi, %eax

方法 3(使用 g++6.2 生成，未优化，删除存储/重新加载)

    mov    %edi, %eax
    sal    $2, %eax
    add    %edi, %eax
    add    %eax, %eax

哪个版本最快，为什么？主要对 Intel Haswell 感兴趣。

Answer 1

根据 Agner Fog's testing (以及 AIDA64 等其他东西)自 Core2 以来的英特尔 CPU 的 imul r32,r32, imm 延迟为 3c，吞吐量为每 1c。自 Nehalem 以来，64 位乘法也那么快。 (Agner 说 Nehalem 的 imul r64,r64,imm 比 imul r64,r64 慢(2c 吞吐量)，但这与其他结果不匹配。Instlatx64 says 1c. )

Ryzen 之前的 AMD CPU 速度较慢，例如对于 32 位乘法，Steamroller 有 lat=4c tput=one per 2c。对于 64 位乘法，lat=6c tput=one per 4c。 AMD Ryzen 具有与 Intel 一样出色的乘法性能。

---

在寻址模式下具有 2 个组件的 LEA(基址 + 索引，但没有恒定位移)在所有 Intel CPU 上以 1c 延迟运行¹，除了 Atom，LEA 在不同阶段运行流水线(在实际的 AGU 中，而不是 ALU)并且需要比“正常”ALU 指令早 4c 就绪的输入。相反，我认为它的输入会更快准备好，因此 ADD 可以使用相同周期的结果。 (我没有对此进行测试，也没有任何 Atom 硬件。)

在 Intel SnB 系列上，simple-LEA 可以在端口 1 或 5 上运行，因此它的吞吐量是 IMUL 的两倍。

ADD 可以在任何 CPU 上的任何 ALU 端口上运行。 HSW 引入了第 4 个 ALU 端口(相对于 IvyBridge)，因此它可以维持每个时钟 4 个 ALU 微指令(理论上)。

所以 LEA+ADD 版本在大多数 x86 CPU 上有 2c 延迟，而在 Haswell 上每个时钟可以运行两次乘法。

脚注 1:在 AMD(包括 Zen/Zen2)上，缩放索引使 LEA“变慢”(2 个周期延迟并在更少的端口上运行)。例如lea r32，[r64+r64*2] 在 2 个周期延迟下测得 on Zen2与 1 个周期 on Skylake . (Agner Fog 还提到 lea r32, [r64...] 在 AMD 上速度较慢，但​​这可能只是推土机效应；在 Zen/Zen2 的 https://uops.info/'s 结果中并不明显。 )

---

但是，如果乘法只是更大的周围循环的一小部分，它会限制总 uop 吞吐量，而不是乘法延迟或吞吐量，则 IMUL 版本更好。

---

如果您的乘法常数对于两个 LEA 或 SHL+LEA 来说太大，那么您可能最好使用 IMUL，尤其是在主要针对具有极高性能整数乘法器的 Intel CPU 进行调整时。

SHL+LEA 或 SHL+SUB 可能有用，例如乘以 63。(来自 Godbolt:gcc6.2 -O3 -march=haswell)

    movl    %edi, %eax
    sall    $6, %eax
    subl    %edi, %eax

在 Haswell 上，MOV 是零延迟的，这只有 2c 延迟。但对于 imull $63, %edi, %eax，它是 3 个融合域 uops 而不是 1 个。所以它在管道中有更多的微指令，减少了 CPU 可以“看到”进行乱序执行的超前距离。它还增加了 uop 缓存和 L1 I 缓存的压力，因为它需要更多的指令字节，因此编译器会始终选择这种策略。

在 IvyBridge 之前的 CPU 上，这绝对比 IMUL 差，除非有其他东西在竞争端口 1，因为它是 3c 延迟(MOV 在关键路径依赖链上，并且有 1c 延迟)。

和往常一样，没有一个 asm 片段可以说是适用于所有情况的最佳选择。这取决于周围代码中的瓶颈是什么:延迟、吞吐量或 uops。

对于不同微架构上的相同周边代码，答案也会不同。