China-pub.com 下载 第8章 代码生成 本章要点 ·中间代码和用于代码生成的数据结构 ·商用编译器中的代码生成：两个案例研究 ·基本的代码生成技术 ·TM:简单的目标机器 ·数据结构引用的代码生成 ,TNY语言的代码生成器 ·控制语句和逻辑表达式的代码生成 ·代码优化技术考察 ·过程和函数调用的代码生成 ,TNY代码生成器的简单优化 在这一章中，我们着手编译器的最后工作 用来生成日标机器的可执行代码，这个可执 行代码是源代码语义的忠实体现。代码生成是编译器最复杂的阶段，因为它不仅依赖于源语言 的特征，而且还依赖于目标结构、运行时环境的结构和运行在目标机器的操作系统的细节信息 通过收集源程序进一步的信息，并通过定制生成代码以便利用目标机器，如寄存器、寻址模式、 管道和高速缓存的特殊性质，代码生成通常也涉及到了一些优化或改善的尝试。 由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构的步骤 其中包括了某种称做中间代码(itermediate code)的抽象代码。编译器也可能没有生成真正的可 执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处 理。汇编器、链接器和装入器可由操作系统提供或由编译器自带。在这一章中，我们仅仅集中 关注于中间代码和汇编代码的生成，这两者之间有很多共同特性。我们不考虑汇编代码到可执 行代码的更进一步的处理，汇编语言或系统的编程文本可以更充分地处理它。 本章的第1节考虑中间代码的两种普遍形式，三地址码和P代码，并且讨论它们的一些属 性。第2节描述生成中间代码或汇编代码的基本算法。接下来的章节讨论针对不同语言特性的 代码生成技术，这包括了表达式、赋值语句、控制语句（如if语句，while语句）以及过程和函 数调用。 之后的一节将应用在前面章节中学到的技术开发TY语言的一个汇编代码生成器。由于 在这种细节水平上的代码生成需要实际的目标机器，因此首先讨论一个目标结构和机器模拟器 TM。附录C提供了源代码清单。然后，我们再描述完整的TNY语言的代码生成器。最后给出 ,个关于标准代码的改善、优化技术的简介，同时描述了怎样将一些简单的技术融入到TNY 代码生成器之中。 8.1中间代码和用于代码生成的数据结构 在翻译期间，中间表示(intermediate representation)或IR代表了源程序的数据结构。迄今为 止，本文使用了抽象语法树作为主要的R。除R外，翻译期间的主要数据结构是符号表，这在 第6章中已学过了。 虽然抽象语法树是源代码完美充分的表述，即使对于代码生成也不过这样（这一点我们将 在后面的章节中看到)，但是它与目标代码极不相像，在控制流构造的描述上尤为如此。在控 制流构造上，目标代码（如机器代码或汇编代码）使用转移语句而不是if和wh11e语句。因此
下载 第8章 代 码 生 成 本章要点 • 中间代码和用于代码生成的数据结构 • 商用编译器中的代码生成：两个案例研究 • 基本的代码生成技术 • TM：简单的目标机器 • 数据结构引用的代码生成 • TINY语言的代码生成器 • 控制语句和逻辑表达式的代码生成 • 代码优化技术考察 • 过程和函数调用的代码生成 • TINY代码生成器的简单优化 在这一章中，我们着手编译器的最后工作——用来生成目标机器的可执行代码，这个可执 行代码是源代码语义的忠实体现。代码生成是编译器最复杂的阶段，因为它不仅依赖于源语言 的特征，而且还依赖于目标结构、运行时环境的结构和运行在目标机器的操作系统的细节信息。 通过收集源程序进一步的信息，并通过定制生成代码以便利用目标机器，如寄存器、寻址模式、 管道和高速缓存的特殊性质，代码生成通常也涉及到了一些优化或改善的尝试。 由于代码生成较复杂，所以编译器一般将这一阶段分成几个涉及不同中间数据结构的步骤， 其中包括了某种称做中间代码 (itermediate code)的抽象代码。编译器也可能没有生成真正的可 执行代码，而是生成了某种形式的汇编代码，这必须由汇编器、链接器和装入器进行进一步处 理。汇编器、链接器和装入器可由操作系统提供或由编译器自带。在这一章中，我们仅仅集中 关注于中间代码和汇编代码的生成，这两者之间有很多共同特性。我们不考虑汇编代码到可执 行代码的更进一步的处理，汇编语言或系统的编程文本可以更充分地处理它。 本章的第1节考虑中间代码的两种普遍形式，三地址码和 P -代码，并且讨论它们的一些属 性。第2节描述生成中间代码或汇编代码的基本算法。接下来的章节讨论针对不同语言特性的 代码生成技术，这包括了表达式、赋值语句、控制语句 (如i f语句，w h i l e语句)以及过程和函 数调用。 之后的一节将应用在前面章节中学到的技术开发 T I N Y语言的一个汇编代码生成器。由于 在这种细节水平上的代码生成需要实际的目标机器，因此首先讨论一个目标结构和机器模拟器 T M。附录C提供了源代码清单。然后，我们再描述完整的 T I N Y语言的代码生成器。最后给出 一个关于标准代码的改善、优化技术的简介，同时描述了怎样将一些简单的技术融入到 T I N Y 代码生成器之中。 8.1 中间代码和用于代码生成的数据结构 在翻译期间，中间表示(intermediate representation)或I R代表了源程序的数据结构。迄今为 止，本文使用了抽象语法树作为主要的I R。除I R外，翻译期间的主要数据结构是符号表，这在 第6章中已学过了。 虽然抽象语法树是源代码完美充分的表述，即使对于代码生成也不过这样 (这一点我们将 在后面的章节中看到 )，但是它与目标代码极不相像，在控制流构造的描述上尤为如此。在控 制流构造上，目标代码 (如机器代码或汇编代码 )使用转移语句而不是 i f和w h i l e语句。因此
306 翁译原理及实践 China-pub.Co 下载 编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中 间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示 称为中间代码(intermediate code)。 中间代码能采用很多形式，几平有多少种编译器就有多少种中间代码形式。然而所有中间 代码都代表了语法树的某种线性化(linearization)形式，也就是说，语法树用顺序形式表示。中 间代码可以是高水平的，它几乎和语法树一样可以抽象地表示各种操作。它或者还可以非常接 近目标代码。它可以使用或不使用目标机器和运行时环境的细节信息，如数据类型的尺寸、变 量的地址和寄存器。它可以混合或不混合符号表中包括的信息，如作用域、嵌套层数和变量的 偏移量。假如它混合了符号表中包括的信息，目标代码的生成基于中间代码就足够了：否则， 编译器必须保留符号表 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。如要产生高效的代码 就需要相当数量的目标代码属性分析，使用中间代码能使这变得容易。特别地，虽然从语法 树中直接得到混合细节分析信息的附加数据结构不是不可能的，但它能更容易地从中间代码 中得到。 中间代码在使编译器更容易重定向上也是有用的：假如中间代码与目标机器相对独立，那 么要为不同目标机器生成代码就仅需重写从中间代码到目标代码的翻译器。这比重写整个编译 器要容易。 在本节中我们将学习两个中间代码的普遍形式：三地址码(hrce-addresscode)和P代码(P code)。这两种中间代码以许多不同的形式出现，我们的研究将仅集中在普遍特性上，而不是 代表了某一个版本的细节化描述。这种描述能在本章最后“注意与参考”节所描述的文献中 找到。 8.1.1三地址码 三地址码最基本的用法说明被设计成表示算术表达式的求值，形式如下： x y op z 这个用法说明表示了对y和z的值的应用操作符p,并将值赋给x。这里的p可以是算术运算符， 如+或，也可以是其他能操作于y、z值的操作符。 三地址码这个名字来自于这个用法说明的形式，因为x、y、z通常代表了内存中的3个地 址。但是要注意，x的地址的使用不同于y、z的地址的使用。y、z(x不能)可以代表常量或没 有运行时地址的字面常量。 为了看清这种形式的三地址码如何能表示表达式的计算，考虑下边的算术表达式 2*a+(b-3) 语法树如下： 相应的三地址码如下 七1=2★a
编译器编写者可能希望从语法树生成一个更接近目标代码的中间表示形式，或者用这样一个中 间表示代替语法树，然后再从这个新的中间表示生成目标代码。这种类似目标代码的中间表示 称为中间代码(intermediate code)。 中间代码能采用很多形式，几乎有多少种编译器就有多少种中间代码形式。然而所有中间 代码都代表了语法树的某种线性化 ( l i n e a r i z a t i o n )形式，也就是说，语法树用顺序形式表示。中 间代码可以是高水平的，它几乎和语法树一样可以抽象地表示各种操作。它或者还可以非常接 近目标代码。它可以使用或不使用目标机器和运行时环境的细节信息，如数据类型的尺寸、变 量的地址和寄存器。它可以混合或不混合符号表中包括的信息，如作用域、嵌套层数和变量的 偏移量。假如它混合了符号表中包括的信息，目标代码的生成基于中间代码就足够了；否则， 编译器必须保留符号表。 当编译器的目标是产生非常高效的代码时，中间代码是极其有用的。如要产生高效的代码 就需要相当数量的目标代码属性分析，使用中间代码能使这变得容易。特别地，虽然从语法 树中直接得到混合细节分析信息的附加数据结构不是不可能的，但它能更容易地从中间代码 中得到。 中间代码在使编译器更容易重定向上也是有用的：假如中间代码与目标机器相对独立，那 么要为不同目标机器生成代码就仅需重写从中间代码到目标代码的翻译器。这比重写整个编译 器要容易。 在本节中我们将学习两个中间代码的普遍形式：三地址码 (three-address code)和P -代码( P - c o d e )。这两种中间代码以许多不同的形式出现，我们的研究将仅集中在普遍特性上，而不是 代表了某一个版本的细节化描述。这种描述能在本章最后“注意与参考”节所描述的文献中 找到。 8.1.1 三地址码 三地址码最基本的用法说明被设计成表示算术表达式的求值，形式如下： x = y o p z 这个用法说明表示了对y和z的值的应用操作符o p，并将值赋给x。这里的o p可以是算术运算符， 如+或-，也可以是其他能操作于y、z值的操作符。 三地址码这个名字来自于这个用法说明的形式，因为 x、y、z通常代表了内存中的 3个地 址。但是要注意，x的地址的使用不同于 y、z的地址的使用。y、z(x不能)可以代表常量或没 有运行时地址的字面常量。 为了看清这种形式的三地址码如何能表示表达式的计算，考虑下边的算术表达式 2*a + ( b-3 ) 语法树如下： 相应的三地址码如下 t1 = 2 * a 3 0 6 编译原理及实践 下载
China-pub.com 第8章代码生成 307 下载 t2=b-3 t3=t1+t2 三地址码要求编译器产生临时变量名，在这个例子中的是t1、t2和3。这些临时变量对应于 语法树的内部节点而表示计算值，在这个例子中用临时变量七3表示根节点值⊙。这里并没有说 明如何在内存中分配这些临时变量：它们通常将被分到寄存器中，但也有可能保存在活动记录 里面（参见第7章“临时栈”的讨论）。 三地址码仅代表了从左至右的语法树线性化，因为首先列出了相对于根的左子树的求值的 代码，编译器在某种情况下希望用另一种顺序也是有可能的。我们注意到对于三地址码来说， 是有可能使用另一顺序，即（临时变量有不同的意思）： t1=b-3 t2=2*a t3=t2+t1 很明显，上面所示的这种三地址码形式对于表示所有语言，即使是最小的程序语言的特性也是 不够的。例如一元操作符（如负号）就需要一个三地址码的变种（包含两个地址）如： t2=-t1 为适应标准程序语言的使用结构，必须为每个结构改变三地址码的形式。如果语言中含有 不常见到的特性，那么就必须为表达的这种特性发明另一种三地址码形式。这就是三地址码之 所以没有标准形式的原因（正如语法树没有标准形式一样）。 在这一章余下的章节中我们将逐个处理一些程序语言共有的结构，并显示怎样将这些结构 翻译成三地址码。为了知道其结果，我们给出一个用TNY语言编写的完整示例。 请考虑来自第1章1.7节的TNY例子，该例计算了一个整数的阶乘，我们把它重新放在程序 清单8-1中。 程序清单81TINY程序示例 in TINY language computes factorial fact 1; x:=x-1 unt10 程序清单8-2是这个例子的三地址码。这个代码包含了许多三地址码的不同形式。首先，内 置的输入和输出操作符read和write已被直接翻译成一地址指令。其次，这里有一个条件 转移指令1￡￡a1se,它通常被用来翻译i语句和循环语句，它包含两个地址：被检测的条 诸如1、2的名字仅仅意味着是这种代码通常类型的代表实际上，如果像这里一样使用源代码名字的话 三地址码中的临时变量名必须区别于在实际的源代码中所用的名字
t2 = b - 3 t3 = t1 + t2 三地址码要求编译器产生临时变量名，在这个例子中的是 t 1、t 2和t 3。这些临时变量对应于 语法树的内部节点而表示计算值，在这个例子中用临时变量 t 3表示根节点值 。这里并没有说 明如何在内存中分配这些临时变量；它们通常将被分到寄存器中，但也有可能保存在活动记录 里面(参见第7章“临时栈”的讨论)。 三地址码仅代表了从左至右的语法树线性化，因为首先列出了相对于根的左子树的求值的 代码，编译器在某种情况下希望用另一种顺序也是有可能的。我们注意到对于三地址码来说， 是有可能使用另一顺序，即(临时变量有不同的意思)： t1 = b-3 t2 = 2*a t3 = t2+t1 很明显，上面所示的这种三地址码形式对于表示所有语言，即使是最小的程序语言的特性也是 不够的。例如一元操作符(如负号)就需要一个三地址码的变种(包含两个地址)如： t2 = -t1 为适应标准程序语言的使用结构，必须为每个结构改变三地址码的形式。如果语言中含有 不常见到的特性，那么就必须为表达的这种特性发明另一种三地址码形式。这就是三地址码之 所以没有标准形式的原因(正如语法树没有标准形式一样)。 在这一章余下的章节中我们将逐个处理一些程序语言共有的结构，并显示怎样将这些结构 翻译成三地址码。为了知道其结果，我们给出一个用 T I N Y语言编写的完整示例。 请考虑来自第1章1 . 7节的T I N Y例子，该例计算了一个整数的阶乘，我们把它重新放在程序 清单8 - 1中。 程序清单8-1 TINY程序示例 程序清单 8 - 2是这个例子的三地址码。这个代码包含了许多三地址码的不同形式。首先，内 置的输入和输出操作符 r e a d和w r i t e已被直接翻译成一地址指令。其次，这里有一个条件 转移指令i f _ f a l s e，它通常被用来翻译 i f语句和循环语句，它包含两个地址：被检测的条 第 8章 代 码 生 成 3 0 7 下载 诸如t 1、t 2的名字仅仅意味着是这种代码通常类型的代表。实际上，如果像这里一样使用源代码名字的话， 三地址码中的临时变量名必须区别于在实际的源代码中所用的名字
308 翁译原理及实践 China-pub.com 下载 件值和转移的代码地址。一地址的1abe1指令指示了这个转移地址的位置。有了用以实现三 地址码的数据结构，这些1abel指令可能并不是必需的。halt指令（无地址）用来标志代码的 结束。 程序清单8-2程序清单8-1中TNY程序的三地址码 read x t1=g>0 ig_false ti goto L1 02 t2▣fact·x actt2 t4▣x0 if_false t4 goto L2 halt 最后，我们注意到原代码中的赋值语句导致了如下形式的copy指令 x=y 例如，例程中语句 fact:mfact'x; 翻译成2个三地址码 即使三地址码指令也是足够了，这种情况的技术原因将在8.2节中讲述。 8.1.2用于实现三地址码的数据结构 三地址码通常不被实现成我们所写的文本形式（虽然这是可能的），相反是将其实现为包含 几个域的记录结构。并将整个三地址指令序列实现成链表或数组，它能被保存在内存中并在需 要时可以从临时文件中读写。 最通常的实现是将三地址码按其所显示的内容实现。这意味着有4个域是必需的：1个操作 符和3个地址。对于那些少于3个地址的指令，将一个或更多的地域置成null或“empy”,具体 选择哪个域取决于实现。必须有4个域的三地址码表示叫做四元式(quadruple)。程序清单8-2的 三地址码的四元式在程序清单83中给出。这里我们用数学中的元组概念书写四元式。 程序清单8-3程序清单8-2中的三地址码的四元式实现 (rd,x,--】 (e (amn,1,fact,_)
件值和转移的代码地址。一地址的 l a b e l指令指示了这个转移地址的位置。有了用以实现三 地址码的数据结构，这些 l a b e l指令可能并不是必需的。 h a l t指令(无地址)用来标志代码的 结束。 程序清单8-2 程序清单8 - 1中T I N Y程序的三地址码 最后，我们注意到原代码中的赋值语句导致了如下形式的 c o p y指令 x = y 例如，例程中语句 f a c t : = f a c t * x ; 翻译成2个三地址码 t2=tact *x f a c t = t 2 即使三地址码指令也是足够了，这种情况的技术原因将在 8 . 2节中讲述。 8.1.2 用于实现三地址码的数据结构 三地址码通常不被实现成我们所写的文本形式 (虽然这是可能的)，相反是将其实现为包含 几个域的记录结构。并将整个三地址指令序列实现成链表或数组，它能被保存在内存中并在需 要时可以从临时文件中读写。 最通常的实现是将三地址码按其所显示的内容实现。这意味着有 4个域是必需的：1个操作 符和3个地址。对于那些少于3个地址的指令，将一个或更多的地域置成 n u l l或“e m p t y”，具体 选择哪个域取决于实现。必须有 4个域的三地址码表示叫做四元式 ( q u a d r u p l e )。程序清单8 - 2的 三地址码的四元式在程序清单8 - 3中给出。这里我们用数学中的元组概念书写四元式。 程序清单8-3 程序清单8 - 2中的三地址码的四元式实现 3 0 8 编译原理及实践 下载
China-pub.com 第8章代码生成 309 下载 《aat2,g (amn,t3,x,_) (1ab,1,-,) (ha1t,-,-,-) 程序清单84程序清单8-3中四元式的数据结构的C定义 typedef snum (rd,gt,if_f,aan,lab,mul, d 【Addrkind kind: union ）contentsr 】Addx0ss: typedef struct apiai.aha.aa, ouad: 程序清单84所示的是程序清单8-3中的四元式的C类型定义，在这些定义中，允许地址为 整数、常量或字符串（代表临时变量或一般变量的名字）。由于使用了名字，就必须将其加入到 符号表中，以供进一步处理时查询。另一种替代方法是在四元式中使用指向符号表入口的指针 这将避免额外的查询。这对可嵌套的语言来说有特别的好处，因为这时候的名字查询还需要更 多的嵌套层信息，如果常量也输入符号表，那么将不再需要地址数据类型中的uion 三地址码另一个不同的实现是用自己的指令来代表临时变量，这样地址域从3个减少到了 两个。因此在三地址指令中包含3个地址而日标地址总是一个临时变量⊙。如此的三地址码实现 称为三元式(ple)。它要求：或是通过数组的索引号或是通过链表指针，每个三地址指令都是 可引用的，如程序清单85是程序清单82的三地址码作为三元式实现的抽象表达。在那幅图中， 我们使用了一个数字系统，它对应于代表三元式的数组索引。在三元式内，把三元式引用用圆 括号括起，以同常量相区别。程序清单8-5取消了1abe1指令，代之以三元式引用。 程序清单8-5程序清单8-2中三地址码的三元式表示 (0) (rd,x) (1) (gt,0) (5) (asn,(4),fact) 7 an,(6),x) 日这不是三地址码的固有属性，但能通过实现来保证。例如，程序清单82的代码就是这样的（程序消单83也是）
程序清单8-4 程序清单8 - 3中四元式的数据结构的C定义 程序清单8 - 4所示的是程序清单8 - 3中的四元式的C类型定义，在这些定义中，允许地址为 整数、常量或字符串(代表临时变量或一般变量的名字 )。由于使用了名字，就必须将其加入到 符号表中，以供进一步处理时查询。另一种替代方法是在四元式中使用指向符号表入口的指针， 这将避免额外的查询。这对可嵌套的语言来说有特别的好处，因为这时候的名字查询还需要更 多的嵌套层信息，如果常量也输入符号表，那么将不再需要地址数据类型中的 u n i o n。 三地址码另一个不同的实现是用自己的指令来代表临时变量，这样地址域从 3个减少到了 两个。因此在三地址指令中包含3个地址而目标地址总是一个临时变量 。如此的三地址码实现 称为三元式( t r i p l e )。它要求：或是通过数组的索引号或是通过链表指针，每个三地址指令都是 可引用的，如程序清单8 - 5是程序清单8 - 2的三地址码作为三元式实现的抽象表达。在那幅图中， 我们使用了一个数字系统，它对应于代表三元式的数组索引。在三元式内，把三元式引用用圆 括号括起，以同常量相区别。程序清单8 - 5取消了l a b e l指令，代之以三元式引用。 程序清单8-5 程序清单8 - 2中三地址码的三元式表示 第 8章 代 码 生 成 3 0 9 下载 这不是三地址码的固有属性，但能通过实现来保证。例如，程序清单8 - 2的代码就是这样的(程序清单8 - 3也是)