编译原理与实践：删除公共子表达式

如果一个表达式E之前已经计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式。对于公共子表达式，我们可以避免对其重复计算，这种优化技术称为删除公共子表达式，或称为删除多余计算。

就例8.2中的语句（7）和（11）来说，（7）中计算了R+r的值，而（11）中又重复计算了该表达式的值，因此，可以把（11）中的T4：=R+r改写为T4：=T2。类似地，可以把（10）中的T3：=2*T0改写为T3：=T1。于是，修改后的基本块L3为：

(5)T0:=3.14 (10)T3:=T1

(6)T1:=2*T0 (11)T4:=T2

(7)T2:=R+r (12)T5:=T3*T4

(8)A:=T1*T2 (13)T6:=R-r

(9)B:=A (14)B:=T5*T6

从代码实现的角度来说，为了能够删除基本块中的公共子表达式，需要记录那些至今已被计算过，而且从此以后其操作数并未发生改变的基本块中的表达式。采用五元组的形式来记录这些表达式，并称该五元组的集合为表达式集合，定义如下：

＜no,operand1,operator,opreand2,tmp＞

其中，no表示表达式在基本块中被计算时所在语句的编号，operand1是表达式的第1个操作数，operator为操作符，operand2则是表达式的第2个操作数，tmp为临时变量。

我们从基本块的开始依次扫描各语句，并向表达式集合中添加或者删除一些项，同时插入将表达式的值保存至一个新的临时变量的语句，并对相应的语句做修改。具体算法为：

①对于每一条语句i，首先判断其是否为一个表达式，若是，则转②；否则，判断下一条语句i+1。

②将语句i的操作数和操作符与表达式集合中的五元组相比较，若匹配，则检查其tmp是否为空，若为空则创建一个新的临时变量tmpi以替代空白，同时在该五元组所在的编号为no的语句之前插入tmpi：=operand1 operator opreand2语句，并用tmpi替代语句i及编号为no的语句中的表达式；若匹配成功的同时，检查发现tmp=tmpj，且不为空，则用tmpj替代语句i中的表达式。

③如果语句i中表达式的值被存放在一个结果变量中，检查此结果变量是否作为操作数出现在表达式集合中的五元组内。若出现，则删除表达式集合中的此五元组。之所以这样做，是因为即使有相同的表达式重复出现，但是表达式中操作数的值发生了变化，也不能视其为公共子表达式。

按照这一算法，使用如下的代码对其进行描述：

依据上述算法，我们再次考虑例8.2中基本块L3的最初代码。开始时，表达式集合为空，且i=1。

(5)1 T0:=3.14 (10)6 T3:=2*T0

(6)2 T1:=2*T0 (11)7 T4:=R+r

(7)3 T2:=R+r (12)8 T5:=T3*T4

(8)4 A:=T1*T2 (13)9 T6:=R-r

(9)5 B:=A(14)10 B:=T5*T6

由于L3的首条语句T0：=3.14赋值号右侧不是表达式，因此考虑下一条语句T1：=2*T0，其中含有二元表达式，且表达式集合为空。于是，将五元组＜2，2，*，T0，nil＞加入表达式集合中。同样，在处理完T2：=R+r和A：=T1*T2之后，此时的表达式集合如下所示：

{＜2,2,*,T0,nil＞,＜3,R,+,r,nil＞,＜4,T1,*,T2,nil＞}

由于B：=A赋值号的右侧不是表达式，因此考虑下一条语句T3：=2*T0，发现表达式2*T0与＜2，2，*，T0，nil＞相匹配，于是，将插入tmp1到该五元组以替代nil，并在2之前生成一个tmp1：=2*T0语句。同时，用T1：=tmp1代替T1：=2*T0，用T3：=tmp1代替T3：=2*T0。(www.xing528.com)

此时，i=6，表达式集合为

{＜2,2,*,T0,tmp1＞,＜3,R,+,r,nil＞,＜4,T1,*,T2,nil＞}

基本块L3的代码变为

(5)1 T0:=3.14 (10)7 T3:=tmp1

(6)2 tmp1:=2*T0 (11)8 T4:=R+r

3 T1:=tmp1 (12)9 T5:=T3*T4

(7)4 T2:=R+r (13)10 T6:=R-r

(8)5 A:=T1*T2 (14)11 B:=T5*T6

(9)6 B:=A

现在考虑下一条语句T4：=R+r，发现该表达式与＜3，R，+，r，nil＞相匹配，于是，将插入tmp2到该五元组以替代nil，并在4之前生成一个tmp2：=R+r语句。同时，用T2：=tmp2代替T2：=R+r，用T4：=tmp2代替T4：=R+r。

此时，i=7，表达式集合为

{＜2,2,*,T0,tmp1＞,＜3,R,+,r,tmp2＞,＜4,T1,*,T2,nil＞}

基本块L3的代码变为

(5)1 T0:=3.14 (9)7 B:=A

(6)2 tmp1:=2*T0 (10)8 T3:=tmp1

3 T1:=tmp1 (11)9 T4:=tmp2

(7)4 tmp2:=R+r (12)10 T5:=T3*T4

5 T2:=tmp2 (13)11 T6:=R-r

(8)6 A:=T1*T2 (14)12 B:=T5*T6

最终，处理完T5：=T3*T4、T6：=R-r以及B：=T5*T6之后，得到如下的表达式集合：

{＜2,2,*,T0,tmp1＞,＜3,R,+,r,tmp2＞,＜4,T1,*,T2,nil＞,

＜7,T3,*,T4,nil＞,＜8,R,-,r,nil＞,＜9,T5,*,T6,nil＞}

经过处理发现，尽管代码的语句数量和变量个数增加了，然而需要执行的二元运算数量却减少了。优化是否能实际改善基本块代码的性能取决于代码本身和目标机的情况。如果所有的变量都放在寄存器中，则代码的性能较好；若部分变量放在主存中，则优化的结果要好。