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

1、学习必备欢迎下载1与机器有关的代码优化有那些种类，请分别举例说明。解答：与机器有关的优化有：寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。冗余指令删除假设源程序指令序列a:=b+c;c:=a-d;编译程序为其生成的代码很可能是下列指令序列：MOVb, R0ADDMOVc, R0R0,aSUBd, R0MOVR0,c假如第四条指令没有标号， 上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。特殊指令的使用例如，如果目标机器指令系统包含增1 指令INC ，对于i:=i+1的目标代码MOVi, R0ADDMOV#1, R0R0, 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

3、+d)优化后的四元式序列。解答：该表达式的四元式序列为：（ 1） （ * ， b,c,T1 ）（ 2） (+,a,T1 ,T2)学习必备欢迎下载（ 3） (*,c,b,T 3)（ 4） (+,T3,a,T4)（ 5） (-,T4,e,T5)（ 6） (*,b,c,T 6)（ 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）(

4、-,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)

5、,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*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*G学习必备欢迎下载F:=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在基本块后面要被引用 ;（

6、2） 假设只有 L 在基本块后面要被引用。解答 : 一般应用 DAG在一个基本块内可以进行三种优化 : 合并常量、删除无用赋值以及多余运算。对于基本块 B1, 其 DAG如图 7.1 所示。7F9F,L,M*E5*+H8*A,G3D4*/BC21图 7.1基本块 B1 的 DAG图6:2优化后的四元式序列如下(1) 若只有 G、L、M在基本块后面要被引用G:=B*CH:=G*GL:=H*G或G:=B*CS:=G*GL:=S*GM:=LM:=L(S为临时变量)(2) 若只有 L 在基本块后面要被引用G:=B*C或S1:=B*C学习必备欢迎下载H:=G*GS2:=S1*S1L:=H*GL:=S2*

7、S1(S1、 S2 为临时变量 )对于基本块 B2, 其 DAG如图 7.2 所示。G6 +L,M7 *F,J9+D,HE,L54+*1BK8233AC15图 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*CS2:=A*CF:=D+ES3:=S1+S2L:=F+15L:=S3+15(S1、S2、 S3 为临时变量 )6. 对于基本块 PS 0:=2S 1:=3/S 0S2:=T-CS 3:=T

8、+CR:=S 0/S 3H:=RS4:=3/S 1S 5:=T+C学习必备欢迎下载S6:=S4/S 5H:=S6*S2(1) 试应用 DAG进行优化。(2) 假定只有 R、 H 在基本块出口是活跃的 , 试写出优化后的四元式序列。(3) 假定只有两个寄存器 R0、 R1 试写出上述优化后的四元式序列的目标代码。解答 : (1)构造 DAG如图 7.3所示。H7R,6 ,SH64S2/-S53,S 5+S 00,S 4S 112321.5TC图 7.3基本块 P 的 DAG图优化后的四元式序列为 :S0:=2S 4:=2S1:=1.5S 2:=T-CS 3:=T+CS5:=S3R:=2/S 3S

9、6:=RH:=S6* S2(2) 若只有 R、H 在基本块出口是活跃的 , 优化后的四元式序列为 :S2:=T-CS 3:=T+CR:=2/S 3H:=R*S2(3) 假定只有两个寄存器 R0、R1,上述优化后的四元式序列的目标代码为 :LDR0TSUBR0CSTR0S2学习必备欢迎下载LDRADDRLDRDIVRLDRMULRSTR0011011TC2RSRH0207. 设有入图 7.4 所示的程序流程图 :B1B2B3B4B5B6B7B8图 7.4 程序流图(1) 求出流图中各个结点 n 的必经结点集 D(n);(2) 求出该流图中的回边 ;(3) 求出该流图中的循环。解答 :(1) 在程

10、序流图中 , 对任意的结点 ni 和 nj , 如果从流图的首结点出发 , 到达 nj 的任一通路都必须经过 ni , 则称 ni 是 nj 的必经结点 , 记为 ni DOM nj。流图中结点 n 的所有必经结点称为结点 n 的必经结点集 , 记为 D (n) 。流图中各结点 n 的必经结点集 D (n) 为: D (B 1) =B 1学习必备欢迎下载D (B 2) =BD (B 3) =BD (B 4) =BD (B 5) =BD (B 6) =BD (B 7) =BD (B 8) =B1,B21,B 2,B 31,B 2,B 3,B 41,B 2,B 3,B 51,B 2,B 3,B 6

11、1,B 2,B 71,B 2,B 7,B 8(2) 流图的回边是指 : 若 ab 是流图中一条有向边 , 且有 b DOM a,则称 ab 是流图的一条回边。题目所给流图中 , 有有向边 B7 B2, 又有 D (B7)=B 1,B 2,B 7, 所以 , B2 DOMB7,即 B7B2 是流图的回边。且无其他回边。(3) 该流图中的循环可利用回边求得。如果以知有向边 nd 是一回边 , 由它组成的循环就是由结点 d、结点 n 以及有通路到达 n 而该通路不经过 d 的所有结点组成 , 且 d 是该循环的唯一入口结点。题目所给出流图中 , 只有一条回边 B7B2, 在该流图中 , 凡是不能经过

12、结点 B2 有通路到达结点 B7 的结点 , 只有 B3,B 4 ,B 5,B6, 所以 , 由回边 B7 B2 组成的循环是 B 2,B3,B 4,B 5,B6,B7 。8. ( 中国科学院计算机所 1997 年) 试画出如下中间代码序列的程序流图 , 并求出 :(1) 各结点的必经结点集合 D (n);(2) 流图中的回边与循环。J:=0;L1: I:=0;if I<8 goto L3;L2: A:=B+C;B:=D*C;L3: if B=0 goto L4;WriteB;gotoL5;L4: I:=I+1;if I<8 goto L2;L5: J:=J+1;if J<=

13、3 gotoL1;HALT解答 :程序的流图入图7.5 所示。(1) 各结点的必经结点集分别为 : D (n 0) =n 0D (n 1) =n 0,n 1D (n 2) =n 0,n 1,n 2 D (n 3) =n 0,n 1,n 3 D (n 4) =n 0,n 1,n 3,n 4 D (n 5) =n 0,n 1,n 3,n 5学习必备欢迎下载D (n 6) =n 0,n 1,n 3,n 6D (n 7) =n 0,n 1,n 3,n 6,n 7n0J:=0;nL1: I:=0;1if I<8 goto L3;n2L2: A:=B+C;B:=D*C;n3L3: if B=0 go

14、to L4;n4Write B;goto L5;n5L4: I:=I+1;if I<8 goto L2;L5: J:=J+1;n6if J<=3 goto L1;n7HALT图 7.5程序流图（ 2） 流图中的回边有一条：即 n6n1该回边表示的循环为：（n1,n 2 ,n 3,n 4,n 5,n 6） , 入口为 n1, 出口为 n69.( 武汉大学 1991 年) 试对下面的程序段进行尽可能的优化：i ： =j ：=readkl ： x ： =k* iy: =j* iz: =x*ywrite ji:=i+1学习必备欢迎下载if i<100 goto lhalt并指明你进行

15、了何种优化，给出优化过程的简要说明及每种优化后的结果形式。解答：程序的流程图如下所示：1： 2: 3:i ： =j ： =readkl ： x ： =k* i y: =j* iz: =x*y write ji:=i+1if i<100 goto lhalt图 7.6 程序流图由程序流图可知，为一个循环。对于本题中的循环可进行以下优化：·削减强度循环中有x:=x*iy:=y*ij,k 在循环中不改变值。 i 每次增加 ,x 和 y 的赋值运算可进行强度削减，于是程序流图变为图 7.7 所示。B1:i ： =j ： =read kB2 :x： =0y： =0l 1： x： =x+k

16、y： =y+10z： =x*ywriteji： =i+1if ijh<100 goto l 1学习必备欢迎下载：B3:halt图 7.7 削减强度后的程序流图·删除归纳变量由于 i 是循环中的基本归纳变量，x、y 是与 y 同族的归纳变量，且有线性关系x： =k*iy：=j*i所以， i<100 完全可用 x<100*k 或 y<100*j 代替。于是，进一步优化为图7.8所示。·代码外提将循环中不变运算write jtl:=100*k提到循环外的前置节点B21 中，于是程序流图变为7.9 所示的情形。i ： =j ： =B1:readkB12x：

17、=0y： =0l1： x： =x+ky： =y+10B2 :z： =x*ywritejtl:=100*kif ijh<tl goto l 1学习必备欢迎下载B3:图 7.8 归纳变量后的程序流图i ： =1j ： =B :read kB21:x： =0y： =0writejtl:=100*kl1： x： =x+kB:y： =y+102z： =x*yif ijh<tl goto l 1B3 :halt图 7.9 代码外提后的程序流图10. 在循环优化中，为什么要代码外提？试说明在哪些情况下代码可外提？解答：代码外提可以减少循环中的指令数目，从而节省目标代码运行的时间。对于循环中 L

18、的每一个不变运算s： A： =B op C 或 A ：=B检查它是否满足以下两个条件：（1） （a）s 所在的节点是 L 的所有的出口节点的必经节点；（b）在中其他地方未再定值；（c）中所有的引用点只有s 中的定植才能到达。(2)离开后不再是活跃的，并且条件（）中的（ a）和（ b）成立，所谓离开后不再是活跃的，是指在的任何出口节点的后继节点（当然是指那些不属于的后继）入口处不是活跃的。符合上述（）或（）的不变运算 s 可以外提到的前置节点中。 但是。S 的运算对象（或）是在中定植的，那么只有当这些定植代码都已外提到前置节点中时。才能把 s 也提到前置节点中。11. 以下循环是最内循环，是对其

19、进行循环优化。A:=0学习必备欢迎下载I:=1L1:B:=J+1C:=B+IA:=C+AIFI = 100GOTO 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设有循环语句FORi:=1TOnDOBEGINaa:=u*vb:=m*mc:=c+b*bEND试写出循环外提后的结果。解答：该语句的四元式为：（1）（:=，1, , i）（2）) (-, n, i, T 0 )（3）(BMZ, T 0, ，（14）)（4）（* ，u, v, T1 ）（5）（:=, T1， ， a）（6）（* ， m,m, T2）（7）（:=, T2， ，