编译原理chapter9优化.ppt

中国科大 第十章 代 码 优 化 通过程序变换（局部变换和全局变换）来改进程序，称为优化 介绍独立于机器的优化，即不考虑任何目标机器性质的优化变换 流图中循环的识别 数据流分析 代码改进变换 10.1 引言 10.1.1 代码改进变换的标准 代码变换必须保程序的含义 采取安全稳妥的策略 变换减少程序的运行时间平均达到一个可度量的值 变换所作的努力是值得的 10.1 引言 10.1.2 性能的提高 优化可以在源程序阶段也可以在编译阶段进行。算法有优劣，有适用范围。源程序设计时算法的选择极需斟酌，需要在时间复杂性、空间复杂性上作出比较以决定对算法的取舍。例如对N个元素排序，插入排序需要2.02N2μs，而快速排序则为12Nlog2Nμs，当N=100时两者速度差2.5倍，而当N=100000时，速度差1000余倍。很明显，源程序阶段的优化不是编译程序能够和应该完成的。 10.1 引言 10.1.3 优化编译器的组织 实现高级结构的操作在中间代码中是显式的 中间代码基本上独立于目标机器 10.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 t3v goto (5) 10.2 优化的主要种类 本节所用的例子 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.2 优化的主要种类 10.2.1 局部优化 t6 := 4 * I x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 10.2.2 公共子表达式删除 如果表达式E先前已计算，并且从先前的计算到E的再次出现，E中变量的值没有改变，那么E的这个再次出现称为公共子表达式 10.2.2 公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.2.2 公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.2.2 公共子表达式删除 B5 x=a[i]; a[i]=a[j]; a[j]=x; 10.2.2 公共子表达式删除 10.2.3 复写传播 形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 10.2.3 复写传播 形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f := g后，尽可能用g代表f 10.2.3 复写传播 成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换的做法是在复写语句f := g后，尽可能用g代表f 复写传播变换本身并不是优化，但它给其它优化带来机会 常量合并 死代码删除 10.2.4 死代码删除 死代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例： debug := true; debug := false; . . . 测试后改成 . . . if (debug) print … if (debug) print … 10.2.4 死代码删除 代码是指计算的结果决不被引用的语句 一些优化变换可能会引起死代码 例：复写传播可能会引起死代码删除 10.2.5 循环优化 代码外提 归纳变