第六章 中间代码生成.docx
《第六章 中间代码生成.docx》由会员分享，可在线阅读，更多相关《第六章 中间代码生成.docx（65页珍藏版）》请在冰点文库上搜索。
第六章中间代码生成
第六章中间代码生成
在编译器的分析-综合模型中，前端对源程序进行分析并产生中间表示，后端在此基础上生成目标代码。
在理想情况下，和源语言相关的细节在前端分析中处理，而关于目标机器的细节则在后端处理。
基于一个适当定义的中间表示形式，可以把针对源语言i的前端和针对目标机器j的后端组合起来，构造得到源语言i在目标机器j上的一个编译器。
这种创建编译器组合的方法可以节约大量的工作量：
只要写出m种前端和n种后端处理程序，就可以得到m×n种编译程序。
本章的内容处理中间代码表示、静态类型检查和中间代码生成。
为简单起见，我们假设一个编译程序的前端处理按照图6.1所示方式进行组织，顺序地进行语法分析、静态检查和中间代码生成。
有时候这几个过程也可以组合起来，在语法分析中一并完成。
我们将使用第二章和第五章中的语法制导定义来描述类型检查和翻译过程。
大部分的翻译方案可以基于第五章中给出的自顶向下或自底向上的技术来实现。
所有的方案都可以通过生成并遍历抽象语法树来实现。
静态检查包括类型检查，保证运算符被作用于兼容的运算分量。
静态检查还包括在语法分析之后进行的所有语法检查。
例如，静态检查保证了C语言中的一条break指令必然位于一个while/for/switch语句之内。
如果不存在这样的语句，静态检查将报告一个错误。
本章介绍的方法可以用于多种中间表示，包括抽象语法树和三地址代码。
这两种中间表示方法都在本书的2.8节中介绍过。
名为“三地址代码”的原因是这些指令的一般形式x=yopz具有三个地址：
两个运算分量y和z，一个结果变量x。
在将给定源语言的一个程序翻译成特定的目标机器代码的过程中，一个编译器可能构造出一系列的中间表示，如图6.2所示。
高层的表示接近于源语言，而低层的表示接近于目标机器。
语法树是高层的表示，它刻画了源程序的自然的层次性结构，并且很适合进行诸如静态类型检查这样的处理。
低层的表示形式适合进行机器相关的处理任务，比如寄存器分配、指令选择等。
通过选择不同的运算符，三地址代码既可以是高层的表示方式，也可以是低层的表示方式。
从6.2.3节将可以看出，对表达式而言，语法树和三地址代码只是在表面上有所不同。
对于循环语句，语法树表示了语句的各个组成部分，而三地址代码包含了标号和跳转指令，用来表示目标语言的控制流。
不同的编译程序对中间表示的选择和设计各有不同。
中间表示可以是一种真正的语言，也可以是编译器的各个处理阶段共享的多个内部数据结构。
C语言是一种程序设计语言。
它具有很好的灵活性和通用性，可以很方便地把C程序编译成高效的机器代码，并且有很多C的编译器可用，因此C语言也常常被用作中间表示。
早期的C++编译器的前端生成C代码，而把C编译器作为其后端。
6.1语法树的变体
语法树中各个结点代表了源程序的构造；一个结点的所有子结点反映了该结点对应构造的有意义的组成成分。
为表达式构建的无环有向图（Directedacyclicgraph,以后简称DAG）指出了表达式中的公共子表达式（多次出现的子表达式）。
在本节我们将看到，可以用构造语法树的技术去构造DAG图。
6.1.1表达式的有向无环图
和表达式的语法树类似，一个DAG图的叶子结点对应于原子运算分量，而内部结点对应于运算符。
与语法树不同的是，如果DAG图中的一个结点N表示一个公共子表达式，则N可能有多个父结点。
在语法树中，公共子表达式每出现一次，代表该公共子表达式的子树就会被复制一次。
因此，DAG不仅更简洁地表示了表达式，而且可以为最终生成表达式的高效代码提供重要的信息。
例子6.1：
图6.3给出了下面的表达式的DAG图
a+a*（b-c）+（b-c）*d
叶子结点a在表达式中出现了两次，因此a有两个父结点。
值得注意的是，结点“-”代表公共子表达式b-c的两次出现。
该结点同样有两个父结点，表明该子表达式在子表达式a*（b-c）和（b-c）*d中两次被使用。
尽管b和c在整个表达式中出现了两次，它们对应的结点都只有一个父结点，因为对它们的使用都出现在同样的公共子表达式b-c中。
□
图6.4给出的SDD（语法制导定义）既可以用来构造语法树，也可以用来构造DAG图。
它在例5.11中曾被用于构造语法树。
在那时，函数lead和node每次被调用都会构造出一个新结点。
要构造得到DAG图，这些函数就要在每次构造新结点之前首先检查是否已存在这样的结点。
如果存在一个已被创建的结点，它们就返回这个结点。
例如，在构造一个新结点Node（op,left,right）之前，我们首先检查是否已存在一个结点，该结点的标号为op，且其两个子结点为left和right。
如果存在，Node函数返回这个已存在的结点；否则它创建一个新结点。
例子6.2:
图6.5给出了构造图6.3中所示DAG图的各个步骤。
如上所述，函数node和leaf尽可能地返回已存在的结点。
我们假设entry-a指向符号表中a的位置，其它标识符也类似。
当在第2步上再次调用Leaf（id,entry-a）时，函数返回的是之前已生成的结点，因此p2=p1。
类似地，第8步和第9步上返回的结点分别和第3步及第4步中返回的结果相同（即p8=p3，p9=p4）。
同样，第10步中返回的结点必然和第5步中返回的相同，即p10=p5。
□
6.1.2构造DAG的值编码方法
语法树或DAG图中的结点通常被存放在一个记录数组中，如图6.6所示。
数组的每一行表示一个记录，也就是一个结点。
在每个记录中，第一个域是一个运算符代码，也是该结点的标号。
在图6.6（b）中，各个叶子结点还有一个附加的域，存放了标识符的字面值（在这里，它是一个指向符号表的指针或一个常量）。
而内部结点则有两个附加的域，分别指明其左右子结点。
在这个数组中，我们只需要给出一个结点对应的记录在此数组中的整数序号就可以引用该结点。
在历史上，这个序号被称为相应结点或该结点所表示的表达式的值编码。
例如，在图6.6中，标号为“+”的结点的值编码为3,其左右子结点的值编码分别为1和2。
在实践中，我们可以用记录指针或对象引用来代替整数下标，但是我们仍然把一个结点的引用称为该结点的“值编码”。
如果使用适当的数据结构，值编码可以帮助我们高效地构造出表达式的DAG图。
下一个算法将给出构造的方法。
假定结点按照如图6.6所示的方式存放在一个数组中，每个结点通过值编码引用。
令每个内部结点用一个三元组表示。
其中op是标号，l是其左子结点对应的值编码，r是右子结点对应的值编码。
假设单目运算符对应的结点中r=0。
算法6.3:
构造DAG图的值编码方法。
输入：
标号op、结点l和结点r。
输出：
数组中具有三元组形式的结点的值编码。
方法：
在数组中搜索标号为op、左子结点为l且右子结点为r的结点M。
如果存在，则返回M结点的数值号。
若不存在，则在数组中添加一个结点N，其标号为op，左右子结点分别为l和r；返回新建结点对应的值编码。
□
虽然算法6.3可以产生我们期待的输出结果，但是每次定位一个结点时都要搜索整个数组。
这个开销是很大的，当数组中存放了整个程序的所有表达式时尤其如此。
更高效的途径是使用哈希表，将结点放入若干“桶”中，每个桶通常只包含少量结点。
哈希表是能够高效支持词典功能的少数几个数据结构之一。
词典是一种抽象的数据类型，它可以插入或删除一个集合中的元素，可以确定一个给定元素当前是否在集合中。
类似于哈希表这样为词典设计的优秀数据结构可以在常数或接近常数的时间内完成上述的操作，所需时间和集合的大小无关。
要给DAG图中的结点构造哈希表，首先需要建立哈希函数h。
这个函数为形如的三元组计算“桶”的索引，把三元组在各个桶之间进行分配，使得每个“桶”中的元组数量都不大可能超过平均数很多。
通过对op、l、r的计算，可以确定地得到桶索引h（op,l,r）。
因而我们可以多次重复这个计算过程，总是得到结点的相同的桶索引。
桶可以通过链表来实现，如图6.7所示。
一个由哈希值索引的数组保存桶的头。
每个头指向列表中的第一个单元。
所有其哈希值指向这个桶的结点都存放在这个桶的链表中，链表的各个单元记录了这些结点的值编码。
就是说，在以数组的第h（op,l,r）个元素为头的链表中可以找到结点。
因此，给定一个输入结点（op,l,r），我们首先计算桶索引h（op,l,r），然后在该桶的链表单元中搜索这个结点。
通常情况下有足够多的桶，因此链表中不会有很多单元。
然而，我们可能必须查看一个桶中的所有单元，并且对于每一个单元中的值编码v，我们必须检查输入结点的三元组是否和单元列表中值编码为v的结点相匹配。
如果我们找到了匹配的结点，就返回v。
如果我们没有找到，我们知道任何其它桶中都不会有这样的结点。
我们就创建一个新的单元，添加到“桶”索引为h（op,l,r）的单元链表中，并返回新建结点对应的值编码。
6.1.36.1节的练习
练习6.1.1:
为下面的表达式构造DAG图
（（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y））
练习6.1.2:
为下列表达式构造DAG图，且指出它们的每个子表达式的值编码。
假定＋是左结合的。
a）a+b+（a+b）
b）a+b+a+b
c）a+a+（a+a+a+（a+a+a+a））
6.2三地址代码
在三地址代码中，一条指令的右部最多允许有一个运算符；也就是说，不允许组合的算术表达式。
因此象x+y*z这样的源语言表达式需要被翻译成如下的三地址指令序列。
t1=y*z，
t2=x+t1。
其中t1和t2是编译器产生的临时名字。
因为三地址代码拆分了多运算符算术表达式以及控制流语句的嵌套结构，它很适合于目标代码的生成和优化。
具体的过程将在第8、9章中详细介绍。
因为用名字来表示程序计算得到的中间结果，三地址代码可以方便地进行重组。
例6.4：
三地址代码是一棵语法树或一个DAG图的线性表示形式。
三地址代码中的名字对应于图中的内部结点。
图6.8中再次给出了图6.3中的DAG图，以及该图对应的三地址代码序列。
□
6.2.1地址和指令
三地址代码基于两个基本概念：
地址和指令。
按照面向对象的说法，这两个概念对应于两个类，而各种类型的地址和指令对应于某个适当的子类。
另一种方法是用记录的方式来实现三地址代码，记录中的域被用来保存地址。
6.2.2节将简要介绍被称为四元式和三元式的记录表示方式。
地址可以具有如下形式之一：
●名字。
为方便起见，我们允许源程序中的名字出现在三地址代码中。
在实现中，源程序名字被替换为指向符号表条目的指针。
关于该名字的所有信息均存放在该条目中。
●常量地址。
在实践中，一个编译器往往要处理很多不同类型的常量和变量。
6.5.2节将考虑表达式中的类型转换问题。
●编译器生成的临时变量。
在每次需要临时变量时产生一个新名字是必要的，在优化编译器中尤其如此。
当为变量分配寄存器的时候，我们可以尽可能地合并这些临时变量。
下面我们介绍本书的其余部分常用的几种三地址指令。
改变控制流的指令将使用符号化标号。
每个符号化标号表示了指令序列中的一条三地址指令的位置。
通过一次单独的扫描，或者通过回填技术就可以把符号化标号替换为实际的指令位置。
回填技术将在6.7节中讨论。
下面给出几种常见的三地址指令形式：
1.形如x=yopz的赋值指令，其中op是一个双目算术或逻辑运算符。
x、y、z是地址。
2.形如x=opy的赋值指令，其中op是单目运算符。
基本的单目运算符包括单目减、逻辑非、移位操作和转换操作。
将整数转换成浮点数的操作就是转换操作的一个例子。
3.形如x=y的复制指令，它把y的值赋给x。
4.无条件转移指令gotoL，下一步要执行的指令是带有标号L的三地址指令。
5.形如ifxgotoL或ifFalsexgotoL的条件转移指令。
分别当x为真或为假时，这两个指令的下一步将执行带有标号L的指令。
否则下一步将照常执行序列中的后一条指令。
6.形如ifxrelopygotoL的条件转移指令。
它对x和y应用一个关系运算符（<,==,>=等等）。
如果x和y之间满足relop关系，那么下一步将执行带有标号L的指令。
否则将执行指令序列中跟在这个指令之后的指令。
7.过程调用和返回通过下列指令来实现：
paramx进行参数传递，callp,n和y=callp,n分别进行过程调用和函数调用；returny是返回指令，其中y表示被返回值，它是可选的。
这些指令的常见用法见下面的三地址指令序列
paramx1
paramx2
…
paramxn
callp,n
它是为过程调用p（x1,x2,…xn）所生成代码的一部分。
“callp,n”中的n是实在参数的个数。
这个n并不是冗余的，因为存在嵌套调用的情况。
就是说，前面的一些param指令可能是p返回之后才执行的某个函数调用的参数，而p的返回值又成为这个后续函数调用的参数。
过程调用的实现将在6.9节中概要描述。
8.带下标的复制指令x=y[i]和x[i]=y。
x=y[i]指令将把距离位置y处i个内存单元的位置中存放的值赋给x。
指令x[i]=y将距离位置x处i个内存单元的位置中的内容设置为y的值。
9.形如x=&y、x=*y或*x=y的地址及指针赋值指令。
指令x=&y将x的右值设置为y的地址（左值）。
这个y通常是一个名字，也可能是一个临时变量。
它表示一个诸如A[i][j]这样、具有左值的表达式。
x是一个指针名字或临时变量。
在指令x=*y中，假定y是一个指针，或是一个其右值表示内存位置的临时变量。
这个指令使得x的右值等于存储在这个地址中的值。
最后，指令*x=y则把y的右值赋给由x指向的目标的右值。
例子6.5：
考虑语句
doi=i+1;while（a[i]图6.9给出了这个语句的两种可能的翻译。
在图6.9的翻译中，第一条指令上附加了一个符号化标号L。
（b）中的翻译显示了每条指令的位置号，我们在图中任意地选择100作为开始位置。
在两种翻译中，最后一条指令都是目标为第一条指令的条件转移指令。
乘法运算i*8适用于每个元素占8个存储单元的数组。
□
选择使用哪些运算符是中间表示形式设计的一个重要问题。
显然，这个运算符集合需要能够实现源语言中的所有操作。
接近目标指令的运算符可以使在目标机器上实现中间表示形式更加容易。
然而，如果前端必须为某些源语言操作生成很长的指令序列，那么优化和代码生成器就需要花费更多的时间去重新发现程序的结构，然后才能为这些结构生成高质量的目标代码。
6.2.2四元式表示
上述对三地址指令的描述详细说明了各类指令的组成部分，但是并没有描述这些指令在某个数据结构中的表示方法。
在编译器中，这些指令可以被描述为对象，或者是带有运算符域和运算分量域的记录。
四元式、三元式和间接三元式是三种这样的描述方式。
一个四元式有四个域，我们分别称之为op、arg1、arg2、result。
域op包含了一个运算符的内部编码。
举例来说，三地址指令x=y+z相应的四元式中，op域中存放+，arg1中为y，arg2中为z，result中为x。
下面是这个规则的一些特例。
1.形如x=minusy的单目运算符指令和赋值指令x=y不使用arg2。
特别注意象x=y这样的赋值语句，op是=；而对大部分其它操作而言，赋值操作是隐含表示的。
2.象param这样的运算既不使用arg2，也不使用result域。
3.条件或非条件转移指令将目标标号放入result域。
例子6.6：
赋值语句a=b*-c+b*-c的三地址代码如图6.10（a）所示。
这里我们使用特殊的minus运算符来表示“-c”中的单目减运算符“-”，以区别于“b-c”中的双目减运算符“-”。
请注意单目减的三地址指令中只有两个地址。
复制指令a=t5也是如此。
图6.10（b）描述了实现（a）中三地址代码的四元式序列。
□
为了提高可读性，我们在图6.10（b）中直接用实际标识符，比如象a、b、c，来描述arg1、arg2以及result域，而没有使用指向相应符号表条目的指针。
临时名字可以像程序声明中的变量一样被加入到符号表中，也可以实现为Temp类的实例对象。
这个Temp类有自己的例程。
6.2.3三元式表示
一个三元式只有三个域，我们分别称之为op,arg1和arg2。
请注意，图6.10（b）中的四元式的result域主要被用于临时变量名。
使用三元式时，我们将用运算xopy的位置来表示它的结果，而不是用一个明确的临时名字表示。
例如，在三元式表示中将直接用位置（0），而不是象图6.10（b）中那样用临时名字t1来表示对相应运算结果的引用。
带有括号的数字表示指向相应三元式结构的指针。
在6.1.2节中，指针或位置信息被称之为值编码。
三元式基本上和算法6.3中的结点范型等价。
因此，表达式的DAG图表示和三元式表示是等价的。
当然这种等价关系仅对表达式成立，语法树的变体和三地址代码分别以完全不同的方式来表示控制流。
例子6.7：
图6.11中给出的语法树和三元式表示对应于图6.10中的三地址代码及四元式序列。
在图6.11（b）给出的三元式表示中，复制指令a=t5按照下列方式被表示为一个三元组：
在域arg1是a，而在域arg2中是三元式位置的值编码（4）。
□
象x[i]=y这样的三元操作在三元式结构中需要两个条目；例如，我们可以把把x和i置于一个三元式，并把y置于另一个三元式。
类似的，我们可以把x=y[i]看成是两条指令t=y[i]和x=t，从而用三元式实现这个语句。
其中的t是编译器生成的临时变量。
请注意，实际上t是不会出现在三元式中的，因为在三元式结构中是通过相应三元式结构的位置来引用临时值的。
（a）语法树（b）三元式
图6.11：
a+a*（b-c）+（b-c）*d的表示
在优化型编译器中，由于指令的位置常常会发生变化，四元式相对于三元式的优势就体现出来了。
使用四元式时，如果我们移动了一个计算临时变量t的指令，那些使用t的指令不需要作任何改变。
而使用三元式时，对于操作结果的引用是通过位置号完成的，因此如果改变一条指令的位置，则引用该指令的结果的所有指令都需要做出修改。
使用下面考虑的间接三元式时就不会发生这个问题。
间接三元式包含了一个指向三元式的指针的列表，而不是列出三元式序列本身。
例如，我们可以使用数组instruction按照适当的顺序列出指向三元式的指针。
这样，图6.1.1（b）中的三元式序列就可以表示成为图6.12中的形式。
使用间接三元式表示方法时，优化型编译器可以通过对指针数组的重新排序来移动指令的位置。
在用Java实现时，一个指令对象的数组和间接三元式表示类似，因为java将数组元素作为对象引用来处理。
6.2.4静态单赋值形式
静态单赋值形式（SSA）是另一种中间表示形式，它支持某些类型的代码优化。
SSA和三地址代码的区别主要在两个方面。
首先，SSA中的所有赋值都是针对具有不同名字的变量的，这也是术语静态单赋值的由来。
图6.13给出了分别以三地址代码形式和静态单赋值形式表示的中间程序。
可以看出，SSA表示中对变量p和q的每次定值都以不同的下标加以区分。
（a）三地址代码（b）静态单赋值表示
图6.13：
三地址代码形式和SSA形式的中间程序
在一个程序中，同一个变量可能在不同的控制流路径中被定值。
例如，下列源程序
if（flag）x=-1;elsex=1;
y=x*a;
中，x在两个不同的控制流路径中被定值。
如果我们对条件语句的真分支和假分支中的x使用不同的变量名进行定值，那么我们应该在赋值运算y=x*a中使用哪个名字？
这也是SSA的第二个特别之处。
SSA使用一种被称为φ-函数的记号规则将x的两处定值合并起来：
if（flag）x1=-1;elsex2=1;
x3=φ（x1,x2）
如果控制流经过这个条件语句的真分支，φ（x1,x2）的值为x1，否则如果经过假分支，φ-函数取x2值。
也就是说，根据到达包含φ-函数的赋值语句的不同控制流路径，φ-函数返回不同的参数。
6.2.56.2节的练习
练习6.2.1:
将算术表达式a+-（b+c）翻译成：
a）语法树
b）四元式序列
c）三元式序列
d）间接三元式序列
练习6.2.2:
对下列赋值语句重复练习6.2.1。
i.a=b[i]+c[j]
ii.a[i]=b*c–b*d
iii.x=f（y+1）+2
iv.x=*p+&y
！
练习6.2.3:
说明如何对一个三地址代码序列进行转换，使得每个被定值的变量都有独一无二的变量名。
6.3类型和声明
可以把类型的应用划分为类型检查和翻译：
●类型检查。
类型检查利用一组逻辑规则来推理一个程序在运行时刻的行为。
更明确地讲，类型检查保证运算分量的类型和运算符的预期类型相匹配。
例如，java要求&&运算符的两个运算分量必须是boolean型；如果满足这个条件，结果也具有boolean类型。
●翻译时的应用。
根据一个名字的类型，编译器可以确定这个名字在运行时刻需要多少存储空间。
类型信息还会在其它很多地方被用到，包括计算一个数组引用所指示的地址，插入显式的类型转换，选择正确版本的算术运算符，等等。
在这一节中，我们将考虑在某个过程或类中申明的变量的类型及存储空间布局问题。
一个过程调用或对象的实际存储空间是在运行时刻，当该过程被调用或该对象被创建时，进行分配的。
然而，当我们在编译时刻检查局部声明时，我们可以进行相对地址的布局，一个名字或某个数据结构分量的相对地址是指它相对于某个数据区域开始位置的偏移量。
6.3.1类型表达式
类型自身也有结构，我们使用类型表达式来表示这种结构：
类型表达式可能是基本类型，也可能通过把被称为类型构造算子的运算符作用于类型表达式而构造得到。
基本类型的集合和类型构造算子根据被检查的具体语言而定。
例子6.8：
数组类型int[2][3]表示“由两个数组组成的数组，其中的每个数组各包含3个整数”。
它的类型表达式可以写成array（2,array（3,integer））。
该类型可以用如图6.14中的树来描述。
Array运算符有两个参数：
一个数字和一个类型。
□
我们将使用如下的类型表达式的定义：
●一个基本类型是一个类型表达式。
一种语言的基本类型通常包括：
boolean，char，integer，float和void。
最后一个类型表示“没有值”。
●一个类名是一个类型表达式。
●将类型构造算子array作用于一个数字和一个类型表达式可以构造得到一个类型表达式。
●一个记录是包含有名域的数据结构。
将record类型构造符应用于域名和相应的类型可以构造得到一个类型表达式。
在6.3.6节中，记录类型的实现方法是把构造算子record应用于包含了各个域对应条目的符号表。
●使用类型构造算子可以构造得到函数类型的类型表达式。
我们把“从类型s到类型t的函数”写成st。
在6.5节中讨论类型检查时，函数类型表达式是有用的。
●如果s和t是类型表达式，则其卡氏积s×t也是类型表达式。
引入卡氏积主要是为了定义的完整性。
它可以被用于描述类型的列表或元组（例如，带参数的函数类型）。
我们假定×具有左结合性，并且其优先级高于。
●类型表达式可以包含取值为类型表达式的变量。
在6.5.4节中将用到编译器产生的类型变量。
图是表示类型表达式的一种比较方便的方法。
可以修改6.1.2节中给出的值编码方法，用来构造一个类型表达式的DAG图。
图的内部结点表示类型构造算子，而叶子结点是基本类型、类型名或类型变量。
6.1.4给出了一棵树的实例。
6.3.2类型等价
两个类型表达式什么
升级会员 