编译原理代码生成

1、第12章代码生成第十二章代码生成课前索引【课前思考】在第2章PL/0语言编译程序的实现中，产生的目标代码是一种与机器无关的假想栈式 计算机器汇编语言类 PCODE,它的执行需要用具体机器配置的语言编写一个解释程序。本 章将介绍的代码生成是把某种高级程序设计语言经过语法语义分析或优化后的中间代码作 为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码 生成器，因此，代码生成器的构造与输入的中间代码形式和输出的目标代码的机器结构密 切相关。本章将主要介绍生成具体机器汇编语言为目标代码时需要考虑的一些共同问题和 中间语言的选择考虑。建议学员考虑如何把 PL/0语言编译程序的

2、目标代码类 PCODE翻译成你所熟悉的具体 机器的汇编语言，作为学习代码生成的预习思考。【学习目标】本章将介绍以具体计算机指令作为目标代码的代码生成器的设计，以一个计算机模型 为例介绍一个简单的代码生成器需要考虑的问题，在代码生成时要考虑充分利用寄存器， 以减少对内存的存取次数以提高目标程序运行速度，为此，本章将给出寄存器分配的原则，并使用待用信息链表法的代码生成算法，最后给出中间语言的选择需要考虑的问题。【学习指南】由于代码生成的目标代码与具体计算机的结构有关，如指令格式、字长及寄存器的个数和种类，并与指令的语义和所用操作系统等都密切相关，因此实现非常困难。通过本章 学习，仅为学员初步了解一

3、个高级程序设计语言编译程序目标代码生成需要考虑的问题和 解决这些问题的基本原则和方法，为今后应用打下初步基础。要想真正掌握代码生成技术的细节，最好的方法是实现一个代码生成器，建议学员学 习本章后，用第2章PL/0语言的中间代码类 PCODE为输入，选择一个自己熟悉的汇编语 言为输出，编写一个代码生成器。【难重点】重点：衡量目标代码的质量主要从占用空间和执行效率两方面考虑，而寄存器的合理 分配对解决这两方面的问题起着重要的作用，因此要求学员了解寄存器的分配原则很重要，一个要求执行效率高的编译器对寄存器的分配可能要进行优化。另外对中间语言的选择也 很重要，希望有较强可移植性，就要求选择的中间语言能

4、适用较多种类的高级语言和多种 不同的具体计算机指令。难点：原则好讲实践困难，对具体要求和现实环境需要具体分析综合考虑。【知识点】代码生成A代码生成概述 ,A 一个计算机模型 个简单的代码生成器IA寄存器分配的原则待用信息链表法1A代码生成篁法*中间语言的选择第12章代码生成第12章代码生成代码生成概述代码生成是把某种高级程序设计语言经过语法语义分析或优化后的中间代码作为输 入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成 器，因此，代码生成器的构造与输入的中间代码形式和输出的目标代码的机器结构密切相 关。特别是高级程序设计语言和计算机硬件结构的多种多样性为代码生成

5、的理论研究和实 现技术带来很大的复杂性。由于一个高级程序设计语言的目标代码需反复使用，因而，代码生成器的设计要着重 考虑目标代码的质量问题。衡量目标代码的质量主要从占用空间和执行效率两个方面综合 考虑。到底产生什么样的目标代码取决于具体的机器结构、指令格式、字长及寄存器的个 数和种类，并与指令的语义和所用操作系统、存储管理等都密切相关。又由于目标代码的 执行效率在很大程度上依赖于寄存器的使用，所以本章将着重介绍目标代码生成的一些共 同问题，如寄存器的分配算法，而不讨论某个特定机器的目标代码生成问题。对寄存器分 配的算法仅限定在一个基本块的范围内，以四元式的中间代码作为输入，以一个称作M的模型机

6、的汇编语言作为输出。第12章代码生成一个计算机模型假定一个M计算机具有n个通用寄存器为 Ro ,Ri,R.1。它们既可作为累加器又可作 为变址器，如果用op表示运算符，用M表示内存单元，用变量名表示该变量所在的单元， C表示常量，*表示间址方式存取，指令形式可包含以下四种类型，见表 12.1(a)。表 12.1(a)指令形式意义(设op是二目运算符)卜接地址型op Ri,M(Ri)op(M)=Ri器型op Ri,Rj(Ri)op(Rj)= Rik址型op Ri,c(Rj)(Ri)op(Rj)+c)= R可接型op Ri,*M(Ri)op(M)op Ri,*Rj(Ri)op(Rj)=Riop R

7、i,*c(Rj)(Ri)op(Rj)+c) = R如果op是一目运算符，则op Ri,M的意义为：op(M) = Ri,其余类型可类推。以上指令中的运算符(操作码)op包括一般计算机上常见的一些运算符。我们将某些指 令的意义说明如表 12.1(b)。表 12.1(b)指令意义指令意义LD Ri,B把B单兀的内容取到寄存器Ri,即(B)与JX如CT=0转X单元。1.Ri。JX如CTM转X单元。CMP比较情况把机器内部特征寄存器CT置成J x如CT=2转X单元。A,B相应状态。CT占两个二进位。根据 AB分别置 CT为0或1或2。元。思考问题： 代码生成器的设计要着重考虑哪些问题?决定目标代码的因

8、素有哪些？第12章代码生成一个简单的代码生成器本节介绍一个简单的代码生成器。它以四元式的中间代码为输入。将其转换成第12.2节中所指的M计算机的目标代码为输出， 并着重讨论在一个基本块内如何充分利用寄存器 提高目标代码的运行效率和给出寄存器分配的一般算法。寄存器分配的原则当生成某变量的目标代码时，尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配时为止，这样引用变量值时可减少对内存的存取次数，以提高运行速度。当到基本块出口时，将变量的值存放在内存中，因为一个基本块可能有多个后继结点或多个前驱结点，同一个变量名在不同前驱结点的基本块内出口前存放的R可能不同，或没有定值，所以应在出口前把寄存

9、器的内容放在内存中，这样从基本块外入口的变量值 都在内存中。对于在一个基本块内后边不再被引用的变量所占用的寄存器应尽早释放，以提高寄存器的利用效率。对基本块的划分可按基本块的划分算法（见11.2.1）在生成四元式的目标代码时进行，以区分基本块的入口和出口。待用信息链表法为了在一个基本块内的目标代码中，寄存器得到充分利用，我们需把基本块内还要被 引用的变量值尽可能保存在寄存器中，而把基本块内不再被引用的变量所占的寄存器尽早 释放。当由四元式生成相应机器指令时，每翻译一个四元式，如： A ： =B op C时，则需 知道在本基本块内今后还有哪些四元式要对变量A, B, C进行引用。也就是说若在一个

10、基本块中，变量 A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j 之间没有其它对 A的定值点，这时我们称 j是四元式i中对变量A的待用信息或称下次引 用信息，同时也称 A是活跃的，若A被多处引用则可构成待用信息链与活跃信息链。为了得到在一个基本块内每个变量的待用信息和活跃信息，可以从基本块出口的四元 式开始由后向前扫描，对每个变量名建立相应的待用信息链和活跃变量信息链。考虑到处 理的方便，可假定对基本块中的变量在出口处都是活跃的，而对基本块内的临时变量可分 为两种情况处理。a）对于没经过数据流分析且中间代码生成的算法中临时变量不允许在基本块外引用， 则临时变量在基本块出口处都认

11、为是不活跃的。b）如果中间代码生成时的算法允许某些临时变量在基本块外引用时，则假定这些临时变量也是活跃的。下面介绍对变量待用信息的计算方法。假设在变量的符号表的记录项中含有待用信息 和活跃信息的栏目，其算法步骤如下：对各基本块的符号表中的待用信息栏和活跃信息”栏置初值，即把待用信息”栏 置非待用二 对活跃信息栏按在基本块出口处是否为活跃而置成活跃或非活跃。现假定变量都是活跃的，临时变量都是非活跃的。从基本块出口到基本块入口由后向前依次处理每个四元式。对每个四元式i: A:=Bop C,依次执行下述步骤：a）把符号表中变量A的待用信息和活跃信息附加到四元式i上。b）把符号表中变量 A的待用信息栏

12、和活跃信息栏分别置为“非待用和非活跃”。由于在i中对A的定值只能在i以后的四元式才能引用，因而对i以前的四元式来说 A 是不活跃也不可能是待用的。c）把符号表中B和C的待用信息和活跃信息附加到四元式i上。第12章代码生成d）把符号表中B和C的待用信息栏置为i,活跃信息栏置为活跃。注意，以上a）和b）, c）和d）的次序不能颠倒。例若用A, B, C, D表示变量，用T, U, V表示中间变量，有四元式如下：T ： =A-BU : =A-C V ： =T+U D ： =V+U其名字表中的待用信息和活跃信息如表12.2,用F表示非待用和非活跃，用L表示活跃，用（1）、（2）、（3）、（4）表示四元

13、式序号。表 12.2f12-3-1.swf表12.2中待用信息链与活跃信息链”的每列从左至右为每从后向前扫描一个四元式 时相应变量的信息变化情况，空白处为没变化。待用信息和活跃信息在四元式上的标记如下所示。T（3）L:= AL - bflU（3）L:= AFL - CFL vl：= tff + u（4）l DFL:= VFF+ uff代码生成算法为了在代码生成中能有效地分配寄存器，还需随时掌握各寄存器的使用情况。用一个 数组RVALUE来描述（记录）每个寄存器当前的状况，是处于空闲状态还是被某个或某几个 变量占用；用寄存器 Ri的编号值作为数组 RVALUE的下标，其数组元素值为变量名（当 变

14、量被复写时，则一个寄存器的值可表示多个变量的值）；用数组AVALUEM表示变量的存放情况。因此一个变量的值可能存放在寄存器中或存放在内存中，也可能既在寄存器中 又在内存中。综上所述一个变量的值表示可能有：RVALUER i=A,C表示Ri的现行值是变量 A , C的值AVALUEA=A 表示A的值在内存中AVALUEA=R i,A表示A的值既在寄存器Ri中又在内存中AVALUEA=R i表示变量A的值在寄存器Ri中有了上述对寄存器和地址的描述，可给出寄存器分配和代码生成的具体算法为：设GETREG是一个函数过程，它的参数是一个形如i: A:=B op C的四元式，每次调用GETREG（i: A

15、:=B op C）则返回一个寄存器 R,用以存放A的结果值。对如何给出寄存器 R, 要用到四元式i上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用 函数GETREG。GETREG分配寄存器的算法为：如果B的现行值在某寄存器 Ri中，且该寄存器只包含 B的值，或者B与A是同一 标识符，或B在该四元式后不会再被引用，则可选取Ri作为所需的寄存器 R,并转（4）。如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器 R,并转（4）。从已分配的寄存器中选取一个Ri作为所需寄存器 R,其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器 Ri所含的

16、变量和变量在主存中的情况必须先做如下调整：即对RVALUER i中的每一变量 M,如果M不是A且AVALUEM不包含M ,则需完成以下处理。a）生成目标代码 ST Ri,M;即把不是A的变量值由Ri中送入内存中。b）如果 M 不是 B,则令 AVALUEM=M,否则，令 AVALUEM=M, R i。第12章代码生成c)删除 RVALUER 口中的 M。给出R,返回。这样，一旦得到了一个为四元式运算的操作寄存器R,就可以进行代码生成，而当目标代码生成完成后，则又需修改寄存器的使用信息和地址描述信息。我们可用图12.1和图12.2给出算法的流程图。图12.1代码生成流程图f12-3-2.swf图

17、12.2修改寄存器使用信息和地址描述信息流程图f12-3-3.swf在图12.2中的B =和C =iR是为了判定B和C是否占有寄存器 Ri(i=0,若 占有并在四元式i后又不是活跃的则可释放寄存器R。思考问题：为什么在代码生成时要考虑充分利用寄存器？寄存器分配的原则是什么？第12章代码生成12.4中间语言的选择由于代码生成的任务是把某种中间语言翻译成某机器的汇编语言或机器语言，因而中 间语言在编译过程中起着桥梁作用。中间语言的选择也成为一个重要的研究课题。现仅简 单介绍中间语言选择的一些问题。人们期望能找到这样一种中间语言，它既能适用绝大多数高级程序设计语言，也能适用各 种计算机硬件的结构，这

18、样只要把各种高级语言都翻译成一种中间语言，而再把中间语言翻译成各种机器的目标语言 (汇编语言或机器语言)。前者称分析程序，后者称代码生成程序，那么对一个新的高级语言只要写出它的分析程序，则可用不同机器的代码生成程序，翻译成各种机器的目标代码，这也就相当在每种机器上都有了这样一种新的语言。对于一个新的计算机来说，只要再写出中间语言翻译成该机器语言的代码生成程序，那么所有的语言和其应用程序都可应用于这种新机器。例如：若用过去传统的方法，有m种语言，要在n种计算机上实现，则需要编写mxn个编译程序，而若用上述方法选定的通用中间代码实现则只要 m+n个编译程序就可实现。如图 12.3和图12.4所示。

19、图12.4限定几种源语言和目标机有中间语言的编译程序示意图尽管上述的设想是非常可取的,加种源语言nHn个编译器n种目标机因为当m和n都较大时，为开发编译程序所节省的人力和时间是相当可观的，然而，要设计一种中间语言既满足各种高级程序设计语言的特性 又要反映不同计算机的特点，同时还需要达到高级程序设计语言编译程序在各种计算机上 实现应有的效率，这是一个相当困难的问题。人们进一步考虑在限定的条件下解决这样的 问题，虽不能理想的解决问题，但在限定的范围内是可以节省人力和时间的，其限定的条 件可从以下3种情况考虑。(1)限定几种高级语言和几种计算机：这种想法仅是把理想的适应各种高级语言和各种计 算机的特

20、点范围缩小而已，它的极小限制是一种高级语言对应一种计算机。而通常可以把 共性较多、特性较接近的高级语言作为几种限定的语言，同样把特点较接近的各种计算机 归结为限定的几种计算机。按这种限定几种高级语言和限定几种计算机所设计的中间语言 较容易满足，并且实现后的效率也不难达到。(2)限定计算机情况下的中间语言：当限定某种计算机时，而高级语言为多种情况下 所设计的中间语言， 应能充分反映限定计算机的特点称 MSIL(Machine Specific Intermediate第12章代码生成language)o对这种机器的所有编译程序在分析阶段都生成MSIL ,在实现一个编译程序时,尽量把编译过程的大量

21、工作放在代码生成阶段，即MSIL到目标程序的翻译上，以减轻不同语言翻译的分析任务。因不管多少种高级语言，MSIL到目标程序的代码生成只需做一次即可。如图12.5所示。图12.5多种源语言对应一种目标机编译程序的示意图多种源语言一种目标计算机(3)限定高级语言情况下的中间语言：这种中间语言是针对某种特定的高级语言设计的，称LSIL(Language Specific Intermediate Language),它可以充分反映特定高级语言的特性， 只要把这特定的高级语言翻译成中间语言 LSIL ,然后对不同的计算机只要编写从 LSIL到 相应目标机的代码生成器， 便可实现这特定高级语言的编译程序

22、。 如图12.6所示。其LSIL 的设计要求与具体计算机无关，而LSIL到目标机的代码生成一般来说不难实现。图12.6 一种源语言对应多种目标机时编译程序示意图多种目标机以限定高级语言情况下的中间语言，有利于编译程序实现途径的可移植性，如果分析 器是用高级语言自身编写，那么编译程序还具有自展功能也为移植带来极大的方便。这种 方法虽然相当成功，但与一种高级语言对应一种计算机所设计的编译程序相比，编译程序 的效率还是会有所下降。(4)假想栈式抽象机假想栈式抽象机是一种包括基本运算和数据类型的中间语言。这种抽象机描述了一种或一类高级语言的特性。例如，由U. Ammann等人提供的可移植的 PASCA

23、L编译程序P4, 采用的栈式抽象机称 SC,对应的中间语言称 PCODE。它的实现是把 PASCAL语言翻译成 不依赖任何具体计算机， 而适合在SC上运行的PCODE代码，然后当需要在某一具体机器 上实现PASCAL编译程序时，就用该计算机已有的语言或汇编语言书写一个对抽象机SC及其语言的描述，而描述的最简捷办法是书写对PASCAL目标程序PCODE在SC上的汇编和解释程序，用以代替代码生成过程。 由于它的分析程序是用 PASCAL语言自身编写的， 所以它的可扩展性和可移植性相当好，若用汇编语言书写解释程序，其效率是可以达到一般实用要求的。它的最大缺点是由于 SC和PCODE不依赖于具体机器，

24、 而对其PCODE又 用解释执行代替代码生成，因而不能反应近代计算机多变址器的特点，致使变址器不能有 效利用，所以这种办法的目标程序执行效率下降。综上所述，一种合适的中间语言选择是很不容易的，因为既要考虑高级语言的实现模第12章代码生成型，又要能体现目标机的特点，再则既要考虑可移植性强又希望移植后的效率尽量不下降。目前中间代码的形式通常有前缀表示、后缀表示、四元组、三元组、树表示等各种形式。 在实际应用中只好根据具体需要进行选择。小结：一个高级程序设计语言编译程序的代码生成部分在编译中起着关键性的作用，而它又 与计算机硬件的结构乃致细节紧密相关，这导致了代码生成的可移植性及自动生成算法的 研究

25、，无论在理论上还是在实践上都相当困难。因此，本章介绍的仅是一些一般性的考虑 原则问题。在目前实际应用中大多数高级程序设计语言编译程序的前端用编译程序的构造 工具(将在第13章介绍)实现，后端的代码生成按选好的中间代码作为输入，但是中间语言的选择希望既满足各种高级程序设计语言的特性又要反映不同计算机的特点，也是一个 相当困难的问题。实际应用中中间代码的选择如12.4节中给出的限定条件下解决的3种情况。(1)限定几种高级语言和几种计算机把共性较多、特性较接近的高级语言作为几种限定的语言，同样把特点较接近的各种 计算机归为限定的几种计算机。(2)在计算机限定情况下的中间语言限定某种计算机时，而高级语言为多种情况下所设计的中间语言，能充分反映限定计 算机的特点。(3)高级语言限定情况下的中间语言这种中间语言是针对某种特定的高级语言设计的，它可以充分反映特定高级语言的特 性，只要把这特定的高级语言翻译成中间语言LSIL ,然后对不同的计算机只要编写从LSIL到相应目标机的代码生成器，便可实现这特定高级语言的编译程序。其LSIL的设计要求与具体计算机无关。而 LSIL到目标机的代码生成一般来说不难实现，这种编译程序的