StaticProgramAnalysis

A1：活跃变量分析和迭代求解器

CFG<Node>是一种图类型，Node包含了BB的语句，Fact包含是bitVector，其中DataflowResult<Node, Fact> 是一个LinkedHashMap，键是Node值是Fact。

pascal.taie.analysis.dataflow.analysis.LiveVariableAnalysis

/**  
 * Implementation of classic live variable analysis. 
 */
 public class LiveVariableAnalysis extends  
        AbstractDataflowAnalysis<Stmt, SetFact<Var>> {  
  
    public static final String ID = "livevar";  
  
    public LiveVariableAnalysis(AnalysisConfig config) {  
        super(config);  
    }  
  
    @Override  
    public boolean isForward() {  
        return false;  
    }  
  
    @Override  
    public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {  
        // TODO - finish me  
        return new SetFact<Var>();  
    }  
  
    @Override  
    public SetFact<Var> newInitialFact() {  
        // TODO - finish me  
        return new SetFact<Var>();  
    }  
  
    @Override  
    public void meetInto(SetFact<Var> fact, SetFact<Var> target) {  
        // TODO - finish me  
        target.union(fact);  
    }  
  
    @Override  
    public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {  
        // TODO - finish me  
        // 获取语句左值中的定义，最多为一个  
        Optional<LValue> def = stmt.getDef();  
        // 获取语句中的右值，右值可能有多个，使用List存起来  
        List<RValue> uses = stmt.getUses();  
        // 定义算法中的IN[]  
        SetFact<Var> newSetFact = new SetFact<>();  
        // 将OUT[]中的值union到IN[]  
        newSetFact.union(out);  
        if(def.isPresent()) {
            // 如果左值是一个变量 
            if(def.get() instanceof Var) {  
                // 那么就在IN[]中kill掉  
                newSetFact.remove((Var) def.get());  
            }  
        }  
        // 遍历右值中的每一个元素  
        for (RValue use : uses) {  
            // 如果它是一个变量  
            if (use instanceof Var) {  
                // 那么就Gen一个对应的  
                newSetFact.add((Var) use);  
            }  
        }  
        // 如果本次的IN[]和经历过Gen&Kill过后的IN[]不一样  
        if (!in.equals(newSetFact)) {  
            // 那么就更新IN[]  
            in.set(newSetFact);  
            return true;  
        }  
        return false;  
    }  
}

pascal.taie.analysis.dataflow.solver.Slover#initializeBackward

protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {  
    // TODO - finish me  
    // step1 将 exit节点的InFact置为空集  
    result.setInFact(cfg.getExit(), analysis.newBoundaryFact(cfg));  
    // step2 将 除了exit节点之外的其他节点的InFact和OutFact置为空集  
    for (Node node : cfg.getNodes()) {  
        if (cfg.isExit(node)) continue;  
        result.setInFact(node, analysis.newInitialFact());  
        // 将OutFact也置为空集  
        result.setOutFact(node, analysis.newInitialFact());  
    }  
  
}

pascal.taie.analysis.dataflow.solver.IterativeSolver#doSolveBackward

@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;  // 出口节点不需要特殊处理  
            // 获取当前节点的 OUT 和 IN            
            Fact outFact = result.getOutFact(node);  
            Fact inFact = result.getInFact(node);  
            // 对于每个节点，调用函数 meetInto 和 transferNode (DataflowAnalysis 中)  
            for (Node succs : cfg.getSuccsOf(node)) {  
                // DataflowResult是存储着Node-Fact表，这里通过Node得到对应的Fact  
                Fact succsInFact = result.getInFact(succs);  
                // meet操作  
                analysis.meetInto(succsInFact, outFact);  
            }  
            if (analysis.transferNode(node, inFact, outFact)) {  
                flag = true;  
            }  
        }  
    }  
}

A2：常量传播和 Worklist 求解器

2024-12-08 17:24:40 (GMT+08:00)	ERROR	analysis has "Exception" on [hidden] testcase(s)
Analyze 53 methods, pass 51 methods
There are 485 Stmts in all test cases
Your submission correctly analyzes 476 Stmts


[!] Failed on [hidden] testcase(s)
Tips: we will not give you any information about [hidden] testcase(s)