高级编译器设计与实现

高级编译器设计与实现涵盖了现代微处理器编译器的设计和实现方面的所有高级主题。

高级编译器设计与实现首先介绍编译器的结构、符号表管理、中间代码结构、运行时支持等问题，探讨过程内的控制流分析、数据流分析、依赖关系分析和别名分析的各种方法，并介绍一系列的全局优化。接下来，讲述过程间的控制流分析、数据流分析和别名分析，以及程间优化和如何应用过程间信息来改善全局优化。然后，讨论有效利用层次存储系统的优化技术。最后，详细介绍4种商业化编译系统，以提供编译器结构、中间代码设计、优化策略和效果的专门例子。

高级编译器设计与实现适合作为高等院校计算机专业研究生和高年级本科生的教材，也适合需要了解高级编译器设计和构造有关问题的计算机专业人员参考。

高级编译器设计与实现特点

　　  ●为理解高级编译器设计的主要问题奠定了基础

　　  ●深入阐述优化问题

　　  ●用sun的sparc、ibm的power和powerpc、dec的alpha以及intel的pentium和相关商业编译器作为案例，说明编译器结构、中间代码设计和各种优化方法

　　  ●给出大量定义清晰的关于代码生成、优化和其他问题的算法

　　  ●介绍由作者设计的以清晰、简洁的方式描述算法的语言ican  (非形式编译算法表示)。

高级编译器设计与实现(中文版)  目录:

出版者的话

专家指导委员会

译者序

序

前言

第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附录b  集合、序列、树、dag和函数的表示  549

附录c  软件资源  557

参考文献  561

索引  579