编译原理(王晓斌)第十二章.ppt

《编译原理(王晓斌)第十二章.ppt》由会员分享，可在线阅读，更多相关《编译原理(王晓斌)第十二章.ppt（52页珍藏版）》请在三一办公上搜索。

1、第十二章代码优化和目标代码生成,本章主要讨论以下两个问题：1.如何对中间代码进行优化；2.如何由优化后的中间代码生成有效和目标代码；,电子科技大学计算机科学与工程学院,一、优化的定义,第一节 局部优化,优化是一种等价的，有效的程序变换,等价不改变程序运行结果,有效时空效率要高,电子科技大学计算机科学与工程学院,二、不同阶段的优化,局部优化：在基本块内的优化全局优化：超越基本块，在基本块之间的优化,1.源程序阶段的优化：考虑DS和算法2.编译优化中间代码优化和目标代码优化,电子科技大学计算机科学与工程学院,中间代码优化局部优化和全局优化,三、划分基本块和构造程序流图,1.划分基本块,基本块是指程

2、序中的一段语句（四元式）序列。一个入口语句，即程序中该语句序列的第一个语句；一个出口语句，即该语句序列的最后一个语句；,（1）入口语句,紧跟在条件转向语句后的那个语句,程序的第一条语句,能由条件或无条件转向语句转移到的语句,(2)出口语句,转向语句,停止语句,电子科技大学计算机科学与工程学院,入口语句 入口语句 入口语句 入口语句 转向语句 停语句,(3)确定基本块,删除未被划入基本块的语句,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=at1(5)i:=i+1(6)t2:=4*i(7)t3:=at2(8)i

3、f t3v goto(9)(13)if i=j goto(23)(14)t6:=4*i(15)x:=at6,(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5)(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at13(28)at12:=t14(29)t15:=4*n(30)at15:=x,B1,B2,B3,B4,B5,B6,例,2.构造流图,G=(N,E,n0）,(1)基本块集即为结点集N;(2)含程序第一个语句的基本块为首结点

4、n0;(3)设Bi,Bj N，若满足下列条件之一，则Bi Bj,Bj 紧跟在Bi 之后，且Bi 的出口语句不是无条件转向或停止语句,Bi 的出口语句为转向语句，其转向点恰为Bj 的入口语,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=at1,(5)i:=i+1(6)t2:=4*i(7)t3:=at2(8)if t3v goto(5),(9)j:=j-1(10)t4:=4*j(11)t5:=at4(12)if t5v goto(9),(13)if i=j goto(23),(14)t6:=4*i(15)x:=a

5、t6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5),(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at13(28)at12:=t14(29)t15:=4*n(30)at15:=x,B1,B2,B3,B4,B5,B6,四、基本块内的优化,对于A:=OP B 或 A:=B OP C这样的语句，若B及C为常数，则编译时可以把它们计算出来，把值存放在临时单元中，相应的语句变成A:=T;,1.合并已知量,2.删除公共子表达式,也叫

6、删除多余运算；例如两条赋值语句A:=B+C*DU:=V-C*D中有两次C*D运算。只计算一次，将值存在临时单元中T第二个语句改为：U:=V-T,电子科技大学计算机科学与工程学院,4.删除死代码,例如四元式序列(p)A:=B+D(q)A:=M+N中没有对A的引用，则第一个赋值无用，可删除。,3.删除无用赋值,iF语句条件为定值,电子科技大学计算机科学与工程学院,F:=1I:=H*GC:=F+EJ:=D/4D:=F+3 K:=J+CB:=A*AL:=HG:=B-DL:=I-JH:=E,合并已知量,F:=1I:=H*GC:=1+EJ:=1D:=4K:=2+EB:=A*AL:=HG:=B-4L:=I-

7、1H:=E,删除公共子表达式；I:=E*G,删除无用赋值；,假定F,C,D和J在基本块外不再引用，可得结果：,B:=A*A G:=B-4 K:=2+EI:=E*G L:=I-1,电子科技大学计算机科学与工程学院,例1,(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5),(14)t6:=4*i(15)x:=at6(17)t8:=4*j(18)t9:=at8(19)at6:=t9(21)at8:=x(22)goto(5),优化后,例2,电子科技大学计算

8、机科学与工程学院,删除公共子表达式,第二节 全局优化,一、循环的定义,全局优化有很多种，本节只讨论循环优化；,如何找出程序中的所有循环？循环优化有哪些？,循环是程序流图中有唯一入口结点的强连通子图,入口结点:子图中满足下列条件的结点n:或者n是流图的首结点,或者在子图外有一结点m,它有一有向边mn引向结点n;,强连通子图:任意两个结点可互相连联通,电子科技大学计算机科学与工程学院,1,2,3,4,5,6,7,8,9,10,5,6,7,8,9,例:,电子科技大学计算机科学与工程学院,是循环,4，,不是循环,不是循环,二、循环的的查找,1.必经节点,从流图的首结点出发到达结点n的任一通路都必须经过

9、的结点d,称d为n的必经结点，记为d DOM n,流图的首结点是流图中任一结点的必经结点 即n0 DOM n,每个结点是它本身的必经结点，即n DOM n,必经结点集：流图中结点n的所有必经结点的集合，称为n的必经结点集，记为D(n),电子科技大学计算机科学与工程学院,1,2,3,4,5,6,7,8,9,10,D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,5,6D(7)=1,2,4,5,6,7D(8)=1,2,4,5,6,8D(9)=1,2,4,5,6,9D(10)=1,2,4,10,电子科技大学计算机科学与工程学院,必经结点

10、具有如下性质：自反性：即对任意结点n，有n DOM n传递性：若n1 DOM n2,n2 DOM n3，则n1 DOM n3反对称性：若n1 DOM n2,n2 DOM n1，则n1=n2,电子科技大学计算机科学与工程学院,2.回边,流图G=(N，E，n0)中的有向边nd，如果d是n的必经结点,即dD(n),则称nd为流图的一条回边。,54,95,102,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,若nd是流图G=(N,E,0)的一条回边，M是流图中有通路到达n而该通路不经过d的结点集,则集合 LOOP=n,dM组成了G的一个子图,称为由回边nd组成的循环。,该流图有三

11、条回边：1.回边54构成循环 5,4,6,7,8,92.回边95构成循环 9,5,6,7,83.回边102构成循环 10,2,3,4,5,6,7,8,9,3.由回边构成的循环,二、循环优化,1.代码外提,2.强度削弱,基本归纳变量，i有唯一定值，i:=i c同族归纳变量，j:=c1 i c2,变成j:=j c1 c,但j必须在循环外赋初值 j:c1*i c2,电子科技大学计算机科学与工程学院,3.删除归纳变量,即改用同族归纳变量作为判断条件例如将 i 10 改为 t3 100+t1因原来t3:=10*i+t1，而100 t1 即 10*10+t1,电子科技大学计算机科学与工程学院,电子科技大学

12、计算机科学与工程学院,例,电子科技大学计算机科学与工程学院,另例：(1)PROD:=0(2)I:=1(3)T1:=4*I(4)T2:=a0 4(5)T3:=T2T1(6)T4:=4*I(7)T5:=b0 4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I 20 goto(3),电子科技大学计算机科学与工程学院,删除多余运算，代码外提,删除多余运算，代码外提(1)PROD:=0(2)I:=1(4)T2:=a0 4(7)T5:=b0 4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=

13、T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)if I20 goto(3),电子科技大学计算机科学与工程学院,强度削弱,强度削弱(1)PROD:=0(2)I:=1(4)T2:=a0 4(7)T5:=b0 4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(3)T1:=T1+4(12)if I 20 goto(5),电子科技大学计算机科学与工程学院,强度削弱(1)PROD:=0(2)I:=1(4)T2:=a0 4(7)T5:=b0 4(3)T1:=4*I(5)

14、T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(3)T1:=T1+4(12)if I 20 goto(5),电子科技大学计算机科学与工程学院,变换循环控制条件,变换循环控制条件(1)PROD:=0(2)I:=1(4)T2:=a0 4(7)T5:=b0 4(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(3)T1:=T1+4(12)if T1 80 goto(5),电子科技大学计算机科学与工程学院,合并已知量,(1)PROD:=0(2

15、)I:=1(4)T2:=a0 4(7)T5:=b0 4(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)if T1 80 goto(5),电子科技大学计算机科学与工程学院,1.代码生成的任务 将中间代码翻译成等价有效的目标代码 2.代码生成器的输入 中间代码，符号表 3.代码生成器的输出 目标代码 绝对机器代码 可重定位代码 汇编码,第三节 目标代码生成,电子科技大学计算机科学与工程学院,op 源，目的 其中op是操作码；源和目的是两个操作对象，可以是内存地址、寄存器或常数（1）直接地址型 op

16、Ri,M(Ri)op(M)=Ri（2）寄存器型 op Ri,Rj(Ri)op(Rj)=Ri,4.抽象机的指令形式,电子科技大学计算机科学与工程学院,（3）变址型 op Ri,C(Rj)(Ri)op(Rj)+C)=Ri（4）间接型 op Ri,*Rj(Ri)op(Rj)=Ri op Ri,*M(Ri)op(M)=Ri op Ri,*C(Rj)(Ri)op(Rj)+C)=Ri,电子科技大学计算机科学与工程学院,（5）其它几种常用指令MOV Ri,M(Ri)=MMOV M,Ri(M)=RiJ x goto x,电子科技大学计算机科学与工程学院,5.简单的代码生成方法,（1)p:x:=y op z 的

17、翻译 MOV y,Ri op Ri,z,电子科技大学计算机科学与工程学院,结果（x 的值）在寄存器Ri中,(2)为 结果（x）分配寄存器的方法,1.y 本身占有寄存器Ri，且y在p点后不再被引用,2.有空余的可用寄存器Ri,3.寄存器均被占用：保存副本，选择一个最好选择占用Ri的变量在主存中已有副本的或者在p点后该变量不再被引用的或者在离p点最远处才被引用的,电子科技大学计算机科学与工程学院,例:基本块中有如下指令：t:=a-bu:=a+cv:=a-tw:=v+u,MOV a,R0SUB R0,b(t占用R0)MOV a,R1ADD R1,c(u占用R1)MOV R1,u(释放R1)MOV a

18、,R1SUB R1,R0(v占用R1）MOV R1,v(释放R1)ADD R1,u(w占用R1),假设可以两个寄存器,电子科技大学计算机科学与工程学院,6.循环中的寄存器的分配,(1)指令的执行代价 该指令访问主存的次数寄存器型 op Ri，Rj 执行代价为1直接地址型 op Ri，M 执行代价为2变址型 op Ri，C(Rj)执行代价为2间址型 op Ri,*Rj 执行代价为2 op Ri,*M 执行代价为3 op Ri,*C(Rj)执行代价为3,电子科技大学计算机科学与工程学院,BL,（2）固定分配寄存器节省的代价计算,I.设USE(x,B)为x在B 中被定值前的引用次数，则循环L执行一次

19、，可省的执行代价为,USE(x,B),II.对基本块中定值基本块后的活跃变量x，省去指令 MOV Ri,Mx,可省执行代价,(2*LIVE(x,B),BL,省的执行代价,BL,USE(x,B)+,(2*LIVE(x,B),BL,电子科技大学计算机科学与工程学院,a:=b+cd:=d-be:=a+f,f:=a-d,b:=d+fe:=a-c,b:=d+c,acdef,cdef,bcdef,bcdef,B1,B2,B3,B4,电子科技大学计算机科学与工程学院,B1,B2,B3,B4,a,b,c,d,e,f,1,1,2,2,2,2,1,1,1,1,1,1,1,2,2,2,1,2,1,4,6,3,6,4

20、,4,若有三个可固定分配的寄存器,则 b、d可固定分配寄存器，另一个分配给a、e、f中的一个,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,作业,12.1，12.5，12.6，12.7,12.8,电子科技大学计算机科学与工程学院,内容回顾,1.局部优化,2.全局优化,基本块的划分,出口语句,入口语句,入口语句,入口语句,循环优化,循环的定义,程序流图,G=(N,E,n0）,循环的查找,必经节点,回边,合并已知量,公共子表达式,无用赋值,死代码,必经节点集,回边循环,第五节 参数传递,先看例子:procedure swap(a,b:integer);var temp:int

21、eger;begin temp:=a;a:=b;b:=temp end;call swap(x,y);.,形式参数,实在参数,1.程序单元间通信方式有非局部环境和参数传递2.参数，形参，实参3.参数传递的三种类型：数据参数传递 过程参数传递 类型参数传递,几点说明:,以调用 swap(i,ai)为例，且调用前 i=3 a 的几个元素分别为7，1，4，5，8,1.引用调用（传地址）,在单元中对形参的引用，实际上是对形式单元中实参地址的间接引用,将实参的地址传递给相应的形参,swap(i,ai);相当于执行:a:=i的地址;b:=a3的地址;temp:=a;(temp=3)a:=b;(i=4)b:

22、=temp;(a3=temp=3)执行结果:i=4,a3=3,2.值调用,形参只起局部变量作用(1)传值:实参的值形式单元(2)结果调用:形参的结果值实参单元(3)传值得结果：实参的值形式单元 形参的结果值实参单元 实现技术：一个形参对应两个单元,对“传值得结果”swap(i,ai);相当于执行:a1:=i的地址;a2:=3;b1:=a3的地址;b2:=4;temp:=a2;(temp=a2=3)a2:=b2;(a2=b2=4)b2:=temp;(b2=temp=3)a1:=a2;(i=a2=4)b1:=b2;(a3=b2=3)执行结果:i=4,a3=3,3.名调用,用实参原样替换形参的出现若

23、被调用单元中的局部名与调用处的名发生冲突，则对局部名重新命名实现技术：把实参处理成一个子程序（thunk,称为参数子程序），对形参的每次引用就调用该子程序,swap(i,ai);相当于执行:temp:=i;(temp=i=3)i:=ai;(i=a3=4)ai:=temp;(ai=a4=temp=3)执行结果:i=4,a4=3(a3不变),练习,program main;var a,b:integer;procedure P(x,y,z)beginy:=y+1;z:=z+x;end begina:=2;b:=3;P(a+b,a,a);Write(a,b);End.,对引址调用、传值和名调用三种参数传递方式，打印的a,b的值分别是什么,