# 函数调用与栈帧

函数把复杂任务分解为可复用的模块，调用则是把这些模块拼接起来的机制。函数调用不是一条跳转指令就能完成的操作：调用者要把实参交给被调用者，被调用者要能分配局部空间、保存必要状态，并在结束时把结果和控制权交回。MIPS用一块向低地址生长的栈、以及每次调用新建的栈帧来实现这套约定。本页的寄存器名沿用MIPS；指令格式见[Simple-MIPS教学指令集](/knowledge/cs/computer-architecture/simple-mips/)，PC与寄存器组的分工见[CPU的核心部件](/knowledge/cs/computer-architecture/cpu-components/)。

## 定义

### 函数调用要完成的六件事

设发起调用的函数为调用者，被调用的函数为被调用者。一次调用需要依次完成：

1. **传递参数**：调用者把实参放在被调用者能访问的地方，通常是参数寄存器；寄存器放不下时放到栈上。
2. **转移控制**：执行流程从调用者跳转到被调用者的入口。
3. **获得存储空间**：被调用者在栈上开辟自己的栈帧，用于局部变量和临时数据。
4. **执行任务**：执行函数体内的指令。
5. **放置结果**：被调用者把返回值放在调用者能访问的地方，通常是返回值寄存器。
6. **返回控制**：被调用者释放自己的栈帧，把执行流程交还调用者，调用者从调用点之后继续执行。

这六件事里，第1、2、5、6步需要调用者与被调用者共同遵守约定，否则各自独立编译的函数无法正确拼接。

### 栈

栈是内存中用于存放临时数据的一段区域，按后进先出（LIFO）的方式工作：最后压入的数据最先弹出。可以把栈想成一摞盘子，只能从最上面放取。MIPS的栈向低地址方向生长，压栈让地址变小，出栈让地址变大，因此“栈顶”是当前占用区域中地址最低的一端。

`$sp`是栈顶指针，始终指向栈顶。压入一个32位字时，先把 `$sp`减4取得空间，再把数据写到 `$sp`指向的地址；弹出一个字时，先读出 `$sp`处的数据，再把 `$sp`加4。这里的4来自MIPS的字长：每个字占4字节。

`$fp`是帧指针，指向当前栈帧的固定位置，通常取帧的基址。函数执行过程中 `$sp`会随临时数据的压入和弹出而变化，`$fp`保持不变，所以用 `$fp`加固定偏移访问局部变量和保存的寄存器，比用不断变化的 `$sp`更稳定。

### 栈帧

每次函数调用都会在栈上分配一段属于这次调用的空间，称为**栈帧**，也叫活动记录。一个典型的栈帧保存以下内容：

| 内容          | 作用                                                                     |
| :---------- | :--------------------------------------------------------------------- |
| 返回地址        | 当前函数执行完后回到调用者的位置。函数体内若还要调用其他函数，`jal`会覆盖 `$ra`，所以必须先在序言中把自己的 `$ra`存入栈帧。 |
| 放不进参数寄存器的实参 | 前4个参数走 `$a0`–`$a3`，更多参数由调用者放在栈上。                                       |
| 需要保留的寄存器旧值  | 被调用者若使用约定由它保存的非易失性寄存器，要先存旧值，返回前恢复。                                     |
| 局部变量        | 数组、结构体等不适合放在寄存器中的局部数据。                                                 |

`$fp`标记帧的基址，`$sp`标记当前栈顶，两者共同界定当前帧的范围。函数返回时先恢复保存的寄存器和返回地址，再把 `$sp`恢复到进入函数时的位置，整帧占用的空间就被释放。

> [!NOTE]
> 栈帧的具体布局由调用约定决定。`$fp`可以指向帧的高地址端，也可以指向低地址端，偏移的正负随之改变；阅读汇编时要先确认当前约定，不要默认某个字段固定在`0($fp)`。

## 调用机制

### 寄存器分工

MIPS的调用约定把一部分寄存器固定用于传递信息和维护栈：

| 寄存器         | 用途      |
| :---------- | :------ |
| `$a0`–`$a3` | 传递前4个参数 |
| `$v0`–`$v1` | 存放返回值   |
| `$ra`       | 保存返回地址  |
| `$sp`       | 栈顶指针    |
| `$fp`       | 帧指针     |

参数超过4个时，多出的参数由调用者放在栈上；调用结束后，调用者负责清理这部分参数空间。`$ra`、`$sp`、`$fp`都是单个寄存器，函数体内的一次新调用就可能改写 `$ra`，这正是函数体内还会发起调用的函数必须保存返回地址的原因。

### 调用者与被调用者

调用者把参数送入 `$a0`–`$a3`（或栈上），然后执行跳转链接指令`jal`。`jal`做两件事：把下一条指令的地址（PC+4）写入 `$ra`，再跳转到被调用者的入口。返回地址是调用点之后的指令，而不是`jal`本身。

被调用者分三个阶段工作：

1. **序言：保存现场并开辟栈帧**

   序言要保存调用者的 `$fp`、设置新的 `$fp`、调整 `$sp`开辟局部空间，并把 `$ra`和需要保留的寄存器存入栈帧；具体顺序由栈帧布局决定。叶子函数（不调用其他函数的函数）可以不保存 `$ra`。

2. **执行函数体**

   用 `$fp`加偏移访问局部变量和保存的寄存器；函数体内如有新的调用，新的被调用者会建立更低的栈帧。

3. **尾声：放置结果并恢复现场**

   把结果写入 `$v0`或 `$v1`，恢复保存的寄存器（包括调用者的 `$fp`）和 `$ra`，把 `$sp`恢复到进入函数时的位置以释放本帧，最后用`jr $ra`跳回调用者。

序言和尾声必须成对：序言保存了哪些寄存器，尾声就要按相反的顺序恢复哪些；序言开辟了多大空间，尾声就要释放多大空间。

### 递归与栈

栈是递归能够正确回溯的基础。递归调用与普通调用没有本质区别，只是被调用者又是同一个函数：

* **独立栈帧**：每进入一层递归，都会新建一个栈帧；不同层的同名参数和局部变量各自占用不同地址，互不覆盖。
* **状态保存**：每层栈帧都保存该层自己的参数、局部变量和返回地址。返回地址指向调用它的上一层，而不是最初的调用点。
* **逐层回溯**：到达递归基后开始返回，栈帧按后进先出的顺序逐个弹出，程序能回到上一层的调用位置继续执行。

如果没有栈，递归的每一层会覆盖上一层的返回地址和局部变量，回到上一层时就失去了继续执行所需的状态。

## 例子

**嵌套调用时栈帧如何变化**

假设`main`调用`A`，`A`调用`B`，三个函数都使用栈帧。

1. `main`运行：栈上只有`main`的栈帧。
2. `main`调用`A`：在`main`栈帧的下方（更低地址）建立`A`的栈帧，`$sp`移到`A`帧的栈顶。
3. `A`调用`B`：在`A`栈帧的下方建立`B`的栈帧，`$sp`继续下移。
4. `B`返回：`B`的栈帧被弹出，`$sp`回到`A`帧的栈顶，`A`的局部变量和保存的返回地址仍然完好；`A`继续执行`jal B`之后的指令。

可以看到，一次返回只销毁最上面的一层栈帧，不会清空整个栈。若`B`返回后`A`又调用`C`，`C`会复用`B`刚释放的那段空间。

**返回地址为什么必须入栈**

设`main`在地址`0x00400020`处执行`jal A`，`$ra`因此保存`0x00400024`。`A`的序言把`0x00400024`存入自己的栈帧；随后`A`在`0x00400100`处执行`jal B`，`$ra`被改写为`0x00400104`。

`B`返回时用`jr $ra`回到`0x00400104`，`A`继续执行。等`A`结束时，它从自己的栈帧取回`0x00400024`写入 `$ra`，再用`jr $ra`回到`main`。如果`A`没有保存最初的 `$ra`，`0x00400024`会被`jal B`覆盖，`A`就找不到回`main`的路。

## 练习

1. 依次把1、2、3压入栈，再连续弹出两次，第一次弹出的值是 \_\_\_\_\_\_（first-popped）。

   答案：3

   栈按后进先出工作，最后压入的3最先弹出；第二次弹出的是2，1仍留在栈中。

2. MIPS的栈向低地址方向生长。压入一个32位字后，`$sp`的值如何变化？

   * A.  减小4
   * B.  增大4
   * C.  保持不变
   * D.  减小32

   答案：A

   压栈先让 `$sp`减4取得空间，再写入一个字；减32是把32位错当成32字节。

3. 一个典型的栈帧可能保存下列哪些内容？

   * A.  返回地址
   * B.  放不进参数寄存器的实参
   * C.  需要跨调用保留的寄存器旧值
   * D.  程序中所有的全局变量

   答案：A、B、C

   栈帧保存与本次调用有关的状态：返回地址、放不下的参数、需要恢复的寄存器和局部变量。全局变量不在栈帧里，它们有独立的存储区域。

4. 帧指针 `$fp`的主要作用是什么？

   * A.  始终指向栈顶，随压栈和出栈移动
   * B.  指向当前栈帧的固定基址，便于用固定偏移访问局部变量和保存的寄存器
   * C.  保存函数的返回值
   * D.  保存调用结束后的返回地址

   答案：B

   `$sp`会随压栈和出栈变化，`$fp`在函数执行期间保持不动，所以用 `$fp`加偏移访问帧内数据更稳定。返回地址由 `$ra`保存。

5. MIPS用固定的寄存器承担调用中的不同角色。

   1. `$ra`保存的是什么？

      * A.  返回地址
      * B.  栈顶地址
      * C.  帧基址
      * D.  函数返回值

      答案：A

      `jal`把下一条指令的地址写入 `$ra`，被调用者返回时用`jr $ra`跳回这个地址。

   2. 调用有5个参数的MIPS函数时，第5个参数通常放在哪里？

      * A.  `$a0`
      * B.  `$v0`
      * C.  栈上
      * D.  `$ra`

      答案：C

      `$a0`–`$a3`只能容纳前4个参数，第5个及之后的参数由调用者放在栈上。

6. 递归函数每进入一层新的调用时，栈会发生什么变化？

   * A.  新建一个独立的栈帧，保存该层的参数、局部变量和返回地址
   * B.  所有层共用同一个栈帧，只覆盖其中的变量
   * C.  只在到达递归基时建立一个栈帧
   * D.  递归不使用栈，返回地址保存在静态存储区

   答案：A

   每层递归都有独立的栈帧，才能同时保留各层的状态；返回时按后进先出的顺序逐层弹出。

7. `main`调用`A`，`A`调用`B`。`B`执行`jr $ra`返回后，`$sp`指向哪里？

   * A.  `main`的栈帧
   * B.  `A`的栈帧顶部
   * C.  `B`的栈帧顶部
   * D.  空栈

   答案：B

   `B`的尾声只释放`B`自己的栈帧，`$sp`回到`A`帧的栈顶；`A`的栈帧和`main`的栈帧都还在。

## 交互探索

交互演示：调用如何展开，又如何返回？。逐步查看阶乘的调用栈，区分等待中的栈帧与正在执行的调用。 请在站点操作演示。