NJU静态分析 - Lab1 - Live Variable Analysis

分析

第一个实验较为简单，如果先前学习过NJU编译原理，那么对活跃变量分析算法应该会较为熟悉。对于活跃变量分析，我们使用的是may-analysis，推导方向是backward，初始化时边界和非边界均初始化为空集，转换函数为OUT = gen + (IN - kill)，Meet函数为取并集。

代码框架分析

本实验的难点与其说是将代码填入每一个TODO，不如说是去理解Tai-e框架。因此首先分析一下对本次实验比较重要的几个类

pascal.taie.ir.stmt.Stmt

这个类表示的是Soot输出的Ir，这种Ir是一种三地址码，由三地址码的性质可知，对于每一条Stmt，至多只可能定义一个变量、而可能使用零或多个变量，因此Tai-e框架的作者用Optional和List去包装这两个信息，而这两种信息的类型分别为LValue和RValue。注意在代码实现中要解包装。

pascal.taie.ir.exp.Var

Var是Exp的一种，从Var的声明可以看出，Varimplement了LValue和RValue，因此在求解器中获取每一条Stmt的LValue和RValue时需要注意类型转换：

public class Var implements LValue, RValue, Indexable {}

List<RValue> uses = stmt.getUses();
for (RValue use : uses) {
    if (use instanceof Var) { // 类型转换
        in.add((Var) use);
    }
}

pascal.taie.analysis.dataflow.fact.DataflowResult

DataflowResult主要维护了两个Map，分别对应于Infact和Outfact，由此来表示CFG上每一个节点的Infact和Outfact：

private final Map<Node, Fact> inFacts = new LinkedHashMap<>();

private final Map<Node, Fact> outFacts = new LinkedHashMap<>();

pascal.taie.analysis.dataflow.solver.Solver

有必要介绍一下求解器的工作流程，这有助于之后几个Lab的实现。首先Solver的构造函数如下：

protected Solver(DataflowAnalysis<Node, Fact> analysis) {
    this.analysis = analysis;
}

可以看到Solver储存了一个DataflowAnalysis作为其成员，因此Solver进行静态分析的主要方式就是对DataflowAnalysis的API进行调用，其调用方式可以在接下里的代码里看到：

public DataflowResult<Node, Fact> solve(CFG<Node> cfg) {
    DataflowResult<Node, Fact> result = initialize(cfg);
    doSolve(cfg, result);
    return result;
}

solve是对外的一个接口，该函数被调用后，求解过程开始，首先进行的是initialize函数，该函数初始化CFG图上所有Node的Fact信息。接下来进行求解。

private void doSolve(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    if (analysis.isForward()) {
        doSolveForward(cfg, result);
    } else {
        doSolveBackward(cfg, result);
    }
}

求解时分为向上求解和向下求解，这种分离使得编写代码的时候更加模块化，其中doSolveForward和doSolveBackward都是Abstract函数，由更加具体的求解器去实现。initialize函数也分向上和向下，再次不多加赘述。

测试方式

Tai-e作者提供的JUnit测试能胜任大部分测试工作，JUnit也可以直接用来Debug，非常的方便。

代码实现

应Academic Integrity的要求，不呈现完整代码，但通过以上分析，完整的代码已经呼之欲出了。