Lec10: Liveness Analysis

What does Chapter 10 focus on?#

Chapter 9 把 canonical IR 翻成了 abstract assembly——指令选好了,但用的还是无穷多个 temporary(t1, t2, t3, ...)。真实机器只有几十个寄存器,根本装不下。Chapter 10 接着问:

怎么知道哪些 temporary “正在使用”,从而把它们挤进有限的寄存器里?

答案是 liveness analysis——一个典型的 dataflow analysis:

Chapter 10 的三个主题:

1. Liveness Analysis<用> dataflow equations 算出每个程序点上哪些变量”活着”
2. Theoretical Results<为什么必须用保守近似>(halting problem)、为什么迭代算法收敛到 least fixed point
3. Interference Graph<把> liveness 结果转成图,供下一章 register allocation 使用

我们在哪里?#

1
┌──────────────────────┐
2
│ Abstract Syntax Tree │
3
└──────────┬───────────┘
4
           ↓ Chapter 5–7
5
┌──────────────────────┐
6
│ IR Tree              │
7
└──────────┬───────────┘
8
           ↓ Chapter 8: Canonical IR
9
┌──────────────────────┐
10
│ Canonical IR list    │
11
└──────────┬───────────┘
12
           ↓ Chapter 9: Instruction Selection
13
┌──────────────────────┐
14
│ Abstract Assembly    │   ← 用无穷 temporary
15
└──────────┬───────────┘
16
           ↓ Chapter 10: Liveness Analysis  ← 你在这里
17
┌──────────────────────┐
18
│ Interference Graph   │
19
└──────────┬───────────┘
20
           ↓ Chapter 11: Register Allocation
21
┌──────────────────────┐
22
│ Real Assembly        │   ← 用真实寄存器
23
└──────────────────────┘

Part 1: Why —— 为什么要做 Liveness Analysis?#

矛盾#

要把多个 temporary 塞进同一个 register,必须先回答一个问题:

哪些 temporary 是”同时活着的”?

关键观察#

1
a := b + 1;
2
return a;

这里 b 在 a := b + 1 之后就再也不用了,而 a 是这之后才需要的——a 和 b 不会同时被需要,完全可以塞同一个 register。

只要能把所有这种”不重叠”的 temporary 配对挤压,就能用少量 register 装下大量 temporary。装不下的那些,溢出到内存(spill)。

Liveness 的非正式定义#

一个变量在某个程序点 live,当且仅当它当前持有的值在未来可能被用到。

注意是”持有的值”——如果以后会再赋值再读,那只是同名变量的不同生命周期。

Part 2: How —— Liveness 是 Backward Analysis#

直觉#

要回答”变量 x 在 statement n 之后还会被用到吗?“,得问两件事:

1. n 之后哪些 statement 可能执行? → 看 control flow graph
2. 那些 statement 用到 x 吗? → 分析每条 statement 的 use/def

由于”未来要不要用”这种问题天然是从后往前推:

Liveness 是 backward analysis——信息从程序的尾部沿 control flow 反向流动。

这跟 reaching definitions、available expressions 等”forward”问题正好相反。

Control Flow Graph(CFG)#

CFG 是 dataflow analysis 的舞台:

• node: 一条 statement / 指令(或 basic block)
• edge: 控制流。m → n 表示 m 之后可能执行 n

1
        a ← 0
2
   L1:  b ← a + 1        →     1: a := 0
3
        c ← c + b              2: b := a+1   ←┐
4
        a ← b * 2              3: c := c+b    │
5
        if a < N goto L1       4: a := b*2    │
6
        return c               5: a < N  ─────┘ (true → 2)
7
                               6: return c   (false from 5)

Part 3: What —— 形式化定义#

Use 和 Def#

也可反过来定义:

• def of variable v = 所有定义 v 的节点集合
• use of variable v = 所有使用 v 的节点集合

1
3: c := c + b      →   def(3) = {c},  use(3) = {b, c}
2
4: a := b * 2      →   def(4) = {a},  use(4) = {b}

Liveness 的精确定义#

A variable is live on an edge if there is a directed path from that edge to a use of the variable that does not go through any def.

通俗讲<沿控制流往下走>,先撞到 use 而不是 def——它才活着。如果先被重新赋值,旧值就死了。

“活着”的两个条件#

变量 a 在某条边上活着 ⟺

1. 未来会被用 —— 控制流上能找到一个 use(a)
2. 被用之前不被覆盖 —— 这条路径上没有 def(a)

1
       ●  v
2
       │      no def(v)
3
       ▼
4
       ●  use(v)         ← v live on the edge above

Part 4: Dataflow Equations#

三条规则推出方程#

从直觉一步步推到方程:

1
       n: ...
2
       /     \
3
     m1       m2
4
   in[m1]    in[m2]

合并 Dataflow Equations#

把 Rule 2 + Rule 3 合并:

$\boxed{\text{in}[n] = \text{use}[n] \cup (\text{out}[n] - \text{def}[n])}$

$\boxed{\text{out}[n] = \bigcup_{s \in \text{succ}[n]} \text{in}[s]}$

这两条方程是 Chapter 10 的灵魂。所有后续算法、定理都围绕它们展开。

1
in[n]  =  use[n]                     ← 自己要用的
2
       ∪  (out[n] - def[n])          ← 出口活着且自己没杀掉的

Part 5: Solving the Equations —— 迭代算法#

为什么不能一次算出来?#

方程是循环的——in[n] 依赖 out[n],out[n] 依赖 in[succ[n]],而 succ 可能绕回 n(循环)。所以得迭代到不动点(fixed point)。

算法#

1
for each n:
2
    in[n] ← {};  out[n] ← {}
3
repeat
4
    for each n:
5
        in'[n] ← in[n];  out'[n] ← out[n]
6
        in[n]  ← use[n] ∪ (out[n] - def[n])
7
        out[n] ← ⋃_{s∈succ[n]} in[s]
8
until in'[n] = in[n] AND out'[n] = out[n] for all n

为什么会终止?#

• use[n] 和 def[n] 是程序静态属性,已知且固定。
• 每次迭代,in[n] / out[n] 只会增加(单调),因为 use[n] 始终包含、out 来自 in[s] 的并集。
• 集合元素来自一个有限的全集(程序里所有变量),不可能无限增长。
• 单调 + 有上界 ⇒ 有限步必到不动点。

计算顺序很关键#

out[n] 依赖 in[s](s 是后继),而 in[n] 依赖 out[n]。所以:

Liveness flows backward along control-flow edges, and from out to in, so the computation should follow the same direction.

也就是按节点编号从大到小(从尾到头)、每个节点先算 out 再算 in,信息一次传播一长段。反过来按 1→6 算的话,要好多轮才传得回去。

Part 6: 实现层面的考虑#

Variant 1 Blocks 当节点#

只有一个前驱、一个后继的节点没意思——把这种节点跟邻居合并成 basic block,CFG 节点数大幅缩小,迭代轮数也变少。

块内 use/def 可以提前算好(只关心”块整体的 use/def”),块间再做 dataflow。

Variant 2<一次只算一个变量>#

不是每次都需要全套 in/out。某些场景下只需要追踪某个变量是否活着——按需计算。许多 temporary 的 live range 很短,这种”按需”很省。

Set 的实现 Array vs Sorted List#

平均每个集合元素数 < N/K 时,sorted list 更快。实际编译器多用 bit array,因为常量因子小、SIMD 友好。

Time Complexity#

设程序大小 N(节点数 ≤ N,变量数 ≤ N):

• 每次 set-union: O(N)(bit array 是 O(N/K),为简化记 O(N))
• 内层 for loop<每节点常数次> set 操作 ⇒ O(N²) per iteration
• 外层 repeat/out 集合大小总和 ≤ 2N²,每轮至少加一个元素,所以最多 O(N²) 轮

最坏(N⁴)。实际(N) ~ O(N²)(选合适的迭代顺序)。

Part 7: 理论结果 —— 不动点与保守近似#

Least Fixed Point#

方程可能有多个解。考虑下面的表(教材 Table 10.7):

• X 和 Y 都满足方程(Y 是把变量 d “假装也活着”)。两个都是 valid 解。
• Z 不满足方程——基于 Z 会推出”b 和 c 不冲突”,可能把它们分到同一寄存器,程序就错了。

1
1:     a := 0
2
2:     b := a + 1
3
3:     c := c + b
4
4:     a := b * 2
5
5:     if a < N goto 2
6
6:     return c

Conservative Approximation —— 保守近似#

任意 fixed point 都是 liveness 的保守上估:

也就是说,我们可能多说几个变量活着(寄存器多用一些),但绝不会漏说。

保守 = 安全<误判活着> ⇒ 多用 register,代码不优但正确;误判死了 ⇒ 寄存器复用导致值被覆盖,程序错。

Static vs Dynamic Liveness#

1
1: a := b * b              ← a >= 0
2
2: c := a + b              ← c >= b
3
3: if c >= b               ← always true!
4
4:     return a            ← 条件为「假」时走这条 → dead branch
5
5:     return c            ← 条件为「真」时走这条

为什么 line 4 是 dead branch?代数推一下:c - b = (b² + b) - b = b² ≥ 0,所以 c >= b 永远成立,跳进 line 4 的”假分支”在动态执行中永远进不去。

• Dynamic liveness<某个>实际执行会从 n 走到 use(a),且不经过 def(a)。
• Static liveness 上存在一条路径从 n 到 use(a),不经过 def(a)。

例子里 node 4 在动态执行中永远到不了,但 static analysis 只看 CFG 结构、不做算术推理,看到 node 3 → node 4 这条边就认为它可达——所以认为 a 在 node 1 之后是 live 的。

Static 总是 ⊇ Dynamic,所以 static liveness 是 dynamic liveness 的保守近似。

为什么必须保守? —— Halting Problem#

Theorem(Halting Problem). 不存在程序 H,对任意程序 P 和输入 X,(在不无限循环的前提下)能判定 P(X) 是否停机。

Corollary. 不存在程序 H’(P, L),能判定程序 P 中的标号 L 在某次执行中是否会被到达。

证明草图<若> H’ 存在,把程序结尾加一个 halt → goto L,就能用 H’ 判定 P 是否停机——矛盾。

推论<编译器>根本不可能精确知道一个变量是否真活,只能用静态、保守的近似。

设计原则 equation 应当设计成”任何解都是保守的”。这样优化结果至多 suboptimal,但绝不 incorrect。

Part 8: Interference Graph#

Interference 是什么?#

Interference: 阻止两个 temporary 共享同一个 register 的条件。

两类:

1. Overlapping live ranges<在某个程序点> a 和 b 同时活着 ⇒ 它们必须在不同寄存器。
2. 机器约束<某条指令的结果只能放进特定寄存器>,其他变量碰不得。比如 x86 的乘法结果固定到 RAX。

表示方式#

1
   a  b  c
2
a        x
3
b        x
4
c  x  x

1
    b
2
    │
3
    │      ← b 和 c 之间的边(b 与 c 干涉)
4
    c
5
    │
6
    │      ← c 和 a 之间的边(c 与 a 干涉)
7
    a

怎么从 liveness 构造 interference graph?#

1
for each n that defines variable a:
2
    for each b in out[n], b ≠ a:
3
        add edge (a, b) to interference graph

MOVE 指令的特殊处理#

考虑 t := s(纯 copy,不是 t := s + 1):

1
t := s        ← 此后 t 和 s 值相同
2
...
3
x := ... s ... ← use s
4
...
5
y := ... t ... ← use t

执行完 t := s 后,out[n] 里既有 t 又有 s——按基本规则会加 (s, t) 边。

但其实没必要!s 和 t 此时值相等,完全可以共用一个寄存器(把 MOVE 退化掉,直接复用)。

Zero-length live ranges#

如果某指令 def 了 a,但 a 之后再也没用——a 的 live range 长度为 0。

会不会造成问题?

• 如果是纯计算指令(a := b + c),不用 a 干脆别生成。
• 但如果指令有副作用(比如调用),还是得执行——它会占用某个 register。
• 那个 register 不能跟其他活着的变量重合。

结论 live range 仍然 interfere 它所重叠的活变量。这是 interference graph 构造时容易遗漏的边界。

Part 9: Tiger Compiler 中的实现框架#

(本节理论性较弱,只列接口,不展开)

1
1. Assem program  →  Control-flow graph     (FlowGraph 模块)
2
2. Control-flow graph  →  Liveness 分析     (Liveness 模块)
3
3. 副产物:Interference graph + MOVE pairs

FG_def(n) / FG_use(n) / FG_isMove(n) 提供节点的 use/def 信息; Live_liveness(flow) 返回 interference graph + 应当合并的 MOVE 对。

Summary 10 的核心思路#

一个总的理解框架#

到这里整个编译器已经能算出”哪些 temporary 互相冲突”。下一章 Chapter 11 用 图染色 把 interference graph 涂成 ≤K 色(K = 寄存器数),涂不开就 spill 到内存。

1
abstract assembly + flow graph
2
→ liveness (in/out)
3
→ interference graph     ← 你在这里
4
→ graph coloring → real assembly

学习路线建议#

按以下顺序推进,效率最高: