题目链接:https://tai-e.pascal-lab.net/pa1.html
评测链接:https://oj.pascal-lab.net/problem
作业出品:南京大学《软件分析》课程,谭添、李樾
newInitialFact
:负责创建和初始化控制流图中除了 Entry
和 Exit
之外的结点的 Data Flow Fact
。控制流图中一个结点的 IN
和 OUT
分别对应一个 Data Flow Fact
,记录当前程序点时变量的状态。
直接创建一个空的 CPFact
即可,方法体内还没有开始扫描。
@Override public SetFact<Var> newInitialFact() { // TODO - finish me return new SetFact<>(); }
newBoundaryFact
:负责创建和初始化虚拟结点的 Data Flow Fact
。但是注意要把方法参数初始化为 NAC
。@Override public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) { // TODO - finish me return new SetFact<>(); }
meetInto
:负责处理 transfer function
之前可能遇到多个 OUT
时的合并处理。直接调用接口就行了。
@Override public void meetInto(SetFact<Var> fact, SetFact<Var> target) { // TODO - finish me target.union(fact); }
transferNode
:负责实现控制流图中结点的 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; }
doSolveBackward
:完成 while 循环。@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
:实现算法前三行的初始化操作。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()); } } }