编译 第五章 中间代码优化.ppt

* 首先定义四个基本集合: IN[B] : 代表到达基本块 B 入口点时的各变量的所有定值点集; OUT[B]:代表到达基本块 B 出口点时的各变量的所有定值点集; GEN[B]:表示 B 中所定值的且到达 B 之后的定值点集; KILL[B]: 表示属于 B 外的定值点,而这些定值点所定值的变量在 B中又被重新定值 这几个集合满足如下方程: OUT[B]=(IN[B] - KILL(B)) ∪ GEN[B] IN[B] = OUT[p1] ∪ OUT[p2] ∪...... ∪ OUT[pk] p1 , p2...... pk 为B的前趋结点. 该方程即为到达------定值方程,求解该方程,得到IN[B] . * 2求 ud[ A] 算法如下: 若 B 中,变量 A 的引用点 u 之前有 A 的定值点 d,且到达 u ,则 ud[ A] = { d }; 否则 ud[ A] = { di | di ∈IN[B] 且 di为A的定值点}. 这样,可以求出每个变量在引用点 u 的定值状况. * 四 循环的几种基本优化 下面介绍三种循环优化: 代码外提,强度削弱,删除归纳变量. 一 代码外提 定义: 对于循环中的语句 A:= B op C, 若 B 及 C 均为常量,或者 为 循环中未改变的变量, 那么每次循环 A的值都一样,称A:= B op C 为不变运算. 对于不变运算,有可能把 A:= B op C 放到循环前,具体做法是: a) 建立一前置结点; b) 循环入口结点(唯一的) 为前置结点的唯一后继; c) 循环外流向入口结点的有向边,改为流向前置结点; d) 把循环中可以外提的不变运算放在前置结点中. 见下图: * 循环入口结点 循环外流向前置结点 前置结点 循环入口结点 下面讨论两个问题: (1)哪些是循环中的不变运算? (2) 循环中的哪些不变运算可以放到前置结点中? 循环外流向入口结点 循环内结点 循环内结点 改为 * 1 不变运算的确定算法 (1) 察看循环中的每条四元式,若每个运算对象或为常量,或定 值点在循环外的变量,则标记为不变运算; (2) 察看尚未标记为不变运算的四元式,若每个运算对象或为 常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变 量且该定值点已经标记为不变运算,则标记为不变运算; (3)重复 (2),直到不产生新的不变运算. * (1) PROD:=0 (2) I:=1 (3) T1:=4*I (4) T2:=addr(A)-4 (5) T3:=T2[T1] (6) T4:=4*I (7) T5:=addr(B)-4 (8) T6:=T5[T4] (9) T7:=T3*T6 (10)T8=T5*10 (11) PROD:=PROD+T7 (12) I:= I+1 (13) if I=20 goto(3) * 2 代码外提算法 (1) 对循环中每一不变运算 (S) A:=B op C (包括 A:= op C 或 A:=B), 检查是否满足如下条件之一 : a) S所在的结点是循环所有出口结点的必经结点, 且 S为变量A 在循环中唯一 定值点, 且 A 的定值点 S 能到达循环中所有 A 的引用点; b) S为 变量 A 在循环中唯一 定值点, 且 A 的定值点 S 能到达循环中所有 A 的引用点, 且 A 在循环之后不再引用. (2) 把循环中满足条件 a) 或 b) 的不变运算移至前置结点中, 若运算对象 B 或 C 是在循环中定值, 则只有当 B 或 C 的 定值点四元式已放入前置结点中后,才可以把 S 外提. * * 二 强度削弱 强度削弱是指循环中,把执行时间较长的运算转换为执行时 间较短的运算. 下面仅讨论乘法运算转换为加法运算. ( 注:并非每个乘运算都可以进行强度削弱) 定义: 若循环中对 B 只有唯一的递归赋值 B:=B+C 且 C 为循环不 变量,则称 B 为循环的基本归纳变量. 定义: 若 B 为基本归纳变量,而 A 在循环中的定值,可以化归为 B 的线性函数: A:=C1*B+C2 (C1 , C2为循环不变量 ) 则称