编译原理(清华)第十一讲代码优化

第11章代码优化学习目标：掌握：基本块的划分、基本块的DAG优化理解：什么是局部优化、循环优化、全局优化了解：循环优化技术11.1优化技术简介11.2局部优化11.3循环优化简介11.1优化技术简介什么是优化：所谓优化是对代码进行等价变换，使得变换后的代码的效率更高（节省运行时间、存储空间或两者兼而有之）优化可在编译的不同阶段进行，最主要的优化有–中间代码优化（不依赖具体计算机）–目标代码优化（依赖于具体计算机）中间代码优化中间代码源代码编译前端代码生成目标代码目标代码优化编译的优化工作阶段优化的分类：根据优化涉及的程序范围，分为：–局部优化：在只有一个入口、一个出口的基本块上进行优化–循环优化：对循环中的代码进行优化–全局优化：在整个程序范围内进行的优化中间代码优化常用技术1.删除多余运算（删除公共子表达式）如果子表达式E在前面计算过，且之后E中的变量值都未改变，那么E的重复出现称为公共子表达式，可避免重复计算(1)和(4)中都有4*I的运算，(1)到(4)之间无对I的赋值，显然两次计算的值是相等的，(4)的运算是多余的例(1)T1:=4*I(2)T2:=addr(A)－4(3)T3:=T2[T1](4)T4:=4*I(5)……(4)变换成T4:=T12.合并已知量与复写传播如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量若有A:=B，称为把B值复写到A。如果其后有引用A的地方，且其间A、B的值都未改变，则可把对A的引用改为对B引用，称为复写传播。例：（1）I:=1（2）T1:=4*I（3）T4:=T1（4）T6:=T5[T4]I是已知量把T1的值复写到T4（4）T6:=T5[T1]复写传播（2）T1:=4合并已知量3.删除无用赋值有些变量的赋值从未被引用，称为无用赋值，应删除。无用赋值分三种情况：–变量被赋值，但在程序中从未被引用（在局部范围内难判定）–变量赋值后未被引用又重新赋值，则前面赋值是无用的–变量的赋值只被计算变量自己引用，其他变量都不引用它例（1）I:=1（2）T1:=4（3）T3:=T2[T1]（4）T4:=T1（5）I:=I+1（6）T1:=T1+4（7）ifT1≤80goto(3)(4)中对T4赋值，但T4未被引用；(1)和(5)对I赋值，但只有(5)中计算I时引用I如果程序其他地方不需要引用T4和I，则(4)、(1)和(5)是无用赋值，可删除。（2）T1:=4（3）T3:=T2[T1]（6）T1:=T1+4（7）ifT1≤80goto(3)4.其他优化技术以下优化技术将在循环优化中介绍：代码外提强度削弱变换循环控制条件（删除归纳变量）11.2局部优化局部优化是指基本块内的优化基本块是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从入口语句进入，从其出口语句退出11.2.1基本块的划分把程序（中间代码形成）划分成基本块的算法：1.求基本块的入口语句，它们是：1)程序的第一个语句；或者2)条件转移或无条件转移语句的转移目标语句；或者3)紧跟在条件转移语句后面的语句。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)halt(1)、(3)、(5)和(8)是入口语句，分别构成基本块B1{(1)、(2)}B2{(3)、(4)}B3{(5)、(6)、(7)}B4{(8)、(9)}(1)readX(3)R:=XmodY(5)X:=Y(8)writeY11.3循环优化简介循环就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，所以循环的代码优化对提高目标代码的效率将起更大的作用。11.3.1程序流图把控制流的信息加到基本块集合上构成的有向图称为表示程序的流图，简称流图。流图的构造方法：点集：以基本块为结点，含程序第一条语句的结点为首结点。边集：从基本块Bi向基本块Bj引有向边，仅当1)Bj在程序中的位置紧跟在Bi之后,且Bi的出口语句不是无条件转移语句或停止语句。或者2)Bi的出口是转移语句(goto(s)或if…goto(s))，并且转移目标(s)是Bj的入口语句。例：构造以下程序的流图(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt11.3.2循环优化1.代码外提把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面，使之只在循环外计算一次，这种优化称为代码外提。循环不变运算：运算量为常量或在循环外定值，每次循环时其值不变的运算。(1)P:=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)P:=P+T7(11)I:=I+1(12)ifI≤20goto(3)中间代码段B1B2(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(4)中的运算量addr(A)是分配的数组A的首地址，是个常量，4也是常量，因而(4)是循环不变运算，同样(7)也是循环不变运算，(4)、(7)都可提到循环前2.强度削弱强度削弱是指把程序中强度大的运算替换成强度小的运算。例如把乘法运算换成加法运算等(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)中间代码段(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)强度削弱I和T1始终保持T1:=4*I的线性关系这样把(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)ifI≤20goto(5)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(3’)T1:=T1+4(12)ifT1≤80goto(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)I:=I+1(3’)T1:=T1+4(12)ifI≤20goto(5)本章小结主要讨论在中间代码级别上进行的优化优化的种类：局部优化、循环优化、全局优化基本块内的优化删除公共子表达式、合并已知量、复写传播、删除无用赋值循环优化代码外提、强度削弱、变换循环控制条件