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
的声明可以看出,Var
implement了LValue
和RValue
,因此在求解器中获取每一条Stmt
的LValue
和RValue
时需要注意类型转换:
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);
}
}
求解时分为向上求解和向下求解,这种分离使得编写代码的时候更加模块化,其中doSolveForward
和doSolveBackward
都是Abstract
函数,由更加具体的求解器去实现。initialize
函数也分向上和向下,再次不多加赘述。
测试方式
Tai-e作者提供的JUnit测试能胜任大部分测试工作,JUnit也可以直接用来Debug,非常的方便。
代码实现
应Academic Integrity的要求,不呈现完整代码,但通过以上分析,完整的代码已经呼之欲出了。