作业 2：常量传播和 Worklist 求解器

南京大学《软件分析》实验二

2025-09-29
SAST Assignments

文章大纲

作业2
要求为java实现常量传播算法,首先先回顾一下常量传播分析,也就是判断每个变量的值是否为常量,是标记为C,如果不是或者不确定标记为NAC;worklist求解器是迭代求解器的优化版本,不会重复计算那些已经得到最终结果(没有变动)的block

实现常量传播

要求

分析范围

在此次作业中，你需要实现针对 int 类型的常量传播。注意，在 Java 中，boolean、byte、char 和 short 类型在运行时实际上都以 int 值的形式进行表示和计算，因此你的分析算法也应当能处理这些类型。其他基本数据类型（例如 long、float 和 double）以及引用类型（例如 class types、array types）不在此次作业的考虑范围内，所以你可以在分析时忽略它们的值。

至于语句的处理，你只需要关注等号左侧为变量且右侧只能是如下几类表达式的赋值语句：

  • 常量，如 x = 1
  • 变量，如 x = y
  • 二元运算表达式，如 x = a + b 和 x = a >> b

下表列举出了除逻辑运算符以外所有作用在 int 类型上的二元运算符。请确保你的算法能正确处理它们：

运算类型 运算符
Arithmetic + - * / %
Condition == != < > <= >=
Shift << >> >>>
Bitwise | & ^
至于等号左侧为变量、等号右侧为其它表达式的赋值语句，例如方法调用（x = m(...)）和字段 load（x = o.f），你需要对它们进行保守的近似处理（也许会不够精确），即把它们当作 x = NAC。后续的作业将逐步解锁方法调用和字段访问的精确分析技巧。

对于上面没有提到的其它语句（例如字段存储 o.f = x），我们只需要使用恒等函数作为它们的 transfer 函数。在未来我们引入别名分析后，你就可以对字段存储进行精确处理了。

需要了解的类

1
2
3
4
5
pascal.taie.ir.IR
pascal.taie.ir.exp.Exp
pascal.taie.ir.exp.Var
pascal.taie.ir.exp.IntLiteral
pascal.taie.ir.exp.BinaryExp

先进到代码里一个个看看这些子类是负责什么功能的

pascal.taie.ir.IR

这个接口实现了对IR的一系列方法

  • getMethod() : 返回 JMethod 对象，表示当前IR对应的方法
  • getThis() : 返回表示this的 Var 对象，静态方法返回null
  • getParams() : 返回参数 Var 列表
  • getVars() : 返回所有变量的列表
  • getStmts() : 返回所有语句的列表
  • getExceptionEntries() : 返回异常处理表项列表

pascal.taie.ir.exp.Exp

这是IR中表示表达式的接口,可以获取表达式中的元素

  • getType() ：

  • 返回表达式的类型（Type对象）

  • 用于类型检查和分析

  • getUses() ：

  • 返回该表达式中使用的所有RValue表达式列表

  • 默认实现返回空列表

  • 子类可以重写此方法来提供实际使用的表达式

pascal.taie.ir.exp.Var

这是taie中表示变量的类,可以获取某个变量的信息,对于实现常量传播分析至关重要

  • 基本信息获取：
1
2
3
4
getMethod()  // 获取所属方法
getName()    // 获取变量名
getType()    // 获取变量类型
getIndex()   // 获取变量索引
  • 常量相关：
1
2
isTempConst()      // 检查是否是临时常量变量
getTempConstValue() // 获取临时常量值
  • 相关语句访问：
1
2
3
4
5
getLoadFields()   // 获取所有字段加载语句
getStoreFields()  // 获取所有字段存储语句
getLoadArrays()   // 获取所有数组加载语句
getStoreArrays()  // 获取所有数组存储语句
getInvokes()      // 获取所有方法调用语句

pascal.taie.ir.exp.IntLiteral

这是taie中便是证书字面量的一个实现类,

  • 静态工厂方法：
1
2
3
4
public static IntLiteral get(int value) {
    // 如果值在缓存范围内，返回缓存的实例
    // 否则创建新实例
}
  • 值访问：
1
2
3
public int getValue() {
    return value;
}
  • 类型获取：
1
2
3
4
@Override
public PrimitiveType getType() {
    return PrimitiveType.INT;
}

pascal.taie.ir.exp.BinaryExp

BinaryExp是Tai-e框架中表示二元表达式的接口,用于RValue的操作

getOperator() ：

  • 返回表达式的操作符（如+, -, *, /, <, > 等）
  • 返回类型为Op接口

getOperand1/2() ：

  • 返回第一/二个操作数
  • 返回类型为Var

任务 [重点!]

需要完成 ConstantPropagation 的下述 API：

  • CPFact newBoundaryFact(CFG)
  • CPFact newInitialFact()
  • void meetInto(CPFact,CPFact)
  • boolean transferNode(Stmt,CPFact,CPFact)

还需要实现下面两个辅助方法：

  • Value meetValue(Value,Value)
    该方法对应着格上的 meet 操作（⊓），见第 6 讲课件的第 238 页。你应当在 meetInto() 方法中调用它。

  • Value evaluate(Exp,CPFact)
    这个方法会计算表达式（Exp）的值（Value）。当然，此处的值是格上的抽象值。你需要参考第 6 讲课件的第 247 页上的内容来实现它的三种情况。对于其它情况，该方法会像我们在第 2.1 节提到的那样返回 NAC。你应该在 transferNode() 方法中调用它来进行表达式的求值。

CPFact newBoundaryFact(CFG)

作业提示:本次作业只关注 int 类型的常量传播。为了实现这一点，框架代码在 ConstantPropagation 类中提供了 canHoldInt(Var) 方法来判断一个变量能否储存 int 类型的值。你需要利用这个方法来判断一个变量是否在本次作业的分析范围内，并忽略那些不在范围内的变量（例如 float 类型的变量）。
那么在设置边界条件的时候,我们也用这个方法来过滤掉那些不用设置边界条件的变量
在ConstantPropagation.java中我们可以找到这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static boolean canHoldInt(Var var) {
	Type type = var.getType();
	if (type instanceof PrimitiveType) {
		switch ((PrimitiveType) type) {
			case BYTE:
			case SHORT:
			case INT:
			case CHAR:
			case BOOLEAN:
				return true;
		}
	}
	return false;
}

直接调用即可

1
2
3
4
5
6
7
8
9
10
@Override
public CPFact newBoundaryFact(CFG<Stmt> cfg) {
	CPFact cpf = new CPFact(); \\实例一个用于常量传播分析的cpf对象
		for (Var var : cfg.getIR().getParams()) { \\遍历每一个cfg中的节点的变量
		if (canHoldInt(var)) { \\如果他们是我们需要关注的变量
			cpf.update(var, Value.getNAC()); \\置为NAC
		}
	}
return cpf; \\返回创建好的常量传播分析对象
}

CPFact newInitialFact()

1
2
3
4
@Override
public CPFact newInitialFact() {
	return new CPFact();
}

meetInto()

1
2
3
4
5
6
@Override
public void meetInto(CPFact fact, CPFact target) {
	for(Var var: fact.keySet()){
		target.update(var, meetValue(fact.get(var), target.get(var)));
	}
}

写了半天才发现下面有个meetValue,可以吧具体规则解耦出来
meetValue按照课上讲的规则即可
NAC П V = NAC
UNDEF П v = v
c П с = с
C1 П C2 = NAC

meetValue(CPFact,CPFact)

实现课上讲的操作:

  • NAC⌈⌉v=NAC
  • UNDEF⌈⌉v=v
  • c⌈⌉v= ?
    • c⌈⌉c=c
    • c1⌈⌉c2=NAC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Value meetValue(Value v1, Value v2) {
// 1. 如果任一值是 NAC，结果是 NAC
	if (v1.isNAC() || v2.isNAC()) {
		return Value.getNAC();
	}
// 2. 如果 v1 是 UNDEF，返回 v2
	if (v1.isUndef()) {
		return v2;
	}
// 3. 如果 v2 是 UNDEF，返回 v1
	if (v2.isUndef()) {
		return v1;
	}
// 4. 两个都是常量的情况
	if (v1.getConstant() == v2.getConstant()) {
		return v1; // 相同常量，返回该常量
	} else {
		return Value.getNAC(); // 不同常量，返回 NAC
	}
}

transferNode(Stmt,CPFact,CPFact)


可以看到和之前的作业差不多,只不过操作的是x对应的值的定义
给定一个语句s:x=…我们将其转换函数定义为：
F:OUT[s]=gen ∪ (IN[s]−{(x,  ‾)})
下面来看如何针对三类不同的语句生成 gen：

s: x = c，则 gen = {(x, c)} gen={(x,c)}
s: x = y，则 gen = {(x, val(y))} gen={(x,val(y))}
s: x = y op z，则 gen = {(x, f(y, z))} gen={(x,f(y,z))}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Override
public boolean transferNode(Stmt stmt, CPFact in, CPFact out) {
// 1. 创建输入的副本
	CPFact tmpOut = in.copy();
// 2. 处理赋值语句
		if (stmt.getDef().isPresent()) {
			if ((stmt.getDef().get() instanceof Va) && canHoldInt((Var)stmt.getDef().get())) {
				Var var = (Var) stmt.getDef().get();
// 调用 evaluate 方法
				Value value = evaluate(((DefinitionStmt<Var, RValue>)stmt).getRValue(), in);
				tmpOut.update(var, value);
		}
	}
// 3. 检查是否有变化
	if (!tmpOut.equals(out)) {
// 4. 复制所有变量到输出
		for (Var var : tmpOut.keySet()) {
			out.update(var, tmpOut.get(var));
		}
		return true;
	}
	return false;
}

evaluate(Exp exp, CPFact in)

这个方法会计算表达式（Exp）的值（Value）。当然，此处的值是格上的抽象值。需要参考第 6 讲课件的第 247 页上的内容来实现它的三种情况。对于其它情况，该方法会像我们在第 2.1 节提到的那样返回 NAC。你应该在 transferNode() 方法中调用它来进行表达式的求值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
public static Value evaluate(Exp exp, CPFact in) {
    if (exp instanceof Var) {
        return in.get((Var) exp);
    }
    if (exp instanceof IntLiteral) {
        return Value.makeConstant(((IntLiteral) exp).getValue());
    }
    if (exp instanceof BinaryExp) {
        Value v1 = in.get(((BinaryExp) exp).getOperand1());
        Value v2 = in.get(((BinaryExp) exp).getOperand2());

//NAC的传播处理
        if (v1.isNAC() || v2.isNAC()) {
            if (exp instanceof ArithmeticExp) {
                // 处理除法和取模运算的除零错误(返回UNDEF)
                if (((ArithmeticExp) exp).getOperator() == ArithmeticExp.Op.DIV 
                    && v2.isConstant() && v2.getConstant() == 0) {
                    return Value.getUndef();
                }
                if (((ArithmeticExp) exp).getOperator() == ArithmeticExp.Op.REM 
                    && v2.isConstant() && v2.getConstant() == 0) {
                    return Value.getUndef();
                }
            }
            return Value.getNAC();//其余情况返回NAC
        }
//UNDEF传播处理
        if (v1.isUndef() || v2.isUndef()) {
            return Value.getUndef();
        }
        
//常量计算
        if (v1.isConstant() && v2.isConstant()) {
            if (exp instanceof ArithmeticExp) {
                // 再次检查除零（常量情况）
                if (((ArithmeticExp) exp).getOperator() == ArithmeticExp.Op.DIV 
                    && v2.getConstant() == 0) {
                    return Value.getUndef();
                }
                if (((ArithmeticExp) exp).getOperator() == ArithmeticExp.Op.REM 
                    && v2.getConstant() == 0) {
                    return Value.getUndef();
                }
                // 使用switch表达式处理各种算术运算
                return switch (((ArithmeticExp) exp).getOperator()) {
                    case ADD -> Value.makeConstant(v1.getConstant() + v2.getConstant());
                    case SUB -> Value.makeConstant(v1.getConstant() - v2.getConstant());
                    case MUL -> Value.makeConstant(v1.getConstant() * v2.getConstant());
                    case DIV -> Value.makeConstant(v1.getConstant() / v2.getConstant());
                    case REM -> Value.makeConstant(v1.getConstant() % v2.getConstant());
                };
            }
            if (exp instanceof ConditionExp) {
                // 条件表达式处理
                return switch (((ConditionExp) exp).getOperator()) {
                    case EQ -> Value.makeConstant(v1.getConstant() == v2.getConstant() ? 1 : 0);
                    case NE -> Value.makeConstant(v1.getConstant() != v2.getConstant() ? 1 : 0);
                    case GE -> Value.makeConstant(v1.getConstant() >= v2.getConstant() ? 1 : 0);
                    case GT -> Value.makeConstant(v1.getConstant() > v2.getConstant() ? 1 : 0);
                    case LE -> Value.makeConstant(v1.getConstant() <= v2.getConstant() ? 1 : 0);
                    case LT -> Value.makeConstant(v1.getConstant() < v2.getConstant() ? 1 : 0);
                };
            }
            if (exp instanceof ShiftExp) {
                // 位移表达式处理
                return switch (((ShiftExp) exp).getOperator()) {
                    case SHL -> Value.makeConstant(v1.getConstant() << v2.getConstant());
                    case SHR -> Value.makeConstant(v1.getConstant() >> v2.getConstant());
                    case USHR -> Value.makeConstant(v1.getConstant() >>> v2.getConstant());
                };
            }
            if (exp instanceof BitwiseExp) {
                // 位运算表达式处理
                return switch (((BitwiseExp) exp).getOperator()) {
                    case OR -> Value.makeConstant(v1.getConstant() | v2.getConstant());
                    case AND -> Value.makeConstant(v1.getConstant() & v2.getConstant());
                    case XOR -> Value.makeConstant(v1.getConstant() ^ v2.getConstant());
                };
            }
        }
        //默认返回值
        return Value.getNAC();
    }
    //默认返回值
    return Value.getNAC();
}

实现Worklist求解器

  • pascal.taie.analysis.dataflow.solver.WorkListSolver

    该类继承了 Solver 类，实现了 worklist 算法。它的实现是不完整的，在本作业中需要完成它

任务[重点!]

Solver.initializeForward(CFG,DataflowResult)

1
2
3
4
5
6
7
8
9
10
11
12
13
protected void initializeForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
	for (Node node : cfg.getNodes()) {
		if (cfg.isEntry(node)) {
		// 入口节点：IN设置为边界条件，OUT设置为初始事实
			result.setInFact(node, analysis.newBoundaryFact(cfg));
			result.setOutFact(node, analysis.newInitialFact());
		} else {
		// 其他节点：IN和OUT都设置为初始事实
			result.setInFact(node, analysis.newInitialFact());
			result.setOutFact(node, analysis.newInitialFact());
		}
	}
}

WorkListSolver.doSolveForward(CFG,DataflowResult)


按照课上的伪代码实现即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
protected void doSolveForward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
	ArrayList<Node> nodeArrayList = new ArrayList<Node>();
	for (Node node: cfg.getNodes()) {
		if (cfg.isEntry(node)) {
			continue;
			}
		nodeArrayList.add(node);
		}
	nodeArrayList.add(node);
	while(!nodeArrayList.isEmpty()) {
		Node node = nodeArrayList.remove(0);
		for (Node p: cfg.getPredsOf(node)) {
			analysis.meetInto(result.getOutFact(p), result.getInFact(node));
		}
		boolean changed = analyss.transferNode(node, result.getInFact(node), result.getOutFact(node));
		if (changed) {
			nodeArrayList.addAll(cfg.getSuccsOf(node));
		}
	}
}

测试

然后运行测试./gradlew run --args="-cp src/test/resources/dataflow/constprop -m SimpleBranch"

1
2
3
4
5
6
7
8
9
10
11
class SimpleBranch {
	static void NAC(int p) {
		int x;
		if (p > 0) {
			x = 1;
		} else {
			x = 2;
		}
		int y = x;
	}
}

输出

1
2
3
4
5
6
7
8
9
10
11
[0@L5] %intconst0 = 0; {%intconst0=0}
[1@L5] if (p > %intconst0) goto 3; {%intconst0=0}
[2@L5] goto 6; {%intconst0=0}
[3@L5] nop; {%intconst0=0}
[4@L6] x = 1; {%intconst0=0, x=1}
[5@L5] goto 8; {%intconst0=0, x=1}
[6@L5] nop; {%intconst0=0}
[7@L8] x = 2; {%intconst0=0, x=2}
[8@L8] nop; {%intconst0=0, x=NAC}
[9@L10] y = x; {%intconst0=0, x=NAC, y=NAC}
[10@L10] return; {%intconst0=0, x=NAC, y=NAC}

可以看到已经能进行常量传播分析了


也可以打断点看一下Worklist求解器是如何高效迭代的