Data Flow Analysis -- Live variable analysis

17 July 2020 - less than 1 min read time
Tags: program analysis

  《Engineering a Compiler》中的8.6.1章介绍了一种数据流分析算法，Live variable analysis，即活动变量分析，这种技术可以用来检测未初始化变量的使用。编译器或者代码扫描器可以发现并报告这种漏洞。

  举个栗子，当从p到某处使用变量v的位置之间的路径，在这之间变量v没有被重新定义，那么我们就说v在p处是活动的。我们通过计算后，我们将基本块b的变量活动信息存储到 LiveOut(b) 中，该集合包含了从程序块b退出时所有的活动变量。因此，在某个cfg中，我们如果求出entry的 LiveOut(n0) 集合不是空集，则这些变量存在潜在的为初始化调用。

缺个图片儿～ 给个demo图

不动点法求解LiveOut集合

  对于cfg的每个节点n来说，LiveOut(n)是通过一个方程决定的，该方程使用了n节点的所有后继LiveOut集合，以及 UEVar(n) 和 VarKill(n) 集合。定义 LiveOut(n)的方程如下：

\[LiveOut(n) = \mathop{\cup}\limits_{m \in succ(n)}(UEVar(m)\cup(LiveOut(m) \cap \overline{VarKill(m)}))\]

  UEVar(m) 包含了m中向上展示的变量，即在m中没有重新定义就使用的变量，这种关系在LLVM中一般对应一种use关系。而 VarKill(m) 则代表了在m中被重新定义的变量，重新定义即代表原值的生命周期结束，所以被kill掉。上述方程上划线代表了 VarKill(m) 的逻辑补集，这里的m则是n的某后继节点。

  究竟怎么样才算变量存活嘞？对于一个基本程序块m来说，一般只有两种情况，某变量v：

  1. 在m中，对v重新定义之前就使用了v，这种情况就是
\[v \in UEVar(m)\]
  1. v在退出程序块m时仍然是存活的，就是v”毫发无损”的穿过了m，因为m中没有对v进行重新定义，在m后的block有对v的use，所以这种情况就是：
\[v \in LiveOut(m) \cap \overline {VarKill(m)}\]

于是乎，把这俩集合并起来就是m对对 LiveOut(n) 的贡献，然后把所有n的后继m的结果并起来就是整个 LiveOut(n) 的正确结果。

  关于这部分内容，在李樾老师的《软件分析》第4课中有所介绍，但是迭代方式稍有不同，他给出了另一个公式：

\[LiveOut(n) = \mathop{\cup}\limits_{m \in succ(n)}(UEVar(m)\cup(LiveOut(m) - VarKill(m))\]

缺个图片儿～ 给出这两种情况展示图

  事实上这两个公式是一个意思，这个方程描述了一个反向数据流问题.

反向数据流问题： 信息沿着图的边的反向流动。

  那么为啥这里要取所有后继节点m的运算结果的并集嘞？因为后继的任何一个Basic Block用到了某变量v都会产生一个use关系，因此都有可能引发变量的未初始化调用。所以这个数据流分析应该属于 May Analysis, 故应当使用并集运算，而 Must Analysis 通常使用交集的运算。

迭代法求不动点

  数据流分析我们通常使用迭代法来reach fixed point。对于一个过程，我们可以使用如下三步来实现算法：

  1. 构建CFG
  2. 收集初始信息 – 通过一个pass来初始化 UEVar 和 VarKill
  3. 求不动方程 – 通过多趟pass来迭代，计算LiveOut集合，最后达到不动点。

具体实现的伪代码如下：

# assume block b has k operations
# of form "x = y op z"

# Collect initial info
def Init(b):
    b.UEVar = null
    b.VarKill = null
    for i in range(k):
        b[i].VarKill.append(x)
        if y not in b.VarKill:
            b[i].UEVar.append(y)
        if z not in b.varKill:
            b[i].UEVar.append(z)

# init every block
for i in block:
    Init(b)


# assume CFG has N blocks
# numbered 0 to N - 1

def GetLiveOutPass(cfg):
    for i in range(N):
        cfg[i].LiveOut = null

    changed = true
    while(changed):
        changed = false
        for i in range(N):
            cfg[i].LiveOut = cfg[i].LiveOut.recompute()
            if (cfg[i].LiveOut.changed):
                changed = true
阅读量