前言
因为开始写博客的时间已经完成了前两次的实验，所以也不打算重新补写前两次的实验笔记了。如果增加这个工作量我肯定会对写博客产生抵触心理，因为我补充了这个那我后续在其他方面不能不补充厚此薄彼吧，这样一下子积压了大量需要补充的内容压力过大会导致我直接化身怯战蜥蜴——放弃。
作业3：死代码检测，并不是我们上课学习的内容，但是通过组合我前两次作业中实现的分析方法：活跃变量分析和常量传播，可以实现一个Java的死代码检测算法。
课程网站为Static Program Analysis | Tai-e
本次实验为作业 3：死代码检测 | Tai-e
死代码检测介绍
死代码指的是程序中不可达的（unreachable）代码（即不会被执行的代码），或者是执行结果永远不会被其他计算过程用到的代码。去除死代码可以在不影响程序输出的前提下简化程序、提高效率。我们在这次实验中考虑两种死代码：不可达代码（unreachable code）和无用赋值（unreachable code）。这好像正好分别对应了常量传播和活跃变量分析。
不可达代码
一个程序中永远不可能被执行的代码被称为不可达代码。我们考虑两种不可达代码：控制流不可达代码（control-flow unreachable code）和分支不可达代码（unreachable branch）。
控制流不可达代码：在一个方法中，如果不存在从程序入口到达某一段代码的控制流路径，那么这一段代码就是控制流不可达的。
检测方式：利用所在方法的控制流图（CFG，即 control-flow graph）检测出来。我们只需要从方法入口开始，遍历 CFG 并标记可达语句。当遍历结束时，那些没有被标记的语句就是控制流不可达的。
分支不可达代码：在 Java 中有两种分支语句：if 语句和 switch 语句。它们可能会导致分支不可达代码的出现。
对于一个 if 语句，如果它的条件值（通过常量传播得知）是一个常数，那么无论程序怎么执行，它两个分支中的其中一个分支都不会被走到。这样的分支被称为不可达分支。该分支下的代码也因此是不可达的，被称为分支不可达代码。
对于一个 switch 语句，如果它的条件值是一个常数，那么不符合条件值的 case 分支就可能是不可达的。
检测方式：为了检测分支不可达代码，我们需要预先对被检测代码应用常量传播分析，通过它来告诉我们条件值是否为常量，然后在遍历 CFG 时，我们不进入相应的不可达分支。
无用赋值
一个局部变量在一条语句中被赋值，但再也没有被该语句后面的语句读取，这样的变量和语句分别被称为无用变量（dead variable，与活跃变量 live variable 相对）和无用赋值。无用赋值不会影响程序的输出，因而可以被去除。
检测方式：为了检测无用赋值，我们需要预先对被检测代码施用活跃变量分析。对于一个赋值语句，如果它等号左侧的变量（LHS 变量）是一个无用变量（换句话说，not live），那么我们可以把它标记为一个无用赋值。
但需要注意的是，以上讨论有一种例外情况：有时即使等号左边的变量 x 是无用变量，它所属的赋值语句 x = expr 也不能被去除，因为右边的表达式 expr 可能带有某些副作用。例如，当 expr 是一个方法调用（x = m()）时，它就有可能带有副作用，可能在m()中改变了某些值。对于这种情况，作业提供了一个 API 供检查等号右边的表达式是否可能带有副作用。如果带有副作用，那么为了保证 safety，即使 x 不是一个活跃变量，也不应该把这个赋值语句标记为死代码。
任务
补全代码
完成本次实验首先需要补全 LiveVariableAnalysis.java 和 ConstantPropagation.java。我可以拷贝之前作业中的实现。另外，我也需要完成一个同时支持前向分析和后向分析的 worklist 求解器。我可以从实验2中拷贝我之前对 Solver.java 和 WorkListSolver.java 的实现，并在这次作业中实现 Solver.initializeBackward()和 WorkListSolver.doSolveBackward()。所以要先打开我心爱的idea进行复制粘贴。这里还要单独实现后向分析的初始化和流程。死代码检测除了前向分析还会后向分析？
认识新的类
- pascal.taie.analysis.graph.cfg.Edge
这个类表示 CFG 中的边（提示：CFG 中的节点是 Stmt）。它具有方法 getKind()，可以用来得知某个边的种类（你可以通过阅读类 Edge.Kind 的注释来理解各个种类的含义），并且可以像下面这样检查边的种类：
Edge<Stmt> edge = ...;
if (edge.getKind() == Edge.Kind.IF_TRUE) { ... }
在这次作业中，我需要考虑四种边：IF_TRUE、IF_FALSE、SWITCH_CASE 和 SWITCH_DEFAULT。IF_TRUE 和 IF_FALSE 表示从 if 语句到它的两个分支的出边，SWITCH_CASE 和 SWITCH_DEFAULT 表示从 switch 语句到它的 case 分支和 default 分支的出边。对于 SWITCH_CASE 边，可以通过 getCaseValue() 方法来获取它们对应的 case 分支的条件值。
- pascal.taie.ir.stmt.If（
Stmt的子类）
这个类表示程序中的 if 语句。可以通过getCondition()获得条件语句exp，然后可以通过getOperator()获得操作符包括==、!=、<、>、<=、>=。
- pascal.taie.ir.stmt.SwitchStmt（
Stmt的子类）
这个类表示程序中的 switch 语句。getVar()获得case的值，getDefaultTarget()获得默认执行的语句，getTarget(int i)获得第 i + 1 条 case 执行的语句，getTargets()可以获得一个集合。
- pascal.taie.ir.stmt.AssignStmt（
Stmt的子类）
这个类表示程序中的赋值语句（比如 x = ...;）。你可能会觉得它有点像你之前看到过的 DefinitionStmt。事实上，AssignStmt 是 DefinitionStmt 两个子类的其中一个（另一个是 Invoke，它表示程序中的方法调用）。这意味着除了等号右侧是方法调用的赋值语句，其他赋值语句都用 AssignStmt 表示。本次作业中所有可能的无用赋值都只可能是 AssignStmt 的实例。你只需要关注 AssignStmt 这个类即可。
- pascal.taie.analysis.dataflow.analysis.DeadCodeDetection
这个类是实现死代码检测的类，也是我们要实现的API所在的类。
实现过程
复制粘贴的过程非常的简单，然后要完成的是针对 WorkList 的 Solver.initializeBackward()和 WorkListSolver.doSolveBackward()的实现。这里我又回去看了一下啊A1，然后整理发现Solver.initializeBackward()实际上是没有变化的，WorkList只是针对迭代的判断进行了优化。所以在原有的基础上对 Solver.initializeBackward()进行修改如下：
@Override
protected void doSolveBackward(CFG cfg, DataflowResult result) {
// TODO - finish me
ArrayList Worklist = new ArrayList<>();
for(Node n : cfg){
if (!cfg.isExit(n))
Worklist.add(n);
}
while(!Worklist.isEmpty()){
Node node = Worklist.remove(0);
for(Node n : cfg.getSuccsOf(node)){
analysis.meetInto(result.getInFact(n), result.getOutFact(node));
}
if(analysis.transferNode(node, result.getOutFact(node), result.getInFact(node))){
for(Node n : cfg.getPredsOf(node)){
Worklist.add(n);
}
}
}
}
这里其实很简单，只要根据 forward 稍微修改一下即可。
然后是 SetIR 作为输入，返回一个包含 IR 中死代码的集合。我的任务是找出前文中描述的两种死代码（也就是不可达代码和无用赋值），然后将它们加入到作为结果返回的集合中。 为了简单起见，你不需要考虑由删除死代码而产生的新的死代码。
最终实现如下：
@Override
public Set analyze(IR ir) {
// obtain CFG
CFG cfg = ir.getResult(CFGBuilder.ID);
// obtain result of constant propagation
DataflowResult constants =
ir.getResult(ConstantPropagation.ID);
// obtain result of live variable analysis
DataflowResult> liveVars =
ir.getResult(LiveVariableAnalysis.ID);
// keep statements (dead code) sorted in the resulting set
Set deadCode = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
// TODO - finish me
// Your task is to recognize dead code in ir and add it to deadCode
//要先判断是否可达
ArrayList reach = new ArrayList<>();//记录可达
ArrayList reached = new ArrayList<>();//记录已到达避免无限循环
reach.add(cfg.getEntry());
reach.add(cfg.getExit());
ArrayList stmts = new ArrayList<>();
stmts.add(cfg.getEntry());
while(!stmts.isEmpty()) {
Stmt s = stmts.remove(0);
//记录已到达s
reached.add(s);
if (s instanceof If) {
reach.add(s);//记录可到达 if stmt
//if语句的值
Value flag = ConstantPropagation.evaluate(((If) s).getCondition(), constants.getResult(s));
//判断是否为常数
if (flag.isConstant()) {
//true语句可达
if (flag.getConstant() == 1) {
for (Edge edge : cfg.getOutEdgesOf(s)) {
Stmt target = edge.getTarget();
if (edge.getKind() == Edge.Kind.IF_TRUE && !reached.contains(target)) {
// 将未遍历过的 true stmt 添加到队列
stmts.add(target);
}
}
} else {
//false语句可达
for (Edge edge : cfg.getOutEdgesOf(s)) {
Stmt target = edge.getTarget();
if (edge.getKind() == Edge.Kind.IF_FALSE && !reached.contains(target)) {
// 将未遍历过的 false stmt 添加到队列
stmts.add(target);
}
}
}
}else{
for (Stmt succ : cfg.getSuccsOf(s)) {
if (!reached.contains(succ)) {
// 将未遍历过的 stmt 添加到队列
stmts.add(succ);
}
}
}
} else if (s instanceof SwitchStmt) {
//记录可到达 switch stmt
reach.add(s);
//switch语句的case值
Value caseValue = constants.getResult(s).get(((SwitchStmt) s).getVar());
//判断是否为常数
if (caseValue.isConstant()) {
//满足case的id
int val = caseValue.getConstant();
List valList = ((SwitchStmt) s).getCaseValues();
int id = valList.indexOf(val);
//存在满足条件的
if (id != -1) {
for (Edge edge : cfg.getOutEdgesOf(s)) {
//先判断是switchcase语句，然后或取值与常量对比，然后判断是否已到达
if (edge.getKind() == Edge.Kind.SWITCH_CASE && edge.getCaseValue() == val && !reached.contains(edge.getTarget())) {
// 将未遍历过的 switch stmt 添加到队列
stmts.add(edge.getTarget());
}
}
} else {
//若没有则default
Stmt target = ((SwitchStmt) s).getDefaultTarget();
if (!reached.contains(target)) {
stmts.add(target);
}
}
}else{
for (Stmt succ : cfg.getSuccsOf(s)) {
if (!reached.contains(succ))
stmts.add(succ);
}
}
} else if (s instanceof AssignStmt) {
LValue l = ((AssignStmt)s).getLValue();
RValue r = ((AssignStmt)s).getRValue();
boolean is_dead = false;
if (l instanceof Var) { //要判断左值是否能转化成变量类型,前面有过类似问题
if (!liveVars.getResult(s).contains((Var) l)) { // 不活跃
if (hasNoSideEffect(r)) { // 没有副作用
is_dead = true;
}
}
}
if(!is_dead){
reach.add(s);
}
for (Stmt succ : cfg.getSuccsOf(s)) {
if (!reached.contains(succ)) {
// 将未遍历过的后续 stmt 添加到队列
stmts.add(succ);
}
}
} else{
//记录可到达该 stmt
reach.add(s);
for (Stmt succ : cfg.getSuccsOf(s)) {
if (!reached.contains(succ))
stmts.add(succ);
}
}
}
for (Stmt s : ir) {
if(!reach.contains(s)){
deadCode.add(s);
}
}
return deadCode;
}
这里一开始对于Assignment的分析是正向写的，导致漏了一些情况将他们加入可以到达的语句，后面只考虑特殊情况来做特殊处理就通过了。
不过我还遇到一个问题就是在我的idea里面始终不通过，我首先针对前面复制的部分我做了一一对比，甚至重新复制粘贴，在复制粘贴前甚至还重新测试了 A1，A2 但均未发现问题。然后我试着尝试提交发现我的代码找到了所有的死代码，但是有一些误报（如上文），然后我再重新修改的时候，在本地通过了四个测试，这进一步说明我的复制粘贴部分是正确的，但是我发现我修改的逻辑是反的，于是我改正了之后，本地的test又全部失败，我找了很久没发现问题，我再次尝试提交到网站上测试，最终AC。不知道是不是我误触了什么改变了一些本地的代码，导致这样的情况发生。
总之，由于本地的问题，本应该昨天就写完的一直拖到今天才结束，不过不影响这是一次有意义的学习过程。