编译原理实用教程教学课件杨德芳第8章 代码优化.ppt

《编译原理实用教程教学课件杨德芳第8章 代码优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章代码优化本章学习目标源程序经过词法分析、语法分析、语义分析等阶段的编译后，就得到和与源程序等价的中间代码。但是，此时的中间代码是“机械”生成的，有很多冗余代码，降低了效率，因此，需要进行代码的优化。代码优化的目的是为了提高目标程序的质量。优化可以分为局部优化、循环优化和全局优化。本章要点：局部优化循环优化全局优化8.1优化的概念8.1.1优化概述所谓优化，一般是指为提高目标程序的质量而进行的各项工作。即对程序或中间代码进行各种等价的变换，使得从变换后的程序出发，能生成更有效的目标代码。这里所说的质量，通常就是指目标程序所占的存储

2、空间的大小和运行目标程序所需要的时间的多少。优化的目的在于，既要设法缩小存储空间，又要尽量提高运行速度，而且常常偏重于提高运行速度。代码涉及面很广，从优化与机器的关系出发，可将优化分为与机器无关的优化和与机器相关的优化。与机器无关的优化可以在源程序或中间语言程序一级上进行。这类优化主要包括①常数合并②公共表达式的消除③循环中不变式的外提④运算强度的削弱等。此外，从优化与源程序的关系而言，可以把优化分为局部优化和全局优化。局部优化通常指只有一个入口（即程序段的第一条代码）和一个出口（即程序段的最后一条代码）的基本块上的优化。因为只有一个

3、出口和一个入口，所以是线性的，处理起来比较简单，但是效果较差。全局优化是指在非线性程序块上的优化，由于程序块是非线性的，因此需要分析比基本块更大的程序块乃至整个源程序的控制流程，需要考虑较多的因素。这样的优化比较复杂，开销大，但是效果较好。与机器相关的优化是在目标机上进行的，这类优化主要包括①寄存器的优化②并行分支优化③窥孔优化等。与机器相关的优化依赖于机器。源代码前端中间代码代码生成中间代码优化目标代码目标代码优化图8-1编译的优化工作阶段8.1.2优化技术的简介为了说明问题，我们来看下面的例子，源程序如下：p：=0forI:=1t

4、o20dop:=p+A[I]*B[I]（1）P=0（2）I=1(3）T1:=4*I(4)T2=addr(A)-4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)-4(8)T6=T5[T4](9)T7=T3*T6(10)P=P+T7(11)I=I+1(12)ifI≤20goto(3)图8-2中间代码段1．删除多余的运算（删除公共子表达式）优化的目的是在于使目标代码的执行速度较快。图中（3）和（6）是一个重复的运算，有一个是多余的。将（6）变为T4=T1；这种优化的方式为删除公共子表达式。2．代码外提代码外提为了减少循

5、环中代码的总数。这种方法就是把循环中不变的运算提到循环的外面，使之只在循环外计算一次。经过删除和循环外提后得到的中间代码变如图8-3所示。（1）P=0（2）I=1(4)T2=addr(A)-4(7)T5=addr(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(12)ifI≤20goto(3)图8-3所示删除公共子表达式和代码外提3．强度削弱强度削弱就是把强度大的运算换算成强度小的运算，例如把乘法运算换算成加法运算等。例如：（3）T

6、1:=4*I和（11）I=I+1变为T1:=T1+4中间代码就变为图8-4。4．变换循环控制条件将上面的循环控制条件变为：(12)ifI≤20goto(3)改为T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件，经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）可以从循环中删除，如图8-5所示。（1）P=0（2）I=1(4)T2=addr(A)－4(7)T5=addr(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

7、)I=I+1(3′)T1=T1+4(12)ifT1≤20goto(5)图8-4强度削弱后的中间代码（1）P=0（2）I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)T6=T5[T1](9)T7=T3*T6(10)P=P+T7(11)I=I+1(3′)T1=T1+4(12)ifT1≤80goto(5)图8-5变换循环控制条件，合并已知量，复写传播5．合并已知量与复写传播（2）和（3）合并在一起，使得T1=4。这种变换称为合并已知量。同时把T1的值传递给T4，而

8、（6）和（8）之间并没有改变T4和T1的值。这种方法叫复写传播。四元式序列变为图8-6所示。（1）P=0(4)T2=addr(A)-4(7)T5=addr(B)-4(3)T1=4(5)T3=T2[T1](8)T6=T5[