《编译原理分知识点习题代码优化》由会员分享，可在线阅读，更多相关《编译原理分知识点习题代码优化（14页珍藏版）》请在金锄头文库上搜索。
1、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,
2、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
3、, 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
4、) （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) 可对其进行删除公共子表达式的优化。优化后的三元
5、式列为： （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*CD:=B/CE:=A+DF:=E*2G:=B*CH:=G*GF:=H*GL:=F9857F16342M:=L B2: B:=3D:=A+CE:=A*CF:=D+EG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L并就以下两种情况分别
6、写出优化后的四元式序列： （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*CH:=G*G S:=G*GL:=H*G L:=S*GM:=L M:=L (S 为临时变量) (2)若只有 L 在基本块后
7、面要被引用 G:=B*C 或 S1:=B*CH:=G*G S2:=S1*S1L:=H*G L:=S2*S1 (S1、S2为临时变量)381726954对于基本块 B2,其 DAG 如图 7.2 所示。G L,M * F,J +D,H E,L+ *B K3 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+
8、S2 L:=F+15 L:=S3+15 (S1、S2、S3为临时变量) 6. 对于基本块 PS0:=2S1:=3/S0S2:=T-CS3:=T+CR:=S0/S3H:=R S4:=3/S1S5:=T+C S6:=S4/S5 H:=S6*S21H0473652(1)试应用 DAG 进行优化。 (2)假定只有 R、H 在基本块出口是活跃的,试写出优化后的四元式序列。 (3)假定只有两个寄存器 R0、R1试写出上述优化后的四元式序列的目标代码。解答: (1) 构造 DAG 如图 7.3 所示。HR, ,S6S2 / -S3,S5+S0,S4 S1 2 1.5 T C图 7.3 基本块 P 的 DAG
9、 图 优化后的四元式序列为: S0:=2S4:=2S1:=1.5S2:=T-CS3:=T+C S5:=S3 R:=2/S3 S6:=R H:=S6*S2(2) 若只有 R、H 在基本块出口是活跃的,优化后的四元式序列为: S2:=T-CS3:=T+C R:=2/S3 H:=R*S2 (3) 假定只有两个寄存器 R0、R1,上述优化后的四元式序列的目标代码为:LD R0 TSUB R0 CST R0 S2LD R0 TB8B2B3B4B7B6B5B1ADD R0 CLD R1 2DIV R1 R0LD R0 S2MUL R1 R0ST R1 H 7. 设有入图 7.4 所示的程序流程图:图 7.
10、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,B2D (B3) =B1,B2,B3 D (B4) =B1,B2,B3,B4 D (B5) =B1,B2,B3,B5 D
11、 (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 是该循环的唯一入口结 点。题目所给出流图中,只有一条回
12、边 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
13、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,n5J :=0;L1: I:=0 ;if I8 goto L3;L2: A:=B +C;B:=D *C;L3: if B=0 goto L4;W rite B;goto L5;L4: I:=I +1;if I8 goto L2;L5: J:=J +1; i f J=3 goto L1;H ALTD (n6) =n0,n1,n3,n6 D (n7) =n0,n1,n3,n6,n7n0n1n2n3n4n5n6n7
