石河子大学信息科学与技术学院编译原理课件第十一章 代码优化.ppt

如：语句 x := y ** 2 中的乘方运算，通常需要调用一个函数来实现。可以用代数上等价的形式，用简单的运算 x := y * y 替换。 对基本块中求值的表达式，用代数上等价的形式替换，以期使复杂运算变成简单运算。我们称这种变换为代数变换。 4. 代数变换 每个流图以基本块为结点。 如果一个结点的基本块的人口语句是程序的第一条语句，则称此结点为首结点。 通过构造一个有向图，称之为流图，我们可以将控制流的信息增加到基本块的集合上来表示一个程序。 1. 概念 2. 构造流图示例 (1) read X (2) read Y B1 (3) R := X mod Y (4) if R=0 goto(8) B2 (5) X := Y (6) Y := R (7) goto (3) B3 (8) write Y (9) halt B4 DAG (Directed Acyclic Graph)无环路有向图 一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG 1. 概念 1. 叶结点——值 3. 多标记共享 2.其他结点——运算 图的叶结点以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。 如果叶结点用来代表某变量A的地址，则用addr(A)作为该结点的标记 内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果 图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值 2. 构造基本块的DAG的算法 1. 叶结点生成 代码类型判断 3.查找、处理公共子表达式 单目运算（3（1））双目运算（3（2）） 2.常数参数与非常数参数的判断（2（1）单目、2（2）双目）合并已知量（2（3）单目、2（4）双目） 4.赋值号处理 3. 构造基本块的DAG的算法流程 初 始 化 生 成 B 0 1 生成C B是常数 2 B不是常数 寻找公共 子表达式 B、C都是常数 B或者C不是常数 合并已知量 生成新常数P 处理赋值号 处理A 合并已知量 生成新常数P 寻找公共 子表达式 n1 3.14 T0 T0 := 3.14 T1 := 2 * T0 T2 := R + r A := T1 * T2 B := A T3 := 2 * T0 T4 := R + r T5 := T3 * T4 T6 := R – r B := T5 * T6 文法G NODE(3.14)无定义，构造一个标记为3.14的结点 当前代码为0型，记NODE(3.14)的值为n1,转4 T0 := 3.14 NODE(T0)无定义，将T0附加在结点n1上 令NODE(T0) = n1，转处理下一条代码 T1 := 2 * T0 NODE(2)无定义，构造一个标记为2的结点 当前代码为2型，NODE(T0)已定义，转2（2） NODE(2) 和NODE(T0)均已定义，转2（4） 执行 2 * T0 ，新得到常数6.28 ,NODE(2) 是处理当前代码时新构造出来的，删除之，NODE(6.28)无定义，构造一个标记为6.28的结点n2，置NODE(6.28) = n2，转4 NODE(T1)无定义，将T1附加在结点n2上 令NODE(T1) = n2，转处理下一条代码 n2 2 T1 n2 6.28 T2 := R + r NODE(R)无定义，构造一个标记为R的结点n3，令NODE(R) = n3 当前代码为2型，NODE(r) 无定义， 构造一个标记为r的结点n4，令NODE(r) = n4，转2（2） n3 R n4 r NODE(R) 不是标记为常数的结点，转3（2） DAG中无结点其左后继为NODE(R) ，故构造一个结点n5， 其左后继为NODE(R)，右后继为 NODE(r)，转4 n5 + NODE(T2)无定义，将T2附加在结点n5上， 令NODE(T2) = n5，转处理下一条代码 T2 A := T1 * T2 NODE(T1)已定义，当前代码为2型， NODE(T2)已定义，转2（2） NODE(T1)不是标记为常数的结点，转3（2） DAG中无结点其左后继为NODE(T1)，故构造结点n6， 其左后继为NODE(T1)，右后继为NODE(T2)，转4 n6 * NODE(A)无定义，将A附加到结点n6上， 令NODE(A) = n6，转处理下一条代码 A B := A NODE(A)已定义，当前代码为0型，转4 NODE(B)无定义，将B附加到结点n6上， 令NODE(B) = n6，转处理下一条代码 T3 := 2 * T0 NODE(2)无定义，构造一个标记为2的结点n7， 令NODE(2) = n7 n7 2 当前代码为2型，