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

第十二章代码优化和目标代码生成,本章主要讨论以下两个问题：1.如何对中间代码进行优化；2.如何由优化后的中间代码生成有效和目标代码；,电子科技大学计算机科学与工程学院,一、优化的定义,第一节 局部优化,优化是一种等价的，有效的程序变换,等价不改变程序运行结果,有效时空效率要高,电子科技大学计算机科学与工程学院,二、不同阶段的优化,局部优化：在基本块内的优化全局优化：超越基本块，在基本块之间的优化,1.源程序阶段的优化：考虑DS和算法2.编译优化中间代码优化和目标代码优化,电子科技大学计算机科学与工程学院,中间代码优化局部优化和全局优化,三、划分基本块和构造程序流图,1.划分基本块,基本块是指程序中的一段语句（四元式）序列。一个入口语句，即程序中该语句序列的第一个语句；一个出口语句，即该语句序列的最后一个语句；,（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)if 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)含程序第一个语句的基本块为首结点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:=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,四、基本块内的优化,对于A:=OP B 或 A:=B OP C这样的语句，若B及C为常数，则编译时可以把它们计算出来，把值存放在临时单元中，相应的语句变成A:=T;,1.合并已知量,2.删除公共子表达式,也叫删除多余运算；例如两条赋值语句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-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,电子科技大学计算机科学与工程学院,删除公共子表达式,第二节 全局优化,一、循环的定义,全局优化有很多种，本节只讨论循环优化；,如何找出程序中的所有循环？循环优化有哪些？,循环是程序流图中有唯一入口结点的强连通子图,入口结点:子图中满足下列条件的结点n:或者n是流图的首结点,或者在子图外有一结点m,它有一有向边mn引向结点n;,强连通子图:任意两个结点可互相连联通,电子科技大学计算机科学与工程学院,1,2,3,4,5,6,7,8,9,10,5,6,7,8,9,例:,电子科技大学计算机科学与工程学院,是循环,4，,不是循环,不是循环,二、循环的的查找,1.必经节点,从流图的首结点出发到达结点n的任一通路都必须经过的结点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,电子科技大学计算机科学与工程学院,必经结点具有如下性质：自反性：即对任意结点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组成的循环。,该流图有三条回边：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,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,例,电子科技大学计算机科学与工程学院,另例：(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:=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)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)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 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 的翻译 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,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执行一次，可省的执行代价为,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,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:integer;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:=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.名调用,用实参原样替换形参的出现若被调用单元中的局部名与调用处的名发生冲突，则对局部名重新命名实现技术：把实参处理成一个子程序（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的值分别是什么,