1 实验内容

• 为 Java 实现一个 alias-aware 的过程间常量传播分析

2 实验概览

在 Java 中，对实例字段和数组的访问可以形成别名，举例来说，如果变量 x 和 y 指向相同的对象，那么 x.f 和 y.f 这两个字段访问构成了别名，因为它们实际上指向同一个字段。

在别名存在的情况下，通过对一个字段/数组的访问来修改一个实例字段/数组将会同时修改与这一访问相关的所有别名值。举例来说，如果 x.f，y.f 和 z.f 互为别名，那么 store 语句 x.f = 5; 不仅将 x.f 的值修改为 5，而且同时将 y.f 和 z.f 的值设为 5。因此，为了在常量传播中精确地分析字段和数组的值，我们需要取得被分析程序的别名信息。

值得注意的是，Java 中的静态字段不能拥有别名：对一个静态字段 T.f，它有唯一的符号名（即 T.f），且只能通过 T.f 被访问。

3 实验过程重点

在没有引入指针分析之前，过程间常量传播主要的问题在于 evaluate 函数能处理的 Exp 种类太少：

public static Value evaluate(Exp exp, CPFact in) {
    if (exp instanceof IntLiteral intLiteral) { ... }
    if (exp instanceof Var var) { ... }
    if (exp instanceof BinaryExp binaryExp) { ... }
    return Value.getNAC();
}

它处理不了对象字段（T.f = x 和 o.f = x）和数组（a[..]），所以一个很自然的想法就是在 evaluate 里添加对这两个对象的处理。

但是由于这个方法在 ConstantPropagation.java 中，而分析这二者需要借助 InterConstantPropagation.java 中指针分析的结果，并且根据提示，我应该不用修改 ConstantPropagation.java 里面的 API ：

如果你的提交包含该文件，则我们将会用你提交的 ConstantPropagation.java 来进行测试并评分，否则我们使用我们自己的该类来运行测试。

所以最好的方法是另起炉灶，在 InterConstantPropagation.java 中再实现一个 evaluate 函数：

public static Value evaluate(Exp exp, CPFact in) {
    if (exp instanceof IntLiteral intLiteral) { ... }
    if (exp instanceof Var var) { ... }
    if (exp instanceof BinaryExp binaryExp) { ... }
    if (exp instanceof StaticFieldAccess staticFieldAccess) { ... }
    if (exp instanceof InstanceFieldAccess instanceFieldAccess) { ... }
    if (exp instanceof ArrayAccess arrayAccess) { ... }
    return Value.getNAC();
}

但是这样貌似样板代码就有些太多了，更何况有些情况(比如BinaryExp)可能涉及 if 嵌套，所以可以考虑使用访问者模式，正巧 Tai-e 提供了 Exp 对应的访问者 ExpVisitor ：

public interface ExpVisitor<T> {
    default T visit(Var var) {
        return (T)this.visitDefault(var);
    }
    ...
}

于是我们可以考虑实现一个 Evaluator :

public class Evaluator implements ExpVisitor<Value> {
    private final CPFact in;
    public Evaluator(CPFact in) {
        this.in = in;
    }
    @Override
    public Value visit(IntLiteral literal) {...}
    ...
}

A6 Bug

在完成 A6 的时候有一点我没发现，就是这个 callgragh 是在实现指针分析的时候 “顺手” 构造的。

换句话说，即使在指针分析中构造的 callgragh 是错的，甚至不去构造 callgragh ，也可以得到正确的指针分析结果。

而 A6 的测试并不会去测我构造的 callgragh 是否正确，这就导致了我没意识到我的 callgraph 的构造其实是错的。

但是这次的 A7 需要用到这个 callgraph ，于是就出现了非常诡异的一幕：一个静态方法明明已经被标记为是 reachable，但是 callgraph 上却没有对应的 call edge。

transferNonCallNode 实现问题

在一开始实现 transferNonCallNode 的时候，我并没有处理 o.f = x, T.f = x, a[..] = x 这三类语句。

换句话说，当我在处理这些语句的时候，transferNonCallNode 是个恒等函数。

原因很简单：

1. 这些语句的左值不是 Var 及其子类，无法被 CPFact 记录（本质 Pair<Var, Value>）
2. 记录了也没用，由于别名的存在，记录单个别名的 Value 的变化并没什么用

但是这样做会有一些问题，先来看原先的常量传播算法;

不难看出，每当有一个节点的 out fact 变化，那它的后继节点便会被加入 worklist 继续处理。

但是由于我在处理上面三种语句的时候什么也没做，所以这个算法并不能 “感知” 到在这过程中发生了什么变化，也就是不能像之前一样将这个变化信息 “传导” 到后继节点。

所以解决方法也简单，在处理上面三种语句的时候找到所有别名的load语句，并将其加入 worklist 。