前言

这是南大软件分析课程的第三个作业,综合了存活变量分析、常量传播和CFG的相关知识,都是我们已经学过的内容。实验手册见官方网站

具体到代码层面,我们可以把A1实验A2实验的代码直接拿过来填充到本实验中相应的存活变量分析和常量传播对应模块,实际需要完成的只有基于Worklist的backward求解方法和死代码检测的analyze方法,而前者又非常简单,只需要根据borward的求解实现简单调整一下即可。

因此,本实验的重点和难点都在于如何应用学过的数据流分析来实现死代码检测。

与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类型,需要先判断再强制转换。

总体来讲,这个实验还是蛮有趣的,只是在黑盒状态下调试并不方便,但也无伤大雅。

如何检测死代码

检测死代码,就要首先明确一下何为死代码,再谈检测方法。在本实验中,我们主要关注两类死代码:

  1. 不可达代码(unreachable code),这又分为两种情况:
    1. 控制流不可达代码(control-flow unreachable code),指的是从程序入口到某一段代码的控制流路径不存在的情况。例如,在方法return语句后的代码就是控制流不可达的。检测方法也很简单,我们可以从程序入口遍历CFG,所有遍历到的节点都是控制流可达的,其余节点就是控制流不可达的死代码了。
    2. 分支不可达代码(unreachable branch),指的是某个条件分支可能不会执行。Java中的条件分支语句有两种:if语句和switch语句。如果if语句的判断条件为永真或永假,那么必定有一个分支是不可达的,成为死代码。对于switch语句来说,情况有些不同。如果switch语句中的判断变量是常量且会命中某个case,那么该case上方的所有分支一定是不可达的,下方的则要根据目标case代码块及下方cases代码块的break情况来判断——如果目标case后没有break,甚至下方若干cases都没有break,那这些部分是可达的(fall-through),其余情况则不是。对于分支情况,检测方法是首先应用常量传播的结果来判断分支条件是否为常量,如果是常量,则在遍历CFG时,跳过不可达分支代码块即可。
  2. 无用赋值(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
    Set<Stmt> badIfBranches = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
    Set<Stmt> badSwBranches = new TreeSet<>(Comparator.comparing(Stmt::getIndex));
    for (Stmt s: ir) {
	    // 1. unreachable code
        // 1.2 branch unreachable
        // 1.2.1 `if` branch unreachable
        if (s instanceof If) {
            // ...
        }
        // 1.2.2 `switch` branch unreachable
        if (s instanceof SwitchStmt) {
            Var var = ((SwitchStmt) s).getVar();
            if(constants.getInFact(s).get(var).isConstant()) {
                // ...
            }
        }
        // 2. useless assignment
        if (s instanceof AssignStmt<?,?>) {
            // ...
        }
    }
    // deal with bad branches
    ArrayList<Stmt> goodArrayList = new ArrayList<Stmt>();
    ArrayList<Stmt> nodeArrayList = new ArrayList<Stmt>();
    nodeArrayList.add(cfg.getEntry());
    while(!nodeArrayList.isEmpty()) {
        Stmt s = nodeArrayList.remove(0);
        goodArrayList.add(s);
        for (Edge<Stmt> edge: cfg.getOutEdgesOf(s)) {
            // ...
        }
    }
    // (also including) 1.1 control-flow unreachable
    for(Stmt stmt: ir) {
        if (!goodArrayList.contains(stmt) && !cfg.isExit(stmt))
            deadCode.add(stmt);
    }
    return deadCode;
}

总结与思考

这几个实验都非常有意思,能够帮助我们把知识应用于实践。老师们设计这些实验应该也投入了很多精力。为了不给南大的老师和同学添麻烦,我将在实验相关的博客文章中隐去关键代码块,仅仅保留大体实现框架。如此用心的课程,国内并不多见,也希望南大和其他高校的同学们珍惜这样的学习机会。独立思考,勤于实践,共勉。