编译原理：第十章优化.ppt

(1) I:=1 (2‘) I:=3 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 考虑: B2 ?B3 ? B4 ? B2 ? B4 ? B5 I=3, J=3 (2‘) I:=3 (2) if XY goto B3 B1 B2 (3) I:=2 (4) X:=X+1 (5) Y:=Y-1 (6) if Y=20 goto B5 (7) J:=I B3 B4 B5 (1) I:=1 B2’ 考虑: B2 ?B3 ? B4 ? B2 ? B4 ? B5 I=2, J=2 代码外提条件: A在循环中其他地方未再定值,才能把循环不变运算A:=B op C外提; 考虑: X=0, Y=2 B2 ?B3 ? B4 ? B2 ? B4 ? B5 A=2, J=2 (1) I:=1 (2) if XY goto B3 B1 B2 (3) A:=I+1 (4) X:=X+1 (5) I:=2 (6) Y:=Y-1 (7) if Y=0 goto B5 (8) J:=A B3 B4 B5 (5) I:=2 (2) if XY goto B3 B1 B2 (3) A:=I+1 (4) X:=X+1 (6) Y:=Y-1 (7) if Y=20 goto B5 (8) J:=A B3 B4 B5 (1) I:=1 B2’ 考虑: X=0, Y=2 B2 ?B3 ? B4 ? B2 ? B4 ? B5 A=3, J=3 S(A:=B OP C)外提条件:循环中所有A的引用点只有S中的A的定值才能到达。 查找循环L的不变运算的算法： 依次查看L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在 L外，则将次四元式标记为不变运算; 重复第3步直至没有新的四元式被标记为不变运算为止; 依次查看尚未被标记为不变运算的四元式，如果它的每个运算对象或为常数，或定值点在L之外，或只有一个到达-定值点且该点上的四元式已被标记为不变运算，则把被查看的四元式标记为不变运算。 代码外提算法: 1. 求出L的所有不变运算 2. 对每个不变运算s:A:=B op C 或 A:=op B 或 A:=B检查是否满足条件(1)或(2) (1) (i) s所在的结点是L所有出口结点的必经结点; (ii) A在L中其他地方未再定值; (iii) L中所有A的引用点只有s中的A的定值才能到达。 (2) A在离开L后不再是活跃的，并且条件(1)的(ii)和(iii)成立。所谓A在离开L后不是活跃的是指，A在L的任何出口结点的后记结点入口处不是活跃的。 3.按步骤1所找出的不变运算的次序，依次把符合条件2的条件(1)或(2)的不变运算s外提到L的前置结点中。但是，如果s的运算对象(B或C)是在L中定值的，那么，只有当这些定值四元式都已外提到前置结点中时，才能把s也外提到前置结点中。 10.3.2 强度消弱 把程序中执行时间较长的运算转换为执行时间较短的运算。 (1) I:=1 (2) if I10 goto (15) (4) T2=10*I (5) T3= T2+ T1 (8) T6=10*I (9) T7= T6+ T5 (11) T9= T8[T7] (12) T4[T3]= T9+1 (13) I:=I+1 (14) goto B2 B3 B2 B1 (15) (3) T1=2*J (6) T4=addr(A)-11 (7) T5=2*J (10) T8=addr(A)-11 B2’ (1) I:=1 (2) if I10 goto (15) (5) T3= T2+ T1 (9) T7= T6+ T5 (11) T9= T8[T7] (12) T4[T3]= T9+1 (13) I:=I+1 (4‘) T2= T2 +10 (8’) T6= T6 +10 (14) goto B2 B3 B2 B1 (15) (3) T1=2*J (6) T4=addr(A)-11 (7) T5=2*J (10) T8=addr(A)-11 (4) T2=10*I (8) T6=10*I B2’ (1) I:=1 (2) if I10 goto (15) (5) T3= T2+ T1 (9) T7=