优化编译器的设计

2011-04-20郭静

群文天地 2011年14期

■郭静

编译器的研究综合了计算机科学中的操作系统、计算机系统结构、图算法、人工智能等众多领域，因此对编译器的研究要求研究者在各方面都有很深的理解。编译器的研究可以追溯到上世纪50年代。从Fortran语言出现的那天起，研究者们就在不断地探索怎样使高级语言编译后能够和机器语言编写的程序具有相当的效率。Fortran语言的成功很大程度上得益于它从一开始就有很好的编译器。随着越来越多的高级语言的出现，计算机的应用领域越来越广泛，编译器所扮演的角色显得越来越重要。

随着现代先进的计算机系统结构（Computer Architecture）的出现，现代化编译器（Optimizing Compiler）的能力也越来越强大，编译出的程序的效率也越来越高。最初的编译器已经远远不能和现代先进的编译器相提并论了，但是今天编译器仍有许多可以改进的地方，这就需要我们进行更深入的研究。

一、编译器的结构

编译器的结构包括词法分析器(Lexical Analyzer)，语法分析器（Syntax Parser），语言分析器（Semantic Analyzer）,中间代码生成器（Intermediate Code Generator），代码优化器（Code Optimizer），符号表（Symbol Table）,错误处理器（Error Handler）。词法分析器直到中间代码生成器又称为前端（Front End），代码优化器到代码生成器又称后端（Back End）。这个界限并不是严格的，而且有些研究者喜欢把优化过程独立提出来讨论。这样的分层是很有工程价值的，在大型的多语言的编译系统中，任何语言的编译器都共用一个后端，因为后端与高级语言之间几乎没有联系，大多与机器相关；如果有开发者想在某编译系统中添加一种语言的编译功能，只需编写该语言的前端即可；如果需要将已有的编译器移植到新机器上，只需重新编写一个与机器相关的后端即可，前端可以不加修改或者稍作修改后重复使用。以前要编在m种机器上运行，能编译n种语言的编译系统，需要编写n*m个不同的编译器；而按照这种工程分层，则只需编写n个前端以及m个后端即可。著名的编译系统GCC(GNU Compiler Collection)就是按照这种工程分层方式开发的。

词法分析器的实现主要依靠有穷自动机（Finiter Automata）理论。有穷自动机可以识别正则表达式，而NFA可由查表程序模拟来识别高级语言中的“词”，然后生成一个符号表，并将源文件里的每个“词”用一个词素标记（Token）来代替。语法分析器的实现则依靠上下文无关文法（context-Free Grammar）理论以及下推式自动机（Pushdown Automata）理论。由于现代高级语言的语法定义都是以BNF范式给出的，因此用上下文无关文法理论可以很好的解决编译中语法分析这一环节。语法分析主要有LL(1)分析，LR(1)分析，LALR(1)分析等，这正体现出人们在编译器这一领域中的研究成果。现代大部分高级语言编译器使用的是LALR(1)分析。

以上两个过程若手写程序实现很机械也很容易出错，因此人们想到了用计算机自动生成词法分析器和语法分析器的代码。有两个很著名的工具Lex和Yacc以及它们的现代加强版本Flex和Bison就是分别用来自动生成词法分析器和语法分析器的代码的。语言分析主要是检查语法分析生成的语法数结构中是否有错，同时为进一步地生成中间代码做准备。

中间代码生成和优化实际上是一个可以循环执行的过程。每次优化都生成中间代码，而每次优化都有不同的目的，并且这些不同次的优化是互不影响的，不同的优化方面的先后顺序不同，对最终的结果也是有影响的。后文将重点结合现代计算机系统结构来讨论一起优化过程中可能遇到的问题，以及需要注意的一些事项。由于这个话题范围相当广，况且优化这一块不象前端那样有坚实的理论基础且都有固定的优秀算法，其中某些问题甚至是NPC类问题，只有用近似的图论算法或者启发式搜索来得到一个较优化结果；有些优化甚至是无法在编译时刻确定最优情况的，必须在运行时进行优化，这类问题编译器是无法解决的。而解释性的语言如Java,Lisp，Python的解释器有可能做到这一层优化，但目前还没有这方面的有效实现。因此本论文全部的论题是不现实的，只能讨论到其中很小的一部分。

二、编译器如何优化

编译器的优化步骤在整个编译器中是最重要的，也是最难的。它重要是因为一个编译器的好坏主要就是看这个编译器优化的效果是否良好。如果一个编译器的优化效果很差，那么由该编译器编译出与用机器语言编写的程序对系统资源的开销是相当大的，而程序设计语言的设计者往往希望编译器能够编译出与用机器语言编写的程序效率相当的程序；它难是因为优化中的众多问题都没有定型的好算法。有些优化问题的求解甚至是不可计算的。现代系统结构中流水线，超标量以及多核处理器的出现无疑给编译器的设计实现者加重了任务。

优化的正确性原则是优化前后的代码对于任何输入（合法或者非法），都应给出相同的结果。这条原则是显然的，但并不是总那么容易做到。曾经有一段时间，GCC在Intel的机器上对浮点数的存取优化就没能做到这一点。优化代码的提供者没有考虑到Intel的FPU是扩展的80位的，因此对于float,double类型在寄存器中的数据和存在内存中的数据是不一样的，即使逻辑上相等的数据拿寄存器中的与内存中的比较也会得到不相等的结果，优化者期望通过将临时变量存在寄存器中以获取效率，但导致了与未优化的代码产生不同输出的结果。

普通优化一般都会经过以下几个过程：常量转换，将源文件中的常量变量及常量表达式都用其真实值来代替，这将可以节省一定的时间和空间；公共子表达式求值，将多次出现的子表达式预先求值，并存入临时变量，这样可以避免重复求值，但必须保证子表达式的值在任何地方都不会改变；冗余代码的删除，将那些并不会用到的代码删除；优化存储器，将频繁使用的临时变量放入寄存器中；表达式求值优化，改变表达式求值顺序，有时可能达到优化目的；函数过程在线展开，将自程序代码内嵌到调用代码中，这样可以避免函数调用的开销。普通优化还有很多，此处只是试举几例。

针对流水线的优化尤其需要注意代码的顺序以避免各种流水线冒险：结构冒险，当硬件知指令重叠执行中不能支持指令所有可能的组合时发生的资源冒险；数据冒险，在同时执行的几条指令中，一条指令依赖于前一条指令的数据却得不到时发生的冒险；控制冒险，流水线中的转移指令或其他改写程序计数器的指令造成的冒险。现在的指令集系统和CPU设计一般不会出现结构冒险了。

数据冒险一般出在算术指令中，这是编译器最好解决的一种冒险。出现这种冒险，最显然的处理办法是加上一条nop；但是这种处理方式既浪费了时间，又浪费了能量，如果编译器能有效地调整指令顺序，是有可能避免这两种冒险的。如在MIPS的五段流水线中：

在此出现了数据冒险，如果没有发生中断，sub访问r1时add还没有及时更新r1中的内容，因此sub会访问到错误的数据。但如果编译器将后面的一些不会干扰到这块代码、也不依赖于这块代码的指令加在这两条指令中间，就可以避免这个数据冒险了。本节对一般的优化方法和常见的问题做了简单的介绍，还有很多深入的话题有待研究。