公共子表达式消除

公共子表达式消除，又称CSE（Common subexpression elimination（英语：Common subexpression elimination）），是一个编译器优化技术。在执行这项优化的过程中，编译器会视情况将多个相同的表达式替换成一个变量，这个变量存储着计算该表达式后所得到的值。^[1] 该优化技术十分常见，在现代各大编译器中（如LLVM、GCC）均有实现。

例子

考虑到下列代码：

 a = b * c + g; d = b * c + e; 

可以观察到 b * c 是两项表达式中的公共子表达式。如果计算这个子表达式并将其计算结果存储起来的开销，低于重复计算这个子表达式的开销，则能够将以上代码转换成以下代码：

 temp = b * c; a = temp + g; d = temp + e; 

原理

执行这项优化的可能性基于表达式的定义可达性。当以下条件成立，则一个表达式 ${\displaystyle b*c}$  在程序的某个点 ${\displaystyle p}$  被定义为是可达的：

• 从初始节点到点 ${\displaystyle p}$  的每条路径在到达 ${\displaystyle p}$  之前计算过 ${\displaystyle b*c}$ ；
• ${\displaystyle b*c}$  被计算后，无论 ${\displaystyle b}$  或 ${\displaystyle c}$  到点 ${\displaystyle p}$  以前都没有被重新赋值过。

由编译器计算的成本效益分析可以判断出，重复计算该表达式的开销是否大于存储该表达式的计算结果，并且这个分析也要将寄存器等因素考虑在内。

编译器开发者将公共子表达式消除分成两种：

• 本地公共子表达式消除：这项优化技术工作于基本块之内。
• 全局公共子表达式消除：这项优化技术工作于整个过程之中。

参考资料

1. Steven Muchnick; Muchnick and Associates. Advanced Compiler Design Implementation. Morgan Kaufmann. 15 August 1997. ISBN 978-1-55860-320-2. Common subexpression elimination.