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

Question

假设%edi包含x，我想使用仅有的2个连续leal指令得到37*x，我该怎么做？

例如，要得到45x，你可以执行：

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

我根本不知道应该用什么数字来替换8和4，以便结果（%eax）为37x。

- Newbie18

---

你试过问编译器吗？https://godbolt.org/g/nMbujJ。提示：你需要更改的不仅是比例因子。第二个LEA使用原始输入和第一个LEA结果。 - Peter Cordes

另外，考虑到您选择的寄存器，这似乎是在使用System V ABI的64位代码。在64位模式下使用地址大小覆盖前缀获取32位寻址模式没有任何好处。让lea将64位寻址模式截断为32位始终是安全的。https://dev59.com/kek6XIcBkEYKwwoYDPsR - Peter Cordes

Answer 1

在 -O3 优化级别下，gcc 会生成以下结果 (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值，这样可以在第二个lea中同时使用两个值。

不过你并不孤单，在这个问题上：即使是最近版本的clang（3.8及以上），通常也会使用2个lea指令来替代imul（例如对于*15），但是它会忽略这个问题，使用如下代码：

    imull   $37, %edi, %eax
    ret

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

ICC和MSVC也使用imul，但它们似乎不喜欢使用2个lea指令，因此imul是“故意”使用的。

请参见godbolt链接，以了解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吞吐量乘法，但是解码通常是瓶颈（根据Agner Fog的说法，http://agner.org/optimize/）。您甚至可以考虑使用imul $64，%edi，%eax（或其他2的幂）而不是mov / shl，因为imul-immediate是复制和乘法。

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

较旧的clang（3.7及更早版本）除非单个lea足以完成任务，否则将使用imul。我没有查看更新日志以查看他们是否进行了基准测试来决定支持延迟还是吞吐量。

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

- Peter Cordes

---

“clang通常会使用2个lea指令而不是imul”。我做出了相反的观察。从我看到的情况来看，Clang倾向于发出单个IMUL而不是任何其他指令序列。实际上，我曾经考虑过将其报告为优化缺陷，但后来我决定这并不重要。性能影响几乎无法测量。 :-) - Cody Gray

@CodyGray：这在clang3.7或者之后的版本中有所改变。我猜他们决定优先考虑延迟而不是吞吐量。但是没错，旧版clang更喜欢使用imul，除非它可以使用单个lea。 - Peter Cordes