Lecture 4: 栈抽象、栈帧与用栈做算术 (The Stack Abstraction, Stack Frames, and Arithmetic Using a Stack)
Lecture 4: 栈抽象、栈帧与用栈做算术 (The Stack Abstraction, Stack Frames, and Arithmetic Using a Stack)
概述
第 3 讲给出了调用约定，但没有回答”参数、返回值、返回地址、局部变量究竟放在哪里”——本讲给出答案： 放在栈 (stack) 上的一块连续区域里，这块区域叫栈帧 (stack frame / activation record)。 本讲引入 LIFO 语义、两条指令的 push/pop、R6 栈指针与 R5 帧指针的分工，以及完整的 LC-3 栈帧布局； 并用两个真实例子把它落地：用栈计算后缀表达式 1 2 + 3 4 - *（即 (1+2)*(3-4)），以及一个带完整帧的加法子程序。 这套机制正是 C 中 automatic 变量、递归与”栈溢出”的物理基础，也是后续数组、指针与动态数据结构的前提。
核心概念与底层机制图解
- 栈抽象 (Stack Abstraction)：栈是一种只能在顶端进出的数据结构，提供 LIFO（后进先出） 语义——像一摞餐盘，只能把新盘子放在最上面、也只能从最上面取走。
底层机制图解：
操作 含义 与队列 (queue, FIFO) 的对比（BFS 用队列，见第 1 讲） PUSH 把数据放到栈顶 队列：从尾部加入 POP 取走栈顶数据 队列：从头部取出 栈的生长方向（关键约定）： 高地址 +----------+ ← 栈底 (base)：一开始 R6 指向这里，此时栈为空 低地址 +----------+ ← 栈顶 (top)：R6 指向最后一个被压入的字；压栈时地址减小内存里”栈顶以上（更高地址）”的内容是旧数据：还在内存里但已不属于栈——弹出并不擦除数据。
作用域与存储期：栈上的数据是 automatic storage duration：进入函数/块时创建、离开时销毁，生命周期与”活跃的调用”严格对应；C 中函数内定义的普通变量就在这类存储里。
- PUSH / POP 的两条指令实现：LC-3 没有
PUSH/POP指令，但每个操作恰好用两条指令完成——压栈 = 先把手指往下挪一格再放东西，弹栈 = 先拿起东西再把手指往上挪一格。底层机制图解：
压栈（push R0） 弹栈（pop 到 R0） ADD R6,R6,#-1 ; 先腾出空间 LDR R0,R6,#0 ; 先取数据 STR R0,R6,#0 ; 再存入数据 ADD R6,R6,#1 ; 再收回空间顺序不能颠倒：
ADD R6,R6,#-1放到后面就会写错格子、甚至覆盖别的帧；两条移动指令一条#-1、一条#1，对称且容易检查。作用域与存储期：被压入的值活到它被弹出为止；一旦弹出，它对应的存储期就结束了（比特还在内存里，但读取它是未定义行为——这正是”返回局部变量地址”错误的根源）。
- R6 栈指针与 R5 帧指针 (Stack Pointer and Frame Pointer)：
R6指向栈顶（一直在动，像”当前手的位置”），R5指向当前帧的基准（本层内固定不动，像”本层书本的封面标签”）。底层机制图解：本课与 MP 使用的完整帧布局（高地址在上、低地址在下）：
高地址 +--------------------------+ \| caller 的栈帧 \| 调用者的帧 +--------------------------+ \| parameters \| ← R5+4, R5+5, ...（第一个参数固定在 R5+4） +--------------------------+ \| return value | ← R5+3 ┐ | return address (R7) | ← R5+2 ├ 这三格是 linkage（连接信息） | previous frame pointer | ← R5+1 ┘ +--------------------------+ \| local variable 0 | ← R5+0 ← R5 指向局部变量底部 | local variable 1, ... | ← R5-1, R5-2, ... 低地址 +--------------------------+ ← R6 指向栈顶（最低的活动字）关键顺序（课程真实约定，见
translate.asm的FIND_ABS）：R5+0（及R5-1、R5-2、…）= 局部变量；R5+1= 旧帧指针；R5+2= 返回地址；R5+3= 返回值；R5+4、R5+5、… = 参数。返回值必须在R5+3，因为它要紧贴在第一个参数R5+4之下，调用者才能用一条ADD R6,R6,#(nparams+1)同时弹掉参数和返回值（538-mt1-review：”Pop parameters and return value (destroy the params)”）。作用域与存储期：
R5/R6在子程序入口保存、出口恢复，因此每个活跃的调用都有自己的一对值；配合”每次调用都有自己的帧”，就得到 C 中局部变量互不干扰与递归可行的保证。
- 为什么两者缺一不可：R6 在函数体内不断移动，R5 不动——R6 像电梯楼层号（一直在变），R5 像”我家在 5 楼”，用它来算相对位置。
底层机制图解：
时刻 R6 R5 R5-R6 刚建好帧 R5 R5 0 ← 两者相同 压 2 个参数后 R5-2 R5 2 ← R6 变了；参数仍在 R5+4、R5+5 调用返回后 R5 R5 0 又压 1 个临时值 R5-1 R5 1 用 R6 定位参数：LDR R0,R6,#2 的偏移每次都不同（无法使用） 用 R5 定位参数：LDR R0,R5,#4 永远成立x86-64 的调用约定（
rbp帧指针 +rsp栈指针）与 LC-3 完全同构；高优化下编译器会”省略帧指针”，代价是调试器无法可靠地还原调用栈。作用域与存储期：
R5让”帧内偏移”成为编译期常量（编译器符号表里find_abs/num → R5+4那一列），R6只负责空间的分配与回收。
- 建立与拆除栈帧 (Prologue / Epilogue)：调用者压参数，被调用者建帧，返回时按相反顺序拆帧——像进房间先挂外套摆好工具（prologue），离开前收好工具取回外套（epilogue）。
底层机制图解：
① 调用者压参数（右到左）：先压 p2（在更高地址），再压 p1（落在栈顶 = R6，它就是新帧的 R5+4） ② 调用者 JSR 子程序 ；R7 ← 返回地址 ③ 被调用者 prologue（FIND_ABS 的写法：k 个局部变量就压 3+k 格） ADD R6,R6,#-(3+k) ；3 格 linkage + k 个局部变量 STR R5,R6,#1 ；R5+1 ← 旧帧指针（此时 R6+1 正是将来的 R5+1） ADD R5,R6,#0 ；R5 = R6；R5+0 就是第一个局部变量 STR R7,R5,#2 ；R5+2 ← 返回地址 ④ 函数体：局部变量用 R5+0、R5-1、…，参数用 R5+4、R5+5、… ⑤ 被调用者 epilogue STR R0,R5,#3 ；返回值写进 R5+3（紧贴第一个参数之下） LDR R7,R5,#2 ；取回返回地址 LDR R5,R5,#1 ；恢复调用者的帧指针 ADD R6,R6,#(k+2) ；弹出局部变量与 linkage，只把 R5+3 的返回值留在栈顶 RET ；JMP R7 ⑥ 调用者：LDR R0,R6,#0 读返回值，再用一条 ADD R6,R6,#(nparams+1) 弹掉参数与返回值（
FIND_ABS有 1 个局部变量：压 3+1=4 格、epilogueADD R6,R6,#3；FOO有 2 个局部变量：压 5 格、ADD R6,R6,#4。 没有局部变量时（translate.asm的MAIN）只压 3 格并令R5 = R6-1，R5+1…R5+3的语义完全不变。）作用域与存储期：帧的存活期 = 一次调用；
R5的恢复使调用者的作用域不受影响，这就是”两个函数里的同名变量互不干扰”的机制来源。
- 用栈做算术 (Arithmetic Using a Stack)：后缀（postfix）表达式天然对应”遇到数就压栈、遇到运算符就弹两次再压结果”；中缀
1 + 2 × 3有歧义、需要优先级规则，而后缀1 2 3 × +无歧义，连括号都不用。底层机制图解：把
(1+2)*(3-4)写成后缀1 2 + 3 4 - *并用 R6 执行：输入记号 动作 栈内容（栈顶在左） R6 1 push 1 [1] base-1 2 push 2 [2, 1] base-2 + pop 2 和 1，push 1+2=3 [3] base-1 3 与 4 各压一次栈 [4, 3, 3] base-3 - pop 4 和 3，push 3-4=-1 [-1, 3] base-2 * pop -1 和 3，push 3×(-1) [-3] base-1 结束 结果在栈顶 结果 = -3实现上只需要”弹两个、算、压一个”的子程序，每个都恰好是
LDR R1,R6,#1（更深的操作数）+LDR R0,R6,#0（栈顶）+ADD R6,R6,#2+ 计算 +ADD R6,R6,#-1+STR。作用域与存储期：栈上每个操作数的存储期就是它参与运算的那一瞬间；这种数据流驱动的求值方式也是 JVM 字节码与许多解释器的模型。
- 栈与堆相向增长 (Stack and Heap Grow Toward Each Other)：两个区域从内存两端出发，中间是自由空间——栈像从天花板往下挂的盘子，堆像从地面往上堆的箱子。
底层机制图解：
高地址 +--------------------+ \| 系统空间 / I/O | xFE00 起；栈 stack 从上方往下增长 ↓（R6/R5） | ↓ | | ↑ | | 堆 heap | 向上增长 ↑ malloc 从低处往高处要空间 | 全局数据 global data| R4 指向这里（本课约定 x4000 起） | 代码 code | 从 x3000 开始 低地址 +--------------------+malloc与函数调用在同一个地址空间的两端抢空间，这是”栈溢出”与”内存耗尽”在系统层面的真实图景。作用域与存储期：栈对应 automatic、堆对应 allocated（
malloc→free）、全局数据对应 static；三种存储期在内存图上就是三段不同的区域。
- 栈溢出与下溢 (Overflow / Underflow)：LC-3 的栈没有任何检查——一摞盘子堆到顶会塌，抽空了还继续抽也会塌，机器不会报警，只会悄悄写坏别人的数据。
- 底层机制图解：溢出（压栈过多，R6 撞上堆或全局数据）在 LC-3/嵌入式/内核里造成静默的数据破坏 (silent data corruption)，是最难查的一类 bug；在桌面/手机上则由硬件检测越界页、由操作系统让程序崩溃（
segmentation fault）。下溢（弹出过多，R6 越过栈底往上跑）会读到别的帧的内容。递归深度过大是溢出的最常见原因。 - 作用域与存储期：栈的检查是运行期问题，与语言层无关——C 不检查，LC-3 不检查，只有操作系统 + 硬件通过”页保护”近似兜底。
- 底层机制图解：溢出（压栈过多，R6 撞上堆或全局数据）在 LC-3/嵌入式/内核里造成静默的数据破坏 (silent data corruption)，是最难查的一类 bug；在桌面/手机上则由硬件检测越界页、由操作系统让程序崩溃（
- 与 C 的连接 (Connection to C)：C 的每一次函数调用都是本讲这套动作的翻译结果。写 C 时你只管定义变量、调用函数，编译器负责建帧、算偏移、拆帧。
底层机制图解：
C 语言 LC-3 机制（本讲） 函数参数 调用者压栈；第一个参数固定在 R5+4 局部变量 (automatic) R5+0, R5-1, ...（帧内偏移是编译期常量） return 值 写进 R5+3，调用者用 LDR R0,R6,#0 读回 递归 每层调用都有自己的帧（R5/R6 各不一样） 变量的作用域 (scope) 由符号表（R5+偏移）实现，与运行期无关教学目标 2/3/4/7（作用域与存储、调用约定、数组与指针、递归）都直接建立在这张帧图上。
作用域与存储期：C 的 storage duration 分类（automatic / static / allocated）与本讲的内存图一一对应；而 scope 是编译期概念，它决定编译器把名字翻译成哪个
R5+偏移。
代码示例与底层机制分析
示例 1：用栈执行后缀程序 1 2 + 3 4 - *
代码 (LC-3 assembly):
; 计算 (1+2)*(3-4)，即后缀式 1 2 + 3 4 - *
; 寄存器用途
; R6 : 栈指针（指向栈顶，栈向低地址增长）
; R0 : 操作数 / 返回值 / 算术临时
; R1 : 第二个操作数（更深的那个）与乘法计数器
; R2 : MULT 的累加器
.ORIG x3000
LEA R6,STK_BASE ; x3000: R6 = x4000，栈基址（空栈）
; ---- 执行 "1" 与 "2"：压栈 ----
AND R0,R0,#0 ; x3001
ADD R0,R0,#1 ; x3002
ADD R6,R6,#-1 ; x3003 压栈的固定两步
STR R0,R6,#0 ; x3004
AND R0,R0,#0 ; x3005
ADD R0,R0,#2 ; x3006
ADD R6,R6,#-1 ; x3007
STR R0,R6,#0 ; x3008
; ---- 执行 "+" ----
JSR STACKADD ; x3009: 弹出 2 与 1，压回 3
; ---- 执行 "3" 与 "4" ----
AND R0,R0,#0 ; x300A
ADD R0,R0,#3 ; x300B
ADD R6,R6,#-1 ; x300C
STR R0,R6,#0 ; x300D
AND R0,R0,#0 ; x300E
ADD R0,R0,#4 ; x300F
ADD R6,R6,#-1 ; x3010
STR R0,R6,#0 ; x3011
; ---- 执行 "-" 与 "*" ----
JSR STACKSUB ; x3012: 弹出 4 与 3，压回 -1
JSR STACKMUL ; x3013: 弹出 -1 与 3，压回 -3
LDR R0,R6,#0 ; x3014: 结果出栈
ADD R6,R6,#1 ; x3015
HALT ; x3016
; STACKADD -- 弹出两个操作数，压回它们的和
; 栈顶是 rhs，其下是 lhs；出口 R0 = lhs + rhs；改变 R0、R1
STACKADD
LDR R1,R6,#1 ; x3017: R1 ← lhs（更深的一个）
LDR R0,R6,#0 ; x3018: R0 ← rhs（栈顶）
ADD R6,R6,#2 ; x3019: 一次弹出两个
ADD R0,R0,R1 ; x301A: R0 ← lhs + rhs
ADD R6,R6,#-1 ; x301B: 压回结果
STR R0,R6,#0 ; x301C
RET ; x301D
; STACKSUB -- 弹出两个操作数，压回 lhs - rhs
STACKSUB
LDR R1,R6,#1 ; x301E: R1 ← lhs
LDR R0,R6,#0 ; x301F: R0 ← rhs
ADD R6,R6,#2 ; x3020: 弹出两个
NOT R0,R0 ; x3021: 取 rhs 的补码
ADD R0,R0,#1 ; x3022: R0 ← -rhs
ADD R0,R1,R0 ; x3023: R0 ← lhs - rhs
ADD R6,R6,#-1 ; x3024: 压回结果
STR R0,R6,#0 ; x3025
RET ; x3026
; STACKMUL -- 弹出两个操作数，压回 lhs * rhs
; 它要调用 MULT，所以必须先把 R7 保存到栈上（第 3 讲的 R7 纪律）
STACKMUL
ADD R6,R6,#-1 ; x3027: 在栈上腾一格保存 R7
STR R7,R6,#0 ; x3028: 现在栈布局是 [R7, rhs, lhs]
LDR R1,R6,#2 ; x3029: R1 ← lhs（跳过 R7 与 rhs）
LDR R0,R6,#1 ; x302A: R0 ← rhs
JSR MULT ; x302B: R0 ← lhs * rhs
LDR R7,R6,#0 ; x302C: 恢复返回地址
ADD R6,R6,#1 ; x302D: 丢掉保存的 R7
ADD R6,R6,#2 ; x302E: 弹出两个操作数
ADD R6,R6,#-1 ; x302F: 压回乘积
STR R0,R6,#0 ; x3030
RET ; x3031
; MULT -- 用重复加法计算 R0 * R1（假设 R1 >= 0），结果放 R0；改变 R1、R2
MULT AND R2,R2,#0 ; x3032: R2 ← 0
ADD R1,R1,#0 ; x3033: 测试乘数
BRz MULT_DONE ; x3034
MULT_L ADD R2,R2,R0 ; x3035: 累加
ADD R1,R1,#-1 ; x3036
BRnp MULT_L ; x3037
MULT_DONE
ADD R0,R2,#0 ; x3038
RET ; x3039
.BLKW #64 ; x303A..x3079: 给栈留出空间
STK_BASE ; x307A: 空栈时 R6 指向这里
.END
【代码做什么？】
LEA R6,STK_BASE把栈指针指到栈底；此时”栈是空的”（没有任何字低于 R6 属于栈）。- 每个数字记号（1、2、3、4）都用固定两条指令压栈：
ADD R6,R6,#-1然后STR R0,R6,#0。 - 每遇到运算符就
JSR对应子程序：取两个操作数、一次弹出、算出结果、再压回；STACKMUL在调用MULT前把 R7 压栈保存，返回前恢复。 - 最后
LDR R0,R6,#0取回栈顶结果并弹出：R0 = -3（=xFFFD），即(1+2)*(3-4)。
【底层机制透视】
- 栈的”弹出”只是移动指针：
ADD R6,R6,#2之后两个操作数仍在内存里，但已经不属于栈；再压一个新值就会覆盖它们。”一次弹两个”之所以安全，是因为栈是连续内存（等价于两次ADD R6,R6,#1）；而任何”部分弹出”都会让栈失去平衡。 MULT的循环次数取决于操作数的值：R1是乘数（此处lhs = 3），每次减一，内层ADD R2,R2,R0把rhs累加进去。负的rhs能工作（累加负数），但负的R1会死循环——这就是”接口假设必须写进 CIS”的例子。- R7 保存在栈上（比第 3 讲的固定
.BLKW槽更安全），因此STACKMUL即使被再次进入也不会互相覆盖。
【内存布局图解】（STK_BASE = x4000，逐步执行）
初始: R6 = x4000（空栈）
push 1/2: x3FFF = 1、x3FFE = 2 R6 = x3FFE 栈(顶在左): [2, 1]
STACKADD: 读 M[R6+1] = 1 (lhs)、M[R6+0] = 2 (rhs) → R6 = x4000 → 压回 3 于 x3FFF
push 3/4: x3FFE = 3、x3FFD = 4 R6 = x3FFD 栈: [4, 3, 3]
STACKSUB: 读 3 (lhs) 与 4 (rhs) → 3-4 = -1 → R6 = x3FFE，M[x3FFE] = -1 栈: [-1, 3]
STACKMUL: 压 R7 到 x3FFD → 读 3 (lhs) 与 -1 (rhs) → JSR MULT（累加 3 次 -1）→ R0 = -3
→ 弹两格、压回 → R6 = x3FFF，M[x3FFF] = -3 栈: [-3]
结束: LDR R0,R6,#0 → R0 = xFFFD = -3；R6 = x4000（栈恢复为空）
内存快照: x3FFF = xFFFD(-3) 仍在栈上；x3FFE = xFFFD(-1)、x3FFD = R7、x3FFC = 3 都已弹出（属"旧数据"）
【与汇编的对应】：这段程序与它的”高级语言版本”（示例 3）逐句对应——C 的 push(x)/pop() 就是那两条指令，sp 就是 R6，stack[] 就是 x4000 以下的 LC-3 内存；能手工完成的”栈机器求值”是理解所有表达式求值的通用语言。
示例 2：一个带完整栈帧的子程序 SUM2
代码 (LC-3 assembly):
; SUM2 -- 把栈上的两个参数相加，返回值留在栈顶
; 调用接口 (CIS)
; 输入 : 两个参数由调用者压栈（右到左：先压 p2，再压 p1，所以 p1 在栈顶 = R5+4）
; 输出 : 返回值在 M[R6]（即帧内的 R5+3）；调用者用一条 ADD 同时弹掉参数与返回值
; 改变 : R0、R1（caller-saved）
; 副作用: 无（只读写自己的帧）
; 帧布局（R5 相对，与 translate.asm 的 FIND_ABS 完全一致）：
; R5+5 = p2 R5+4 = p1 R5+3 = 返回值 R5+2 = 返回地址
; R5+1 = 旧帧指针 R5+0 = 局部变量
.ORIG x3000
LEA R6,STK_BASE ; x3000: R6 = x305A
LD R0,VAL_B ; x3001: p2 先压（右到左 → p2 在更高地址）
ADD R6,R6,#-1 ; x3002
STR R0,R6,#0 ; x3003
LD R0,VAL_A ; x3004: p1 后压 → 落在栈顶，成为新帧的 R5+4
ADD R6,R6,#-1 ; x3005
STR R0,R6,#0 ; x3006
JSR SUM2 ; x3007: R7 ← x3008
LDR R0,R6,#0 ; x3008: 读返回值（= 35）——R6 正指向它
ADD R6,R6,#3 ; x3009: 一条 ADD 弹掉 2 个参数 + 1 个返回值
HALT ; x300A
SUM2 ; x300B: ---- 被调用者 ----
ADD R6,R6,#-4 ; x300B: prologue：3 格 linkage + 1 个局部变量
STR R5,R6,#1 ; x300C: R5+1 ← 调用者的帧指针（必须在改 R5 之前）
ADD R5,R6,#0 ; x300D: R5 = R6，R5+0 就是第一个局部变量
STR R7,R5,#2 ; x300E: R5+2 ← 返回地址
LDR R1,R5,#4 ; x300F: R1 ← p1（第一个参数固定在 R5+4）
LDR R0,R5,#5 ; x3010: R0 ← p2
ADD R1,R1,R0 ; x3011: R1 ← p1 + p2
STR R1,R5,#0 ; x3012: 局部变量 ← 和
STR R1,R5,#3 ; x3013: epilogue：返回值写进 R5+3
LDR R7,R5,#2 ; x3014: 取回返回地址
LDR R5,R5,#1 ; x3015: 恢复调用者的帧指针
ADD R6,R6,#3 ; x3016: 弹出局部变量与 linkage（返回值除外）→ R6 = R5+3
RET ; x3017
VAL_A .FILL #42 ; x3018
VAL_B .FILL #-7 ; x3019
.BLKW #64 ; x301A..x3059: 栈空间
STK_BASE ; x305A: 空栈位置
.END
【代码做什么？】
- 调用者把参数从右向左压栈：先
p2 = -7（落在更高地址），再p1 = 42（落在栈顶 = 将来的R5+4）；JSR把返回地址放进 R7。 - prologue 压 3+1=4 格：把旧帧指针存到
R6+1（R5 = R6之后它就是R5+1），令R5 = R6，再把返回地址存到R5+2。 - 函数体用
LDR R1,R5,#4、LDR R0,R5,#5从固定偏移取参数，相加后写进局部变量R5+0。 - epilogue 把结果写进
R5+3、恢复 R7 与 R5、用ADD R6,R6,#3让 R6 落在返回值上；调用者读结果（35）后用一条ADD R6,R6,#3弹掉 2 个参数与返回值。
【底层机制透视】
- 参数在 R5+4 而不是 R5+0：因为被调用者的 linkage 与局部变量都压在参数的下面（更低地址）；第一个参数是最后一个被压入的，所以位置固定。
STR R5,R6,#1必须在ADD R5,R6,#0之前：一旦 R5 被覆盖，调用者的帧指针就永远丢失。此时还没设 R5，所以用R6+1作基址——而R5 = R6之后R6+1正是R5+1。- 返回值的位置决定调用者如何弹栈：
R5+3紧贴在第一个参数R5+4之下，所以RET之后 R6 指向返回值、参数就在它上面，调用者于是能用一条ADD R6,R6,#(nparams+1)同时弹掉两者。若返回值放在别处（例如R5+1），调用者就得先弹掉连接残留、再单独弹参数，一条指令完不成——这正是课程规定”返回值必须在 R5+3”的原因。 - epilogue 的两条
LDR不能交换：LDR R7,R5,#2必须用旧 R5 作基址；先恢复 R5 再去读R5+2只会读到调用者帧里的垃圾值。
【内存布局图解】（prologue 完成后，R5 = x3054）
地址 内容 R5 相对 说明
x3059 xFFF9 (-7) R5+5 参数 p2（先压 → 高地址）
x3058 x002A (42) R5+4 参数 p1（后压 → 栈顶方向）
x3057 x0023 (35) R5+3 返回值（紧贴第一个参数之下）
x3056 x3008 R5+2 返回地址（JSR 写入的 R7）
x3055 x0000 R5+1 旧帧指针（调用者的 R5）
x3054 x0023 (35) R5+0 局部变量（和） ← R5 = R6 = x3054
x305A STK_BASE 调用前的 R6（空栈位置；x3053 以下是 SUM2 的帧）
函数体执行时 R5 = R6 = x3054；若又压了两个临时值，R6 = x3052（R5−R6 = 2），
但 LDR R1,R5,#4 仍正确取到 p1 —— 这就是"为什么要留着 R5"。
epilogue 之后 R6 = R5+3 = x3057（指向返回值）、R5 = x0000；
调用者 ADD R6,R6,#3 后 R6 = x305A，与调用前完全一致（栈平衡）。
【与汇编的对应】（逐条手算执行结果）
| 时刻 | R0 | R1 | R5 | R6 | 内存变化 |
|---|---|---|---|---|---|
LD R0,VAL_B 后 | #−7 | — | x0000 | x305A | — |
| 压 p2 后 | #−7 | — | x0000 | x3059 | M[x3059] = −7 |
LD R0,VAL_A 后 / 压 p1 后 | #42 | — | x0000 | x3058 | M[x3058] = 42（p1 成为 R5+4） |
JSR 后（prologue 前） | #42 | — | x0000 | x3058 | R7 = x3008 |
ADD R6,R6,#-4 后 | #42 | — | x0000 | x3054 | — |
STR R5,R6,#1 后（R5 还是旧值） | #42 | — | x0000 | x3054 | M[x3055] = 0（旧帧指针 → R5+1） |
ADD R5,R6,#0 后 | #42 | — | x3054 | x3054 | R5 = R6 |
STR R7,R5,#2 后 | #42 | — | x3054 | x3054 | M[x3056] = x3008（返回地址） |
| 求和并存储后 | #−7 | #35 | x3054 | x3054 | M[x3054]=35（局部变量） |
| epilogue 后 | #−7 | #35 | x0000 | x3057 | M[x3057]=35（返回值 → R5+3） |
RET 后 / ADD R6,R6,#3 后 | #35 | #35 | x0000 | x305A | R6 先指向返回值，读回后用一条 ADD 弹掉参数与返回值，栈完全恢复 |
即 R0 = 35，正是 42 + (−7)。
示例 3：C 版本的后缀求值器（同一算法的”高级语言形态”）
代码 (C):
/* ECE 220 -- Lecture 4 example: arithmetic on a stack.
*
* Running the postfix program "1 2 + 3 4 - *", which is (1 + 2) * (3 - 4).
* The array below plays the role of LC-3 memory, sp plays the role of R6,
* and push/pop are exactly ADD R6,R6,#-1 + STR and LDR + ADD R6,R6,#1.
*/
#include <stdio.h>
#include <stdint.h>
#define STK_SIZE 16
static int32_t stack[STK_SIZE]; /* LC-3 memory used as the stack */
static int32_t sp = STK_SIZE; /* R6: index of the top element */
static void push(int32_t value)
{
sp = sp - 1; /* ADD R6,R6,#-1 : make space first */
stack[sp] = value; /* STR R0,R6,#0 : then store */
}
static int32_t pop(void)
{
int32_t value = stack[sp]; /* LDR R0,R6,#0 */
sp = sp + 1; /* ADD R6,R6,#1 : remove space */
return value;
}
static void show(const char *label)
{
int32_t i;
printf("%-12s stack (top first):", label);
if (sp == STK_SIZE) {
printf(" <empty>");
}
for (i = sp; i < STK_SIZE; i = i + 1) {
printf(" %d", (int)stack[i]);
}
printf(" [R6 offset = %d]\n", (int)(sp - STK_SIZE));
}
int main(void)
{
const char *program[] = { "1", "2", "+", "3", "4", "-", "*" };
int32_t i;
show("start");
for (i = 0; i < 7; i = i + 1) {
const char *token = program[i];
if (token[0] >= '0' && token[0] <= '9') {
push((int32_t)(token[0] - '0'));
printf("push %s\n", token);
} else {
int32_t rhs = pop();
int32_t lhs = pop();
int32_t result = 0;
if (token[0] == '+') {
result = lhs + rhs;
} else if (token[0] == '-') {
result = lhs - rhs;
} else {
result = lhs * rhs;
}
push(result);
printf("%s: %d %c %d = %d\n", token, (int)lhs, token[0], (int)rhs,
(int)result);
}
show(" after");
}
printf("result = %d\n", (int)pop());
return 0;
}
编译与运行：
$ gcc -g -std=c99 -Wall -Werror ece220_l04_rpn.c -o ece220_l04_rpn
$ ./ece220_l04_rpn
start stack (top first): <empty> [R6 offset = 0]
push 1
after stack (top first): 1 [R6 offset = -1]
push 2
after stack (top first): 2 1 [R6 offset = -2]
+: 1 + 2 = 3
after stack (top first): 3 [R6 offset = -1]
push 3
after stack (top first): 3 3 [R6 offset = -2]
push 4
after stack (top first): 4 3 3 [R6 offset = -3]
-: 3 - 4 = -1
after stack (top first): -1 3 [R6 offset = -2]
*: 3 * -1 = -3
after stack (top first): -3 [R6 offset = -1]
result = -3
【代码做什么？】
sp从STK_SIZE出发表示”空栈”；push先减sp再写入，pop先读出再增sp——与ADD R6,R6,#-1+STR/LDR+ADD R6,R6,#1一一对应。- 主循环遍历记号数组：数字解析为整数后压栈；运算符先弹
rhs、再弹lhs，按lhs op rhs计算后压回。 show每步打印栈内容与”R6 偏移”，便于与手算的 LC-3 栈图对照；最后输出result = -3，与示例 1 的R0 = xFFFD一致。
【底层机制透视】
sp用的是数组下标而非地址，sp - STK_SIZE就是”R6 相对栈底移动了多少个字”。stack[sp]的”先减指针、再写入”顺序保证了栈向低地址生长；反过来写就与 LC-3 语义相反。pop()不会擦除stack[sp]——与 LC-3 一样，”弹出”只是移动指针，旧值仍在内存里。- 运算符分派用
if/else链实现，对应 LC-3 的比较与分支；真实编译器会把它变成跳转表 (jump table)。
【内存布局图解】
全局数据区（static storage duration）
+-----------------------------+ 0x4040a0 附近
| stack[0] ... stack[15] | 32 字节；sp 从 16 开始，向索引 0 方向"生长"
| sp = 0 | 执行到最后：栈里只剩 1 个元素
+-----------------------------+
栈内容（打印中"-"一步之后）：
+---+---+---+---+---+
| 4 | 3 | 3 | ? | ? | ... 打印时从 sp 到 15 依次输出 → "4 3 3"
+---+---+---+---+---+
↑
sp（栈顶）；索引 13、14 的旧值已不在"栈上"
【与汇编的对应】
; C: sp = sp - 1; stack[sp] = value;
ADD R6,R6,#-1 ; sp--
STR R0,R6,#0 ; stack[sp] = value
; C: value = stack[sp]; sp = sp + 1;
LDR R0,R6,#0 ; value = stack[sp]
ADD R6,R6,#1 ; sp++
; C: rhs = pop(); lhs = pop(); result = lhs - rhs; push(result);
JSR POP_R0 ; rhs 在 R0
ADD R3,R0,#0 ; 暂存 rhs（R3 是 caller-saved）
JSR POP_R0 ; lhs 在 R0
NOT R3,R3 ; -rhs
ADD R3,R3,#1
ADD R0,R0,R3 ; lhs - rhs
JSR PUSH_R0
一次调用一层帧：递归的前奏
把 SUM2 的 prologue/epilogue 放在一个自我调用的子程序里，就得到递归：每层调用都在更低地址压出自己的一份完整帧（自己的 R5、R7、局部变量），同一段代码于是可以有任意多份互不干扰的数据。在真实机器上可直接观察（本机实测每层相差 0x30 = 48 字节）：
$ gcc -g -std=c99 -Wall -Werror ece220_l04_frames.c -o ece220_l04_frames && ./ece220_l04_frames
main : &automatic = 0x7ffe86cb5c68
frame 3: &local = 0x7ffe86cb5c4c local = 30 （完整程序见 ece220_l04_frames.c）
frame 2: &local = 0x7ffe86cb5c1c local = 20 地址随 ASLR 变化，但逐层下降
frame 1: &local = 0x7ffe86cb5bec local = 10
frame 0: &local = 0x7ffe86cb5bbc local = 0
sum of the four locals = 60
在 LC-3 上重复同样的实验，就是观察 DEPTH_REPORT 每次 prologue 之后的 R5：每递归一层就减小固定的字节数， 直到 R6 撞上代码或全局数据——那就是前面说的”栈溢出”。
常见错误与调试技巧
- R6 失去平衡（弹栈数量算错）：调用者忘记执行
ADD R6,R6,#(nparams+1)，或弹多了把调用者的数据当参数弹掉；现象是程序”跑一会儿就错”，多个函数间互相踩数据。调试：在每个调用点前后比较 R6；gdb中用p $rsp（对应 R6）核对；lc3sim里print R6并用dump观察栈区。 - prologue 顺序写错：先
ADD R5,R6,#0再STR R5,R6,#1，把新帧指针当成旧帧指针存进R5+1；或者把偏移写成#3（那是返回值的位置）。现象是调用者返回后局部变量与 R5 全部错乱。调试：逐条单步 prologue，检查M[R5+1]是否等于调用前的 R5，M[R5+2]是否等于JSR的下一条指令地址。 - 用 R6 而不是 R5 访问参数：写成
LDR R0,R6,#2，一旦函数体内压过临时值，偏移就失效，现象是”参数偶尔读错”。调试：检查所有访问参数/局部变量的指令是否都以 R5 为基址；在gdb中打印$rbp/$rsp的差，确认帧内偏移恒定。 - 返回局部变量的地址：
int32_t *f(void) { int32_t x = 1; return &x; }——帧一拆，x就没有存储期了，现象是调用后读到的值随机变化。调试：-Wall -Werror会给出-Wreturn-local-addr；valgrind --tool=memcheck ./prog或gcc -fsanitize=address -g能直接指出”使用了已释放的栈内存”。 - 把”弹出”误解为”擦除”：弹出后仍去读
M[R6]之上的旧值，误以为那是”栈上的数据”，于是读到残留值。调试：用x/8xw $rsp（gdb）或dump（lc3sim）观察栈区，对照”R6 以上不属于栈”逐字检查。 - 栈溢出：无限递归或每层帧过大（例如把大数组声明为局部变量）。LC-3 上是静默数据破坏，Linux 上是
Segmentation fault。调试：gdb中bt 50看递归深度；ulimit -s查栈上限；把递归改成用显式栈的迭代（如同示例 1）。
关键要点
- 栈提供 LIFO 语义；在 LC-3 上压栈是
ADD R6,R6,#-1+STR R0,R6,#0，弹栈是LDR R0,R6,#0+ADD R6,R6,#1，顺序不可颠倒，而且”弹出”只移动指针、不擦除数据。 R6是栈指针（一直移动），R5是帧指针（本帧内固定）；没有 R5，函数体一旦压入临时值，就无法再用固定偏移访问参数与局部变量。C 的自动变量、递归、作用域隔离全部依赖这一点。- 栈帧布局（课程真实约定）：
R5+0/R5-1/… 局部变量、R5+1旧帧指针、R5+2返回地址、R5+3返回值、R5+4/R5+5/… 参数；返回值必须在R5+3，这样调用者才能用一条ADD R6,R6,#(nparams+1)同时弹掉参数与返回值。 - 用栈求值是表达式求值的通用模型（遇到数压栈、遇到运算符就”弹两次、算、压一次”）：
1 2 + 3 4 - *最终得到-3，与 C 版本一致；而栈与堆从地址空间两端相向增长，相遇即内存耗尽，栈的溢出/下溢在 LC-3 上没有任何检查，只会造成静默的数据破坏。
思考题（带答案）
问题 1：为什么 LC-3 的帧布局把返回值放在 R5+3（紧贴第一个参数 R5+4 之下），而不是像局部变量那样放在 R5 以下？如果 C 规定实参从左向右压栈，R5+4 还会是第一个参数吗？
答案：因为调用者返回后要用一条 ADD R6,R6,#(nparams+1) 同时弹掉参数和返回值；由于参数在 R5+4 及以上连续排列，只有把返回值放在它们正下方的 R5+3，这一条指令才能一次清掉两者（538-mt1-review 的原话是 “Pop parameters and return value”）。那些”连接信息”（旧帧指针 R5+1、返回地址 R5+2）由被调用者的 epilogue 自己弹掉，调用者不必关心。如果改成从左向右压栈，最后一个参数会落在 R5+4、第一个参数跑到更远处；对固定参数个数的函数两者都可行，但变参函数（如 printf）就无法知道第一个参数在哪里，所以 C 选择右到左压栈。
问题 2：某个 LC-3 子程序的 epilogue 写成下面这样，哪里有问题？会造成什么后果？
STR R0,R5,#3 ; 返回值 → R5+3
LDR R5,R5,#1 ; 先恢复调用者的帧指针
LDR R7,R5,#2 ; 再想用 R5+2 取回返回地址
ADD R6,R6,#3
RET
答案：LDR R5,R5,#1 与 LDR R7,R5,#2 的顺序反了：R5+1 是旧帧指针、R5+2 才是返回地址，一旦先用 LDR R5,R5,#1 恢复 R5，R5+2 就变成调用者帧里的某个字，LDR R7,R5,#2 取到垃圾值，RET 跳向随机位置（ADD R6,R6,#3 也会因为基准不清而算错栈顶）。正确顺序是先取回返回地址、再恢复帧指针、最后调 R6——即 STR R0,R5,#3 / LDR R7,R5,#2 / LDR R5,R5,#1 / ADD R6,R6,#3 / RET。
问题 3：下面的 C 函数返回了局部变量的地址。请解释为什么它危险，并给出两种修法。
int32_t *make_value(int32_t v)
{
int32_t local = v * 2;
return &local; /* 危险 */
}
答案：local 具有 automatic storage duration，家在 make_value 的栈帧里；函数一返回帧就被拆除（LC-3 上就是 R5/R6 被恢复），那块空间随时会被下一次调用覆盖，因此返回的指针指向已经结束存储期的对象，读取它是未定义行为。两种修法：(1) 让调用者提供存储 void make_value(int32_t v, int32_t *out) { *out = v * 2; }，或直接返回值 int32_t make_value(int32_t v) { return v * 2; }；(2) 改用 allocated storage：int32_t *p = malloc(sizeof(int32_t)); *p = v * 2; return p;（调用者负责 free）。编译器在 -Wall 下会给出 -Wreturn-local-addr 警告——让工具替你发现存储期错误。