題目鏈接：https://tai-e.pascal-lab.net/pa1.html

評(píng)測(cè)鏈接：https://oj.pascal-lab.net/problem

作業(yè)出品：南京大學(xué)《軟件分析》課程，譚添、李樾

實(shí)現(xiàn)活躍變量分析

• newInitialFact ：負(fù)責(zé)創(chuàng)建和初始化控制流圖中除了 Entry 和 Exit 之外的結(jié)點(diǎn)的 Data Flow Fact。

控制流圖中一個(gè)結(jié)點(diǎn)的 IN 和 OUT 分別對(duì)應(yīng)一個(gè) Data Flow Fact ，記錄當(dāng)前程序點(diǎn)時(shí)變量的狀態(tài)。

直接創(chuàng)建一個(gè)空的 CPFact 即可，方法體內(nèi)還沒有開始掃描。

@Override
public SetFact<Var> newInitialFact() {
    // TODO - finish me
    return new SetFact<>();
}

• newBoundaryFact ：負(fù)責(zé)創(chuàng)建和初始化虛擬結(jié)點(diǎn)的 Data Flow Fact。但是注意要把方法參數(shù)初始化為 NAC 。

@Override
public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {
    // TODO - finish me
    return new SetFact<>();
}

• meetInto ：負(fù)責(zé)處理 transfer function 之前可能遇到多個(gè) OUT 時(shí)的合并處理。

直接調(diào)用接口就行了。

@Override
public void meetInto(SetFact<Var> fact, SetFact<Var> target) {
    // TODO - finish me
    target.union(fact);
}

• transferNode ：負(fù)責(zé)實(shí)現(xiàn)控制流圖中結(jié)點(diǎn)的 transfer function 。如果 IN 改變，返回 true ；否則返回 false 。

@Override
public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {
    // TODO - finish me
    // IN = OUT \cup (use - def)
    Optional<LValue> def = stmt.getDef();
    List<RValue> uses = stmt.getUses();
    SetFact<Var> newSetFact = new SetFact<>();
    newSetFact.union(out);
    if (def.isPresent()) {
        LValue defValue = def.get();
        if (defValue instanceof Var) {
            newSetFact.remove((Var) defValue);
        }
    }
    for (RValue use : uses) {
        if (use instanceof Var) {
            newSetFact.add((Var) use);
        }
    }
    if (!in.equals(newSetFact)) {
        in.set(newSetFact);
        return true;
    }
    return false;
}

實(shí)現(xiàn)迭代求解器

• doSolveBackward ：完成 while 循環(huán)。

@Override
protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    // TODO - finish me

    boolean flag = true;
    while (flag) {
        flag = false;
        for (Node node : cfg) {
            if (cfg.isExit(node)) continue;
            Fact outFact = result.getOutFact(node);
            Fact inFact = result.getInFact(node);
            for (Node succs : cfg.getSuccsOf(node)) {
                Fact succsInFact = result.getInFact(succs);
                analysis.meetInto(succsInFact, outFact);
            }
            if (analysis.transferNode(node, inFact, outFact)) {
                flag = true;
            }
        }
    }
}

• initializeBackward ：實(shí)現(xiàn)算法前三行的初始化操作。

protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
    // TODO - finish me

    // Init Exit node
    result.setInFact(cfg.getExit(), analysis.newBoundaryFact(cfg));

    // Init other nodes
    for (Node node : cfg) {
        if (!cfg.isExit(node)) {
            result.setInFact(node, analysis.newInitialFact());
            result.setOutFact(node, analysis.newInitialFact());
        }
    }
}

評(píng)測(cè)結(jié)果