下载掌阅APP，畅读海量书库
立即打开
编译器的工作一般可分为若干逻辑环节，编写者称之为阶段（phase）。阶段的确切数目和名称随编译器而异，不过许多编译器都有下面这些阶段：词法分析（lexical analysis）阶段、语法分析（syntax analysis）阶段、中间代码生成（intermediate code generation）阶段、本机码生成（native code generation）阶段，如果编译器支持优化的话，还有代码优化（optimization）阶段。
图4-2给出了编译器适当安排这些阶段的形式，以便将高级语言源代码转换成机器（目标）代码。
图4-2 编译过程的各阶段
图4-2似乎表明编译器是依次经过这些阶段的，但大部分编译器并不按顺序执行，而是穿插执行这些阶段。每个阶段做少许工作后，就将其输出送往下一个阶段，然后等待前一阶段的输入。语法分析阶段的分析程序（parser）大概是典型编译器中最像主程序或主进程的部分。通常由语法分析程序推动编译过程，它调用词法分析阶段的扫描程序（scanner）以获得输入，调用中间代码生成程序来处理其输出。中间代码生成程序能够调用可选的优化程序，然后调用本机码生成程序。本机码生成程序同样也可调用优化程序。本机码生成阶段的输出就是可执行代码。在本机码生成程序/优化程序产生一些代码后，又返回到中间代码生成程序，由中间代码生成程序返回到语法分析程序。而语法分析程序要求从扫描程序那里再得到一些输入，该过程反反复复进行下去。
注意： 其他编译器组织形式也是可能的。例如，有些编译器不存在优化阶段；而另一些编译器允许用户选择是否运行这一阶段。类似地，有些编译器省略中间代码生成阶段，而直接调用本机码生成程序。还有些编译器另有一些阶段，可处理不同时候编译的目标模块。
所以尽管图4-2并未精确地给出典型编译器的执行路径，不过它还是正确指示了编译器内的数据流向。即扫描程序读取源文件，将其转换为不同的形式，然后将转换后的数据送往语法分析程序。语法分析程序接收并加工来自扫描程序的输入，将新结果送给中间代码生成程序。类似地，其余阶段都是从前一阶段读取输入，把输入转换为一种（可能）不同的形式，再送到下一个阶段。编译器将最后阶段的输出写到外存，形成可执行的目标文件。
我们来仔细观察代码转换过程的各个阶段。
扫描程序即词法分析器（或称为“词法分析程序”），负责读取从源文件中找到的字符和字符串数据，将这些数据分类为表示源文件词素项的记号。如前所述，词素项就是源文件中的字符序列，我们将其识别为程序语言的原子级组件。例如，C语言的词法分析程序lexer会识别出诸如if、while之类的C保留字。但lexer不会将标识符ifReady中的“if”挑出，而认为它是保留字。扫描程序会考虑保留字的语境，从而区分出保留字和标识符。扫描程序将为每个词素创建一个小的数据包，即“记号”，并将此数据包发往语法分析程序。记号一般包括下列值：
●小的整数值，用于唯一标识该记号的种类（即它是保留字、标识符、整型常量、运算符，还是字符串文字常量）。
●另一个值，用于区分某类别内的各记号（例如，可指示扫描程序对保留字的处理）。
●扫描程序与该词素可能关联的其他属性。
注意： 请勿将此处提到的记号与前面讨论的解释器中的压缩类型记号混为一谈。记号只是与变量一般大的数据结构，用以向解释器/编译器关联词法。
举个例子，如果扫描程序发现源文件中有12345，则对应记号的类别大概是文字常量，第二个值也许被标识为整型常量，记号可能会有一个属性，即此字符串对应的数值，例如一万二千三百四十五。图4-3展示了该记号在内存中的样子。
图4-3 词素"12345"的记号
值345用作记号值（以整型常量指明），值5用作记号类别（指示是文字常量），属性值是12345（词素的数字形式），词素字符串是lexer扫描得到的"12345"。编译器中各处的编码序列都可以在必要时引用此记号的数据结构。
严格来说，词法分析阶段是可选的。语法分析程序可以直接工作于源文件。然而在进行记号化处理后，编译过程就能更高效，因为这样能让语法分析程序将记号当作整数值而非字符串数据。由于大部分CPU处理小值整数要比处理字符串数据的效率高得多，并且语法分析程序需要多次引用记号数据，有了扫描程序的参与，就能为编译过程节约相当可观的时间。一般来说，在分析阶段多次扫描每个记号的语言系统只有纯解释器，这也正是纯解释器很慢的主要原因之一。（我们是将其与以记号化格式保存源文件的解释器相比的。这种解释器之所以用记号化格式保存源文件，旨在避免反复处理纯文本源文件。）
语法分析程序作为编译器的一部分，负责检查源程序的语法、语义是否正确。如果编译器发现源文件中有错误，通常正是由语法分析程序发现并报告错误的。语法分析程序也负责将记号流，即源代码重组为更复杂的数据结构，使之表示程序的意思，即语义。扫描程序和语法分析程序一般以线性方式从头至尾加工源文件，编译器通常只读源文件一次。但随后的阶段要以随机访问方式引用源程序体。通过构建代表源代码的数据结构—我们通常称之为抽象语法树（abstract syntax tree，AST），语法分析程序能使代码生成阶段和优化阶段方便地引用程序的不同部分。
图4-4给出了编译器在抽象语法树上用3个节点表示表达式“12345+6”的方法（43是额外运算符的值，7是代表算术运算符的子类）。
图4-4 抽象语法树的某部分
中间代码生成阶段负责将源文件的抽象语法树表示转换成“准机器码”形式。编译器一般要将程序先转换到中间代码，而不直接转换为本机机器码，基于两个原因。
首先，编译器的优化阶段可进行某些类型的优化，诸如公共子表达式消除，该优化措施对中间代码形式而言要容易操作得多。
其次，许多编译器都是跨平台的编译器，能生成工作于不同CPU架构的机器码。将代码生成过程分成两块—中间代码生成程序和本机码生成程序—编译器的编写者就能将所有不依赖于特定CPU的动作放到中间代码生成阶段，只需生成这些代码一次。这也简化了本机码生成阶段。由于编译器只需要一种中间代码生成阶段，而对编译器所支持的CPU分别设立本机码生成阶段，将不依赖于特定CPU的操作尽可能多地放入中间代码生成程序，可以减小本机码生成程序的体积。同样道理，优化阶段也经常分为两个部分：独立于CPU的部分（中间代码生成程序后面那部分）和依赖于CPU的部分，请参看图4-2。
诸如微软的VB.NET和C#等语言系统，其编译器实际输出的是中间代码。在.NET系统中，微软将这些代码称为通用中间语言（Common Intermediate Language，CIL）。本机代码和优化其实交由微软的通用语言运行时（Common Language Runtime，CLR）处理，CLR也负责完成对.NET编译器生成的CIL的即时编译。
中间代码生成阶段后面的优化阶段会将中间代码转换成更高效的形式，通常是消除抽象语法树中不必要的项。例如，下面的中间代码：
优化器会将其转换为：
如果对i和j不再有引用，优化程序（即优化器）会消除对它们的所有引用。事实上，倘若此后再未使用k，优化程序还会将这两个指令合并为“将5加到m”。请注意这种转换适用于几乎所有CPU。因此，将其放在前一个优化阶段再合适不过了。
将中间代码转换为“更高效的形式”并不是一个定义明确的过程。凭什么说一种形式的程序比另一种程序的效率高？高效的根本定义为程序对某些系统资源的最少占用，通常体现在内存（体积）和CPU周期（速度）上。编译器的优化程序还能管理其他资源，但对程序员而言，体积和速度是其中的两个主要方面。即便我们只考虑优化这两个方面，描述“最佳的”结果也很困难。问题在于，朝着某个目标优化（比如更好的性能）可能与朝着另一个目标优化的措施（比如减少内存的占用）发生冲突。由于这个原因，优化通常是一个折中过程，需要牺牲某些次要目标（比如，代码的某些部分要运行得慢一些）来换取某个合理的结果（比如，得到的程序没有占用太多内存）。
你也许会想，仅选择一个目标，比如尽可能高的性能，并严格为此目标来优化，总可以吧？然而，编译器还得能在合理时间内产生出可执行的结果。优化过程是所谓“ NP 完全问题”（NP-complete problem）复杂度理论的例子。这些都是我们所知的棘手问题。即我们无法得到完全保证正确的结果，例如程序的最优化版本—除非计算所有的可能性，从中找出最好的结果。不幸的是，解决NP完全问题所需的时间与输入量呈指数关系。具体到编译器优化，输入量大致为源代码的行数。
这意味着在“最坏情况”下，产生真正最优化的程序会得不偿失。向源代码中增加一行就会使编译和优化代码的时间翻一番，增加两行代码就会翻两番。事实上，若要对现代应用程序进行完全的最优化，所需时间比我们所知的宇宙寿命还要长。
除非源文件极小，只有几十行代码，否则完美优化程序对其进行优化所要花费的时间将完全体现不出实用价值（这样的优化程序据说已经写出来了，用你顺手的搜索引擎在网上查找“superoptimizers”，就能得到所有细节信息）。因此，编译器的优化程序很少会生成真正最优化的程序。它们只是在用户能容忍的有限CPU时间里产生最好的结果。
注意： 依赖即时（JIT）编译的语言，比如Java、C#和VB.NET，将部分优化措施搬到了运行阶段。因此，优化器的性能直接影响到应用程序的运行效果。由于即时编译系统随应用程序同时运行，因此无法花费太多的时间来优化代码，又不影响运行效果。这个原因造成的后果是，在Java和C#等语言中，即便最终编译出底层机器码，也很难达到传统语言—比如C/C++和Pascal—编译时经过高度优化的运行效果。
现代优化程序并不尝试所有的可能性，并从中挑选最好的结果，而是使用启发式和案例型算法，以确定生成机器码应采取的转换过程。如果我们想从高级语言程序获得尽可能好的机器码，就需要知晓编译器所用到的这些技术。
要写出能让编译器优化程序高效发挥的卓越代码，很有必要了解编译器如何组织所产生的中间代码，以便在后续环节中生成良好的机器代码。编译器优化程序随着贯穿程序的控制流跟踪变量值。这个过程即所谓的数据流分析（data flow analysis，DFA）。经过仔细的数据流分析，编译器就能确定变量何处尚未初始化、何时包含某个值、程序何时不再使用它，以及同样重要的是，编译器在什么时候对变量值一无所知。例如，请看如下Pascal代码：
好的优化程序会将这段代码替换成如下形式：
事实上，编译器可能不会为最后两行语句产生代码，而是在后面的引用中以0代替i，以6代替path。编译器这么了不起？！要知道有些编译器甚至能跟踪嵌套函数调用和复杂表达式中的常量赋值以及表达式。
编译器如何做到这一点？对此的完整说明超出了本书范围，但我们应当大致了解编译器在优化阶段怎样跟踪变量，因为粗枝大叶编写的程序只会妨碍编译器的优化能力。卓越代码应很好地配合编译器，而不是与其唱反调。
优化高级语言代码时，有些编译器可以做出令人称奇的事情来。然而，优化是固有的缓慢过程。正如前面所述，优化是一个棘手的问题。幸运的是，多数程序无须进行彻底的优化。采用近似最佳的程序，即使运行起来比最佳程序慢一点，但与冗长的编译时间权衡，其仍然是一种可接受的折中方案。
编译器优化时对编译时间所做的主要让步是，编译器在进行下一步之前，为一段代码找寻较多可能的优化办法。因此，如果我们的编程风格容易将编译器搞糊涂，那么编译器也许无法产生最佳的（甚至接近最佳的）的可执行文件，因为编译器有太多的可能方案要考虑。诀窍就是要搞清楚编译器是如何优化源文件的，以便其能为我所用。
为了分析数据流，编译器将源代码划分成一些被称为基本块（basic block）的序列。基本块就是除了块的开始、结束位置外没有任何分支的机器指令序列。例如，请考虑如下C语言代码：
这个程序片段含有5个基本块。基本块1从源代码头开始。基本块会在指令序列跳入/跳出的地方终结，基本块1在调用f()函数时结束。基本块2开始于调用f()函数后的语句，尽头位于if语句起始处，因为if会将控制导向两个可能的位置。基本块1的else子句结束了基本块3，也标记出基本块4的开始，因为从if的then到达else后跟着的语句，需要跳转到else子句后的语句。基本块4的结束并非因为代码将控制发往别的地方，而是由于基本块2跳转的第一条语句启动了基本块5（从if的then子句出来）。基本块5以对C语言printf()函数的调用结束。
要确定基本块在何处起止，最容易的办法是考虑编译器为该段代码产生的汇编代码。只要有地方是条件分支/跳转、无条件跳转或调用指令，就表明该基本块到头了。然而应注意，基本块可包含将控制发往别处的指令，在将控制发往别处的指令后马上开始新的基本块。还需要注意的是，任何条件分支的目标标记、无条件跳转或调用指令，都会形成新的基本块。
基本块的好处在于，它使编译器跟踪变量及其他程序数据的操作变得方便。编译器处理每条语句时，能基于变量初始值按符号跟踪其在基本块中的值，跟踪对这些变量进行的运算。
当两个基本块的路径汇集到同一个代码流时，问题就来了。比如在这个例子中，在块3结束处编译器能容易地确定变量j为0，因为该基本块将0赋给j，此后再没有对j赋值。类似地，在块3结束处，程序知道j的值为j0+x0（假设j0表示j在进入该基本块时的初始值，x0表示x在进入该基本块时的初始值）。但当路径在块4开始处汇集在一起时，编译器可能无法确定j的值是0，还是j0+x0。所以编译器要注意，j的值在该点处可能是截然不同的两个值之一。
尽管只要优化程序说得过去，就很容易跟踪某变量在给定某点可能的两个值，但不难想象编译器有很多可能的不同值需要跟踪时会是什么情形。事实上，只要我们有若干if语句顺序执行的代码，通过这些if的每个路径都可以修改给定的变量，那么某变量可能值的数目就会随着每条if语句增长1倍。换句话说，可能的数目将与代码序列中的if语句条数呈指数关系。这种情况达到某种程度后，编译器将无法跟踪变量所有可能的值，只好停止跟踪给定变量的信息。要是这样的话，编译器能考虑的优化方案就变少了。
幸运的是，尽管循环、条件语句、switch/case语句、过程/函数调用会以指数方式增加可能的路径数，但对于写得好的程序，实践中编译器很少出问题。这是由于，即便来自基本块的路径汇合在一起，程序也会经常对变量赋予新值，因而编译器也就不必跟踪旧信息了。编译器通常假设程序不会在每个路径内都对变量赋予不同值，编译器的内部数据结构也据此构建。所以要记住，倘若我们违背了这一假设，编译器对变量值的跟踪就可能会迷失，因而产生较差的代码。
对于结构糟糕的程序，由于其创建的控制流路径会迷惑编译器的优化程序，也就减少了优化机会。合理的程序能产生可归约的流程图（reducible flow graph）。流程图就是程序控制流的图形化表示。图4-5就是前面代码片段的流程图。
图4-5 流程图示例
在此可以看出，各基本块的结束处与其转送控制的基本块开始处被用箭头线连接起来。在该个例中，所有的箭头都朝下，但实际情况并不总是这样。打个比方，循环在流程图中能将控制转回去。我们来看另一个例子，请考虑下列Pascal代码：
图4-6给出了这段简单代码的流程图。
图4-6 while循环的流程图
我们已经提到，对于结构合理的程序，其流程图是可归约的。本书不打算详细介绍可归约流程图，我们只需知道，仅由if、while、repeat...until等结构化控制语句组成且不用goto的程序都是可归约的。这是一个重要的说法，因为编译器工作于可归约的程序时会表现很好。相比之下，不可归约的程序往往会破坏优化程序。
可归约的程序为什么便于优化程序处理呢？因为这种程序里的基本块可被缩写成提纲方式，提纲方式的块继承了基本块内在的特性（例如，块内修改了哪些变量）。通过将源文件按提纲方式处理，优化程序只需应对数目较少的基本块，而不是大量的语句。这种优化分级办法更有效率，可使优化程序维护更多有关程序状态的信息。另外，优化时间与复杂度的指数关系在此也起了作用。通过减少要处理的代码块数（化简），能够急剧减少优化程序的工作量。再次指出，编译器如何做到这一点的确切细节在此并不重要，关键是注意：程序如果避免采用goto语句等怪异的控制流传送算法，通常就是可归约的，优化程序将能对代码优化得更好。塞入一大堆goto语句，以免代码重复和执行不必要的测试—这样尝试“优化”代码只会适得其反。我们也许能在眼前的某些地方节约几个字节或几个周期，但其后果足以迷惑编译器，使之无法很好地实现全局优化，造成整体的效率损失。
第12章将提供编译器优化措施的完整说明，并给出编程语境中常见编译器优化措施的示例。不过现在，我们先浏览一下优化的基本类型。
常量折叠
常量折叠就是在编译时期即计算出常量表达式或子表达式的值，而不是到运行时才发送代码去计算结果。参看12.2.1节。
常量传播
如果编译器能够更早确定在代码中某变量被赋值为常量，那么常量传播会把程序中要访问该变量的地方替换成常量值。参看12.2.2节。
死码消除
死码消除就是删除那些与特定源代码语句关联的目标码，这些源代码语句的结果从未被用过，或者条件块从来不为true。参看12.2.3节。
公共子表达式消除
通常，表达式的一部分会在当前函数中的其他地方出现，这“一部分”被称为子表达式。如果子表达式中的变量值并未修改过，程序就不需要在出现子表达式的地方重复计算该表达式的值。程序可以在第一次计算时保存子表达式的值，然后将此值用到子表达式出现的其他地方。参看12.2.4节。
强度削弱
CPU经常能采取与源代码不同的运算符，直接计算出某值。例如，当常量为2的次数（即2的整数次幂）时，移位（shift）操作可以代替操作数与此常量的乘除操作。某些取模（余数）操作可通过按位的and指令实现。而shift和and指令通常比乘法、除法指令快得多。多数优化程序都能准确地识别出这些开销很大的操作，并将其替换成开销较小的机器指令序列。参看12.2.5节。
归纳变量
对于许多表达式，特别是位于循环中的表达式，式中的某个变量值完全依赖于其他某个变量。这时编译器通常省去对其新值的计算，或者在循环期间将变量值计算与表达式计算合二为一。参看12.2.6节。
循环不变体
迄今为止所提到的优化措施，都是编译器用来改进精心编写的代码的技术。相比而言，处理循环不变体则是针对糟糕代码的编译器优化措施。循环不变体就是不随循环中每次迭代而变化的表达式。优化程序只要在循环外一次计算出这种运算的结果，就可以在循环体内使用该结果。许多优化程序很聪明，能找出循环不变体的计算式，并使用代码移动（code motion）将其移出循环体。参看12.2.7节。
出色的编译器还有不少优化“花招”。不过，以上是我们对任何像样编译器都能指望得上的标准优化措施。
默认情况下，多数编译器几乎不采取优化措施：我们必须明确通知编译器执行某些优化。这似乎违反常理，毕竟大家通常希望编译器能为自己生成足够好的代码。然而，“最优化”的解释有许多种，哪个编译器的输出都无法满足这个术语的所有可能定义。
你也许会争辩：有几种优化—即使并非你感兴趣的类型，也总比没有强吧。但是，默认状态没有优化还是有一些理由的：
●优化是一个漫长的过程。如果关掉优化程序，编译可以快一些。当处于快速的编辑－编译－测试周期时，这会很有帮助。
●代码优化后许多调试器不能很好地工作。为了对应用程序使用调试器，只能关掉优化功能。这样还使得分析编译器的输出变得容易多了。
●编译器的大部分缺陷都在优化程序中。倘若产生不经优化的代码，遇到编译器缺陷的可能性就会小一些（于是，编译器的编写者被告知缺陷的可能性相应也会小一些）。
多数编译器提供命令行选项，以便我们控制编译器实现的优化类型。UNIX的早期C语言编译器，使用诸如-O、-O1和-O2这样的命令行参数来控制编译器的优化阶段。后来的许多C语言及其他编译器也采纳了同样的策略，尽管命令行选项并不完全一样。
你大概在想，编译器为何提供多个选项来控制优化，只要一个选项控制优化与否不就行了？请记住，“优化”对不同的人有不同的意义。有些人也许希望代码针对空间优化，而另一些人可能希望针对速度优化，而这两种优化在给定条件下是相互矛盾的。有的人似乎只想进行少量优化，不想让编译器老在处理他们的文件，所以他们只愿意进行少量的快速优化。还有的人希望针对CPU家族的某个特定成员，例如80x86中的Core i9来优化。再有，一些优化措施只有在以某种方式写程序时，才是“安全的”，即总能生成正确代码。倘若程序员无法保证他们是用这种方式写程序的，当然不希望使用这种优化功能。最后一点，对于程序员认真编写的高级语言代码，编译器所做的某些优化实际可能产生出劣质代码，所以程序员要想生成足够好的代码，具备设定专门优化方案的能力将会很方便。因此，现代编译器大都在要做的优化措施方面具备一定的灵活性。
就拿Microsoft Visual C++来说吧，下面是Visual C++提供的用来控制优化的命令行选项：
GCC也有类似的清单，但比这还长，可以对GCC命令指定选项“-v --help”来查看。大部分优化选项以“-f”打头。我们还可以用“-O n ”来指定不同的优化级别，其中 n 为一位数字。应小心使用“-O3”或更高级别的优化选项，因为某些情况下优化也许是不可靠的。
有一个现实因素将限制我们生成卓越代码，那就是不同编译器的优化措施千差万别。即使两个编译器实施同样的优化方案，其效果也会大不相同。
幸运的是，可以访问某些网站，它们对各种编译器进行了定量评测。这方面有一个非常好的网站Willus.com。只要在线找寻诸如“compiler benchmarks”或“compiler comparisons”话题，就能得到有趣的信息。
本机码生成阶段负责将中间代码转换成目标CPU的机器码。例如，80x86本机码生成程序会将前述的中间代码序列转换成下面这种形式：
本机码生成后会进入二次优化阶段，按照本机器专有的特性来优化代码。例如，针对Pentium II的优化程序会将“add(1,eax);”替换成“inc(eax);”。较新CPU的优化程序或许做的是相反操作。优化程序对某些80x86处理器进行优化时，或许会将指令组织成某种序列形式，以便充分发挥超标量架构CPU的并行执行性能；而针对其他80x86 CPU的优化程序，可能对指令采取另外的组织形式。