整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L12 注解幻灯片。
源网页：12.1 Annotated Slides | Procedures and Stacks
讲师：Chris Terman。图片直接引用 OCW 原站链接。
L12：过程与栈（Procedures and Stacks）
本讲讲清过程（procedure）抽象为何需要激活记录（activation record），以及为何 LIFO 栈能自然支持嵌套与递归；随后给出 Beta 上的 SP/LP/BP 约定、栈帧布局、callee-saves 契约，并用阶乘与“栈侦探”题目串起整套调用约定。
1. 过程：软件抽象（Procedures: A Software Abstraction）
过程/子程序：完成特定任务的指令序列，有唯一命名入口。可有形式参数（formal parameters）；调用时实参（arguments）与之对应。过程体可定义仅在执行期间存在的局部变量；可返回值，也可只为副作用而执行。
例：COPRIMES 只需知道 GCD 的入参/返回类型即可调用——实现被封装成黑盒。标准库提供大量预建过程（数学、容器、文件等）。过程抽象是高级语言表达力的核心。
2. 实现过程（Implementing Procedures）
两种思路：
- 内联（inline）：用过程体副本替换调用，实参代入形参（类似宏）。短过程有时值得；长过程多次调用会膨胀代码。递归在编译期无法终止展开 → 内联失败。
- 链接（link）：过程代码只保留一份；调用方求实参、存约定位置，
BR到入口并保存返回地址（return address）；过程算完把结果放约定位置，再JMP回返回地址。
3. 过程调用约定（Procedure Calling Convention）
需约定：实参放哪、返回值放哪。可尝试用寄存器：如 R1 起传参、R28 存返回地址（linkage pointer）、R0 返回值。BR/JMP 正好对应 call/return。
目标：所有调用与过程体用同一约定——含递归 fact(n-1) 与顶层 fact(3)。
4. 过程链接：初试（Procedure Linkage: First Try）
按上述约定编译 fact()：入参进 R1，BR 保存返回地址到 R28；递归时又把 n-1 写入 R1、新返回地址写入 R28——覆盖外层还需要的 n 与返回地址。深度为 时需要约 个存储槽，寄存器不够。禁止递归可绕过，但语言通常允许递归 → 必须动态为每次活跃调用分配存储。
5. 过程的存储需求（Procedure Storage Needs）
每次活跃调用需要：实参、返回地址、返回值、局部变量、以及调用方寄存器现场。不想限制参数/局部变量个数 → 每次调用一块存储，即激活记录。不能静态只为某过程留一块（递归有多份同时活跃）→ 调用时分配、返回时回收。
6. 激活记录（Activation Records）
fact(3)→fact(2)→fact(1)→fact(0)：每层调用创建自己的激活记录；嵌套调用返回后其记录先丢弃。LIFO：被调方记录总在调用方之前释放——调用方必须等被调返回才能结束。需要高效支持这种分配/释放的结构。
7. 洞察：需要栈！（Insight: We Need a Stack!）
激活记录按 LIFO 进出 → 栈（stack）：PUSH 加顶、POP 去顶。C 过程通常只访问栈顶记录；Java 等可访问其他活跃帧。闭包 / continuation（如 Python yield）需在返回后仍保留帧 → 纯栈不够，属更高级课程话题。
8. 栈实现（Stack Implementation）
Beta：专用 R29 = SP（stack pointer）。PUSH 时递增 SP，栈向高地址生长。约定：SP 指向下一个未用字；低于 SP 的地址是已分配内容。
栈纪律（stack discipline）：一段代码 PUSH 的内容必须在结束前 POP 掉，使 SP 恢复原值。栈放在大块内存区，系统常设最大栈长，溢出报错。Beta 用现有指令实现栈，纯软件约定；有的 ISA 有专用栈指令。
9. 栈管理宏（Stack Management Macros）
UASM 宏：
PUSH：先ADDC分配栈顶，再ST初始化（顺序重要：中断可能夹在两指令之间；先分配再写更安全）POP：先LD取值，再SUBC释放ALLOCATE/DEALLOCATE：预留/释放 个字（不必初始化）
见 PUSH/ALLOCATE 应能找到配对的 POP/DEALLOCATE。
10. 玩转栈（Fun With Stacks）
临时占用寄存器前可 PUSH 旧值，用完按相反顺序 POP 恢复（LIFO）。有了栈，即可解决激活记录的分配/释放问题。
11. 解决过程链接问题（Solving Procedure Linkage Problems）
栈上放激活记录：实参、局部变量、以及保存的 LP（以便嵌套调用）。职责分摊：
- 调用方（caller）：求实参并逆序
PUSH（第一实参最后压栈）；BR到入口，返回地址进 LP=R28；返回后DEALLOCATE去掉实参。 - 被调方完成帧的其余部分（下页）。
逆序原因后文说明（可变参数）。
12. 栈帧作激活记录（Stack Frames as Activation Records）
入口序列完成帧（也称 stack frame）：保存 LP；再保存调用方的 BP=R27，并用当前 SP 设本帧 BP；ALLOCATE 局部变量；再 PUSH 本过程将破坏的寄存器（callee saves：除 R0 外寄存器跨调用保持）。
有了 BP，帧内访问用相对 BP 的固定偏移，比相对 SP 更稳（SP 会随 PUSH/POP 变）。
13. 栈帧细节（Stack Frame Details）
回到问题：为何实参逆序压栈？
14. 实参顺序与 BP（Argument Order & BP Usage）
逆序后，第一实参（arg 0）相对 BP 偏移固定（如 ），与共压几个实参无关；第二参 …… C 的可变参数（如 printf：格式串在第一个实参）依赖这一点。局部变量亦固定偏移：第一局部 ，第二 …… 帧上更高地址可用于嵌套调用建新帧。
15. 过程链接契约（Procedure Linkage: The Contract）
Caller：逆序压实参 → BR 到入口（返回地址→LP）→ 返回后卸掉实参。
Callee：计算结果放 R0 → JMP 返回地址 → 卸掉自己压上的内容，栈恢复入口时模样 → 除 R0 外保持所有寄存器。
16. 过程链接模板（Procedure Linkage Templates）
入口：保存 LP、BP；MOVE(SP,BP)；ALLOCATE 局部；PUSH 将用寄存器。出口：按相反顺序 POP 恢复；MOVE(BP,SP) 隐式撤销 ALLOCATE；最后 JMP(LP) 回调用方。
17. 综合：阶乘（Putting It All Together: Factorial）
C 版 fact 的编译结果：入口/出口序列清晰；嵌套调用栈上传参并在返回后 DEALLOCATE；体用上讲模板。链接开销约十余条指令；对极短非递归过程，优化器可能选择内联。
18. 递归？（Recursion?）
已解决：每次调用新栈帧；返回按逆序释放。沿 BP 链可读出活跃调用、实参、局部变量 → stack trace（运行时出错时常打印）。能解读栈帧 ≈ 理解调用约定（测验常见题）。
19. 栈侦探（Stack Detective）
练习：已知 PC=0x40、栈转储，推断：
- 当前
fact实参为 3；沿保存的 BP/LP 找到原始调用实参为 6 - 原始调用的
BR在 0x7C（保存的 LP=0x80 为下一指令） - 即将执行的是
DEALLOCATE(1)（递归返回后的指令） - BP 等可由帧布局与十六进制地址推出
关键：会读帧布局、十六进制算术、区分递归返回地址与外部返回地址。
20. 专用寄存器小结（Summary of Dedicated Registers）
| 寄存器 | 角色 |
|---|---|
| R31 | ISA 规定恒为 0 |
| R30 | 留给下讲 Beta 实现（XP）；用户代码勿用 |
| R29 (SP) | 栈指针 |
| R28 (LP) | 链接指针（返回地址） |
| R27 (BP) | 基址指针（当前帧） |
21. 小结（Summary）
激活记录由 caller/callee 共同建造，返回时丢弃；含实参、保存的 LP/BP、其他被保存寄存器、局部变量。BP 指向当前帧；callee saves（除 R0）保证嵌套与递归安全。至此可编译并执行任意 C 程序（在约定意义下）。