第十章 优化.ppt

1、第十章 代 码 优 化,通过程序等价变换（局部变换和全局变换）来改进程序，称为优化 介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换,优化编译器的组织,10.1.1 代码改进变换的原则 （1）等价原则。经过优化后不应改变程序运行的结果。 （2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。 （3）合算原则。应尽可能以较低的代价取得较好的优化效果。,10.1 优化的概述,10.1.2 优化的主要种类 本节所用的例子 i = m 1; j = n; v = an;(1) i := m 1 while (1) (2) j := n do i = i +1; while(

2、aiv); (4) v := at1 if (i = j) break;(5) i := i + 1 x=ai; ai=aj; aj=x; (6) t2 := 4 * i (7) t3 := at2 x=ai; ai=an; an=x; (8) if t3 v goto (5),10.1 优化的概述,本节所用的例子 i = m 1; j = n; v = an;(9) j := j 1 while (1) (10) t4 := 4 * j do i = i +1; while(aiv);(12) if t5v goto (9) if (i = j) break;(13) if i =j got

3、o (23) x=ai; ai=aj; aj=x;(14) t6 := 4 * i (15 ) x := at6 x=ai; ai=an; an=x;. . .,10.1 优化的概述,(1) 公共子表达式删除 B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,10.1 优化的概述,B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j

4、 t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,10.1 优化的概述,B5 x=ai; ai=aj; aj=x;,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,t6 := 4 * i x := at6 t7 := t6 t8 := 4 * j t9 := at8 at7 := t9 t10 := t8 at8 := x goto B2,10.1 优化的概述,(2)复写传播 形成为f := g的赋

5、值叫做复写 优化过程中会大量引入复写,t6 := 4 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,t6 := 4 * i x := at6 t7 := t6 t8 := 4 * j t9 := at8 at7 := t9 t10 := t8 at10 := x goto B2,10.1 优化的概述,(2)复写传播 复写传播是在复写语句f := g后，尽可能用g代表f，目的是使某些变量的赋值变为无用,t6 := 4 * i x := at6 t7 := 4 * i

6、t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,t6 := 4 * i x := at6 t7 := t6 t8 := 4 * j t9 := at8 at7 := t9 t10 := t8 at10 := at6 goto B2,t6 := 4 * i x := at6 t7 := t6 t8 := 4 * j t9 := at8 at6 := t9 t10 := t8 at8 := at6 goto B2,10.1 优化的概述,(3) 删除无用代码 无用代码是指计算的结果决不被引用的语句 一些优化变换可能会引起无

7、用代码,x := t3 at2 := t5 at4 := t3 goto B2,at2 := t5 at4 := t3 goto B2,x := t3 at2 := t5 at4 := x goto B2,10.1 优化的概述,(4)代码外提 代码外提是循环优化的一种 循环优化的其它重要技术 归纳变量删除 强度削弱 例：while (i = limit 2 ) 变换成 t = limit 2; while (i = t ) ,10.1 优化的概述,(5) 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变

8、量删除 过程来完成 对本例可以先做强度削弱 它给删除归纳变量创造机会,10.2 局 部 优 化,怎样为三地址语句序列生成目标代码？ begin |(1)prod := 0 prod := 0; |(2)i := 1 i := 1; |(3)t1 := 4* i do begin |(4)t2:= at1 prod := prod + ai * bi;|(5 )t3 := 4* i i := i +1 |(6 )t4 := bt3 end while i = 20 |(7 )t5 := t2 * t4 end |(8 )t6 := prod + t5 |(9 )prod := t6 |(10)t

9、7 := i +1 |(11)i := t7 |(12 )if i = 20 goto (3),10.2 局 部 优 化,10.2.1 基本块 基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开 再用有向边表示基本块之间的控制流信息，就能得到程序的流图,10.2 局 部 优 化,三地址语句序列的划分基本块 首先确定所有的入口语句 序列的第一个语句是入口语句 能由条件转移语句或无条件转移语句转到的语句是入口语句 紧跟在条件转移语句或无条件转移语句后面的语句是入口语句 每个入口语句到下一个入口语句之前的语句序列构成一个基本块,10.2 局 部 优 化,(1)prod := 0 (2)i

10、 := 1 (3)t1 := 4* i (4)t2:= at1 (5 )t3 := 4* i (6 )t4 := bt3 (7 )t5 := t2 * t4 (8 )t6 := prod + t5 (9 )prod := t6 (10)t7 := i +1 (11)i := t7 (12 )if i = 20 goto (3),10.2 局 部 优 化,基本块的变换 三地址语句x := y + z引用y和z并对x定值 一个名字的值在基本块的某一点以后还要引用的话，我们说这个名字在该点是活跃的,10.2 局 部 优 化,合并已知量 a := 2 .(中间没有改变a的值) b := a * 4/可

11、以变换为b:=8 临时变量改名,10.2 局 部 优 化,交换相邻的独立语句 t1 := b + c t2 := x + y t2 := x + y t1 := b + c 当且仅当x和y都不是t1，b和c都不是t2 代数变换 x := x + 0可以删除 x := x * 1 可以删除 x := y *2 改成x := y * y 有没有基本块优化的形式化方法？,10.2 局 部 优 化,10.2.2 基本块的DAG表示 1）图的叶结点以标识符或常数作为标记 2）图的内部结点以一运算符作为标记，表示该结点是应用该运算符对其后继结点所代表的值进行运算的结果 3）各结点可能附加一个或多个标识符，

12、表示这些变量具有该结点所代表的值 算法演示,10.3 循环优化,循环是程序中那些可能反复执行的代码序列。 对循环中的代码，可以实行代码外提、强度削弱和删除归纳变量等优化 103l 代码外提 1032 强度削弱 1033 删除归纳变量,代码外提 将循环不变语句提到循环的前置结点中 并不是所有的循环不变语句都可以外提 我们讨论三个条件（并非是必要条件）,10.3 循环优化,语句s : x := y+ z可以外提的条件 含s的块是循环所有出口结点的必经结点,10.3 循环优化,10.3 循环优化,语句s : x := y+ z可以外提的条件 循环中没有其它语句对x定值 考查B2-B3-B4 -B2-

13、B4-B5 i：=3外提，j=2 不外提，i=3,10.3 循环优化,语句s : x := y+ z可以外提的条件 x的其它定值都不能到达循环中x的引用 考查B4的循环 不变运算i:=2 s是出口必经的 循环中唯一的 i定值点 x=0 y=2 B2B3B4B2B4B5,10.3 循环优化,强度削弱：执行时间较长的运算替换为执行时间较短的运算 13)i:=i+1 4) 8)计算的t2,t6是i的线性函数 强度削弱的结果10.16 10.16中对t3,t7进行强度削弱,1)i := 1,B1,B2,3)t1 := 2*j 6)t4 := addr(A)-11 7)t5 := 2*j 10)t8 :

14、= addr(A)-11,4)t2 := 10*i 5)t3 := t2+t1 8)t6 := 10*i 9)t7:=t6+t5 11)t9:=t8t7 12)t4t3:=t9+1 13)i:=i+1 14)goto B2,B3,2)i f i10 goto 15,B2,15).,10.3 循环优化,归纳变量删除 循环归纳变量:在循环中，其值的每次改变都增加或减少某个固定的常量 基本归纳变量：在循环中只有一个形如i := i c的i，其中c是常量 其它归纳变量:在循环中仅定值一次，并且其值是某个基本归纳变量的线性函数。,10.3 循环优化,寻找归纳变量 找出所有基本归纳变量i := i c寻找只有一个赋值的k，其形式为 k := j*b, k := b*j, k := j / b, k := j b, k :=