编译器优化--6--代码移动

编译器优化–6--代码移动

将一个计算移动到相比原来位置执行得不那么频繁的位置上，可以减少运行程序执行的总操作数。因为相对于包围循环的代码来说，循环本身倾向于执行多得多的次数，所以此领域的大部分工作都专注于将不变的表达式从循环中移出。该变换插入代码以使这些操作在所有代码路径上都变成冗余的，并删除这些新的冗余表达式。

惰性代码移动（Lazy Code Motion，LCM）

Lazy Code Motion有文献也翻译为缓式代码移动，我个人觉得惰性代码移动这种翻译，更容易望文生义，让读者一看就知道这种优化大概是干什么的。

惰性代码移动（LCM）使用数据流分析来发现代码移动的候选操作以及放置这些操作的适当目标位置。该算法运行在程序的IR形式及其CFG上。它使用3组不同的数据流方程，并从其结果推导出额外的集合。算法为CFG中的每条边都生成了一个表达式集合，其中包含了沿该边应该求值的所有表达式，并为CFG中的每个结点都生成了一个表达式集合，其中的表达式在对应程序块中的向上展现求值应该删除。使用一个简单的重写策略即可解释这个集合并修改代码。

LCM将代码移动与冗余、部分冗余计算的消除结合起来。

冗余：如果在通向位置$p$p的每条代码路径上，表达式$e$e都已经进行过求值，那么表达式$e$e在位置$p$p处是冗余的。

部分冗余：如果表达式$e$e在到达位置$p$p的部分（而非全部）代码路径上是冗余的，则表达式$e$e在位置$p$p处是部分冗余的。

下图来说明表达式的冗余和部分冗余：

通过使循环中不变的计算成为冗余的并消除之，LCM将其从循环移出，这种优化在独立进行时被称为循环不变量代码移动（loop-invariant code motion）。

整个LCM的优化过程可以大致分为如下几步：

1. 计算可用表达式。LCM需要程序块末尾处的可用信息；
2. 为捕获可用于判断表达式反向移动的信息，LCM需要计算可预测性。
3. 如果给出了可用性和可预测性的解，对于每个表达式，编译器都可以判断在程序中最早于何处可以对该表达式进行求值。
4. LCM中最后一个数据流问题用于判断何时一个最早置放能被推迟到CFG中稍后的一个位置，而仍然能够实现相同的结果。延迟分析表述为CFG上的一个前向数据流问题，其目标在于每个结点n关联的一个集合LaterIn(n)，为每条边(i, j)关联一个集合Later(i, j)。
5. 利用从数据流计算推导出的知识重写代码。

由于算法本身涉及大量的数据流方程、方程的不动点解法和CFG图的理论知识，关于算法的细节展开说可能会使读者望而生畏。有兴趣的读者看《Engineering a Compiler》的10.3章节

参考

《编译原理》

《Engineering a Compiler》