《编译原理 第11章 代码优化》由会员分享，可在线阅读，更多相关《编译原理 第11章 代码优化（15页珍藏版）》请在金锄头文库上搜索。
1、编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 1第第 11 章章 代码优化代码优化 第题第题 何谓代码优化？进行优化所需要的基础是什么？何谓代码优化？进行优化所需要的基础是什么？ 答案： 对代码进行等价变换， 使得变换后的代码运行结果与变换前代码运行结果相同， 而运行 速度加快或占用存储空间减少，或两者都有。 优化所需要的基础是在中间代码生成之后或目标代码生成之后。 第题第题 编译过程中可进行的优化如何分类？编译过程中可进行的优化如何分类？ 答案： 依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。 第题第题 最常用的代码优化技术有哪些？最常用的代码优化技术有哪
2、些？ 答案： 1. 删除多余运算 2. 代码外提 3. 强度削弱 4. 变换循环控制条件 5. 合并已知量与复写传播 6. 删除无用赋值 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 2第第 4 题题 图 图 11.23 是图是图 11.22 的的 C 代码的部分三地址代码序列。代码的部分三地址代码序列。 void quicksort(m,n) int m,n; int i,j; int v,x; if (nv); if (i=j) break; x = ai; ai = aj; aj = x; x = ai; ai = an; an = x; /* fragment ends
3、 here */ quicksort (m,j); quicksort(i+1,n); 图图 11.22 (1) i:=m-1 (2) j:=n (3) t1:=4*n (4) v:=at1 (5) i:=i+1 (6) t2:=4*i (7) t3:=at2 (8) if t3 v goto (9) (13) if i = j goto (23) 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 3(14) t6:=4*i (15) x:=at6 (16) t7:=4*i (17) t6:=4*j (18) t9:=at8 (19) at7:=t9 (20) t10:=4*j (
4、21) at10:=x (22) goto (5) (23) t11:=4*i (24) x:=at11 (25) t12:=4*i (26) t13:=4*n (27) t14:=at13 (28) at12:=t14 (29) t15:=4*n (30) at15:=x 图图 11.23 (1) 请将图请将图 11.23 的三地址代码序列划分为基本块并做出其流图。的三地址代码序列划分为基本块并做出其流图。 (2) 将每个基本块的公共子表达式删除。将每个基本块的公共子表达式删除。 (3) 找出流图中的循环找出流图中的循环,将循环不变量计算移出循环外。将循环不变量计算移出循环外。 (4) 找出
5、每个循环中的归纳变量，并在可能的地方删除它们。找出每个循环中的归纳变量，并在可能的地方删除它们。 答案：答案： （1） 基本块 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 4流图 （2） B5 中（14）和（16）是公共子表达式、 （17）和（20）是公共子表达式，B5 变为 （14） t6:=4*I （15） （16） t7:=t6 （17） t8:=4*J （20） t10:=t8 （21） （22） B6 中（23）和（25）是公共子表达式、 （26）和（29）是公共子表达式，B6 变为 （23） t11:=4*I （24） （25） t12:=t11 （26） t13
6、:=4*n 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 5 （29） t15:=t13 （3） 循环 B2 B3 B2，B3，B4，B5 (4) 在循环B2，B3，B4，B5中，原来的(14)(17)都可以删除。编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 6第第 5 题：题： 如下程序流图如下程序流图(图图 11.24)中，中，B3 中的中的 i=2是循环不变量，可以将其提到前置结点吗是循环不变量，可以将其提到前置结点吗? 你还能举出一些例子说明循环不变量外移的条件吗你还能举出一些例子说明循环不变量外移的条件吗? 图 11.24 答案：答案： 不能。因为 B
7、3 不是循环出口 B4 的必经结点。 循环不变量外移的条件外有： （a）(I)s 所在的结点是 L 的所有出口结点的必经结点 (II)A 在 L 中其他地方未再定值 (III)L 中所有 A 的引用点只有 s 中 A 的定值才能到达 （b）A 在离开 L 之后不再是活跃的，并且条件(a)的(II)和(III)成立。所谓 A 在离开 L 后不再是活跃的是指，A 在 L 的任何出口结点的后继结点的入口处不是活跃的（从此点后 不被引用） （3）按步骤（1）所找出的不变运算的顺序，依次把符合（2）的条件(a)或(b)的 不变运算 s 外提到 L 的前置结点中。如果 s 的运算对象（B 或 C）是在 L
8、 中定值的，则只有 当这些定值四元式都已外提到前置结点中时，才可把 s 也外提到前置结点。编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 7第第 6 题题 试对以下基本块试对以下基本块 B1 和和 B2： B1： A：=B*C D：=B/C E：=A+D F：=2*E G：=B*C H：=G*G 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 分别应用分别应用 DAG 对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：对它们进行优化
9、，并就以下两种情况分别写出优化后的四元式序列： （1）假设只有）假设只有 G、L、M 在基本块后面还要被引用。在基本块后面还要被引用。 （2）假设只有）假设只有 L 在基本块后面还要被引用。在基本块后面还要被引用。 答案答案: B1： 基本块对应的 DAG 如下： 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 8根据 DAG 图,优化后的语句序列为 A：=B*C G：=A D：=B/C E：=A+D H：=A*A F：=A*H L：=F M：=F （1）假设只有 G、L、M 在基本块后面还要被引用； S1：=B*C G：=S1 S2：=S1*S1 S3：=S1*S2 L：=S3
10、 M：=S3 （2）假设只有 L 在基本块后面还要被引用； S1：=B*C S2：=S1*S1 S3：=S1*S2 L：=S3 （备注：S1，S2，S3 为新引入的临时变量） 或者：或者： 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 9B2: 基本块对应的 DAG 如下： 优化后的四元式序列： 对假设（） B:=3 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 10D:=A+C E:=A*C F:=D+E G:=B*F K:=B*5 L:=K+F M:=L 对假设（2） B:=3 D:=A+C E:=A*C F:=D+E K:=B*5 L:=K+F编译原理课后
11、习题答案第十一章 盛威网（）专业的计算机学习网站 11第第 7 题题 分别对图分别对图 11.25 和和 11.26 的流图：的流图： (1) 求出流图中各结点求出流图中各结点 n 的必经结点集的必经结点集 D(n)。 (2) 求出流图中的回边。求出流图中的回边。 (3) 求出流图中的循环。求出流图中的循环。 图 11.25 图 11.26 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 12答案：答案： 对图对图 11.25： （1）流图中各结点 N 的必经结点集 D(n)： D(1)=1 D(2)=1,2 D(3)=1,2,3 D(4)=1,2,3,4 D(5)=1,2,3,
12、5 D(6)=1,2,3,6 D(7)=1,2,7 D(8)=1,2,7,8 （2）回边： 72 （3）循环： 2，3，4，5，6，7 对图对图 11.26： (1)流图中各结点 N 的必经结点集 D(n)： D(l)1 D(2)1,2 D(3)1,2,3 D(4)=1,2,3,4 D(5)1,2,5 D(6)1,2,5,6 (2)求出流图中的回边： 52，43 (3)求出流图中的循环： 回边 52 对应的循环： 2，5，3，4 回边 43 对应的循环： 3，4 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 13附加题附加题 问题问题 1： 给出如下给出如下 4 元式序列：元式
13、序列： (1) J:=0; (2)L1:I:=0; (3) IF I8,goto L3; (4)L2:A:=B+C; (5) B:=D*C; (6)L3:IF B=0,goto L4; (7) Write B; (8) goto L5; (9)L4:I:=I+1; (10) IF I8,goto L2; (11)L5:J:=J+1; (12) IF J=3,goto L1; (13) STOP 画出上述画出上述 4 元式序列的程序流程图元式序列的程序流程图 G, 求出求出 G 中各结点中各结点 N 的必经结点集的必经结点集 D(n), 求出求出 G 中的回边与循环。中的回边与循环。 答案：答案
14、： 四元式程序基本块入口语句的条件是： (1)它们是程序的第一个语句；或， (2)能由条件转移语句或无条件转移语句转移到的语句；或， (3)紧跟在条件转移语句后的语句。 (4)根据这 3 个条件，可以判断，设 1，2，3，4，6，7，9，11，13 为入口语句，故基本块 为 l，2/3，4/5，6，7/8，9/1O，11/12，13， 故可画出程序流图如下图所示： 编译原理课后习题答案第十一章 盛威网（）专业的计算机学习网站 14D(l)1，D(2)1，2，D(3)1，2，3，D(4)=1，2，4，D(5)1，2，4，5， D(6)1，2，4，6，D(7)1，2，4，7，D(8)1，2，4，7，8，即为所求必经结点集。 回边的定义为： 假设 ab 为流图中一条有向边， 若 b DOM a，
