旭穹の陋室

函数与递归

要在汇编中“调用函数”，你需要跳转到函数的开头，执行完毕后再跳转回来。这引出了两个重要问题：

• 如果调用者将数据存储在与被调用者相同的寄存器中，该怎么办？

• 跳转回那个地方？

这两个问题都可以通过在内存中设置一个专用位置来解决，在调用函数之前，我们可以往该位置写入从函数返回时需要的所有信息。这个位置被称为栈（stack）。

硬件栈的工作方式与软件栈相同，并且类似地仅用两个指针进行实现：

• 栈底指针（base pointer）标记栈的开始，通常存储在rbp寄存器中；
• 栈顶指针（stack pointer）标记栈中最后一个元素，通常存储在rsp寄存器中。

当你需要调用一个函数时，您可以将所有本地变量压进栈中（在其他情况下也可以这样做；例如，当寄存器用完时），当前指令指针压栈，然后跳转到函数的开头。从函数中退出时，查看存储在栈顶的指针，跳转到那里，然后仔细地将存储在栈中的所有变量读取回对应的寄存器。

你可以通过一般的内存操作和跳转指令来实现压栈出栈操作，但由于使用频率的不同，有4条专用指令来实现：

• push在栈顶指针处写入数据并令其递减；
• pop从栈顶指针处读取数据并令其递增；
• call将其后面的指令的地址放在栈的顶部，并跳转到函数标签处；
• ret从堆栈顶部读取返回地址并跳转；

这些专有指令并不是实际的硬件指令，而是两个指令片段的融合，被称为语法糖（syntactic sugar）：

; "push rax"
sub rsp, 8
mov QWORD PTR[rsp], rax

; "pop rax"
mov rax, QWORD PTR[rsp]
add rsp, 8

; "call func"
push rip ; <- instruction pointer (although accessing it like that is probably illegal)
jmp func

; "ret"
pop  rcx ; <- choose any unused register
jmp rcx

rbp和rsp之间的内存区域被称为栈帧（stack frame），函数的局部变量通常存储在这个地方。它在程序开始时预先分配，如果在往栈上压入的数据超过其容量（在Linux上默认为8MB），就会遇到堆栈溢出（stack overflow）错误。因为现代操作系统在实际读取或写入内存地址空间之前，不会给你分配内存页，所以你可以自由地指定一个非常大的栈大小，这更像是对可以使用的栈内存的上限限制，而不是每个程序必须使用的固定大小。

开发编译器和操作系统的那批人最终提出了关于如何编写和调用函数的约定。这些约定实现了一些重要的软件工程创举，例如将编译拆分为单独的单元，重用已经编译的库，甚至可以用不同的编程语言编写它们。

考虑如下C语言的例子：

int square(int x) {
    return x * x;
}

int distance(int x, int y) {
    return square(x) + square(y);
}

按照惯例，函数应该从rdi、rsi、rdx、rcx、r8、r9中的获取参数（如果这些参数还不够的话，其他参数存放在栈中），将返回值放入rax中，然后返回。因此，square作为一个简单的单参数函数，可以这样实现：

square:             ; x = edi, ret = eax
    imul edi, edi
    mov  eax, edi
    ret

每次我们通过distance函数调用它时，我们就需要克服一些保存局部变量的麻烦：

distance:           ; x = rdi/edi, y = rsi/esi, ret = rax/eax
    push rdi
    push rsi
    call square     ; eax = square(x)
    pop  rsi
    pop  rdi

mov  ebx, eax   ; save x^2
    mov  rdi, rsi   ; move new x=y

push rdi
    push rsi
    call square     ; eax = square(x=y)
    pop  rsi
    pop  rdi

add  eax, ebx   ; x^2 + y^2
    ret

这里有很多细节，但我们不会在这里详细介绍，因为这本书是关于性能的，而处理函数调用的最佳方法实际上是首先避免进行调用。

在栈中来回移动数据会给类似这样的小函数带来明显的开销。但你必须这样做，因为通常情况下，你不知道被调用的函数是否会修改存储局部变量的寄存器。但是，当你可以访问square的代码时，你可以通过将数据存放在你知道不会被修改的寄存器中来解决这个问题。

distance:
    call square
    mov  ebx, eax
    mov  edi, esi
    call square
    add  eax, ebx
    ret

这样做更好，但我们仍然在隐式访问栈内存：你需要在每次函数调用时将指令指针压栈和出栈。在这种简单的情况下，我们可以通过将被调用者的代码缝合到调用者中并解决寄存器冲突来内联函数调用。我们的示例可以这样：

distance:
    imul edi, edi       ; edi = x^2
    imul esi, esi       ; esi = y^2
    add  edi, esi
    mov  eax, edi       ; there is no "add eax, edi, esi", so we need a separate mov
    ret

这与编译器优化这段代码的结果相当接近——只是他们使用lea技巧使生成的机器代码序列少了几个字节：

distance:
    imul edi, edi       ; edi = x^2
    imul esi, esi       ; esi = y^2
    lea  eax, [rdi+rsi] ; eax = x^2 + y^2
    ret

在这种情况下，函数内联显然是有益的，编译器大多是自动执行函数内联的，但函数内联并不总是带来收益——我们稍后会讨论这些。

尾调用优化

当被调用函数中不进行任何其他函数调用时，或者至少其调用中没有递归时，内联很简单。让我们继续看一个更复杂的阶乘的递归计算的例子：

int factorial(int n) {
    if (n == 0)
        return 1;
    return factorial(n - 1) * n;
}

相应的汇编代码为：

; n = edi, ret = eax
factorial:
    test edi, edi   ; test if a value is zero
    jne  nonzero    ; (the machine code of "cmp rax, 0" would be one byte longer)
    mov  eax, 1     ; return 1
    ret
nonzero:
    push edi        ; save n to use later in multiplication
    sub  edi, 1
    call factorial  ; call f(n - 1)
    pop  edi
    imul eax, edi
    ret

如果函数是递归的，仍然可以通过重构来使其“少调用”。当函数是尾部递归（tail recursive）的时候就可以做到，即函数在进行递归调用后立即返回。由于调用后不需要任何操作，因此也不需要在栈上存储任何内容，并且递归调用可以安全地用跳转到开头来代替，从而有效地将函数变成循环。

为了使我们的factorial函数尾部递归，我们可以向它传递“当前乘积”作为参数：

int factorial(int n, int p = 1) {
    if (n == 0)
        return p;
    return factorial(n - 1, p * n);
}

那么，这个函数就可以折叠成一个循环：

; assuming n > 0
factorial:
    mov  eax, 1
loop:
    imul eax, edi
    sub  edi, 1
    jne  loop
    ret

递归之所以慢，主要原因是它需要在栈上读取和写入数据，而迭代和尾部递归算法则不需要。这个概念在函数式编程（functional programming）中非常重要，因为函数式编程没有循环，只能使用函数。如果没有尾部调用优化，函数程序将需要更多的时间和内存来执行。