Lec6: Activation Records

What does Chapter 6 focus on?#

Chapter 5 解决了”AST 是否语义合法”——我们现在有了 typed AST + symbol tables。Chapter 6 紧接着回答:

函数调用在机器上到底是怎么跑起来的?局部变量、参数、返回地址都放在哪?

答案是 Activation Record(活动记录),也叫 Stack Frame(栈帧)——它是编译器前端与机器层面真正接轨的第一个概念。

Chapter 6 的两大主题:

1. Stack Frames(栈帧的通用概念)——调用约定、frame pointer、static link、caller/callee-save、escape 分析等
2. Frames in the Tiger Compiler——Tiger 编译器中 Frame 模块的抽象接口和 Translate 层

Storage Organization#

从编译器作者的视角看,目标程序运行在自己的 逻辑地址空间 里,每个程序值都有一个位置。一个典型的运行时内存布局:

1
 Low  ┌──────────────┐
2
      │    Code      │  可执行目标代码
3
      ├──────────────┤
4
      │    Static    │  编译期大小已知:全局常量、编译器生成的数据
5
      ├──────────────┤
6
      │    Heap      │  程序控制的动态分配 (C: malloc/free) ↓
7
      ├──────────────┤
8
      │  Free Memory │
9
      ├──────────────┤
10
      │    Stack     │  函数调用期间生成的 activation records ↑
11
 High └──────────────┘

• Code / Static<大小在编译期就定下来>
• Heap / Stack<都是> dynamic,但用法完全不一样
  • Heap 由程序显式控制
  • Stack 跟函数调用的 LIFO 结构一一对应

按习惯,stack 从高地址向低地址生长。

为什么函数调用要用 stack?#

考虑 Tiger 代码:

1
function f(x: int): int =
2
  let var y := x + x
3
  in if y < 10 then f(y) else y - 1
4
  end

• 一次 invocation 就叫一次 activation
• 每次调用 f,都会 新建一个 x 的实例(由 caller 初始化)
• 在很多语言(C / Pascal / Java)中,局部变量在函数返回时销毁
• 递归调用意味着很多个 x 同时存在

函数调用天然是 LIFO(Last In, First Out,后进先出)<最后调用的最先返回>。所以用 stack 这个 LIFO 数据结构来放局部变量再自然不过。

1
main() 调 f() 调 g() 调 h()
2

3
调用顺序: main → f → g → h    (依次 push)
4
返回顺序: h → g → f → main    (依次 pop)

每个活着的 activation 在 control stack 上都有一个 activation record(也叫 frame)。

Part 1: Stack Frames 的通用结构#

为什么不能只用纯 push/pop?#

理论上 stack 只要 push / pop 就够了,但实际上:

• 局部变量是 成批 push/pop 的(进入函数一次性开,退出一次性收)
• 局部变量不一定创建后就立刻初始化
• 我们想访问 stack 深处 的变量,而不只是栈顶

所以实际实现是:把 stack 当成一个大数组,用 Stack Pointer (SP) 这个寄存器指向某个位置(栈向低地址生长,SP 指栈顶,也就是当前最低的已用地址):

• SP 上面(更高地址):已分配(历史 frame)
• SP 下面(更低地址):garbage(还没用到)

1
高地址 ↑
2
       ┌──────────────┐
3
       │   已分配     │
4
       │  (in use)    │
5
   SP →├──────────────┤   ← 栈顶
6
       │   garbage    │
7
       │  (free)      │
8
低地址 ↓

操作语义:

• push:SP ← SP − size(SP 往下走,新空间纳入”已分配”)
• pop :SP ← SP + size(SP 往上走,腾出的空间变回 garbage)
• 访问深处变量:MEM[SP + offset](offset > 0,往上数)

Stack Frame 的角色#

Stack 通常 只在进入函数时增长,一次增加足以容纳该函数所有局部变量的大小;退出前再收缩回去。

一个函数的 activation record / stack frame = stack 上分给这个函数的那一片区域,装着:

• 局部变量
• 参数
• 返回地址
• 临时值

核心问题 怎么布局,才能让 caller 和 callee 正确通信?

典型的 Stack Frame 布局#

1
                    ┌─────────────────┐ ↑ 高地址
2
                    │   argument n    │ ↖
3
                    │      ...        │  │ incoming args
4
                    │   argument 2    │  │ (caller 压的,但属于
5
                    │   argument 1    │  │  current function 使用)
6
     frame pointer →│   static link   │ ↙
7
                    ├─────────────────┤ ← current frame 起点
8
                    │ local variables │ ↖
9
                    │                 │  │
10
                    │ return address  │  │
11
                    │   temporaries   │  │ current function 自用
12
                    │ saved registers │  │
13
                    │                 │  │
14
                    │   argument m    │  │ outgoing args
15
                    │      ...        │  │ (current 作为 caller,
16
                    │   argument 2    │  │  给下一层函数准备)
17
                    │   argument 1    │  │
18
     stack pointer →│   static link   │ ↙
19
                    ├─────────────────┤
20
                    │                 │   next frame 将在这里展开
21
                    │                 │
22
                    └─────────────────┘ ↓ 低地址

⚠️ 图里上方的 argument 1..n 其实是 current function 的 incoming args——虽然物理上是 caller 压的(所以画在 previous frame 区),但它们正是”传给我”的参数。最下面那段 argument 1..m 才是 current function 作为 caller 要传给 下一个 函数的 outgoing args。

为什么 argument 在高地址、local vars 在低地址? 因为 stack 向下生长,push 得越早,地址越高:

① caller 先 push incoming args(最高) → ② call 指令 push return address → ③ current 进入后 SP 下移开 local(更低) → ④ current 要调下一层时 push outgoing args(最低)

从 FP 看出去天然对称:

• MEM[FP + 正 offset] → 访问 incoming arguments(上方)
• MEM[FP − 正 offset] → 访问 local variables / saved regs(下方)

各字段含义:

Frame Pointer#

设 g 调用 f(a1, ..., an),g 是 caller,f 是 callee:

进入 f 时:

1. SP 原先指向 g 传给 f 的第一个参数
2. 在 frame 里保存旧的 FP
3. FP ← SP
4. SP ← SP − framesize

f 退出时:

1. SP ← FP
2. 从 frame 里恢复旧的 FP

1
Before call:            After call:
2
┌──────────┐            ┌──────────┐
3
│ frame of │← FP        │ frame of │← FP (old)
4
│    g     │            │    g     │
5
│          │← SP        ├──────────┤← FP (new)
6
└──────────┘            │ frame of │
7
                        │    f     │
8
                        │          │← SP
9
                        └──────────┘

当 frame size 可变或 frame 不连续时,FP 才真正需要。如果 frame size 固定,FP = SP + framesize,FP 就是一个”虚构”的寄存器——编译器知道,不需要真寄存器保存。

Registers: Caller-save vs Callee-save#

访问 register 比访问 memory 快,但寄存器数量有限(一般 32 个),所有函数都要用。

场景: f 在 reg r 里存了局部变量,然后调用了 g,g 也要用 r——必须有人 save / restore r。

由调用约定决定哪些寄存器是哪种。

Parameter Passing<为什么要用寄存器>?#

Tiger 用 pass-by-value<传实参的值>,修改形参不影响实参。

如果参数 只放 stack,每次函数调用都要写内存、读内存,开销很大。现代机器的调用约定通常:

前 k 个参数(k = 4 或 6)放寄存器 $r_p, ..., r_{p+k-1}$,剩下的放内存。

1
void f(int a) {     // 假设 a 在 r1
2
  int z = ...;
3
  h(z);             // h 的第一个参数也要放 r1 → 先 save a
4
  int t = a + 2;    // 调用后还要 restore a
5
}

Return Address#

如果 g 中调用指令的地址是 a,那么 f 返回后应继续从 a + 1 执行——这就是 return address。

现代机器的 call 指令 一般把 return address 放到一个 专用寄存器(MIPS 的 $ra),而不是写入栈里:

• Leaf procedure<不再调用别人>,$ra 不会被覆盖,无需写 frame
• Non-leaf procedure<在调用别人之前必须把> $ra 存到 frame(除非做了 inter-procedural 寄存器分配)

Frame-Resident Variables#

现代调用约定<参数>、返回地址、返回值都在寄存器里,很多局部变量和中间值也放寄存器。

那什么时候一个值必须写到 frame?只有必要的时候:

• 变量将通过 reference 传递(需要真实地址)
• 变量被嵌套内层函数访问
• 值太大,单个 register 放不下
• 变量是 数组,需要地址算术
• 持有它的 register 要挪作他用(比如参数传递)
• 局部变量太多,register 不够——spill 到 frame

Part 2: Static Links —— 如何支持嵌套函数#

问题<嵌套函数访问外层变量>#

在允许嵌套函数声明的语言(Pascal、ML、Tiger)里,内层函数可以用外层函数的变量:

1
function prettyprint(tree: tree) : string =
2
  let var output := ""
3
      function write(s: string) =
4
        output := concat(output, s)        (* 访问 prettyprint 的 output *)
5
      function show(n: int, t: tree) =
6
        let function indent(s: string) =
7
          ( for i := 1 to n do write(" ");   (* 访问 show 的 n、调 write *)
8
            output := concat(output, s) )     (* 访问 pp 的 output *)
9
        in ... end
10
  in show(0, tree); output end

通过 FP 能访问 当前函数自己 的局部变量(每个变量相对 FP 的 offset 编译期就定了)。

但嵌套函数怎么访问非本地变量?

解决方案 1 Link#

每次调用 f,都把 “在程序文本中直接包围 f 的函数 g 的最近一次 activation record 的指针” 作为一个额外参数传进去。这个指针就是 static link。

1
int g(int x) {
2
  int f(int y) { ... }     // f 的 static link 指向 g 的 frame
3
  return f(x) + 1;
4
}

1
Frame of f:             ... → Frame of g
2
  static link ────────────────┘
3
  ...

1
pp's frame         show's frame        indent's frame
2
┌───────────┐      ┌───────────┐       ┌───────────┐
3
│static link│←─────│static link│←──────│static link│
4
│  output   │      │     n     │       │           │
5
└───────────┘      └───────────┘       └───────────┘

1
int f(link, int x, int y) {
2
  int m;
3
  int g(link, int z) {
4
    int h(link) {
5
      return link->prev->m + link->z;   // 沿 link 链上去
6
    }
7
    return 1;
8
  }
9
  return 0;
10
}

解决方案 2#

全局数组 d[],d[i] 指向 当前最近进入的、嵌套深度为 i 的函数的 frame。

1
nesting depths:           d[] array:
2
main      1               d[2] ────→ prettyprint's frame
3
  pp      2               d[3] ────→ show's frame
4
    write 3               d[4] ────→ indent's frame
5
    show  3
6
      indent 4

访问非本地变量时,直接 d[depth] 一步到位,不用沿链找。

1
pp 调 write:  d[3] ← write.FP    (write 执行期间 d[3] 指向 write)
2
write 返回:   d[3] 恢复
3
pp 调 show:   d[3] ← show.FP    (show 执行期间 d[3] 指向 show)

解决方案 3 Lifting#

重写程序<把每个非本地变量改写成显式参数>。

1
// 原始                          // Lambda-lifted
2
int f(int x, int y) {            int f(int x, int y) {
3
  int m;                           int m;
4
  int g(int z) {                   int g(int &m, int z) {
5
    int h() {                        int h(int &m, int &z) {
6
      return m + z;                    return m + z;
7
    }                                }
8
    return 1;                        return 1;
9
  }                                }
10
  return 0;                        return 0;
11
}                                }

从最内层开始往外变换,把每层用到的外层变量都加成引用参数。

Higher-Order Functions —— 栈用不完了#

1
fun f(x) =
2
  let fun g(y) = x + y
3
    in g
4
  end
5
val h = f(3)
6
val z = h(5)              (* 这里 f 已经返回,但 g 还引用 f 的 x! *)

• 如果 g 被 返回出去,f 的 frame 不能随着 f 的返回而销毁——x 还活着
• 栈方式不再适用,局部变量的生命周期超过了所在函数

1
调 f(3):          f 返回后:         调 h(5):
2
┌─────────┐       ┌─────────┐       ┌─────────┐
3
│ x = 3   │       │garbage  │       │garbage  │ ← g 想读 x,读到垃圾!
4
└─────────┘       └─────────┘       └─────────┘

1
堆上:                   h ──→  ┌─────────────┐
2
                              │ code: g     │
3
                              │ x: 3        │  ← 由 GC 管理
4
                              └─────────────┘

Part 3: Frames in The Tiger Compiler#

为什么要抽象?#

不同机器的调用约定不同(参数位置、寄存器编号、对齐方式……)。Tiger 把机器细节封装在 Frame 模块里,前端(Semant / Translate)根本不需要知道是 MIPS 还是 Pentium。

1
┌────────────────────────────┐
2
│         semant.c           │
3
├────────────────────────────┤
4
│        translate.h         │
5
│        translate.c         │   (管嵌套 scope / static link)
6
├─────────────┬──────────────┤
7
│   frame.h   │    temp.h    │   (机器独立接口)
8
├─────────────┼──────────────┤
9
│ mipsframe.c │   temp.c     │   (机器相关实现)
10
└─────────────┴──────────────┘

两层抽象:

• frame + temp<机器无关的>”变量放在哪”视图
• translate<处理嵌套作用域>(static link),是 Semant 看到的接口

1
translate.c 调用 frame.h 的接口（机器无关）
2
           ↓
3
frame.h 定义抽象接口
4
           ↓
5
mipsframe.c 提供具体实现（机器相关）

frame.h 抽象接口#

1
typedef struct F_frame_  *F_frame;
2
typedef struct F_access_ *F_access;
3
typedef struct F_accessList_ *F_accessList;
4

5
F_frame      F_newFrame(Temp_label name, U_boolList formals);
6
Temp_label   F_name(F_frame f);
7
F_accessList F_formals(F_frame f);
8
F_access     F_allocLocal(F_frame f, bool escape);

• F_frame<保存该函数所有> formal / local 信息
• F_access<描述一个变量> 在 frame 里 还是 在 register 里(是抽象数据类型)
• F_newFrame(name, l)<新建> frame,l 是 k 个 bool——每个 formal 是否 escape
• F_allocLocal(f, escape)<为新局部变量分配位置>

1
struct F_access_ {
2
  enum {inFrame, inReg} kind;
3
  union {
4
    int offset;          /* InFrame */
5
    Temp_temp reg;       /* InReg */
6
  } u;
7
};

“Shift of View” 看到的 vs callee 看到的#

同一个参数,caller 和 callee 看到的位置 不一样:

F_formals 返回的是 callee 视角 的 access list。

F_newFrame 为每个 formal parameter 要算两样东西:

1. 它在函数内部怎么看(register / frame)
2. 实现这个 “view shift” 所需的指令

1
function m(x: int, y: int) = (h(y,y); h(x,x))

Local Variables<何时调> F_allocLocal?#

每次遇到 variable declaration,就调 F_allocLocal 分一个位置(temp or frame slot);遇到 end / } 时 忘掉名字绑定,但空间仍然保留。

也就是:整个函数内,每个变量声明都分配一个独立的位置,即使名字复用。

1
function f() =
2
  let var v := 6 in           (* v1 *)
3
    (print(v);
4
     let var v := 7            (* v2,独立于 v1 *)
5
     in print(v) end;
6
     print(v);                 (* 这里访问的是 v1,print 6 *)
7
     let var v := 8 in         (* v3 *)
8
       print(v)
9
     end;
10
     print(v))                 (* 仍然是 v1 *)
11
  end
12
(* 输出:6 7 6 8 6 *)

Calculating Escapes:escape.c#

F_allocLocal(f, escape) 的第二个参数从哪来?需要一个 pre-pass:

1
void Esc_findEscape(A_exp exp);

遍历整棵 AST,对每个变量声明记 “它是否 escape”。判断标准前面讲过(pass-by-ref / 取地址 / 嵌套函数访问)。

实现上用的是环境:

1
static void traverseExp(S_table env, int depth, A_exp  e);
2
static void traverseDec(S_table env, int depth, A_dec  d);
3
static void traverseVar(S_table env, int depth, A_var  v);

若某变量在比它声明 深 的函数里被用到,就标记 escape。

Temporaries and Labels<抽象>”寄存器”和”地址”#

语义分析阶段要给参数/局部变量分配寄存器,要给函数体选地址——但此刻 太早了,我们还不知道真实的机器寄存器编号和代码地址。

解决办法<抽象>

• Temp<一个>”临时寄存器”,相当于无限多个虚拟寄存器
• Label<一个>”机器地址”,最终地址还不确定

1
typedef struct Temp_temp_ *Temp_temp;
2
Temp_temp  Temp_newtemp(void);             // 无限分发临时寄存器
3

4
typedef S_symbol Temp_label;
5
Temp_label Temp_newlabel(void);            // 无限分发 label
6
Temp_label Temp_namedlabel(string name);   // 指定汇编名
7
string     Temp_labelstring(Temp_label s);

Temp_namedlabel 要小心——不同 scope 里可能有同名函数,直接用名字可能撞。

Translate 层<在> Frame 之上管嵌套#

为什么不把 static link 塞进 Frame 模块?

因为很多源语言(C、Java)没有嵌套函数。Frame 模块应当独立于源语言。

Static link 的做法:当作一个隐藏的参数——Translate 对每个函数的 formals 列表偷偷加一个 static link 参数。

1
typedef struct Tr_access_ *Tr_access;
2
typedef ... Tr_accessList ...
3

4
Tr_level     Tr_outermost(void);
5
Tr_level     Tr_newLevel(Tr_level parent, Temp_label name,
6
                         U_boolList formals);
7
Tr_accessList Tr_formals(Tr_level level);
8
Tr_access    Tr_allocLocal(Tr_level level, bool escape);

1
/* 在 translate.c 内部 */
2
struct Tr_access_ { Tr_level level; F_access access; };

1
struct E_enventry_ {
2
  enum {E_varEntry, E_funEntry} kind;
3
  union {
4
    struct { Tr_access  access; Ty_ty ty; } var;
5
    struct { Tr_level   level;  Temp_label label;
6
             Ty_tyList  formals; Ty_ty result; } fun;
7
  } u;
8
};

一个访问链的例子#

1
function f(x: int) =
2
  let
3
    function g() = print_int(x)   (* g 的 level.parent = f 的 level *)
4
  in g() end

Semant 处理 print_int(x) 时:

1. x 的 E_VarEntry 里记了 Tr_access = { level=f, access=InReg/InFrame(...) }
2. 当前代码位于 g 的 level
3. g.level ≠ f.level → 需要沿 static link 爬 g.depth - f.depth 层
4. Translate 产出类似 MEM(FP + x_offset),其中 FP 是经过若干次 MEM(staticLink) 解引用后得到的 f 的 frame pointer

这正是 Chapter 7 IR 生成要做的事——Chapter 6 只是 把接口摆好。

Summary 6 的核心思路#

一个总的理解框架#

到这里,编译器视角下的 执行模型 初具雏形:

1
source → tokens → CST → AST → typed AST → typed AST + frame info

下一章 Chapter 7 会接着把 typed AST 真正翻译成 IR——那时候所有前几章铺好的 Tr_exp / Tr_access / F_access 才开始产出真正的代码。