活跃变量分析

excerpt

应用

考虑下面的三地址码，假设目标架构中，只存在一个寄存器 r ，是否可以将所有三个变量 a、b 和 c 放在寄存器 r 中？

a = 1;
b = a + 2;
c = b + 3;
return c;

活跃变量分析的一个应用：寄存器分配。

活跃变量分析的另一个应用：死代码删除。

活跃变量分析

数据流分析 —— 控制流图 CFG

此处所指的控制流图中，节点是一个 statement（例如条件跳转语句中的比较部分、赋值语句、…）。边是控制流。

例如，下图展示了一个代码片段（左）与其对应的控制流图（右）：

src:https://rainoftime.github.io/teaching/index.html

变量的「活跃性」/「Liveness」

称变量 x 在语句 s 中是具有活跃性的，当下面的命题全部成立时：

• 存在使用变量 x 的语句 s'
• 有一条从 s 到 s' 的路径，并且该路径中没有对 x 的赋值/定义

依赖于 CFG 的一些术语

$\text{pred}()$

$\text{pred}(n):=$ 一个节点 $n$ 的全体前驱节点。节点 $n$ 的前驱节点指的是，有一条指向 $n$ 的出边的节点。

例如，在上面的控制流图中：

$\text{pred}(2) = \{1\}$

$\text{pred}(3) = \{2, 5\}$

$\text{succ}()$

$\text{succ}(n) :=$ 一个节点 $n$ 的全体后继节点。节点 $n$ 的后继节点指的是，被 $n$ 的出边所指向的节点。

例如，在上面的控制流图中：

$\text{succ}(2) = \{3\}$

$\text{succ}(3) = \{4, 6\}$

$\text{def}()$

$\text{def}(x) :=$ 包含对变量 $x$ 的定义（出现在赋值语句左侧）的全体节点。

$\text{def}(n) :=$ 节点 $n$ 中定义（出现在赋值语句左侧）的全体变量。

例如，在上面的控制流图中：

$\text{def}(x) = \{1, 5\}$

$\text{def}(1) = \{x\}$

$\text{use}()$

$\text{use}(x) :=$ 包含变量 $x$ 出现在表达式右侧的语句的全体节点。

$\text{use}(n) :=$ 节点 $n$ 中出现在表达式右侧的全体变量。

例如，在上面的控制流图中：

$\text{use}(a) = \{1, 2, 3, 4, 5\}$

$\text{use}(1) = \{a, b\}$

可判定性

考虑下面的代码片段，判定变量 x 在第一行语句处的活跃性：

x = 10;     // is x live here?
f(); 
return x;

如果函数 f() 在调用后永远不会返回，那么变量 x 在第一行语句处实际上是不活跃的：因为此时最后的 return x 不可能被执行，变量 x 的值永远不会被再次使用。

实际上这个构造将「变量的活跃性判定问题」归约到「停机问题」，从而证明了将「变量的活跃性判定问题」是不可判定的。

因此，在理论上不存在一个能够对所有可能输入在有限时间内给出正确答案的算法。我们使用下面将介绍的一种保守的近似算法判定变量 x 在语句 s 处的活跃性。所谓保守的近似算法，是指如果这个算法判定变量 x1 在语句 s1 处是活跃的，则变量 x1 在语句 s1 处可能活跃但也可能不活跃；而如果这个算法判定变量 x2 在语句 s2 处是不活跃的，则变量 x2 在语句 s2 处一定不活跃。

一种保守的近似算法

这种近似算法扩大了变量活跃性的范畴，通过讨论下面定义的 $\text{live-in}(n)$ 和 $\text{live-out}(n)$ 来分析有哪些变量在节点 $n$ 所对应的语句 $s$ 处是活跃的：

$\text{live-in}()$

称变量 x 在边 E 上是活跃的，当下面的命题全部成立时：

• $x \in \text{use}(s')$，即，变量 x 将出现在语句 s' 的表达式右侧
• 有一条经过 E，到 s' 的路径，并且该路径中的所有节点的 $\text{def}()$ 均不包括 $x$

如果一个变量 $x$ 在某个节点 $n$ 的任何一个入边上是活跃的，那么该变量 $x \in \text{live-in}(n)$。

简写为 $\text{in}()$。

$\text{live-out}()$

如果一个变量 $x$ 在某个节点 $n$ 的任何一个出边上是活跃的，那么该变量 $x \in \text{live-out}(n)$。

简写为 $\text{out}()$。

算法

遵循对变量活跃性的定义，以及自下而上的分析方法，这个算法给出了对于 CFG 上的某一节点 $n$，计算 $\text{in}(n)$ 和 $\text{out}(n)$ 的三个法则：

RULE 1：如果变量 $x \in \text{in}(n)$，对于 $\forall m \in \text{pred}(n)$，都有 $x \in \text{out}(m)$。

假设 $\text{pred}(n) = \{m_1, m_2, \dots, m_k\}$，根据出边和入边的定义，必定存在 $1 \leq i \leq k$ 使得 $x \in \text{out}(m_i)$，对于其他的节点 $m_\_$，根据根据边上的变量活跃性的定义，符合条件的路径是 $m_\_ \sim n$ 与 $m_i \sim s'$ 的后半段 $n \sim s'$ 的组合。此处的规则将这里的存在认为是任意（即对每一个前驱节点都成立），这是过度近似。

RULE 2：如果变量 $x \in \text{use}(n)$，那么 $x \in \text{in}(n)$。

符合条件的路径是以节点 $n$ 为终点的所有包含 $n$ 的入边的路径。

RULE 3：如果变量 $x \in \text{out}(n)$，并且 $x \notin \text{def}(n)$，那么 $x \in \text{in}(n)$。

使得 $x \in \text{out}(n)$ 成立的符合条件的路径，可以穿越节点 $n$，增加节点 $n$ 的入边作为其延伸段，因为节点 $n$ 没有修改变量 $x$ 的值。

根据以上的 RULE 1, 2, 3，通过以下互递归公式，可以计算所有节点的 $\text{in}()$ 和 $\text{out}()$：

$$\begin{array}[rl] \displaystyle \text{in}(n) &= \displaystyle \text{use}(n) \cup (\text{out}(n) - \text{def}(n)) \\ \displaystyle \text{out}(n) &= \displaystyle \bigcup_{s \in \text{succ(n)}} \text{in}(s) \end{array} $$

这个互递归公式一定是收敛的，由于单调有界定理：$|\text{in}(n)|$ 和 $|\text{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] \cup (out[n] − def[n])
        out[n] <- \bigcup_{s in succ[n]} s
until in′[n] == in[n] and out′[n] == out[n] for all n

改进

对节点的分析遵从控制流的倒序，遵循自下而上、从出到入的分析方法。这将有效减少迭代次数。

复杂度分析

对于一个大小为 $N$ 的程序（即，程序中至多包含 $N$ 个节点 $N$ 个变量）：

• 每个对集合的并操作需要 $\mathcal{O}(N)$ 时间。
• 对于内层的 for 循环：对每个节点所需要的并操作是常数个，因此循环总共需要 $\mathcal{O}(N^2)$ 时间。
• 对于外层的 repeat ... until ... 循环：所有 $\text{in}()$ 与所有 $\text{out}()$ 集合的大小之和为 $\mathcal{O}(2N^2)$，这是 repeat ... until ... 循环所能迭代的最高次数。

时间复杂度相乘，整个算法的最坏时间复杂度为 $\mathcal{O}(N^4)$。

如果选择合适的运算顺序，算法的实际运行时间介于 $\mathcal{O}(N)$ 与 $\mathcal{O}(N^2)$。

最小不动点

方程组

$$\begin{array}[rl] \displaystyle \text{in}(n) &= \displaystyle \text{use}(n) \cup (\text{out}(n) - \text{def}(n)) \\ \displaystyle \text{out}(n) &= \displaystyle \bigcup_{s \in \text{succ(n)}} \text{in}(s) \end{array} $$

拥有不止一个解，但是上面的算法能够计算出所有解中规模最小的一个解。并且这个解是所有解的交集，称为最小不动点。

证明留作课后习题：

src: Tiger p.225, p.233

静态活跃性与动态活跃性

静态活跃性（Static liveness）：如果一个变量 a 从某个节点 n 开始，存在一条控制流路径到达某个使用变量 a 的地方，且这条路径上没有对 a 的定义，认为在节点 n 处，变量 a 是静态活跃的。

动态活跃性（Dynamic liveness）：如果 在某次程序执行中，一个变量 a 从某个节点 n 开始，到达某个使用变量 a 的地方，且这条路径上没有对 a 的定义，认为在节点 n 处，变量 a 是静态活跃的。

动态活跃集合是静态活跃集合的子集，如果一个变量 a 在节点 n 是动态活跃的，那么它在这个节点一定是静态活跃的。
静态活跃性是一种保守的近似估计，它认为所有分支都会被执行。上面的算法是一种静态活跃性分析，这体现在RULE 1中。