《第十章优化.ppt

中国科大 第十章 代 码 优 化 通过程序等价变换（局部变换和全局变换）来改进程序，称为优化 介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换 优化编译器的组织 10.1 优化的概述 10.1.1 代码改进变换的原则 （1）等价原则。经过优化后不应改变程序运行的结果。 （2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。 （3）合算原则。应尽可能以较低的代价取得较好的优化效果。 10.1.2 优化的主要种类 本节所用的例子 i = m ?1; j = n; v = a[n]; (1) i := m ?1 while (1) { (2) j := n do i = i +1; while(a[i]v); (3) t1 := 4 * n do j =j ?1;while (a[j]v); (4) v := a[t1] if (i = j) break; (5) i := i + 1 x=a[i]; a[i]=a[j]; a[j]=x; (6) t2 := 4 * i } (7) t3 := a[t2] x=a[i]; a[i]=a[n]; a[n]=x; (8) if t3 v goto (5) 10.1 优化的概述 本节所用的例子 i = m ?1; j = n; v = a[n]; (9) j := j ?1 while (1) { (10) t4 := 4 * j do i = i +1; while(a[i]v); (11) t5 := a[t4] do j =j ?1;while (a[j]v); (12) if t5v goto (9) if (i = j) break; (13) if i =j goto (23) x=a[i]; a[i]=a[j]; a[j]=x; (14) t6 := 4 * i } (15 ) x := a[t6] x=a[i]; a[i]=a[n]; a[n]=x; . . . 10.1 优化的概述 (1) 公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.1 优化的概述 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.1 优化的概述 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.1 优化的概述 (2)复写传播 形成为f := g的赋值叫做复写 优化过程中会大量引入复写 10.1 优化的概述 (2)复写传播 复写传播是在复写语句f := g后，尽可能用g代表f，目的是使某些变量的赋值变为无用 10.1 优化的概述 (3) 删除无用代码 无用代码是指计算的结果决不被引用的语句 一些优化变换可能会引起无用代码 10.1 优化的概述 (4)代码外提 代码外提是循环优化的一种 循环优化的其它重要技术 归纳变量删除 强度削弱 例：while (i = limit ? 2 ) … 变换成 t = limit ? 2; while (i = t ) … 10.1 优化的概述 (5) 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变量删除 过程来完成 对本例可以先做强度削弱 它给删除归纳变量创造机会 10.2 局 部 优 化 怎样为三地址语句序列生成目标代码？ begin |(1) prod := 0 prod := 0; |(2) i := 1 i := 1; |(3) t1 := 4* i do begin |(4) t2:= a[t1] prod := prod + a[i] * b[i];|(5 ) t3 := 4* i i := i +1 |(6 ) t4 := b[t3] end while i = 20 |(7 ) t5 := t2 * t4 end |(8 ) t6 := prod + t5 |(9 ) prod := t6 |(10) t7 := i +1 |(11) i := t7 |(12 ) if i = 20 goto (3) 10.2 局 部 优 化 10.2.1 基本块 基本块：连续的语句序列，控制流从它的开始进入，并从它的末尾离开 再用有向边表示基