编译原理 第11章 代码优化

《编译原理 第11章 代码优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《编译原理》课后习题答案第十一章第11章代码优化第１题何谓代码优化？进行优化所需要的基础是什么？答案：对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加快或占用存储空间减少，或两者都有。优化所需要的基础是在中间代码生成之后或目标代码生成之后。第２题编译过程中可进行的优化如何分类？答案：依据优化所涉及的程序范围，可以分为：局部优化、循环优化和全局优化。第３题最常用的代码优化技术有哪些？答案：1.删除多余运算2.代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值盛威网（www.sn

2、wei.com）专业的计算机学习网站1《编译原理》课后习题答案第十一章第4题图11.23是图11.22的C代码的部分三地址代码序列。voidquicksort(m,n)intm,n;{inti,j;intv,x;if(n<=m)return;/*fragmentbeginshere*/i=m-1;j=n;v=a[n];while(1){doi=i+1;while(a[i]v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n

3、]=x;/*fragmentendshere*/quicksort(m,j);quicksort(i+1,n);}图11.22(1)i:=m-1(2)j:=n(3)t1:=4*n(4)v:=a[t1](5)i:=i+1(6)t2:=4*i(7)t3:=a[t2](8)ift3vgoto(9)(13)ifi>=jgoto(23)盛威网（www.snwei.com）专业的计算机学习网站2《编译原理》课后习题答案第十一章(14)t6:=4*i(

4、15)x:=a[t6](16)t7:=4*i(17)t6:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x图11.23(1)请将图11.23的三地址代码序列划分为基本块并做出其流图。(2)将每个基本块的公共子表达式删除。(3)找出流图中的循环,将循环不

5、变量计算移出循环外。(4)找出每个循环中的归纳变量，并在可能的地方删除它们。答案：（1）基本块盛威网（www.snwei.com）专业的计算机学习网站3《编译原理》课后习题答案第十一章流图（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盛威网（www.snwei.com）专业的计算机学习网站4《编译原理》课后习题答案第十一章…（29）t15:=t13（3）循环①{B2}②{B3}③{B2，B3，B4，B5}(4)在循环{B2，B3，B4，B5}中，原来的(14)(17)都可以删除。盛威网（www.snwei.com）专业的计算机学习网站5《编译原理》课后习题答案第十一章第5题：如下程序流图(图11.24)中，B3中的i=∶2是循环不变量，可以将其提到前置结点吗?你还能举出一些例子说明循环不变量外移的条件吗?图11.24答案：不能。因为B3不是循环出口B4的必经结点

7、。循环不变量外移的条件外有：（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也外提到前置结点。盛威网（www.snwei.com）专业的计算机学习网站6《编译原理》课后习题答案第十一章第6题试对以下基本块B1和B2：B1：A：=B*CD：=B/CE：=A+DF：