3.5函数调用与栈

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

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更稳定。

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

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

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

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

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

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

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

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

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

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