《编译第012章》由会员分享，可在线阅读，更多相关《编译第012章（60页珍藏版）》请在金锄头文库上搜索。
1、第十二章 代码优化和 目标代码生成,一. 优化的定义优化是一种等价的，有效的程序变换 等价不改变程序运行结果 有效时空效率要高,1. 源程序阶段的优化考虑DS和算法2. 编译优化中间代码和目标代码优化,二. 不同阶段的优化,中间代码优化局部优化和全局优化,局部优化：在基本块内的优化 全局优化：超越基本块，基本块之间的优化,一. 划分基本块和构造程序流图1. 划分基本块(1)寻找入口语句 程序的第一条语句 由转向语句转移到的语句 紧跟在条件转向语句后的那个语句,第一节 局部优化,(2)确定基本块入口语句 入口语句,入口语句转向语句,入口语句停语句,(3)删除未被划入基本块的语句,思考,基本块的特
2、点？,(1)i:=m-1 (2)j:=n (3)t1:=4*n (4)v:=at1 (5)i:=i+1 (6)t2:=4*i (7)t3:=at2 (8)if t3v goto (9) (13)if i=j goto (23) (14)t6:=4*i (15)x:=at6,(16)t7:=4*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5) (23)t11:=4*i (24)x:=at11 (25)t12:=4*i (26)t13:=4*n (27)t14:=at13 (28)at12:=t1
3、4 (29)t15:=4*n (30)at15:=x (31)HALT or STOP,2. 构造流图 G = ( N , E , n0) (1)基本块集即为结点集N; (2)包含程序第一个语句的基本块为首结点n0;,(3)设Bi , Bj N ，若满足下列条件之一，则Bi Bj Bj 紧跟在Bi 之后，且Bi 的出口语句不是无条件转向或停止语句 Bi 的出口语句为转向语句，其转向点恰为Bj 的入口语句,(1)i:=m-1 (2)j:=n (3)t1:=4*n (4)v:=at1,(5)i:=i+1 (6)t2:=4*i (7)t3:=at2 (8)if t3v goto (9),(13)if
4、 i=j goto (23),(14)t6:=4*i (15)x:=at6 (16)t7:=4*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5),(23)t11:=4*i (24)x:=at11 (25)t12:=4*i (26)t13:=4*n (27)t14:=at13 (28)at12:=t14 (29)t15:=4*n (30)at15:=x,B1,B2,B3,B4,B5,B6,= n0,二. 基本块内的优化 1. 合并已知量 2. 删除公共子表达式 3. 删除无用赋值 4. 删除死代
5、码,合并己知量,对于语句A:=op B 或 A:=B op C 若B及C为常数，则编译时将它们计算出来，存放在临时单元T中，相应的语句换成 A:=T,删除公共子表达式,实际上就是删除多余运算。 例如ti:=C*D 和 tj :=C*D 若在计算tj之前，C和D未重新赋值，则第2个赋值语句改为tj := ti 或 对tj的使用就是ti,删除无用赋值,若有四元式 （p）A:=B+C （q）A:=M+N 在（p）和（q）之间，没有引用过A，则（p）对A的赋值应当删除。,删除死代码,若某个基本块实际不可能被执行该基本块为死代码可以删除。,(14)t6:=4*i (15)x:=at6 (16)t7:=4
6、*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5),(14)t6:=4*i (15)x:=at6 (17)t8:=4*j (18)t9:=at8 (19)at6:=t9 (21)at8:=x (22)goto (5),优化后,例1,T0 : = 3.14 T1 : = 2 * T0 T2 : = R + rA : = T1 * T2B : = A T3 : = 2 * T0 T4 : = R + r T5 : = T3 * T4 T6 : = R rB : = T5 * T6,T2 : = R
7、 + r A : = 6.28 * T2 T6 : = R rB : = A * T6,优化后,例2,要进行全局优化，必须对程序的数据流进行分析，这是比较复杂的。只讨论对循环进行的优化。 循环优化对提高目标代码的有效性特别有意义。 循环：程序中重复执行的代码序列,第二节 全局优化,容易找出循环语句构成的循环。 但由条件转移和无条件转移语句构成的循环其结构要复杂些。 为了找出循环，必须对程序中的控制流进行分析。 控制流分析也是程序中数据流分析的基础，它是优化的重要工具。,一. 循环的定义程序流图中, 有唯一入口结点的强连通子图。,(1)入口结点 子图中满足下列条件的结点n: 或者n是流图的首结点
8、或者在子图外有结点m有边mn引向结点n;,(2)强连通子图,所谓强连通是指任意两个结点之间必有一条通路（即子图中任何两个结点m和n可相互到达） 而且该通路上的各结点都属于该结点序列。 如果序列只包含一个结点，则必有一有向边从该结点引向它自身。,1,2,4,3,5,6,9,10,7,8,5,6,7,8,9 是一循环 4, 不是循环 , 不是循环,例:,1. 必经结点从流图的首结点出发，到达结点n的任一通路都必须经过的结点d，称为n的必经结点记为d DOM n,二. 循环的查找,根据定义可知: 每个结点是它本身的必经结点，即n DOM n 首结点是任一结点的必经结点，即n0 DOM n,D(1)=
9、1 D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,5,6D(7)=1,2,4,5,6,7D(8)=1,2,4,5,6,8D(9)=1,2,4,5,6,9D(10)=1,2,4,10,各结点的必经结点集,2. 回边流图G=(N，E，n0)中的有向边nd如果d是n的必经结点,则称nd为流图的一条回边。,有三条回边 54 95 102,1,2,3,4,5,6,7,8,9,10,若nd是G=(N,E, n0)的一条回边，M是流图中有通路到达n而该通路不经过d的结点集,则Loop= n, dM 组成了G的一个子图 称为由回边nd组成的自然循环。,3
10、. 由回边组成的循环,54 组成5, 4, 6, 7, 8, 9 95 组成9, 5, 6, 7, 8 102 组成10, 2, 3, 4, 5, 6, 7, 8, 9,1. 代码外提 2. 强度削弱 3.变换循环控制条件，复写传播，合并已知量 4删除归纳变量,三. 循环优化(自学),基本归纳变量，i有唯一定值，i := i c 同族归纳变量，j := c1 i c2则变成j := j c1 c , 但j必须在循环外赋初值 j : c1 * i c2,3. 删除归纳变量 即改用同族归纳变量作为判断条件 例如将 i 10 改为 t3 100 + t1 因原来t3 := 10 * i + t1 ，
11、而100 t1 即 10 * 10 + t1,(1)i:=1,(2)if i10 goto (16),(3)t1:=2*j (4)t2:=10*i (5)t3:=t2+t1 (6)t4:=a0-11 (7)t5:=2*j (8)t6:=10*i (9)t7:=t6+t5 (10)t8:=a0-11 (11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (15)goto (2),(16) .,优化之前,B1,B2,B3,B4,(1)i:=1,(4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5 (11
12、)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (15)goto (2),(16) .,(2)if i10 goto (16),(3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11,代码外提后,B1,B2,B2,B3,B4,(1)i:=1,(11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (4)t2:=t2+10 (8)t6:=t6+10 (5)t3:=t3+10 (9)t7:=t7+10 (15)goto (2),(16) .,(2)if i10
13、 goto (16),(3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5,强度削弱后,B1,B2,B2,B3,B4,(1)i:=1,(11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (4)t2:=t2+10 (8)t6:=t6+10 (5)t3:=t3+10 (9)t7:=t7+10 (15)goto (2),(16) .,(2)if t3s goto (16),(3)t1:=2*j (6)t4:=a0-11 (7)t
14、5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5 (2)s:=100+t1,删除归纳变量后,B1,B2,B2,B3,B4,另例：(1)PROD := 0(2)I := 1(3)T1 := 4 * I(4)T2 := a0 4(5)T3 := T2T1(6)T4 := 4 * I(7)T5 := b0 4(8)T6 := T5T4(9)T7 := T3 * T6(10)PROD := PROD + T7(11)I := I + 1(12)if I 20 goto (3),删除多余运算，代码外提(1)PROD := 0(2)I := 1(4)T2 := a0 4(7) T5 := b0 4(3) T1 := 4 * I(5)T3 := T2T1(6)T4 := T1(8) T6 := T5T4(9) T7 := T3 * T6(10) PROD := PROD + T7(11) I := I +1(12)if I20 goto (3),
