题目链接:https://tai-e.pascal-lab.net/pa3.html
评测链接:https://oj.pascal-lab.net/problem
作业出品:南京大学《软件分析》课程,谭添、李樾
直接看题目链接中的讲解即可,非常详细。
整体思路:
不从死代码出发,而是记录所有可达的语句,最后一个方法中没有被记录的语句都是不可达的死代码。
不能直接遍历控制流图中的 IR
,这些 IR
有可能是不可达的,而是使用队列(stmts
)记录所有即将被访问的语句,使用 bfs
进行遍历,对于每条语句根据其不同的类型进行不同处理。
除了队列以外,还需要一个集合(reached
)来判断某条语句是否访问过,避免重复访问,防止死循环。
最后使用一个集合(reachable
)记录哪些语句是可达的(语句先访问再判断是否可达)。
有几个易错点:
AssignStmt
处理时,左值要先判断能否转成成 Var
,防止类型转换异常。SwitchStmt
处理时,如果所有 case
都匹配不到,可能会执行 default
中控制流,别忘了。@Override 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 // Your task is to recognize dead code in ir and add it to deadCode ArrayDeque<Stmt> stmts = new ArrayDeque<>(); // 队列 Set<Stmt> reachable = new HashSet<>(); Set<Stmt> reached = new HashSet<>(); stmts.addLast(cfg.getEntry()); // 第一个访问结点是方法的入口 reachable.add(cfg.getExit()); // 方法的入口和出口肯定是可达的 reachable.add(cfg.getEntry()); while (!stmts.isEmpty()) { // bfs开始 Stmt stmt = stmts.pollFirst(); // 弹出队头 reached.add(stmt); // 记录弹出结点被访问 if (stmt instanceof AssignStmt assignStmt) { // 无用赋值语句处理 SetFact<Var> liveVarsResult = liveVars.getResult(assignStmt); // 获取当前语句执行后的活跃变量结果 LValue lValue = assignStmt.getLValue(); // 获取当前语句的左值 RValue rValue = assignStmt.getRValue(); // 获取当前语句的右值 boolean f = true; // 特殊情况:左值是死变量,右值没有side effect的语句是死代码 if (lValue instanceof Var) { // 易错点1:要判断左值是否能转化成变量类型 if (!liveVarsResult.contains((Var) lValue)) { // dead if (hasNoSideEffect(rValue)) { // no side effect f = false; } } } if (f) { // 如果不是特殊情况,那么当前语句可达 reachable.add(assignStmt); } for (Stmt succ : cfg.getSuccsOf(assignStmt)) { // 后继结点加入队列 if (!reached.contains(succ)) stmts.addLast(succ); } } else if (stmt instanceof If ifStmt) { // if语句处理 CPFact result = constants.getResult(ifStmt); // 获取常量传播结果 ConditionExp condition = ifStmt.getCondition(); // 获取if条件表达式 ConditionExp.Op operator = condition.getOperator(); // 获取运算符 Value evaluate = ConstantPropagation.evaluate(condition, result); // 计算if条件表达式 reachable.add(ifStmt); // 当前if语句可达 if (evaluate.isConstant()) { // 如果if条件表达式是个常数,那么只可能到达一个分支 if (evaluate.getConstant() == 1) { // 永远true for (Edge<Stmt> edge : cfg.getOutEdgesOf(ifStmt)) { // 所有出边 if (edge.getKind() == Edge.Kind.IF_TRUE) { // true边一定到 Stmt target = edge.getTarget(); if (!reached.contains(target)) stmts.add(target); // 目标结点添加到队列 } } } else { // 永远false for (Edge<Stmt> edge : cfg.getOutEdgesOf(stmt)) { // 所有出边 if (edge.getKind() == Edge.Kind.IF_FALSE) { // false边一定到 Stmt target = edge.getTarget(); if (!reached.contains(target)) stmts.add(target); // 目标节点添加到队列 } } } } else { // 如果if条件表达式不是个常数,那么两条分支都可能,按照控制流执行 for (Stmt succ : cfg.getSuccsOf(stmt)) { if (!reached.contains(succ)) stmts.addLast(succ); } } } else if (stmt instanceof SwitchStmt switchStmt) { // switch语句处理 Var var = switchStmt.getVar(); // 获取switch表达式的变量 CPFact result = constants.getResult(switchStmt); // 获取常量传播结果 reachable.add(switchStmt); // 当前switch语句可达 if (result.get(var).isConstant()) { // 如果switch表达式是常数,只可能到达几个分支 int constant = result.get(var).getConstant(); // 获取表达式的常量值 boolean match = false; // 易错点2:记录是否匹配case,如果没有,将执行default for (Edge<Stmt> edge : cfg.getOutEdgesOf(switchStmt)) { // 获取所有出边 if (edge.getKind() == Edge.Kind.SWITCH_CASE) { // 如果是case类型边 int caseValue = edge.getCaseValue(); // 获取case值 if (caseValue == constant) { // 如果是匹配的case match = true; if (!reached.contains(edge.getTarget())) stmts.addLast(edge.getTarget()); } } } if (!match) { // 如果不匹配,执行default Stmt defaultTarget = switchStmt.getDefaultTarget(); // 获取default对应的目标语句 if (!reached.contains(defaultTarget)) stmts.addLast(defaultTarget); } } else { // 如果switch表达式不是常数,每个case都可能执行,按照控制流执行 for (Stmt succ : cfg.getSuccsOf(switchStmt)) { if (!reached.contains(succ)) stmts.addLast(succ); } } } else { // 其他类型语句,都可达,按照控制流执行 reachable.add(stmt); for (Stmt succ : cfg.getSuccsOf(stmt)) { if (!reached.contains(succ)) stmts.addLast(succ); } } } for (Stmt stmt : ir.getStmts()) { // 遍历当前方法的所有IR,如果不可达,那么就是死代码 if (!reachable.contains(stmt)) { deadCode.add(stmt); } } return deadCode; }
⭐ 新语法知识:
在Java 14及更高版本中,可以使用" Pattern Matching for instanceof
"特性来将 instanceof
的结果转化并赋值给一个新的变量。这种语法可以简化类型判断和类型转换的代码。注意,被转换的对象必须是final
或effectively final
的,以确保转换后的变量是不可变的。此外,这种语法只适用于局部变量,不能用于成员变量或静态变量的赋值。
if (obj instanceof MyClass myObj) { // 将obj转换为MyClass类型,并赋值给myObj变量 // 可以在if语句的代码块中使用myObj myObj.doSomething(); } else { // obj不是MyClass类型的处理逻辑 // ... }