Part12-代码优化.ppt.ppt

编译技术 代码优化 授课：胡静 * 编译技术 * 编译器的结构 出 错 处 理 语法分析程序 语义分析程序 目标代码生成程序 词法分析程序 中间代码生成程序 代码优化程序 表 格 管 理 * 编译技术 * 概述 代码优化（code optimization） 指编译程序为了生成高质量的目标程序而做的各种加工和处理 目的：提高目标代码运行效率 时间效率（减少运行时间） 空间效率（减少内存容量） 原则：进行优化必须严格遵循“不能改变原有程序语义”原则。 * 编译技术 * 代码优化分类 从优化的层次，与机器是否有关，分为： 独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进行的优化。 与机器有关的优化：充分利用系统资源。（指令系统个，寄存器资源）。 从优化涉及的范围，分为： 局部优化：是指在基本块内进行的优化。 循环优化：对循环语句所生成的中间代码序列上所进行的优化。 全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是指在非线性程序段上（包括多个基本块，GOTO，循环）的优化。需要进行全局控制流和数据流分析，复杂。 * 编译技术 * 优化所花费的代价和产生效果图 局部优化：只要做一些简单的处理便能得到明显的优化效果 循环优化：若要进一步提高优化效果，就要逐步付出更大的代价 全局优化：付出很大 代价，但是优化效果 不会非常明显 * 编译技术 * 为什么要优化 有的大型计算程序一运行要花上几十分钟，甚至好几个小时，这时为优化即使付出些代价也是值得的 另外，程序中的循环往往要占用大量的计算时间。所以为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义——尤其对有实时要求的程序。如市场决策，供需及求益的平衡 至于简单的小程序（例如作业），或者在程序的调试阶段，花费许多代价去进行一遍一遍的优化就毫无必要了。 * 编译技术 * 优化的基本方法(1) 优化应该是针对中间代码或者目标代码进行的，但此处为了说明方便，举例均为源程序的形式。 基本方法1：利用代数性质（代数变换） 编译时完成常量表达式的计算，整数类型与实数类型的转换 a:=5+6+x → a:=11+x 设x为实型，x:=3+1可变换成x:=4.0 下标变量引用时，其地址计算的一部分工作可以在编译时预先做好（运行时只需计算“可变部分”即可） * 编译技术 * 优化的基本方法(2) 基本方法1：利用代数性质（代数变换） 运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度，以及时空开销） x^2 → x*x 3*x → x+x+x 8*x, 4*x等换成左移运算 x/2，x/16等换成右移运算 x:=x+1 → INC x x/5 → x*0.2 机器硬件提供的一些功能。 或者是和选择的指令集相关的功能。 * 编译技术 * 优化的基本方法(3) 基本方法2：复写传播（copy） 复写语句：如x:=y这样的赋值语句称为复写语句。由于x和y值相同，所以当满足一定条件时，在该赋值语句下面出现的x可用y来代替，这就是复写传播。 例如 经过优化后，如果以后的语句中不再使用x，则x:=y可以删掉 * 编译技术 * 优化的基本方法(4) 基本方法2：复写传播（copy） 如果上例中不是x:=y，而是x:=3，则复写传播变成了常量传播 常量传播会引起常量计算： * 编译技术 * 优化的基本方法(5) 基本方法3：删除公共子表达式 具有相同值的子表达式在两个以上地方出现时，称它为共子表达式(common sub-expression) 可用DAG（directed acyclic graph,有向无循环图）来表示具有公共子表达式的抽象语法树。 对公共子表达式只需要计算一次即可 * 编译技术 * 优化的基本方法(6) 基本方法4：删除冗余代码 冗余代码就是毫无实际意义的代码，又称死代码(dead code)或无用代码(useless code)。 * 编译技术 * 循环优化（1） 经验规则告诉我们：“程序运行时间的80%是由仅占源程序20%的部分执行的”。这20%的源程序就是循环部分，特别是多重循环的最内层的循环部分。因为减少循环部分的目标代码对提高整个程序的时间效率有很大作用。 * 编译技术 * 循环优化（1） 经验规则告诉我们：“程序运行时间的80%是由仅占源程序20%的部分执行的”。这20%的源程序就是循环部分，特别是多重循环的最内层的循环部分。因为减少循环部分的目标代码对提高整个程序的时间效率有很大作用。 * 编译技术 * 循环优化（2） 循环不变式的代码外提 不变表达式：不随循环控制变量改变而改变的表达式或子表达式。 * 编译技术 * 循环优化（3） 循环不变式的代码外提 不变表达式：不随循环控制变量