编译原理 教学课件 作者 康慕宁 林奕 讲稿_7.ppt

《编译原理 教学课件 作者 康慕宁 林奕 讲稿_7.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章代码优化内容概述代码优化的基本原则基本块及其优化数据流分析循环优化7.1概述中间代码是一种通用的抽象，不考虑与具体机器相关的细节内容。高级语言编写的程序可能本身并不是优化的。某些高级语言的特征在映射到更低层面语言时，存在多种实现方式，具有不同的时间、空间开销。优化必须保证语义上的等价在具有相同功能的条件下，使系统在某方面具有更好的指标。优化的指标：目标代码指令条数目标代码运行效率目标代码占用内存的多少目标代码的功耗……优化的时机中间代码生成时的优化平台无关的优化平台相关的优化（很多在代码生成阶段进行考虑）本章主要关注代码优化的基本原理，不考虑具体机器的情况。7.2中间代码生成阶段的优化

2、大部分优化是在生成中间代码后进行的在中间代码生成阶段也可进行部分优化布尔表达式的优化。主要是短路机制的实现控制流语句的少量优化。如书中例子里，while语句尾部的if-then-else语句在生成then部分的中间代码时，直接跳转到while开头的做法。内置调用语句的优化，可根据已经知道的调用规律，减少不必要的开销。7.3代码优化的基本原则、思路和范围代码优化的基本原则等价原则：所谓等价原则（有的文献上称为“安全性”），就是优化前后的代码具有完全相同的功能。有效原则：优化后产生的代码达到预期的优化目标。合算原则：以较小的代价获得尽可能高的优化效果。优化的基本思路（1）冗余代码的消除（2）重复

3、计算的合并与提取（3）复杂计算的简单化优化的范围子程序内部的优化第一，局部优化。该范围优化针对一个基本块内的中间代码进行优化。第二，超局部优化和区域优化。该范围的优化考虑多个基本块之间的控制流关系，能够实现跨越多个基本块边界的优化。第三，全局优化，也称过程内优化。是针对一个完整的子程序进行的优化。全局优化的主要技术是数据流分析技术。过程间优化（Interprocedural）7.4基本块及其优化方法所谓基本块，就是只包含线性无谓词代码的最长片段。基本块是符合以下性质的代码序列：（1）一个基本块有唯一的入口和出口，分别对应于该块的第一个和最末一个指令；（2）基本块内部的所有指令都是顺序执行的，

4、不存在任何转跳（除了出口语句可以指向其他基本块的入口）；基本块划分算法由于基本块中不包含指向内部的转跳语句，因此分支语句的转跳目标点只可能是一个基本块的开始；而分支语句本身是某个基本块的出口。如果在两个入口语句之间既没有转跳语句作为出口，也没有其他入口语句，则第一个入口语句到第二个入口语句之间的所有语句属于一个基本块。基本块划分算法（1）确定所有的基本块入口点有三种情况：第一，程序的第一个四元式是一个基本块的入口点；第二，条件转移或无条件转移所指向的四元式或指令是一个基本块的入口点；第三，紧跟在条件转移四元式之后的四元式是一个基本块的入口点。（2）从每个入口四元式或指令出发，分别确定各基本块

5、包含的所有四元式。具体判断方法如下：第一，如果从一个入口到一个出口之间没有其他出口和入口四元式，则该入口语句到出口语句间的所有四元式属于一个基本块；第二，如果一个入口到下一个入口四元式之间没有其他出口语句，则二者之间的所有四元式或指令（不包含下一入口）属于一个基本块；第三，如果从一个入口到停机四元式之间不存在其他入口和出口，则该入口到停机四元式之间的所有四元式属于同一个基本块。注意，停机四元式也可以是表示子程序结束的return等语句。基本块划分的例子1左面的程序等价于以下的四元式序列：<1>(=,6,0,a)<2>(=,7,0,b)<3>(-,x,a,T1)<4>(=,T1,0,a)<5>

6、(j<,a,5,<3>)<6>(=,10,0,y)<1><2>是一个基本块。其判定依据是<1>是入口，<2>是<1>到下一入口<3>之间的四元式，且其间没有其他入口和出口四元式。<3><4><5>是一个基本块。其判定依据是<3>是<5>的转跳目标，因此是一个入口点。<3>～<5>中，只有<5>是出口点，且没有停机语句、其他出口点或入口点。<6>是条件转移语句<5>的下一条语句，是一个入口点。如果没有其他后续语句，则<6>可以构成一个单独的基本块。基本块划分的例子2该程序写成等价的四元式序列如下：<1>(=,0,0,a)<2>(=,0,0,b)<3>(+,x,1,T1)<4>(=,T1,0,b

7、)<5>(-,y,a,T2)<6>(=,T2,0,a)<7>(j<,a,5,<5>)<8>(j>,b,7,<3>)对该四元式序列划分基本块，可得到以下结果：<1><2>属于同一个基本块；<3><4>属于一个基本块（对应于b=x+1）；<5><6><7>属于一个基本块（对应于a=y-a和if(a<5)gotoL_a）；<8>属于一个基本块（对应于if(b>7)gotoL_b）。利用基本块删除无用代码如果用上述算