优化编译器的发展

1. 19世纪50年代，IBM的Backus领导开发了Fortran语言及相应的编译器，这个项目是编译器发展中的一个重要里程碑。这个编译器生成的代码与机器语言程序员所写的代码相当。遍（pass或phase）的概念就是在这个项目中引入的。Backus认为编译器的转化可以理解为是消除，这个项目中使用了循环不变量代码外移，数据流分析和寄存器分配等优化。 John Backus. The history of Fortran I, II, and III. In Wexelblat, editor, History of Programming Languages, pages 25--45. Academic Press, 1981. 　　 2. 60年代，IBM的一个团队为360/370机器开发了Fortran/Level H编译器。这也是一个高度优化的编译器，四元式的概念就是在这里引入。后来Scarborough和Kolsky又对这个编译器进行了提高。这个项目使用了控制流和数据流分析，公共子表达式消除，计算强度降低，寄存器分配，跳转优化等。 （编译器的“前端-中端-后端”经典结构在60年代已经形成。） 　　 R. G. Scarborough and H. G. Kolsky. Improved optimization of FORTRAN object programs. IBM Journal of Research and Development, pages 660--676, Nov. 1980. 　　 3. 60年代末至70年代，IBM的Allen领导的小组，和NYU的Schwartz的小组（SETL），发展了到达定义（reaching definition）和位向量等概念来描述程序转换条件。CMU的Wulf等人定义了结构化的语言Biliss（1975），进行编译优化技术研究，后来这个项目发展成PQCC，用于开发元编译器技术（Leverett 1979）。一些商业组织也在开发编译器，COMPASS开发了基于p-grpah技术的编译器（Karr1975）。这个技术优于到达定义因为数据结构易于升级。IBM基于p-graph提出了SSA格式（Cytron 1989）。 　　 Kennedy在RICE大学建立了编译组，主要关注向量化技术，尤其是scalar optimization。该组的Cooper也进行过程间分析优化。这个组在算法方面很强，尤其是在寄存器分配方面。Cooper等人最近关注编译优化序列问题，这个问题近几年很受关注。 　　 5.70年代末和80年代初，超级计算机和RISC处理器的出现，新的编译技术开始发展。流水线使得设计者开始关注指令调度。最早是Sites（1978）重排Cray-1的汇编代码。后来IBM 801项（1982）目和CMU的Gross（1983）将这个技术用于RISC处理器。寄存器分配也是一个难问题。Chaitin将这个问题归结为图染色问题。CMU的PQCC使用了bin-packing来解决寄存器分配。 　　 用于构造优化编译器的必要技术在80年代就已存在。目前的研究主要集中在如何更高效和更容易的实现这些技术。比如Fortran Level H编译器通过确定循环嵌套来优化循环，后来Morel使用了部分冗余消除拉进行更有效的代码移动，不必对循环进行计算。SSA的概念也使得很多优化非常直观，比如常数传播（Killdall1973，Wegman1985）。