Chapter10 - Liveness Analysis（活跃分析）

10.1 Liveness Analysis（活跃分析）

10.1.1 Why Liveness Analysis（为什么需要活跃分析）？

中间表示（IR）可以使用无限多个临时变量（temporaries）。真实机器，只有有限数量的寄存器。这是编译器中的巨大矛盾。

如果临时变量 a 和 b 不会同时“正在使用”，那么它们可以放进同一个寄存器。
如果寄存器不够，多余变量可以存进内存。

编译器必须知道哪些变量会同时使用。

活跃变量分析：用于确定每个变量的活跃性。如果一个变量保存的值未来可能还会被使用，那么它是活跃的（live）。

10.1.2. liveness Analysis - How

如何进行活跃分析？

问题变成：变量 x 在语句 n 之后会不会再被使用？

哪些语句可能在 n 之后执行？
建立控制流图（control flow graph）
x 是否在这些语句中被使用？
分析语句

活跃分析是：逆向分析（Backward Analysis）,从未来往过去推。

10.1.3. 控制流图 control flow graph（ CFG）示例

构建控制流图：

节点（node）一条语句。
边（edge）控制流。如果语句 m 后可能执行语句 n：则有边：m → n

代码：

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

形成：

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

因为if 可能跳回,所以形成循环。

10.1.3.1. b 在哪里活着？

代码：

2: b := a+1
3: c := c+b
4: a := b*2

第3句用了 b，第4句也用了 b，因此在 2→3，3→4 这两条边上，b 是 live

但 4 之后，b 不再被用。所以 4 后面 b 不再活跃。

2 前面 b 不活着，因为但凡跳转到 2 或者执行到 2 的指令，b 都会被覆盖，前面 b 根本不影响。

10.1.3.2. 变量 a 的活跃性

代码：

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

形成：

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

a 在 if 判断中被使用。因此 4 定义的 a，在 5 使用，所以 4→5 上，a live。

因为存在循环 5 -> 2 a 的活跃性会“绕回来”。5 -> 2 a 活跃

1 -> 2 a 活着，因为 1 被赋值 2 时使用

其他时候都不活跃。

10.1.3.3. 变量 c 的活跃性

1 -> 2 , 2->3 , 3->4 , 4->5 , 5 -> 2 , 2-> 3 c 都是活跃的，因为数据要在 3 被使用

但是这个程序我们发现 c 没有被定义，所以要么是参数要么是局部变量

10.1.3.4. 总结

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

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

边	a	b	c
1->2	live		live
2->3		live	live
3->4		live	live
4->5	live		live
5->2	live		live
5->6			live

由于 a 和 b 从不会同时活跃，它们可以放进同一个寄存器。

10.2 Flow Graph Terminology

10.2.1. 定义

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

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

out-edges 出边
- 例如 5 的出边是 5->2 和 5->6
in-edges 入边
- 例如 2 的入边是 1->2 和 5->2
pred[n] 节点 n 的前驱集合
- 例如 pred[2] = {1,5}
succ[n] 节点 n 的后继集合
- 例如 succ[5] = {2,6}

10.2.2. Uses and Defs

定义：

use：使用变量的节点，或者该节点使用的变量
def：定义变量的节点，或者该节点定义的变量

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

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

def(a) = {1,4}
def(3) = {c}
use(a) = {2,5}
use(3) = {b, c}

10.2.3. Liveness 正式定义

如果从某条边开始，存在一条路径：

能到达该变量的 use
且中间没有经过新的 def

则变量在该边上是 live。

如果一个变量：在某节点某一条入边上是 live，那么它是该节点的 live-in 变量。

如果变量：在节点的任意一条出边上 live，那么它是该节点的 live-out 变量。

in[n]：节点 n 的 live-in 变量集合

out[n]：节点 n 的 live-out 变量集合

10.3. 活跃分析数据流方程

10.3.1. 规则：

If a ∈ in[m] for ∃m∈succ[n]，then a ∈ out[n]

如果 n 的某个后继节点 m 的 in[m] 中有 a，则 a ∈ out[n]

意思：如果后面 a 是 live 的。那么，当前节点出去时，a 必须 live。
If a ∈ use[n]，then a ∈ in[n]

如果语句 n 使用 a，那么 a 在进入 n 时必须 live。

辨析： If a ∈ out[n], then a ∈ in[n] 正确吗？错误！因为 n 可以定义 a

If a ∈ out[n] and a ∉ def[n]，then a ∈ in[n]

如果：a 在离开 n 时 live，且 n 没有重新定义 a，那么 a 在进入 n 时也 live。

如果未来还要用，且当前没覆盖，那现在必须保留。

10.3.2. 例子

p: b := c+1
    |
    v
n: b < 10
  |    |
  v    v
  m1   m2

假如

in[m1] = {d}, in[m2] = {e}

根据规则 1，out[n] = in[m1] ∪ in[m2] = {d, e}

根据规则 2 和 3， in[n] = {b} ∪ {{d, e}- ∅} = {b, d, e}

out[p] = {b, d, e}

in[p] = {c} ∪ ({b, d, e}- {b}) = {c, d, e}

10.3.3 活跃方程

公式1

\[ in[n] = use[n] \cup (out[n] - def[n]) \]

意思：进入 n 时 live 的变量 = 当前要用的变量 * 未来要用且当前没覆盖的变量

公式2

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

意思：出去时 live 的变量 = 所有后继入口 live 的并集

10.4. 求解

10.4.1. 如何求解数据流方程

核心算法

初始化：

in[n]={}
out[n]={}

然后：

for each n
  in[n] <- {}; out[n] <- {}


repeat
  for each n
    in′[n] ← in[n]; out′[n] ← out[n]
    in[n] ← use[n] ∪ (out[n] − def[n])
    out[n] ← ⋃in[s] (for all s ∈ success [n])   
until in′[n] = in[n] and out′[n] = out[n] for all n

10.4.2. Calculation of Liveness（活跃性计算）

活跃变量方程（Liveness Equations）如何一步一步迭代求解

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

1 -> 2 -> 3 -> 4 -> 5 -> 6
     ^              |
     |______________|

左边表格中列出了：

节点	use	def
1	∅	a
2	a	b
3	b,c	c
4	b	a
5	a	∅
6	c	∅

10.4.2.1. 自顶向下分析

\[ in[n] = use[n] \cup (out[n] - def[n]) \]

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

当前：

\[ out[2]=\emptyset \]

因此：

\[ in[2] = use[2]\cup(out[2]-def[2])={a} \]

\[ use[3]=\{b,c\}, def[3]=\{c\} \]

但当前：

\[ out[3]=\emptyset \]

\[ in[3]=\{b,c\}\cup(\emptyset-\{c\})=\{b,c\} \]

总之最后计算出：

#	use	def	1st in	1st out	2nd in	2nd out	3rd in	3rd out	4th in	4th out	5th in	5th out	6th in	6th out	7th in	7th out
1		a				a		a		ac	c	ac	c	ac	c	ac
2	a	b	a		a	bc	ac	bc	ac	bc	ac	bc	ac	bc	ac	bc
3	bc	c	bc		bc	b	bc	b	bc	b	bc	b	bc	bc	bc	bc
4	b	a	b		b	a	b	a	b	ac	bc	ac	bc	ac	bc	ac
5	a		a	a	a	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac
6	c		c		c		c		c		c		c		c

10.4.2.2. 自底向上分析

可以通过反方向计算来加快收敛。也就是不要从1算到6，而是从6算到1。

	use	def	1st out	1st in	2nd out	2nd in	3rd out	3rd in
6	c			c		c		c
5	a		c	ac	ac	ac	ac	ac
4	b	a	ac	bc	ac	bc	ac	bc
3	bc	c	bc	bc	bc	bc	bc	bc
2	a	b	bc	ac	bc	ac	bc	ac
1		a	ac	c	ac	c

为什么反向顺序这么快？

因为当算节点4时，节点5的信息已经有了；算节点3时，节点4的信息已经有了；算节点2时，节点3的信息已经有了。信息一路顺着“活跃性传播方向”往前传，所以不用空等很多轮。

用迭代法解数据流方程时，计算顺序应该尽量沿着信息流动方向。这会更加高效。

活跃性信息沿控制流箭头的反方向传播，并且从 out 传到 in，所以计算也应该按这个方向进行。

10.5. 性能提升

10.5.1. Variants of the Calculation 计算方式的变体

10.5.1.1. Basic blocks 基本块

从以节点为单位到以块为单位构建控制流图，减少计算量。

Basic blocks：如果控制流图中的某些节点只有一个前驱和一个后继，它们本身不太有趣。一串顺序执行的语句，可以合并成一个基本块。 * 可以把这些节点和它们的前驱、后继合并 * 得到一个节点更少的图，其中每个节点表示一个基本块。

10.5.1.2. One variable at a time 一次只分析一个变量

也就是说，不一定每次都维护所有变量的 in/out 集合。可以在需要某个变量信息时，只针对这个变量计算。

很多临时变量的活跃区间很短。

10.5.2. in[n] 和 out[n] 集合表示方式

在实现中，如何表示 in[n] 和 out[n]？

需要支持集合并集、集合差集的操作：

10.5.2.1. Bit Arrays 位数组

假设程序中有 N 个变量，一个机器字有 K 位。那么每个集合用 N 个 bit 表示，如果第 i 个变量在集合里，就把第 i 位设为 1。集合并集可以用按位 OR。

一次集合并操作需要 N/K 次机器字操作

适合 dense set 稠密集合

10.5.2.2. Sorted Lists 排序链表

变量按某个全序 key 排序，例如变量名或编号。并集操作就像归并两个有序链表。

当集合很稀疏时，排序链表更快。

10.6. 复杂度分析

迭代式数据流分析有多快？

假设程序大小为 N，最多 N 个节点，最多 N 个变量

每次集合并操作需要 \(O(N)\)
- in 集合大小小于 N，out 集合大小小于 N，所以一轮合并 \(O(N)\)
for 循环中，每个节点做常数次集合操作，N 个节点，所以一轮 \(O(N^2)\)
repeat 循环每次至少要增大一个 in 集合或者 out 集合，in 集合和 out 集合大小最大为 N，N 个节点最大能增大 \(O(N^2)\) 次。所有 in 和 out 集合大小之和最多是 \(2N^2\)，所以最多执行 \(O(N^2)\) 次。

所以最坏情况：最多执行 \(O(N^2)\) 次，N 个节点的 \(O(N)\) 的归并

\[ O(N^4) \]

但实际中通常是 \(O(N)\) 到 \(O(N^2)\)

尤其是如果计算顺序合理，速度会快很多。

10.7.1. 最小不动点 Least Fixed Points

数据流方程不一定是唯一解的，例如假设还有一个程序变量 d，在这段程序中完全没有使用，那么包含不包含 d 都是可行的解。

数据流方程的任何解都是一种保守近似。如果变量 a 在节点 n 后某次执行中确实需要，那么任何方程解都会把 a 放进 out[n]。

但是反过来不一定成立，a ∈ out[n]，不一定表示 a 的值真的会被使用。

如果编译器认为一个变量是 live，就会确保它的值在寄存器中。

保守近似 conservative approximation 的意思是：

可能错误地认为变量还活着
但不会错误地认为活变量已经死了

可能多用寄存器，但程序结果一定正确

10.7.2. 最小 fixed point 定理

数据流方程可能有多个解。如果 X 是一个解，并且所有其他解都包含 X，那么 X 就叫 least solution/least fixed point/最小解 / 最小不动点

方程 10.3 存在最小不动点，并且前面描述的迭代算法总能计算出这个最小不动点。

10.7.3. Static and Dynamic Liveness

a = b*b --- c = a+b --- c >= b --- return b
                          |
                        return c

注意，根据 chapter 9 的分析，规范的顺序就是 true 跳转的 return b 是 node 5，而 false 分支是 node 4。

Node 1: a = b*b >= 0
Node 2: c = a+b >= b
Node 3: c >= b, always be true
Node 4: return c, will never be reached

从数学上看，条件永远为真，所以节点4永远不会执行。但是数据流方程不知道这个条件一定为真。它只看控制流图上有没有边。方程不知道条件分支实际会走哪条路。

如果方程更聪明，知道节点4不可达，就可能允许 a 和 c 分配到同一个寄存器。

编译器不可能完全理解控制流。没有任何编译器能完全理解所有程序的控制流实际会如何运行。

定理（停机问题是 NP 难解问题）：不存在一个程序 H，可以对任意程序 P 和输入 X 判断 P(X) 会停机还是死循环，并且 H 自己不会死循环。

推论：不存在一个通用程序 H'，可以判断任意程序 P 中的某个标签 L 是否会在执行中到达。如果能判断某个标签会不会到达，就能把“程序结束处”设成标签 L，从而判断程序会不会停机。这与停机问题不可判定矛盾。

10.7.4. 保守近似

这个定理不是说我们永远不能判断某个标签是否可达；而是说不存在一个对所有程序都有效的通用算法。所以：

编译器可以做一些特殊情况优化：
但它不能总是判断变量是否真正会被需要。
因此只能使用：conservative approximation 保守近似
- 具体做法：假设任何条件分支两边都有可能走。

10.7.5. 动态活跃性与静态活跃性定义

动态活跃性 dynamic liveness：变量 a 在节点 n 动态 live，如果程序的某次实际执行会从 n 到达 a 的一次使用，并且中途没有重新定义 a。

重点是：某次真实执行

静态活跃性 static liveness：变量 a 在节点 n 静态 live，如果控制流图中存在一条从 n 到 a 的使用点的路径，并且中途没有重新定义 a。

重点是：控制流图上存在某条路径

如果 a 动态 live，那么 a 一定静态 live。但反过来不一定。因为控制流图上的某条路径可能实际永远不会走。

10.8. Interference Graphs 冲突图 / 干涉图

10.8.1. 冲突

活跃变量分析最重要的应用之一是寄存器分配。

我们有一堆临时变量：

a, b, c, ...

也有有限个寄存器：

r1, ..., rk

如果 a 和 b 不能分配到同一个寄存器，这种限制叫：interference 冲突 / 干涉

两类冲突：

overlapping live ranges：活跃区间重叠。如果两个变量同时 live，它们不能共用一个寄存器。
机器指令限制导致的冲突：如果某个变量 a 必须由一条不能访问 r1 的指令生成，那么 a 和 r1 也冲突。

冲突可以用两种方式表示：

matrix 矩阵：用 x 标记两个变量之间有冲突。

x a b c

a x x

b x

c x
undirected graph 无向图
```
      a
     / \
    b   c
```

10.8.2. MOVE 指令的特殊处理

不要在 MOVE 指令的源和目标之间制造人为冲突。

例子：

t := s   (copy)
...
x := ... s ...   (use of s)
...
y := ... t ...   (use of t)

通常来说，如果 s 和 t 活跃区间重叠，可能会加边：

(s, t)

但这里不应该加。

原因：

t := s

只是复制，s 和 t 保存的是同一个值。理想情况下，可以让 s 和 t 分配到同一个寄存器，这样 MOVE 指令甚至可以删掉。

解决方案：不要为 move 的源和目标添加干涉边

但如果后面有非 move 定义：

t := s       (copy)
t := ...     (non-move)
x := ... s ...
y := ... t ...

这时 t 已经变成新值，而 s 还活着，那么 t 和 s 就真的冲突，需要加边。

10.8.3. 如何添加冲突边

对于任何定义变量 a 的非 move 指令 n，如果 out[n]={b1,...,bj}，就添加边：

(a,b1), ..., (a,bj)

意思是：a 被定义之后，out[n] 中的变量还活着，所以 a 不能和它们共用寄存器。

对于 move 指令：

a := s

如果：

out[n]={b1,...,bk}

则给 a 和每个 bi 加边，但跳过：

bi == s

也就是不添加：

(a,s)

因为希望 a 和 s 可以合并到同一个寄存器，消除 move。

10.8.4. 零长度活跃区间

如果一个新定义的临时变量在定义之后立刻就不 live，怎么办？

可能情况：变量被定义了，但从未使用，似乎不需要给它分配寄存器。

但是只要定义它的指令会执行，它就会写入某个寄存器。这个寄存器不能正好装着另一个 live 变量，否则会把那个变量覆盖掉。因此：零长度活跃区间也会与和它重叠的活跃区间发生冲突。

即使结果不用，只要指令会写寄存器，就不能破坏其他仍然活着的值。

#	use	def	1st in	1st out	2nd in	2nd out	3rd in	3rd out	4th in	4th out	5th in	5th out	6th in	6th out	7th in	7th out
1		a				a		a		ac	c	ac	c	ac	c	ac
2	a	b	a		a	bc	ac	bc	ac	bc	ac	bc	ac	bc	ac	bc
3	bc	c	bc		bc	b	bc	b	bc	b	bc	b	bc	bc	bc	bc
4	b	a	b		b	a	b	a	b	ac	bc	ac	bc	ac	bc	ac
5	a		a	a	a	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac
6	c		c		c		c		c		c		c		c

	use	def	1st out	1st in	2nd out	2nd in	3rd out	3rd in
6	c			c		c		c
5	a		c	ac	ac	ac	ac	ac
4	b	a	ac	bc	ac	bc	ac	bc
3	bc	c	bc	bc	bc	bc	bc	bc
2	a	b	bc	ac	bc	ac	bc	ac
1		a	ac	c	ac	c

#	use	def	1st in	1st out	2nd in	2nd out	3rd in	3rd out	4th in	4th out	5th in	5th out	6th in	6th out	7th in	7th out
1		a				a		a		ac	c	ac	c	ac	c	ac
2	a	b	a		a	bc	ac	bc	ac	bc	ac	bc	ac	bc	ac	bc
3	bc	c	bc		bc	b	bc	b	bc	b	bc	b	bc	bc	bc	bc
4	b	a	b		b	a	b	a	b	ac	bc	ac	bc	ac	bc	ac
5	a		a	a	a	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac	ac
6	c		c		c		c		c		c		c		c

	use	def	1st out	1st in	2nd out	2nd in	3rd out	3rd in
6	c			c		c		c
5	a		c	ac	ac	ac	ac	ac
4	b	a	ac	bc	ac	bc	ac	bc
3	bc	c	bc	bc	bc	bc	bc	bc
2	a	b	bc	ac	bc	ac	bc	ac
1		a	ac	c	ac	c