编译原理分知识点习题代码优化_计算机-搜索引擎优化.pdf

1与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除 假设源程序指令序列 a:=b+c;c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOV b,R0 ADD c,R0 MOV R0,a SUB d,R0 MOV R0,c 假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用 例如，如果目标机器指令系统包含增 1 指令 INC，对于 i:=i+1 的目标代码 MOV i,R0 ADD#1,R0 MOV R0,i 便可被代之以 1 条指令 Inc i 说明：优化的特点是每个改进可能会引发新的改进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。2设有语句序列 a:=20 b:=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 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 9 8 5 7 F 1 6 3 4 2 F:=H*G L:=F M:=L B2: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 所示。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 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 3 8 1 7 2 6 9 5 4 H:=G*G S2:=S1*S1 L:=H*G L:=S2*S1 (S1、S2为临时变量)对于基本块 B2,其 DAG 如图 7.2 所示。G L,M *F,J +D,H E,L +*B K 3 A C 15 图 7.2 基本块 B2的 DAG 图 优化后的四元式序列如下:(1)若只有 G、L、M在基本块后面要被引用 D:=A+C E:=A*C F:=D+E G:=3*F L:=F+15 M:=L(2)若只有 L在基本块后面要被引用 D:=A+C 或 S1:=A+C E:=A*C S2:=A*C F:=D+E S3:=S1+S2 L:=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:=R S4:=3/S1 S5:=T+C 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 1 H 0 4 7 3 6 5 2 S6:=S4/S5 H:=S6*S2(1)试应用 DAG 进行优化。(2)假定只有 R、H在基本块出口是活跃的,试写出优化后的四元式序列。(3)假定只有两个寄存器 R0、R1试写出上述优化后的四元式序列的目标代码。解答:(1)构造 DAG 如图 7.3 所示。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+C S5:=S3 R:=2/S3 S6:=R H:=S6*S2 (2)若只有 R、H在基本块出口是活跃的,优化后的四元式序列为:S2:=T-C S3:=T+C R:=2/S3 H:=R*S2(3)假定只有两个寄存器 R0、R1,上述优化后的四元式序列的目标代码为:LD R0 T SUB R0 C ST R0 S2 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 B8 B2 B3 B4 B7 B6 B5 B1 LD R0 T ADD R0 C LD R1 2 DIV R1 R0 LD R0 S2 MUL R1 R0 ST R1 H 7.设有入图 7.4 所示的程序流程图:图 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)=B1 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 D(B2)=B1,B2 D(B3)=B1,B2,B3 D(B4)=B1,B2,B3,B4 D(B5)=B1,B2,B3,B5 D(B6)=B1,B2,B3,B6 D(B7)=B1,B2,B7 D(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)=n0 D(n1)=n0,n1 D(n2)=n0,n1,n2 D(n3)=n0,n1,n3 D(n4)=n0,n1,n3,n4 D(n5)=n0,n1,n3,n5 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 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 D(n6)=n0,n1,n3,n6 D(n7)=n0,n1,n3,n6,n7 n0 n1 n2 n3 n4 n5 n6 n7 图 7.5 程序流图（2）流图中的回边有一条：即 n6 n1 该回边表示的循环为：（n1,n2,n3,n4,n5,n6）,入口为 n1,出口为 n6 9.(武汉大学 1991 年)试对下面的程序段进行尽可能的优化：i：=j：=read k l：x：=k*i y:=j*i z:=x*y write j i:=i+1 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 if i100 goto l halt 并指明你进行了何种优化，给出优化过程的简要说明及每种优化后的结果形式。解答：程序的流程图如下所示：1：2:3:图 7.6 程序流图 由程序流图可知，为一个循环。对于本题中的循环可进行以下优化：削减强度 循环中有 x:=x*i y:=y*i j,k在循环中不改变值。i 每次增加,x 和 y 的赋值运算可进行强度削减，于是程序流图变为图 7.7 所示。B1:B2:i：=j：=read k l：x：=k*i y:=j*i z:=x*y write j i:=i+1 if i100 goto l halt i：=j：=read k x：=0 y：=0 l：x：=x+k y：=y+10 z：=x*y write j i：=i+1 if ijh100 goto l 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答：B3:图 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 所示的情形。B1:B2 B2:halt i：=j：=read k x：=0 y：=0 l：x：=x+k y：=y+10 z：=x*y write j tl:=100*k if ijhtl goto l 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 B3:图 7.8 归纳变量后的程序流图 B1:B2:B2: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：=j：=read k x：=0 y：=0 write j tl:=100*k l：x：=x+k y：=y+10 z：=x*y if ijhtl goto l halt 化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答 I:=1 L1:B:=J+1 C:=B+I A:=C+A IF I=100 GOTO L2 I:=I+1 GOTO L1 L2:解答：程序的流程图如图所表示 有流程图可见，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*b END 试写出循环外提后的结果。解答：该语句的四元式为：（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）（+，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,T1）化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答（3）（:=,T1，a）（4）（*，m,m,T2）（5）（:=,T2，b）（6）（*，b,b,T3）（7）（:=，0，c）（8）)(-,n,i,T0)（9）(BMZ,T0,，（14）)（10）（+，c，T3，T4）（11）（：=，T4，c）（12）（+，1，i,T5）（13）(:=,T5,i)(14)(BR,(8)（15）（9）（+，c，T3，T4）（10）（：=，T4，c）（11）（+，1，i,T5）(15)(:=,T5,i)(16)(BR,(2)15.如何理解有的程序优化后质量反而下降？解答：进行了代码优化后生成的目标代码，对于极个别的源程序来说，可能质量可能非但没有改进，发而有所下降。这是因为，源程序形形色色，内涵丰富，某种语言结构组合可能进行优化反而降低质量的反例。这并不矛盾，只要对于大多数源程序有较明显的质量改进就可以认为所做的优化成功。化无用的指令消除等四类冗余指令删除假设源程序指令序列编译程序为其生成的代码很可能是下列指令序列假如第四条指令没有标号上述两个赋值语句在一个基本块内则第四条指令是多余的可删除特殊指令的使用例如如果目标机器了得到最好的改进一般可能需要对目标代码重复扫描进行优化设有语句序列试写出合并常量后的三式序列解答该语句序列对应的三式序列为合并常量后的三式序列为试写出算术表达式优化后的四式序列解答该表达式的四式序列为可答该算术表达式的三元序列为可对其进行删除公共子表达式的优化优化后的三元式列为试对以下基本块和应用进行优化并就以下两种情况分别写出优化后的四元式序列假设在基本块后面要被引用假设只有在基本块后面要被引用解答