《编译原理(王晓斌)第十二章.ppt》由会员分享，可在线阅读，更多相关《编译原理(王晓斌)第十二章.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、程序设计语言与编译第十二章代第十二章代码优化和目化和目标代代码生成生成本章主要讨论以下两个问题：本章主要讨论以下两个问题：1.1.如何对中间代码进行优化；如何对中间代码进行优化；2.2.如何由优化后的中间代码生成有效和目标代码；如何由优化后的中间代码生成有效和目标代码；电子科技大学计算机科学与工程学院程序设计语言与编译一、优化的定义一、优化的定义第一节第一节 局部优化局部优化优化是一种等价的，有效的程序变换等价等价不改变程序运行结果有效有效时空效率要高电子科技大学计算机科学与工程学院程序设计语言与编译二、不同阶段的优化二、不同阶段的优化局部优化：在基本块内的优化局部优化：在基本块内的优化全局优
2、化：超越基本块，在基本块之间的优化全局优化：超越基本块，在基本块之间的优化1.源程序阶段的优化：考虑DS和算法2.编译优化中间代码优化和目标代码优化电子科技大学计算机科学与工程学院中间代码优化局部优化和全局优化程序设计语言与编译三、划分基本块和构造程序流图三、划分基本块和构造程序流图1.划分基本块基本块基本块是指程序中的一段语句（四元式）序列。一个入口语句，即程序中该语句序列的第一个语句；一个出口语句，即该语句序列的最后一个语句；（1 1）入口语句）入口语句紧跟在条件转向语句后的那个语句程序的第一条语句能由条件或无条件转向语句转移到的语句(2)(2)出口语句出口语句转向语句停止语句电子科技大学
3、计算机科学与工程学院程序设计语言与编译 入口语句 入口语句 入口语句 入口语句 转向语句 停语句(3)(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)goto(9)(13)if i=j goto(23)goto(23)(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20
4、)t10:=4*j(21)at10:=x(22)goto(5)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:=xB B1 1B B2 2B B3 3B B4 4B B5 5B B6 6例例程序设计语言与编译2.构造流图G=(N,E,nG=(N,E,n0 0）(1)基本块集即为结点集N;(2)含程序第一个语句的基本块为首结点n0;(3)设Bi,Bj N，若满足下列条件之一，则Bi Bj Bj 紧跟在Bi 之后，且Bi 的出口语句不是无条件转向
5、或停止语句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(9)goto(9)(13)if i=j goto(23)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)goto(
6、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:=xB B1 1B B2 2B B3 3B B4 4B B5 5B B6 6程序设计语言与编译四、基本块内的优化四、基本块内的优化对于A:=OP B 或 A:=B OP C这样的语句，若B及C为常数，则编译时可以把它们计算出来，把值存放在临时单元中，相应的语句变成A:=T;1.合并已知量2.删除公共子表达式也叫删除多余运算；例如两条赋值语句A:=B+C*DU:=V-C*D中有两次C*D运算。只计算
7、一次，将值存在临时单元中T第二个语句改为：U:=V-T电子科技大学计算机科学与工程学院程序设计语言与编译4.删除死代码例如四元式序列 (p)A:=B+D (q)A:=M+N中没有对A的引用，则第一个赋值无用，可删除。3.删除无用赋值iF语句条件为定值电子科技大学计算机科学与工程学院程序设计语言与编译F:=1F:=1F:=1F:=1I:=H*GI:=H*GC:=C:=F F F F+E+EJ:=J:=D/4D/4D/4D/4D:=F+3 D:=F+3 D:=F+3 D:=F+3 K:=K:=J+CJ+CJ+CJ+CB:=A*AB:=A*AL:=HL:=HG:=B-G:=B-D D D DL:=I
8、-L:=I-J J J JH:=EH:=E合并已知量合并已知量F:=1F:=1I:=I:=H*GH*GC:=1+EC:=1+EJ:=1J:=1D:=4D:=4K:=2+EK:=2+EB:=A*AB:=A*AL:=HL:=HL:=HL:=HG:=B-4G:=B-4L:=I-1L:=I-1H:=H:=E E删除公共子表达式；删除公共子表达式；I:=E*GI:=E*G删除无用赋值；删除无用赋值；假定假定F,C,DF,C,D和和J J在基本块外不再引用，可得结果：在基本块外不再引用，可得结果：B:=A*A G:=B-4 K:=2+EI:=E*G L:=I-1电子科技大学计算机科学与工程学院例例1 1程
9、序设计语言与编译(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 2电子科技大学计算机科学与工程学院删除公共子表达式程序设计语言与编译第二节第二节 全局优化全局优化一、循环的定义一、循环的定义全局优化有很多种，本节只讨论循环优化；如何找出程序中的所有循环？循环优化有哪些？循环是程序
10、流图中有唯一入口结点的强连通子图入口结点入口结点:子图中满足下列条件的结点n:或者n是流图的首结点,或者在子图外有一结点m,它有一有向边mn引向结点n;强连通子图强连通子图:任意两个结点可互相连联通电子科技大学计算机科学与工程学院程序设计语言与编译12345 56789105,6,7,8,95,6,7,8,9例例:电子科技大学计算机科学与工程学院是循环是循环,44，不是循环不是循环不是循环不是循环程序设计语言与编译二、循环的的查找二、循环的的查找1.必经节点从流图的首结点出发到达结点n的任一通路都必须经过的结点d,称d为n的必经结点，记为d DOM n流图的首结点是流图中任一结点的必经结点 即
11、n0 DOM n每个结点是它本身的必经结点，即n DOM n必经结点集必经结点集：流图中结点n的所有必经结点的集合，称为n的必经结点集，记为D(n)电子科技大学计算机科学与工程学院程序设计语言与编译1 12 23 34 45 56 67 78 89 91010D(1)=1D(1)=1D(2)=1,2D(2)=1,2D(3)=1,2,3D(3)=1,2,3D(4)=1,2,4D(4)=1,2,4D(5)=1,2,4,5D(5)=1,2,4,5D(6)=1,2,4,5,6D(6)=1,2,4,5,6D(7)=1,2,4,5,6,7D(7)=1,2,4,5,6,7D(8)=1,2,4,5,6,8D(
12、8)=1,2,4,5,6,8D(9)=1,2,4,5,6,9D(9)=1,2,4,5,6,9D(10)=1,2,4,10D(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电子科技大学计算机科学与工程学院程序设计语言与编译1 12 23 34 45 56 6
13、7 78 89 910102.回边流图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.1.1.1.回边回边回边回边5 5 5 54 4 4 4构成循环构成循环 5,4,6,7,8,9 5,4,6,7,8,92.2.2.2.回边回边回边回边9 9
14、 9 95 5 5 5构成循环构成循环 9,5,6,7,8 9,5,6,7,83.3.3.3.回边回边回边回边101010102 2 2 2构成循环构成循环 10,2,3,4,5,6,7,8,9 10,2,3,4,5,6,7,8,93.由回边构成的循环1 12 24 43 35 56 69 910107 78 81 12 24 43 35 56 69 910107 78 81 12 24 43 35 56 69 910107 78 81 12 24 43 35 56 69 910107 78 8程序设计语言与编译二、循环优化二、循环优化1.代码外提2.强度削弱基本归纳变量基本归纳变量，i有唯一
15、定值，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)i:=1(2)if i10 goto(16)(3)t1:=2*j (4)t2:=10*i(5)t3:=t2+t1 (6)t4:=a0-11(7)t5:=2*j (8)t6:=1
16、0*i(9)t7:=t6+t5 (10)t8:=a0-11(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto(2)(16).B B1 1B B2 2B B3 3B B4 4例例(1)i:=1(4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(15)goto(2)(16).(2)if i10 goto(16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t
17、8:=a0-11B B1 1B B2 2B B3 3B B4 4BB2 2代码外提后的流图代码外提后的流图代码外提后的流图代码外提后的流图程序设计语言与编译电子科技大学计算机科学与工程学院(1)i:=1(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (14)i:=i+1(4)t2:=t2+10 (8)t6:=t6+10(5)t3:=t3+10 (9)t7:=t7+10(15)goto(2)(16).(2)if i10 goto(16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11(4)t2:=10*i (8)t6:
18、=10*i(5)t3:=t2+t1 (9)t7:=t6+t5 B B1 1B B2 2B B3 3B B4 4BB2 2强度削弱后的流图强度削弱后的流图强度削弱后的流图强度削弱后的流图(1)i:=1(11)t9:=t8t7 (12)t10:=t9+1(13)t4t3:=t10 (4)t2:=t2+10(8)t6:=t6+10 (5)t3:=t3+10 (9)t7:=t7+10 (15)goto(2)(16).(2)if t3s goto(16)(3)t1:=2*j (6)t4:=a0-11(7)t5:=2*j (10)t8:=a0-11(4)t2:=10*i (8)t6:=10*i(5)t3:
19、=t2+t1 (9)t7:=t6+t5(2)s:=100+t1 B B1 1B B2 2B B3 3B B4 4BB2 2删除归纳变量后的流图删除归纳变量后的流图删除归纳变量后的流图删除归纳变量后的流图2106优化后化后06413优化前化前变址加址加加法数加法数乘法数乘法数语句数句数B3 3 3 3B B B B3 3 3 3优化前后的比较优化前后的比较优化前后的比较优化前后的比较程序设计语言与编译另例：(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:=
20、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)电子科技大学计算机科学与工程学院强度削弱强度削弱程序设计
21、语言与编译强度削弱强度削弱 (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
22、(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)电子科技大学计算机科学与工程学院合并已知量合并已知量程序设计
23、语言与编译 (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 源
24、，目的 其中op是操作码；源和目的是两个操作对象，可以是内存地址、寄存器或常数 （1）直接地址型 op Ri,M (Ri)op(M)=Ri （2）寄存器型 op Ri,Rj (Ri)op(Rj)=Ri4.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）其它几种常用指令MO
25、V Ri,M (Ri)=MMOV M,Ri (M)=RiJ x goto x电子科技大学计算机科学与工程学院程序设计语言与编译5.5.简单的代码生成方法简单的代码生成方法（1)p:x:=y op z 的翻译 MOV y,Ri op Ri,z 电子科技大学计算机科学与工程学院结果（x 的值）在寄存器Ri中程序设计语言与编译(2)为 结果（x）分配寄存器的方法1.y 本身占有寄存器Ri，且y在p点后不再被引用2.有空余的可用寄存器Ri3.寄存器均被占用：保存副本，选择一个最好选择占用Ri的变量在主存中已有副本的或者在p点后该变量不再被引用的或者在离p点最远处才被引用的电子科技大学计算机科学与工程学
26、院程序设计语言与编译例:基本块中有如下指令：t:=a-bu:=a+cv:=a-tw:=v+uMOV 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.6.循环中的寄存器的分配循环中的寄存器的分配(1)指令的执行代价 该指令访问主存的次数寄存器型 op Ri，Rj 执行代价为1直接地址型 op Ri，M 执行代价为2变址型 op Ri，C(Rj)执
27、行代价为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+ca:=b+cd:=d-bd:=d-be:=a+f
28、e:=a+ff:=a-df:=a-db:=d+fb:=d+fe:=a-ce:=a-cb:=d+cb:=d+cacdefacdefcdefcdefbcdefbcdefbcdefbcdefB1B1B2B2B3B3B4B4电子科技大学计算机科学与工程学院程序设计语言与编译B1B2B3B4abcdef1122221111111222121463644若有三个可固定分配的寄存器,则 b、d可固定分配寄存器，另一个分配给a、e、f中的一个电子科技大学计算机科学与工程学院程序设计语言与编译电子科技大学计算机科学与工程学院作作作作业业12.1，12.5，12.6，12.7,12.8程序设计语言与编译电子科技大
29、学计算机科学与工程学院内容回顾内容回顾1.局部优化2.全局优化基本块的划分出口语句入口语句入口语句入口语句循环优化循环的定义程序流图G=(N,E,nG=(N,E,n0 0）循环的查找必经节点回边合并已知量公共子表达式无用赋值死代码 必经节点集回边循环程序设计语言与编译第五节第五节 参数传递参数传递先看例子:procedure swap(a,b:integer);var temp:integer;begin temp:=a;a:=b;b:=temp end;call swap(x,y);.形式参数形式参数实在参数实在参数程序设计语言与编译1.程序单元间通信方式有非局部环境和参数传递2.参数，形参
30、，实参3.参数传递的三种类型：数据参数传递 过程参数传递 类型参数传递几点说明几点说明:程序设计语言与编译以调用 swap(i,ai)为例，且调用前 i=3 a 的几个元素分别为7，1，4，5，8程序设计语言与编译1.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.2.值调用值调用形参只起局部变
31、量作用形参只起局部变量作用 (1)(1)传值传值:实参的值实参的值形式单元形式单元 (2)(2)结果调用结果调用:形参的结果值形参的结果值实参单元实参单元 (3)(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)
32、b1:=b2;(a3=b2=3)执行结果:i=4,a3=3程序设计语言与编译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;program main;var a,b:integer;var a,b:integer;procedure P(x,y,z)procedure P(x,y,z)beginbeginy:=y+1;y:=y+1;z:=z+x;z:=z+x;endend begin begina:=2;a:=2;b:=3;b:=3;P(a+b,a,a);P(a+b,a,a);Write(a,b);Write(a,b);End.End.对引址调用、传值和名调用对引址调用、传值和名调用三种参数传递方式，打印的三种参数传递方式，打印的a,ba,b的值分别是什么的值分别是什么