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

1、1 .与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除假设源程序指令序列a:=b+c;c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOVb,RoADDc,RoMOVRo,aSUBd,RoMOVRo,c假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用例如，如果目标机器指令系统包含增1指令INC,对于i:=i+1的目标代码MOVi,RoADD#1,RoMOVRo,i便可被代之以1条指令Inci说明：优化的特点是每个改进可能会引发新的改

2、进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。2 .设有语句序列a:=20b:=a*(a+10);c:=a*b;试写出合并常量后的三元式序列。解答：该语句序列对应的三元式序列为：(1) (k,20,a)(2) (+,a,10)(3) (*,a,(2)(4) (:=,a,b)(5) (*a,b)(6) (:=,(5),c)合并常量后的三元式序列为：(1)(k,20,a)(2) (:=,600,b)(3) (:=,12000,c)3、试写出算术表达式a+b*c-(c*b+a-e)/(b*c+d)优化后的四元式序列。解答：该表达式的四元式序列为：(1) (*,b,c,)(2)

3、(+,a,Ti,T2)(3) (*,c,b,T3)(4) (+,T3,a,T4)(5) (-,T4,e,T5)(6) (*,b,c,T6)(+,T6,d,T7)(8) (/,T5,T7,T8)(9) (-,T2,T8,T9)可对该表达式进行删除公共子表达式的优化。优化后的四元式序列为:(1) (*,b,c,Ti)(2) (+,a,Ti,T2)(3) (-,T2,e,T5)(4) (+,Ti,d,T7)(5) (/,T5,T7,T8)(6) (-,T2,T8,T9)4.设有算术表示式(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)试给出其优化后的三元式序列。解答：该算术表达式的

4、三元序列为：(1) (*,a,b)(2) (+,(1),c)(3) (*,a,b)(4) (-,(3),c)(5) (/,(2),(4)(6) (*,c,b)(7) (+,(6),a)(8) 37),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),(

5、8)5: 试对以下基本块B1和B2应用DAG进行优化81: A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:二FM:二L82: B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L并就以下两种情况分别写出优化后的四元式序列：(1)假设GL、M在基本块后面要被引用；(2)假设只有L在基本块后面要被引用。解答：一般应用DAGS一个基本块内可以进行三种优化：合并常量、删除无用赋值以及多余运算。所示。对于基本块B,其DAG®图7.1如下、1优化后的四元式C图7.12基本块；B124

6、DAG图6(1)若只有GL、M在基本块后面要被引用G:=B*C或G:=B*CH:=G*GS:=G*GL:=H*GL:=S*GM:=LM:=L（S为临时变量）（2）若只有L在基本块后面要被引用G:=B*C或Si：=B*CH:=G*GS2：=Si*SiL:=H*GL:=S2*Si（S1、&为临时变量）对于基本块B2,其DAGta图7.2所示。+*3AC 15图7.2基本块B2的DAGffl优化后的四元式序列如下：(1)若只有GL、M在基本块后面要被引用D:=A+CE:=A*CF:=D+EG:=3*FL:=F+15M:=L(S1、S2、S3为临时变量)(2)若只有L在基本块后面要被引用D:=

7、A+C或S1：=A+CE:=A*CS2：=A*CF:=D+ES3：=S1+S2L:=F+15L:=S3+156.对于基本块PSo:=2Si：=3/SoS2：=T-CS3：=T+CR:=S0/S3H:二RS4：=3/S1S5：=T+CS6：=S4/S5H：=S6*S2(1)试应用DAG!行优化。假定只有R、H在基本块出口是活跃的，试写出优化后的四元式序列。(3)假定只有两个寄存器的、R试写出上述优化后的四元式序列的目标代码。解答：(1) 构造DAGfc图7.3所示H图7.3基本块P的DAGS优化后的四元式序列为：S0：=2S4：=2Si：=1.5S2：=T-CS3：=T+CS5：=S3R:=2/

8、S3S6：=RH：=S6*S2(2)若只有R、H在基本块出口是活跃的，优化后的四元式序列为XS2：=T-CS3：=T+CR:=2/S3H:=RS2(3)假定只有两个寄存器R0、Ri,上述优化后的四元式序列的目标代码为LDRoTSUBRoCSTRoS2LDRoTADDRoCLDRi2DIVRiRoLDRoS2MULRiRoSTRiH7.设有入图7.4所示的程序流程图图7.4程序流图(1)求出流图中各个结点n的必经结点集D(n);(2)求出该流图中的回边；(3)求出该流图中的循环。解答：(1)在程序流图中，对任意的结点ni和nj,如果从流图的首结点出发，到达nj的任一通路都必须经过ni,则称ni是

9、nj的必经结点，记为niDOMp流图中结点n的所有必经结点称为结点n的必经结点集，记为D(n)。流图中各结点n的必经结点集D(n)为：D(Bi)=B1D(B2)=B1,B2D(B3)=B1,B2,B3D(B4)=B1旧2旧3旧4D(B5)=B1,B2,B3,B5D(B6)=B1,B2,B3,B6D(B7)=B1,B2,B7D(B8)=B1,B2,B7,B8(2)流图的回边是指：若a-b是流图中一条有向边，且有bDOMa,则称a-b是流图的一条回边。题目所给流图中，有有向边6B2,又有D(B7)=B1,B2,B7,所以，B2DOM用即曲一B2是流图的回边。且无其他回边。(3)该流图中的循环可利用

10、回边求得。如果以知有向边n-d是一回边，由它组成的循环就是由结点d、结点n以及有通路到达n而该通路不经过d的所有结点组成，且d是该循环的唯一入口结点。题目所给出流图中，只有一条回边B7一电在该流图中，凡是不能经过结点B2有通路到达结点B7的结点，只有&旧4旧5旧6,所以，由回边&一场组成的循环是B2,B3,B4,B5,B6,B7。8.(中国科学院计算机所1997年)试画出如下中间代码序列的程序流图，并求出：(1) 各结点的必经结点集合D(n);(2) 流图中的回边与循环。J:=0;L1:I:=0;ifI<8gotoL3;L2:A:=B+C;B:=D*C;L3:ifB=0g

11、otoL4;WriteB;gotoL5;L4:I:=I+1;ifI<8gotoL2;L5:J:=J+1;ifJ<=3gotoL1;HALT解答：程序的流图入图7.5所示(1)各结点的必经结点集分别为D(n0)=n0D(n1)=no,n1D(n2)=no,ni,n2D(n3)=no,ni,n3D(n4)=no,ni,n3,n4D(n5)=no,ni,n3,n5D(n6)=no,ni,n3,n6D(n7)=no,ni,n3,n6,n7J:=0;no1'oLi:I:=0;ifI<8gotoL3;niL2:A:=B+C;n2B:=D*C;L3:ifB=0gotoL4;n3n4

12、WriteB;gotoL5;n5L4:I:=I+i;ifI<8gotoL2;L5:J:=J+i;ifJ<=3gotoLi;n6n7HALT图7.5程序流图(2)流图中的回边有一条：即n6ni该回边表示的循环为：(ni,n2,n3,n4,n5,n6),入口为ni,出口为防9.（武汉大学1991年）试对下面的程序段进行尽可能的优化:i：=1j:=10readkl：x：=k*iy:=j*iz:=x*ywriteji:=i+1ifi<100gotolhalt并指明你进行了何种优化，给出优化过程的简要说明及每种优化后的结果形式。解答：程序的流程图如下所示：i：=1j:=10readkl

13、：x：=k*iB 2:y:=j*iz:=x*ywriteji:=i+1ifi<100gotolhaltB3:图7.6程序流图由程序流图可知，B2为一个循环。对于本题中的循环可进行以下优化：削减强度循环中有x:=x*iy:=y*ij,k在循环中不改变值。i每次增加1,x和y的赋值运算可进行强度削减,于是程序流图变为图7.7所示。B1:i：=1j:=10readkx:=0y:=0B211:x：=x+ky：=y+10z:=x*ywriteji：=i+1ifijh<100gotol1haltB3:图7.7削减强度后的程序流图删除归纳变量由于i是循环中的基本归纳变量，x、y是与y同族的归纳变

14、量，且有线性关系x：=k*iy:=j*i所以，i<100完全可用x<100*k或y<100*j代替。于是，进一步优化为图7.8所示。代码外提将循环中不变运算writejtl:=100*k提到循环外的前置节点B21中，于是程序流图变为7.9所示的情形。i：=1j:=10readkx:=0y:=011：x：=x+ky:=y+10z:=x*ywritejtl:=100*kifijh<tlgotol1R:BI23：图7.8归纳变量后的程序流图i：=1j:=10readk2I:x:=0y:=0writejtl:=100*k2：l1:x:=x+ky：=y+10z:=x*yifijh

15、<tlgotol13：halt图7.9代码外提后的程序流图10 .在循环优化中，为什么要代码外提？试说明在哪些情况下代码可外提？解答：代码外提可以减少循环中的指令数目，从而节省目标代码运行的时间。对于循环中L的每一个不变运算s：A:=BopC或A:=B检查它是否满足以下两个条件：（1） （a）s所在的节点是L的所有的出口节点的必经节点；（b） A在L中其他地方未再定值；（c） L中所有A的引用点只有s中A的定植才能到达。（2） A离开L后不再是活跃的，并且条件（1）中的（a）和（b）成立，所谓A离开L后不再是活跃的，是指A在L的任何出口节点的后继节点（当然是指那些不属于L的后继）入口处不

16、是活跃的。符合上述（1）或（2）的不变运算s可以外提到L的前置节点中。但是。S的运算对象（8或。）是在L中定植的，那么只有当这些定植代码都已外提到前置节点中时。才能把s也提到前置节点中。11 .以下循环是最内循环，是对其进行循环优化。A:=0I :=1II :B:=J+1C:=B+IA:=C+AIFI=100GOTOL21 :=I+1GOTOL1L2:解答：程序的流程图如图所表示BlB2B3有流程图可见，B2,B3是一个循环，该循环可进行以下有话：代码外提B2中的B:=J+1是循环的不变运算，可提到循环外。删除归纳变量I是循环的基本归纳变量，C是与I同组的归纳变量，且二者有如下线性关系：C:=

17、B+I于是I=100完全可用C=B+100代替。相应的I:=I+1可用C:=C+1代替。于是流程图变为图所表示图7.10优化后的程序流图14.设有循环语句FORi:=1TOnDOBEGINaa:=u*vb:=m*mc:=c+b*bEND试写出循环外提后的结果。解答：该语句的四元式为：(1) (：=,1,i)(2) )(-,n,i,To)(3) (BMZ,To,(14)(4) (*,u,v,Ti)(5)(k,Ti,a)(6) (*,m,m,T2)(k,T2,b)(8) (*,b,b,T3)(9) (+,c,T3,T4)(10) (:二,T4,c)(11) (+,1,i,T5)(12) (:=,T5,i)(13) (BR,(2)由于a:=u*v；b:=m*m是循环的不变运算，均可外提；且b:=m*m;外提后，b*b也是循环的不变运算，也可外提。优化后的四元式如下：(1) (：=,1,i)(2) (*,u,v,Ti)(3)(k,Ti,a)(4) (*,m,m,T2)(5)(k,T2,b)(6)(*,b,b,T3)(k，0,c)(8) )(-,n,i,To)(9) (BMZ,To,(14)(10) (+,C,T3,T4)(11