第11章-代码优化

武汉理工大学计算机科学系林泓第11章代码优化11.1代码优化技术11.2局部优化11.3控制流程分析和循环武汉理工大学计算机科学系林泓【学习目标】通过本章学习：◇理解所谓代码优化是指什么？◇知道最常用的代码优化技术有哪些？◇知道实现代码优化要进行哪些工作？【学习指南】所谓代码优化是指对程序代码进行等价变换。程序代码可以是中间代码(如四元式代码)，也可以是目标代码。优化的含义是最终生成的目标代码短(而运行速度快)，时空效率优化。最常用的代码优化技术有删除多余运算，循环不变代码外提，强度削弱，变换循环控制条件，合并已知量与复写传播，以及删除无用赋值等等。【难重点】从概念上理解什么是代码优化，编译过程中可进行哪些优化，以及进行优化所需要的基础都没有难点，但在实现上是有相当复杂的工作。武汉理工大学计算机科学系林泓11.0概述源语言程序经过词法分析、语法分析、语义分析和中间代码生成等编译前期工作（编译前端），得到了与源程序等价的中间代码程序。中间代码程序的质量将直接影响目标程序执行的效率。程序执行的效率体现在两个方面：目标程序运行时刻所占用的存储空间和目标程序运行时刻所耗费的时间。所谓优化，是为了提高程序的执行效率而对程序代码进行的等价变换。使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。编译过程中可进行的优化可按阶段划分：优化可在编译的不同阶段进行，分为中间代码一级和目标代码一级的优化。可按优化涉及的程序范围划分：对同一阶段，分为局部优化,循环优化和全局优化。可按优化是否涉及具体计算机来划分：分为与计算机有关的优化和与计算机无关的优化。武汉理工大学计算机科学系林泓优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也有所不同，在同一范围内，可进行多种优化。目前编译程序的优化工作一般是在中间代码生成之后和（或）目标代码生成之后进行。如图11.1所示。编译前端代码生成中间代码优化目标代码目标代码优化中间代码源程序目标程序武汉理工大学计算机科学系林泓中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化是对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。武汉理工大学计算机科学系林泓编译程序的优化工作旨在生成较好性能的目标代码，为此，编译程序需要对代码（中间代码或目标代码）进行各种方式的变换。变换的宗旨是：等价－经优化工作变换后的代码运行结果应与原来程序运行结果一样。有效－经优化工作变换后的代码应运行时间较短，占用的存储空间较小。合算－获得较好性能的目标代码是优化工作的意图，而优化本身包括大量的代码分析和变换工作，这里有个权衡：应尽可能以较低的代价取得较好的优化效果。武汉理工大学计算机科学系林泓11.1代码优化技术常用的优化技术有：①删除多余运算；②循环不变代码外提；③强度削弱；④变换循环控制条件；⑤合并已知量与复写传播；⑥删除无用赋值。为了说明这些常用的优化技术，我们来看下面这个例子。例11.1源程序是：P∶=0for（I=1；I=20；I=++）P∶=P+A[I]*B[I]；经过编译得到的中间代码如图11.2所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定每个元素按4字节编址。那么，对于这个中间代码段，如何进行上述优化。武汉理工大学计算机科学系林泓图11.2中间代码段(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)B1B2数组元素地址计算的常量部分T2数组元素地址计算的增量部分T1P∶=0for（I=1；I=20；I=++）P∶=P+A[I]*B[I]；武汉理工大学计算机科学系林泓1）删除多余运算（删除公共子表达式）优化的目的在于使生成的目标代码较少而执行速度较快。四元式（6）变换成：T4∶=T1。这种优化称为删除多余运算或称为删除公共子表达式。图11.2中间代码段(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)B1B2武汉理工大学计算机科学系林泓2）代码外提减少循环中代码总数的一个重要办法是循环不变代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面,使之只在循环外计算一次。上例中，我们可以把四元式（4）和四元式（7）提到循环外。经过删除多余运算和代码外提后，代码变换成图11.3。图11.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)B1B2武汉理工大学计算机科学系林泓3）强度削弱强度削弱的思想是把强度大的运算换算成强度小的运算。循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图11.4所示。图11.4强度削弱(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(3)T1:＝T1+4(12)ifI≤20goto(5)B1B2武汉理工大学计算机科学系林泓4）变换循环控制条件图11.4的代码中，四元式（12）的循环控制条件I≤20变换成T1≤80，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）成为多余运算，可以从循环中删除。变换循环控制条件可以达到代码优化的目的。(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(3)T1:＝T1+4(12)ifT1≤80goto(5)B1B2图11.5变换循环控制条件，合并已知量，复写传播武汉理工大学计算机科学系林泓图11.4中，四元式（3）可变为T1＝4，这种变换称为合并已知量。图11.4中，四元式(6)把T1的值复写到T4中，四元式（8）要引用T4的值，而从四元式（6）到四元式（8）之间未改变T4和T1的值，则将四元式（8）改为T6∶=T5[T1]，这种变换称为复写传播.复写传播之后运算结果保持不变。图11.4经过变换循环控制条件，合并已知量和复写传播等变换后，变为图11.5。图11.5变换循环控制条件，合并已知量，复写传播(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)B1B2武汉理工大学计算机科学系林泓6）删除无用赋值在图11.5中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图11.6所示。比较图11.2和图11.6可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的一系列工作是非常复杂的，代价也是很大的。图11.6删除无用赋值(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)B1B2武汉理工大学计算机科学系林泓11.2局部优化我们所说的局部优化是指基本块内的优化。所谓基本块，是指程序中一个单入口、单出口的线性程序块（顺序执行的语句序列）。控制流只能从其入口语句进入，从其出口语句退出,没有中途停止或分支。局部优化工作包括对于一个给定的程序，把它划分为一系列的基本块,在各个基本块范围内分别进行优化。局限于基本块范围内的优化称为基本块内的优化，也称为局部优化。武汉理工大学计算机科学系林泓11.2.1基本块的划分我们先定义基本块的入口语句。所谓入口语句有三种，就是：①程序的第一个语句；②条件转移语句或无条件转移语句的转移目标语句；③紧跟在条件转移语句后面的语句。有了入口语句的概念之后，我们就可以给出划分中间代码（四元式程序）为基本块的算法。武汉理工大学计算机科学系林泓划分中间代码（四元式程序）为基本块的算法：①求出四元式程序中各个基本块的入口语句。②对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。③凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。武汉理工大学计算机科学系林泓我们以下述四元式程序为例来说明如何划分基本块的。例11.1:有四元式程序如下，构造其基本块。(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt武汉理工大学计算机科学系林泓先求出四元式程序中各个基本块的入口语句：1.语句（1）是程序的第一个语句，因此它是入口语句。2.语句（4）和语句（8）是条件转移语句或无条件转移语句的转移目标语句，因此是入口语句。3.语句（6）是紧跟在条件转移语句后面的语句，因此是入口语句。(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt基本块：语句（1），（2）和（3）构成第一个基本块；语句（4）和（5）构成第二个基本块；语句（6）和（7）构成第三个基本块；语句（8）和（9）构成第四个基本块。武汉理工大学计算机科学系林泓11.2.2基本块内的优化变换很多优化变换可作用于基本块而不改变它计算的表达式集合，这样的变换对改进代码的质量是很有用的。有两类重要的局部等价变换可用于基本块；它们是保结构的变换和代数变换。基本块的主要保结构变换是：①删除公共子表达式②删除无用代码③重新命名临时变量④交换语句次序武汉理工大学计算机科学系林泓对于删除公共子表达式和删除无用代码这两种优化技术，我们在11.1中已经讨论过，这里简单介绍重新命名临时变量和交换语句次序是什么含义。重新命名临时变量：假如有语句t∶=b+c，其中t是临时变量。如果把这个语句改为u∶=b+c，其中u是新的临时变量，并且把这个t的所有引用改成u，那么基本块的运算结果不变。交换语句次序：如果基