编译原理课后第十一章答案.pdf

编译原理课后习题答案第十一章 第 11 章 代码优化 第题 何谓代码优化？进行优化所需要的基础是什么？ 答案： 对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行 速度加快或占用存储空间减少，或两者都有。 优化所需要的基础是在中间代码生成之后或目标代码生成之后。 第题 编译过程中可进行的优化如何分类？ 答案： 依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。 第题 最常用的代码优化技术有哪些？ 答案： 1. 删除多余运算 2. 代码外提 3. 强度削弱 4. 变换循环控制条件 5. 合并已知量与复写传播 6. 删除无用赋值 计算机咨询网（ ）陪着您 1 编译原理课后习题答案第十一章 第 4 题 图 11.23 是图 11.22 的 C 代码的部分三地址代码序列。 void quicksort(m,n) int m,n; int i,j; int v,x; if (n=j) break; x = ai; ai = aj; aj = x; x = ai; ai = an; an = x; /* fragment ends 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) 计算机咨询网（ ）陪着您 2 编译原理课后习题答案第十一章 (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 (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) 找出每个循环中的归纳变量，并在可能的地方删除它们。 答案： （1 ） 基本块 计算机咨询网（ ）陪着您 3 编译原理课后习题答案第十一章 流图 （2 ） B5 中（14）和（16）是公共子表达式、（17）和（20）是公共子表达式，B5 变为 （ 14） t 6 :=4*I （ 15） （ 16） t 7 :=t 6 （ 17） t 8 :=4*J （ 20） t 10 :=t 8 （ 21） （ 22） B6 中（23）和（25）是公共子表达式、（26）和（29）是公共子表达式，B6 变为 （ 23） t 11 :=4*I （ 24） （ 25） t 12 :=t 11 （ 26） t 13 :=4*n 计算机咨询网（ ）陪着您 4 编译原理课后习题答案第十一章 （ 29） t 15 :=t 13 （3 ） 循环 B2 B3 B2，B3 ，B4 ，B5 (4) 在循环B2 ，B3 ，B4 ，B5 中，原来的(14)(17) 都可以删除。 计算机咨询网（ ）陪着您 5 编译原理课后习题答案第十一章 第 5 题： 如下程序流图( 图 11.24)中，B3 中的 i=2是循环不变量，可以将其提到前置结点吗 ? 你还能举出一些例子说明循环不变量外移的条件吗? 图 11.24 答案： 不能。因为 B3 不是循环出口 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 中定值的，则只有 当这些定值四元式都已外提到前置结点中时，才可把 s 也外提到前置结点。 计算机咨询网（ ）陪着您 6 编译原理课后习题答案第十一章 第 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 对它们进行优化，并就以下两种情况分别写出优化后的四元式序列： （1 ）假设只有 G、L、M 在基本块后面还要被引用。 （2 ）假设只有 L 在基本块后面还要被引用。 答案: B1： 基本块对应的 DAG 如下： 计算机咨询网（ ）陪着您 7 编译原理课后习题答案第十一章 根据 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 M：=S3 （2 ）假设只有 L 在基本块后面还要被引用； S1：=B*C S2：=S1*S1 S3：=S1*S2 L：=S3 （备注：S1 ，S2 ，S3 为新引入的临时变量） 或者： 计算机咨询网（ ）陪着您 8 编译原理课后习题答案第十一章 B2: 基本块对应的 DAG 如下： 优化后的四元式序列： 对假设（） B:=3 计算机咨询网（ ）陪着您 9 编译原理课后习题答案第十一章 D:=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 计算机咨询网（ ）陪着您 10 编译原理课后习题答案第十一章 第 7 题 分别对图 11.25 和 11.26 的流图： (1) 求出流图中各结点 n 的必经结点集 D(n)。 (2) 求出流图中的回边。 (3) 求出流图中的循环。 图 11.25 图 11.26 计算机咨询网（ ）陪着您 11 编译原理课后习题答案第十一章 答案： 对图 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,5 D(6)=1,2,3,6 D(7)=1,2,7 D(8)=1,2,7,8 （2 ）回边： 7 2 （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 计算机咨询网（ ）陪着您 12 编译原理课后习题答案第十一章 附加题 问题 1： 给出如下 4 元式序列： (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 中的回边与循环。 答案： 四元式程序基本块入口语句的条件是： (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， 故可画出程序流图如下图所示 - 1 - 编译原理课后习题答案第十一章 D(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，则 ab 为流图中一条回边。 故当已知必经结点集时，可立即求出所有回边。 易知本题回边只有 72 。( 按递增顺序考察所有回边。） 称满足如下两个条件的结点序列为一个循环。 (1)它们强连通，即任意两个结点，必有一通路，且该通路上各结点都属于该结点序列，如 序列只包含一个结点，则必有一有向边从该结点引到自身。 (2)它们中间有一个而且只有一个是入口结点。所谓入口结点，是指序列中具有下列性质的 结点，从序列外某结点有一有向边引到它，或它就是程序流图的首结点。 求出回边 72 ，可知循环为 234567，即为所求。 问题 2： 基本块的 DAG 如下图所示，若(1)B 在该基本块出口处不活跃,(2)B 在该基本块出口处 活跃的，请分别给出以下代码经过优化后的代码。 A:B+C B:A-D C:B+C D:A-D - 2 - 编译原理课后习题答案第十一章 答案： 当 B 在出口不活跃时，则 B 在外面就无用了，故 B：=A-D 这条赋值语句可删去，另外， 由于代码生成方面的关系，可把 D 的赋值语句提前到 C 的赋值语句以前。 故得到： A:=B+C D:=A-D C:=D+C 当 B 在出口活跃时，则 B 在出口处要引用， B 的赋值语句就不可删去了，然而 D 与 B 充 全一样，故 D 的赋值语句可简化，得： A:B+C B:A-D D:=B C:=B+C - 3 -