编译原理：第九章 代码优化

1、第九章 代 码 优 化通过程序变换（局部变换和全局变换）来改进程序，称为优化介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换流图中循环的识别数据流分析代码改进变换9.1 优化的主要种类9.1.1 代码改进变换的标准代码变换必须保程序的含义采取安全稳妥的策略变换减少程序的运行时间平均达到一个可度量的值变换所作的努力是值得的9.1 优化的主要种类本节所用的例子i = m 1; j = n; v = an;(1) i := m 1while (1) (2) j := n do i = i +1; while(aiv);(4) v := at1 if (i = j) break;(5) i :

2、= 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)9.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 goto (23) x=ai; ai=aj; aj=x;(14) t6 := 4 * i(15 )

3、x := at6x=ai; ai=an; an=x;. . .9.1 优化的主要种类i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 优化的主要种类9.1.2 公共子表达式删除B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B29.1 优化的主要种类B5 x=ai; ai

4、=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B29.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B29.1 优化的主要种类i := m 1

5、j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B69.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B29.1 优化的主要种类B5 x=ai; ai=

6、aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B29.1 优化的主要种类i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j g

7、oto B6B4B3B5B69.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B29.1 优化的主要种类B5 x=ai; ai=aj; aj=x;t6 := 4 * ix := at6t7 := 4 * i

8、 t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2x := at2t9 := at4at2 := t9at4 := xgoto B2x := t3at2 := t5at4 := xgoto B29.1 优化的主要种类B6 x = ai; ai = an; an = x;t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t

9、15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 9.1 优化的主要种类B6 x = ai; ai = an; an = x;at1能否作为公共子表达式？t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t15 := 4 * n at15 := x x := t3t14 := at1at2 := t14at1 := x 9.1 优化的主要种类i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 *

10、 it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6把at1作为公共子表达式是不稳妥的 9.1 优化的主要种类9.1.3 复写传播形成为f := g的赋值叫做复写语句优化过程中会大量引入复写t := d + ea := t 删除局部公共子表达式期间引进复写t := d + eb := tc := tc := d + eb := d + ea := d + e9.1 优化的主要种类9.1.3 复写传播形成为f := g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f := g后，尽可能用g代表fx := t3at2 :=

11、t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B29.1 优化的主要种类9.1.3 复写传播形成为f := g的赋值叫做复写语句优化过程中会大量引入复写复写传播变换的做法是在复写语句f := g后，尽可能用g代表f复写传播变换本身并不是优化，但它给其它优化带来机会常量合并死代码删除9.1 优化的主要种类9.1.4 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：debug := true; debug := false;. . . 测试后改成 . . .if (debug) print if (debug) prin

12、t 9.1 优化的主要种类9.1.4 死代码删除死代码是指计算的结果决不被引用的语句一些优化变换可能会引起死代码例：复写传播可能会引起死代码删除x := t3at2 := t5at4 := t3goto B2at2 := t5at4 := t3goto B29.1 优化的主要种类9.1.5 代码外提代码外提是循环优化的一种循环优化的其它重要技术归纳变量删除强度削弱例：while (i = limit 2 ) 变换成t = limit 2;while (i v goto B3B39.1 优化的主要种类i := m 1j := nt1 := 4 * nv := at1B1B2j := j 1t4 := t4 4t5 := at4if t5 v goto B3B4B3B5B6t4 := 4 * jif i = j goto B6j := j 1t4 := 4 * jt5 := at4if t5 v goto B3B3除第一次外，t4 = 4 * j在B3的入口一定保持在j := j 1后，关系t4 = 4 * j + 4也保持9.1 优化的主要种类i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B3if i = j goto B6B4B3B5B6B2也可以进行