编译原理 教学课件 作者 李冬梅 施海虎 第8章 代码优化.ppt

《编译原理 教学课件 作者 李冬梅 施海虎 第8章 代码优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、S.PO.P语义分析、生成中间代码目标代码生成代码优化语法分析程序词法分析程序错误处理符号表管理第8章　代码优化要求明确代码优化的目的和分类掌握基本块的划分方法，基本块内的三种优化方法掌握程序流图的构造方法，循环优化的三种优化方法教学目标8.1局部优化8.2循环优化教学内容8.1代码优化原则：不能改变原有程序语义时间效率（减少运行时间）空间效率（减少内存容量）目的：提高目标代码运行效率优化实质上是对代码进行等价变换，变换后代码结构不同但运行结果相同。代码优化分类从优化的层次，与机器是否有关与机器无关：与目标机无关，在中间代码上优化与机

2、器有关：充分利用系统资源，（指令系统，寄存器）从优化涉及的范围局部优化：在基本块内进行优化。循环优化：对循环语句所生成的中间代码进行优化。全局优化：跨越多个基本块的全局范围内的优化，复杂。8.1局部优化基本块：程序中一个顺序执行的语句序列，即一个程序段，它只有一个入口和一个出口，入口是第一条语句，出口是最后一条语句。在一个基本块上进行的优化基本块划分方法（1）确定各个基本块的的入口语句（基本块的第一个语句）①语句序列的第一个语句是入口语句；②能由条件转移语句或无条件转移语句转到的语句是入口语句；③紧跟在条件转移语句或无条件转移语句后面

3、的语句是入口语句。基本块划分方法（2）对于每个入口语句，构造其所属的基本块。它是以下三种情况之一：①该入口语句到下一条入口语句（不包括该入口语句）之间的语句序列；②该入口语句到一条转移语句（包括该转移语句）之间的语句序列；③该入口语句到一条停语句（包括该停语句）之间的语句序列；（3）凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，将其删除。【例8.1】（1）readX（2）readY（3）R=XmodY（4）ifR==0goto（8）（5）X=Y（6）Y=R（7）goto（3）（8）write

4、Y（9）halt1345620101121⊕FACTOR=2EXP1=…IF()GOTO10BASE=2.0FACTOR=FACTOR**2GOTO2010.BASE=…11.FACTOR…20.Q=21.RETURN基本块基本块基本块基本块练习：基本块内的优化方法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四元式基本块内的优化方法2．删除公共子表达式x

5、=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四元式基本块内的优化方法3．删除无用赋值（1）x=10+a（2）y=x+b（1）x=1（2）x=10+a（3）y=x+b8.2　循环优化首结点：从它开始到有向图中任何结点都有一条通路的结点。一个程序流图是具有唯一首结点的有向图。程序流图（控制流程图或流图）：三元组G=(N，E，n0)N：结点（基本块）集

6、E：边集n0：首结点。循环优化方法1．代码外提：将循环中的不变运算提到循环前面，不变运算是指其运算结果不受循环影响的表达式。循环中的不变运算均可提到循环外×2．强度削弱：把程序中执行时间较长的运算替换为执行时间较短的运算。如：x**2x*xx/5x*0.2x*2,x*4左移运算x/2,x/4右移运算循环优化方法循环优化方法3．删除归纳变量一个基本归纳变量一定是归纳变量。√如果循环中变量I只有唯一的形如I=I±C的赋值，其中C为循环不变量，则称I为基本归纳变量。如果I为循环中的基本归纳变量，循环中的另一变量J可以表示为I的线性函

7、数形式：J=C1*I±C2C1和C2是循环不变量，则称J为循环中与I同族的归纳变量。小结明确代码优化的目的和分类掌握基本块的划分方法，基本块内的三种优化方法：合并常量、删除公共子表达式和删除无用赋值掌握程序流图的构造方法，循环优化的三种优化方法：代码外提、强度削弱和删除归纳变量习题1(1)—(7)、2、3思考题