前言

自从1940年代晚期和1950年代早期数字计算机出现以来，构建编译器一直是一项具有挑战的活动。在那个时候，实现从数学家熟悉的算式到计算机指令的自动翻译是一项困难的任务。开发者需要解决如何将算术表达式翻译为指令，如何将数据存储在内存中，如何挑选指令来构建过程和函数。在1950年代晚期和1960年代早期，大多数计算机专家可以编写出简单的编译器，某种程度上实现了上述过程的自动化。事实上，翻译器采用”小型语言“是UNIX社区的基本理念。

从开始以来，人们一直要求翻译器生成高效的代码：翻译器必须充分利用计算机的性能。本来，有这种要求的原因是计算机内存小并且执行速率低。计算机硬件一代一代地更新，每一代都应用了新的架构理念。在每个阶段，也要求编译器不断改进，以更有效地利用这些新的机器。奇怪的是，权威人士总是预测，廉价而低效的翻译器将会胜任工作。他们争辩道，随着机器越来越快，内存越来越大，人们不再需要优化的编译器。不幸的是，人们购买了更大更快的机器，就想要处理更大或更复杂的问题，因此我们仍然需要优化的编译器。事实上，我们更加需要这样的编译器，因为新架构机器的性能对所生成代码的质量是敏感的。相比1970年代和1980年代的复杂指令集计算（CISC）机器，稍微改动指令的序列或者指令的选择，对这些机器性能的影响会大得多。

精简指令集计算（RISC）架构让计算机架构和编译器性能之间的相互影响变得合理。编译器和计算机架构有着一种相互的依赖关系，双方共同努力，让应用程序运行得更快。为了这个目的，通过暴露一些硬件操作的细节，简化了硬件，例如简单的load-store指令集和指令调度。这要求编译器处理这些新暴露的细节，生成执行更快的代码，比在CISC处理器上可能生成的代码都要快。

本书描述编译器中的优化和代码生成phase的设计。有很多书描述编程语言分析。它们强调词法分析、解析、语义分析等流程。有几本书描述针对向量和并行处理器的编译过程。本书描述针对单一超标量RISC处理器的高效程序的编译，包括算法的次序和结构和高效的数据结构。

本书是一份高层级设计文档。这有两个理由。起初，我试图写一本介绍所有可能方法的书，这样读者可以自己选择使用哪些方法。这太庞大了，预计书的页数是几千页——太大了，不现实。在优化的编译器中有大量的不同算法和结构。选择是相互关联的，因此百科全书式的优化编译器方案不能解决一些最困难的问题。

其次，对大型软件流程，我想鼓励这种形式的设计。政府用一种三级的文档系统描述软件项目：A层级文档是概述文档，描述项目的整体情况，列出各个部分。B层级文档描述每个组件的操作，细节足够详细，让读者能够理解每个组件做什么，它怎么做的，而C层级文档是低层级文档，描述项目的每个细节。

作为一个开发者，我发现这种结构负担沉重，因为它退化为一种官僚主义的设施，用了大量纸张，表述极少内容。但是，其基本思想是合理的。本书将描述编译器的优化和代码生成组件，细节足够详细，让读者能够实现这些组件，如果他或者她认为合适。我会为每个组件描述一种方法，可以详细地考察组件之间的相互作用，这样所有的设计和实现都是清楚的。

每章会有一个描述其它可能的实现技术的小节。这个小节将包括目录信息，这样有兴趣的读者可以找到这些技术。

选择编译器技术的哲学

在书的开头，我想说一说我的设计哲学。当我刚开始编写编译器时（大约1964年），我注意到很多研究和开发工作是由文献描述的。虽然这些项目是基于不同的假设和需求的，但是有了文献之后，仿效和使用早前方法变得容易了，不必重新发明它们。因此在设计的时候，我会查阅文献和其它的实现，选择符合我的需求的技术。我的贡献是，选择技术，实现技术，让它适合其它组件，还有我所观察到的小的改进。

必须引入一条工程经验法则。决定使用已经发表的最新的技术是容易的。这种策略是危险的。任何优化或代码生成技术仅仅被使用了一段时间就选择它们会带来副作用。因此，我尝试避开那些不曾在原型或产品编译器中实现至少两次的技术。当我确定一项技术是合理的时候，我会破例一到两次，但是仅此而已。

在写作本书的过程中，我的观点在进化。它从记录已知的知识开始。我利用存在的技术设计并构建了几个编译器。随着书的文字越写越多，我学到很多集成这些算法的方法。它从串联不相关的想法开始，融合为更加集成的整体。它从简单描述工程规划开始，现在包含了一些崭新的想法。这大概就是任何智力工作的过程；但是，我发现它令人耳目一新，令人精神振奋。

如何使用本书

本书是为三个用途而设计的。第一个用途是描述优化编译器的结构，让读者可以实现它或它的变体（编译器编写者总是修改设计）。书的结构反应了这个用途。起始章描述了各个编译phase和它们之间的相互作用；后续章描述了每个编译phase涉及的算法。

本书也可以用作关于编译器优化技术的课本。它采用了一个样例，通过这个样例描述每个编译流程。学生分析不同的样例，而不是求解小的家庭作业问题。

实际上，本书的最大用途是满足求知欲。如果你和我一样，你捡起书本是因为你想学到某种知识。我希望你喜爱这本书，找到你想要的内容。开卷有益。