# 3.5函数调用与栈

## 阅读入口

* [函数调用与栈帧](/knowledge/cs/computer-architecture/function-call-stack/)

## 一次调用要完成的事

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

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

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)`。

[来源：函数调用与栈帧](/knowledge/cs/computer-architecture/function-call-stack/#definition)

这份清单把一次调用拆成参数、控制、空间和结果四类事情。读下面一段寄存器分工时，把每件事对应到具体寄存器或栈上的位置，清单就不再是记忆项。

## 寄存器分工与调用序列

### 寄存器分工

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`跳回调用者。

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

### 递归与栈

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

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

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

[来源：函数调用与栈帧](/knowledge/cs/computer-architecture/function-call-stack/#properties)

`jal`写入 `$ra`、序言与尾声成对出现，这两点在知识点里已经拆开说明。下面的“读调用序列的顺序”只是把这段内容落到纸上的跟踪步骤。

## 学习安排

3.2和3.3讨论的是单条指令如何改变寄存器、内存与PC；这一节把若干条指令组合成一次完整的函数调用。读的时候分三个位置跟踪：调用点的`jal`、被调用者的序言与尾声、返回后继续执行的调用点。

教材用MIPS的调用约定，而前面的指令表是[Simple-MIPS教学指令集](/knowledge/cs/computer-architecture/simple-mips/)。`jal`、`jr`不在Simple-MIPS的指令表中，`$ra`、`$sp`、`$fp`也不在[CPU的核心部件](/knowledge/cs/computer-architecture/cpu-components/) 的寄存器用途表里；读这一节时按真实MIPS理解。`jal`也不等同于`goto`：它在跳转前还会把PC+4写入 `$ra`。

## 课程约定

* 画栈时先标出低地址端；栈向低地址生长，`$sp`指向当前栈顶。
* 教材把 `$fp`当作栈帧的基址，帧内字段用 `$fp`加偏移表示；`$sp`负责分配和释放空间。
* 前4个参数用 `$a0`–`$a3`，第5个起由调用者放在栈上；返回值用 `$v0`–`$v1`。
* 序言与尾声按“保存什么、恢复什么”成对记。教材用 `$sp = $fp`概括释放栈帧，各字段的具体偏移以教材图示为准。

## 读调用序列的顺序

1. 先找`jal`，标出调用点，以及 `$ra`在这一刻被写成哪个地址。
2. 进入被调用者，看序言保存了哪些寄存器、为栈帧分配了多大空间。
3. 看尾声是否按相反顺序恢复这些寄存器，并确认 `$sp`回到进入函数时的位置。
4. 遇到递归时，按“进入一层建一帧、返回一层弹一帧”画栈，不要把所有层画成同一帧。

## 易错点

* 压栈是让 `$sp`减4，不是加4；栈顶在低地址端。
* `$fp`在函数执行期间不变，`$sp`会随压栈和出栈变化；用 `$sp`访问局部变量时，偏移会跟着改变。
* `jal`会覆盖 `$ra`。函数体内还有调用时，要在序言里先把自己的返回地址存进栈帧，不能等到返回前才保存。
* 被调用者返回时只销毁自己的栈帧；调用者的局部变量和保存的寄存器仍在栈上，下一次调用会复用刚释放的空间。
* 递归的每一层都有独立的栈帧，返回地址和局部变量不能跨层共用。