10第10章 代码优化.pptVIP

第10章 代码优化 10.1局部优化 10.1.1基本块的划分 10.1.1基本块的划分 10.1.1基本块的划分 10.1.2 基本块的优化技术 第10章 代码优化 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.3 基本块的DAG表示 10.1.5 基本块优化的实现 10.1.5 基本块优化的实现 10.2 循环内的优化 10.2.1 循环结构的定义 10.2.2循环的查找 第10章 代码优化 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 10.3.2 循环优化的实现 习题 不变表达式外提算法如下： 1)求出循环L中的所有不变表达式。 2)对求得的每个不变表达式S(如A=B 或A=OP 或A=B OP C)，检查它是否满足以下条件1和2 ①a.S所在的结点是L的所有出口结点的必经结点。 b.A在L中其它地方未在定值 c.L中所有A的引用点只有S中A的定值才能到达。 ② A在离开L之后，不再是活跃的(即A在L的任何出口结点的后继结点的入口处不是活跃的)，并且条件1)中的b和c成立。 3)按不变表达式求得的顺序，依次把符合(2)的条件1)或2)不变表达式S外提到L的前置结点中。如果S的运算对象(B或C)是在L中定值的，则只有当这些定值四元式都以外提到前置结点中时，才能把S也外提到前置结点中。 2、强度削弱 强度削弱优化技术是指将一种执行时间较长的运算用另一种需用较少执行时间的运算来代替，从而达到提高目标程序执行效率的目的。 乘法运算代之以加法运算，则可节省时间。将计算X2的函数调用代之以花时间较少的乘法，即计算X*X。而正定点数的对于2的幂次方数的乘法和除法可通过移位操作来实现效率更高。 I=0; L1: J=I*4; I=I+1; IF I100 GOTO L1; I=0; J=-4； L1: J=J+4; I=I+1; IF I100 GOTO L1; 3、删除归纳变量 如果在循环L中对变量只有唯一的递归赋值I=I+C，其中C为循环不变量，则称I为循环中的基本归纳变量。 如果I是循环中的一个基本归纳变量，而变量J=C1*I+C2，其中C1、C2为循环不变量，则称J是归纳变量，且与I同族。一个基本归纳变量也是一个归纳变量, 如果循环中的某个变量，其值随着循环的每次重复都是增加或减少某个固定的量，则这个变量就是循环的归纳变量。 由于在执行循环时，同族的各归纳变量的值同步变化，那么，当同族的归纳变量有多个时，就可以删除一些归纳变量的计算，从而提高目标程序的效率。 例如，有程序代码如下，该程序流图如图10.11所示。 A=0; I=1； L1: B=J+1; C=B+I; A=C+A;; IF I=100 GOTO L2; I=I+1; GOTO L1; L2: … * 代码优化是指编译程序为了生成高质量的目标程序而做的各种加工和处理。而高质量的目标程序是指对同一源程序在运行时所占的内存空间较小，且在同一台机器上运行时间也较短的目标程序。代码优化并不能保证得到的目标代码是最优的，而只能是相对较优的。优化的原则是在编译阶段能计算的量绝不留到运行时刻去做，能在外层循环中计算的量绝不放到内层去做，能够共用存储单元(寄存器)的尽量共用。 优化可在编译的各个阶段进行，最主要的时机是在语法、语义分析生成中间代码之后，在中间代码上进行。这一类优化不依赖于具体的计算机，而取决于语言的结构。 局部优化：是指在只有一个入口和一个出口，且语句为顺序执行的程序段上所进行的优化。这种程序段，称为基本块。将基本块作为优化要考虑的主要范围为优化决策提供了基础，在一般情况下，将会产生更高质量的代码。 循环优化：是对循环语句所生成的中间代码序列所进行的优化处理，这类优化包括外提不变表达式、强度削弱和删除归纳变量。 全局优化：是在非线性程序段上的优化。因为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂 局部优化是指局部范围内的优化。这个“局部范围”是指基本块，即只有一个入口和一个