值编号（Value Numbering）

值编号是一种简单的表达式优化技术，它通过在程序中识别出相同的表达式，然后将它们替换为同一个临时变量来消除冗余的计算。

这种技术的基本思想是，如果两个表达式的值相同，那么它们就可以用同一个临时变量来表示。例如，对于表达式a+b和c+d，如果a=c且b=d，那么这两个表达式的值就相同，可以用同一个临时变量来表示。这样我们通过对每个表达式都进行标号，就可以追踪每个表达式的值，从而消除冗余的计算。

值编号的基本做法

值编号技术主要基于以下两个核心原理：

1. 表达式等价性

   • 如果两个表达式在语义上等价，那么它们会产生相同的值
   • 等价性判断需要考虑操作符的交换律、结合律等代数性质
   • 例如：a+b 和 b+a 是等价的

2. 值映射表

   • 维护一个映射表，记录每个表达式的值编号
   • 对于每个新表达式，先查找是否已存在等价表达式
   • 如果存在，使用已有的值编号
   • 如果不存在，分配新的值编号

一个直观的例子

int compute(int a, int b) {
    int c = a + b;
    int f = b;
    int d = c * a;
    int b = 1;
    int e = a + b;
    int g = f + a;
    int h = a * g;
    return e - h;
}

我们仔细观察可以发现，表达式a+b出现了两次，但实际上计算的并不是同一个值，因为b的值在第二次计算时被修改了。 而因为f等于b，所以f+a等于b+a，所以a*g等于a*(b+a)，与之前的c*a为同一计算。

值编号技术就是为了将相同"值"的表达式用同一个临时变量来表示，从而避开符号相同但值不同的表达式。

让我们为每个表达式分配一个值编号：

语句	被赋值符号	表达式	值编号	说明
c = a + b	c: v3	a + b	v1 + v2	a为v1，b为v2
f = b	f: v2	b	v2	b仍为v2
d = c * a	d: v4	c * a	v3 * v1	c为v3，a为v1
b = 1	b: v5	1	v5	常量1
e = a + b	e: v6	a + b	v1 + v5	a仍为v1，新的b为v5
g = f + a	g: v3	f + a	v2 + v1	f为v2，a为v1，发现 v1 + v2 已经计算过
h = a * g	h: v4	a * g	v1 * v3	a为v1，g为v3，发现 v3 * v1 已经计算过
return e - h	-	e - h	v6 - v4	e为v6，h为v8

通过这个表格，我们可以清楚地看到：

1. 每个基本变量（如a、b）都有自己的值编号
2. 复合表达式（如a+b）的值编号由其组成部分的值编号组成
3. 当变量被重新赋值时（如b = 1），它获得新的值编号
4. 相同的表达式组合会产生相同的值编号表示
5. 每个被赋值的符号都获得一个新的值编号，除非它直接使用另一个变量的值编号

所以化简后的代码为：

int compute(int a, int b) {
    int c = a + b;
    int f = b;
    int d = c * a;
    int b = 1;
    int e = a + b;
    int g = c;  // 发现 c 已经计算过，直接使用
    int h = d;  // 发现 d 已经计算过，直接使用
    return e - d; // 之后 g 和 h 其实可以被死代码删除清理掉
}