本页目录
【程序分析】知识汇总
参考资料
L1. Introduction
静态分析算法大多保证Soundness（允许误报），妥协Completeness
L2. Intermediate Representation
L3-L4. Data Flow Analysis - Applications
可达定义分析 Reaching Definitions Analysis
应用举例：如果在初始时视为所有变量均定义为undef，且该定义能到达某个变量被使用的点，则说明程序可能存在未定义的变量使用。
活跃变量分析 Live Variables Analysis
可用表达式分析 Available Expressions Analysis
应用举例：程序优化，在程序点处可以把表达式替换成上一次的计算结果，避免重复计算。
总结
Assignment 1 Tips
在活跃变量分析中，newInitialFact和newBoundaryFact都是空集，本次作业中用不到newBoundaryFact的参数cfg。
public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg)（在下一次常量分析作业中，就需要用到cfg来获取方法的参数，newBoundaryFact中要把参数初始化成NAC）
L5-L6. Data Flow Analysis - Foundations
关于对称性和反对称性：
若二元关系满足对称性：
若二元关系满足反对称性：（即除非相等，否则不能双向成立；例如小于等于关系）
对称性和反对称性并不是互斥的关系：例如相等关系同时满足对称性和反对称性。
关于全序关系和偏序关系：
全序关系：在偏序关系的基础上，要求任意两个元素都可以比较（）
例如，整数集上的小于等于关系是全序关系（任意两个整数都可以比较大小）；而集合的子集关系是偏序关系（两个集合可能互不包含）。
是格、但不是完全格的例子：整数集上的小于等于关系；考虑正整数子集，显然没有最小上界。
有限格一定是完全格，完全格不一定是有限格（例如区间内实数集上的小于等于关系）。
常量传播 Constant Propagation
Assignment 2 Tips
Worklist算法可以使用集合实现，因为同一个Node （或Basic Block）如果同时是多个Node （或Basic Block）的后继，则可能被重复添加多次。
while (Worklist is not empty)
...
if (old_OUT != OUT[B])
Add all successors of B to Worklist
具体写法为：
Set<Node> worklist = new HashSet<>();取出一个元素并从集合中删除：
while (!worklist.isEmpty()) {
Iterator<Node> it = worklist.iterator();
Node node = it.next();
it.remove();
// ...
}
Assignment 3 Tips
L7. Interprocedural Analysis
receiver object指的是在面向对象方法调用中，实际接收并执行该方法的对象实例：
obj.func()例子中obj就是receiver object。
关于Dispatch和Resolve：
对于以下代码：
A x = new B();
x.foo();
Dispatch(B, A.foo())用于模拟运行时的方法分派，传入的两个参数是receiver object的实际类型B和foo的部分方法签名（只需要method name + descriptor）。
注意由于多态允许x被赋值为其他子类C/D或类A本身，因此实际上静态分析时，不保证能够确定receiver object的实际类型。
Resolve(callsite of x.foo())用于静态的调用解析，根据receiver object x的声明类型A（不考虑等号右边）确定可能的目标方法集合。
当callsite是一个virtual call时，由于不确定x的实际类型，因此需要考虑A及其所有子类中是否有重写foo方法的情况。此时Resolve会在A的直接或间接子类上运行Dispatch。
Assignment 4 Tips
在过程内常量分析中，newBoundaryFact中要把参数初始化成NAC，因为方法被调用时，参数的值是不确定的，为了保证Soundness，只能视为NAC。在本次作业做更精细的过程间常量分析，因此不再需要对大部分方法的参数做特殊处理，只需要处理整个ICFG的入口方法（如main方法）。
private void initialize() {
// TODO - finish me
for (Node node : icfg) {
result.setInFact(node, analysis.newInitialFact());
result.setOutFact(node, analysis.newInitialFact());
}
icfg.entryMethods().forEach(method -> {
Node entry = icfg.getEntryOf(method);
result.setOutFact(entry, analysis.newBoundaryFact(entry));
});
}
（然而作业只考虑整数类型，main的String[] args参数不会被考虑，实测不对ICFG的入口方法做newBoundaryFact初始化也能过OJ）
过程内常量传播分析时，节点的是其所有前驱节点的的meet；过程间常量传播分析时，节点的是其所有前驱节点的先经过transferEdge，再meet；transferEdge主要是为了解决传参和返回的过程，对于过程内的普通边，transferEdge什么都不做。
transferEdge的框架已经实现好了，作业中需要分别实现不同的细分情况。
@Override
public Fact transferEdge(ICFGEdge<Node> edge, Fact out) {
if (edge instanceof NormalEdge) {
return transferNormalEdge((NormalEdge<Node>) edge, out);
} else if (edge instanceof CallToReturnEdge) {
return transferCallToReturnEdge((CallToReturnEdge<Node>) edge, out);
} else if (edge instanceof CallEdge) {
return transferCallEdge((CallEdge<Node>) edge, out);
} else {
return transferReturnEdge((ReturnEdge<Node>) edge, out);
}
}
对于call node，transferCallNode是恒等函数，不做任何处理。（参数会由transferCallEdge处理）
protected boolean transferCallNode(Stmt stmt, CPFact in, CPFact out) {
// TODO - finish me
return out.copyFrom(in);
}
transferCallEdge时，核心是对应实参和形参，实参可以这样获取：
Invoke invoke = (Invoke) edge.getSource();
List<Var> actualParams = invoke.getInvokeExp().getArgs();
形参可以这样获取：
JMethod callee = edge.getCallee();
List<Var> formalParams = callee.getIR().getParams();
整个transferCallEdge的实现：
@Override
protected CPFact transferCallEdge(CallEdge<Stmt> edge, CPFact callSiteOut) {
// TODO - finish me
// 实参
Invoke invoke = (Invoke) edge.getSource();
List<Var> actualParams = invoke.getInvokeExp().getArgs();
// 形参
JMethod callee = edge.getCallee();
List<Var> formalParams = callee.getIR().getParams();
assert actualParams.size() == formalParams.size();
CPFact result = newInitialFact();
for (int i = 0; i < actualParams.size(); i++) {
Var actual = actualParams.get(i);
Var formal = formalParams.get(i);
result.update(formal, callSiteOut.get(actual));
}
return result;
}
注意result是从newInitialFact开始添加，而不是基于callSiteOut。本地变量不需要流入被调用方法。（本地变量由call-to-return边处理）
transferReturnEdge时，edge.getReturnVars在有多个return语句时会返回多个returnVar，比如这种情况：
int foo(...) {
if (...) {
return x;
} else {
return y;
}
}
此时需要对这些返回值做meetValue。
L8. Pointer Analysis
Java中的指针：Local variable、Static field、Instance field、Array element