软件分析实验笔记丨A7

作业目标

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

在本次作业中，我们需要在作业4的基础上，进一步提高常量传播的精度。具体而言，我们需要借助之前作业中实现的指针分析，根据指针分析结果来得到程序中的别名（alias）信息，并用这一信息来在过程间常量传播中更精确地处理对象字段（field）和数组（array）。

和作业4一样，常量传播中只需要考虑 int 类型的值，但在本次作业中，需要额外考虑程序中的别名，用别名信息来更精确地处理对字段和数组的存取。不过，可以忽略一些将在后续描述的情况。

Alias-Aware的常量传播

别名

别名用于描述以下情况：一个内存中的数据位置可以通过不同的符号名来访问，这些指向内存中的同一位置的不同符号互为别名。在 Java 中，对实例字段和数组的访问可以形成别名，举例来说，如果变量 x 和 y 指向相同的对象，那么 x.f 和 y.f 这两个字段访问构成了别名，因为它们实际上指向同一个字段；如果变量 a 和 b 指向同一个数组，并且 i 和 j 有相同的值，那么 a[i] 和 b[j] 这两个数组访问构成了别名，因为它们实际上指向同一个数组中的同一个位置。

在别名存在的情况下，通过对一个字段/数组的访问来修改一个实例字段/数组将会同时修改与这一访问相关的所有别名值。举例来说，如果 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 被访问。由于不需要考虑别名的存在，对静态字段的处理要比对实例字段和数组的处理简单。

分析实例字段

更精确地处理实例字段

在作业2和作业4中，我们对实例字段的 load 语句进行了保守的处理，即直接将 load 语句等号左侧的变量设置为 NAC：

x = a.f; // always set val(x) to NAC in previous assignments

在本次作业中，我们朝着精度更高的方向迈进了一步：当分析实例字段的 load 语句时（设该语句为 L），我们找到所有对这一实例字段（以及其别名）进行修改的 store 语句，并将这些语句要 store 的值 meet 之后赋给 L 等号左侧的变量，如下所示：

   y = 5;
   p.f = y; // p.f is an alias of a.f
   ...
L: x = a.f; // meet val(y) to val(x)

此时，若所有可能的 store 语句赋予该字段的值都为同一个常量（本例中为5），那么相比于之前保守的处理方法（认为 x = NAC），我们能得到一个更精确的结果（x = 5）。现在假设另一种情况：某个实例字段被多个 store 语句赋予了不同的值（例如 q.f = 6; 且 q.f 也是 a.f 的别名），或该实例字段被赋值为 NAC（例如 p.f = y; 且 y = NAC），那么为了保证分析 soundness，load 该实例字段的语句 L 等号左侧的变量也应当是 NAC (即 x = NAC)。

计算别名信息

在本次作业中，我们借助在之前的作业中实现的指针分析来计算程序的别名信息。具体而言，对任意两个实例字段的访问（设为 x.f 和 y.f），如果它们的 base 变量的指针集（points-to set）有交集（即 x 和 y 的指针集有交集），那么我们认为对这两个实例字段的访问（x.f 和 y.f）互为别名。

分析实例字段的精读取舍

我们上面描述的处理实例字段的方式忽略了 load 和 store 语句出现的顺序，也就是说，我们的处理是流不敏感的（flow-insensitive）。和其他流不敏感的分析一样，这种处理方式会损失一些精度，例如如下代码片段：

p = q = a;
p.f = 555;
x = a.f; // x -> NAC in the current handling
q.f = 666;

分析可以发现 p.f 和 q.f 都是 a.f 的别名，因此我们将所有 store 到 a.f 和其任意别名的值（即 555 和 666）进行 meet 之后赋给 load 语句 x = a.f 的左侧变量 x，从而结果得到 x 在第 3 行后为 NAC，这实际上是不精确的结果。

我们可以通过一些别的分析手段来获得比上面的处理方式更高的精度，例如采用流敏感的方式追踪所有的变量和 access path 的值（一个 access path 表示由一个变量和一系列的字段名构成的访问路径，例如 p.f 和 q.f.g ）。然而，这种处理方式需要对分析算法进行复杂的修改，因此我们在本次作业中选择上述更为简单直接的处理方式。

分析静态字段

对静态字段的处理比实例字段简单，因为不需要考虑静态字段的别名。当处理一个静态字段的 load 语句时（假设为 x = T.f;），只需要找到对同一个字段（T.f）的 store 语句，并将这些保存进字段的值进行 meet 后赋给 load 语句等号左侧的变量（x）。这一处理可以在没有指针分析和别名信息的情况下完成。

值得注意的是，静态字段的值可能来自于字段的初始化 field initializer 或类静态初始化块 static initializer ，例如下面代码片段中的第 2 行和第 7 行：

class A {
    static int one = 1; // field initializer
    static int two;
     
    static { // static initializer
        one = 1; // generated for field initializer at line 2
        two = 2;
    }
}

具体而言，第 2 行的静态字段初始化会被编译为一个静态初始化块（5 - 8 行）中的 store 语句（第 6 行），因此仅处理静态初始化块即可。然而，本次作业中的 call graph builder 并不处理静态初始化块（但在 Tai-e 中它们会被正确处理），因此这些 store 语句在 ICFG 上是不可达的。简单起见，我们在本次作业中忽略字段的初始化和静态初始化块。

分析数组

对数组的处理和对实例字段的处理类似。当分析一个数组的 load 语句如 x = a[i]; 时，我们需要找到所有修改 a[i] 别名的值的 store 语句，并将这些值 meet 后赋给 x。此处对数组的处理要更复杂一些：当判断两个对数组的访问 a[i] 和 b[j] 是否互为别名时，不仅需要考虑它们的 base 变量（a 和 b）的指针集是否有交集，还需要考虑索引值 i 和 j 的关系。有趣的是，由于数组索引也是 int 类型，因此可以用常量分析来实时计算 i 和 j 的关系。

假设 a 和 b 的指针集有交集，我们根据常量传播中 i 和 j 的结果来决定 a[i] 和 b[j] 是否互为别名。具体参照如下表格（该设计考虑了分析的单调性并确保了分析的 soundness）：

a[i] and b[j]	j = UNDEF	j = c₂	j = NAC
i = UNDEF	不互为别名	不互为别名	不互为别名
i = c₁	不互为别名	当且仅当 c₁ = c₂ 时互为别名	互为别名
i = NAC	不互为别名	互为别名	互为别名

对字段/数组初始化的说明

由于我们对于字段和数组的处理是流不敏感的，所以当分析 load 一个字段/数组的语句时，我们需要 meet 所有被 store 到该字段/数组的值。在 Java 中，和局部变量不同，字段（包括实例字段和静态字段）和数组即使没有被显式地初始化过也能被 load，这是因为 Java 会隐式地给 int 类型赋初始值为0。例如下面这一代码片段：

class A {
    int f; // f is implicitly initialized to 0 by default
}
...
A a = new A();
// a.f = 5;
int x = a.f;

即使对象 new A 的字段 f 没有被显式地初始化，它仍然能够在第 7 行被 load，并且 load 得到的结果为 0（Java 的隐式初始化）。

在这种隐式初始化存在的情况下，如果一个实例字段在程序中被赋予了一个非 0 常量（比如将上述代码片段中的第 6 行解除注释），我们就必须认为它的值为 NAC。这是将它的默认初始化值 0 和被赋予的值（上述代码片段中的值 5）进行 meet 后得到的，也就是说我们会在第 7 行得到 x = NAC。在这种情况下，会发现我们上面所描述的对字段和数组的处理都变得没有意义了：它会认为任何被 load 的值都是 NAC。

为了处理这一情况，我们为被分析程序设置一个合理的假设：假设所有程序中的字段和数组都在被 load 之前通过 store 语句显式地初始化了。在这一假设下，所有的 load 语句得到的值一定来自于程序中的 store 语句，因此我们可以忽略默认初始值0对 int 型字段和数组带来的影响。

实现

本次作业中，需要更加精确地处理实例字段、静态字段和数组。

为了使 InterConstantPropagation 类可用，需要首先完成 ConstantPropagation 类。可以将作业 2 中的实现复制到本作业中。类似地，需要完成 Solver（位于包 pascal.taie.analysis.pta.cs 中）和 _2ObjSelector（本作业的默认上下文 selector ）这两个类以进行上下文敏感的指针分析，其结果将被用来建立调用图（call graph）和计算别名信息。可以将作业 6 中的实现复制到本作业中。

提示：

InterConstantPropagation 的 initialize() 方法会在求解器启动前被调用，它包含了获取 PointerAnalysisResult 的相关代码，如果你的实现中需要进行一些初始化操作，你可以考虑在该方法中进行。
根据你的需要，你可以任意向 InterConstantPropagation 和 InterSolver 中添加 API 和字段。
InterConstantPropagation 在其字段中持有 InterSolver 的实例，因此你可以在 InterConstantPropagation 中调用 solver 的 API。

在本次作业中，我们需要实现在作业四中实现过的两个类的 API，即来自 pascal.taie.analysis.dataflow.inter.InterConstantPropagation 的六个 API：boolean transferCallNode(Stmt,CPFact,CPFact) 、boolean transferNonCallNode(Stmt,CPFact,CPFact) 、CPFact transferNormalEdge(NormalEdge,CPFact) 、CPFact transferCallToReturnEdge(CallToReturnEdge,CPFact) 、CPFact transferCallEdge(LocalEdge,CPFact) 、CPFact transferReturnEdge(LocalEdge,CPFact) 和来自 pascal.taie.analysis.dataflow.inter.InterSolver 的两个 API:void initialize() 、void doSolve() 。

其中主要改动的地方有：

InterConstantPropagation

导入部分：

import pascal.taie.World;
import pascal.taie.analysis.dataflow.analysis.constprop.CPFact;
import pascal.taie.analysis.dataflow.analysis.constprop.ConstantPropagation;
import pascal.taie.analysis.dataflow.analysis.constprop.Value;
import pascal.taie.analysis.graph.cfg.CFGBuilder;
import pascal.taie.analysis.graph.icfg.CallEdge;
import pascal.taie.analysis.graph.icfg.CallToReturnEdge;
import pascal.taie.analysis.graph.icfg.NormalEdge;
import pascal.taie.analysis.graph.icfg.ReturnEdge;
import pascal.taie.analysis.pta.PointerAnalysisResult;
import pascal.taie.analysis.pta.core.heap.Obj;
import pascal.taie.config.AnalysisConfig;
import pascal.taie.ir.IR;
import pascal.taie.ir.exp.*;
import pascal.taie.ir.stmt.*;
import pascal.taie.language.classes.JField;
import pascal.taie.language.classes.JMethod;
 
import java.util.*;
import java.util.stream.Stream;
 
import static pascal.taie.analysis.dataflow.analysis.constprop.ConstantPropagation.canHoldInt;

初始化修改的部分：

public static final String ID = "inter-constprop";
private final ConstantPropagation cp;
private final Map> alias;
private final Map> staticLoadFields;
private final Map> staticStoreFields;
public InterConstantPropagation(AnalysisConfig config) {
    super(config);
    cp = new ConstantPropagation(new AnalysisConfig(ConstantPropagation.ID));
    alias = new HashMap<>();
    staticStoreFields = new HashMap<>();
    staticLoadFields = new HashMap<>();
}
@Override
protected void initialize() {
    String ptaId = getOptions().getString("pta");
    PointerAnalysisResult pta = World.get().getResult(ptaId);
    // You can do initialization work here
    // 获取别名
    Collection vars = pta.getVars();
    for (Var x : vars) {
        alias.put(x, new HashSet<>() {{
            add(x);
        }});
        Set pointsToSet = pta.getPointsToSet(x);
        for (Var y : vars) {
            if (!x.equals(y)) {
                for (Obj obj : pta.getPointsToSet(y)){
                    if (pointsToSet.contains(obj)) {
                        alias.get(x).add(y);
                        break;
                    }
                }
            }
        }
    }
    // 获取静态字段语句
    for (Stmt stmt : icfg) {
        if (stmt instanceof StoreField storeField) {
            if (storeField.isStatic()) {
                JField field = storeField.getFieldRef().resolve();
                if (!staticStoreFields.containsKey(field)) {
                    staticStoreFields.put(field, new HashSet<>());
                }
                staticStoreFields.get(field).add(storeField);
            }
        } else if (stmt instanceof LoadField loadField) {
            if (loadField.isStatic()) {
                JField field = loadField.getFieldRef().resolve();
                if (!staticLoadFields.containsKey(field)) {
                    staticLoadFields.put(field, new HashSet<>());
                }
                staticLoadFields.get(field).add(loadField);
            }
        }
    }
}

修改的部分

protected boolean transferNonCallNode(Stmt stmt, CPFact in, CPFact out) {
    // TODO - finish me
    // 要考虑字段的修改
    boolean change = false;
    for(Var key : in.keySet()){
        change |= out.update(key, in.get(key));
    }
    // x.f = y
    if(stmt instanceof StoreField storeField){
        Var rVal = storeField.getRValue();
        if(canHoldInt(rVal)){
            JField field = storeField.getFieldRef().resolve();
            if(storeField.isStatic()){
                staticLoadFields.getOrDefault(field, new HashSet<>()).forEach(solver::add);
            }else{
                Var base = ((InstanceFieldAccess) storeField.getLValue()).getBase();
                for(Var x : alias.getOrDefault(base, new HashSet<>())){
                    x.getLoadFields()
                            .stream()
                            .filter(loadField -> field.equals(loadField.getFieldRef().resolve()))
                            .forEach(solver::add);
                }
            }
        }
        change = true;
    }else if(stmt instanceof LoadField loadField){    // y = x.f
        Var lVal = loadField.getLValue();
        if(canHoldInt(lVal)){
            Value res = Value.getUndef();
            JField field = loadField.getFieldRef().resolve();
            if(loadField.isStatic()){
                for(StoreField storeField : staticStoreFields.getOrDefault(field, new HashSet<>())){
                    CPFact inFact = solver.getInFact(storeField);
                    res = cp.meetValue(res, inFact.get(storeField.getRValue()));
                }
            }else{
                Var base = ((InstanceFieldAccess) loadField.getRValue()).getBase();
                for(Var x : alias.getOrDefault(base, new HashSet<>())){
                    for(StoreField storeField : x.getStoreFields()){
                        if(storeField.getFieldRef().resolve().equals(field)){
                            CPFact inFact = solver.getInFact(storeField);
                            res = cp.meetValue(res, inFact.get(storeField.getRValue()));
                        }
                    }
                }
            }
            change |= out.update(lVal, res);
        }
    }else if(stmt instanceof StoreArray storeArray){
        if(canHoldInt(storeArray.getRValue())){
            ArrayAccess access = storeArray.getArrayAccess();
            for(Var x : alias.getOrDefault(access.getBase(), new HashSet<>())){
                x.getLoadArrays().forEach(solver::add);
            }
        }
        change = true;
    }else if(stmt instanceof LoadArray loadArray){      // x = a[i]
        Var left = loadArray.getLValue();
        if(canHoldInt(left)){
            Value res = Value.getUndef();
            ArrayAccess access = loadArray.getArrayAccess();
            for(Var x : alias.getOrDefault(access.getBase(), new HashSet<>())){
                for(StoreArray storeArray : x.getStoreArrays()){
                    CPFact inFact = solver.getInFact(storeArray);
                    if(checkIndex(in.get(access.getIndex()), inFact.get(storeArray.getArrayAccess().getIndex()))){
                        res = cp.meetValue(res, inFact.get(storeArray.getRValue()));
                    }
                }
            }
            change |= out.update(left, res);
        }
    }else if(stmt instanceof DefinitionStmt def){
        LValue left = def.getLValue();
        if(left instanceof Var x){
            if(canHoldInt(x)){
                Value res = ConstantPropagation.evaluate(def.getRValue(), in);
                change |= out.update(x, res);
            }
        }
    }
    return change;
}

添加的部分（别名分析的计算）

private boolean checkIndex(Value x, Value y){
        if(x.isUndef() || y.isUndef()){
            return false;
        }
        if(x.isConstant() && y.isConstant()){
            return x.equals(y);
        }
        return true;
    }

InterSolver

添加的辅助函数

public Fact getInFact(Node node){
    return result.getInFact(node);
}
public void add(Node node){
    this.workList.add(node);
}