将基本递归 C 函数转换为汇编

Question

我在用汇编编写递归函数时遇到了一些麻烦。我想在这里模拟 C 函数：

int power(int base, int exponent)
{
    if (exponent==0)
        return 1;
    else {
        /* return base * power(base, --exponent); -- in normal form, writing in long-form below*/
        exponent--;
        int tmp1 = power(base, exponent);
        int tmp2 = base * tmp1;
        return tmp2;
    }
}

到目前为止我在汇编中的内容如下：

power:
    // int power(int base=rdi, int exponent=rsi)
    push %rbp
    mov %rsp, %rbp

    // if (exponent==0) return 1
    cmp [=11=], %rsi
    jnz exponentiate

 return_one:
    mov , %eax
    jmp cleanup

 exponentiate:
    dec %rsi
    push %rax
    call power
    pop %rbx
    imul %rbx, %rax

 cleanup:
    mov %rbp, %rsp
    pop %rbp
    ret

这会产生结果零。我认为我的错误在 exponentiate 函数中，但我很难调试它。我知道我可以 'find the answer' 使用 Compiler Explorer，但我想知道是否有人可以帮助指出我的代码中的错误。

我已经能够将其简化为以下内容，我什至不必为递归情况设置堆栈框架：

 exponentiate:
    dec %rsi
    call power
    imul %rdi, %rax

为什么允许这样做？我以为所有的递归函数都需要设置自己的栈帧，但为什么在上述情况下没有必要？

Answer 1

您想将递归调用的 return 值乘以 base 的值。那是在 %edi 中。出于某种原因，在您的原始版本中，即使它仅在函数的（第一个）入口处包含垃圾，您也会推送 %rax 。（mov , %eax 之后跳转到 cleanup，所以它不会在 exponentiate 之前运行。）然后你跳转到 %rbx，这是一个调用-保存的寄存器；如果你想修改它，你必须保存它的值并在以后恢复它。

更自然的做法是简单地在调用周围压入和弹出 %rdi，因为它包含您之后需要的值。但是，正如您最终注意到的那样，您实际上不需要修改 base，因此您最好保持它不变，并认为 %rdi 在整个函数中都是“只读的” .那么你根本不需要使用堆栈，除了隐式地使用 return 地址。（在这里你可以打败编译器，我猜它必须假设 %rdi 被任何调用破坏，包括对其正在编译的函数的调用，即使它知道自己的寄存器用法......）

因此您确实可以将 exponentiate 部分写为：

exponentiate:
    dec %esi
    call power
    imul %edi, %eax

（您使用 32 位寄存器是正确的，因为您在 C 示例中将所有内容都声明为 int。如果您希望它在 int64_t 上工作，请随意更改回到 64 位寄存器。）

其他说明：

堆栈帧设置从来都不是真正需要的，尤其是当您根本不需要堆栈时。特别是没有递归函数需要它的规则（如果你认为你会看到它不会做任何事情）。你可以跳过它。最糟糕的情况是调试器无法为您提供回溯。
如果使用 32 位值，您希望将 %esi 与零进行比较，而不是 %rsi；它还保存了一个字节的 REX 前缀。您可以通过写入 test %esi, %esi 代替 cmp [=29=], %esi 来保存另一个字节，因为您需要查看的只是零标志。
你可以通过
稍微简化一下跳跃

power:
    mov , %eax
    test %esi, %esi
    jz cleanup
    // former label exponentiate was here, no longer needed
    dec %esi
    call power
    imul %edi, %eax
cleanup:
    ret

如果您运行 exponentiate 部分，它只会覆盖 eax 中的 1，所以不会造成任何伤害。运行一个非常便宜的 mov 无条件指令可能比额外跳转要好。

Answer 2

这是我为保持递归情况而想出的最简洁的转换：

// int power(int base=rdi, int exponent=rsi)
power:
    cmp [=10=], %esi                  # if (exponent==0)
    jnz exponentiate                # // 
    mov , %eax                    # tmp = 1
    ret                             # return tmp
  exponentiate:                  # else
    dec %esi                       # exponent--
    call power                     # int tmp = power(base, exponent)
    imul %edi, %eax                # tmp = tmp * base
    ret                            # return tmp

它最终看起来与您拥有的 C 代码比较接近。

将基本递归 C 函数转换为汇编

Converting a basic recursive C function into assembly

assembly

x86-64