第11章代码优化

第11章代码优化源语言程序经过词法分析、语法分析、语义分析等编译前期工作，得到了不改变原来程序运行结果且与原来程序功能等价的中间代码。而生成的中间代码并不是最优的，所以要对中间代码进行优化。所谓优化，实质上是对程序进行各种等价变换，使得从变换后的程序出发，能够生成更有效的目标代码。所谓有效，无非从时间和空间两个因素来考虑，即使得变换之后的程序运行速度更快、占用存储空间更少，这两个因素需要均衡考虑。词法分析器语法分析器中间代码生成器优化段源程序单词符号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码优化：对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。等价：指不改变程序的运行结果。有效：指目标代码运行时间短，占用的存储空间小。编译前端代码优化器编译后端控制流分析数据流分析代码变换本章教学内容优化的分类；常用的代码优化技术;局部优化；循环优化。一、代码优化的分类根据代码优化是否涉及具体的计算机来划分，代码优化可分为两大类。一类是与机器有关的优化，这类优化一般在目标代码上进行，需要依赖于具体的机器。具体的有对寄存器优化、多处理机的优化、特殊指令的优化等。另一类是与机器无关的优化，在中间代码上进行，我们主要讨论这一种优化。另外根据代码优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化是对循环中的代码进行的优化，在一个程序运行时，相当多的一部分时间会花在循环上，因此，基于循环的优化非常重要。全局优化是在整个程序范围内进行的优化。二、常用的代码优化技术代码优化的目的是为了产生效率更高的代码。编译程序中的代码优化阶段提供的对代码的各种变换必须遵循一定的原则。（1）等价原则。经过优化后不应改变程序运行的结果。（2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。（3）合算原则。应尽可能以较低的代价取得较好的优化效果。为了获得更优化的程序，可以从各个环节着手。首先，在源代码这一级，程序员可以通过选择适当的算法和安排适当的实现语句来提高程序的效率。例如，进行排序时，采用“快速排序”比采用“插入排序”就要快得多。其次，在设计语义动作时，我们不仅可以考虑产生更加高效的中间代码，而且还可以为后面的优化阶段做一些可能的预备工作。例如，可以在循环语句的头和尾对应的中间代码“打上标记”，这样可以有助于后面的控制流和数据流分析；代码的分叉处和交汇处也可以打上标记，以便于识别程序流图中的直接前驱和直接后继。对编译产生的中间代码，我们安排专门的优化阶段，进行各种等价变换，以改进代码的效率。在目标代码这一级上，我们应该考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等等。通常为了使优化不依赖于目标机器的特性，主要的优化工作在中间代码上进行。因此，我们着重讨论中间代码这一级上的优化。这时的问题是，优化应用于程序的哪些部分？示例【例10．1】设A,B分别为两个一维数组，其初始地址分别表示为addr(A),addr(B)。源程序段为：X＝0；For(i=1;i20;i++)X=X+A[i]*B[i]；若机器按字节编址，按照循环语句的翻译，可以得到一组中间代码。（1）X=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）X=X+T7（11）i=i+1（12）ifi≤20goto(3)真假中间代码1.删除公共子表达式(删除多余运算)如果一个表达式E在前面已经计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式，是指在一个基本程序块内计算结果相同的子表达式。对相同的子表达式只在第一次出现时计算并且仅计算一次，其结果暂存入Ti，而不必重复计算，这样既节约了空间，又节省了时间。这种优化称为删除公共子表达式，也称为删除多余运算。（1）X=0（2）i=1（3）T1=4*i（4）T2=addr（A）-4（5）T3=T2[T1]（6）T4=T1（7）T5=addr（B）-4（8）T6=T5[T4]（9）T7=T3*T6（10）X=X+T7（11）i=i+1（12）ifi≤20goto(3)真假删除公共子表达式2.代码外提代码外提是指将循环中的不变运算提到循环体前面。处在循环体内的不变运算，不论循环体重复执行多少次都不影响其计算结果，这样的运算只会浪费代码执行时间。因此将这类运算提到循环体外并不影响程序运行结果，还可加快代码执行速度。（1）X=0（2）i=1（3）T1=4*i（4）T2=addr（A）-4（5）T3=T2[T1]（6）T4=T1（7）T5=addr（B）-4（8）T6=T5[T4]（9）T7=T3*T6（10）X=X+T7（11）i=i+1（12）ifi≤20goto(3)真假代码外提3.强度削弱强度削弱是指用执行效率较高的操作等价地替换原操作。对于非算术运算可削弱强度，如尽量使用寄存器，少访问内存（或外存）等。例如，对计算机上的二进制算术运算，做加法一般比作乘法的速度快。如果能在循环中进行这种变换，其优化效果更是显而易见。因此，推广到一般，对中间代码级的运算尽可能降低运算级别。（1）X=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）X=X+T7（11）i=i+1（12）ifi≤20goto(3)真假强度削弱T1=T1＋44.变换循环控制条件(删除归纳变量)for循环中，控制变量i的作用域是本循环体。如果在循环体内存在一个变量（或临时变量）T与循环控制变量i保持线性关系，同时在循环的后面不引用i，而删去i又不影响程序结果，则可由T取代i的控制循环次数的作用。从循环中删除i，这种方法称为变换循环控制条件，或者称为删除归纳变量。（1）X=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）X=X+T7（11）i=i+1（3’）T1=T1+4（12）ifi≤20goto(5)真假变换循环控制条件T1≤805.合并已知变量已知量是指常数或在编译时就能确定其值的变量。合并已知量是指在编译时就将源程序中关于已知量的表达式之值先行算出，不必生成计算该表达式的代码。（1）X=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）X=X+T7（11）i=i+1（3’）T1=T1+4（12）ifT1≤80goto(5)真假合并已知变量4*1=46.复写传播复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响其运行结果的变量。（1）X=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[T4]（9）T7=T3*T6（10）X=X+T7（11）i=i+1（3’）T1=T1+4（12）ifT1≤80goto(5)真假复写传播T17.删除无用赋值变量的最后一次引用到下次引用之前的最近一次赋值期间，可视为无用变量。在变量的无用期内，对它的任何赋值均可删除。对于那些被赋值后从未被引用的变量，对其进行赋值操作也是无用赋值，可删除。即对赋值语句X＝Y，若在程序的任何的地方都不引用X，这是该语句执行与否对程序最终运行结果没有任何作用，这种语句称为无用赋值语句，可以删除。删除无用赋值语句可以减少程序中的无用的变量，还可以使代码更简洁。（1）X=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）X=X+T7（11）i=i+1（3’）T1=T1+4（12）ifT1≤80goto(5)真假删除无用赋值（1）X=0（4）T2=addr（A）-4（7）T5=addr（B）-4（3）T1=4（5）T3=T2[T1]（8）T6=T5[T1]（9）T7=T3*T6（10）X=X+T7（3’）T1=T1+4（12）ifT1≤80goto(5)真假优化后的代码序列优化后的代码序列具有以下特点：减少了循环体内可执行代码，由12条减至10条。减少了作乘法运算的次数，由3次降为1次。减少了全程范围内使用的变量，如i,T4等变量。综上可知，经过一系列优化后的代码其执行效率明显提高。当然优化工作越多，编译系统的代价就会越大。因此，对某种程序设计语言翻译出来的中间代码要实施什么优化，就要视语言的特点具体分析，力争设计一个最适应本语言特点的代码优化方案。三、局部优化局部优化（local）是指基本块内的优化。对于给定的程序，我们可以把它划分为一系列的基本块。在各个基本块的范围内，分别进行优化。局限在基本块范围内的优化称为基本块内的优化，或者称为局部优化。1.基本块的定义所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出，不存在跳转和分叉汇合的情况。2．基本块的划分算法从四元式程序中划分基本块的算法步骤如下：第一步：确定四元式程序（中间代码）中各个基本块的人口语句；所谓入口语句，严格地说来就是下述语句之一：①程序的第一个语句；②能够由条件转移语句或无条件转移语句转移到的目标语句；③紧跟在条件转移语句后面的语句。划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)之间的语句序列组成的。入口语句n……入口语句m划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m入口语句n……停语句m划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。第三步：凡未被纳入某一基本块的语句，都是程序中控制流程无法达到的语句，因而也是不会被执行到的语句，我们可以把它们删除。例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8