编译原理基础(刘坚)第6章.ppt

《编译原理基础(刘坚)第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章代码生成6.1代码生成的相关问题6.2简单的计算机模型6.3简单的代码生成器6.4本章小结6.1代码生成的相关问题1．中间代码形式中间代码有多种形式，其中树与后缀式形式适用于解释器，而对于希望生成目标代码的编译器而言，中间代码多采用与一般机器指令格式相近的三地址码形式。2．目标代码形式目标代码的形式可以分为两大类：汇编语言和机器指令。而机器指令又可以根据需求的不同分为绝对机器代码和可再定位机器代码。绝对机器代码的优点是可以立即执行，一般应用于一类称为load-and-go形式的编译模式，即编译完成后立即执行，不形成磁盘形式的目标文件

2、，这种形式特别适合于初学者学习语言的情况。可再定位机器代码的优点是目标代码可以被任意链接并装入内存的任意位置，是编译器最多采用的代码形式。汇编语言作为一种中间输出形式，便于软件开发人员的测试；load-and-go提供给初学者使用；可再定位机器代码用于真正的软件开发。出于教学的目的，此处选择汇编语言作为目标代码。3．寄存器的分配由于寄存器的存取速度远远快于内存，一般情况下，总是希望尽可能多地使用寄存器，而寄存器的个数是有限的，因此，如何分配寄存器的使用，是目标代码生成时需要考虑的重要因素之一。4．计算次序的选择代码执行的次序不同，会使代码

3、的运行效率有很大差别，在生成正确目标代码的前提下，优化安排计算次序和适当选择代码序列，也是代码生成需要考虑的重要因素之一。6.2简单的计算机模型1．指令系统与寻址方式计算机模型的寻址方式如表6.1所示。令X代表Ri或者M，则赋值号右边的(X)表示直接取X内容作为操作对象，((X))表示一层间接，即取X的内容作为地址。可以看出，此模型中的指令与三地址码十分相似。基本寻址方式有直接型、寄存器型和变址型，对应这三种寻址方式，均可以间接寻址。表6.1计算机模型的指令系统与寻址方式表6.1中op均表示二元运算；若为一元运算，则指令opRi,M的意义

4、为Ri:=op(M)，对应三地址码形式为x:=opy。2．特殊指令除了上述的寻址方式和一般的运算指令之外，计算机模型的指令系统中还包括如表6.2所示的特殊指令，主要有两大类：内存与寄存器交换类，包括LD与ST；比较与转移类，如CMP与JX等。表6.2计算机模型的特殊指令3．指令的代价由于各指令中操作对象可以是寄存器，也可以是内存地址，可以是直接寻址，也可以是间接寻址，因此，各条指令的执行时间是不同的。每条指令执行的时间称为指令的代价。假设寄存器的代价为1，内存地址的代价为2，则上述计算机模型的指令代价如表6.3所示。代价并不是一个严格的量

5、化指标，只是可以用它大概估算不同类型指令执行时间的差异，因此也可以采用所谓的相对代价，即令代价最小的指令的相对代价为0，则其它指令代价与其的差就是相对代价的值。表6.3计算机模型的指令代价例6.1以下是一个三地址码序列和对应的目标代码序列，它们的相对代价被分别列在指令的右边。t:=a+bLDR1,a0t:=t*cADDR1,b1t:=t/dMULR1,c1DIVR1,d16.3简单的代码生成器6.3.1基本块与程序流图定义6.1一段顺序执行的语句序列被称为一个基本块，其中，第一条语句被称为基本块的入口，最后一条语句被称为基本块的出口。由于

6、基本块中的语句是被顺序执行的，因此基本块的控制流总是从入口进入，从出口退出。任何一个复杂的程序控制流，均可以划分为若干个基本块；极端情况下，一条语句构成一个基本块。因此可以将一段完整的程序表示为一个程序流图。定义6.2程序流图(简称流图)是一个有向图，基本块构成图的节点。含有程序的第一条语句的基本块被称为流图的首节点。若在程序控制流中，基本块Bj紧接在基本块Bi之后执行，即控制流从Bi流向Bj，则从Bi到Bj有一条有向边，且称Bi是Bj的前驱节点，Bj是Bi的后继节点。所谓基本块的划分，实际上就是如何找出程序段中所有顺序执行的子序列。将这

7、些基本块作为流图的节点，并且在基本块划分时记录下控制流的转移，即可得到程序流图。基本块的划分与程序流图的构造算法如下所示。算法6.1划分基本块与构造程序流图。输入三地址码的指令序列输出程序流图方法按下述原则划分基本块，并且记录基本块之间的控制流转移：①求出各基本块的入口语句，并为其编号1，2，…，它们包括：(a)程序的第一条语句；或者(b)能由条件转移或无条件转移语句转移到的语句；或者(c)紧跟条件转移语句之后的语句。②对所求出的每个入口i(i=1,2,…,n)，构造基本块Bi。令每个Bi的前驱节点prev(Bi)=null，每个基本块包

8、括下述语句序列和相关信息：(a)从入口i到下一入口j的前一条语句，且令prev(Bj)=Bi；(b)从入口i到一转移语句，若转移语句转向入口j，则令prev(Bi)=Bj；(c)从入口i到停语