2.构造流图 G=(n,E, no (1)基本块集即为结点集N; (2)含程序第一个语句的基本块为首结点n (3)设Bi,Bj∈N,若满足下列条件之一, 则Bi→>Bj Bj紧跟在Bi之后,且Bi的出口语句不是 无条件转向或停止语句 ●Bi的出口语句为转向语句,其转向点恰为 Bj的入口语句
2. 构造流图 G = ( N , E , n0 ) (1)基本块集即为结点集N; (2)含程序第一个语句的基本块为首结点n0 ; (3)设Bi , Bj ∈ N ，若满足下列条件之一， 则Bi →Bj •Bj 紧跟在Bi 之后，且Bi 的出口语句不是 无条件转向或停止语句 •Bi 的出口语句为转向语句，其转向点恰为 Bj 的入口语句
():=m1(2):=n BI (3)t1:=4*n(4)v:atl (5)i:=i+1(6t2:=4* B2 7)t3:=a[t2](8)if3< v goto(5 (9):1(10)t4:=4 B3 (11)t5: = a[t4(12)if t5>v goto(9 (13)if i>=j goto(23) B4 B6 (14)6=4*i(15x=t61B5 (16)t7:=4*1(17)t8:=4 (23)t1:=4*i(24)x:=a[tll (18)9 (19)a[t7=t9 (25)t12=4*1(26t13:=4*n (20t10=4*(21)a[t10]=x (27)t14:=at13](28atl2]=t14 (22)goto(5) (29)t15:=4*n(30at15]=x
(1)i:=m-1 (2)j:=n (3)t1:=4*n (4)v:=a[t1] (5)i:=i+1 (6)t2:=4*i (7)t3:=a[t2] (8)if t3<v goto (5) (9)j:=j-1 (10)t4:=4*j (11)t5:=a[t4] (12)if t5>v goto (9) (13)if i>=j goto (23) (14)t6:=4*i (15)x:=a[t6] (16)t7:=4*i (17)t8:=4*j (18)t9:=a[t8] (19)a[t7]:=t9 (20)t10:=4*j (21)a[t10]:=x (22)goto (5) (23)t11:=4*i (24)x:=a[t11] (25)t12:=4*i (26)t13:=4*n (27)t14:=a[t13] (28)a[t12]:=t14 (29)t15:=4*n (30)a[t15]:=x B1 B2 B3 B4 B5 B6
四.局部优化 1.合并已知量 2.删除公共子表达式 3.删除死代码 (a)if的条件为定值: (b)定值后不引用或仅是A:=A±C 的递归赋值
四. 局部优化 1. 合并已知量 2. 删除公共子表达式 3. 删除死代码 （a）if 的条件为定值; （b）定值后不引用或仅是 A: = A±C 的递归赋值
之例1 (14)t6:=4*1 15)X:=a[t6 (14)t6:=4*1 (16)t7:=4*1 15)x:=al[6 (17)t8:=4*j (17)t8:=4*j (18)9:=a[t8] 优化后 (18)9:=a[t8] (19)at=9 19)at6]:=t9 (20)t10:=4*1 (21)at8]:=x (2 1)a[t10:=X (22)goto(5 (22)goto(5)
(14)t6:=4*i (15)x:=a[t6] (16)t7:=4*i (17)t8:=4*j (18)t9:=a[t8] (19)a[t7]:=t9 (20)t10:=4*j (21)a[t10]:=x (22)goto (5) (14)t6:=4*i (15)x:=a[t6] (17)t8:=4*j (18)t9:=a[t8] (19)a[t6]:=t9 (21)a[t8]:=x (22)goto (5) 优化后 例 1
例2 To:=3.14 2 =R+r A:=T1* S,,=R+r B:=A 优化后 A:=6.28*S1 2 0 R-r =R+r B:=A*S2 R B: =Ts*T 5 6
T 0 : = 3.14 T 1 : = 2 * T 0 T 2 : = R + r A : = T 1 * T 2 B : = A T3 : = 2 * T 0 T 4 : = R + r T 5 : = T 3 * T 4 T 6 : = R － r B : = T 5 * T 6 S 1 : = R + r A : = 6.28 * S 1 S 2 : = R － r B : = A * S 2 优化后 例 2