[工学]编译原理第10章

《[工学]编译原理第10章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、14-七月-21第十章优化10.1概述10.2局部优化10.3循环优化10.4数据流分析(不介绍）14-七月-21什么是代码优化p272含义是指对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码代码优化器的地位和结构优化可在编译的各个阶段进行最主要的一类优化是在目标代码生成之前，对语义分析后的中间代码进行编译前端代码优化器代码产生控制流分析数据流分析代码变换14-七月-2110.1概述优化的目的和原则p272优化目的产生更高效的目标代码合理利用计算机资源优化原则等价不改变程序的运行结

2、果高效运行时间较短，占用存储空间较小合算以较低的代价取得较好的优化效果例如优化算法虽然使最后生成的目标代码的运行时间缩短，占用空间减少，但是若优化算法本身运行是浪费了过多的时间和空间，则从总体上说就不一定合算14-七月-21优化的分类按阶段分成与机器无关的优化，对中间代码进行依赖于机器的优化，生成目标代码时进行根据优化时所涉及的程序范围分成局部优化在基本块内部进行优化循环优化对循环中的代码进行优化全局优化大范围的优化，涉及整个程序优化工作的基础控制流分析(data-flowanalysis)数据流分析(

3、control-flowanalysis)变换(transformations)14-七月-21程序举例例如P:=0；forI:=1to20doP:=P+A[I]*B[I]；翻译成三地址代码是：(1)P:=0(2)I:=1元素A[I]的地址=base+(I-1)*w=I*w+A-w=4*I+A-4(3)T1:=4*IA的可变(4)T2:=A-4A的不变(5)T3:=T2[T1]T3存A[I](6)T4:=4*I(7)T5:=B-4(8)T6:=T5[T4]T6存B[I](9)T7:=T3*T6(10)P

4、:=P+T7增1(11)I:=I+1(12)ifI<=20goto(3)进入循环前循环体问题：可采取哪些优化技术？14-七月-21优化技术举例(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=A-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=B-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)代码外提p276每次循环结果不改变的代码(1)P:=0(2)I:=1(4)T2:=A-4(7)T5:=B

5、-4删除公共子表达式p273删除多余运算避免重复计算(3)T1:=4*I(5)T3:=T2[T1](6)T4:=(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI<=20goto(3)T114-七月-21强度削弱p277例如将循环中的*变换为+，提高运算速度(1)P:=0(2)I:=1(4)T2:=A-4(7)T5:=B-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:

6、=P+T7(11)I:=I+1(12)ifI<=20goto(3)I每次增1T1每次增4外提(3)给T1赋初值新增(3’)给T1增4(1)P:=0(2)I:=1(4)T2:=A-4(7)T5:=B-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)14-七月-21复写传播p275例T6:=T2…x:=T6(1)P:=0(2)I:=1(4)

7、T2:=A-4(7)T5:=B-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)目的：使对某些变量的赋值变为无用(6)T4无用T2(1)P:=0(2)I:=1(4)T2:=A-4(7)T5:=B-4(3)T1:=4*1(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(1

8、1)I:=I+1(3’)T1:=T1+4(12)ifI<=20goto(5)14-七月-21删除归纳变量p277例(11)I:=I+1(3’)T1:=T1+4T1:=4*IT1与循环变量I保持线性关系T1称为归纳变量因为I在其它地方没有引用所以(12)中条件可变换为(12)ifT1<=80goto(5)故(2)I(11)I的赋值无用(1)P:=0(2)I:=1(4)T2:=A-4(7)T5:=B-4(3)T1:=4*1(5)T3:=T2[T