南大软分实验笔记｜A1 存活变量分析与迭代求解器

前言

在学完前四节课后，我们迎来第一个实验作业——存活变量分析与迭代求解器。其中存活变量分析在《南大软件分析课程笔记｜04 数据流分析应用》中有讲解，迭代求解器则在第三、四节课中都有涉及，因此还可以参考《南大软件分析课程笔记｜03 数据流分析应用》。

课程提供了完整的实验环境配置说明（IntelliJ IDEA + Java 17）、实验手册和相关源码，见官方网站。拥有教育邮箱的同学还可以在官方OJ平台注册账号，提交自己的作业源代码，使用平台提供的大量测试用例测试你的程序正确与否，获得失败反馈，从而加以改进。

在完成第一个实验之后，个人感觉本课的实验设计十分到位；从搭建实验环境、完成代码、提交OJ、根据反馈改进代码，到最终提交OJ并通过所有测试，整个流程十分流畅。下面是我的OJ提交记录：

我也确实在短时间内学到很多——这正是实战项目的独特优势。所谓纸上得来终觉浅，绝知此事要躬行，正是如此。看过课程视频、写过课程笔记之后，我们也许会对数学语言和伪代码描述的定义与思路了然于胸，然而只有通过编程实践，我们才能将知识转化为技能，联系理论和实际，最终学以致用。

课程作业主页“概述”部分的末尾引用了宋代诗人陆九渊的一句：读书切戒在慌忙，涵泳工夫兴味长。确实如此——一搭建好环境准备上手的时候，我读了几遍实验描述和已有的框架代码，似乎知所云但并不能着手把之前学到的理论在已有框架的基础上实现。这个时候，我是有些“慌忙”的。现在从事后的角度，我尝试总结一下刚开始手足无措的原因：

1. 不清楚理论在实际中如何映射。举个例子，课上李樾老师用了位向量来代表data flow facts，但是实验框架看起来使用的是集合。当然了，从编程的角度来说，位向量向集合转化是一件十分容易的事情——只需要将向量中置1的位置对应的facts加入集合即可。然而，最开始我的茫然在于，不清楚这个实验框架希望我用位向量还是集合去实现，至少一开始我是以为要往集合里面塞一堆0和1的。理论中使用的抽象描述在实际编程中会有多种实现（数据结构），一开始可能不清楚具体应该使用哪种实现。
2. 不清楚我的代码将被如何使用。这个问题是在子任务一“存活变量分析”上遇到的。看到要求实现的API，但是并不知道这些API是如何被调用的，那么这些API是有状态的还是无状态的，它们的return value、side effect将被如何使用？事实上，读了子任务二“迭代求解器”部分的已有源码后，我们就能够知道子任务一中的API将如何被调用了。

如何解决以上问题呢？多读实验材料、已有源码，多尝试。哪怕一开始出错，没关系，根据反馈慢慢就摸出道道了。读书切戒在慌忙，涵泳工夫兴味长。诚不我欺。

在初步弄清楚调用关系和Tai-e框架的设计的基础上，整体而言，作为第一个实验，这个作业的难度是不高的，代码量也不大，只需要将API实现补充完整即可。然而，即使本地测试通过，OJ平台的大量用例也很可能帮助我们发现代码中考虑不周的地方。例如，一开始我没有在transfer function中判断$def_{B}$和$use_{B}$元素的类型——理论层面上，我们当然只会去考虑data flow facts；然而在编程层面上，你需要滤去其他非data flow facts类型的元素。

在这个长前言的最后，感谢李樾、谭添老师和其他为此课程付出努力的老师和同学。

任务一：实现存活变量分析

如需完整的实验说明，请参考官方文档，考虑到篇幅，本文仅对实验内容做简单介绍，重点在于解决思路和实现。

在IntelliJ IDEA点击左下方的“TODO”标签可以很方便地看到所有我们需要填充的函数体。存活变量分析部分，任务是LiveVariableAnalysis类的4个方法：

1. SetFact newBoundaryFact(CFG)
2. SetFact newInitialFact()
3. void meetInto(SetFact, SetFact)
4. boolean transferNode(Stmt, SetFact, SetFact)

这4个方法分别对应存活变量分析算法中的边界初始化、非边界基本块初始化、control flow handling和transfer function。在任务二中，这些方法将被我们的迭代求解器调用。其中，前三个方法是非常简单的，无需过多讲解，如下所示：

public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {
    return new SetFact<>();
}
public SetFact<Var> newInitialFact() {
    return new SetFact<>();
}
public void meetInto(SetFact<Var> fact, SetFact<Var> target) {
    target.union(fact);
}

Transfer function稍微复杂一些，但基本还是按照上一节讲解的算法展开的，只不过在处理变量定义和变量使用时需要将非变量的成分过滤掉（instanceof）：

public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {
    SetFact<Var> inTmp = new SetFact<>();
    inTmp.union(out);
    if (stmt.getDef().isPresent()) {
        if (stmt.getDef().get() instanceof Var) {
            inTmp.remove((Var)(stmt.getDef().get()));
        }
    }
    for (RValue rValue: stmt.getUses()) {
        if (rValue instanceof Var) {
            inTmp.add((Var)rValue);
        }
    }
    if (in.equals(inTmp)) {
        return false;
    } else {
        in.set(inTmp);
        return true;
    }
}

我在OJ上第一次未通过的原因是从右值获取变量使用的逻辑有些问题，也没有判断类型是否为Var。OJ平台虽然没有给出具体的失败原因，但是给出了未通过的测试用例，我们可以把它保存到本地，手动运行测试查找原因。我第一次未通过的测试用例如下所示：

/* AnonInner.java */
interface Adder {
    int add(int j);
}
class AnonInner {
    static Adder makeAdder(final int i) {
        return new Adder() {
            @Override
            public int add(int j) {
                return i + j;
            }
        };
    }
    static void show() {
        System.out.println(makeAdder(2).add(5));
    }
}

结合一些调试打印语句，我们很容易就能摸清楚各个对象的成分和代码存在的问题。

任务二：实现迭代求解器

任务二涉及两个方法的实现：

1. Solver中的void initializeBackward(CFG, DataflowResult)
2. IterativeSolver中的void doSolveBackward(CFG, DataflowResult)

其中，Solver是求解器的基类，IterativeSolver继承了Solver类。从任务二可以体会到面向对象语言带来的抽象之美——作为基类，Solver的initializeBackward并不关心边界和非边界基本块的初始化方式及具体值，而是直接调用我们在任务一中实现的LiveVariableAnalysis的相关方法。下次即使换了一个分析应用场景，Solver的方法不需要做改变。

Solver的initializeBackward方法实现如下：

protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    result.setInFact(cfg.getExit(), analysis.newBoundaryFact(cfg));
    for (Node node: cfg) {
        if (cfg.isExit(node)) {
            continue;
        }
        result.setInFact(node, analysis.newInitialFact());
        result.setOutFact(node, analysis.newInitialFact());
    }
}

需要注意的是，由于没有刻意要求迭代求解过程的基本块处理顺序（事实上也不需要，无论从哪个块开始，最终总会达到同一结果并终止），我们需要在initializeBackward方法中将所有基本块的$OUT[B]$初始化为空集。这一点在上一节中的算法上并未明确体现。这是因为，我们在control flow handling的实现上做了变通，并未按照原算法那样每次为$OUT[B]$新生成一个集合，而是直接将后继块中的facts并入了原来的$OUT[B]$，这就要求我们在最开始对$OUT[B]$初始化，否则会遇到空指针问题。

IterativeSolver的void doSolveBackward方法实现如下：

protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    boolean changesOccur = true;
    while(changesOccur) {
        boolean transferRes = false;
        for (Node node: cfg) {
            if (cfg.isExit(node)) {
                continue;
            }
            for (Node s: cfg.getSuccsOf(node)) {
                analysis.meetInto(result.getInFact(s), result.getOutFact(node));
            }
            boolean tmpRes = analysis.transferNode(node, result.getInFact(node), result.getOutFact(node));
            if (!transferRes && tmpRes) {
                transferRes = true;
            }
        }
        changesOccur = transferRes;
    }
}

测试示例

这里我们展示一下前文实现的存活变量分析程序对Branch用例的分析结果。Branch类的源码如下所示：

class Branch {
    int ifElse(int m, int n, int k) {
        int x = m;
        if (n > 0) {
            return x + n;
        } else {
            return k + n;
        }
    }
}

分析结果如下：

-------------------- <Branch: void <init>()> (livevar) --------------------
[0@L1] invokespecial %this.<java.lang.Object: void <init>()>(); []
[1@L1] return; []

-------------------- <Branch: int ifElse(int,int,int)> (livevar) --------------------
[0@L4] x = m; [k, n, x]
[1@L5] %intconst0 = 0; [%intconst0, k, n, x]
[2@L5] if (n > %intconst0) goto 4; [k, n, x]
[3@L5] goto 7; [k, n]
[4@L5] nop; [n, x]
[5@L5] temp$1 = x + n; [temp$1]
[6@L6] return temp$1; []
[7@L6] nop; [k, n]
[8@L6] temp$3 = k + n; [temp$3]
[9@L8] return temp$3; []

值得注意的是， 结果中每行后的中括号括起来的内容是$OUT[B]$，而非$IN[B]$。

总结与思考

本实验帮助我们增强了对数据流分析应用的理解，初步实现了从理论到实践的转化。除了作为实验作业平台之外，Tai-e还是一个优秀的Java静态分析框架，学习它的使用方法和设计实现，对于掌握静态分析技术大有裨益。