第三节代码优化 优化的定义 优化是一种等价的,有效的程序变换 等价—不改变程序运行结果 有效时空效率要高
第三节 代码优化 一. 优化的定义 优化是一种等价的，有效的程序变换 等价——不改变程序运行结果 有效——时空效率要高
不同阶段的优化 1.源程序阶段的优化:考虑DS和算法 2.编译优化—一中间代码优化和目标代码 优化 3.中间代码优化—局部优化和全局优化 局部优化:在基本块内的优化 全局优化:超越基本块,在基本块之间的优 化
二. 不同阶段的优化 1. 源程序阶段的优化：考虑DS和算法 2. 编译优化——中间代码优化和目标代码 优化 3. 中间代码优化——局部优化和全局优化 局部优化：在基本块内的优化 全局优化：超越基本块，在基本块之间的优 化
三.划分基本块和构造程序流图 1.划分基本块 (1)找入口语句 程序的第一条语句 能由条件或无条件转向语句转移到的语 紧跟在条件转向语句后的那个语句
三. 划分基本块和构造程序流图 1. 划分基本块 (1)找入口语句 程序的第一条语句 能由条件或无条件转向语句转移到的语 句 紧跟在条件转向语句后的那个语句
(2)确定基本块 入口语句入口语句入口语句 入口语句(转向语句停语句 (3)删除未被划入基本块的语句
(2)确定基本块 入口语句 入口语句 入口语句 …… …… …… 入口语句 转向语句 停语句 (3)删除未被划入基本块的语句
→(1)i:=m-1 于(16)t7:=4*1 (2):=n (17)t8:=4 3)t1:=4*n 18)t9:=al[t8 (4)v: =at1 (19)a[t7]:=t9 (5)i:=i+1 (20t10:=4*1 6)t2:=4*i 21atl0]:=x (7)t3:=a[2 22)oto(5) (8)if t3v goto(9) (27)tl4:=al[t13] 13)if i>=j goto(23) (28)a[t12]:=t14 (14)t6:=4* (29)t15=4*n 15)X:=a[t6 (30)atl5]:=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 t3v 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
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)if3v 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 t3v 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