NJU静态分析 - Lab7 - Alias-Aware的过程间常量传播
分析
这次的实验非常有意思，实验文档并没有告诉我们该用什么算法、什么函数、什么数据结构去实现Alias-Aware的过程间常量传播，这一切都需要我们自己来设计。我想先从我们需要维护什么关系来入手，从设计数据结构开始，去逐步解决这一难题。
我们需要维护什么关系
这次新增的分析类型大体可分为两类：字段和数组，其中字段又可以分为实例字段和静态字段。由于静态字段可以看作没有别名的实例字段，因此可以归为一类一起讨论。
首先我们来看如何维护字段间的别名关系。首先我们需要知道什么情况下我们要用到（或者说读取）别名关系，最明显的是LoadField语句。在该类语句中，我们需要得到程序中所有与该语句等号右边的FieldAccess拥有别名关系的FieldAccess，且这些FieldAccess应当位于StoreField语句的等号左边。因此自然而然可以想到用一个Map去维护这一关系，且这个Map应当为MultiMap，因为一个LoadField语句中的FieldAccess可以拥有多个别名：
1
private final MultiMap<FieldAccess, FieldAccess> aliasFields;
其次我们也应当维护一个相反的关系，即从StoreField到LoadField的映射。因为我们希望字段的值在StoreField语句中有所更新时，所有与他有别名关系的FieldAccess所处在的LoadField语句应当被加入到WorkList中，符合WorkList求解算法:
1
private final MultiMap<Stmt, Stmt> storeToLoad;
而这又引出两个问题：在处理LoadField语句时我们需要搜索别名关系，因此我们就需要知道程序中已有的StoreField语句。而目前已有的接口中似乎找不到一个得到程序中所有StoreField语句的接口，于是我们也应当用一个Set去记录出现过的StoreField语句：
1
private final Set<StoreField> storeFields;
另一个问题是在LoadField语句中meet所有别名的值时，这些别名的值我们实际上无法在该语句InFact中找到，因为FieldAccess并不是Var的子类。于是我们需要维护一个与InFact类似的数据结构去记录FieldAccess的值：
1
private final Map<FieldAccess, Value> fieldValues;
对于数组来说，所需要维护的数据结构与字段大致相同，但由于数组索引的存在，我们还需要维护ArrayAccess到与之可能成为别名的ArrayAccess之间的关系。这是由于，并非所有base指针集有交集的ArrayAccess都可以拥有别名关系，他们的索引也需要满足一些关系（即实验文档中的表格）。而每当数组索引的值有更新时，我们希望找到所有与之可能拥有别名关系的ArrayAccess，再次确定是否具有别名关系。这样不用每一次有数组索引的值更新时，把所有的数组访问语句都放入到WorkList中。
于是维护数组所需的数据结构有：
1
2
3
4
5
6
7
8
9
private final Set<StoreArray> storeArrays;
private final MultiMap<ArrayAccess, ArrayAccess> aliasArrayAccess;
private final MultiMap<StoreArray, LoadArray> mayAliasArrayStmt;
private final Map<ArrayAccess, Value> arrayAccessValues;
private final Map<ArrayAccess, Value> arrayIndexValues;
我们应当使用什么算法
首先计算base的指针集是否有交集很简单，我们只需要去用指针分析的结果即可：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void aliasAnalysis(PointerAnalysisResult pta) {
// Get variable pairs that may alias
for (Var var1 : pta.getVars()) {
Set<Obj> pts1 = pta.getPointsToSet(var1);
for (Var var2 : pta.getVars()) {
Set<Obj> pts2 = pta.getPointsToSet(var2);
if (mayAlias(pts1, pts2)) {
alias.put(var1, var2);
alias.put(var2, var1);
}
}
}
}
private static boolean mayAlias(Set<Obj> pts1, Set<Obj> pts2) {
return pts1.stream().anyMatch(pts2::contains);
}
接下来需要解决的就是如何更改我们的WorkList求解算法去支持新增的规则。通过以上分析，我们可以看到对于字段来说，从StoreField到LoadField的关系与icfg中的边非常相似，实际上也正是如此。我们可以在开始WorkList求解算法前得到所有的字段别名关系，并将其作为一条有向边加入到icfg中。然后在transferNode中，每当遇到StoreField中的FieldAccess的值有更新时，返回true，这样就可以利用已有算法将其后继节点加入WorkList中。这样还有一个好处便是我们只需要维护一个数据结构：
1
private final Map<FieldAccess, Value> fieldValues;
然而这样的算法面对数组时会遇到一些问题：对于同一个StoreArray的ArrayAccess，我们不但需要维护与其拥有别名关系的ArrayAccess，还需要维护与其可能有别名关系的ArrayAccess，这是在icfg中加边无法解决的。当然，我们可以只维护mayAliasArrayStmt，每次都判断一下是否真的具有别名关系，从而在icfg中能够加边，但这样的效率似乎有点低下了。
于是作者选用更加暴力的手段：doSolve两遍，这样在第一遍时，我们得到了所有的别名关系（或者可能的别名关系），之后再进行一遍求解，这次求解便能得到所有正确结果。当然，作者有些偷懒了，第二遍求解时应该可以只加入所有load语句（并未进行验证），这样代价就会小很多。
算法设计
作者在编写算法时，借鉴了实验5和实验6的思路，使用了访问者模式去解决这个问题，对于所有语句，我们只需要调用他的accept函数即可：
1
2
3
4
@Override
public boolean transferNode(Stmt stmt, CPFact in, CPFact out) {
return stmt.accept(new StmtProcessor(in, out));
}
具体每个visitor该如何实现就不再展示了，由前面的分析也可以得到，大致是在store语句中更新变量值，在load语句中查找别名关系，更新fact。
踩过的坑
- 在计算
base的指针集是否有交集时，不需要考虑过多限制条件，不然可能过不了oj（作者也未弄清原因） AbstractInterDataflowAnalysis里是有一个InterSolver的指针的，在向WorkList中添加语句的时候可能会用到- 如果你也使用了访问者模式，不要忘了重写
visitDefault和visit(Unary)函数 - 静态字段和实例字段的处理可能要加以区分