Liveness Analysis：活跃性分析¶
约 1215 个字 1 张图片 预计阅读时间 4 分钟
这一部分的目标是通过对变量的活跃性分析，确定谁是“in use”的，构建出干扰图，从而便于后续的寄存器分配。
1. 控制流图¶
活跃性分析的第一步是构建控制流图，很简单：
- 每个语句是一个节点
- 每个节点之间的边表示控制流
- 如果 x 节点的下一步可能是 y 节点，则在 x 和 y 之间添加一条边
活跃性分析实际上就是一种数据流分析的实例。这里面有一些术语：
- out-edges：从一个节点出发的边
- in-edges：指向一个节点的边
- pred[n]：节点 n 的前驱节点集合
- succ[n]：节点 n 的后继节点集合
- def
- 对一个变量、临时值的赋值，就定义了这个变量或临时值
- 变量的 def：定义这个变量的节点集合
- 节点的 def：这个节点定义的变量集合
- use：类似。出现在赋值语句右边或其他表达式中的变量或临时值称为使用了这个变量或临时值
- 变量的 use：使用这个变量的节点集合
- 节点的 use：这个节点使用的变量集合
2. 活跃性¶
2.1 定义¶
说一个变量在某条边上是活跃的，如果存在一条从这条边指向 use 这个变量的节点的路径，并且在这条路径上没有对这个变量的 def。
- 这个变量后续会使用
- 这个变量在后续使用之前，没有被重新定义
几个术语：
- Live-in：某个变量在某个节点 live-in，如果这个变量在该节点的所有 in-edges 上都是活跃的。
- Live-out：某个变量在某个节点 live-out，如果这个变量在该节点的所有 out-edges 上都是活跃的。
- in[n]：节点 n 的 live-in 集合
- out[n]：节点 n 的 live-out 集合
2.2 计算¶
推导过程不写了，直接给出公式：
给出一张控制流图，如何去分析活跃性呢？
- 先把每个节点的 use 和 def 都计算好，视作已知变量
- 可以 forward 算：从第一个节点开始，先算 in 再算 out，重复迭代到结果不动为止
- 也可以 backward 算：从最后一个节点开始，先算 out 再算 in，重复迭代到结果不动为止
3. 其他知识¶
3.1 计算过程的其他变种¶
- 基本块化：把只有一个前驱节点且只有一个后继节点的节点合并成一个节点
- 计算活跃性的时候可以一次算一个变量的活跃性而不是节点的活跃性
3.2 集合的表示方法¶
在 in 和 out 集合中常用的操作是求并集和求差集。可以用
- Bit Arrays：集合稠密的时候使用
- Sorted Lists：集合稀疏的时候使用
3.3 时间复杂度¶
对于大小为 N 的程序（最多 N 个节点，N 个变量）：
- 最差时间复杂度是 \(O(N^4)\)
- 实际操作的时候时间复杂度在 \(O(N)\) 到 \(O(N^2)\) 之间
- 需要有合适的计算顺序
3.4 保守估计¶
在活跃性分析中，可能会出现一些保守估计的情况。意思就是说我们可能会选择详细一个变量是活跃的，而实际上这个变量并没有被使用。注意不会发生反过来的情况，即不会漏掉一个变量的活跃性。
4. 干扰图¶
这是为了后续的寄存器分配。如果两个变量互相干扰（说他们之间有 interference），则这两个变量不能被分配到同一个寄存器中。
4.1 定义¶
干扰有两种情形：
- 活跃范围重叠
- 变量 a 必须被一个不能访问 r1 寄存器的指令所生成，则 a 和 r1 互相干扰
干扰图可以用
- 矩阵
- 矩阵 a 行 b 列画叉代表 a 和 b 互相干扰
- 无向图
- 节点代表变量
- 边代表互相干扰
4.2 计算¶
首先需要说明对于 MOVE 指令的特殊处理。
MOVE 指令的特殊处理
MOVE 指令的源和目标变量在做完指令之后就一样了。后续如果只涉及到两者的使用，实际上是可以把它们当成同一个变量来处理的。所以这里不人为为 MOVE 指令的源和目标变量添加干扰边。（如果后续有一个又被 non-move 重新定义了，干扰边自然会被添加上去）
计算方法是：
- 对于任意定义变量 a 的 non-move 节点 n：
- 如果 out[n] 中有变量 b，则 a 和 b 互相干扰
- 对于任意 move 节点 n，例如
a := c：- 如果 out[n] 中有不同于变量 c 的变量 b，则 a 和 b 互相干扰