如何在 x86 中仅使用 2 条连续的 leal 指令将寄存器乘以 37？

Question

假设 %edi 包含 x，我想只使用 2 个连续的 leal 指令以 37*x 结束，我该怎么做？

例如，要获得 45 倍，您会这样做

leal (%edi, %edi, 8), %edi   
leal (%edi, %edi, 4), %eax (to be returned)

我这辈子都想不出用什么数字来代替 8 和 4，这样结果 (%eax) 就是 37x

Answer 1

At -O3, gcc will emit (Godbolt compiler explorer):

int mul37(int a)  { return a*37; }

    leal    (%rdi,%rdi,8), %eax      # eax = a * 9
    leal    (%rdi,%rax,4), %eax      # eax = a + 4*(a*9)
    ret

这是在使用 37 = 9*4 + 1，不会破坏第一个 lea 的原始 a 值，因此它可以在第二个中使用两者。

虽然你没有发现这个，但你是个好伙伴：最近的 clang（3.8 和更新版本）通常会使用 2 lea 指令而不是 imul（例如 *15), 但它错过了这个并使用：

    imull   , %edi, %eax
    ret

它确实 *21 使用与 gcc 使用相同的模式，如 5*4 + 1。（clang3.6 和更早版本总是使用 imul 除非有单指令替代 shl 或 lea）

ICC 和 MSVC 也使用 imul，但他们似乎不喜欢使用 2 lea 指令，所以 imul 是 "on purpose"。

请参阅 godbolt link 了解 gcc7.2 与 clang5.0 的各种乘法器。尝试 gcc -m32 -mtune=pentium 甚至 pentium3 看看 gcc 当时愿意使用多少指令是很有趣的。尽管 P2/P3 对于 imul r, r, i 有 4 个周期的延迟，所以这有点疯狂。 Pentium 有 9 个周期 imul 并且没有 OOO 来隐藏延迟，因此努力避免它是有意义的。

mtune=silvermont 可能只愿意用一条指令替换 32 位 imul，因为它有 3 周期延迟/1c 吞吐量乘法，但解码通常是瓶颈（根据阿格纳雾，http://agner.org/optimize/）。您甚至可以考虑 imul , %edi, %eax（或 2 的其他幂）而不是 mov/shl，因为 imul-immediate 是复制和乘法。

具有讽刺意味的是，gcc 错过了 * 45 的情况，并使用了 imul，而 clang 使用了 2 个 lea。猜猜是时候提交一些未优化的错误报告了。如果2 个 LEA 优于 1 个 IMUL，则应尽可能使用它们。

较旧的 clang（3.7 及更早版本）使用 imul，除非单个 lea 可以解决问题。我没有查看变更日志，看看他们是否做了基准测试来决定优先考虑延迟而不是吞吐量。

相关：关于为什么 LEA 使用内存操作数语法和机器编码的规范回答，即使它是一个 shift+add 指令（并且在大多数现代微体系结构中运行在 ALU 而不是 AGU 上。）

如何在 x86 中仅使用 2 条连续的 leal 指令将寄存器乘以 37？

How to multiply a register by 37 using only 2 consecutive leal instructions in x86?

x86

assembly

x86-64

multiplication

strength-reduction