公共子表达式消除

复习

• 无用代码删除：去掉白算的代码
• 数据流分析：判断表达式的可用性
• 静态单赋值形式：让分析更简单

TL;DR

• 公共子表达式指重复出现的相同计算
• 只算一次，之后复用结果
• 前提是这中间没有改变相关变量的值
• SSA 让这种分析和复用更容易

正文

　　程序里常常出现同样的计算被反复做。既然结果一样，做一次就够了——这就是公共子表达式消除（common subexpression elimination）。

算一次，到处用

　　看一个例子：

a = x + y
...
b = x + y

　　中间如果没有改动 x 或 y，那么 x + y 两次算出来必然相同。于是第二次可以直接复用第一次的结果：

t = x + y
a = t
...
b = t

　　一次计算，两处使用。省下的不只是一次加法——如果这个表达式很复杂、位于循环里，收益还会被放大。

前提：中间不能变

　　复用的前提非常关键：从第一次算，到下一次用，相关变量的值必须没有改变过。

　　如果中间有 x = 100 这样的赋值，那么第二次的 x + y 已经和第一次不是一回事了，自然不能复用。所以，编译器需要一套分析（判断“某个表达式在某点是否一定已经被算出且仍然有效”），来确认这一点。

　　在 SSA 里，这件事会简单很多：因为每个变量名字只对应一个定义，“x + y 里的 x 有没有变过”这种问题，看一眼名字就知道，不必反复追踪。这也是 SSA 让优化更轻松的一个典型例子。

一次小优化，可能引出更多

　　别小看这一步。当重复计算被合并后，往往会有旧的临时变量变得“没人用”，从而触发无用代码删除；而删除之后，控制结构可能又变得更简单。优化之间常常互相成全，这正是下一章“优化流水线”要讲的主题。

思考题 1

公共子表达式消除，到底在“省”什么？

思考题 2

为什么必须确认“中间没有改变相关变量”，才能复用结果？

小结

知识点

• 公共子表达式是重复出现的相同计算
• 消除后只算一次、复用结果
• 前提是相关变量在此期间未改变
• SSA 让这类分析更直接

参考资料

1. Wikipedia(zh)：公共子表达式消除：复用相同计算的结果
2. Wikipedia(zh)：静态单赋值形式：简化此类分析的形式

思考题答案（仅供参考）

思考题 1

　　它在省重复的计算：同一个表达式算了多次，只保留一次，其余使用第一次的结果，从而减少运行时的运算量与相关开销。

思考题 2

　　因为复用的前提是两次计算的结果相同。如果中间有赋值改变了参与运算的变量，第二次的表达式已经是另一个值，复用就会得到错误结果。所以必须确认相关变量在这期间没有被修改。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪