11.4 编译器优化技术 11.4.4 公共子表达式消除

11.4.4 公共子表达式消除

公共子表达式消除是一项非常经典的、普遍应用于各种编译器的优化技术，它的含义是：如果一个表达式E之前已经被计算过了，并且从先前的计算到现在E中所有变量的值都没有发生变化，那么E 的这次出现就称为公共子表达式。对于这种表达式，没有必要花时间再对它重新进行计算，只需要直接用前面计算过的表达式结果代替E。如果这种优化仅限于程序基本块内，便可称为局部公共子表达式消除（Local Common Subexpression Elimination），如果这种优化的范围涵盖了多个基本块，那就称为全局公共子表达式消除（Global Common Subexpression Elimination）。下面举个简单的例子来说明它的优化过程，假设存在如下代码：

int d = (c * b) * 12 + a + (a + b * c);

如果这段代码交给Javac编译器则不会进行任何优化，那生成的代码将如代码清单11-12所示，是完全遵照Java源码的写法直译而成的。

代码清单11-12 未作任何优化的字节码

iload_2     // b 
imul        // 计算b*c 
bipush 12   // 推入12 
imul        // 计算(c * b) * 12 
iload_1     // a 
iadd        // 计算(c * b) * 12 + a 
iload_1     // a 
iload_2     // b 
iload_3     // c 
imul        // 计算b * c 
iadd        // 计算a + b * c 
iadd        // 计算(c * b) * 12 + a + a + b * c 
istore 4

当这段代码进入虚拟机即时编译器后，它将进行如下优化：编译器检测到cb与bc是一样的表达式，而且在计算期间b与c的值是不变的。

因此这条表达式就可能被视为：

int d = E * 12 + a + (a + E);

这时候，编译器还可能（取决于哪种虚拟机的编译器以及具体的上下文而定）进行另外一种优化 ——代数化简（Algebraic Simplification），在E本来就有乘法运算的前提下，把表达式变为：

int d = E * 13 + a + a;

表达式进行变换之后，再计算起来就可以节省一些时间了。如果读者还对其他的经典编译优化技术感兴趣，可以参考《编译原理》（俗称龙书）中的相关章节。