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

1、文档编码 : CV5Z10X4X10A4 HM3L6K6V4Y7 ZK7J8F10U9D2学习必备 欢迎下载 1与机器有关的代码优化有那些种类,请分别举例说明； 解答：与机器有关的优化有：寄存器优化,多处理优化,特别的指令优化,无用 的指令排除等四类； 冗余指令删除 假设源程序指令序列 a:=b+c; c:=a-d; 编译程序为其生成的代码很可能是以下指令序列： MOV b, R0 就第四条指令是 ADD MOV SUB MOV c, R0 R0,a d, R0 R0,c 假如第四条指令没有标号, 上述两个赋值语句在一个基本块内, 余外的,可删除； 特别指令的使用 例如,假如目标机器指令系统包

2、含增 MOV i, R0 ADD #1, R0MOV R0, i 便可被代之以 1 条指令 Inc i1 指令 INC,对于 i:=i+1 的目标代码 说明：优化的特点是每个改进可能会引发新的改进机会,为了得到最好的改进, 一般可能需要对目标代码重复扫描进行优化； 2设有语句序列 a:=20 b:=a*a+10; c:=a*b; 试写出合并常量后的三元式序列； 解答：该语句序列对应的三元式序列为： （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （:=, 20,a） +, a, 10 *, a, 2 :=, a, b * a, b :=, 5, c 合并常量后的三元式序列为： （

3、1） （ 2） （ 3） （:=, 20,a） :=, 600, b :=, 12022, c 3,试写出算术表达式 a+b*c-c*b+a-e/b*c+d 优化后的四元式序列； 解答：该表达式的四元式序列为： （ 1） （*, b,c,T1 ） （ 2） +,a,T1 ,T2 第 1 页,共 14 页（ 3） *,c,b,T 3 +,T3,a,T4 学习必备 欢迎下载 （ 4） （ 5） -,T4,e,T5 *,b,c,T 6 （ 6） （ 7） +,T6,d,T7 （ 8） /,T5,T7,T8 -,T2,T8 ,T9 （ 9） 可对该表达式进行删除公共子表达式的优化；优化后的四元式序列为

4、： （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （* ,b,c,T1） +,a,T1,T2 -,T2,e,T5 +,T1,d,T7 /,T5,T7,T8 -,T2,T8,T9 4.设有算术表示式 （a*b+c）/a*b-c+c*b+a-d/a*b+c试给出其优化后的三元式序列； 解答：该算术表达式的三元序列为： （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） （ 9） （*,a,b） +,1,c *,a,b -,3,c /,2,4 *,c,b +,6,a -,7,d （*,a,b） （ 10）+,9,c （ 11）/,8,10 （ 12）+,5,

5、11 可对其进行删除公共子表达式的优化；优化后的三元式列为： （ 1）（*,a,b） 2 3 +,1,c -,1,c B1 和 B2 应用 DAG 进行优化 4 5 6 7 /,2,3 *, c, b +,5,a -,6,d 8 9 /,7,2 +,4,8 5.试对以下基本块 B1: A:=B*C D:=B/C E:=A+D F:=E*2 G:=B*C H:=G*G 第 2 页,共 14 页B2: F:=H*G 学习必备 欢迎下载 L:=F M:=L 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

6、 并就以下两种情形分别写出优化后的四元式序列： （ 1） 假设 G,L,M 在基本块后面要被引 ; 用 （ 2） 假设只有 L 在基本块后面要被引用； 解答 : 一般应用 DAG 在一个基本块内可以进行三种优化 : 合并常量,删除无用 赋值以及余外运算； 对于基本块 B1, 其 DAG如所示； 7F 图 9F , L , M 5*4E *+ H8*A , G 3D*/ 26B C图 基本块 B1 的 2DAG 图 优化后的四元式序列如下 : 11 如只有 G,L,M 在基本块后面要被引 用 G:=B*C 或 G:=B*C 为暂时变量 H:=G*G S:=G*G L:=H*G L:=S*G M:

7、=L M:=L S 2 如只有 L 在基本块后面要被引用 G:=B*C 或 S 1:=B*C 第 3 页,共 14 页H:=G*G B2, 其 S 学习必备 欢迎下载 1, S2 为暂时变量 2:=S1*S1 L:=H*G L:=S 2*S1S 对于基本块 DAG如所示； 图 7G + *4F,J L,M 59*6 + E,L D,H 1B + 2K 383 A C 15 图 基本块 B2 的 DAG优化后的四元式序列如下 : 图 1 如只有 G,L,M 在基本块后面要被引用 D:=A+CE:=A*CF:=D+EG:=3*F L:=F+15 2 M:=L S 1:=A+C 如只有 L 在基本块

8、后面要被引用 D:=A+C E:=A*CS 2:=A*C F:=D+E S 3:=S1+S2 L:=F+15 L:=S 3+15 S1,S2, S3 为暂时变量 6. 对于基本块 P S 0:=2 S 1:=3/S 0S2:=T-C S 3:=T+C R:=S 0/S 3 H:=R S4:=3/S 1 S 5:=T+C 第 4 页,共 14 页学习必备 欢迎下载 S6:=S4/S 5 H:=S6*S2 1 试应用 DAG 进行优化； 2 假定只有 R, H 在基本块出口是活跃 , 试写出优化后的四元式序列； 3 假定只有两个寄存器 R0, R1 试写出上述优化后的四元式序列的目标代码； 解答

9、: 1 构造 DAG如图 所示； H 7R, 6 ,S H 6 4 S 2/ S -53,S 5 + 2S 00,S 4 S 1 T 1C23优化后的四元式序列为 图 基本块 P 的 DAG: 图 S0:=2 S 4:=2 S1 S 2:=T-C S 3:=T+C S5:=S3 R:=2/S 3 S6:=R H:=S6* S2 2 如只有 R,H 在基本块出口是活跃的 S2:=T-C S 3:=T+C R:=2/S 3 H:=R*S2 , 优化后的四元式序列为 : 3 假定只有两个寄存器 R0,R1,上述优化后的四元式序列的目标代码为 : LD R 0 T SUB R 0 CST R 0 S2

10、 第 5 页,共 14 页LD R0T 学习必备 欢迎下载 ADDR0CLDR12DIV R1R0LDR 0S 2MUL R1R 0ST R1H7. 设有入图 所示的程序流程图 : B1 B2 B3 B4 B5 B6 B7 B8 图 程序流图 1 2 3 求出流图中各个结点 n 的必经结点集 Dn; 求出该流图中的回边 ; 求出该流图中的循环； 解答 : 1 在程序流图中 , 对任意的结点 ni 和 nj , 假如从流图的首结点动身 , 到达 nj 的任 一通路都必需经过 ni, 就称 ni是 nj的必经结点 , 记为 niDOM nj；流图中结点 n的全部必经结点称为结点 n 的必经结点集

11、, 记为 D n ； 流图中各结点 n 的必经结点集 D n 为: D B 1 =B 1 第 6 页,共 14 页D B 2 =B 1,B 2 学习必备 欢迎下载 D B 3 =B 1,B 2,B 3 D B 4 =B D B 5 =B D B 6 =B D B 7 =B D B 8 =B 1,B 2,B 3,B 4 1,B 2,B 3,B 5 1,B 2,B 3,B 6 1,B 2,B 7 1,B 2,B 7,B 8 2 流图的回边是指 : 如 ab 是流图中一条有向边 , 且有 b DOM a,就称 ab 是 流图的一条回边； 题目所给流图中 , 有有向边 B7 B2, 又有 D B7=B

12、 1,B 2,B 7, 所以 , B2DOMB7, 3 即 B7B2 是流图的回边；且无其他回边； 该流图中的循环可利用回边求得； 假如以知有向边 nd 是一回边 , 由它组成的循环就是由结点 d,结点 n 以及 有通路到达 n 而该通路不经过 d 的全部结点组成 , 且 d 是该循环的唯独入口结点； 题目所给出流图中 , 只有一条回边 B7B2, 在该流图中 , 凡是不能经过结点 B2 有通 路到达结点 B7 的结点 , 只有 B3,B 4 ,B 5,B6, 所以 , 由回边 B7 B2 组成的循环是 B 2,B 3,B 4,B 5,B 6,B 7 ； 8. 中国科学院运算机所 1997 年

13、 试画出如下中间代码序列的程序流图 , 并求 出: 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 解答 : 程序的流图入图 所示； 1 各结点的必经结点集分别为 : D n 0 =n 0 D n 1 =n 0,n 1 D n 2 =n 0,n 1,n 2 D n 3 =n 0,n 1,

14、n 3 D n 4 =n 0,n 1,n 3,n 4 D n 5 =n 0,n 1,n 3,n 5 第 7 页,共 14 页D n 6 =n 0,n 1,n 3,n 6 学习必备 欢迎下载 D n 7 =n 0,n 1,n 3,n 6,n 7 nn0 1J:=0; L1: I:=0; if I8 goto L3; n2 L2: A:=B+C; B:=D*C; n3 L3: if B=0 goto L4; n4 n5 Write B; goto L5; L4: I:=I+1; if I8 goto L2; n6 n7 L5: J:=J+1; if J=3 goto L1; HALT 图 程序流图

15、 （ 2） 流图中的回边有一条：即 n6 n1 该回边表示的循环为： （n1,n 2 ,n 3,n 4,n 5,n 6）, 入口为 n1, 出口为 n6 9. 武汉高校 1991 年 试对下面的程序段进行尽可能的优化： i ： = j ：= read k l ： x ：=k* i y: =j* i z: =x*y write j i:=i+1 第 8 页,共 14 页学习必备 欢迎下载 if i100 goto l halt 并指明你进行了何种优化,给出优化过程的简要说明及每种优化后的结果形式； 解答：程序的流程图如下所示： i ： = 1： 2: j ： = read k l ： x ： =

16、k* i y: =j* iz: =x*y write ji:=i+1 if i100 goto l halt 3: 图 程序流图 由程序流图可知,为一个循环； 对于此题中的循环可进行以下优化： 削减强度 循环中有 x:=x*i y:=y*i j,k 在循环中不转变值； i 每次增加 ,x 和 y 的赋值运算可进行强度削减,于 是程序流图变为图 所示； i ： = B1: j ： = read k B2 : x： =0 y： =0 l 1： x： =x+k y： =y+10 z： =x*y write j i： =i+1 if ijh100 goto l 1 第 9 页,共 14 页学习必备 欢

17、迎下载 ： B3: halt 图 削减强度后的程序流图 删除归纳变量 由于 i 是循环中的基本归纳变量, x,y 是与 y 同族的归纳变量,且有线性关 系 x：=k*i y ：=j*i 所以, i100 完全可用 所示； 代码外提 将循环中不变运算 write j tl:=100*k x100*k 或 y100*j 代替；于是,进一步优化为图 提到循环外的前置节点 B21 中,于是程序流图变为 所示的情形； i ： = j ： = B 1: read k x： =0 B 12 y： =0 l 1： x： =x+k B2 : y： =y+10 z： =x*y write jtl:=100*k i

18、f ijhtl goto l 1 第 10 页,共 14 页B 3: 学习必备 欢迎下载 图 B1: 归纳变量后的程序流图 i ： = j ： = read k B 21: x： =0 y： =0write jtl:=100*k l 1： x： =x+k B 2: y： =y+10 z： =x*y if ijhtl goto l 1 B 3 : halt 图 代码外提后的程序流图 10. 在循环优化中,为什么要代码外提？试说明在哪些情形下代码可外提？ 解答：代码外提可以削减循环中的指令数目,从而节约目标代码运行的时间； 对于循环中 L 的每一个不变运算 s： A： =B op C 或 A ：=

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

20、1 页,共 14 页学习必备 欢迎下载 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 代替； 于是流程图变为图所表示 第 12 页,共 14 页学习必备 欢迎下载 图 优化后的程序流图 14设有循环语句 n DO FOR i:=1 TO BEGINa a:=u*v b:=m*m c:=c+b*b END 试写出循环外提后的结果； 解答：该语句的四元式为： （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, ,