活跃度分析¶

约 1046 个字 25 行代码预计阅读时间 6 分钟

从 IR 到具体汇编语言之间存在一个很大的鸿沟：IR 表示中我们总是假设有无限多的虚拟寄存器，而真实机器中寄存器数量是有限的。将 IR 中的虚拟寄存器映射到有限物理寄存器的过程，称为寄存器分配（Register Allocation）。

在讨论寄存器分配之前，首先要理解其前置问题——活跃性分析（Liveness Analysis）：

如果一个寄存器的值在将来还会被用到，那么从当前点到那次使用之间，该寄存器就是活跃的，不能将其他值覆盖到它上面。

实际上,如果要回答一个变量x在语句n后会不会被使用,我们可以把这个拆分为两个问题:

n后有哪些语句会被执行?

控制流分析
这些语句中哪些会使用到x?

活跃性分析很自然的,是一个backward的过程,我们从程序的最后一行开始分析,逐行往前分析每个变量的活跃性.

控制流分析¶

Control Flow Graph (CFG)

控制流图(Control Flow Graph, CFG) 是一个有向图,用于描述程序执行时可能经过的控制路径.

在活跃度分析中,我们通常把 CFG 建在语句或汇编指令的粒度上:

node: 一条语句或一条指令.
edge: 控制流关系.如果语句 m 执行后可能紧接着执行语句 n,则有一条边:

\[ m \to n \]

构造 CFG 时,给定一段按顺序排列的语句,可以按下面规则添加边:

对普通语句 s_i,如果下一条语句是 s_{i+1},则加入边 \(s_i \to s_{i+1}\).
对无条件跳转 goto L,只加入从当前语句到标签 L 对应语句的边.
对条件跳转 if cond goto L,需要加入两类边:
- 条件为真时跳到 L;
- 条件为假时继续执行下一条语句.
对 return 这样的函数出口语句,通常没有后继节点.

例如,考虑如下带循环的伪代码:

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

其中第 5 条语句是条件跳转:

如果 a < N 为真,控制流回到第 2 条语句;
如果 a < N 为假,控制流继续到第 6 条语句.

对应的控制流图为:

flowchart TD
    s1["1: a <- 0"] --> s2["2: b <- a + 1"]
    s2 --> s3["3: c <- c + b"]
    s3 --> s4["4: a <- b * 2"]
    s4 --> s5{"5: a < N ?"}
    s5 -- true --> s2
    s5 -- false --> s6["6: return c"]

当我们说某个变量是否活跃时,我们说它在CFG的某条边上是否活跃,比如,对于变量b,它在\(2 \to 3,3 \to 4\)这两条边上是活跃的,因为在第3个节点和第4个节点的语句右边都使用了b.

实际上,我们可以从这个简单的例子中看出活跃的一些性质:

如果3号节点变成c <- c + 1,那么变量b在\(2 \to 3\)这条边上依然活跃,因为后面第4号节点的语句a <- b * 2依然使用了b.
如果3号节点变成b <- c + 1,那么变量b在\(2 \to 3\)这条边上不再活跃了,因为出现了重新定义

在对每个变量完成了活跃性分析后,如果我们发现两个变量的活跃区间完全不重叠,那么它们就可以分配到同一个物理寄存器上,因为它们不会在同一时间被使用.

Solution of Dataflow Equations¶

在这一部分,我们介绍如何通过具体的算法来求解活跃性分析中的数据流方程.

流图术语（Flow Graph Terminology）

对 CFG 中的节点 \(n\)：

out-edge（出边）: 从 \(n\) 指向其后继节点的边。
in-edge（入边）: 从某前驱节点指向 \(n\) 的边。
succ[n]: 节点 \(n\) 的所有后继节点集合。
pred[n]: 节点 \(n\) 的所有前驱节点集合。

use 与 def

对每条语句（或指令），定义两个基本集合：

def[n]: 在节点 \(n\) 中被赋值（即出现在赋值语句左侧）的所有变量/临时变量的集合。

对变量或临时变量的赋值，称该变量在 \(n\) 中被定义（define）。
use[n]: 在节点 \(n\) 中出现在赋值右侧（或其他表达式）被读取的所有变量/临时变量的集合。

变量出现在赋值右侧或其他表达式中，称该变量在 \(n\) 中被使用（use）。

反过来，给定一个变量 \(a\)，也可以按变量视角来组织：

def(a): 所有定义了变量 \(a\) 的 CFG 节点集合——即 \(a\) 出现在赋值语句左侧的所有节点。
use(a): 所有使用了变量 \(a\) 的 CFG 节点集合——即 \(a\) 出现在赋值右侧或其他表达式中的所有节点。

现在,我们可以用确定性的语言来描述一个变量在某条边上是否活跃了:

变量在边 \(m \to n\) 上是活跃的，当且仅当从节点 \(n\) 出发存在一条有向路径，到达该变量的一次使用，且路径上不经过该变量的任何定义点。等价于两个条件同时满足：

该变量在将来会被使用；
该变量在被使用之前不会被重新定义。

活跃性、live-in 与 live-out

live-in：变量在节点 \(n\) 的入口是活跃的，当且仅当它在 \(n\) 的任意一条入边上活跃。

live-out：变量在节点 \(n\) 的出口是活跃的，当且仅当它在 \(n\) 的任意一条出边上活跃。

记法：

in[n]: 节点 \(n\) 的 live-in 集合——在 \(n\) 入口处活跃的所有变量。
out[n]: 节点 \(n\) 的 live-out 集合——在 \(n\) 出口处活跃的所有变量。

在有了以上所有概念后,我们就可以定义具体的算法了.

活跃度分析的数据流方程

活跃度分析本质上是在 CFG 上反复传播变量集合.对每个节点 \(n\),我们需要求两个集合:

\(in[n]\): 进入节点 \(n\) 之前活跃的变量集合.
\(out[n]\): 离开节点 \(n\) 之后活跃的变量集合.

这些集合满足下面三条规则:

如果变量 \(a \in in[m]\),并且 \(m \in succ[n]\),那么 \(a \in out[n]\).

也就是说,只要 \(n\) 的某个后继节点入口需要变量 \(a\),那么 \(a\) 在 \(n\) 的出口就必须是活跃的.
如果变量 \(a \in use[n]\),那么 \(a \in in[n]\).

因为节点 \(n\) 自己要读取变量 \(a\),所以 \(a\) 在进入 \(n\) 之前必须已经可用.
如果变量 \(a \in out[n]\) 且 \(a \notin def[n]\),那么 \(a \in in[n]\).

如果变量 \(a\) 在离开 \(n\) 后还要被使用,并且 \(n\) 没有重新定义 \(a\),那么进入 \(n\) 前的旧值仍然需要保留,所以 \(a\) 在 \(n\) 的入口也是活跃的.

因此可以得到活跃度分析的数据流方程:

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

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

这里 \(out[n]\) 由后继节点的 \(in\) 集合决定,所以活跃度分析是一个 backward dataflow analysis.

保守近似（Conservative Approximation）

数据流方程的解是保守近似的。如果变量 \(a\) 在节点 \(n\) 之后的某次执行中确实会被用到，那么在任何方程的解中都可以保证 \(a \in out[n]\)（不会漏报）。但反过来不成立：\(a \in out[n]\) 并不意味着 \(a\) 的值真的会在后续执行中被使用——它可能存在于解中但实际永远不会被用到（可能误报）。

活跃性分析的保守性方向是"宁可多报不可漏报"：漏报会导致寄存器被过早覆盖而丢失数据，多报只是浪费一个寄存器，不影响正确性。

迭代求解过程

因为 \(out[n]\) 依赖后继节点的 \(in\) 集合,所以实现时通常按反向顺序遍历节点.这样不能改变最终结果,但通常可以减少迭代次数.

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

repeat
    for each node n
        oldIn[n]  <- in[n]
        oldOut[n] <- out[n]

        out[n] <- U_{s in succ[n]} in[s]
        in[n]  <- use[n] U (out[n] - def[n])

until oldIn[n] = in[n] and oldOut[n] = out[n] for all nodes n

这个算法一定会收敛,因为:

每个 \(in[n]\) 和 \(out[n]\) 都只是变量全集的子集;
每次迭代只会向集合中加入变量,不会无限产生新变量;
当所有集合都不再变化时,就达到了数据流方程的一个不动点(fixed point).

迭代求解示例

继续使用前面的循环例子.为了让信息更快从出口传播回入口,每一轮都按节点编号的反向顺序计算:

\[ 6 \to 5 \to 4 \to 3 \to 2 \to 1 \]

计算时先根据后继节点的 \(in\) 集合更新 \(out[n]\),再根据 \(out[n]\) 更新 \(in[n]\):

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

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

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

flowchart TD
    s1["1: a <- 0"] --> s2["2: b <- a + 1"]
    s2 --> s3["3: c <- c + b"]
    s3 --> s4["4: a <- b * 2"]
    s4 --> s5{"5: a < N ?"}
    s5 -- true --> s2
    s5 -- false --> s6["6: return c"]

use / def第 1 轮第 2 轮第 3 轮

节点	use[n]	def[n]	succ[n]
6	\(\{c\}\)	\(\varnothing\)	\(\varnothing\)
5	\(\{a\}\)	\(\varnothing\)	\(\{2, 6\}\)
4	\(\{b\}\)	\(\{a\}\)	\(\{5\}\)
3	\(\{b, c\}\)	\(\{c\}\)	\(\{4\}\)
2	\(\{a\}\)	\(\{b\}\)	\(\{3\}\)
1	\(\varnothing\)	\(\{a\}\)	\(\{2\}\)

初始时所有 \(in[n]\) 与 \(out[n]\) 都是空集.按 \(6 \to 1\) 反向更新后:

节点	out[n]	in[n]
6	\(\varnothing\)	\(\{c\}\)
5	\(\{c\}\)	\(\{a, c\}\)
4	\(\{a, c\}\)	\(\{b, c\}\)
3	\(\{b, c\}\)	\(\{b, c\}\)
2	\(\{b, c\}\)	\(\{a, c\}\)
1	\(\{a, c\}\)	\(\{c\}\)

第 2 轮中,第 5 个节点的后继包含节点 2.由于上一轮已经得到 \(in[2] = \{a, c\}\),所以:

\[ out[5] = in[2] \cup in[6] = \{a, c\} \]

更新后得到:

节点	out[n]	in[n]
6	\(\varnothing\)	\(\{c\}\)
5	\(\{a, c\}\)	\(\{a, c\}\)
4	\(\{a, c\}\)	\(\{b, c\}\)
3	\(\{b, c\}\)	\(\{b, c\}\)
2	\(\{b, c\}\)	\(\{a, c\}\)
1	\(\{a, c\}\)	\(\{c\}\)

第 3 轮再次更新后,所有 \(in[n]\) 与 \(out[n]\) 都不再变化,因此算法收敛:

节点	out[n]	in[n]
6	\(\varnothing\)	\(\{c\}\)
5	\(\{a, c\}\)	\(\{a, c\}\)
4	\(\{a, c\}\)	\(\{b, c\}\)
3	\(\{b, c\}\)	\(\{b, c\}\)
2	\(\{b, c\}\)	\(\{a, c\}\)
1	\(\{a, c\}\)	\(\{c\}\)

Representation of Sets¶

实现中 \(in[n]\) 和 \(out[n]\) 有两种表示方式：

位数组（Bit Arrays）——适用于稠密集：

假设程序共有 \(N\) 个变量，每个机器字 \(K\) 位，则每个集合需要 \(N\) 位。
集合并操作：对每个位置按位 or。
一次并操作需要 \(N/K\) 次机器指令。

有序链表（Sorted Lists）——适用于稀疏集：

按全序键值（如变量名）排序。
并操作：归并两个有序链表。
当集合较稀疏（平均元素数 \(\ll N/K\)）时，有序链表比位数组更快。

迭代分析的时间复杂度¶

程序规模为 \(N\)：最多 \(N\) 个节点、\(N\) 个变量。
每次集合并操作 \(O(N)\)，每轮迭代每个节点做常数次集合操作，共 \(O(N)\) 个节点 → 每轮 \(O(N^2)\)。
\(in\) 和 \(out\) 集合是单调增长的，所有集合大小之和上界为 \(2N^2\)，这是最坏迭代轮数的上界。
最坏情况：\(O(N^4)\)。
实际情况:通常在 \(O(N)\) 到 \(O(N^2)\) 之间，取决于遍历顺序。

活跃度分析¶

控制流分析¶

Solution of Dataflow Equations¶

Representation of Sets¶

迭代分析的时间复杂度¶

评论