资源描述：
《编译原理分知识点习题代码优化》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1．与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除假设源程序指令序列a:=b+c;c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOVb,R0ADDc,R0MOVR0,aSUBd,R0MOVR0,c假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用例如，如果目标机器指令系统包含增1指令INC，对于i:=i+1的目标代码MOVi,R0ADD#1,R0MOVR0,i便可被代之以1条指令Inci说明：优化的特点是每个
2、改进可能会引发新的改进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。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)优化后的四元式序列。解答：该表达式的四元式序列为：（
3、1）（*，b,c,T1）（2）(+,a,T1,T2)（1）(*,c,b,T3)（2）(+,T3,a,T4)（3）(-,T4,e,T5)（4）(*,b,c,T6)（5）(+,T6,d,T7)（6）(/,T5,T7,T8)（7）(-,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)试给出其优化后
4、的三元式序列。解答：该算术表达式的三元序列为：（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),
5、(2))(9)(+,(4),(8))5.试对以下基本块B1和B2应用DAG进行优化B1:A:=B*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=FM:=LB2:B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L并就以下两种情况分别写出优化后的四元式序列：（1）假设G、L、M在基本块后面要被引用;（2）假设只有L在基本块后面要被引用。解答:一般应用DAG在一个基本块内可以进行三种优化:合并常量、删除无用赋值以及多余运算。对于基本块B1,其DAG如图7.1所示。9857
6、F16342F,L,M*E*+H*A,GD*/BC2图7.1基本块B1的DAG图优化后的四元式序列如下:(1)若只有G、L、M在基本块后面要被引用G:=B*C或G:=B*CH:=G*GS:=G*GL:=H*GL:=S*GM:=LM:=L(S为临时变量)(2)若只有L在基本块后面要被引用G:=B*C或S1:=B*CH:=G*GS2:=S1*S1L:=H*GL:=S2*S1(S1、S2为临时变量)对于基本块B2,其DAG如图7.2所示。381726954GL,M*F,J++D,HE,L+*BK3AC15图7.2基本块B2的DAG图优化后的四元式序列如下:(1)若只有G、L、M
7、在基本块后面要被引用D:=A+CE:=A*CF:=D+EG:=3*FL:=F+15M:=L(2)若只有L在基本块后面要被引用D:=A+C或S1:=A+CE:=A*CS2:=A*CF:=D+ES3:=S1+S2L:=F+15L:=S3+15(S1、S2、S3为临时变量)6.对于基本块PS0:=2S1:=3/S0S2:=T-CS3:=T+CR:=S0/S3H:=RS4:=3/S1S5:=T+CS6:=S4/S5H:=S6*S2(1)试应用DAG进行优化。(2)假定只有R、H在基本块出口是活跃的,试写出优化后的四元式序列。(3)假定
