c - 尝试获取addq，但不断获取leaq

Question

因此，我试图熟悉汇编并尝试对某些代码进行反向工程。我的问题在于尝试解码addq，据我了解它执行Source + Destination = Destination。

我使用的假设是，参数x，y和z在寄存器％rdi，％rsi和％rdx中传递。返回值存储在％rax中。

long someFunc(long x, long y, long z){
1.  long temp=(x-z)*x;
2.  long temp2= (temp<<63)>>63;
3.  long temp3= (temp2 ^ x);
4.  long answer=y+temp3; 
5.  return answer;
}

到目前为止，第4行上方的所有内容正是我想要的。但是，第4行给了我 leaq (%rsi,%rdi), %rax而不是 addq %rsi, %rax。我不确定这是否是我做错的事情，但是我正在寻找一些见识。

Answer 1

这些说明不相同。对于LEA，rax是纯输出。对于您希望的add，它是rax += rsi，因此编译器必须先mov %rdi, %rax。这效率较低，因此无法做到这一点。

lea是编译器实现dst = src1 + src2并保存mov指令的一种完全正常的方法。通常，不要期望C运算符会编译为以它们命名的指令。特别是很小的左移，然后加或乘以3、5或9，因为这些是使用LEA优化的主要目标。例如lea (%rsi, %rsi, 2), %rax实现result = y*3。有关更多信息，请参见Using LEA on values that aren't addresses / pointers?。如果稍后需要它们，则LEA还可用于避免破坏任何一个输入。



假设您的意思是t3与temp3相同，那么clang确实会按照您期望的方式进行编译，从而更好地完成了寄存器分配，因此它可以使用更短，更有效的add指令而无需任何额外的 说明，而不需要 mov。

Clang选择比GCC做更好的寄存器分配，因此它可以只使用 lea而不是最后一条指令需要 add。 （ Godbolt）。这样可以节省代码大小（由于采用了索引寻址模式），并且 lea在大多数CPU上的吞吐量比LEA略好，例如4 / clock而不是2 / clock。

Clang还优化了向 add / andl $1, %eax的移位，以创建该算术右移位=广播的0或 negq %rax结果。在最初的几个步骤中，它还优化为32位操作数大小，因为移位将丢弃 -1的低位以外的所有位。

# side by side comparison, like the Godbolt diff pane
clang:                           |    gcc:
        movl    %edi, %eax              movq    %rdi, %rax
        subl    %edx, %eax              subq    %rdx, %rdi
        imull   %edi, %eax              imulq   %rax, %rdi  # temp1

        andl    $1, %eax                salq    $63, %rdi
        negq    %rax                    sarq    $63, %rdi   # temp2

        xorq    %rdi, %rax              xorq    %rax, %rdi  # temp3

        addq    %rsi, %rax              leaq    (%rdi,%rsi), %rax   # answer
        retq                            ret

请注意，clang选择了 temp1（进入RAX），但是GCC选择了乘以RDI。这就是寄存器分配的差异，导致GCC在最后需要 imul %edi, %eax而不是 lea。

如果最后的操作不是像加法那样可以用 add作为非破坏性方式完成的操作，则编译器有时甚至会在小功能的结尾卡住额外的 mov指令并复制。这些是错过的优化错误；您可以通过GCC的bugzilla报告它们。



其他错过的优化

仅当两个输入均为奇数时，才可以通过使用 lea而不是 and来优化GCC和clang来设置低位。

另外，由于仅 imul输出的低位有效，因此XOR（不带进位的加法）将起作用，甚至加法！ （奇数+偶数=奇数。偶数+偶数=偶数。奇数+奇数=奇数。）这将允许 sub代替 lea作为第一条指令。

        lea    (%rdi,%rsi), %eax
        and    %edi, %eax           # low bit matches (x-z)*x

        andl    $1, %eax            # keep only the low bit
        negq    %rax                # temp2

让我们为 mov/sub和 x的低位制作一个真值表，看看如果我们想更多/不同地进行优化，这会如何震撼：

# truth table for low bit: input to shifts that broadcasts this to all bits
 x&1  |  z&1  | x-z = x^z | x*(x-z) = x & (x-z)
  0       0          0       0
  0       1          1       0
  1       0          1       1
  1       1          0       0
                            x & (~z) = BMI1 andn

所以 z。而且 temp2 = (x^z) & x & 1 ? -1 : 0。
 我们可以将其重新排列为 temp2 = -((x & ~z) & 1)，这使我们可以并行地从 -((x&1) & ~z)和 not z开始，以获得更好的ILP。或者，如果可能首先准备好 and $1, x，我们可以对其进行操作，并缩短 z-> x的关键路径，而以 answer为代价。

或者使用执行 z的 BMI1 andn指令，我们可以在一条指令中执行此操作。 （加上另一个隔离低位）

我认为该函数对于所有可能的输入都具有相同的行为，因此编译器可能已从您的源代码中发出了该函数。这是您希望编译器发出的一种可能性：

# hand-optimized
# long someFunc(long x, long y, long z)
someFunc:
        not    %edx                   # ~z
        and    $1, %edx
        and    %edi, %edx             # x&1 & ~z = low bit of temp1
        neg    %rdx                  # temp2 = 0 or -1

        xor    %rdi, %rdx            # temp3 = x or ~x

        lea    (%rsi, %rdx), %rax    # answer = y + temp3
        ret

因此，除非在 (~z) & x和/或 z之前准备好 x，否则仍然没有ILP。使用额外的 y指令，我们可以与 mov并行执行 x&1

可能您可以使用 not z / test或 setz来执行某些操作，但如果IDK可以击败lea / and（temp1）+和/ neg（temp2）+ xor +加，则可以执行IDK。

我没有考虑优化最终的xor和加法，但请注意 cmov基本上是 temp3的条件NOT。您可以一次计算两种方式并使用cmov在这两种方式之间进行选择，从而以牺牲吞吐量为代价来改善延迟。可能通过涉及2的补码身份 x。也许可以通过执行 -x - 1 = ~x然后用取决于x和z条件的方法进行校正来改善ILP /等待时间？由于我们无法使用LEA进行减法运算，因此最好只进行NOT和ADD运算。

# return y + x  or   y + (~x) according to the condition on x and z
someFunc:
        lea    (%rsi, %rdi), %rax     # y + x

        andn   %edi, %edx, %ecx       # ecx = x & (~z)

        not    %rdi                   # ~x
        add    %rsi, %rdi             # y + (~x)

        test    $1, %cl
        cmovnz  %rdi, %rax            # select between y+x and y+~x
        retq

这具有更多的ILP，但需要BMI1 x+y仍然只有6条（单uop）指令。 Broadwell及其以后具有单样本CMOV。在较早的Intel上是2微秒。

使用BMI andn的其他功能可能是5微秒。

在此版本中，假设x，y和z已准备就绪，则前3条指令均可在第一个周期中运行。然后在第二个循环中，ADD和TEST都可以运行。在第3个周期中，CMOV可以运行，从LEA，ADD获得整数输入，从TEST获得标志输入。因此，在此版本中，x-> answer，y-> answer或z-> answer的总延迟时间为3个周期。 （假设单联/单循环cmov）。如果它处在关键路径上，那就太好了；如果它是独立的dep链的一部分，那么就不是很相关，而吞吐量才是最重要的。

与之前尝试的5个（andn）或6个周期（无）相比。对于使用 andn而不是 imul的编译器输出，甚至更糟（仅针对该指令的3个周期延迟）。