例子 x+y*t-a*(x+y*t /y*t) t1 t1 t3 t3 t4 a t4 t5 / t5 t1 t7 2t7t8 消除公共子表达式之后 + X t2 t5 /55 t1 t7 t2 t t8
例子 • 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
削减计算强度 实现同样的运算可以有多种方式。用计算 较快的运算代替较慢的运算 变成 2*x或20*x变成 变成 x米0.5 anx+an1x1+…+a1x+a0变成 (….(anx+an1)x+an2)…)x+a1)x+ao
削减计算强度 • 实现同样的运算可以有多种方式。用计算 较快的运算代替较慢的运算。 • X2 变成 x*x。 • 2*x或2.0*x 变成 x+x • x/2 变成 x*0.5 • anx n+an-1x n-1+…+a1x+a0变成 – ((…(anx+an-1 )x+ an-2 )…)x+a1 )x+a0
删除无用代码 如果四元式 op x y Z之后,z的值 再也没有被使用到,那么这个四元式是无 用的。 ·无用的四元式往往意味着程序的错误, 般不会出现再正确的程序里面。 多数无用四元式是由优化引起的 t3,如果我们尽量用t1替代t3, 可能使t3不被使用,从而这个四元式称为无 用的四元式
删除无用代码 • 如果四元式op x y z之后，z的值 再也没有被使用到，那么这个四元式是无 用的。 • 无用的四元式往往意味着程序的错误，一 般不会出现再正确的程序里面。 • 多数无用四元式是由优化引起的。 • = t1 t3，如果我们尽量用t1替代t3， 可能使t3不被使用，从而这个四元式称为无 用的四元式
等价变换的分类 保结构等价变换 删除公共子表达式和删除无用代码,重新命名临 时变量和交换独立四元式的顺序等 ++ t变成+ xax yby Xyt2变成 t2 代数等价变换利用了代数恒等性质, 削减计算强度。2x=x+x, B and true=B 需要考虑双目运算符的可交换特性
等价变换的分类 • 保结构等价变换 – 删除公共子表达式和删除无用代码，重新命名临 时变量和交换独立四元式的顺序等。 – + 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图。 • 用DAG图表示各个值的计算/依赖关系。 • 图中的标记： – 叶子节点的标记为标识符（变量名）或常数作为唯 一的标记。叶子节点是标识符时，用下标0表示它 时初值。 – 内部节点用运算符号作为标记，表示计算的值。每 个节点的值都可以用关于变量初始值的表达式表示。 – 各节点可能附加有一个或者多个标识符。同一个节 点的标识符表示相同的值