《【教学课件】第九章代码生成.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第九章代码生成.ppt（36页珍藏版）》请在三一办公上搜索。
1、1,第九章 代码生成,2,第九章 代 码 生 成,本章内容一个简单的代码生成算法涉及存储管理，指令选择，寄存器分配和计算次序选择等基本问题,3,9.1 代码生成器设计中的问题,9.1.1 目标程序可执行目标模块可重定位目标模块允许程序模块分别编译调用其它先前编译好的程序模块汇编语言程序免去编译器重复汇编器的工作从教学角度，增加可读性,4,9.1 代码生成器设计中的问题,9.1.2 指令的选择目标机器指令系统的性质决定了指令选择的难易程度指令系统的一致性和完备性是重要的因素指令的速度和机器特点是另一些重要的因素,5,9.1 代码生成器设计中的问题,若不考虑目标程序的效率，指令的选择是直截了当的。
2、如：三地址语句x:=y+z翻译成如下代码序列：（x，y和z都是静态分配）MOVy,R0/*把y装入寄存器R0*/ADDz,R0/*z加到R0上*/MOVR0,x/*把R0存入x中*/逐个语句地产生代码，常常得到低质量的代码,6,9.1 代码生成器的设计中的问题,语句序列 a:=b+c d:=a+e的代码如下MOV b,R0ADDc,R0MOVR0,a-若a不再使用，第三条也多余MOVa,R0-多余的指令ADDe,R0MOVR0,d,7,9.1 代码生成器设计中的问题,9.1.3 寄存器分配运算对象处于寄存器中的指令通常比运算对象处于内存的指令要短一些，执行也快一些寄存器分配选择驻留在寄存器中的
3、一组变量寄存器指派挑选变量要驻留的具体寄存器,8,9.1 代码生成器设计中的问题,9.1.4 计算次序的选择某种计算次序可能会比其它次序需要较少的寄存器来保存中间结果选择最佳次序是一个NP完全问题,9,9.2 目 标 机 器,9.2.1 目标机器的指令系统选择可作为几种微机代表的寄存器机器四字节组成一个字，有n个通用寄存器R0,R1,Rn-1。二地址指令：op源，目的MOV 将源移到目的中ADD将源加到目的中SUB在目的中减去源,10,9.3 基本块和流图,怎样为三地址语句序列生成目标代码？begin|(1)prod:=0 prod:=0;|(2)i:=1 i:=1;|(3)t1:=4*i d
4、o begin|(4)t2:=at1 prod:=prod+ai*bi;|(5)t3:=4*i i:=i+1|(6)t4:=bt3 end while i=20|(7)t5:=t2*t4 end|(8)t6:=prod+t5|(9)prod:=t6|(10)t7:=i+1|(11)i:=t7|(12)if i=20 goto(3),11,9.3 基本块和流图,9.3.1 基本块基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开再用有向边表示基本块之间的控制流信息，就能得到程序的流图,12,9.3 基本块和流图,将三地址语句序列划分成基本块首先确定所有的入口语句序列的第一个语句是入口
5、语句能由条件转移语句或无条件转移语句转到的语句是入口语句紧跟在条件转移语句或无条件转移语句后面的语句是入口语句每个入口语句到下一个入口语句之前的语句序列构成一个基本块,13,9.3 基本块和流图,(1)prod:=0(2)i:=1(3)t1:=4*i(4)t2:=at1(5)t3:=4*i(6)t4:=bt3(7)t5:=t2*t4(8)t6:=prod+t5(9)prod:=t6(10)t7:=i+1(11)i:=t7(12)if i=20 goto(3),14,9.3 基本块和流图,9.3.2 基本块的变换三地址语句x:=y+z引用y和z并对x定值一个名字的值在基本块的某一点以后还要引用的
6、话，我们说这个名字在该点是活跃的基本块的等价两个基本块计算一组同样的表达式这些表达式的值分别代表同样的活跃名字的值有很多等价变换可用于基本块局部变换全局变换,15,9.3 基本块和流图,公共子表达式删除a:=b+c a:=b+cb:=a d b:=a dc:=b+c c:=b+cd:=a d d:=b无用代码删除定值x:=y+z以后不再引用，则称x为无用变量,16,9.3 基本块和流图,语句交换t1:=b+c t2:=x+yt2:=x+y t1:=b+c当且仅当x和y都不是t1，b和c都不是t2 代数变换x:=x+0可以删除x:=x*1 可以删除x:=y*2 改成x:=y*y,17,9.3 基
7、本块和流图,9.3.3 流图把控制流信息加到基本块集合，形成一个有向图来表示程序首结点、前驱、后继,18,9.3 基本块和流图,什么是循环?所有结点是强连通的唯一的循环入口外循环和内循环内循环不含其它循环,19,9.3 基本块和流图,9.3.4 下次引用信息为每个三地址语句x:=y op z决定x、y和z的下次引用信息i:x:=y op z.没有对x的赋值j:=x.没有对x的赋值k:=x,20,9.3 基本块和流图,9.3.4 下次引用信息为每个三地址语句x:=y op z决定x、y和z的下次引用信息i:x:=y op z.没有对x的赋值j:=x.没有对x的赋值k:=x,21,9.3 基本块和
8、流图,对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息i:x:=y op z.没有对x的赋值j:=x.没有对x的赋值k:=x,22,9.3 基本块和流图,对每个基本块从最后一个语句反向扫描到第一个语句，可以得到下次引用信息i:x:=y op z.没有对x的赋值j:=x.没有对x的赋值k:=x利用下次引用信息，可以压缩临时变量需要的空间,23,9.4 一个简单的代码生成器,依次考虑基本块的每个语句，为其产生代码假定三地址语句的每种算符都有对应的目标机器算符假定计算结果留在寄存器中尽可能长的时间,除非：该寄存器要用于其它计算，或者到基本块结束,24,9.4 一个简单的代码生成器
9、,在没有收集全局信息前，暂且以基本块为单位来生成代码,25,9.4 一个简单的代码生成器,9.4.1 寄存器描述和地址描述例：对a:=b+c如果寄存器Ri含b，Rj含c，且b此后不再活跃产生ADD Rj,Ri，结果a在Ri中如果Ri含b，但c在内存单元，b仍然不再活跃产生ADD c,Ri，或者MOV c,RjADD Rj,Ri若c的值以后还要用,第二种代码比较有吸引力,26,9.4 一个简单的代码生成器,在代码生成过程中，需要跟踪寄存器的内容和名字的地址寄存器描述符记录每个寄存器当前存的是什么在任何一点，每个寄存器保存若干个(包括零个)名字的值名字的地址描述符记录运行时每个名字的当前值存放的一
10、个或多个位置该位置可能是寄存器、栈单元、内存地址或者是它们的某个集合这些信息可以存放在符号表中这两个描述符在代码生成过程中是变化的。,27,9.4 一个简单的代码生成器,9.4.2 代码生成算法对每个三地址语句x:=y op z调用函数getreg决定放y op z的计算结果的位置L查看y的地址描述符以确定y值当前的一个位置y.如果y的值还不在L中，产生指令MOV y，L 产生指令op z，L，其中z是z的当前位置之一如果y和/或z的当前值不再引用，在块的出口也不活跃，并且还在寄存器中，则修改寄存器描述符,28,9.4 一个简单的代码生成器,9.4.3 寄存器选择函数函数getreg返回保存x
11、:=y op z的x值的位置L如果名字y在R中，且R不含其它名字的值,并且在执行x:=y op z后y不再有下次引用，那么返回R作为L。否则，返回一个空闲寄存器，如果有的话否则，如果x在块中有下次引用，或者op是必须用寄存器的算符，则找一个已被占用的寄存器R(可能产生MOV R，M指令，并修改M的地址描述符)否则，如果x在基本块中不再引用，或者找不到适当的被占用寄存器，则选择x的内存单元作为L。,29,9.4 一个简单的代码生成器,赋值语句d:=(a b)+(a c)+(a c)编译产生的三地址语句序列为：t1:=a bt2:=a ct3:=t1+t2d:=t3+t2,9.4 一个简单的代码生
12、成器,31,9.4 一个简单的代码生成器,前三条指令可以修改，使执行代价降低MOV a,R0MOV a,R0SUB b,R0MOV R0，R1 MOV a,R1SUB b,R0SUB c,R1SUB c,R1.,32,9.4 一个简单的代码生成器,9.4.4 为变址和指针语句产生代码变址与指针运算的三地址语句的处理和二元算符的处理相同,33,9.4 一个简单的代码生成器,9.4.5 条件语句实现条件转移有两种方式根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正用条件码来表示计算的结果或装入寄存器的值是负、零还是正,34,9.4 一个简单的代码生成器,根据寄存器的值是否为下面六个条件之一进行分支：负、零、正、非负、非零和非正例如：if x y goto z把x减y的值存入寄存器R，如果R的值为负，则跳到z,35,9.4 一个简单的代码生成器,用条件码的例子if x y goto zx:=y+z的实现：if x 0 goto zCMP x,y 的实现：CJz MOVy，R0ADDz，R0MOVR0，xCJz,36,本 章 要 点,代码生成器设计中的主要问题：存储管理、计算次序的选择、寄存器的分配、指令的选择等。目标机器几种常用的地址模式和一些常用的指令。基本块和程序流图。简单的代码生成算法。,
