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

第十二章代码优化和目标代码生成,本章主要讨论以下两个问题：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)ift3vgoto(9)(13)ifi=jgoto(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,BjN，若满足下列条件之一，则BiBj,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)ift3vgoto(9),(13)ifi=jgoto(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:=OPB或A:=BOPC这样的语句，若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+3K:=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*AG:=B-4K:=2+EI:=E*GL:=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的必经结点，记为dDOMn,流图的首结点是流图中任一结点的必经结点即n0DOMn,每个结点是它本身的必经结点，即nDOMn,必经结点集：流图中结点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，有nDOMn传递性：若n1DOMn2,n2DOMn3，则n1DOMn3反对称性：若n1DOMn2,n2DOMn1，则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:=ic同族归纳变量，j:=c1ic2,变成j:=jc1c,但j必须在循环外赋初值j:c1*ic2,电子科技大学计算机科学与工程学院,3.删除归纳变量,即改用同族归纳变量作为判断条件例如将i10改为t3100+t1因原来t3:=10*i+t1，而100t1即10*10+t1,电子科技大学计算机科学与工程学院,电子科技大学计算机科学与工程学院,例,电子科技大学计算机科学与工程学院,另例：(1)PROD:=0(2)I:=1(3)T1:=4*I(4)T2:=a04(5)T3:=T2T1(6)T4:=4*I(7)T5:=b04(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)ifI20goto(3),电子科技大学计算机科学与工程学院,删除多余运算，代码外提,删除多余运算，代码外提(1)PROD:=0(2)I:=1(4)T2:=a04(7)T5:=b04(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)ifI20goto(3),电子科技大学计算机科学与工程学院,强度削弱,强度削弱(1)PROD:=0(2)I:=1(4)T2:=a04(7)T5:=b04(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)ifI20goto(5),电子科技大学计算机科学与工程学院,强度削弱(1)PROD:=0(2)I:=1(4)T2:=a04(7)T5:=b04(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)ifI20goto(5),电子科技大学计算机科学与工程学院,变换循环控制条件,变换循环控制条件(1)PROD:=0(2)I:=1(4)T2:=a04(7)T5:=b04(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)ifT180goto(5),电子科技大学计算机科学与工程学院,合并已知量,(1)PROD:=0(2)I:=1(4)T2:=a04(7)T5:=b04(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)ifT180goto(5),电子科技大学计算机科学与工程学院,1.代码生成的任务将中间代码翻译成等价有效的目标代码2.代码生成器的输入中间代码，符号表3.代码生成器的输出目标代码绝对机器代码可重定位代码汇编码,第三节目标代码生成,电子科技大学计算机科学与工程学院,op源，目的其中op是操作码；源和目的是两个操作对象，可以是内存地址、寄存器或常数（1）直接地址型opRi,M(Ri)op(M)=Ri（2）寄存器型opRi,Rj(Ri)op(Rj)=Ri,4.抽象机的指令形式,电子科技大学计算机科学与工程学院,（3）变址型opRi,C(Rj)(Ri)op(Rj)+C)=Ri（4）间接型opRi,*Rj(Ri)op(Rj)=RiopRi,*M(Ri)op(M)=RiopRi,*C(Rj)(Ri)op(Rj)+C)=Ri,电子科技大学计算机科学与工程学院,（5）其它几种常用指令MOVRi,M(Ri)=MMOVM,Ri(M)=RiJxgotox,电子科技大学计算机科学与工程学院,5.简单的代码生成方法,（1)p:x:=yopz的翻译MOVy,RiopRi,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,MOVa,R0SUBR0,b(t占用R0)MOVa,R1ADDR1,c(u占用R1)MOVR1,u(释放R1)MOVa,R1SUBR1,R0(v占用R1）MOVR1,v(释放R1)ADDR1,u(w占用R1),假设可以两个寄存器,电子科技大学计算机科学与工程学院,6.循环中的寄存器的分配,(1)指令的执行代价该指令访问主存的次数寄存器型opRi，Rj执行代价为1直接地址型opRi，M执行代价为2变址型opRi，C(Rj)执行代价为2间址型opRi,*Rj执行代价为2opRi,*M执行代价为3opRi,*C(Rj)执行代价为3,电子科技大学计算机科学与工程学院,BL,（2）固定分配寄存器节省的代价计算,I.设USE(x,B)为x在B中被定值前的引用次数，则循环L执行一次，可省的执行代价为,USE(x,B),II.对基本块中定值基本块后的活跃变量x，省去指令MOVRi,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）,循环的查找,必经节点,回边,合并已知量,公共子表达式,无用赋值,死代码,必经节点集,回边循环,第五节参数传递,先看例子:procedureswap(a,b:integer);vartemp:integer;begintemp:=a;a:=b;b:=tempend;callswap(x,y);.,形式参数,实在参数,1.程序单元间通信方式有非局部环境和参数传递2.参数，形参，实参3.参数传递的三种类型：数据参数传递过程参数传递类型参数传递,几点说明:,以调用swap(i,ai)为例，且调用前i=3a的几个元素分别为7，1，4，5，8,1.引用调用（传地址）,在单元中对形参的引用，实际上是对形式单元中实参地址的间接引用,将实参的地址传递给相应的形参,swap(i,a