《编译原理课程教案》第7章：代码优化

《《编译原理课程教案》第7章：代码优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、代码优化第十章本章要求主要内容：代码优化的主要功能，局部优化、全局优化和循环优化的相关概念，各种优化技术重点掌握：代码优化技术，基本块、流图、DAG的概念，必经结点、回边、循环的概念，各种优化技术。代码优化所地位和作用：7.1概述实际上很多地方可以对代码的执行效率进行改进，主要讲对中间代码的优化代码优化：对程序进行等价变换，使得从变换后的程序出发，能够生成更有效的目标代码。优化分类按阶段分:与机器无关的优化--对中间代码进行依赖于机器的优化--对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大

2、范围的优化优化的原则等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果宗旨：获得较好性能的代码（时间，空间）等价意图、结果之间要权衡中间代码优化技术优化工作数据流分析(control-flowanalysis)控制流分析(data-flowanalysis)变换(transformations)快速排序程序voidquicksort(intm,intn){inti,j,v,x;if(n

3、while(a[j]>v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;quicksort(m,j);quicksort(i+1,n);}(1)i:=m–1(2)j:=n(3)T1:=4*n(4)v:=a[T1](5)i:=i+1(6)T2:=4*i(7)T3:=a[T2](8)ifT3vgoto(9)(13)ifi>=jgoto(23)(14)T6:=4*i(15)x:=a[T6](1

4、6)T7:=4*i(17)T8:=4*j(18)T9:=a[T8](19)a[T7]:=T9(20)T10:=4*j(21)a[T10]:=x(22)goto(5)(23)T11:=4*j(24)x:=a[T11](25)T12:=4*i(26)T13:=4*n(27)T14:=a[T13](28)a[T12]:=T14(29)T15:=4*n(30)a[T15]:=x中间代码7.2基本块的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句如果x:=y+z则称对x定值,引用y和z在一个基本块内的一个

5、名字,在程序中的某个给定点是活跃的，是指如果在程序中它的值在该点之后被引用.入口语句：1．程序的第一个语句；或者，2．条件转移语句或无条件转移语句的转移目标语句（此处的转移语句包括各种控制的转向，如call，return，end，stop等）；或者3．紧跟在条件转移语句后面的语句。执行：对于一个基本块，执行时只能从其入口进入，从其出口退出划分基本块的算法求出四元式程序之中各个基本块的入口语句对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。凡未被纳入

6、某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。一般把过程调用语句作为一个单独的基本块*(1)readx(2)readyB1*(3)r:=xmody(4)ifr=0goto(8)B2*(5)x:=y(6)y:=r(7)goto(3)B3*(8)writey(9)haltB4例：*(1)readx(2)ready*(3)r:=xmody(4)ifr=0goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)writey(9)halt流图：有向图。将控制流的信息增加到基本块的集合上来表示一个程序。流图以基本块

7、为单位。如果按顺序执行，就画一条有向边。基本块间的关系:(前驱,后继)B1是B2的前驱，B2是B1的后继:有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个无条件转移语句。*(1)readx(2)ready*(3)r:=xmody(4)ifr=0goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)writey(9)halt练习f0=0f1=1ifm<=1gotoL3i=2L1:ifi<=mgotoL3L2:f2=f0+f1f0=f1f1=f