题目链接:https://tai-e.pascal-lab.net/pa2.html
评测链接:https://oj.pascal-lab.net/problem
作业出品:南京大学《软件分析》课程,谭添、李樾
实验进行之前,要对项目中类和方法充分理解,找到每个类所对应的代码分析领域中的部分。
类 | 含义 |
---|---|
CFG |
一个方法的控制流图。 |
IR |
一个非抽象方法的方法体的中间表示,其中包含方法签名的参数(parameters )、方法体中的变量(variables )和方法体中的所有中间表示语句(Stmts )。这里需要注意一点,一个方法体的中间表示由多个中间表示语句(Stmts )组成。 |
Stmt |
一条中间表示语句。 |
Exp |
表达式的中间表示。要注意,表达式不是语句。 |
CPFact |
建立变量 Var 到格上的值 Value 之间的映射,代表 Data Flow Fact (IN ,OUT )。一个程序点(program point )对应一个 CPFact 。 |
DataflowResult |
包含控制流图中的所有 Data Flow Fact 。 |
算法伪代码描述:
newBoundaryFact
:负责创建和初始化虚拟结点的 Data Flow Fact
。但是注意要把方法参数初始化为 NAC
。原因是为了 safe-approximation
,我们不知道通过形参传递过来的参数是否是常量,所以为了安全,假设所有参数都是 NAC
,当然这样会导致精度损失问题,后面通过过程间分析可以有效解决这个问题。
根据题目要求,不是所有类型的参数都考虑,只有能转换成 int
类型的参数才考虑,所以别忘了用 canHoldInt
过滤一下。
@Override public CPFact newBoundaryFact(CFG<Stmt> cfg) { // TODO - finish me CPFact cpFact = new CPFact(); for (Var param : cfg.getIR().getParams()) { if (canHoldInt(param)) { // 只考虑可转换int类型的参数 cpFact.update(param, Value.getNAC()); // 建立参数到格上值(NAC)的映射 } } return cpFact; }
newInitialFact
:负责创建和初始化控制流图中除了 Entry
和 Exit
之外的结点的 Data Flow Fact
。控制流图中一个结点的 IN
和 OUT
分别对应一个 Data Flow Fact
,记录当前程序点时变量的状态。
直接创建一个空的 CPFact
即可,方法体内还没有开始扫描。
@Override public CPFact newInitialFact() { // TODO - finish me return new CPFact(); }
meetInto
:负责处理 transfer function
之前可能遇到多个 OUT
时的合并处理。具体的合并操作通过调用 meetValue
来处理。
@Override public void meetInto(CPFact fact, CPFact target) { // TODO - finish me for (Var var : fact.keySet()) { Value v1 = fact.get(var); Value v2 = target.get(var); target.update(var, meetValue(v1, v2)); } }
meetValue
:负责对格上的值进行合并。分三种情况实现即可。
/** * Meets two Values. */ public Value meetValue(Value v1, Value v2) { // TODO - finish me if (v1.isNAC() || v2.isNAC()) { return Value.getNAC(); } else if (v1.isUndef()) { return v2; } else if (v2.isUndef()) { return v1; } else if (v1.isConstant() && v2.isConstant()) { if (v1.getConstant() == v2.getConstant()) { return v1; } else { return Value.getNAC(); } } else { return Value.getNAC(); } }
transferNode
:负责实现控制流图中结点的 transfer function
。如果 OUT
改变,返回 true
;否则返回 false
。stmt
表示结点中的一条中间表示,一个结点只有一个中间表示。
题目要求只需要对赋值语句处理,所以用 DefinitionStmt
类型过滤。
对于所有赋值语句,只考虑具有左值,并且左值是变量且类型可以转换成 int
的语句。这些语句的右值是一个表达式,可能是常量,也能是变量、二元表达式。这个右值表达式的值将通过 evaluate
函数计算。
对于其他类型的语句,不做处理,out
直接复制 in
即可,相当于经过一个恒等函数。
@Override public boolean transferNode(Stmt stmt, CPFact in, CPFact out) { // TODO - finish me CPFact copy = in.copy(); // 复制in给copy,避免影响in。 if (stmt instanceof DefinitionStmt) { // 只处理赋值语句 if (stmt.getDef().isPresent()) { // 如果左值存在 LValue lValue = stmt.getDef().get(); // 获取左值 if ((lValue instanceof Var) && canHoldInt((Var) lValue)) { // 对于符合条件的左值 copy.update((Var) lValue, evaluate(((DefinitionStmt<?, ?>) stmt).getRValue(), copy)); // 计算右值表达式的值用来更新左值变量在格上的值 } } } return out.copyFrom(copy); // copy复制给out。copy和in相比,有更新,返回true;反之返回false }
evaluate
:负责表达式值的计算。表达式分三种情况讨论
有几个易错点,容易卡评测:
NAC / 0 = Undef
:这个点没有明确在题目中说明,但确实存在,需要单独处理。NAF
:不仅仅说上面三种类型之外的表达式,二元运算中有可能还有别的类型的运算,也需要返回 NAF
。/** * Evaluates the {@link Value} of given expression. * * @param exp the expression to be evaluated * @param in IN fact of the statement * @return the resulting {@link Value} */ public static Value evaluate(Exp exp, CPFact in) { // TODO - finish me if (exp instanceof Var) { // 变量 return in.get((Var) exp); } else if (exp instanceof IntLiteral) { // 常量 return Value.makeConstant(((IntLiteral) exp).getValue()); } else if (exp instanceof BinaryExp) { // 二元运算 Value v1 = in.get(((BinaryExp) exp).getOperand1()); // 获取运算分量在格上的值 Value v2 = in.get(((BinaryExp) exp).getOperand2()); if (v1.isNAC() || v2.isNAC()) { // 易错点1:NAC / 0 = Undef if (v1.isNAC() && v2.isConstant() && exp instanceof ArithmeticExp) { ArithmeticExp.Op operator = ((ArithmeticExp) exp).getOperator(); if (operator == ArithmeticExp.Op.DIV || operator == ArithmeticExp.Op.REM) { if (v2.getConstant() == 0) return Value.getUndef(); } } return Value.getNAC(); } if (v1.isUndef() || v2.isUndef()) { return Value.getUndef(); } if (exp instanceof ArithmeticExp) { ArithmeticExp.Op operator = ((ArithmeticExp) exp).getOperator(); switch (operator) { case ADD -> { return Value.makeConstant(v1.getConstant() + v2.getConstant()); } case DIV -> { if (v2.getConstant() == 0) return Value.getUndef(); return Value.makeConstant(v1.getConstant() / v2.getConstant()); } case MUL -> { return Value.makeConstant(v1.getConstant() * v2.getConstant()); } case SUB -> { return Value.makeConstant(v1.getConstant() - v2.getConstant()); } case REM -> { if (v2.getConstant() == 0) return Value.getUndef(); return Value.makeConstant(v1.getConstant() % v2.getConstant()); } } } else if (exp instanceof ConditionExp) { ConditionExp.Op operator = ((ConditionExp) exp).getOperator(); switch (operator) { case EQ -> { if (v1.getConstant() == v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } case GE -> { if (v1.getConstant() >= v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } case GT -> { if (v1.getConstant() > v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } case LE -> { if (v1.getConstant() <= v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } case LT -> { if (v1.getConstant() < v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } case NE -> { if (v1.getConstant() != v2.getConstant()) return Value.makeConstant(1); else return Value.makeConstant(0); } } } else if (exp instanceof BitwiseExp) { BitwiseExp.Op operator = ((BitwiseExp) exp).getOperator(); switch (operator) { case OR -> { return Value.makeConstant(v1.getConstant() | v2.getConstant()); } case AND -> { return Value.makeConstant(v1.getConstant() & v2.getConstant()); } case XOR -> { return Value.makeConstant(v1.getConstant() ^ v2.getConstant()); } } } else if (exp instanceof ShiftExp) { ShiftExp.Op operator = ((ShiftExp) exp).getOperator(); switch (operator) { case SHL -> { return Value.makeConstant(v1.getConstant() << v2.getConstant()); } case SHR -> { return Value.makeConstant(v1.getConstant() >> v2.getConstant()); } case USHR -> { return Value.makeConstant(v1.getConstant() >>> v2.getConstant()); } } } else { // 易错点2:二元表达式中的其他类型表达式 return Value.getNAC(); } } return Value.getNAC(); }
算法伪代码描述:
initializeForward
:初始化所有的 Data Flow Fact
。注意虚拟节点 Entry
的 OUT
别忘了protected void initializeForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) { // TODO - finish me result.setOutFact(cfg.getEntry(), analysis.newBoundaryFact(cfg)); for (Node node : cfg) { if (cfg.isEntry(node)) continue; result.setInFact(node, analysis.newInitialFact()); result.setOutFact(node, analysis.newInitialFact()); } }
doSolveForward
:负责实现 Worklist 求解器具体步骤。@Override protected void doSolveForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) { // TODO - finish me ArrayDeque<Node> worklist = new ArrayDeque<>(); // 双端堆栈当队列用 for (Node node : cfg) { // 添加所有结点到队列中 if (cfg.isEntry(node)) { continue; } worklist.addLast(node); } while (!worklist.isEmpty()) { Node node = worklist.pollFirst(); // 弹出队头结点 for (Node pred : cfg.getPredsOf(node)) { // 对该结点以及所有前驱结点的OUT做meet analysis.meetInto(result.getOutFact(pred), result.getInFact(node)); } boolean f = analysis.transferNode(node, result.getInFact(node), result.getOutFact(node)); if (f) { // 如果该节点OUT发生了变化,将其所有后继节点添加到队列 for (Node succ : cfg.getSuccsOf(node)) { worklist.addLast(succ); } } }