编译原理分知识点习题代码优化.doc

1与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除假设源程序指令序列a:=b+c; c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOV b, R0ADD c, R0MOV R0,aSUB d, R0MOV R0,c假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用例如，如果目标机器指令系统包含增1指令INC，对于i:=i+1的目标代码MOV i, R0ADD #1, R0MOV R0, i便可被代之以1条指令Inc i说明：优化的特点是每个改进可能会引发新的改进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。2设有语句序列a:=20b:=a*(a+10);c:=a*b;试写出合并常量后的三元式序列。解答：该语句序列对应的三元式序列为：（1） （:=, 20,a）（2） (+, a, 10)（3） (*, a, (2) )（4） (:=, a, b)（5） (* a, b)（6） (:=, (5), c)合并常量后的三元式序列为：（1） （:=, 20，a）（2） (:=, 600, b)（3） (:=, 12000, c)3、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。解答：该表达式的四元式序列为：（1） （*，b,c,T1）（2） (+,a,T1,T2)（3） (*,c,b,T3)（4） (+,T3,a,T4)（5） (-,T4,e,T5)（6） (*,b,c,T6)（7） (+,T6,d,T7)（8） (/,T5,T7,T8)（9） (-,T2,T8,T9)可对该表达式进行删除公共子表达式的优化。优化后的四元式序列为：（1） （*，b,c,T1）（2） (+,a,T1,T2)（3） (-,T2,e,T5)（4） (+,T1,d,T7)（5） (/,T5,T7,T8)（6） (-,T2,T8,T9)4.设有算术表示式（a*b+c）/(a*b-c)+(c*b+a-d)/(a*b+c)试给出其优化后的三元式序列。解答：该算术表达式的三元序列为：（1） （*,a,b）（2） (+,(1),c)（3） (*,a,b)（4） (-,(3),c)（5） (/,(2),(4)（6） (*,c,b)（7） (+,(6),a)（8） (-,(7),d)（9） （*,a,b）（10） (+,(9),c)（11） (/,(8),(10)（12） (+,(5),(11)可对其进行删除公共子表达式的优化。优化后的三元式列为：（1）（*，a,b） (2) (+,(1),c)(3) (-,(1),c)(4) (/,(2),(3)(5) (*, c, b)(6) (+,(5),a)(7) (-,(6),d)(8) (/,(7),(2)(9) (+,(4),(8)5.试对以下基本块B1和B2应用DAG进行优化B1: A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G F:=H*G L:=F M:=LB2: B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L 并就以下两种情况分别写出优化后的四元式序列：（1） 假设G、L、M在基本块后面要被引用;（2） 假设只有L在基本块后面要被引用。解答:一般应用DAG在一个基本块内可以进行三种优化:合并常量、删除无用赋值以及多余运算。对于基本块B1,其DAG如图7.1所示。9857F16342 F , L , M * E * +H * A , G D * / B C 2 图7.1 基本块B1的 DAG图优化后的四元式序列如下:(1) 若只有G、L、M在基本块后面要被引用 G:=B*C 或 G:=B*C H:=G*G S:=G*G L:=H*G L:=S*G M:=L M:=L (S为临时变量)(2)若只有L在基本块后面要被引用G:=B*C 或 S1:=B*C H:=G*G S2:=S1*S1 L:=H*G L:=S2*S1 (S1、S2为临时变量)对于基本块B2,其DAG如图7.2所示。381726954 G L,M* F,J + + D,H E,L + * B K3 A C 15 图7.2 基本块B2的DAG图优化后的四元式序列如下:(1) 若只有G、L、M在基本块后面要被引用D:=A+CE:=A*CF:=D+EG:=3*FL:=F+15M:=L(2) 若只有L在基本块后面要被引用D:=A+C 或 S1:=A+CE:=A*C S2:=A*CF:=D+E S3:=S1+S2L:=F+15 L:=S3+15(S1、S2、S3为临时变量)6. 对于基本块P S0:=2 S1:=3/S0 S2:=T-C S3:=T+C R:=S0/S3 H:=RS4:=3/S1 S5:=T+CS6:=S4/S5H:=S6*S2(1) 试应用DAG进行优化。(2) 假定只有R、H在基本块出口是活跃的,试写出优化后的四元式序列。(3) 假定只有两个寄存器R0、R1试写出上述优化后的四元式序列的目标代码。解答: (1) 构造DAG如图7.3 所示。1H0473652 H R, ,S6 S2 / - S3,S5 + S0,S4 S1 2 1.5 T C 图7.3基本块P的DAG图优化后的四元式序列为:S0:=2 S4:=2 S1:=1.5 S2:=T-C S3:=T+CS5:=S3R:=2/S3S6:=RH:=S6*S2(2) 若只有R、H在基本块出口是活跃的,优化后的四元式序列为:S2:=T-C S3:=T+CR:=2/S3H:=R*S2(3) 假定只有两个寄存器R0、R1,上述优化后的四元式序列的目标代码为: LD R0 T SUB R0 C ST R0 S2 LD R0 T ADD R0 C LD R1 2 DIV R1 R0 LD R0 S2 MUL R1 R0 ST R1 H7. 设有入图7.4所示的程序流程图:B8B2B3B4B7B6B5B1 图7.4 程序流图(1) 求出流图中各个结点n的必经结点集D(n);(2) 求出该流图中的回边;(3) 求出该流图中的循环。解答:(1) 在程序流图中,对任意的结点ni和nj ,如果从流图的首结点出发,到达nj的任一通路都必须经过ni,则称ni是nj的必经结点,记为ni DOM nj。流图中结点n的所有必经结点称为结点n的必经结点集,记为 D (n)。 流图中各结点n的必经结点集 D (n)为:D (B1) =B1D (B2) =B1,B2D (B3) =B1,B2,B3D (B4) =B1,B2,B3,B4D (B5) =B1,B2,B3,B5D (B6) =B1,B2,B3,B6D (B7) =B1,B2,B7D (B8) =B1,B2,B7,B8(2) 流图的回边是指: 若ab是流图中一条有向边,且有b DOM a,则称ab是流图的一条回边。题目所给流图中,有有向边B7B2,又有D (B7)=B1,B2,B7,所以, B2 DOM B7, 即B7B2是流图的回边。且无其他回边。(3) 该流图中的循环可利用回边求得。如果以知有向边nd是一回边,由它组成的循环就是由结点d、结点n以及有通路到达n而该通路不经过d的所有结点组成,且d是该循环的唯一入口结点。题目所给出流图中,只有一条回边B7B2,在该流图中,凡是不能经过结点B2有通路到达结点B7的结点,只有B3,B4,B5,B6,所以,由回边B7B2组成的循环是 B2,B3,B4,B5,B6,B7。8. (中国科学院计算机所1997年) 试画出如下中间代码序列的程序流图,并求出:(1) 各结点的必经结点集合D (n);(2) 流图中的回边与循环。J:=0; L1: I:=0; if I8 goto L3; L2: A:=B+C; B:=D*C; L3: if B=0 goto L4; Write B; goto L5; L4: I:=I+1; if I8 goto L2;L5: J:=J+1; if J=3 goto L1; HALT 解答: 程序的流图入图7.5所示。 (1) 各结点的必经结点集分别为:D (n0) =n0D (n1) =n0,n1D (n2) =n0,n1,n2D (n3) =n0,n1,n3D (n4) =n0,n1,n3,n4D (n5) =n0,n1,n3,n5D (n6) =n0,n1,n3,n6D (n7) =n0,n1,n3,n6,n7J:=0;L1: I:=0; if I8 goto L3;L2: A:=B+C; B:=D*C;L3: if B=0 goto L4;Write B; goto L5;L4: I:=I+1; if I8 goto L2;L5: J:=J+1;if J=3 goto L1;HALTn0 n1n2n3n4n5n6n7图7.5程序流图（2） 流图中的回边有一条：即n6n1 该回边表示的循环为：（n1,n2,n3,n4,n5,n6）,入口为n1,出口为n69.(武汉大学1991年)试对下面的程序段进行尽可能的优化： i：= j：=readkl： x：=k* i y: =j* i z: =x*y write j i:=i+1 if i100 goto l halt并指明你进行了何种优化，给出优化过程的简要说明及每种优化后的结果形式。解答：程序的流程图如下所示： i：=j：=readk 1：l： x：=k* i y: =j* i z: =x*y write j i:=i+1 if i100 goto l halt2:halt3:图7.6程序流图由程序流图可知，为一个循环。对于本题中的循环可进行以下优化：削减强度循环中有x:=x*i y:=y*i j,k在循环中不改变值。i每次增加,x和y的赋值运算可进行强度削减，于是程序流图变为图7.7所示。i：=j：=readk B1:x：=0y：=0 B2: l： x：=x+ky：=y+10z：=x*ywrite ji：=i+1if ijh100 goto l ： haltB3:图7.7削减强度后的程序流图删除归纳变量由于i是循环中的基本归纳变量，x、y是与y同族的归纳变量，且有线性关系x：=k*i y：=j*i 所以，i100完全可用x100*k或y100*j代替。于是，进一步优化为图7.8所示。代码外提将循环中不变运算write j tl:=100*k 提到循环外的前置节点B21中，于是程序流图变为7.9所示的情形。i：=j：=readkx：=0y：=0 l： x：=x+ky：=y+10z：=x*ywrite jtl:=100*kif ijhtl goto l halt B1: B2B2: B3: 图7.8归纳变量后的程序流图i：=j：=readkB1:x：=0y：=0write jtl:=100*k B2:l： x：=x+ky：=y+10z：=x*y if ijhtl goto l B2: halt B3: 图7.9代码外提后的程序流图10.在循环优化中，为什么要代码外提？试说明在哪些情况下代码可外提？解答：代码外提可以减少循环中的指令数目，从而节省目标代码运行的时间。对于循环中L的每一个不变运算s：A：=B op C 或 A：=B检查它是否满足以下两个条件：（1） （a）s所在的节点是L的所有的出口节点的必经节点；（b）在中其他地方未再定值；（c）中所有的引用点只有s中的定植才能到达。(2) 离开后不再是活跃的，并且条件（）中的（a）和（b）成立，所谓离开后不再是活跃的，是指在的任何出口节点的后继节点（当然是指那些不属于的后继）入口处不是活跃的。符合上述（）或（）的不变运算s可以外提到的前置节点中。但是。S的运算对象（或）是在中定植的，那么只有当这些定植代码都已外提到前置节点中时。才能把s也提到前置节点中。11.以下循环是最内循环，是对其进行循环优化。 A := 0 I := 1L1: B := J + 1C := B + IA := C + AIF I = 100 GOTO L2I := I + 1GOTO L1L2:解答：程序的流程图如图所表示有流程图可见，B2, B3是一个循环，该循环可进行以下有话：代码外提 B2中的 B := J + 1是循环的不变运算，可提到循环外。删除归纳变量 I是循环的基本归纳变量，C是与I同组的归纳变量，且二者有如下线性关系： C: := B + I于是I = 100 完全可用 C = B + 100代替。相应的I := I +1可用C := C + 1代替。 于是流程图变为图所表示图7.10 优化后的程序流图14设有循环语句FOR i:=1 TO n DO BEGINa a:=u*v b:=m*m c:=c+b*bEND试写出循环外提后的结果。解答：该语句的四元式为：（1）（:=，1, , i）（2）) (-, n, i, T0 )（3）(BMZ, T0, ，（14）)（4）（*，u, v, T1 ）（5）（:=, T1， ， a）（6）（*， m, m, T2）（7）（:=, T2， ， b）（8）（*，b, b, T3）（9）