代码生成阶段的循环不变量外提

Loop Invariant Code Motion in Code Generator

循环不变量外提是一种传统的优化算法。在现代编译器中,循环不变量通常在编译器的中端中被删除或外提。中端的中间表示是目标处理机无关的,而编译器的后端的中间表示是目标处理机相关的。尽管中端的优化十分有效,但是从中端的中间表示向后端的中间表示转化的过程中会引入许多循环不变量。因此,有必要在后端再进行循环不变量外提。由于在指令调度的过程能够比较容易地决定一个循环不变量是否需要外提,我们将这一个阶段集成到指令调度中。为了降低指令调度的复杂性,我们把循环不变量的识别和外提区分开来。"识别"独立进行,而决定是否"外提"并实施"外提"则集成到指令调度阶段中。我们在开放源码编译器ORC的代码生成模块中具体实现了本文所介绍的算法。实验结果显示,在代码生成阶段的循环不变量外提能够提高目标代码1%的性能。我们的代价模型避免了78%的循环不变量不必要地外提到循环之外。

Loop invariant code motion (LICM) is a traditional optimization. In modern compiler,it is normally per-formed by the phases of middle-end. The immediate representation (IR) of middle-end is machine independent. And it is machine specific in the back-end. The loop invariants are created when the IR are lowered from middle-end to back-end. Hence,we need to perform the LICM in the back-end. We integrate the LICM into the instruction schedul-ing phase. The reason behind this integration is that it is easy to model the cost of elimination during the phase of scheduling. In order to alleviate the already complex scheduler,we decouple the loop invariant identification from the 'code motion' operation. The identification part is a standalone phase and the 'code motion' part is integrated into scheduling. We have implemented the proposed LICM in the code generator of open source compiler ORC. The result shows the LICM can boost the performance by 1% and obviate the needs of unnecessary motions of 78% loop invariants to their enclosing loops.