Post

NJU静态分析 - Lab1 - Live Variable Analysis

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框架的作者用OptionalList去包装这两个信息,而这两种信息的类型分别为LValueRValue。注意在代码实现中要解包装。

pascal.taie.ir.exp.Var

VarExp的一种,从Var的声明可以看出,Varimplement了LValueRValue,因此在求解器中获取每一条StmtLValueRValue时需要注意类型转换:

1
public class Var implements LValue, RValue, Indexable {}
1
2
3
4
5
6
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:

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

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

pascal.taie.analysis.dataflow.solver.Solver

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

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

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

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

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

1
2
3
4
5
6
7
private void doSolve(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    if (analysis.isForward()) {
        doSolveForward(cfg, result);
    } else {
        doSolveBackward(cfg, result);
    }
}

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

测试方式

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

代码实现

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

This post is licensed under CC BY 4.0 by the author.