前言
这是南大软件分析课程的第三个作业，综合了存活变量分析、常量传播和CFG的相关知识，都是我们已经学过的内容。实验手册见官方网站。
具体到代码层面，我们可以把A1实验和A2实验的代码直接拿过来填充到本实验中相应的存活变量分析和常量传播对应模块，实际需要完成的只有基于Worklist的backward求解方法和死代码检测的analyze方法，而前者又非常简单，只需要根据backward的求解实现简单调整一下即可。
因此，本实验的重点和难点都在于如何应用学过的数据流分析来实现死代码检测。
与A2实验类似，通过本地测试用例很容易，但想要通过所有OJ平台测试用例却并不容易。经过多次迭代，我的代码最终能够正确处理42个方法中的41个，死代码检出率为97.67%，仍然有12个漏报的死代码语句。相关的提交记录如下：
Analyze 42 methods, pass 34 methods
There are 516 dead Stmts in all test cases
Your submission correctly detects 287 dead Stmts
#false negatives: 229
#false positives: 0
Analyze 42 methods, pass 38 methods
There are 516 dead Stmts in all test cases
Your submission correctly detects 462 dead Stmts
#false negatives: 54
#false positives: 0
Analyze 42 methods, pass 41 methods
There are 516 dead Stmts in all test cases
Your submission correctly detects 504 dead Stmts
#false negatives: 12
#false positives: 0
第一次提交后系统就提示所有失败测试均属于非公开测试用例，因此我们只能本地调试。通过编写测试用例并测试，我发现第一版代码并不能正确处理无break的switch/case语句。我有考虑到fall-through，但是在第一版中使用了Stmt的canFallThrough方法来判断，这是不正确的，因为该方法并不是为switch这个情况设计的。
修改正确后，通过率显著提高。接着，我从一篇博客和GitHub issue发现了另一个问题：赋值语句的左值并不一定就是Var类型，需要先判断再强制转换。
总体来讲，这个实验还是蛮有趣的，只是在黑盒状态下调试并不方便，但也无伤大雅。
更新 - 2024-04-13
通过与另一位同学的代码对比，我找到了问题：不能一开始就使用for循环遍历所有IR！这实际上假设了所有IR可达，然而很明显这些IR中存在不可达的。最好从入口点开始BFS搜索判断。
如何检测死代码
检测死代码，就要首先明确一下何为死代码，再谈检测方法。在本实验中，我们主要关注两类死代码：
- 不可达代码（unreachable code），这又分为两种情况：
- 控制流不可达代码（control-flow unreachable code），指的是从程序入口到某一段代码的控制流路径不存在的情况。例如，在方法return语句后的代码就是控制流不可达的。检测方法也很简单，我们可以从程序入口遍历CFG，所有遍历到的节点都是控制流可达的，其余节点就是控制流不可达的死代码了。
- 分支不可达代码（unreachable branch），指的是某个条件分支可能不会执行。Java中的条件分支语句有两种：if语句和switch语句。如果if语句的判断条件为永真或永假，那么必定有一个分支是不可达的，成为死代码。对于switch语句来说，情况有些不同。如果switch语句中的判断变量是常量且会命中某个case，那么该case上方的所有分支一定是不可达的，下方的则要根据目标case代码块及下方cases代码块的break情况来判断——如果目标case后没有break，甚至下方若干cases都没有break，那这些部分是可达的（fall-through），其余情况则不是。对于分支情况，检测方法是首先应用常量传播的结果来判断分支条件是否为常量，如果是常量，则在遍历CFG时，跳过不可达分支代码块即可。
- 无用赋值（dead assignment），指的是某个局部变量在一条语句中被赋值，但再也没有被该语句后面的语句读取。很明显，我们可以应用存活变量分析的结果来判断某个赋值语句是否为死代码。需要注意的是，有的赋值语句可能带有副作用，需要特殊对待。不过，实验中老师们已经实现了一个hasNoSideEffect方法来帮助判断赋值语句是否有副作用，这降低了实验难度。
死代码检测方法的具体实现
理解了不同情形的死代码及对应的检测思路，我们就可以编写代码了。如开头所述，实现一个基础版本并不难，难的是在缺乏足够测试用例的条件下处理各种可能情况。我们可以选择尽量让自己的逻辑严密，也可以选择编写一些新的测试用例辅助调试，但无论选择哪种提高方法，其最终还是依赖于我们对编程语言细节和数据流分析技术的掌握广度和深度。
另外，可以模仿Worklist的方式用一个队列加一个循环来实现从入口开始遍历CFG。最终实现代码如下：
public Set<Stmt> analyze(IR ir) {
// obtain CFG
CFG<Stmt> cfg = ir.getResult(CFGBuilder.ID);
// obtain result of constant propagation
DataflowResult<Stmt, CPFact> constants =
ir.getResult(ConstantPropagation.ID);
// obtain result of live variable analysis
DataflowResult<Stmt, SetFact<Var>> liveVars =
ir.getResult(LiveVariableAnalysis.ID);
// keep statements (dead code) sorted in the resulting set
Set<Stmt> deadCode = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
// TODO - finish me - DONE
System.out.printf("cfg: %s\n", cfg.getNodes());
// Your task is to recognize dead code in ir and add it to deadCode
Set<Stmt> badIfBranches = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
Set<Stmt> badSwBranches = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
// 1. unreachable code
for (Stmt s: ir) {
// 1.2 branch unreachable
// 1.2.1 `if` branch unreachable
if (s instanceof If) {
Var operand1 = ((If) s).getCondition().getOperand1();
Var operand2 = ((If) s).getCondition().getOperand2();
if (constants.getInFact(s).get(operand1).isConstant() &&
constants.getInFact(s).get(operand2).isConstant()) {
Value val = ConstantPropagation.evaluate(((If) s).getCondition(), constants.getInFact(s));
for (Edge<Stmt> edge: cfg.getOutEdgesOf(s)) {
if (edge.getKind() == Edge.Kind.IF_TRUE && val.getConstant() != 1) {
badIfBranches.add(edge.getTarget());
} else if (edge.getKind() == Edge.Kind.IF_FALSE && val.getConstant() != 0) {
badIfBranches.add(edge.getTarget());
}
}
}
}
// 1.2.2 `switch` branch unreachable
if (s instanceof SwitchStmt) {
Var var = ((SwitchStmt) s).getVar();
if(constants.getInFact(s).get(var).isConstant()) {
int idx = ((SwitchStmt) s).getCaseValues().indexOf(constants.getInFact(s).get(var).getConstant());
if (idx >= 0) {
// cases before the target case
for (int i = 0; i < idx; i++)
badSwBranches.add(((SwitchStmt) s).getTarget(i));
// cases after the target case
idx += 1;
for (; idx < ((SwitchStmt) s).getCaseValues().size(); idx++) {
System.out.printf("[%d] %s\n", idx, ((SwitchStmt) s).getTarget(idx));
badSwBranches.add(((SwitchStmt) s).getTarget(idx));
}
badSwBranches.add(((SwitchStmt) s).getDefaultTarget());
}
}
}
// 2. useless assignment
if (s instanceof AssignStmt<?,?>) {
if (((AssignStmt<LValue, RValue>) s).getLValue() instanceof Var) {
Var var = (Var)((AssignStmt<LValue, RValue>) s).getLValue();
if (!liveVars.getOutFact(s).contains(var)) {
if (hasNoSideEffect(((AssignStmt<LValue, RValue>) s).getRValue())) {
deadCode.add(s);
}
}
}
}
}
// deal with bad branches
ArrayList<Stmt> goodArrayList = new ArrayList<Stmt>();
ArrayList<Stmt> nodeArrayList = new ArrayList<Stmt>();
nodeArrayList.add(cfg.getEntry());
while(!nodeArrayList.isEmpty()) {
// System.out.printf("nodeArrList: %s\n", nodeArrayList);
Stmt s = nodeArrayList.remove(0);
goodArrayList.add(s);
for (Edge<Stmt> edge: cfg.getOutEdgesOf(s)) {
if (badIfBranches.contains(edge.getTarget())) {
continue;
}
if ((s instanceof SwitchStmt) && badSwBranches.contains(edge.getTarget())) {
continue;
}
if (goodArrayList.contains(edge.getTarget())) {
continue;
}
nodeArrayList.add(edge.getTarget());
}
}
for(Stmt stmt: ir) {
if (!goodArrayList.contains(stmt) && !cfg.isExit(stmt)) {
deadCode.add(stmt);
}
}
return deadCode;
}
总结与思考
这几个实验都非常有意思，能够帮助我们把知识应用于实践。如此用心的课程，国内并不多见，也希望南大和其他高校的同学们珍惜这样的学习机会。独立思考，勤于实践，共勉。