本书介绍对现代体系结构的编译器进行优化的方法，理论基础是基于循环依赖的。分析基于依赖的变换的正确性论述和依赖测试的详细过程。剖析怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书还讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构（例如，向量、多处理器、超标量）的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人熟知的应用，如硬件设计、数组语言实现以及消息传递系统的编译。
本书特点：
提供一份简单实用的算法和方法的指南，它们在高性能微处理器和并行系统真实领域中是最有效的
用处理过的例子示范每个变换
考察两个实例研究编译器如何实现每一章中描述的理论和实践
介绍任何编译器教科书都要论及的存储层次结构问题的最完善的处理
贯穿全书用依赖图来阐明排序关系
将技术应用到各种语言，包括Fortran 77,C, 硬件定义语言，Fortran 90和High Performance Fortran
对研究工作中知名的最精巧的算法提供广泛的参考文献
无
现代体系结构的编译器设计
影响人们对世界理解的主要方面之一是描述它的方法，人们往往借助于语言中的概念表述来传达他们的理解。在使用计算机语言时这更为明显。计算机科学家使用的语言影响着问题描述到最终实现的算法方法。LISP程序员解决问题的方法与IBM 370汇编程序员的方法就很不相同。
可见语言在应用设计中具有强烈影响，而高级语言具有内在的高效优点，语言研究的主要目标是开发人类更容易理解的计算机语言。尽管语言研究获得的成果使之更容易使用，但是在产品应用的开发中未被广泛采用。主要原因很简单：有效性—从这些语言写的代码产生的可执行程序对于产品使用太慢。而且，如果一个问题描述超出了计算机本机指令，将这些描述映射到指令集则变得更加困难。
如果我们曾经有过这样的实际语言，先进编译器技术将成为克服它们固有性能缺陷的基础工具。换句话说，编译器优化是使用高级语言的基本保证技术。数据依赖是基本的编译器分析工具，用来优化现代机器体系结构上的程序，因为它能使编译器对不同的代码段是否访问相同的或不同的存储单元进行推断。这样可以用它来确定一个给定的程序是否可以并行化，或者可以更加频繁地重用在寄存器和高速缓存中的数据。至今初级编译器课程中很少讲授依赖分析。这样，大多数大学生计算机科学主修课从不讲述。
本书的一个主要目标是集中在一册书里对数据依赖作广泛的介绍，它可以同样由从业人员和学生们用于学习关于数据依赖及其对重要优化问题的应用，如并行化和编译器的存储分层结构管理。虽然在20世纪60年代编译器早期研究人员就提出了数据依赖，大多数有说服力的依赖应用是在使用循环和数组的情况下。这些结构本质上是重复计算，而重复计算提供了最适宜的优化场所。扩充依赖到支持数组和循环是本书的关注点。
这本著作介绍的理论基础是基于循环依赖的。它包括基于依赖的变换的正确性论述和依赖测试的详细过程。说明怎样扩展依赖去处理循环嵌套中的控制流以及跨越整个程序的过程。本书也讨论怎样能用依赖来回答现代计算机系统编译中的众多重要问题，包括支持不同类型体系结构（例如，向量、多处理器、超标量）的并行化，存储层次结构的编译器管理，带指令级并行性的机器的指令调度。最后，介绍一些不大为人们熟知的应用，包括硬件设计、数组语言的实现以及消息传递系统的编译。
除了基本理论，本书还应用依赖处理真实编译器优化中的实际问题。通过介绍一些有效的实现算法，以及我们从结合研究和商用实现的经验中获得的认识，达到上述目的。只要有可能我们就用例子来传授这些认识，经常用图形化的依赖关系描述来传授对讨论中的问题的直观理解。本书介绍的大多数算法是基于我们工作中已经构造的实现。设计的这些算法已达到很高的精度，不需要再花运行时间就可以将它们放在编译器中实际使用。最后，每章包含一些材料，按照我们自己的经验，讨论我们介绍的和已经付诸实现的东西之间的关系，包括优点和缺点。
由于本书将理论与实践融合一体，既适合作为学校的教科书，又可以作为产业界从业人员的参考书。我们仅假定读者了解大学的初级编译器课程，以及具有Hennessy和Patterson的《Computer Organization and Design：The Hardware/Software Interface》水平的机器设计原理。过去几年，我们在Rice大学开设了一门一学期的研究生课程，内容涵盖本书的所有材料。然而我们相信这些材料也适宜包含在一门大学高年级课程中。本书是按指导风格写成的，使读者能获得足够的见解，容易去理解介绍的概念。另外，书中包含为了帮助学生更清楚地思考那些基本问题的讨论和设计的习题。
为了符合商用编译器作者的需要，书中包含对依赖测试和变换算法的详细介绍。这样做的主要理由是可以让实际编译器开发者避免过去20多年我们自己在实现中遇到过的陷阱。例如，第3章中的依赖测试的细节如果从首要的原理推导，那么往往很难精确地得到正确结果。因此在可能时，我们尽力介绍完整的算法。使用书中包含的材料，我们已帮助一些公司在商业产品中实现依赖测试、向量化和并行化。我们确信这些策略在实践中是有效的。
本书是在Rice大学一个为期20年的研究项目的产物，该项目为向量和并行计算机系统研发基础的编译技术。在1979年开始这个研究项目时，我们相信源-源翻译器对向量机的支持才是必要的，而不是基于依赖的编译器。理由是基于实验：依赖实现需要的编译时间对实用来说太长了，并且它们的输出通常可以通过简单的检查加以改善。我们认为在产品编译器中太长的编译时间需求是不能容忍的，但对只做一次的源-源翻译器来说是很好的。此外，可以让有经验的程序员调整源-源翻译器的输出，使之达到更佳的性能。我们研究的最令人满意的结果之一，在于发现我们最初的设想何等错误—依赖不仅对产品编译器是有效的，而且比起我们最初的猜想，它是更加强有力的工具和可用的理论。任何现代优化编译器已将依赖作为基本构件，并且优化的结果不仅应用于向量机（它们做得极为出色），而且也应用于标量机，甚至应用到硬件设计中。
因为机器设计的不断进步，人们对几年前看起来似乎过时的论题（例如向量化），现在重新发现了它们的重要性。向量化方法对改善VLIW和超标量机的性能还是有用的，办法是在最内层循环提供额外的指令级并行性。然而，由于更加重要的原因这本书是适时的。因为处理器和存储器性能之间的距离增加了，在现代体系结构上必须实施的多数优化与存储访问有关。依赖提供一个关于存储访问的合理框架，它将继续增加有用性。
虽然我们打算覆盖许多研究人员的重要工作，但是我们自然将注意力集中在过去二十几年里作者和同事们于Rice大学做过的工作上。总之，我们的目标是将我们从该领域的经历中获得的综合知识付印。因此不应该将本书看成是文献的详尽的综述，而是开发基于依赖的编译器的实用指南。为表达清楚，有时不得不牺牲一些技术细节。我们的总目标是给读者充分的直观知识，使其在编译技术这个引人入胜的领域中能有效地工作。
内容概述
本书由14章组成，它们的内容在下面各段中概述。材料的核心包含在前9章中；余下各章集中于基本材料的扩充和在不同的问题领域的应用。
第1章，高性能体系结构对编译器的挑战，是对现代计算机体系结构所做的综述和分类，并讨论对每一类体系结构提出的主要编译挑战。重要的主题包括流水线并行性，向量指令，异步处理器并行性，超标量指令和VLIW指令，以及存储层次结构管理。引入依赖概念作为保证并行性安全使用的机制。
第2章，依赖：理论与实践，讨论依赖的基本概念，以及它的若干性质，包括方向向量和距离向量。主要的目标是证明一些基本定理，它们确立维持依赖的变换的正确性，特别是在循环嵌套中。这一章以一个样例向量化算法结束，算法说明依赖的有用性，并用作后面讨论向量化和并行化的模型。
第3章，依赖测试，提供对引用偶之间测试依赖的系统介绍。包含对下标分类、单下标测试和耦合下标组中依赖测试的讨论。这部分材料强调在可能的地方彻底地消除一个依赖，并得到尽可能接近的依赖性质，如方向向量。
第4章，初等变换，覆盖精确依赖分析的基本变换，包括循环正规化，标量数据流分析，表达式传播和替换，归纳变量替换，以及标量重命名。
第5章，提高细粒度并行性，集中于需要支持向量指令和VLIW或超标量处理器的内循环并行性。这一章探讨对第2章中介绍的分层并行代码生成过程的变形和扩展。特别将重点放在循环交换、标量扩展、结点分裂，数组重命名和向量化过程中的循环倾斜。
第6章，开发粗粒度并行性，探讨对称多处理器的代码生成策略，在一致共享存储系统中利用异步并行性。这种机器的主要问题是寻找充足大并行性粒度，以补偿较高的任务启动和同步的代价。这个代价是必须交换一个并行循环到最外层合法位置，而不是向量化需要的最内层位置。这一章探讨循环交换的使用、数组私有化、循环对齐和代码复制、循环倾斜和各种索引集分裂策略，以达到在原始程序中寻找可用并行性的目的。
第7章，处理控制流，探讨在程序的分析和变换中由分支引入的复杂性。它深入地讨论两个重要的策略。第一个策略是if转换，这是一种通过将控制流分支下的所有语句转换成条件赋值语句来消除控制流的机制。为支持向量化引入的if转换，是重写条件语句为向量语句所需要的。第二个策略是使用控制依赖边，它们是从条件语句到执行时依赖于它们的那些语句的边。这一章证明如果数据依赖和控制依赖都得到遵从，那么程序的含义便得到维持。最后，该章说明控制依赖如何适应标准的变换算法，包括并行代码生成算法。
第8章，改进寄存器的使用，说明依赖（正确地讲扩展到包含输入依赖）是怎样的一种有效方法，用来探测处理器的寄存器中数据重用的可能性。这一章介绍标量替换，本质上它是将下标变量引用赋给一个寄存器。另外还论述改善各层重用的变换，包括展开和压紧、循环交换、循环对齐和循环合并。
第9章，管理高速缓存，越过简单的数据重用，探讨改善带有高速缓存存储层次结构机器性能的变换。虽然大多数改善寄存器重用的变换也能增强高速缓存的重用，但高速缓存存储器更加复杂，因为它们比典型的寄存器集合要大许多，并且是在若干个字的块中处理数据。这些不同为一些变换提供了机会，如分段循环嵌套使它在适合装在高速缓存的数据集上进行迭代，以及在内循环中引起跨距为1的访问的循环交换。这一章还探讨软件预取—使用显式指令，将数据块在需要用它们之前从存储器移到高速缓存中。
第10章，调度，论述几种基于依赖的方法，通过编译时指令布置来改善超标量机器和VLIW机器的性能。主题包括表调度、踪迹调度、软件流水线和向量操作链接。
第11章，过程间分析和优化，讨论扩展编译器分析（包括依赖分析）的策略到整个程序。这一章介绍分析几个重要的过程间问题的算法，包括副作用、别名和常数传播。然后说明如何将副作用分析扩展到数组子段上。其他主题包括过程间优化（如内联替换和过程克隆），以及过程间分析和优化的管理。
第12章，C语言和硬件设计中的依赖，应用本书中介绍的分析策略到两个新的问题领域。第一个领域是应用依赖测试和程序变换优化C程序。第二个领域是将依赖应用到硬件设计上，包括加速设计模拟的方法和从高层抽象规格说明综合低层硬件的方法。
第13章，编译数组赋值，其中的材料涵盖的方法为Fortran 90中数组赋值语句在标量机和具有定长向量寄存器机器上的实现。主要主题是将数组赋值语句转换成不需要无限制的临时存储的标量循环。
最后一章，编译高性能Fortran，应用依赖分析从高性能Fortran生成有效的消息传递代码，高性能Fortran是Fortran 90的变体，它包含说明如何在一可伸缩并行计算机的存储器中布局数组数据的设施。主题包括根据拥有者计算规则的计算划分和通信生成及优化。
这十四章包含的材料，可以用几种不同的方法组织成多个课程。作为一门高年级的大学生课程，第2章至第7章提供并行化中有关问题的合理的完整的论述。作为集中于单处理器优化的课程，可以跳过第5章中的某些材料（5.1节、5.2节和5.7～5.9节除外，这几节涵盖重要的变换），第6章（6.2节和6.3节除外），以利于包含第8章和第9章。另一方面，熟悉并行化的读者可能想了解其他的应用，包括存储层次结构管理，这方面的内容集中在第8章到第10章，以及第12章到第14章。如前所说，我们已成功地在Rice大学开设的一个学期的研究生课程中讲授本书中的所有材料。
我们力求使本书成为自含的，只假设读者熟悉编译器和机器设计的基础。这种期望必须包含第4章中关于数据流分析（4.4节）的某些材料，它们可能会包含在一门基础编译器课程中。我们感觉到在书中包含这些材料是重要的，所以你能在依赖和变换理论的上下文中看到它们。我们希望在使本书具有可读性和包含针对编译课程的高年级大学生和实际编译器编写者的主题上已获得成功。
每章的结构和特色
我们尽力使每章结构一致。每章包含一个引言，在开始论述详细的技术之前，提供主题的概述。引言通常用例子说明一章将要回答的问题。
技术材料按指导的风格介绍，包括用依赖图说明许多例子。使用变换“前和后”的代码序列描述各种变换。我们介绍程序变换的完整算法，使实践者根据这些材料开发一个编译器的实现变得简单明了。多数情况下，这些算法是在我们自己的研究和商用系统中已实现的直接变体。为有效地处理大程序，我们力求在这些实现中保证算法有可接受的渐进的复杂度。算法是用直观的类Algol表示法表示的，这种表示法对规格说明非常有用。然而，我们增加了某些特殊的构造，用于在元素集合上的迭代（例如，for each循环），这有助于我们回避说明集合实现的细节。
每章的末尾是一个小结，回顾这一章涵盖的要点。随后是实例研究，介绍我们在真实实现中的材料，以及有关策略有效性的实验论据。这里，你将可以找到有关产品编译器需要的设计折衷处理方案的材料。最后一节是历史评述与参考文献，回顾相关的文献，讨论一章中介绍的概念的由来和发展，具体参考文献的引文可以在本书的末尾找到。
在每一章的结尾是少量习题，这是针对书中内容为我们的研究生课程设计的。这些习题的范围从对材料的简单练习到实现作业和研究问题。
辅助的在线材料
与本书关联的网页（www.mkp.com/ocma/）包含勘误表。
致谢
本书是在Rice大学20年研究的产物，而这项研究又依赖在其他学术机构多年做的相关研究工作。本书本身的发展过程已有10年并使用了6种不同的字处理系统。如此大量的工作必然要依靠两位作者以外的更多人的工作，我们要感谢许多人，他们以自己的工作和思想对本书做出了贡献。
列在这张名单前面的是Rice大学过去的博士生们，他们的研究确定了本书的大部分内容。学生们的论文材料直接包含在各章中，他们是Vasanth Bala、David Callahan、Steve Carr、Keith Cooper、Ervan Darnell、Chen Ding、Gina Goff、Mary Hall、Paul Havlak、Kathryn McKinley、Allan Porterfield、Carl Rosene、Jerry Roth、Linda Torczon、Ajay Sethi和Chau-Wen Tseng。特别要感谢贡献习题的人们：Chen Ding、Kathryn McKinley和Jerry Roth。同样重要的是众多的研究生、大学生以及研究和技术人员，他们对PFC，ParaScope，D系统和Ardent Titan编译器的开发做出了贡献。这些人中，我们要特别感谢协助领导了这些开发项目的技术人员：Vikram Adve、David Callahan、Keith Cooper、Mary Hall、Seema Hiranandani、Steve Johnson、Kathryn McKinley、John Mellor-Crummey和Linda Torczon。
另外，在开发这个材料的过程中与杰出的同事们密切地交流使我们获益匪浅。在开发PFC的过程中，IBM的Randy Scarborough花了大量的时间与我们一起工作，提供给我们作为一位有阅历的业界编译器开发人员的很多见解和观点。Ben Wegbreit在Ardent Titan编译器开发过程中给我们带来许多令人兴奋的讨论，Steve Wallach在他的Convex向量化编译器开发过程中与我们交流，导致对我们的方法的很多改进，包括我们对C的关注。
其他应当特别提到的是那些对优化和依赖的理论与实践基础做出贡献的研究人员。这些研究人员（我们不受约束地汲取了他们的工作成果）包括Leslie Lamport、David Kuck、Utpal Banerjee、Michael Wolfe、Ron Cytron、John Cocke、Jack Schwartz、Frances Allen、Susan Graham、Monica Lam以及其他很多人。
没有IBM、国家科学基金会、国防部高级研究计划局以及能源部（通过Los Alamos计算机科学研究所）的经费支持，就不能完成本书的研究工作。我们很幸运有一支强大的程序管理员队伍，他们不仅帮助指导研究，还提供有力的精神支持。这些管理员包括Horace Flatt、Fred Ris、Bill Harris、Kamal Abdali、Rick Adrion、Gil Weigand、Bob Lucas、Frederica Darema和John Reynders。
本书写作的一个重要部分是用于研究生程度的课程。我们非常感谢那些学生和指导老师，他们忍受由于最初版本中错误带来的麻烦，并对我们造成的许多错误提出反馈意见。由于他们提出的改进意见，使本书成为非常优秀的著作。
本书的出版得到了Morgan Kaufmann的编辑们令人惊叹的帮助。Emilia Thiuri在本书准备出版的过程中提供一贯的和有力的支持。Edward Wade耐心和持久地关注每个细节，对本书从内容到外观的卓越性是极为重要的。稿件编辑Ken DellaPenta完成了校正书中错误的出色工作，保证书的表述的一致性。其余制作人员—排版员Nancy Logan、校对员Jennifer McClain和索引编写员Ty Koontz—对最后的质量做了巨大贡献。我们还要对Rebecca Evans & Associates公司的内部设计和Ross Carron Design公司的封面设计表示感谢，对Dartmouth Publishing出版社所绘制的精美插图表示感谢。
复审人员Tarek Abdelrahman、Benjamin Goldberg、Kathryn McKinley、Steven Carr、Allan Porterfield、Andrew Chien、Monica Enand、Rohit Chandra和Bill Appelbe对这册书的结构和内容的改进提出了许多有益的建议。深深地感谢我们的编辑Denise Penrose，没有他的耐心而又坚定的指导和积极的支持态度，不可能完成此书。
最后也是最重要的，我们要感谢我们的家庭，感谢他们的耐心和鼓励，以及他们带给我们的安定生活。我们的妻子Vicky Allen和Carol Quillen对我们难以置信地支持，即使这意味着我们必须长时间把注意力放在别处。当我们处于重大压力下时，她们保持在我们的周围。Jennifer和Caitlin的降生几次延缓写作进程，但是他们使生活更加愉快和满足。
Randy Allen和Ken Kennedy编写的“现代体系结构的优化编译器”一书是并行优化编译技术领域中一部权威性的著作。有幸由乔如良教授和张兆庆教授将全书译成中文，无疑对国内这一领域的教学、科研和工程的发展有着深远意义。
编译优化理论和技术是决定现代高性能计算机发展的十分关键的技术领域之一。优化编译技术的研究发展是和先进计算机结构—从微处理器到超级计算机—紧密相关联的。纵观优化编译技术最为超前的美国，各大学和科研机构中对这一领域的研究多是以电脑主流制造业的密切支持与合作研究为背景的。先进计算机体系结构和编译优化技术真可说是休戚与共、缺一不可。
本书的两位作者是长期从事优化编译技术研究的知名专家。特别是K. Kennedy教授更是学术界公认的泰斗。肯尼迪教授领导主持的一系列优化编译课题，既具有杰出的技术水平，又有着重大的学术影响。早在20世纪70年代末期，肯尼迪的研究工作对自动向量化编译技术的奠基和发展起过重大作用。80年代，肯尼迪和他在RICE大学的研究室对自动并行编译技术的贡献更为卓著。例如，他们在过程间优化的研究成果首创被商用编译器成功采用的先例。
基于他在学术上的成就和对计算机界的卓越贡献，肯尼迪教授先后被选为美国国家工程学院（National Academy of Engineering）院士，美国高科技协会（American Association for Advanced of Science）院士，IEEE院士和美国计算机学会（ACM）院士。肯尼迪教授在其三十多年的学术历程中，亲自指导了三十多名博士生。其中许多都是优化编译技术领域的精英，大多在知名大学任教或成为工业界的骨干。这本巨著中的许多内容正是作者和他的学生们多年经验的结晶。1997年，肯尼迪被美国总统任命为HPCC委员会两主席之一。
张、乔二教授是国内优化编译方面的资深专家和学术带头人。他们主持领导的中国科学院计算所先进编译技术试验室曾承担多项这一领域中重大长期研究项目，成果硕硕。近年来承担的Motorola和Intel等大公司委托的优化编译技术上的工程项目在国际上也颇具影响。由张、乔二教授和冯晓兵、吴承勇、连瑞琦、刘主持本书的翻译本出版是中国计算机学术界的一件大喜事，值得我们庆贺。
我有幸与Kennedy教授及张、乔、冯、吴等译者相识多年，这次能为这本书的中译本做序是我的荣幸。希望我的寥寥数言能有助于本书在国内计算机界广为推广。
(美)Ken Kennedy,Randy Allen：Ken Kennedy: Randy Allen以优异成绩获得Harvard大学化学专业学士学位，在Rice（赖斯）大学获得数学科学硕士和博士学位。成为Rice大学研究员之后，Allen博士参加了业界编译器构造的实践活动。他经历了在Ardent Computers、Sun Microsystems、Chronologic Simulation、Synopsys和CynApps等公司的研究、高级开发以及管理工作。他本人以及和他人合作在各种学术会议和杂志上发表了15篇关于计算机优化、编译器重构和硬件模拟等方面的论文。他出任Super-computing和Conference on Programming Language and Design Implementation等会议的程序委员会成员。目前，他是几家公司（包括IBM、Intermetrics、Microtes Research和Mentor Graphics）的优化编译器顾问，是Catalytic Compilers公司总裁和CEO。
Randy Allen: Ken Kennedy是Rice大学计算工程的Ann and John Doerr教授和高性能软件研究中心（HiPerSoft）主任。他是电气和电子工程师学会（IEEE）、计算机协会（ACM）以及美国科学促进会协会（AAAS）的会士，自1990年起，他是美国工程院院士。从1997年到1999年，任美国总统信息技术顾问委员会（PITAC）副主席。由于他在拟定关于建立信息技术研究基金的PITAC报告中的领导作用，获得计算研究协会杰出贡献奖（1999）和RCI Seymour Cray HPCC Industry Recognition奖（1999）。Kennedy教授发表了150多篇学术论文，并指导34篇有关高性能计算机系统程序设计支撑软件的博士论文。他对高性能计算软件方面的贡献得到了公认，1995年他获得W.Wallace McDowell奖，这是IEEE Computer Society的最高研究奖项。1999年他被提名为ACM SIGPLAN程序设计语言成就奖的第三位接受者。
张兆庆 乔如良 冯晓兵 吴承勇 连瑞琦 等：吴承勇: 副教授，硕士生导师，内蒙古大学计算机学院副院长，自治区信息产业专家小组成员，内蒙古教育和科研网专家组成员。1982年毕业于内蒙古大学电子系，1988年获国防大学硕士学位。长期从事计算机的教学科研工作，主讲计算机网络等课程。
Intel公司David Kuck院士在评论Ken Kennedy和Randy Allen的新书“Optimizing Compilers for Modern Architectures：A Dependence-Based Approach”时，这样写道：“编译程序是计算机科学与技术的皇后。编译器一直是应用与系统之间的桥梁。现在它们不仅决定应在新的硬件中实现哪些体系结构特色，而且说明对软件开发者而言，哪些新的语言特色将是有效的。”
Kuck院士和Kennedy教授都是并行优化编译理论与实践方面的最著名学者。Kuck将编译程序称为“计算机科学与技术的皇后”是十分恰当的。
自1958年ALGOL58问世后，20世纪60年代在程序设计语言理论、数据结构、算法设计与分析、可计算性理论等方面的研究，取得了令人惊叹的硕果，编译理论、技术和实验起了很大的推动作用。至今编译领域中仍有很多具有挑战性的问题，吸引广大计算科学与技术研究人员投身于此项事业。
现代计算机体系结构大都具有各种粒度的并行机制和分层存储结构，访存仍是当今各类计算机体系结构的瓶颈。优化编译器的主要任务可以说是：扬计算机结构之长—挖掘程序中的并行性，避其之短—挖掘程序的局部性（重用性），实施有效的寄存器分配和Cache管理。这正是Kennedy和Allen在书中讲述的主要内容。第5章（提高细粒度并行性），第6章（开发粗粒度并行性），第8章（改进寄存器的使用），第9章（管理Cache）和第10章（调度）是优化的主要手段。第2、3、4章是全书的理论基础和基本的程序变换方法。为使程序分析和优化更精确和有效，第7章和第11章是必须的，但它们增加了编译器的实现难度。最后三章可以看成是编译技术的特定应用。
Kuck院士在他的评论中接着写道：“作为该领域的创新者和研发者，作者依据丰富的经验写出了此书。该书对Cache管理、向量化、并行化等优化，做了非常好的综合。论题涉及到现代体系结构，这些题材确实可以应用于从台式计算机到世界上最快的超级计算机上。书中的例子是从Fortran中抽取出来的，但其理论可以应用到许多程序设计语言上。我认为该书将起到极好的教科书作用，并为软件开发者广泛地利用。”
正如Kuck院士所说，书中用大量的Fortran例子说明基本概念、理论、方法和优化的效果，使全书通俗易懂。每章的后面有一节实例研究，介绍作者在编译器的实践中的真实材料，以及有关策略有效性的实验论据。最后还有若干练习题。这些材料和习题无论是对学生，还是对学术界、工业界的软件开发者都大有益处。这里软件开发者不仅指编译器的设计与实现者，还包括应用软件开发者。他们可以从中学到如何写一个优化程序的许多概念、方法和规范，特别是应使用程序设计语言中那些有效的语言成分，摒弃那些使程序可读性、可维护性差和难以优化的语言成分。
我们希望此书的翻译出版，能对我国高校的软件教学与科研有所帮助。这是我们翻译此书的初衷。
本书的翻译组织工作由张兆庆研究员全面负责。作者介绍、前言、前四章和附录由张兆庆和乔如良研究员译校，第5、6章由刘博士翻译，第7、11、12章由连瑞琦副研究员翻译，第8、10章由吴承勇副研究员翻译，第9、13、14章由冯晓兵副研究员翻译。译者自知水平有限，译文中难免有不妥之处，敬请读者批评指正。
感谢机械工业出版社组织翻译这部巨著，感谢李伯民老师仔细阅读译稿，提出许多宝贵意见，并对译稿做了大量编辑加工。
译 者
2003年11月25日
第1章 高性能体系结构对编译器的挑战 1
1.1 概述和目标 1
1.2 流水线 3
1.2.1 流水线指令部件 3
1.2.2 流水线执行部件 4
1.2.3 并行功能部件 5
1.2.4 标量流水线编译 5
1.3 向量指令 7
1.3.1 向量硬件概述 7
1.3.2 向量流水线编译 8
1.4 超标量处理器和VLIW处理器 9
1.4.1 多发射指令部件 9
1.4.2 多发射处理器的编译 10
1.5 处理器并行性 11
1.5.1 处理器并行性概述 11
1.5.2 异步并行性的编译 12
1.6 存储层次结构 14
1.6.1 存储系统概述 14
1.6.2 存储层次结构的编译 15
1.7 实例研究：矩阵乘法 15
1.8 先进编译技术 19
1.8.1 依赖 19
1.8.2 变换 20
1.9 小结 21
1.10 实例研究 21
1.11 历史评述与参考文献 21
习题 22
第2章 依赖：理论与实践 23
2.1 引言 23
2.2 依赖及其性质 23
2.2.1 存-取分类 24
2.2.2 循环内的依赖 25
2.2.3 依赖和变换 26
2.2.4 距离向量和方向向量 29
2.2.5 循环携带依赖和循环无关依赖 31
2.3 简单的依赖测试 36
2.4 并行化和向量化 38
2.4.1 并行化 38
2.4.2 向量化 39
2.4.3 一个先进的向量化算法 41
2.5 小结 44
2.6 实例研究 44
2.7 历史评述与参考文献 44
习题 45
第3章 依赖测试 47
3.1 引言 47
3.2 依赖测试概述 51
3.2.1 下标划分 51
3.2.2 合并方向向量 52
3.3 单下标依赖测试 52
3.3.1 ZIV测试 53
3.3.2 SIV测试 53
3.3.3 多归纳变量测试 61
3.4 耦合组中的测试 73
3.4.1 Delta测试 73
3.4.2 更强有力的多下标测试 79
3.5 实验研究 80
3.6 各种测试的集成 81
3.7 小结 86
3.8 实例研究 86
3.9 历史评述与参考文献 87
习题 87
第4章 初等变换 91
4.1 引言 91
4.2 信息需求 92
4.3 循环正规化 93
4.4 数据流分析 95
4.4.1 定义-使用链 95
4.4.2 死代码消除 97
4.4.3 常数传播 98
4.4.4 静态单赋值形式 100
4.5 归纳变量暴露 105
4.5.1 前向表达式替换 105
4.5.2 归纳变量替换 107
4.5.3 驱动替换过程 111
4.6 小结 113
4.7 实例研究 113
4.8 历史评述与参考文献 114
习题 114
第5章 提高细粒度并行性 117
5.1 引言 117
5.2 循环交换 118
5.2.1 循环交换的安全性 119
5.2.2 循环交换的有利性 121
5.2.3 循环交换和向量化 122
5.3 标量扩展 126
5.4 标量和数组重命名 133
5.5 节点分裂 138
5.6 归约识别 140
5.7 索引集分裂 143
5.7.1 阈值分析 143
5.7.2 循环剥离 144
5.7.3 基于区域的分裂 145
5.8 运行时符号解析 146
5.9 循环倾斜 147
5.10 各种变换的集成 150
5.11 实际机器的复杂性 155
5.12 小结 157
5.13 实例研究 157
5.13.1 PFC 158
5.13.2 Ardent Titan编译器 158
5.13.3 向量化的性能 159
5.14 历史评述与参考文献 161
习题 161
第6章 开发粗粒度并行性 163
6.1 引言 163
6.2 单循环的处理方法 163
6.2.1 私有化 164
6.2.2 循环分布 167
6.2.3 对齐 167
6.2.4 代码复制 170
6.2.5 循环合并 173
6.3 紧嵌循环 184
6.3.1 为并行化的循环交换 184
6.3.2 循环选择 186
6.3.3 循环反转 189
6.3.4 为并行化的循环倾斜 190
6.3.5 幺模变换 193
6.3.6 基于有利性的并行化方法 194
6.4 非紧嵌循环套 196
6.4.1 多层循环合并 196
6.4.2 一个并行代码生成算法 199
6.5 一个扩充的例子 202
6.6 并行性的封装 204
6.6.1 循环分段 204
6.6.2 流水线并行性 205
6.6.3 调度并行任务 207
6.6.4 制导的自调度 209
6.7 小结 210
6.8 实例研究 211
6.8.1 PFC和ParaScope 211
6.8.2 Ardent Titan编译器 212
6.9 历史评述与参考文献 214
习题 215
第7章 处理控制流 217
7.1 引言 217
7.2 if转换 218
7.2.1 定义 218
7.2.2 分支的分类 219
7.2.3 前向分支 219
7.2.4 出口分支 222
7.2.5 后向分支 227
7.2.6 完全前向分支消除 229
7.2.7 化简 230
7.2.8 迭代依赖 234
7.2.9 if重构 237
7.3 控制依赖 238
7.3.1 构造控制依赖 240
7.3.2 循环中的控制依赖 241
7.3.3 控制依赖的一个执行模型 242
7.3.4 控制依赖在并行化中的应用 244
7.4 小结 254
7.5 实例研究 254
7.6 历史评述与参考文献 255
习题 255
第8章 改进寄存器的使用 257
8.1 引言 257
8.2 标量寄存器分配 257
8.2.1 面向寄存器重用的数据依赖 258
8.2.2 循环携带和循环无关的重用 259
8.2.3 寄存器分配的例子 260
8.3 标量替换 260
8.3.1 依赖图剪枝 261
8.3.2 简单替换 264
8.3.3 处理循环携带依赖 264
8.3.4 跨越多个迭代的依赖 265
8.3.5 删除标量拷贝 265
8.3.6 缓解寄存器压力 266
8.3.7 标量替换算法 267
8.3.8 实验数据 270
8.4 展开和压紧 272
8.4.1 展开和压紧的合法性 274
8.4.2 展开和压紧算法 276
8.4.3 展开和压紧的效果 279
8.5 面向寄存器重用的循环交换 281
8.5.1 对循环交换的考虑 283
8.5.2 循环交换算法 284
8.6 面向寄存器重用的循环合并 285
8.6.1 面向重用的有利的循环合并 285
8.6.2 面向合并的循环对齐 287
8.6.3 合并机制 291
8.6.4 加权循环合并算法 295
8.6.5 面向寄存器重用的多层循环合并 306
8.7 改进寄存器使用的变换综合 308
8.7.1 决定变换的顺序 308
8.7.2 例子：矩阵乘法 309
8.8 复杂的循环嵌套 310
8.8.1 包含if语句的循环 310
8.8.2 梯形循环 312
8.9 小结 316
8.10 实例研究 317
8.11 历史评述与参考文献 317
习题 318
第9章 管理高速缓存 319
9.1 引言 319
9.2 适合于空间局部性的循环交换 320
9.3 分块 325
9.3.1 非对齐的数据 326
9.3.2 分块的合法性 327
9.3.3 分块的有利性 327
9.3.4 一个简单的分块算法 329
9.3.5 带倾斜的分块 330
9.3.6 循环合并和对齐 332
9.3.7 结合其他变换的分块 333
9.3.8 有效性 335
9.4 复杂循环嵌套中的高速缓存管理 335
9.4.1 三角形的高速缓存分块 335
9.4.2 特殊用途的变换 336
9.5 软件预取 338
9.5.1 一个软件预取算法 339
9.5.2 软件预取的有效性 346
9.6 小结 347
9.7 实例研究 347
9.8 历史评述与参考文献 348
习题 349
第10章 调度 351
10.1 引言 351
10.2 指令调度 351
10.2.1 机器模型 353
10.2.2 直线型代码的图调度 353
10.2.3 表调度 354
10.2.4 踪迹调度 356
10.2.5 循环内的调度 359
10.3 向量部件调度 367
10.3.1 链接 368
10.3.2 协处理器 370
10.4 小结 372
10.5 实例研究 372
10.6 历史评述与参考文献 374
习题 375
第11章 过程间分析和优化 377
11.1 引言 377
11.2 过程间分析 377
11.2.1 过程间问题 377
11.2.2 过程间问题分类 382
11.2.3 流不敏感副作用分析 384
11.2.4 流不敏感别名分析 390
11.2.5 常数传播 394
11.2.6 注销分析 397
11.2.7 符号化分析 400
11.2.8 数组区域分析 402
11.2.9 调用图的构造 404
11.3 过程间优化 406
11.3.1 内联替换 407
11.3.2 过程克隆 408
11.3.3 混合优化 409
11.4 管理整个程序的编译 409
11.5 小结 411
11.6 实例研究 411
11.7 历史评述与参考文献 413
习题 414
第12章 C语言和硬件设计中的依赖 417
12.1 引言 417
12.2 优化C语言 417
12.2.1 指针 418
12.2.2 命名和结构 420
12.2.3 循环 421
12.2.4 作用域和静态变量 422
12.2.5 方言 422
12.2.6 其他问题 423
12.3 硬件设计 424
12.3.1 硬件描述语言 426
12.3.2 优化模拟 428
12.3.3 综合优化 439
12.4 小结 448
12.5 实例研究 448
12.6 历史评述与参考文献 449
习题 449
第13章 编译数组赋值 451
13.1 引言 451
13.2 简单的标量化 451
13.3 标量化变换 454
13.3.1 循环反转 454
13.3.2 输入预取 455
13.3.3 循环分裂 458
13.4 多维标量化 461
13.4.1 多维中的简单标量化 461
13.4.2 外层循环预取 462
13.4.3 用于标量化的循环交换 464
13.4.4 通用的多维标量化 467
13.4.5 一个标量化的例子 469
13.5 对向量机器的考虑 471
13.6 标量化后的循环交换和合并 471
13.7 小结 473
13.8 实例研究 474
13.9 历史评述与参考文献 474
习题 474
第14章 编译高性能Fortran 475
14.1 引言 475
14.2 HPF编译器概览 478
14.3 基本循环的编译技术 481
14.3.1 分布信息的传播和分析 481
14.3.2 迭代的划分 482
14.3.3 通信生成 485
14.4 优化 489
14.4.1 通信向量化 489
14.4.2 重叠通信和计算 494
14.4.3 对齐和复制 495
14.4.4 流水 496
14.4.5 一般依赖环的识别 498
14.4.6 存储管理 499
14.4.7 处理多个维 501
14.5 HPF的过程间优化 503
14.6 小结 504
14.7 实例研究 504
14.8 历史评述与参考文献 506
习题 506
附录 Fortran 90基础 509
参考文献 515
索引 535
