编译原理（骆婷）代码优化.ppt

7.1 优化概述 根据划分基本块的算法可以确定四元式(1)(4)(6)(8)是入口语句; (3)(5)(7)(9)是出口语句，因此分为四个基本块 （1）read C （2）A=0 （3）B=1 （4）L1: A=A+B （5）if B≥C goto L2 （6） B=B+1 （7） goto L1 （8）L2: write A （9）halt 7.2.1 划分基本块的方法 利用DAG实现局部优化的思想： 首先对一个基本块构造一个DAG，然后按构造结点的次序将DAG还原成四元式序列。 7.2.2 基本块的DAG表示 DAG ( 无环路有向图 ) n1 n4 n6 n2 n3 n5 n7 n8 n9 7.2.2 基本块的DAG表示 结点带有标记的DAG： n1 B n1 3.1416 n1 Addr(A) n3 T1,T2 n1 B n2 C OP 7.2.2 基本块的DAG表示 基本块的DAG表式： (1) A=B n1 A B (2) A= op B n2 B n1 A OP (3) A=B op C n1 B n2 C n3 A op (4) A=B[C] n1 B n2 C n3 A =[ ] 四元式与DAG 7.2.2 基本块的DAG表示 (5) if B rop C goto(S) n1 B n2 C n3 (S) rop (6) D[C]=B n1 n2 n3 D C B (7) Goto (S) n1 (S) 四元式与DAG n4 =[ ] 7.2.2 基本块的DAG表示 例 构造以下基本块的DAG： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 n1 T0 3.14 n1 T0 3.14 n2 T1 6.28 n3 R n4 r n5 T2 + 7.2.3 利用DAG实现局部优化 对四元式(4) A=T1*T2 有： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 n1 T0 3.14 n2 T1 6.28 n3 R n4 r n5 T2 + n6 A * 7.2.3 利用DAG实现局部优化 对四元式(5) B=A 有： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 n1 T0 3.14 n2 T1 6.28 n3 R n4 r n5 T2 + n6 A, * B 7.2.3 利用DAG实现局部优化 对四元式(6) T3=2*T0 有： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 n1 T0 3.14 n2 T1, 6.28 n3 R n4 r n5 T2 + n6 A, * B T3 7.2.3 利用DAG实现局部优化 对四元式(7) T4=R+r 有： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 T4 n1 T0 3.14 n2 T1, 6.28 n3 R n4 r n5 T2, + n6 A, * B, T3 7.2.3 利用DAG实现局部优化 对四元式(8) T5=T3*T4 有： (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6) T3=2*T0 (7) T4=R+r (8) T5=T3*T4 (9) T6=R-r (10)B=T5*T6 n1 T0 3.14 n2 T1, 6.28 n3 R n4 r n5 T2, + n6 A, * B, T3 T4 T5 7.2.3 利用DAG实现局部优化 对四元式(9) T6=R- r中 (1) T0=3.14 (2) T1=2*T0 (3) T2=R+r (4) A=T1*T2 (5) B=A (6)