《编译技术》学习指南

一、内容设置

编译技术作为一门重要的专业基础课程，讲述的是计算机领域中的一个重要的主题：即

程序从一个语言形式到另一种语言形式的等价转换。编译通过从高级语言程序到低级语言程

序的转换向我们介绍了相关的理论、方法和技术，并进一步阐明了高级语言的工作原理。因

此，学生通过本课程的学习能了解到一个完整的编译过程。在这个过程的基础上或者这个过

程中，学习相关的理论和方法。

课程首先介绍一个完整的最简单的编译过程（翻译过程），在此基础上再根据培养要求

选讲代码优化、词法分析器的自动生成技术和其它语法分析技术（都可以自动生成）。在学

完完整的编译过程之后，就可以开始着手课程设计，即手工编程实现一个小型编译器，同时

继续学习自动生成技术。在完成课程设计的过程中，又能促进对理论知识的理解和巩固。

二、学习指导

学生需通过理论课程的学习，掌握编译过程中各阶段的基本原理和算法，在课程设计环

节，需严格按照各个阶段任务的要求，按时完成各个阶段任务，从而循序渐进地达到从理论

向实践过渡、逐步深入的过程。

课程设计首先让学生阅读经典的PL/O编译器源代码，既可以了解一个小型编译器的结构

和规模，以及其中关键算法的实现复杂度，又可以了解理论知识和算法如何用程序设计语言

来体现。在此基础上，学生可以确定自己将要完成的题目的难度，并根据难度从教学平台获

得一个随机分配的文法，后续的任务都在此文法的基础上完成。为此，第二个阶段任务是对

获取的文法进行解读，了解文法各条规则的作用、约束条件，并设计一个能覆盖所有规则的

程序。然后，需要在设计文档的基础上，依次完成词法分析、语法分析、语义分析和代码生

成的程序，并进行个阶段任务的考核。当学生的程序能够产生目标代码之后，将用三个测试

程序帮助学生进行完善和改进。通过这个过程，学生实现一个完整的编译器并完成作业文档,

即最终的成果。在课程的期末考核环节，教师将对全体学生的作业逐一进行现场考核，用另

外两个测试程序进行测试，并回答问题。

其中高难度和中高难度的题目中涉及到针对目标体系结构的代码生成和代码优化，是

课程设计中的难点。学生需了解目标体系结构的特点以及汇编语言的指令，并设计合适的数

据结构，才能实现相应的算法，这个过程由于综合了多门课程的知识，难度较大。

三、参考内容

1.PL/O编译器

我们将介绍一个编译系统，该编译系统出自著名的计算机科学家N.Wirth之手。考虑到

具体实现环境和教学要求，我们对该编译系统做了适当修改和补充。PL#编译系统是一个比

较简单的编译系统，可看作一个教学模型，它虽然不能真正提供使用，但已充分展示了编译

高级语言最基本的概念，它提出的基本方法对复杂语言的编译是完全适用的。因此，这部分

内容的学习，对实际掌握一个编译程序的构造和实现方法，无疑是非常有益的。

1.1PL/O语言

PL#是一种十分简单的“高级”程序设计语言，它只有整数一种类型，但却具有相当完

全的可嵌套的分程序结构。PL/O可进行常量定义、变量说明和过程调用，并具有通常程序设

计所必需的最基本的语句，如，赋值语句、条件语句、循环语句、过程调用语句和复合语句。

考虑到输入/输出的需要，我们增添了简单的读、写语句。PL/3过程没有参数，但可递归调

用.因此，过程所加工的数据只能通过全局变量进行传递。

下面给出PL/O语言的文法。

PL/3语言文法的扩充BNF表示为：

〈程序〉〈分程序〉.

〈分程序〉：：=［〈常量说明部分习［〈变量说明部分习［〈过程说明部分〉k语句〉

（常量说明部分〉const＜常量定义＞{，＜常量定义＞};

〈常量定义〉：：=（标识符＞=＜无符号整数〉

（无符号整数）:：=〈数字〉{〈数字〉}

〈标识符〉：：=＜字母＞{＜字母＞|＜数字〉}

〈变量说明部分＞::=var＜标识符＞{,〈标识符＞};

〈过程说明部分〉：：=〈过程首部＞＜分程序＞{;〈过程说明部分＞};

〈过程首部）::=procedurec标识符〉；

〈语句〉：:=＜赋值语句＞|（条件语句＞|（当循环语句＞|〈过程调用语句＞|＜复合语句〉|＜读

语句＞|〈写语句＞|＜空＞

〈赋值语句〉::=〈标识符＞:=＜表达式＞

〈表达式〉::=项＞{＜加法运算符＞＜项）}

＜项＞：：=＜因子＞{＜乘法运算符＞＜因子〉}

〈因子〉〈标识符＞|（无符号整数＞|'（'〈表达式〉'）'

＜加法运算符＞：：=+|-

（乘法运算符＞：：=*|/

〈条件＞＜表达式＞＜关系运算符＞＜表达式＞|odd＜表达式〉

〈关系运算符＞::==|＜＞|＜|＜=|＞|＞=

〈条件语句＞：：=if＜条件＞thenc语句〉

（当循环语句）::=whilec条件＞do＜语句＞

〈过程调用语句〉::=cak标识符〉

〈复合语句〉::=begin（语句＞{;＜语句＞}end

〈读语句〉：：=read'（々标识符＞{,〈标识符＞}'）'

〈写语句〉::=write'（'＜表达式＞{,（表达式＞}'）'

〈字母〉：：=a|b|c|d'"x|y|z

（数字＞::=0|1|2|3…8|9

下面给出用PLQ编写的三个小程序。

例1求解鸡兔同笼问题

constz=0;

varhead,foot,cock,rabbit,n;

begin

read(head,foot);

cock:=1;

whilecock<=headdo

begin

rabbit:=head-cock;

ifcock*2+rabbit*4=footthen

begin

write(cock,rabbit);

n:=n+1

end;

cock:=cock+1

end;

ifn=0thenwrite(0z0)

end.

例2求最大公约数和最小公倍数

consta=45,b=27;

varx,y,g,m;

procedureswap;

vartemp;

begin

temp:=x;

x：=y;

y:=temp

end;

proceduremod;

x:=x-x/y*y;

begin

x:=a;

y：=b；

callmod;

whilex<>0do

begin

callswap;

callmod

end;

g：二V；

m:=a*b/g;

write(g,m)

end.

例3打印素数表

consttrue=l,false=O;

varx,y,m,n,pf;

procedureprime;

vari,f;

proceduremod;

x:=x-x/y*y;

begin

f:=true;

i:=3;

whilei<mdo

begin

x:=m;

Y：=i；

callmod;

ifx=0thenf:=false;

i:=i+2

end;

iff=truethen

begin

write(m);

pf:=true

end

end;

begin

pf:=false;

read(n);

whilen>=2do

begin

write(2);

ifn=2thenpf:=true;

m:=3;

whilem<=ndo

begin

callprime;

m:=m+2

end;

read(n)

end;

ifpf=falsethenwrite(O)

end.

1.2PL/O编译系统结构

PL/O编译系统是一个编译-解释执行程序，整个编译过程分两个阶段进行。第一阶段先

把PLQ源程序编译成假想计算机的目标(P-code指令)程序，第二阶段再对该目标程序进

行解释执行，得到运行结果。PL/3编译程序采用一遍扫描，即以语法分析为核心，由它调用

词法分析程序取单词，在语法分析过程中同时进行语义分析处理，并生成目标指令。如遇语

法、语义错误，则随时调用出错处理程序，打印出错信息。在编译过程中要利用符号表的登

录和查找来进行信息之间的联系。

PLQ编译系统是用Pascal语言编写的，整个程序由18个过程或函数(包括主程序)组

成，这些过程和函数形成了嵌套的程序结构。

plO

error

getsym

getch

gen

test

block

enter

position

constdeclaration

vardeclaration

listcode

statement

expression

term

factor

condition

interpret

base

下面简要介绍这些过程（函数）的作用。（请参阅附录A中的PL/O编译器源代码）

plO主程序

error出错处理，打印出错位置和错误代码

getsym词法分析，读取一个单词

getch取字符

gen生成P-code指令，送入目标程序区

test测试当前单词符号是否合法

block分程序分析处理

enter登录符号表

position查找标识符在符号表中的位置

constdeclaration常量定义处理

vardeclaration变量说明处理

listcode列出P-code指令清单

statement语句部分分析处理

expression表达式分析处理

term项分析处理

factor因子分析处理

condition条件分析处理

interpretP-code解释执行程序

base通过静态链求出数据区的基地址

1.3PL/O的词法分析

PLQ的词法分析程序getsym作为一个独立的子程序(过程)由语法分析程序调用，它

的主要功能如下：

(1)跳过源程序中的空格字符。

(2)从源程序正文字符序列中识别出单词符号，并把该单词符号的类别以相应枚举

值的形式(即内部编码)送入变量sym中。

(3)用变量id存放标识符，用二分法查找保留字表，识别诸如begin,end等保留字。

(4)如取来的单词为无符号整数，则将该整数数字字符串转换为整数值存入变量

num中。

getsym调用getch扫描输入的源程序，取来一个个字符。getch实际上是将输入(input)

文件上的每一行源程序先读入缓冲区line中，然后再从line中取出字符。程序用变量II记录

当前源程序行的长度，用变量cc对当前所取字符在该行中的位置进行计数。getch除取来下

个字符外，还完成：

(1)识别并越过行结束信息。

(2)把从input文件读入的源程序同时输出到output文件上，以形成被编译源程序

的清单(用户可以在终端屏幕上看到编译扫描的进程)。

(3)在输出每一条源程序的开始处打印出编译生成的目标指令行号。

PL/3的语法分析采用了所谓“单符号先行”的技术，即在进入某语法成分的分析子程序

前，一定要先读取一个单词符号放在sym中。与此相应，在getsym中，也总是先读取一个

字符放在变量ch中。因此，整个编译过程是先读一个单词符号加一个字符。

1.4PL/O的语法分析

PL/0采用了递归子程序方法进行语法分析，即为每个语法成分都编写了一个分析子程

序，根据当前读取的符号，可以选择相应的子程序进行语法分析。采用不带回溯的递归子程

序法，对语言文法有一定要求：

(1)该文法必须是非左递归的。

(2)文法的任一非终结符，若在其规则右部有多个选择时，则各选择所生产的终结符号

串的头符号集合要两两不想交。

(3)若文法具有形如A£规则，则A的头符号集合不得与由它生产的任何符号串的后继

符号集合相交，BPFIRST(A)nFOLLOW(A)=<|>»

按照1.1节给出的PL/O语言文法，我们列出了PL/O有关语法成分的头符号集合和后继

符号集合，见表1,显然它是完全满足上述要求的.

表1PL/O的头符号与后继符号2

非终结符SFIRST(S)FOLLOW⑸

分程序constvarprocedureidentifcall*/

beginwhilereadwrite

语句identcallbeginifwhilereadwrite.;end

条件oddd—(identnumberthendo

表达式H—(identnumber.;)Rendthendo

项identnumber(.;)Rd—endthendo

因子identnumber(.；)R+—*/

endthendo

其中R表示关系运算符，ident和number分别为标识符和无符号整数。

为了对PL/O程序进行语法分析，各分析子程序之间必定存在相互调用的关系。实际的

语法分析工作，在进入分程序（block）以后可分成两部分进行：先对说明部分进行分析处

理，再对语句部分进行分析处理。下面分别予以介绍。

（-）对说明部分的分析处理

主要处理常量定义，变量说明和过程说明•对合法的常量名、变量名和过程名，应把

它们的名字及有关属性信息通过enter过程一一登录到符号表tab中，tab是一个带变体的

记录数组，表的每个登记项由名字name、种类kind、值val（当kind为常量时）、层次level

和地址adr（当kind为变量或过程时）所组成。对前面列举的例2的说明部分分析处理后，

符号表中的信息应如表2所示。

表2符号表tab中的信息

namekindvalleveladr

1aconstant45

2bconstant27

3Xvariable03

4yvariable04

5gvariable05

6mvariable06

7swapprosedure0*

8tempvariable13

9modprosedure0*

符号表每项记录中的level域应填入说明该变量名或过程名的分程序的层次。主程序的

层次为0,各嵌套分程序的层次随嵌套深度递增（PL/0程序限制level的最大值为3）。

符号表中的adr域应填入每层局部变量所分配单元的相应地址（其起始值为3,由地址

分配索引变量dx指定，后面将详述）。对过程名，则应填入编译该过程所生成的P-code指

令序列的入口地址（表2中记为*）。

（二）对语句部分的分析处理

进入对语句的分析后，只要根据当前读入的符号（应是标识符或其他相应保留字）就

可以立即断定当前的语句属于哪一种，便可以选择相应的分析程序进行分析。其分析过程一

目了然，请对照PLQ源程序清单仔细阅读，这里不再赘述。

在对各种语句进行分析处理时，凡遇到标识符，都要调用position函数去查找符号表

tab。若该名字已定义，则返回它在tab中的位置，并据此取得它的有关属性信息。若tab

中无此名字，则返回值0,表示出错。注意查找符号表时是从后往前查，这样做正好符合嵌

套分程序名字定义及其作用域规定的要求。

1.5出错处理

一个具有良好查错功能的编译程序一般应做到：

（1）任何源程序输入序列都不会导致编译工作的崩溃。

（2）应尽可能多地发现源程序中出现的语法和语义错误，并应尽可能准确地指出出

错位置和错误性质。

(3)应尽量遏止冗余的出错信息，即遏止那些由于程序出错而产生的其他假错误信

息。

尽管编译程序的实现者为此做出了大量努力，但往往由于不可能从程序中准确无误地推

断程序员出错的确切原因及程序员的真实意图，所以彻底的错误校正工作是极为困难的。

表3PL#编译程序的错误信息

1.应是:而不是:二14.call后应为标识符

2.=后应为数15.不可调用常量或变量

3.标识符后应为:16.应为then

4.const,var,procedure后应为标识符17.应为分号或end

5.漏掉逗号或分号18.应为do

6.过程说明后的符号不正确19.语句后的符号不正确

7.应为语句20.应为关系运算符

8.程序体内语句部分后的符号不正确21.表达式内不可有过程标识符

9.应为句号22.漏右括号

10.语句之间漏分号23.因子后不可为此符号

11.标识符未说明24.表达式不能以此符号开始

12.不可向常量或过程赋值30.这个数太大

13.应为赋值运算符:=40.应为左括号

PL/3在错误处理上采取了以下一些措施：

(1)对于在程序中遗漏了像‘；'号或明显的保留字之类的符号时，或者当程序员误

用了像'：='号或'='号之类的符号时，则除报告出错信息外，只要简单地添

上或改正这些符号，便可予以校正，使编译继续进行下去。

(2)在每个语法分析子程序出口处，检测下一个取来的符号是否为该语法成分的合

法后继符号，若不是，则应报告出错信息，并且跳读一段源程序，直至取来的

符号属于该语法成分的合法后继符号集合为止。这样也可以使编译工作正常地

继续下去。然而，为了防止跳读的源程序太多而造成损失太大，程序中又设置

了一个停止符号集合，即只要取来的符号属于合法后继符号集合或者停止符号

集合，都可以使程序停止跳读。停止符号集合里可以放置若干明显的能使程序

重新开始分析的保留字或其他终结符号。

PL/O用test过程来实现这种测试和跳读工作。test的参数S1为合法符号集合，S2为停

止符号集合，n为错误编码(请参看附录A源程序)•实际调用test时，与S1相应的实参是

由各语法分析程序的参数(用fsys表示)给出的。符号集合fsys参数是可以传递的，并且随

着调用语法分析程序的逐次深入，fsys的符号集合将逐步得以补充。

实际上，当进入一个语法成分的分析程序时，还可以利用test来测试当前读取的符号是

否属于该语法成分的合法头符号集合。PLQ编译程序中有多处使用了test的测试来达到上述

两种目的。例如，在进入语句(statement)分析的出口处，在分程序(block)分析的出口

处，在因子(factor)分析的入口处和出口处，以及在分析过程说明之后和进入语句分析之

前都进行了这样的测试。

表3给出了PL/0编译程序的错误编码及出错信息。

1.6目标代码的生成和解释执行

PL/3源程序经过编译得到了一个假想的计算机（以下称之为PLQ计算机）的目标代码,

即P-code指令代码。P-code指令不依赖于任何实际的计算机，它的指令集极为简洁，指令

格式也非常单纯，形如：fl,a。其中，f为操作码（用枚举值表示），I为变量或过程被引用

的分程序与说明该变量或过程的分程序之间的层次差，a对于不同的指令有不同的含义，具

体如下表所示：

LIT0,a取常量a放到数据栈栈顶

OPR0,a执行运算，a表示执行何种运算（详见附录A源程序注释）

LODI,a取变量（相对地址为a,层次差为I）放到数据栈栈顶

STOI,a将数据栈栈顶内容存入变量（相对地址为a,层次差为I）

CALI,a调用过程（入口指令地址为a,层次差为1）

INTO,a数据栈栈顶指针增加a

JMP0,a无条件转移到a

JPCO,a条件转移到指令地址a

REDI,a读数据并存入变量（相对地址a,层次差为I）

WRT0,0将栈顶内容输出

P-code指令可通过解释执行程序interpret使其在PL/O计算机上运行，因此P-code解释

执行程序也可以看作是PL/O计算机的算法描述。

PL/3计算机可看作由两个存储器，一个指令寄存器和三个地址寄存器组成。存储器code

（实际由数组实现），用来存放生成的P-code指令，P-code指令在解释执行过程中始终保持

不变，因此它可以看成是一个只读存储器。数据存储器S,实际是一个堆栈，用来动态分配

程序的数据空间（栈式动态存储分配）。PLQ计算机没有专门供运算的寄存器，因此，所有

的算术运算都在数据堆栈栈顶的两个单元之间进行，并用运算结果取代原来的两个运算对象

而保留在栈顶里。栈顶单元的地址（下标）放在栈顶地址寄存器T中，所以T作为栈顶指针,

永远指向数据栈S的栈顶。指令寄存器I存放当前要执行的P-code指令。程序地址寄存器P

存放下一条要执行的指令地址，当程序顺序执行时，每执行完一条指令后，P中的地址值应

加1。还有一个基地址寄存器B,它用来存放当前运行的分程序数据区在数据栈S中的起始

地址，其作用将在下面进一步说明。

当程序运行进入某一个过程（分程序）后，即在数据栈S中为其分配一个数据区，运算

操作就在该数据区上面的栈顶单元之间进行。若程序在当前过程中要调用其他过程（也可以

是递归调用本身过程），便在当前数据区上面再叠加分配一个新过程的数据区，…，这样下

去，直到某一个过程运行结束后，便从数据栈S中撤销相应的数据区。为了使过程运行结束

后能恢复到原来调用处的运行环境，我们用RA（返回地址）单元来保存应返回的调用点（下

一条）的指令地址，用DL（动态链）单元来保存原调用过程的数据区的起始地址（基地址）。

为此，设立了一个基地址寄存器B来保存最新分配的数据区起始地址，B永远指向动态链的

链头。

PL/3每个过程有自己的局部变量，而采用栈式动态存储分配不可能在编译时就知道该变

量在数据栈中的绝对地址。因此，编译时只能确定该变量在它所在分程序数据区中的相对位

置，即它相对于本分程序数据区的起始地址（基地址）的位移。考虑到在嵌套分程序的内分

程序中可以引用外分程序或主程序中定义的变量，所以还必须在各分程序数据区中设立一个

SL（静态链）单元，用来保存它的直接外层分程序数据区的基地址，以便在引用外层说明的

变量时，可通过静态链来找到该变量在S数据栈中的确切位置。

在编译时，凡生成的涉及存、取变量的指令（如LOD、STO、RED）时，其I值为引用

该变量的分程序层次与说明该变量的分程序层次之差。这样，只要按层次差值I,沿着静态

链往回找I次，即可找到说明该变量的分程序数据区的基地址，再加上相对地址值a,就确

定了该变量在数据栈S中的“绝对”位置。

在经过语法、语义分析后，P-code的生成是非常直观的，有关表达式的处理都按照逆波

兰表示法(后缀表达式)生成相应的运算指令。gen过程只是简单地把生成的P-code指令送

入code指令存储区。ex是指令索引指针，用来表示下一条要生成的指令的地址。在生产某

些转移指令(如JMP、JPC)时，往往不能马上确定转移地址a的值，这时可以把这条指令

的ex值保持起来，等后面确定了转移地址以后，再根据所保持的ex值把转移地址返填回去。

由于PL/O程序具有嵌套的分程序结构，所以编译进入分程序后生成的第一条指令为无

条件转移指令(JMP)。这条指令是为了跳过它所包含的其他分程序所生成的指令序列，而直

接进入程序体中语句部分所生成的指令。语句部分生成的指令序列的第一条指令为INTO,dx,

其作用是实现在数据栈S中为本分程序的数据区动态分配存储空间。

在了解PL/O计算机的结构和P-code指令的含义以后，P-code指令的解释执行程序就不

难理解了。解释执行P-code指令的过程就是用软件来模拟PL/3计算机的运行过程。实际上,

完全可以将P-code指令翻译成某一种计算机的机器指令(或汇编语言指令)，再令其在该计

算机上运行。

2.代码优化

代码优化模块通常在代码生成模块之前被调用，在不改变程序原有语义的前提下，为

代码生成模块提供优化后的中间代码作为后者的输入。代码优化技术在现代编译技术中占

据着核心地位，也是最活跃的研究领域之一。

代码优化技术可以分为与机器相关的优化技术，以及与机器无关的优化技术。与机器

无关的代码优化技术，例如数据流分析、常量传播、公共子表达式删除、死代码删除、循

环优化、代码内联等等，这些优化方法不针对某一特定的目标机体系结构，在几乎所有的

目标体系结构上都有效.当然，最终优化效果的好坏仍要受到被优化程序和目标体系结构

等各方面的影响，并且在其他优化方法的相互影响下，针对运行在某一特定体系结构上的

某一特定程序，并非所有的优化方法都能得到理想的、正面的结果。但总体来说，几乎所

有的优化编译器中都会实现此类技术，它们对目标程序运行效率的提高起到重要的作用。

与机器相关的优化技术，顾名思义，就是针对某一类特定目标机体系结构，在优化过

程中尽可能地充分利用该体系结构的特点和优势，在代码生成模块的辅助下，生成高效的

目标代码。例如，面向超标量超流水线架构、VLIW或者EPIC架构的指令调度方法，面向

SMP架构的同步负载优化方法，面向SIMD、MIMD或者SPMD架构的数据级并行优化方

法等。随着微处理器体系结构的并行处理能力的快速发展，如何提高被执行程序在目标体

系结构上的并行效率成为此类优化的关注重点。这些优化的共同特点是，优化方法仅在某

些特定体系结构下有效，在其他体系结构下可能无效，甚至对程序的执行效率有负面影

响；一旦目标体系结构产生变化，相应的优化方法也要做出调整.但此类优化技术往往又

是非常有效的，对目标代码运行效率的影响是显著的。

从优化方法的作用范围划分，优化技术还可以被分成局部优化技术、全局优化技术以

及跨函数优化技术等。局部优化与全局优化的分界线通常为是否跨越基本块，基本块内的

优化被称为局部优化，例如局部公共子表达式删除；跨越基本块，但仍在函数体内的优化

被称为全局优化，例如全局公共子表达式删除，全局数据流分析等。如果优化的范围是整

个程序，包括多个函数，这样的优化也被称为跨函数或跨过程优化(inter-procedural

optimization),例如跨函数别名分析(aliasanalysis)、逃逸分析(escapeanalysis)等。

优化方法的主要目的通常都是为了提高目标程序的运行效率，但在某些特定环境下，

优化方法也可能是为了获得更紧凑简洁的目标代码，运行效率的高低成为次要考虑。例

如，在某些嵌入式系统上，由于存储空间的物理限制，如果必须面向一个很有限的空间生

成代码，编译器会采用一些特殊的优化技术，尽可能的重用目标代码，或者选取更简洁的

指令集来生成目标代码。例如，某些32位的ARM微处理器同时还支持16位的THUMB指

令集，编译器选择THUMB指令，而不是32位的ARM指令，再辅以其他代码复用技术，

可以有效削减目标代码的存贮空间。

2.1基本块和流图

本节将介绍一种重要的中间代码的图表示方法：基本块和流图。该表示方法在编译器中

被普遍采用，对代码生成和代码优化都具有重要的意义。

基本块的定义如下：

1）基本块中的代码是连续的语句序列；

2）程序的执行（控制流）只能从基本块的第一条语句进入；

3）程序的执行只能从基本块的最后一条语句离开。

需要注意的是，正常的函数调用并不意味着“程序执行的离开”，因为调用完成后程序

仍会继续执行后继的指令。

流图的定义如下：

1）流图是一种有向图；

2）流图的节点是基本块；

3）如果在程序的执行路径中，基本块B2紧随着基本块BL那么从B1到B2存在一条

有向边。所谓‘'紧随"，可以是B1的最后一条语句有条件或无条件跳转到B2；也可以是B1

最后的条件转移指令的判断条件失败后进入B2执行；还可以是B2的第一条语句紧跟在B1

的最后一条语句之后，且B1的最后一条语句不为无条件跳转指令。B1也被称为B2的前驱,

B2也被称为B1的后继。

按照基本块和流图的定义，每个函数的中间代码都可以用一个流图表示，编译器可以按

照“程序一一函数（流图）一一基本块一一中间代码”这样的层次结构，选择合理的数据结

构组织和管理中间代码。

从基本块的定义出发，将中间代码划分为基本块的算法如下：

【算法2.1基本块划分算法】

输入：中间代码语句序列

输出：基本块序列，每条中间代码属于且仅属于一个基本块

方法：

1、首先确定入口语句（每个基本块的第一条语句）的集合；

1.1、整个语句序列的第一条语句属于入口语句；

1.2、任何能由条件/无条件跳转语句转移到的第一条语句属于入口语句；

1.3、紧跟在跳转语句之后的第一条语句属于入口语句

2、每个入口语句直到下一个入口语句，或者程序结束，它们之间的所有语句都属于同

一个基本块。

2.2基本块内优化

基本块内优化的对象是各基本块内部的中间代码，虽然优化的难度和范围都比不上全局

优化，但在提高目标代码质量和运行效率上，同样起着重要的作用。本节主要讨论如何构建

基本块的DAG图，消除局部公共子表达式。

2.2.1基本块的DAG图表示

DAG图的全称是无环有向图(DirectedAcyclicGraph),它是用来实现基本块变换的一

种非常有用的数据结构，可以用来表示基本块内各中间代码之间的关系。基本块DAG图的

定义如下：

1、图的叶节点由变量名或常量所标记。对于那些在基本块内先引用再赋值的变量,

可以采用变量名加下标0的方式命名其初值。

2、图的中间节点由中间代码的操作符所标记，代表着基本块中一条或多条中间代

码。

3、基本块中变量的最终计算结果，都对应着图中的一个节点；具有初值的变量，

其初值和最终值可以分别对应不同的节点。

同样的中间代码，可以有不同的DAG表达形式。得到基本块的DAG图后，可以完成

诸如消除局部公共子表达式等优化，并可以从DAG图重新导出简洁优化的中间代码，以取

代语义等价的原有中间代码。

2.2.2消除局部公共子表达式

在构建DAG图的过程中，如果采用如下算法，可以在构建图的过程中同时找到并消除

局部公共子表达式：

【算法2.2通过构建DAG图消除局部公共子表达式】

输入：基本块内的中间代码序列

输出：完成局部公共子表达式删除后的DAG图

方法：

1、首先建立节点表，该表记录了变量名和常量值，以及它们当前所对应的DAG

图中节点的序号。该表初始状态为空。

2、从第一条中间代码开始，按照以下规则建立DAG图。

3、对于形如z=xopy的中间代码，其中z为记录计算结果的变量名，x为左操作

数，y为右操作数，op为操作符：首先在节点表中寻找x,如果找到，记录下x

当前所对应的节点号i；如果未找到，在DAG图中新建一个叶节点，假设其节

点号仍为i,标记为x(如x为变量名，该标记更改为xo)；在节点表中增加新

的一项(x,i),表明二者之间的对应关系。右操作数y与x同理，假设其对应节

点号为j。

4、在DAG图中寻找中间节点，其标记为op,且其左操作数节点号为i,右操作数

节点号为j.如果找到，记录下其节点号k；如果未找到，在DAG图中新建一

个中间节点，假设其节点号仍为k,并将节点i和j分别与k相连，作为其左子

节点和右子节点；

5、在节点表中寻找z,如果找到，将z所对应的节点号更改为k；如果未找到，在

节点表中新建一项(z,k),表明二者之间的对应关系。

6、对输入的中间代码序列依次重复上述步骤3〜5。

说明：1)上述中间代码形式z=xopy中，x或y均可为空；2)如中间代码形为z=x,

只需按照规则3找到x所对应的节点i,再按照规则5,将z所对应的节点号更改为i,或在

节点表中新建一项(z,i)即可。

2.2.3数组、指针及函数调用

当中间代码序列中出现了数组成员、指针或函数调用时，算法2.2需要作出一定的调整,

否则将得出不正确的优化结果。例如，考虑如下中间代码：

x=a[i]

a[j]=y

z=a[i]

如果按照此前介绍的算法2.2为上述中间代码构建DAG图，会把变量x和变量z划归

到同一节点，该节点由操作符U标识，操作数分别是数组a和下标i,从而得出x和z相等

的结论。但是仔细分析上述中间代码，便会发现在程序运行过程中，无法排除变量j和变量

i拥有同样的值，那么一旦i等于j,而y不等于x,也就意味着x和z的值也不相同，此前

所作的局部子表达式删除优化就是错误的了。

一种可行的方法是，将数组变量a作为一个单独的变量进行考虑，将形如x=a[ij的中

间代码都表示为x=a口j,其中口为数组取值操作符；形如a|j]=y的中间代码都表示为a=j

“U="y,其中“口=”为数组成员赋值操作符。根据算法2,当出现类似a[j]=y的中间代码

时，数组变量a的值将被改变，并将体现在节点表中，后继的z=a[i]便不会引用与x=a[i]

中相同的a节点，二者便不会构成公共子表达式。

当中间代码中出现指针引用时，例如：

X=*p

*q=y

z=*p

其导致的问题与数组类似。由于存在*q=y这样的赋值操作，变量x和z的值便存在不

相等的可能，因此它们之间不能构成公共子表达式。

要正确并详细分析指针p和q可能所指的地址范围，对任何编译器都是一个不小的挑战。

为了避免DAG构建错误，可以采用保守的处理方法，在形如*q=y一类中间代码出现后，

便放弃为此后所有与指针操作相关的中间代码寻找公共子表达式的机会。

函数调用与指针赋值带来的问题比较类似。在缺乏跨函数数据流分析的支持下，需要保

守地假设函数调用改变了所有它可能改变的数据，因此，如果一个变量x可能在某一函数调

用内部被改变，那么在跨越函数调用后，必须假设x的值己经被改变，并在节点表中将x

所在项删除。另一个简单而保守的做法是，当中间代码中出现函数调用时，将此前建立的

DAG图写回中间代码，函数调用后再重新按照算法建立DAG图。

2.2.4从DAG图重新导出中间代码

利用DAG图完成消除局部公共子表达式后，还需要把DAG图重新导出为中间代码，

方便此后进行的其他优化。导出后的中间代码序列中，临时变量可以重新命名，但必须保证

此后的中间代码运算是正确的。局部变量，例如a、b、c,如果它们在基本块出口处仍然活

跃，也就是它们在基本块出口处的值在某条程序执行路径上仍可能被后继的代码使用，那么

这些变量都必须得到应得的值。这也就意味着当多个局部变量共享一个中间节点时，需要生

成显式的赋值语句为所有的变量赋值。

如果无法判断某个变量在基本块出口处是否活跃,编译器的做法通常是保守的将其归为

活跃一类，为其求值或赋值。

【算法2.3从DAG导出中间代码的启发式算法】

输入：DAG图

输出：中间代码序列

方法：

1、初始化一个放置DAG图中间节点的队列。

2、如果DAG图中还有中间节点未进入队列，则执行步骤3,否则执行步骤5。

3、选取一个尚未进入队列，但其所有父节点均已进入队列的中间节点n,将其加入队

歹U;或选取没有父节点的中间节点，将其加入队列。

4、如果n的最左子节点符合步骤3的条件，将其加入队列；并沿着当前节点的最左边,

循环访问其最左子节点，最左子节点的最左子节点等，将符合步骤3条件的中间节

点依次加入队列；如果出现不符合步骤3条件的最左子节点，执行步骤2。

5、将中间节点队列逆序输出，便得到中间节点的计算顺序，将其整理成中间代码序列。

该算法的动机是希望当某个中间节点的左操作数计算完成后，能够立即继续使用该计算

结果(通常是某个寄存器)进行下一步的运算，这样可以减少对临时寄存器的分配压力。该

算法为一种启发式算法，并不能保证得到最优结果，而且从算法设计上更适合x86一类的指

令集架构，针对其他类型的目标体系结构，算法还需要作出相应的调整。

2.2.5窥孔优化

如果采用从中间代码到目标代码逐条生成的方法，也就是代码生成时每输入一条中间代

码，便生成并输出其对应的目标代码，目标代码中通常会含有大量的冗余指令或者较低效率

的指令。通过一些简单的优化方法，我们通常称之为窥孔优化，可以有效地减少这些冗余指

令，并改善目标代码的质量。窥孔优化关注在目标指令的一个较短的序列上，通常称其为“窥

孔”，例如几条目标指令，并通过删除其中的冗余代码，或者用更高效简洁的新代码来替代

其中的部分代码，达到提升目标代码质量的目的。

例如，从中间代码到目标代码的逐条翻译过程中，较易出现如下指令序列：

(1)movEAX,[ESP+O8H]

(2)mov[ESP+O8H],EAX

显然后者是多余的，可以删除。上述指令必须出现在同一基本块中，程序运行不可能从

其他指令转移到它们中间，这样的删除才是正确的。

例如，根据流图生成跳转指令时，有时会得到如下指令序列：

jmpB2

B2:...

B2前的基本块生成了一条无条件跳转指令，跳往基本块B2的开始，但在代码生成时，

恰好B2紧跟在跳转指令之后生成，那么显然前一个跳转指令是多余的，也可以通过窥孔优

化删除。

窥孔优化还可以将一些简单算术指令化简或删除。部分此类化简在中间代码优化阶段便

可以完成，在代码生成时也可以进行相应的处理，但仍有可能遗漏一些优化机会，例如如下

指令：

addEAX,0

如果此类指令不是为了对状态寄存器进行操作，那么完全是多余的，窥孔优化可以找到

并删除它。

如果需要对某个整型变量乘以2或者2的基次常数，与乘法指令比较，更高效的指令是

采用向左移位的方法进行运算；如果是对某个整型变量除以2或者2的基次常数，与除法指

令比较，更高效的指令是采用向右移位的方法进行运算。

需要注意的是，窥孔的范围，不一定局限在基本块内，从上文就可以看出，窥孔可以跨

越基本块，甚至包含多个基本块。

设计出好的窥孔优化方法需要对目标体系结构，指令集都有充分的了解，该优化处理的

是目标代码中一些“微小”的优化机会，但从实际经验看，这些微小的机会汇聚在一起，就

有可能对整个程序的运行效率产生较大的影响，因此也应该得到相应的重视。

2.2.6常数合并和传播

所谓常数合并是将能在编译时计算出值的表达式用其相应的值替代，即如果在编译时，

编译程序能知道这一个表达式的所有操作数的值，则此表达式就可由其计算出的值替代。

例如，语句

A=2+3+A+C

可以由下面的语句替代

A=5+A+C

此处，用值“5”替代了表达式中“2+3”的部分。

常数传播是一种简单的合并，它是用在编译时已知的变量值来代替程序正文中对这些变

量的引用。如下面的程序段

Pl=3.141592

D_TO_R=PI/1800

可重写为

PI=3.141592

D_TO_R=3.14159?/180.0

若采取进一步的合并，则最终将产生：

Pl=3.141592

D_TO_R=0.0174644

这样，在所有后继的语句中PI或D_TO_R上的每一次出现都可由它的对应值替代，直

到该变量被其它语句重新定义为止。

2.3全局优化

在优化编译器中需要完成的一些重要优化，例如全局公共子表达式删除、复制传播、死

代码删除、循环优化，以及全局寄存器分配等，都需要跨越基本块，在获得被分析函数或过

程的整体信息的前提下完成，这些优化被称为全局优化。

2.3.1数据流分析

在全局优化中处于核心和基础地位的一种分析方法被称为数据流分析方法，可以用来获

取数据如何在程序执行路径中流动等相关信息。数据流分析的结果为许多全局优化方法提供

必要的基础信息。

数据流信息可以通过在程序的各个执行点建立和求解与所需信息有关的数据流方程所

得到。典型的数据流方程的形式如下：

out[S]=gen[S]u(in[S]-kill[S]),其中“u”和均为集合操作。

如果S代表某条语句(也可以是基本块，或者语句集合，或者基本块集合等)，上述方

程中的out[S]代表在该语句末尾得到的数据流信息，gen[S]代表该语句本身产生的数据流信

息，in[S]代表进入该语句时的数据流信息，kill[S]代表该语句注销的数据流信息。该方程的

含义是，当执行控制流通过某一条语句时，在该语句末尾得到的数据流信息等于该语句本身

产生的数据流信息，合并进入该语句时的数据流信息减去该语句注销的数据流信息后的数据

流信息。

建立和求解数据流方程时需要注意以下几点：首先，当前语句产生和注销的信息内容取

决于需要解决的具体问题。其次，由于数据是沿着程序的执行路径，也就是控制流路径流动，

因此数据流分析的结果受到程序控制结构的影响。最后，代码中出现的诸如过程调用、指针

访问以及数组成员访问等操作，对定义和求解一个数据流方程都会带来不同程度的困难。

程序的执行过程可以看成程序状态的变换过程。所谓程序状态，由程序中的变量和其他

数据结构组成，每一条实际执行的计算机指令都可能改变此状态。在程序的某个静态点上，

例如某条中间代码之前或者之后，可能存在哪些程序状态，正是数据流分析希望能够回答的

问题。得知这些状态，对程序的优化具有重要意义。

例如，如果得知在某条中间代码之后，无论程序在实际执行时通过哪条路径，某个变量

都不会再被访问，那么该变量此前所保有的全局寄存器或临时寄存器就可以安全地被其他变

量重新使用。例如，如果得知在程序的某个点上，对某个变量进行引用时，无论程序如何运

行，该变量都仅具有某个唯一的常量值，那么就可以将该常量引入中间代码，在代码生成时

生成更高效的指令，等等。

下面通过一种常用的数据流分析方法，所谓到达定义(ReachingDefinition)分析方法,

来阐述如何对程序进行数据流分析。

到达定义分析能够得到的信息是：在程序的某个静态点p，例如某条中间代码之前或者

之后，某个变量可能出现的值都是在哪里被定义的。这些信息对于确定该变量的性质，并选

择合适的优化手段具有重要意义。

如果从该变量的某个定义点d出发，存在一条路径达到p,并且在该路径上，不存在对

该变量的其他定义语句，我们就可以说该变量的定义点d到达静态点p。也就是说，在p处

对该变量的引用，取得的值可能在d处定义的。如果路径上存在对该变量的其他赋值语句，

那么路径上的前一个定义点就被路径上的后一个定义点“杀死”，或者消除了。

由于变量定义方法存在多种形式，例如赋值语句、过程参数和指针引用等，都可能对变

量的值作出改变，因此精确指出某条语句是否对某个变量进行定义并不是一件容易的事情。

在程序分析时，如果不能确定某条语句是否具有定义能力，只要存在可能性，都需要采用保

守的处理方法，将此类语句保守地设定为能够对变量进行定义的语句。同样，如果某条语句，

例如指针引用，可能对不止一个变量进行赋值，也需要保守的将所有可能被定义的变量考虑

在内。

需要重申的是，数据流分析中对程序执行路径的假设是一种保守的假设，也就是只要在

流图中存在的边，便认为该边在实际运行时可能被执行。这样的假设可能对分析结果在精确

度上产生负面影响，但能够保证分析结果的正确性。

每个基本块的到达定义数据流信息，可以从其所含语句的到达定义信息中计算得出。例

如，对于基本块中的某一条中间代码：

dl:u=vopw,其中v和w为变量，op为操作符。

根据前文，该代码对应的到达定义数据流方程是：

out[d1]=gen[dl]u(in[dl]-kill[d1])

其中gen[dl]={dl},表明该语句产生了一个定义点，该定义点定义了变量u。kill[dl]

是程序中所有对变量u定义的其他定义点的集合，无论这些定义点在实际执行路径中位于

dl之前或之后。这也就说明了图13.6中为什么中包括d5、d6、d7、d8这4个定义

点的原因。

对于该代码在同一基本块中紧邻的后继代码，假设其为d2,in[d2]等价于out[dl],可以

得到其数据流方程为：

out[d2]=gen[d2]u(in[d2J-kill[d2])

=gen[d2]u((gen[dl]u(in[dl]-kill[dl])