9.61支配结点 419 10.3.1数据依赖图 459 9.6.2深度优先排序…42】 103.2其本块的列表围度方法·460 9.6.3深度优先生成树中的边 10.3.3带优先级的拓扑排序… 46 964 回边和可归约性 423 10.3410.3节的练习 46 9.65液图的深度. 424 10.4全局代码调度 462 9.6.6 自然循环… 10.4.1基本的代码移动 462 9.6.7 选代数据流算法的收敛速度*· 10.4.2向上的代码移动 46 9.6.89.6节的统习…… 427 10.4.3向下的代马乾动. 464 9.7基于区域的分析 428 10.4.4 更新数据依赖关系 465 9.7.1区域…4… 429 10.4.5 全局调度算法 465 9.7.2可归约流图的区城层次结构： 420 10.4.6高级代码移动技术 d67 97.3 基于区域的分析技术概选 431 10.4.7和动调度器的交 468 9.7.4有关传递函数的必要服设 +43 10.4.810.4节的练习++… 468 9.7.5 一个基于区域的分析算法 433 10.5软件流水线化…。 468 9.7.6处理不可归约流医 436 10.5.1 引言 46 9.7.79.7特的练习 437 10.5.2 循环的软件流水线化… 470 9.8符号分析… 437 10.5.3 寄存器分配和代码生成… 471 9.8.1 参考变量的仿射表达式 438 10.5.4 Do-Across循 472 9.8.2数据液问题的公式化 440 10.5.5软件流水线化的目标和约吏 472 9.8.3基于区城的符号化分析 442 10.5.6 一个软件流水线化算法 474 98.4 9.8节的练习 44 10.5.7对无环数据依赖图进行调度 47 9.9第9章总结 445 10.5.8对有环数据依赖图进行调度 +476 9.10第9章参考文献 448 10.5.9 对液水线化算法的改进 4R0 第10章指令级并行性 4…4450 10.5.10 模数变量扩展 480 10.1处理器体系结构 450 10.5.11条件语句 d82 10.1.1 指令流水线和分支延时 451 10.5.12软件流水线化的硬件支持 10.L2流水线执行…… 45 10.5.1310.5节的练习 483 .1.3多指令发送 10.6第10章总结… 484 10.2 代码调度约味 10.7第10章参考文献 485 10.2.1数据依赖 452 第11章并行性和局部性优化 487 10.2.2寻找内存访间之间的依 11.1基本概念 488 关系 453 11.1.1多处理器 488 10.23寄存器使用和并行性之间的 11.1.2应用中的并行性： 490 折液 454 11.1.3循环层次上的并行性 10.2.4 寄存器分配阶段和代码调度 11.1.4数据局部性 492 阶段之间的顺序… .d55 11.1.5仿时变换理论概述， 407 10.25 控制依赖 11.2矩阵柔法： 个深人的例于 495 10.2.6对投机执行的支持……456 11.2.1矩阵相乘算法 495 102.7一个基本的机器根型……：457 11.22优化 497 10.2.810.2节的练习 458 1.23 高速缓存干扰 10.3基本块调度… 459 11.2.411.2节的练习 499
W 113法代空 …499 11.7.911.7节的练习. 539 11.3.1从循环嵌套结构中构建选代 1山.8并行循环之间的同步 54 空间4…499 11.8.1固定多个同步运算： 541 113.2 循环嵌套结构的执行顺序…501 11.8.2程序依赖图 11.3.3 不等式组的矩阵表示方法…50 11.8.3层次结构化的时间 11.34混合使用符号常量…502 11,8.4并行化算法 544 11.3.5控制执行的顺序： 4502 11.8.511.8节的练习 64G 11.3.6坐标轴的变9 …3505 11.9流水线化技术 545 11.3.711.3节的练习 ++506 119.1什么是水线化. 545 11.4仿射的数组下标 1.9.2连续过松弛方法 一个例子 546 11.4.1仿射访问……507 119,3完全可交换循环…… 54 11.4.2实践中的仿射访间和非仿时 11.9.4把完全可交换循环流水线化·548 访问 508 1.9.5 般性的理 ..54g 11.4.311.4节的练习 4+508 11.9.6时间分划约束…549 11.5数据复用 ...500 11.9.7用Farkas引理求解时间分划 11.5.1 数据复用的类灭 509 约染 552 11.5.2自复用…… …510 11.9.8代码转换…554 11.5.3自空间复用 513 11.9.9具有最小同步量的并行性 11.5.4 组复用 514 1.9.1011.9节的练习 550 11.5.511.5节的练习 ·515 1山.10局部性优化 560 11.6数组数据依赖关系分析 516 11.10.1计算结果数据的时间 11.6.1数组访问的数据依骏关系的 局部性 560 定义 517 11.10.2数组收缩 560 11.62整数线性规划 …518 11.10.3分划单元的交织 562 11.6.3GCD测试… t518 11.10.4合成… 565 11.6.4解决整数线性规的启发式 11.10.511.10节的练习 566 520 11.11仿射转换的其他用途 566 11.6.5解决一般性的整数线性规划 11.11.1分布式内存计算机 56 问题 .+522 1山.11.2多指令发送处理器 567 11.6.6 小结 523 1.11.3向量和sMD指令 .567 11.6.711.6节的练习 t4523 11.11.4数据预取… *+56 117寻找无同步的并行性 .524 11.12第11章总结 ..,。.568 11.7.1 个介绍性的例子 11.13 第11章参考文献 570 11.7.2仿射空间分划 526 第12章过程问分析 573 11.7.3空间分划约束 527 12.1基本概念 .573 11.7.4求解空间分划约束… …529 12.1.1调用图 573 11.7.5 一个简单的代码生成算法…531 12.1.2上下文相关 574 11.7.6消除空选代 533 12.1.3调用 576 11.7.7从最内层循环中消除条件 12.1.4基于克隆的上下文相关分析·57 .535 12.1.5基于摘要的上下文相关分析…578 11.7.8源代码转换 …537 12.1,612.1节的练习 …579
12.2为什么需要过程间分析+ 580 12.5.1一个方法周用的效果· 4595 12.2.1虚方法调用 580 12.5.2在Datao中发现调用图 596 12.2.2指针别名分析 58 12.5.3动态加挑和反射… 597 12.2.3并行化 58 12.5.412.5节的练习…597 12.24软件错误和漏洞的检测 12.6上下文相关指针分析 598 12.2.5S0L注人* 581 12.6.1上下文和调用串… 598 12.2.6缓冲区溢出 582 12.6.2在Datalog规则中加人上下文 12.3数据流的一种逻朝表示方式… 583 信息……4…600 12.3.1 Datalog简介 583 12.6.3关于相关性的更多过论 ..600 2.3.2 Datalog规 584 12.6.412.6节的练习 600 12.3.3内凝斯言和外延断言… 585 12.7使用BDD的Datalog的实现… 601 12.3.4 Datalog程序的执行 587 12.7.】一分决策图4。 601 12.3.5 Datalog程序的增量计算 588 12.7.2 对BDD的转换 60 12.3.6右问题的Datalog规则 589 12.7.3用BDD表示关系 。603 123.712.3节的练习 59d 12.7.4用BDD操作实现关系运算…603 12.4 个简单的指针分析算法 127.5 在指针指向分析中使用 12.4.】为什么指针分折右推度 591 .........44e年4： ::+605 1242 一个指针和引用的模型… 592 12.7.612.7节的练习 605 12.4.3 控制流无关性 59 12.8第12章总结……*……606 12.4.4在Datalog中的表示方法 ,593 12.9第12章参考文就 ...60 12.4.5使用类型信息 594 附录A 一个完整的编译器前端 61 12.4.612.4节的练习 59 附录B寻找线性独立解 ..630 12.5上下文无关的过程间分析 …595
第1章 引 论 程序设计语言是向人以及计算机描述计算过程的记号。如我们所知，这个世界依赖于程序 设计语言，因为在所有计算机上运行的所有软件都是用某种程序设计语言编写的。但是，在一个 程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式。 完成这项翻译工作的软件系统称为编译器(compiler)。 本书介绍的是设计和实现编译器的方法。我们将介绍用于构建面向多种语言和机器的翻译 器的一些基本思想。编译器设计的原理和技术还可以用于编译器设计之外的众多领域。因此 这些原理和技术通常会在一个计算机科学家的职业生涯中多次被用到。研究编译器的编写将涉 及程序设计语言、计算机体系结构、形式语言理论、算法和软件工程。 在本章中，我们将介绍语言翻译器的不同形式，在高层次上概述一个典型编译器的结构 并讨论了程序设计语言和硬件体系结构的发展趋势。这些趋势将影响编译器的形式。我们还 将介绍关于编译器设计和计算机科学理论的关系的一些事实，并给出编译技术在编译领域之 外的一些应用。最后，我们将简单论述在我们研究编译器时需要用到的重要的程序设计语言 概念。 1.1 语言处理器 简单地说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把 该程序翻译成为一个等价的、用另一种语言（目标语言）编写的程序，参见 源程序 图11。编译器的重要任务之一是报告它在翻译过程中发现的源程序中的 编译容 如果目标程序是一个可执行的机器语言程序，那么它就可以被用户调 用，处理输入并产生输出。参见图12。 目标程序 解释器(interpreter)是另一种常见的语言处理器。它并不通过翻译的方图1】一个编译器 式生成目标程序。从用户的角度看，解释器直接利用用户提供的输入执行源程序中指定的操作。 参见图13。 在把用户输人映射成为输出的过程中，由一个编译器产生的输人一目标程序→输出 机器语言目标程序通常比一个解释器快很多。然而，解释器的错 图12运行目标程密 误诊断效果通常比编译器更好，因为它逐个语句地执行源程序。 例Java语言处理器结合了编译和解释过程，如图14所示。一个Java源程序首先被编译成 个称为字节码(yc©od)的中间表示形式。然后由一个虚拟机对得到的字节码加以解释执行。这 样安排的好处之一是在一台机器上编译得到的字节码可以在另一 台机器上解释执行。通过网络就可以完成机器之间的迁移。 源序一解释器日 输出 销人 为了更快地完成输入到输出的处理，有些被称为即时(us hime)编译器的Java编译器在运行中间程序处理输入的前一 图1-3 一个解释器 刻首先把字节码翻译成为机器语言，然后再执行程序 如图15所示，除了编译器之外，创建一个可执行的目标程序还需要一些其他程序。一个源
2 第】章 程序可能被分割成为多个模块，并存放于独立的文件中。把源程序聚合在一起的任务有时会由 一个被称为预处理器(prepo)的程序独立完皮。预处理器 源程序 还负责把那些称为宏的缩写形式转换为源语言的语句。 然后，将经过预处理的源程序作为输入传递给一个编译器。 翻译器 编译器可能产生一个汇编语言程序作为其输出，因为汇编语言 比较容易输出和调试。接着，这个汇编语言程序由称为汇编器 中间程序 一一翰出 (assembler)的程序进行处理，并生成可重定位的机器代码。 人虚拟机 大型程序经常被分成多个部分进行编译，因此，可重定 图14一个混合编译器 位的机器代码有必要和其他可重定位的目标文件以及库文件 连接到一起，形成直正在机器上运行的代码。一个文件中的 源程序 代码可能指向另一个文件中的位置，而链接器(linker)能够 决外部内存地址的问题。最后，加载器(loader)把所有的可执 预处理器 行目标文件放到内存中执行。 经过预处理的源程片 1.1节的练习 编译器 练习1.1.1：编译器和解释器之间的区别是什么？ 练习1.1.2：编译器相对于解释器的优点是什么？解释 目标汇编程序 器相对于编译器的优点是什么？ 汇编器 练习1.1.3：在一个语言处理系统中，编译器产生汇编语 言而不是机器语言的好处是什么？ 可定位机器代码 练习1.1.4：把一种高级语言翻译成为另一种高级语言 的编译器称为源到源(source-to-source)的翻译器。编译器使 用C语言作为日标语言有什么好处？ 目标机器代码 练习1.1.5：描述一下汇编器所要完成的一些任务。 图15一个语言处理系统 1.2 一个编译器的结构 到现在为止，我们把编译器看作一个黑盒子，它能够把源程序映射为在语义上等价的目标程 序。如果把这个盒子稍微打开一点，我们就会看到这个映射过程由两个部分组成：分析部分和综 合部分。 分析(analysis)部分把源程序分解成为多个组成要素，并在这些要素之上加上语法结构。然 后，它使用这个结构来创建该源程序的一个中间表示。如果分析部分检查出源程序没有按照正 确的语法构成，或者语义上不一致，它就必须提供有用的信息，使得用户可以按此进行改正。分 析部分还会收集有关源程序的信息，并把信息存放在 一个称为符号表(symbol table)的数据结构 中。符号表将和中间表示形式一起传送给综合部分。 综合(ynthesis)部分根据中间表示和符号表中的信息来构造用户期待的目标程序。分析部分 经常被称为编译器的前端(front end),而综合部分称为后端(back end)。 如果我们更加详细地研究编译过程，会发现它顺序执行了一组步聚(phs)。每个步骤把源 程序的一种表示方式转换成另一种表示方式。 一个典型的把编译程序分解成为多个步骤的方式 如图1-6所示。在实践中，多个步骤可能被组合在一起，而这些组合在一起的步骤之问的中间表 示不需要被明确地构造出来。存放整个源程序的信息的符号表可由编译器的各个步骤使用。 有些编译器在前端和后端之间有一个与机器无关的优化步骤。这个优化步骤的目的是在中