【程序分析】南京大学软件分析Lab3（死代码消除）思路

int unreachableSwitchBranch() {
    int x = 2, y;
    switch (x) {
        case 1: y = 100; break; // unreachable branch
        case 2: y = 200;
        case 3: y = 300; break; // fall through
        default: y = 666; // unreachable branch
    }
    return y;
}

// 获取if语句的“可达后继”
Set<Stmt> getIfStmtReachableSuccs(If ifStmt, CFG<Stmt> cfg, DataflowResult<Stmt, CPFact> constants) {
    ConditionExp condition = ifStmt.getCondition();
    Var op1 = condition.getOperand1(), op2 = condition.getOperand2();
    Value v1 = constants.getInFact(ifStmt).get(op1), v2 = constants.getInFact(ifStmt).get(op2);
    if (v1.isConstant() && v2.isConstant()) {
        int c1 = v1.getConstant(), c2 = v2.getConstant(); // 条件表达式的两个操作数的（常量）值
        boolean isTrue = switch (condition.getOperator()) {
            case EQ -> c1 == c2;
            case NE -> c1 != c2;
            case LT -> c1 < c2;
            case GT -> c1 > c2;
            case LE -> c1 <= c2;
            case GE -> c1 >= c2;
        };
        for (Edge<Stmt> edge : cfg.getOutEdgesOf(ifStmt)) {
            // 条件值为常量true/false，只保留对应分支的后继
            if (isTrue && edge.getKind() == Edge.Kind.IF_TRUE) {
                return Set.of(edge.getTarget());
            }
            if (!isTrue && edge.getKind() == Edge.Kind.IF_FALSE) {
                return Set.of(edge.getTarget());
            }
        }
    }
    // 条件值不是常量，保留所有后继
    return cfg.getSuccsOf(ifStmt);
}

// 获取switch语句的“可达后继”
Set<Stmt> getSwitchStmtReachableSuccs(SwitchStmt switchStmt, CFG<Stmt> cfg, DataflowResult<Stmt, CPFact> constants) {
    Var condVar = switchStmt.getVar();
    Value v = constants.getInFact(switchStmt).get(condVar);
    if (v.isConstant()) {
        int c = v.getConstant(); // switch语句的条件（常量）值
        for (Edge<Stmt> edge : cfg.getOutEdgesOf(switchStmt)) {
            if (edge.getKind() == Edge.Kind.SWITCH_CASE) {
                int cv = edge.getCaseValue(); // case标签的值
                // 有一个case标签的值等于条件值，只保留对应分支的后继
                if (c == cv) {
                    return Set.of(edge.getTarget());
                }
            }
        }
        // 条件值为常量，但没有case标签的值等于条件值，只保留default分支的后继
        return Set.of(switchStmt.getDefaultTarget());
    }
    // 条件值不是常量，保留所有后继
    return cfg.getSuccsOf(switchStmt);
}

@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

    // 1.不可达代码
    Queue<Stmt> queue = new LinkedList<>();
    Set<Stmt> visited = new HashSet<>();
    Stmt entry = cfg.getEntry();
    queue.add(entry); // BFS遍历图
    while (!queue.isEmpty()) {
        Stmt stmt = queue.poll();
        visited.add(stmt);

        Set<Stmt> reachableSuccs;
        if (stmt instanceof If ifStmt) {
            // if语句的“可达后继”
            reachableSuccs = getIfStmtReachableSuccs(ifStmt, cfg, constants);
        } else if (stmt instanceof SwitchStmt switchStmt) {
            // switch语句的“可达后继”
            reachableSuccs = getSwitchStmtReachableSuccs(switchStmt, cfg, constants);
        } else {
            reachableSuccs = cfg.getSuccsOf(stmt);
        }

        for (Stmt succ : reachableSuccs) {
            if (!visited.contains(succ)) {
                queue.add(succ);
            }
        }
    }
    // 遍历一遍之后，可以找到所有控制流不可达和分支不可达的语句
    for (Stmt stmt : cfg) {
        if (cfg.isExit(stmt)) continue;
        if (!visited.contains(stmt)) {
            deadCode.add(stmt);
        }
    }

    // 2.无用赋值
    for (Stmt stmt : cfg) {
        /*
        见作业文档：
        AssignStmt和Invoke都是DefinitionStmt的子类，但方法调用可能含有很多副作用，
        因此对于像 x = m(); 这样的语句，即使x之后再也不会被用到（x是无用变量），
        这条语句也不会被认为是无用赋值。因此，本次作业中所有可能的无用赋值都只可能是AssignStmt的实例。
        */
        if (stmt instanceof AssignStmt assignStmt) {
            LValue lval = assignStmt.getLValue();
            RValue rval = assignStmt.getRValue();
            if (lval instanceof Var && !liveVars.getOutFact(stmt).contains((Var) lval) && hasNoSideEffect(rval)) {
                deadCode.add(stmt);
            }
        }
    }

    return deadCode;
}