本书迎接现代语言和体系结构的挑战，帮助读者作好准备，去应对将来要遇到的编译器设计的问题。
本书涵盖现代微处理器编译器的设计和实现方面的所有高级主题。本书从编译设计基础领域中的高级问题开始，广泛而深入地阐述各种重要的代码优化技术，分析各种优化之间的相对重要关系，以及实现这些优化的最有效方法。
本书特点
●为理解高级编译器设计的主要问题奠定了基础
●深入阐述优化问题
●用Sun的SPARC、IBM的POWER和PowerPC、DEC的Alpha以及Intel的Pentium和相关商业编译器作为案例，说明编译器结构、中间代码设计和各种优化方法
●给出大量定义清晰的关于代码生成、优化和其他问题的算法
●介绍由作者设计的以清晰、简洁的方式描述算法的语言ICAN (非形式编译算法表示)。
无
本书讨论单机编译器设计和实现技术领域的前沿问题，重点讨论编译优化技术（超过了本书60％的篇幅）。我们考虑了支持指令级并行的机器，但几乎完全忽略了大规模并行处理和向量处理的有关问题。
本书首先讨论编译器的结构、符号表管理（包括那些允许导入和导出作用域的语言）、中间代码结构、运行时支持问题（包括可以在运行时链接的共享对象），以及根据机器描述自动产生代码生成器等。之后，探讨过程内的（通常称为“全局的”）控制流分析、数据流分析、依赖关系分析和别名分析的各种方法，并介绍一系列的全局优化，包括那些作用于程序不同成分（从单个表达式到整个过程）的优化。接下来本书讲述过程间的控制流分析、数据流分析和别名分析，以及过程间优化和如何应用过程间信息来改善全局优化。然后，讨论有效利用层次存储系统的优化技术。最后，详细介绍4个分别来自DEC、IBM、Intel和Sun 微系统公司的商业化编译系统，以提供编译器结构、中间代码设计、优化策略和效果的专门例子。如我们将看到的，这些编译系统采用的技术具有广泛的代表性，并用不同的方法获得了类似的效果。
本书的写作过程
1990年6月到1991年，我在Sun微系统公司担任高级工程师。在ACM SIGPLAN的程序语言设计和实现技术年会上，我用半天时间作了一个名为“RISC系统高级编译技术”的讲座。在这个讲座上，我用大约130张幻灯片讲解了RISC体系结构和相关的编译技术，特别是优化技术。在那次讲座之后，我有了一个想法，即讲座材料可能是一颗渴望着阳光、土壤和水分，期待着长成参天大树的种子（实际上，在我的脑海中是一颗橡树种子），而这棵大树就是你面前的这本书。一年多后，我与Wayne Rosing讨论了这个想法，然后又向Sun微系统实验室主任作了汇报，几周后他就决定支持这本书的写作，并给予了一年半的时间和部分资助。
本书的第一稿中除了高级编译技术外，还包含了相当多的RISC体系结构的内容。不久我就认识到（在3位评阅者的帮助下），不必要写这么多体系结构的内容。新的RISC体系结构不断被开发出来，大多数大学的体系结构课程都介绍了研究编译技术所需要的相关知识，本书的重点应该是编译技术。
这导致了本书写作方向的一次重大改变。体系结构方面的大多数内容都被删除了，仅仅保留了体系结构中与编译过程决策有关的内容。编译器的材料也拓宽为包含了有关CISC的编译技术，同时决定只集中讨论单机编译技术，将并行化和向量化的内容留待其他书去讨论。有关编译技术的内容更加集中和深入，有些方面缩小了范围，有些方面又扩大了范围（例如，有关手工代码生成的内容几乎全部删除了，但添加了有关先进调度技术的内容，如踪迹调度和渗透调度）。这样就形成了你面前的这本书。
关于本书的封面
本书封面的图片是从作者的西北海岸民间艺术收藏中选取的，这是一张奇尔卡特毛毯的照片。这块毛毯是在19世纪晚期，由美国阿拉斯加东南部的一个特里吉特妇女，用红松内层树皮制成的非常细的绳子和山羊毛线编织的。编织这样一块毛毯通常需要6~9个月。这块毛毯的图案分为3个部分。中间的一块描绘了一条在水中潜游的鲸鱼；鲸鱼头位于底部，是一个割裂开了的图形；中间有着鲸鱼面部的那个图形是鲸鱼的身体（在这类绘画中，看起来像鲸鱼面部的图形并不表示鲸鱼的面部）；鲸鱼的侧鳍在身体的两边；而顶部是鲸鱼的尾鳍。这个设计中的每一部分，就本身而言，都是功能上的，并没有表达什么含意；但它们按正确的方式组合起来，就描绘了一条在水中潜游的鲸鱼，显示了拥有这条毛毯的村长的权力和特权。
类似地，一个编译器的每个组件有着某种功能，但仅当这些组件以适当的方式组合在一起时，才能完整地实现编译器的功能。设计和编织这样一块毛毯需要技巧，同样，构造工业水准的编译器也需要技巧。每个行业都有一组特定的工具、材料、设计要素和总体模式，而所有这一切都必须按满足预期用户的需要和愿望的方式组合到一起。
本书的读者
本书预期的读者是需要了解设计和构造单机高级编译器有关问题的计算机专业人员、研究生和高年级本科生。我们假定读者已经选修了数据结构、算法、编译器设计和实现、计算机体系结构、汇编语言程序设计等课程，或已经具有相当的工作经验。
内容概览
全书分为21章，另有3个附录。
第1章 高级主题介绍
这一章介绍本书的主题，即高级编译器的设计和构造，同时讨论编译器的结构和编译优化的重要性，并介绍本书内容的组织结构。
第2章 非形式化编译算法表示
第2章介绍了一种称为ICAN的非形式化的程序设计表示方法，并给出了有关例子。这种表示方法用于表示本书中的编译算法。在介绍了这种语言的语法符号之后，我们给出了ICAN的概述，接着详细描述了该语言。读者读了ICAN的概述，就足以读懂本书中的大多数算法，只是在很少的情况下，才需要了解ICAN的全部细节。
第3章 符号表结构
第3章首先讨论变量的属性，例如存储类、可见性、易变性、作用域、大小、类型、对齐、结构、寻址方法等。然后给出了高效地构造和管理局部和全局符号表的方法，包括导入的和导出的作用域（在Ada、Mesa、Modula-2中存在这种情况）、存储绑定，以及在考虑上述属性的前提下产生取、存指令的方法。
第4章 中间表示
这一章集中介绍中间语言的设计、本书专用的三种中间语言，以及编译器中可能使用的中间代码的其他基本形式。我们使用了密切相关的高、中、低三种形式的中间语言，以便能够深入说明书中讨论的所有优化算法。我们还讨论了本书使用的中间语言和其他中间语言的相对重要性以及它们的用途。
另外两种更详细的中间代码形式，即静态单赋值（SSA）和程序依赖图分别在8.11节和9.5节中讨论。
第5章 运行时支持
第5章关注的问题主要与运行时支持用高级程序设计语言编写的程序有关，我们讨论了数据表示、寄存器使用、运行时栈和栈帧的设计、参数传递、过程结构和链接、过程值变量、代码共享、位置无关代码，以及为支持符号和多态语言涉及的一些问题。
第6章 自动产生代码生成器
第6章讨论根据机器描述自动产生代码生成器的方法。我们详细给出了Graham-Glanville的语法制导技术，并介绍了另外两种方法，即语义制导分析和树模式匹配。
第7章 控制流分析
这一章和随后的三章讨论作用于过程的4种分析方法，这些分析对于实现正确和有效的程序优化至关重要。
第7章重点讨论确定过程中的控制流和构造控制流图（CFG）的方法。我们首先综述了若干种可能使用的方法，然后详细讨论其中的三种。第一种是采用深度为主搜索和必经结点的传统方法。在讨论它的同时，我们也将讨论流图的遍历，如CFG的前序遍历和后序遍历，以及查找CFG的强连通子图。另外两种方法依赖于可归约性的概念，它使得过程的控制流图可以层次式地构成。这两种方法分别称为区间分析和结构分析，两者之间的不同在于它们辨别的结构单元的类型。我们也讨论了用所谓的控制树表示一个过程的层次结构方法。
第8章 数据流分析
第8章讨论确定过程中数据流的方法。它从一个例子开始，然后讨论数据流分析所依赖的基本数学概念，即格、流函数和不动点。接下来给出数据流问题和解法的分类，然后详细讨论与前一章3种控制流分析方法对应的3种数据流分析方法。第一种方法是迭代数据流分析，它对应于使用深度为主搜索和必经结点的控制流分析。另两种数据流分析方法与基于控制树的两种控制流分析对应，并分别具有与它们相同的名字：区间分析和结构分析。在此之后，我们概述一种少见的称为位置式分析的新技术，并描述表示数据流信息的方法，即du链、ud链、网（web）和静态单赋值形式（或SSA）。最后考虑有关数组、结构和指针的处理，并以关于数据流分析器自动构造方法的讨论结束本章。
第9章 依赖关系分析和依赖图
第9章关注依赖关系分析，以及与依赖分析密切相关，称为程序依赖图的中间代码形式，其中的依赖关系分析是对数组和低级存储引用进行数据流分析的一种简易方法。我们首先讨论依赖关系，然后讨论如何计算基本块中的依赖关系，这些内容对于第17章中要介绍的代码调度技术至关重要。接着讨论循环中的依赖关系以及依赖关系测试方法，它们是第20章讨论数据存储优化的基础。最后讨论程序依赖图，这是一种直接表示控制和数据依赖的中间代码形式，用它来进行一系列的程序优化比用隐含着依赖信息的中间代码来进行程序优化要更为有效。
第10章 别名分析
第10章讨论别名分析，这种分析确定一个存储单元是否有可能由多个访问路径访问，例如既可用名字也可通过指针来访问。我们首先讨论在Fortran 77、Pascal、C和Fortran 90等语言中别名对程序的影响。接着讨论一种非常通用的对过程内出现的别名进行判定的方法，这种方法由一个与语言相关的别名收集器和一个与语言无关的别名传播器组成。可以对别名收集器和传播器作裁剪来提供信息，这些信息可以是依赖于或不依赖于过程控制流的信息，也可以是用其他多种方式提供的信息，从而使得它成为一种能够适应特定程序设计语言编译器需要和时间限制的通用方法。
第11章 优化简介
第11章介绍代码优化的内容，它首先讨论了这样一个事实，即，尽管大多数优化的适用性和有效性是递归不可判定的，但仍然值得对于适用性和有效性是确定的程序施加这些优化，并且对第12~18章涉及的过程内优化技术作了一番快速浏览。然后讨论了流敏感性和可能与一定信息，如何将这些信息应用于优化，特定优化的相对重要性，以及它们应有的执行顺序。
第12章 前期优化
本章讨论在优化过程的较早阶段实行的一些优化技术，包括聚合量的标量替代、局部和全局值编号（施加于SSA形式的代码）、局部和全局复写传播、稀有条件常数传播（同样施加于SSA形式的代码）。本章还将讨论常数表达式求值（或常数折叠）和代数化简，以及如何在优化器中以子程序的形式实现它们，以便可随时根据需要而调用。
第13章 冗余删除
第13章关注几种类型的冗余删除。冗余删除的基本功能是删除过程中一条路径上多于一次执行的计算。本章描述了局部和全局公共子表达式删除、向前替换、循环不变代码外提、部分冗余删除和代码提升。
第14章 循环优化
第14章研究施加于循环的优化技术，包括归纳变量的识别、强度削弱、归纳变量删除、线性函数测试替换和不必要边界检查的删除。
第15章 过程优化
第15章给出施加于过程的优化技术，讨论了尾调用优化（包括尾递归删除）、过程集成、内嵌扩展、叶例程优化和收缩包装。
第16章 寄存器分配
第16章关注过程内的寄存器分配和指定。我们首先讨论局部的、基于代价的方法，然后讨论图着色法。我们讨论了作为寄存器分配对象的网、冲突图、冲突图的着色以及溢出代码的生成。在此之后，简要给出了使用过程的控制树进行寄存器分配的方法。
第17章 代码调度
第17章集中讨论局部和全局指令调度，这种调度通过重排指令的顺序来发挥现代处理器中流水线的最佳性能。局部调度有两种途径，一种是表调度，它处理一个基本块内的指令序列；另一种是分支调度，它处理基本块之间的连接。接着我们考察跨基本块边界的调度方法，包括前瞻取和提升。然后讨论两种软流水方法，称为窗口调度和展开-压实。接下来讨论循环展开、变量扩展、寄存器重命名和层次归约技术，前三种技术增加了调度的自由度，层次归约技术处理嵌在循环中的控制结构。最后以踪迹调度和渗透调度两种全局调度方法来结束本章。
第18章 控制流和低级优化
第18章研究控制流优化和通常施加于低级形式的中间代码上或类汇编语言表示上的一些优化。这些优化包括不可到达代码的删除、伸直化、if化简、循环化简、循环倒置、无开关化、分支优化、尾融合（又称交叉转移）、条件传送指令的使用、死代码删除、内嵌扩展、分支预测、机器方言、指令归并，以及寄存器合并或归并。
第19章 过程间分析与优化
第19章关注将分析和优化技术推广到处理整个程序的技术。它讨论过程间的控制流分析、数据流分析、别名分析以及各种变换，给出两种方法，分别用于流不敏感副作用分析和别名分析，同时给出一种计算流敏感性副作用和进行过程间常数传播的算法。然后讨论过程间的优化，并将过程间的信息应用于过程内的优化，之后是过程间寄存器分配和全局引用的聚合。最后讨论将过程间分析和优化集成到编译器优化序列中时应有的顺序。
第20章 存储层次优化
第20章讨论发挥大多数系统都具有的层次存储器，特别是多级高速缓存效率的优化技术。我们首先讨论数据和指令高速缓存对程序性能的影响。然后考虑指令高速缓存的优化，包括指令预取、过程排序、过程和基本块的放置、过程内的代码安置、过程分裂，以及过程内和过程间方法的结合。
接下来我们讨论数据高速缓存的优化，主要集中于循环变换。我们不全面地研究这个问题，而是选择部分问题进行详细讨论，例如数组元素的标量替换和数据预取，并且对于其他问题只概要性地给出定义、术语和技术，它们涉及到的问题，以及相关技术的若干例子。这些技术包括数据重用、局部化、循环铺砌、标量优化与面向存储器的优化之间的相互作用。我们这样写是因为这一方面的技术非常新，以至于难以准确地选择权威性的优化算法。
第21章 编译器实例分析与未来的发展趋势
第21章给出4个商业化编译器的实例，它们涉及了目标机体系结构、编译设计技术、中间代码表示和优化技术的各个方面。这4种体系结构是：Sun 微系统的SPARC、IBM的POWER（和PowerPC）、Digital Equipment的Alpha以及Intel 386系列。对于其中的每一种，我们首先简要讨论它的体系结构，然后介绍硬件厂家为它提供的编译器。
附录A 本书使用的汇编语言指南
附录A对本书使用的每一种汇编语言给出一个简短的描述，使读者能更容易地理解书中的例子。它包含了关于SPARC、POWER（和PowerPC）、Alpha、Intel 386体系结构系列以及PA-RISC等汇编语言的讨论。
附录B 集合、序列、树、DAG和函数的表示
附录B对书中大多数抽象数据结构的具体表示作一番快速的回顾，它不能代替数据结构课程，但可以作为一些问题和方法的备用参考。
附录C 软件资源
附录C给出可通过匿名FTP或万维网访问的一些软件，这些软件可作为教学中的编译器实现课题的基础，在某些情况下，这些软件甚至可作为公司研制编译器的基础。
参考文献
最后的参考文献列出了针对本书所涉及问题的大量进一步阅读材料。
索引
书末附有一个索引，其中列出了本书涉及的各种语法符号和各个主题。
补遗、资源和网络扩充的内容
每一章的结尾都给出了若干习题。高级习题在左页边标注了ADV，研究性的习题标注了RSCH。部分习题解答的电子版可以从原出版社获得。与本书相关的资料可以在关于本书的如下网址找到：http:// books.elsevier. com/us//mk/us /subindex.asp maintarget =companions/ defaultindividual.asp&isbn=1558603204。教师如需本书习题的解答，请直接与原出版社联系。
资源
如上所述，附录C给出了可用于构建编译器项目的自由软件及获取的途径。从上述网址中也可获得整个附录，连同它给出的那些资源的地址链接。
网络扩充的内容
可以从出版社的上述网址得到关于目标代码转换的补充材料，这是一种从一种体系结构的目标代码（而不是从源程序）得到另一种体系结构的目标代码的转换。该网址上的扩充内容讨论了目标代码编译过程的原理，然后集中讨论了3个例子，即Hewlett-Packard的HP3000到PA-RISC的变换器OCT、数字设备公司（DEC）的VAX VMS到Alpha的变换器VEST和MIPS到Alpha的变换器mx。
致谢
首先，也是最重要的，我要感谢我以前在Sun 微系统公司的同事们，其中主要有Peter Deutsch、Dave Ditzel、Jon Kannegaard、Wayne Rosing、Eric Schmidt、Bob Sproull、Bert Sutherland、Ivan Sutherland以及程序设计语言部的成员们，尤其是Sharokh Mortazavi、Peter Damron和Vinod Grover。没有他们的支持和鼓励，就不可能有这本书。我还要特别感谢Wayne Rosing在本书写作的头一年半时间中给予的资助。
其次，我要感谢本书的评阅人J. Randy Allen、Bill Appelbe、Preston Briggs、Fabian E. Bustamante、Siddhartha Chatterjee、Bob Colwell、Subhendu Raja Das、Amer Diwan、Krishna Kunchithapadam、Jim Larus、Ion Mandoiu、Allan Porterfield、Arch Robison、Francisco J. Torres-Rojas和Michael Wolfe，他们都对本书的草稿提出了有价值的意见。
对其他公司和组织中与我共享了他们的编译器和其他技术信息的同行们，我也心怀感激，无论这些信息是否直接被本书采用。他们是：Cygnus Support的Michael Tiemann、James Wilson和Torbj歳n Granlund，Digital Equipment的Richard Grove、Neil Faiman、Maurice Marks和Anton Chernoff，Green Hills Software的Craig Franklin，Hewlett-Packard的Keith Keilman、Michael Mahon、James Miller和Carol Thompson，Intel的Robert Colwell、Suresh Rao、William Savage和Kevin J. Smith，IBM的Bill Hay、Kevin O誃rien和F. Kenneth Zadeck，MIPS Technologies的Fred Chow、John Mashey和Alex Wu，Open Software Foundation的Andrew Johnson，Rice大学的Keith Cooper和他的同事们，斯坦福大学的John Hennessy、Monica Lam和他们的同事们，以及英国国防研究署的Nic Peeling。
我特别感激我的父母Samuel和Dorothy Muchnick，他们为我创造了一个充满希望的家庭氛围，鼓励着我提问和尝试回答艰难的问题，使我更加欣赏世间万物的美丽，无论它们是简单的还是复杂的，是自然的还是人造的。
Morgan Kaufmann出版社的工作人员以他们熟练的技巧和沉着的作风指导了这本书的出版。他们是：Bruce Spatz、Doug Sery、Jennifer Mann、Denise Penrose、Yonie Overton、Cheri Palmer、Jane Elliott和Lisa Schneider。我感谢他们并期待着与他们再度合作。
Windfall Software的排字员Paul Anagnostopoulos设计了ICAN中用的特殊符号，细心而有主见地完成了本书的排版。一天上午他发给我一封电子邮件说，他期待着阅读我们共同劳动的成果，对我而言，这一天就具有了十分重要的意义。
最后，我要感谢Eric Milliren，他在过去的5年中让我花费了这么多的时间来写这本书，为我提供了滋润的家庭生活，并推迟了他自己的几个项目直到这本书即将完成。
从20世纪50年代中期以来，编译器设计就一直是计算机研究和开发中的活跃主题。第一个广泛使用的高级语言Fortran的成功在很大程度上归功于其早期高质量的编译器。John Backus和他在IBM的同事们认识到，除非编译器生成的代码与手工书写的机器代码的性能非常接近，否则程序员就不会放弃他们在使用汇编语言时所习惯采用的细节设计控制方法。Backus的小组创造了若干关键概念，这些概念构成了本书所研究问题的基础。这些概念包括循环优化中数组索引的处理和局部寄存器分配方法等。从那时起，研究人员和开发人员就一直不断用更有效的方法来改善和替代旧的方法。
既然编译器设计已有很长的历史，并且是一门相对成熟的计算技术，人们可能会问，为什么还要写一本有关此领域的新书？回答是明显的，编译器是一种生成由源程序至机器指令的高效映射的工具。语言的设计不断在变化，目标机体系结构也不断在变化，程序越来越复杂，其规模也越来越大。尽管编译器设计问题在高级层次上没有变化，但当我们深入其内部研究就会发现，它其实也一直在变化。此外，我们能够供编译器本身使用的计算资源也在增加。因此，现代编译器可以采用比以前更耗费时间和空间的算法。当然，研究人员也在继续开发新的、更好的技术来解决传统的编译器设计问题。事实上，本书中的所有主题都是计算机体系结构变化的直接结果。
本书迎接现代语言和体系结构的挑战，帮助读者做好准备，去应对将来难免要遇到的编译器设计的新问题。例如，第3章在读者把握了符号表和局部作用域的知识后，讲述了如何处理Ada、Modula-2和其他现代语言中的导入和导出作用域。而且，由于运行时的环境基本上规定了源语言的动态语义，第5章关于运行时支持的高级问题（如编译共享对象）的讨论也是特别有价值的。第5章还讨论了某些现代语言丰富的类型系统和现代体系结构所要求的种种参数传递策略。
任何一部关于编译器设计的书，如果没有介绍代码生成，它就是不完整的。早期的代码生成研究提供了设计手工书写指令选择例程的方法，以及如何在进行指令选择的同时管理寄存器的方法。本书第6章在讨论代码生成时，论述了基于模式匹配的自动化技术。这种自动化技术之所以成为可能，其原因不仅仅是编译器研究的进步，而且也是因为指令集已经变得更为简单和更为规整，以及编译器已经能够构造和遍历中间代码树。
优化是高级编译器设计的核心，也是本书的重点。有许多理论性的成果是关于程序分析的。程序分析的目的既是为了优化的安全，也是为了其他目的。本书第7~10章回顾了迄今为止的各种经典分析方法，同时也介绍了以前只在研究论文中出现过的更新和更有效的方法。这种综合本身就是对编译器设计的一个重要贡献。随后的许多章节都要使用这些分析来完成各种优化方法。
近代计算机系统具备由较多数量的寄存器构成的寄存器集合，这促成了第16章关于寄存器分配的讨论。这一章概括了近十年来在寄存器分配问题上的算法和启发式方法。另外，计算机速度提高的一个重要的原因是并行性，即同时做若干件事情的能力。为了将串行程序转换为可以利用硬件并行性的并行程序，编译器可能需要以既保证正确性又增加并行性的方式重排部分计算。尽管完整的并行处理超出了本书的范围，但本书集中讨论了指令级并行，这导致了第9章关于依赖分析和第17章关于代码调度的关键问题的讨论。
第20章论述存储层次优化，这也是由现代目标机引起的。为了克服处理器和存储器访问速度之间的差距，现代目标机引入了不同的数据访问速度。从本书出版商的网站上还可以得到额外的一章，它讨论了目标代码转换。这种转换是基于编译技术的，它将一个程序在已有体系结构上的目标代码转换为新体系结构的目标代码，即使该程序在新体系结构上的源程序还未出现。
由于新语言的设计一直鼓励程序员对大程序的结构化使用更为成熟的方法，过程间分析和优化的重要性也随之增加了。随着分析方法的不断精炼和调整，以及更快的计算机使得所需要的分析工作已经能够在可接受的时间内完成，这种分析和优化的可行性也增加了。第19章专门讨论过程间信息的确定和使用。
编译器设计本质上是一种工程活动，它所使用的方法必须很好地解决现实（即，用真实的语言书写的且在真实的机器上执行的真实的程序）中出现的各种翻译问题。多数情况下，书写编译器的人必须接受他们面对的语言和机器，很少能够影响和改善这两者的设计。做什么样的分析和转换，以及什么时候做它们都是工程上的选择，但正是这些选择决定了一个优化编译器的速度和质量。这些设计选择在贯穿全书的优化方法和第21章的实例研究中都得到了极为重要的处理和体现。
作者Steven S．Muchnick最大的优势之一是具有丰富而广博的经验。他早期曾是计算机科学教授，后来作为惠普的PA-RISC和Sun的SPARC两种计算机体系结构开发团队的核心成员，将自己的知识和经验应用于编译器设计。每一种体系结构的初始工作完成之后，他就担任了该系统的高级编译器设计与实现小组的负责人。 这些职业经历对他确定读者需要知道高级编译器设计的哪些内容很有帮助。他在研究和亲身开发方面的双重经验，对于指导读者做出编译器设计决策极具价值。
Susan Graham
加利福尼亚大学，伯克利分校
Steven S.Muchnick：Steven S.Muchnick: Steven S．Muchnick具有丰富而广博的经验。他曾经是计算机科学教授，‘后来他将自己的知识和经验应用于编译器设计，成为两种计算机体系结构(惠普的PA-RISC和Sun的SPARC)开发团队的核心成员，并担任这些系统的高级编译器设计与实现的领导人。他的研究和开发经验对于指导读者做出编译器设计决策极具价值。
赵克佳 沈志宇：暂无简介
本书被称为 “鲸书”，这一方面是因为它的英文原版书的封面是一张奇尔卡特毛毯的照片，而这张毛毯的图案是一条在水中潜游的鲸鱼；另一方面则是因为本书是有关编译技术的重要著作之一，被人们誉为与编译技术的经典代表作“龙书”（《Compilers: Principles,Techniques,and Tools》）齐名。
本书的作者Steven S．Muchnick在编译技术方面有着深厚的理论基础，又具有丰富而广博的经验。他以这样两方面的功力写成的这本书，对于从事编译器设计和实现的科技人员具有无法衡量的价值。本书的内容主要集中在编译器的后端以及编译优化实现方面，全面阐述了在编写一个真实的编译器时遇到的各种关键问题及解决方法，反映了近十多年来针对现代计算机体系结构而出现的各种新的编译优化技术，同时作者对仍在研究中的编译实现和优化热点问题也给出了很好的综述和参考文献。注重真实语言和真实体系结构的编译实现方法，注重对现代体系结构性能有重要影响的各种优化是本书的特点，而这正是国内已出版的编译方面的著述所缺乏的，该书的翻译出版填补了国内编译著作在这一方面的空白。对于已经学习过编译原理课程的高年级本科生和研究生而言，书中的内容为他们进一步了解真实编译器中的设计问题和实现技术开拓了视野，而对于想实现一个优化编译器和在编译技术领域进行深入研究的科研人员而言，作者在书中指出的工程上必须注意但容易被忽视的许多问题以及给出的大量有价值的实用方法，为他们进行工程实践提供了指导，也为他们指出了深入研究的方向。
能充分发挥现代并行体系结构性能的优化编译器是最复杂的软件系统之一。设计和实现一个优化编译器既是一项工程，又是一种艺术创造。而翻译这本关于高级编译技术的书，对于我们而言，既是一次学习，又是一种欣赏。通过翻译本书，我们对高级编译技术又进行了一次系统的学习，收获颇丰。编译器的设计和实现要遵循计算机科学技术的规律，编译器的功能要能适应体系结构和编程语言的特点，充分发挥它们的特性，而编译器内部各组件要能有机协调地工作。我们在研究和编写一个好的编译器时，就在欣赏着科学技术的美感。在翻译本书的过程中，我们也钦佩作者杰出的聪明才智，体会到了自然的辩证法。
在自然科学领域，计算机科学技术是一门很年轻的学科，但在计算机科学技术中，编译技术却是一个相对“古老”的研究方向。新技术层出不穷，引人入胜，需要有人去研究。但同时我们也认为，编译技术是计算机技术的重要组成部分，随着计算机新技术新理论的不断涌现，编译技术本身也在不断发展，也还有着无穷的奥秘等待着人们去探索。信息化是全面建设小康社会的必由之路，实现信息化必须真正掌握发展计算机技术的主动权，而编译技术如同微处理器和操作系统技术等一样，是计算机技术的关键，必须掌握在自己手中。通过翻译本书，我们愿为我国编译技术的发展献上一份绵薄之力。
本书的前言和第1、9、10、11章由沈志宇翻译，其余由赵克佳翻译。全书由沈志宇审校。国防科大软件研究所的黄春、王锋、张小强等老师，以及郭学鹏、张定飞等研究生阅读了本书的部分译稿，并给出了不少有价值的修改意见，特此致谢。
由于我们才疏学浅，在翻译中不当之处还恳请读者诸君不吝赐教。
译 者
2005年3月于国防科学技术大学
第1章 高级主题介绍 1
1.1 编译器结构回顾 1
1.2 基本问题中的高级论题 2
1.3 代码优化的重要性 4
1.4 优化编译器的结构 5
1.5 激进型优化编译器中各种优化的位置 7
1.6 本书各章的阅读流程 10
1.7 本书没有涉及的相关主题 10
1.8 例子中所用的目标机 11
1.9 数的表示与数据的大小 11
1.10 小结 11
1.11 进一步阅读 12
1.12 练习 12
第2章 非形式化编译算法表示 13
2.1 扩展的巴科斯-诺尔范式语法表示 13
2.2 ICAN简介 14
2.3 ICAN概貌 16
2.4 完整的程序 17
2.5 类型定义 18
2.6 声明 18
2.7 数据类型和表达式 19
2.7.1 一般简单类型 20
2.7.2 枚举类型 20
2.7.3 数组 21
2.7.4 集合 21
2.7.5 序列 22
2.7.6 元组 23
2.7.7 记录 23
2.7.8 联合 24
2.7.9 函数 24
2.7.10 编译专用的类型 24
2.7.11 值nil 25
2.7.12 size运算符 25
2.8 语句 25
2.8.1 赋值语句 26
2.8.2 过程调用语句 27
2.8.3 返回语句 27
2.8.4 goto语句 27
2.8.5 if语句 27
2.8.6 case语句 27
2.8.7 while语句 28
2.8.8 for语句 28
2.8.9 repeat语句 28
2.8.10 ICAN的关键字 28
2.9 小结 29
2.10 进一步阅读 29
2.11 练习 29
第3章 符号表结构 31
3.1 存储类、可见性和生命期 31
3.2 符号属性和符号表项 32
3.3 局部符号表管理 34
3.4 全局符号表结构 35
3.5 存储绑定和符号寄存器 38
3.6 生成取数和存数指令的方法 42
3.7 小结 46
3.8 进一步阅读 46
3.9 练习 47
第4章 中间表示 49
4.1 与中间语言设计有关的问题 49
4.2 高级中间语言 50
4.3 中级中间语言 51
4.4 低级中间语言 52
4.5 多级中间语言 52
4.6 我们的中间语言：MIR、HIR和LIR 53
4.6.1 中级中间表示（MIR） 53
4.6.2 高级中间表示（HIR） 56
4.6.3 低级中间表示（LIR） 57
4.7 用ICAN表示MIR、HIR和LIR 58
4.7.1 用ICAN表示MIR 59
4.7.2 用ICAN表示HIR 62
4.7.3 用ICAN表示LIR 64
4.8 管理中间代码的若干数据结构和例程的ICAN命名 67
4.9 其他中间语言形式 70
4.9.1 三元式 70
4.9.2 树 71
4.9.3 无环有向图（DAG） 72
4.9.4 前缀波兰表示 73
4.10 小结 74
4.11 进一步阅读 74
4.12 练习 74
第5章 运行时支持 77
5.1 数据表示和指令 77
5.2 寄存器用法 80
5.3 局部栈帧 81
5.4 运行时栈 83
5.5 参数传递规则 84
5.6 过程的入口处理、出口处理、调用和返回 86
5.6.1 用寄存器传递参数：平面寄存器文件 87
5.6.2 用运行时栈传递参数 88
5.6.3 用具有寄存器窗口的寄存器传递参数 89
5.6.4 过程值变量 91
5.7 代码共享与位置无关代码 91
5.8 符号和多态语言支持 94
5.9 小结 96
5.10 进一步阅读 96
5.11 练习 97
第6章 自动产生代码生成器 99
6.1 简介代码生成器的自动生成 100
6.2 语法制导技术 100
6.2.1 代码生成器 102
6.2.2 代码生成器的产生器 103
6.2.3 删除链循环 110
6.2.4 删除句法阻滞 112
6.2.5 最后的考虑 115
6.3 语义制导的分析介绍 115
6.4 树模式匹配和动态规划 116
6.5 小结 120
6.6 进一步阅读 120
6.7 练习 121
第7章 控制流分析 123
7.1 控制流分析的方法 125
7.2 深度为主查找、前序遍历、后序遍历和宽度为主查找 128
7.3 必经结点和后必经结点 132
7.4 循环和强连通分量 139
7.5 可归约性 143
7.6 区间分析和控制树 144
7.7 结构分析 147
7.8 小结 156
7.9 进一步阅读 157
7.10 练习 157
第8章 数据流分析 159
8.1 一个例子：到达-定值 159
8.2 基本概念：格、流函数和不动点 163
8.3 数据流问题及其解决方法的分类 166
8.4 迭代数据流分析 168
8.5 流函数的格 171
8.6 基于控制树的数据流分析 172
8.7 结构分析 172
8.7.1 结构分析：向前问题 172
8.7.2 结构分析：向后问题 178
8.7.3 结构分析方程的表示 180
8.8 区间分析 181
8.9 其他方法 182
8.10 du链、ud链和网 183
8.11 静态单赋值形式 184
8.12 数组、结构和指针的处理 188
8.13 数据流分析器的自动构造 188
8.14 更贪婪的分析 189
8.15 小结 191
8.16 进一步阅读 192
8.17 练习 192
第9章 依赖关系分析和依赖图 195
9.1 依赖关系 195
9.2 基本块依赖DAG 196
9.3 循环中的依赖关系 200
9.4 依赖关系测试 204
9.5 程序依赖图 207
9.6 动态分配的对象之间的依赖关系 209
9.7 小结 210
9.8 进一步阅读 211
9.9 练习 211
第10章 别名分析 213
10.1 各种现实程序设计语言中的别名 215
10.1.1 Fortran 77中的别名 216
10.1.2 Pascal中的别名 216
10.1.3 C中的别名 217
10.1.4 Fortran 90中的别名 218
10.2 别名收集器 218
10.3 别名传播器 222
10.4 小结 227
10.5 进一步阅读 227
10.6 练习 228
第11章 优化简介 229
11.1 第12~18章讨论的全局优化 230
11.2 流敏感性和可能与一定信息 231
11.3 各种优化的重要性 231
11.4 优化的顺序与重复 232
11.5 进一步阅读 235
11.6 练习 235
第12章 前期优化 237
12.1 常数表达式计算（常数折叠） 237
12.2 聚合量标量替代 238
12.3 代数化简和重结合 240
12.3.1 地址表达式的代数化简和重结合 241
12.3.2 对浮点表达式应用代数化简 246
12.4 值编号 247
12.4.1 作用于基本块的值编号 247
12.4.2 全局值编号 251
12.5 复写传播 256
12.6 稀有条件常数传播 261
12.7 小结 267
12.8 进一步阅读 269
12.9 练习 269
第13章 冗余删除 271
13.1 公共子表达式删除 271
13.1.1 局部公共子表达式删除 272
13.1.2 全局公共子表达式删除 276
13.1.3 向前替代 284
13.2 循环不变代码外提 284
13.3 部分冗余删除 292
13.4 冗余删除和重结合 298
13.5 代码提升 299
13.6 小结 302
13.7 进一步阅读 302
13.8 练习 304
第14章 循环优化 305
14.1 归纳变量优化 305
14.1.1 识别归纳变量 306
14.1.2 强度削弱 312
14.1.3 活跃变量分析 319
14.1.4 归纳变量删除和线性函数测试替换 320
14.2 不必要边界检查的消除 325
14.3 小结 327
14.4 进一步阅读 329
14.5 练习 329
第15章 过程优化 331
15.1 尾调用优化和尾递归删除 331
15.2 过程集成 334
15.3 内嵌扩展 337
15.4 叶例程优化和收缩包装 338
15.4.1 叶例程优化 338
15.4.2 收缩包装 339
15.5 小结 341
15.6 进一步阅读 343
15.7 练习 343
第16章 寄存器分配 345
16.1 寄存器分配和指派 345
16.2 局部方法 346
16.3 图着色 347
16.3.1 图着色寄存器分配概述 347
16.3.2 顶层结构 349
16.3.3 网，可分配对象 350
16.3.4 冲突图 354
16.3.5 冲突图的表示 355
16.3.6 寄存器合并 358
16.3.7 计算溢出代价 359
16.3.8 修剪冲突图 361
16.3.9 指派寄存器 363
16.3.10 溢出符号寄存器 365
16.3.11 图着色寄存器分配的两个例子 367
16.3.12 其他问题 375
16.4 基于优先级的图着色 376
16.5 其他寄存器分配方法 377
16.6 小结 377
16.7 进一步阅读 378
16.8 练习 380
第17章 代码调度 381
17.1 指令调度 381
17.1.1 分支调度 382
17.1.2 表调度 385
17.1.3 自动生成指令调度器 390
17.1.4 超标量实现有关的调度 390
17.1.5 基本块调度中的其他问题 390
17.1.6 跨基本块边界的调度 392
17.2 前瞻取和上推 392
17.3 前瞻调度 393
17.4 软流水 393
17.4.1 窗口调度 395
17.4.2 展开-压实软流水 397
17.4.3 循环展开 400
17.4.4 变量扩张 403
17.4.5 寄存器重命名 404
17.4.6 软流水的其他方法 407
17.4.7 层次归约 407
17.5 踪迹调度 408
17.6 渗透调度 409
17.7 小结 411
17.8 进一步阅读 413
17.9 练习 413
第18章 控制流和低级优化 415
18.1 不可到达代码的删除 415
18.2 伸直化 417
18.3 if化简 419
18.4 循环化简 420
18.5 循环倒置 421
18.6 无开关化 422
18.7 分支优化 422
18.8 尾融合或交叉转移 423
18.9 条件传送 424
18.10 死代码删除 425
18.11 分支预测 429
18.12 机器方言和指令归并 430
18.13 小结 433
18.14 进一步阅读 433
18.15 练习 435
第19章 过程间分析与优化 437
19.1 过程间控制流分析：调用图 438
19.2 过程间数据流分析 445
19.2.1 流不敏感副作用分析 445
19.2.2 流敏感副作用：程序概要图 455
19.2.3 副作用计算中的其他问题 458
19.3 过程间常数传播 458
19.4 过程间别名分析 461
19.4.1 流不敏感别名分析 462
19.4.2 传值和传指针语言的过程间别名分析 471
19.5 过程间优化 473
19.6 过程间寄存器分配 475
19.6.1 连接时的寄存器分配 475
19.6.2 编译时的过程间寄存器分配 477
19.7 全局引用的聚合 477
19.8 过程间程序管理中的其他主题 478
19.9 小结 478
19.10 进一步阅读 480
19.11 练习 480
第20章 存储层次优化 483
20.1 数据和指令高速缓存的影响 484
20.2 指令高速缓存优化 485
20.2.1 利用硬件辅助：指令预取 485
20.2.2 过程排序 485
20.2.3 过程和基本块的放置 489
20.2.4 过程内的代码安置 489
20.2.5 过程分裂 492
20.2.6 过程内和过程间方法的结合 492
20.3 数组元素的标量替换 493
20.4 数据高速缓存优化 496
20.4.1 过程间的数据安排 497
20.4.2 循环转换 498
20.4.3 局部性与循环铺砌 502
20.4.4 利用硬件辅助：数据预取 504
20.5 标量优化与面向存储器的优化 505
20.6 小结 506
20.7 进一步阅读 508
20.8 练习 508
第21章 编译器实例分析与未来的发展趋势 509
21.1 Sun用于SPARC的编译器 510
21.1.1 SPARC体系结构 510
21.1.2 Sun SPARC编译器 511
21.2 IBM POWER和PowerPC体系结构的XL编译器 517
21.2.1 POWER和PowerPC体系结构 517
21.2.2 XL编译器 518
21.3 DEC用于Alpha的编译器 524
21.3.1 Alpha体系结构 524
21.3.2 Alpha的GEM编译器 525
21.4 Intel 386体系结构上的Intel参考编译器 530
21.4.1 Intel 386体系结构 530
21.4.2 Intel编译器 531
21.5 小结 538
21.6 编译器设计和实现未来的趋势 539
21.7 进一步阅读 539
附录A 本书使用的汇编语言指南 541
附录B 集合、序列、树、DAG和函数的表示 549
附录C 软件资源 557
参考文献 561
索引 579
