9 Liveness Analysis¶
活跃变量分析是一种后向数据流分析，确定每个变量在程序各点是否"活跃"——即当前值是否会在未来被使用。
- def：变量被赋值的位置（如
a = 1）。 - use：变量被读取的位置（如
b = a + 1）。 - live：变量
v在程序点p活跃，当且仅当存在一条从p出发的路径，在路径上v被使用前未被重新定义。 - interference：两个变量在程序某点同时活跃，则它们干涉——不能共享同一寄存器。
为什么是后向分析
活跃性是"从未来看现在"——一个变量在点 p 是否活跃，取决于它之后是否被用到。因此信息沿控制流的反方向传播。
整个过程：建图 → 设方程 → 求解。
9.1 Build CFG¶
基本块 (Basic Block) 是满足单一入口、单一出口的最大指令序列。划分时先找出所有首指令（程序首条、跳转目标、跳转指令的下一条），每个首指令到下一个首指令之前构成一个基本块。
Note
实际分析时常将单条语句视为一个基本块，使每个 def/use 精确对应到一个节点，干涉分析更准确。
CFG 的节点为每个基本块（或语句），边表示控制流走向（顺序边和跳转边）。为每个节点 \(n\) 记录前驱 pred[n] 和后继 succ[n]。
Example
CFG 示例 (以语句为节点): (1) a = 0 (2) b = a + 1 (3) c = c + b ← 循环头 (4) a = b * 2 (5) if a < N goto (3)
pred[3] = {2, 5} succ[3] = {4}
pred[5] = {4} succ[5] = {3, exit}
9.2 Dataflow Equations¶
活跃分析是后向 (Backward) 分析。为每个节点 \(n\) 定义四个集合：
| 集合 | 含义 |
|---|---|
| \(\text{in}[n]\) | \(n\) 执行前活跃的变量 |
| \(\text{out}[n]\) | \(n\) 执行后活跃的变量 |
| \(\text{use}[n]\) | \(n\) 中被读取的变量（先读后写也算，如 a = a+b 中 a, b 都属于 use） |
| \(\text{def}[n]\) | \(n\) 中被写入的变量 |
核心方程：
\[\text{in}[n] = \text{use}[n] \cup (\text{out}[n] - \text{def}[n])\]
\[\text{out}[n] = \bigcup_{s \in \text{succ}[n]} \text{in}[s]\]
- in 方程：进入时活跃的 = 本节点要用的 + 离开后仍然活跃且没被本节点重新定义的。
- out 方程：离开时活跃的 = 所有后继入口活跃变量的并集（变量只要在某一条后继路径上活跃，出口就是活跃的）。
9.3 Solving (Fixed-Point Iteration)¶
数据流方程递归定义，通过不动点迭代求解：
- 初始化：所有 \(\text{in}[n] = \text{out}[n] = \varnothing\)。
- 迭代：按逆后序（从出口往入口方向）反复更新每个节点，直到全部集合不再变化。
- 终止：活跃变量集合单调递增而变量总数有限，必然在有限步内收敛。
repeat:
for each node n in reverse CFG order:
out[n] = ∪ in[s] for s ∈ succ[n]
in[n] = use[n] ∪ (out[n] - def[n])
until no change
复杂度
最坏 \(O(N \cdot V)\)（\(N\) 个节点，\(V\) 个变量）。但实际中通常 2~3 轮即收敛。
9.4 Example¶
下面完整演示一个程序的活跃分析过程。
程序：计算 1 到 N 的平方和。
a = 0; // (1)
b = 1; // (2)
c = 1; // (3)
a = a + c; // (4) ← 循环开始
c = c + 1; // (5)
b = b + c; // (6)
if (c <= N) // (7)
goto (4); // (8)
return a; // (9)
CFG（每条语句一个节点）：
| 节点 | pred | succ |
|---|---|---|
| (1) | — | (2) |
| (2) | (1) | (3) |
| (3) | (2) | (4) |
| (4) | (3), (8) | (5) |
| (5) | (4) | (6) |
| (6) | (5) | (7) |
| (7) | (6) | (8), (9) |
| (8) | (7) | (4) |
| (9) | (7) | — |
use/def：
| 节点 | 语句 | use | def |
|---|---|---|---|
| (1) | a = 0 |
\(\varnothing\) | {a} |
| (2) | b = 1 |
\(\varnothing\) | {b} |
| (3) | c = 1 |
\(\varnothing\) | {c} |
| (4) | a = a + c |
{a, c} |
{a} |
| (5) | c = c + 1 |
{c} |
{c} |
| (6) | b = b + c |
{b, c} |
{b} |
| (7) | if (c <= N) |
{c, N} |
\(\varnothing\) |
| (8) | goto (4) |
\(\varnothing\) | \(\varnothing\) |
| (9) | return a |
{a} |
\(\varnothing\) |
迭代求解（初始所有 in/out 为空，逆序从 (9) 向 (1) 计算）：
Round 1：
| n | out 计算 | in 计算 | out | in |
|---|---|---|---|---|
| (9) | 无后继 | {a} ∪ ({}−{}) |
{} | {a} |
| (8) | in[4]={} | {} ∪ ({}−{}) | {} | {} |
| (7) | in[8]∪in[9]={a} | {c,N} ∪ ({a}−{}) |
{a} |
{a,c,N} |
| (6) | in[7]={a,c,N} | {b,c} ∪ ({a,c,N}−{b}) |
{a,c,N} |
{a,b,c,N} |
| (5) | in[6]={a,b,c,N} | {c} ∪ ({a,b,c,N}−{c}) |
{a,b,c,N} |
{a,b,c,N} |
| (4) | in[5]={a,b,c,N} | {a,c} ∪ ({a,b,c,N}−{a}) |
{a,b,c,N} |
{a,b,c,N} |
| (3) | in[4]={a,b,c,N} | {} ∪ ({a,b,c,N}−{c}) | {a,b,c,N} |
{a,b,N} |
| (2) | in[3]={a,b,N} | {} ∪ ({a,b,N}−{b}) | {a,b,N} |
{a,N} |
| (1) | in[2]={a,N} | {} ∪ ({a,N}−{a}) | {a,N} |
{N} |
Round 2：
| n | out | in | 变化？ |
|---|---|---|---|
| (9) | {} | {a} |
无 |
| (8) | in[4]={a,b,c,N} | {a,b,c,N} |
变 |
| (7) | in[8]∪in[9]={a,b,c,N} | {a,b,c,N} |
变 |
| (6)~(1) | 与 R1 相同 | 与 R1 相同 | 无 |
Round 3：全部无变化 → 终止。
不动点结果：
| 节点 | out | in |
|---|---|---|
| (1) a=0 | {a,N} | {N} |
| (2) b=1 | {a,b,N} | {a,N} |
| (3) c=1 | {a,b,c,N} | {a,b,N} |
| (4) a=a+c | {a,b,c,N} | {a,b,c,N} |
| (5) c=c+1 | {a,b,c,N} | {a,b,c,N} |
| (6) b=b+c | {a,b,c,N} | {a,b,c,N} |
| (7) if c≤N | {a,b,c,N} | {a,b,c,N} |
| (8) goto(4) | {a,b,c,N} | {a,b,c,N} |
| (9) return a | {} | {a} |
评论区
对你有帮助的话请给我个赞和 star =>
欢迎跟我探讨！！！