第十节代码优化,哈工大王宏志.ppt

第十章 代码优化 优化的概念 编译时刻为改进目标程序的质量而进行的各项工作。 空间效率 时间效率 空间效率和时间效率有时是一对矛盾，有时不能兼顾。 优化的要求： 必须是等价变换 为优化的努力必须是值得的。 有时优化后的代码的效率反而会下降。 优化的分类 机器相关性： 机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。 无关的优化： 优化范围： 局部优化：单个基本块范围内的优化，常量合并优化，公共子表达式删除，计算强度削弱和无用代码删除。 全局优化：主要是基于循环的优化：循环不变优化，归纳变量删除，计算强度削减。 优化语言级： 优化语言级：针对中间代码，针对机器语言。 代码优化程序的结构 控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。 数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。 到达-定义分析；活跃变量；可用表达式； 代码变换：根据上面的分析，对内部中间代码进行等价变换。 基本块和流图 基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。 流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n’当且仅当控制流可能从n的最后的一个四元式到达n’的第一个四元式。 首节点：对应的基本块的第一个四元式是程序的第一个四元式。 流图的构造 以所有的基本块为节点集合。 有B1到B2的边（B2是B1的后继）当且仅当： B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。 B2是紧紧跟随在B1后面的四元式，且B1的最后四元式不是无条件转向语句。 流图的例子 在转移语句中，目标标号转变称为基本块的编号，可以避免因为四元式的变动而引起的麻烦。 基本块的优化 常量合并 公共子表达式删除 强度削弱 无用代码删除 常量合并 例子：l = 2*3.14*r * 2 3.14 t1 * t1 r t2 = t2 l 2*3.1415926的值在编译时刻就可以确定。 * 6.28 r t2 = t2 l 公共子表达式删除 + b c a - a d b + b c c - a d d 显然，第2和4个四元式计算的是同一个值，所以第四个四元式可以修改为 = b _ d。 对于第1和3个四元式，虽然都是计算b+c，但是他们的值其实是不同的，所以不能完成处理。 公共子表达式：如果某个表达式先前已经计算，且从上次计算到现在，E中的变量的值没有改变。那么E的这次出现就称为公共子表达式。 利用先前的计算结果，可以避免对公共子表达式的重复计算。 例子 x+y*t-a*(x+y*t)/(y*t) * y t t1 + x t1 t2 * y t t3 + x t3 t4 * a t4 t5 * y t t6 / t5 t1 t7 - t2 t7 t8 消除公共子表达式之后： * y t t1 + x t1 t2 * a t2 t5 / t5 t1 t7 - t2 t7 t8 强度削弱 实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。 X2 变成 x*x。 2*x或2.0*x 变成 x+x x/2 变成 x*0.5 anxn+an-1xn-1+…+a1x+a0变成 ((…(anx+an-1)x+ an-2)…)x+a1)x+a0 无用代码删除 如果四元式op x y z之后，z的值再也没有被使用到，那么这个四元式是无用的。 无用的四元式往往意味着程序的错误，一般不会出现在正确的程序里面。 多数无用四元式是由优化引起的。 = t1 t3，如果我们尽量用t1替代t3，可能使t3不被使用，从而这个四元式称为无用的四元式。 等价变换的分类 保结构等价变换 删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。 + x y t变成+ x y u + a b t1 + x y t2变成 + x y t2 + a b t1 代数等价变换利用了代数恒等性质， 强度削弱。2x=x+x, B and true = B. 需要考虑双目运算符的可交换特性。 基本块优化的实现 基本块内部优化的实现的主要工具为DAG图。 用DAG图表示各个值的计算/依赖关系。 图中的标记： 叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标0表示它时初值。 内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。 DAG图的例子 + b c a - a d b + b c c - a d d 四元式的分类 0型： = x _ y 1型： op x _ y(单目运算） 2型： op x