如何将优化的x86-64 asm循环转换回C for循环？

Question

我有以下内容：

foo:
   movl $0, %eax                      //result = 0
   cmpq %rsi, %rdi                    // rdi = x, rsi = y?
   jle .L2

.L3:
   addq %rdi, %rax                    //result = result + i?
   subq $1, %rdi                      //decrement?
   cmp %rdi, rsi
   jl .L3

.L2
   rep
   ret

而我正在尝试将其翻译为：

long foo(long x, long y)
{
    long i, result = 0;
    for (i=     ;               ;         ){

      //??

   }

 return result;
}

我不知道cmpq％rsi，％rdi是什么意思。为什么长期不存在另一个＆eax？

我很想得到一些帮助来解决这个问题。我不知道我错过了什么 - 我一直在阅读我的笔记，教科书和其他互联网，我被困住了。这是一个复习问题，我已经有好几个小时了。

Answer 1

假设这是一个采用2个参数的函数。假设这是使用gcc amd64调用约定，它将传递rdi和rsi中的两个参数。在C函数中，您可以调用这些x和y。

long foo(long x /*rdi*/, long y /*rsi*/)
{
    //movl $0, %eax
    long result = 0;  /* rax */

    //cmpq %rsi, %rdi
    //jle .L2
    if (x > y) {
        do {
            //addq %rdi, %rax
            result += x;

            //subq $1, %rdi
            --x;

            //cmp %rdi, rsi
            //jl .L3            
        } while (x > y);
    }

    return result;
}

Answer 2

我不知道cmpq %rsi, %rdi是什么意思

这是cmp rdi, rsi的AT＆T语法。 https://www.felixcloutier.com/x86/CMP.html

您可以在ISA手册中查找单个指令的详细信息。

更重要的是，像cmp / jcc这样的cmp %rsi,%rdi / jl就像jump if rdi<rsi。 Assembly - JG/JNLE/JL/JNGE after CMP。如果你详细了解cmp如何设置标志，以及每个jcc条件检查标记，你可以验证它是否正确，但是更容易使用JL = Jump on Less-than的语义含义（假设标志是由cmp设定）以记住他们的所作所为。

（由于AT＆T语法的原因，它是相反的; jcc谓词对于英特尔语法具有正确的语义含义。这是我通常更喜欢英特尔语法的主要原因之一，但你可以习惯AT＆T语法。）

---

从使用rdi和rsi作为输入（在没有/写入它们之前读取它们），它们是arg传递寄存器。所以这是x86-64 System V调用约定，其中整数args在RDI，RSI，RDX，RCX，R8，R9中传递，然后在堆栈中传递。 （What are the calling conventions for UNIX & Linux system calls on i386 and x86-64涵盖函数调用以及系统调用）。另一个主要的x86-64调用约定是Windows x64，它传递RCX和RDX中的前2个args（如果它们都是整数类型）。

所以是的，x = RDI，y = RSI。是的，结果= RAX。 （写入EAX零扩展到RAX）。

---

从代码结构（不存储/重新加载每个C变量到语句之间的内存），它被编译时启用了一定程度的优化，因此for()循环变为普通的asm循环，条件分支位于底部。 Why are loops always compiled into "do...while" style (tail jump)?（@ BrianWalker的答案显示asm循环音译回C，没有尝试将其重新形成一个惯用的for循环。）

从循环之前的cmp / jcc开始，我们可以看出编译器无法证明循环运行非零次迭代。所以无论for()循环条件如何，第一次都可能是假的。 （鉴于签名整数，这并不奇怪。）

由于我们没有看到单独的寄存器用于i，我们可以得出结论，优化重用了i的另一个var的寄存器。就像for(i=x;，然后x的原始值未用于函数的其余部分，它是“死”，编译器可以只使用RDI作为i，破坏x的原始值。

我猜测i=x而不是y，因为RDI是在循环内修改的arg寄存器。我们期望C源在循环内修改i和result，并且可能不会修改它的输入变量x和y。做i=y然后像x--那样做是没有意义的，尽管这将是另一种有效的反编译方式。

cmp %rdi, %rsi / jl .L3意味着（重新）进入循环的循环条件是rsi-rdi < 0（签名）或i<y。

循环前的cmp / jcc检查相反的条件;注意操作数是反转的，它正在检查jle，即jng。这是有道理的，它实际上是相同的循环条件从循环中剥离出来并以不同的方式实现。因此它与C源兼容，是具有一个条件的普通for()循环。

sub $1, %rdi显然是i--或--i。我们可以在for()内部或循环体底部进行。最简单和最惯用的地方是在for(;;)声明的第3部分。

addq %rdi, %rax显然是将i添加到result。我们已经知道这个函数中的RDI和RAX是什么。

把这些碎片放在一起，我们得出：

long foo(long x, long y)
{
    long i, result = 0;
    for (i= x    ;    i>y    ;    i-- ){
        result += i;
    }

    return result;
}

---

哪个编译器发了这个代码？

从.L3:标签名称，这看起来像gcc的输出。 （它以某种方式被破坏，从:移除.L2，更重要的是在一个cmp中从%移除%rsi。确保将代码复制/粘贴到SO问题中以避免这种情况。）

所以有可能使用正确的gcc版本/选项来获取一些C输入的asm。它可能是gcc -O1，因为movl $0, %eax排除了-O2和更高（GCC会寻找xor %eax,%eax窥视孔优化以有效地归零寄存器）。但它不是-O0，因为那将存储/重新加载循环计数器到内存。和-Og（优化一点，用于调试）喜欢使用jmp循环条件而不是单独的cmp/jcc跳过循环。这种级别的细节基本上与简单地反编译为执行相同操作的C无关。

rep ret是gcc的另一个标志;由于AMD K8 / K10分支预测，gcc7和之前在tune=generic的默认ret输出中使用了它作为分支目标或来自jcc的掉落。 What does `rep ret` mean?

gcc8及更高版本仍将与-mtune=k8或-mtune=barcelona一起使用。但我们可以排除这种情况，因为调整选项会使用dec %rdi而不是subq $1, %rdi。 （对于寄存器操作数，只有少数现代CPU有inc/dec保留CF未修改的任何问题.INC instruction vs ADD 1: Does it matter?）

gcc4.8后来把rep ret放在同一条线上。 gcc4.7和更早版本按照你所示的方式打印它，前面的行上有rep前缀。

gcc4.7以及后来喜欢在mov $0, %eax之前放置初始分支，这看起来像是错过了优化。这意味着他们需要一个单独的return 0路径，该功能包含另一个mov $0, %eax。

gcc4.6.4 -O1完全重现你的输出，对于上面显示的来源，on the Godbolt compiler explorer

# compiled with gcc4.6.4 -O1 -fverbose-asm
foo:
        movl    $0, %eax        #, result
        cmpq    %rsi, %rdi      # y, x
        jle     .L2       #,
.L3:
        addq    %rdi, %rax      # i, result
        subq    $1, %rdi        #, i
        cmpq    %rdi, %rsi      # i, y
        jl      .L3 #,
.L2:
        rep
        ret

这个使用i=y的其他版本也是如此。当然，我们可以添加许多可以优化的东西，比如i=y+1，然后像x>--i这样的循环条件。 （签名溢出是C中未定义的行为，因此编译器可以假设它不会发生。）

// also the same asm output, using i=y but modifying x in the loop.
long foo2(long x, long y) {
  long i, result = 0;
  for (i= y    ;    x>i    ;    x-- ){
      result += x;
   }
   return result;
}

---

In practice the way I actually reversed this:

• 我将C模板复制/粘贴到Godbolt（https://godbolt.org/）中。我可以立即看到（从mov $0而不是xor-zero，从标签名称）它看起来像gcc -O1输出，所以我输入了命令行选项并选择了像gcc6这样的旧版gcc。 （原来这个asm实际上是来自一个更老的gcc）。
• 我尝试了一个基于cmp / jcc和x<y的i++的初步猜测（在我真正仔细阅读其余的asm之前），因为for循环经常使用i++。看似琐碎的无限循环asm输出显示我显然是错误的：P
• 我猜测i = x，但在使用result += x但i--的版本采取了错误的转弯之后，我意识到i是一个分心，最初简化为不使用i。我刚刚在第一次反转它时使用了x--，因为显然RDI = x。 （我知道x86-64 System V调用约定足以立即看到它。）
• 看完循环体后，result += x和x--从add和sub说明中完全明显。
• cmp/jl显然是一个涉及2个输入变量的something < something循环条件。
• 我不确定我是否是x<y或y<x，并且更新的gcc版本使用jne作为循环条件。我想在那一点上我作弊并看着Brian的答案来检查它真的是x > y，而不是花一点时间来完成实际的逻辑。但是，一旦我发现它是x--，只有x>y有道理。如果它完全进入循环，那么另一个将是真实的，但是签名溢出是C中未定义的行为。
• 然后我查看了一些较旧的gcc版本，看看是否有任何asm更像是在问题中。
• 然后我回去用循环内的x取代i。

如果这看起来像偶然和slapdash，那是因为这个循环是如此之小，以至于我没想到要弄清楚它，我更感兴趣的是找到完全复制它的源+ gcc版本，而不是原始版本完全扭转它的问题。

（我不是说初学者应该觉得这很简单，我只是记录我的思考过程以防万一有人好奇。）