11章节 代码优化.pptVIP

第11章 代码优化;本章知识点：; 优 化;1、优化的概念： 优化的定义:对程序进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大，或占用存储空间减少，或两者都有。我们通常称这种变换为优化。 ?; 优化的目的是为了产生更高效的代码。由优化编译程序提供的对代码的各种变换必须遵循下面的原则： 1)等价原则 主要指优化后的目标代码运行时间较短,以及占用的存储空间较小。 2)有效原则 使优化后所产生的目标代码运行时间确实较短，占用的空间确实较小 3）合算原则 应尽可能以较低的代价取得较好的优化效果;3、代码优化的基本方法 按照与机器相关的程度，代码优化分为： 与机器相关的优化：在生成目标程序时进行的，它在很大程度上与具体的计算机有关。 与机器无关的优化：在语法、语义分析生成中间代码之后，在中???代码上进行，这一类优化不依赖于具体的计算机，而取决于语言的结构。;根据优化所涉及的程序范围分成: 局部优化：基本块范围内的优化：合并已知量消除公共子表达式，削减计算强度和删除无用代码 循环优化：主要是基于循环的优化，包括循环不变式外提，归纳变量删除，计算强度削减。 全局优化：主要是在整个程序范围内进行的优化。?因为程序段是非线性的，因此需要分析程序的控制流和数据流，处理比较复杂。;4、优化技术;局限于基本块范围内的优化称为基本块内的优化 或局部优化 。 1、基本块的定义 所谓基本块是指程序中一顺序执行的语句序 列，其中只有一个入口和一个出口，入口就是其 中的第一个语句，出口就是其中的最后一个语 句。 ;划分四元式程序为基本块的算法如下： （1）求出四元式程序中各个基本块的入口语句，它们可以是下述语句之一： ①程序的第一个语句；;（2）对以上求出的每一入口语句构造其所属的基本块。它是由该入口语句到另一入口语句(不包括该入口语句)，或到一转移语句(包括该转移语句)，或到一停语句（包括该停语句)之间的语句序列组成的。;【例如】有下列三地址代码程序： 1）read X 2）read Y 3）R：=X mod Y 4）if R=0 goto (8) 5) X:=Y 6) Y:=R 7) goto (3) 8）write Y 9) halt;【例如】划分基本块 (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt ;3、基本块的变换 基本块内可进行的优化： ;删除公共子表达式 如果一个表达式E的值已计算过，并且在此之后E中变量的值没有改变，则称E为公共子表达式，为避免重复计算而删除，称为删除公共子表达式 【例如】x:=(a+b)*c-(a+b)^2 t1=a+b; t2=t1*c; t3=a+b; t4=t3^2 X:=t2-t4; ;x+y*t-a*(x+y*t)/(y*t) (1)( *， y， t， t1 ) (2)( +， x， t1， t2 ) (3)( *， y， t， t3 ) (4)( +， x， t3， t4 ) (5)( *， a， t4，t5 ) (6)( *， y， t， t6 ) (7)( /， t5， t1，t7 ) (8)( -， t2， t7， t8 );删除无用代码;合并已知量 a = 10 * 5 + 6 - b; t0 = 10; t1 = 5 ; t2 = t0 * t1 ; t3 = 6 ; t4 = t2 +t3 ； t5 = t4 – b; a = t5 ; ;【例】 d = 2*3.14*r (1) ( *，2，3.14，t1 ) (2) ( *，t1 ， r，t2 ) (3) ( =，t2， ， d ) 2*3.14的值在编译时刻就可以确定。 (1) ( *，6.28，r，t2 ) (2) ( =，t2， ， d );复写传播 ;t2 = t1 ; t3 = t2 * t1; t4 = t3 ; t5 = t3 * t2 ; c = t5 + t4 ; ;重新命名临时变量例如:? t:=b+c → u:=b+c;?????;返回;DAG图中结点的特点 1.叶结点????? 标记:标识符名(变量名)或常数,写在结点下面。??????代表:该结点代表该变量或常数的值。??????地址的表示：Addr(A)