编译原理 第11章 代码优化

编译原理2020年2月7日S.PO.P语义分析、生成中间代码目标代码生成代码优化语法分析程序词法分析程序错误处理符号表管理编译原理2020年2月7日第11章代码优化1.要求明确代码优化的目的和分类2.掌握基本块的划分方法，基本块内的三种优化方法3.掌握程序流图的构造方法，循环优化的三种优化方法教学目标编译原理2020年2月7日•11.1优化技术概述•11.2局部优化•11.3循环优化教学内容编译原理2020年2月7日11.1代码优化概述原则：不能改变原有程序语义时间效率（减少运行时间）空间效率（减少内存容量）目的：提高目标代码运行效率优化实质上是对代码进行等价变换，变换后代码结构不同但运行结果相同。编译原理2020年2月7日为什么要优化？•有的大型计算程序一运行就要花上几十分钟，甚至好几小时，这时为优化即使付出些代价也是值得的。•另外，程序中的循环往往要占用大量的计算时间。所以为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义至于（像学生作业之类的）简单小程序（在机器内存，速度也已接受），或在程序的调试阶段，花费许多代价去进行一遍又一遍的优化就毫无必要了。编译原理2020年2月7日代码优化分类从优化的层次，与机器是否有关与机器无关：与目标机无关，在中间代码上优化与机器有关：充分利用系统资源，（指令系统，寄存器）从优化涉及的范围局部优化：在基本块内进行优化。循环优化：对循环语句所生成的中间代码进行优化。全局优化：跨越多个基本块的全局范围内的优化，复杂。编译原理2020年2月7日11.2局部优化基本块：程序中一个顺序执行的语句序列，即一个程序段，它只有一个入口和一个出口，入口是第一条语句，出口是最后一条语句。在一个基本块上进行的优化编译原理2020年2月7日基本块划分方法（1）确定各个基本块的的入口语句（基本块的第一个语句）①语句序列的第一个语句是入口语句；②能由条件转移语句或无条件转移语句转到的语句是入口语句；③紧跟在条件转移语句或无条件转移语句后面的语句是入口语句。编译原理2020年2月7日基本块划分方法（2）对于每个入口语句，构造其所属的基本块。它是以下三种情况之一：①该入口语句到下一条入口语句（不包括该入口语句）之间的语句序列；②该入口语句到一条转移语句（包括该转移语句）之间的语句序列；③该入口语句到一条停语句（包括该停语句）之间的语句序列；（3）凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，将其删除。编译原理2020年2月7日【例11.1】（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）halt编译原理2020年2月7日1345620101121⊕1.FACTOR=22.EXP1=…3.IF()GOTO104.BASE=2.05.FACTOR=FACTOR**26.GOTO2010.BASE=…11.FACTOR…20.Q=21.RETURN基本块基本块基本块基本块练习：编译原理2020年2月7日基本块内的优化方法1.合并常量：编译时就计算表达式中的常量运算x=1a=2*x+1b=x+10c=a+b（1）x=1（2）a=3（3）b=11（4）c=14合并常量（1）x=1（2）T1=2*x（3）a=T1+1（4）b=x+10（5）c=a+b四元式编译原理2020年2月7日基本块内的优化方法2．删除公共子表达式x=a*b+cy=a*b+xz=a*b+y（1）T1=a*b（2）x=T1+c（3）y=T1+x（4）z=T1+y删除公共子表达式（1）T1=a*b（2）x=T1+c（3）T2=a*b（4）y=T2+x（5）T3=a*b（6）z=T3+y四元式编译原理2020年2月7日基本块内的优化方法3．删除无用赋值（1）x=10+a（2）y=x+b（1）x=1（2）x=10+a（3）y=x+b编译原理2020年2月7日11.3循环优化经验规则告诉我们：“程序运行时间的80%是由仅占源程序20%的部分执行的”。这20%的源程序就是循环部分，特别是多重循环的最内层的循环部分。因为减少循环部分的目标代码对提高整个程序的时间效率有很大作用。fori=1to10forj=1to100{x:=x+0；y:=5+7+x;}优化一条，少10*100次运算编译原理2020年2月7日北京航空航天大学计算机学院不变表达式：不随循环控制变量改变而改变的表达式或子表达式。如：FORI:=E1STEPE2WHILEE3DOBEGINS:=0.2*3.1416*RP:=0.35*IV:=S*P……不能外提不变表达式可外提1．代码外提：将循环中的不变运算提到循环前面，不变运算是指其运算结果不受循环影响的表达式。循环优化方法编译原理2020年2月7日北京航空航天大学计算机学院如while…dox:=…（b*b-4.0*a*c)…若a,b,c的值在该循环中不改变时，则可将循环不变式移到循环之外，即变为：t1:=b*b-4.0*a*cwhile…dox:=…(t1)…从而减少计算次数——也称为频度削弱编译原理2020年2月7日2．强度削弱：把程序中执行时间较长的运算替换为执行时间较短的运算。如：x**2→x*x3*x→x+x+x8*x,4*x等换成左移运算x/2,x/16等换成右移运算x:=x+1变为INCx指令x/5→x*0.2等利用机器硬件所提供的一些功能，如左移，右移操作，利用它们做乘法或除法，具有更高的代码效率。循环优化方法编译原理2020年2月7日北京航空航天大学计算机学院循环展开是一种优化技术。它将构成循环体的代码（不包括调节和测试部分），重新产生许多次（这可在编译时确定），而不仅仅是一次以空间换时间。循环优化方法循环展开编译原理2020年2月7日北京航空航天大学计算机学院例PL/1中的初始化循环DOI=1TO30A[I]=0.0ENDA[1]=0.030条语句A[2]=0.0（指令）执行……也是30条语句A[30]=0.0展开编译原理2020年2月7日循环优化方法3．删除归纳变量一个基本归纳变量一定是归纳变量。√如果循环中变量I只有唯一的形如I=I±C的赋值，其中C为循环不变量，则称I为基本归纳变量。如果I为循环中的基本归纳变量，循环中的另一变量J可以表示为I的线性函数形式：J=C1*I±C2C1和C2是循环不变量，则称J为循环中与I同族的归纳变量。编译原理2020年2月7日北京航空航天大学计算机学院总结：优化分为两大类局部优化:（一个入口，一个出口，线性）——基本块方法：常数合并冗余子表达式的削除等循环优化：对循环语句所生成的中间代码序列上所进行的优化方法：循环展开频度削弱（循环不变表达式的外提）强度削弱全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是在非线性程序段上（包括多个基本块,GOTO循环）的优化。与机器无的优化独立于机器的（中间）代码优化与机器无的优化目标代码上的优化（与具体机器有关）