《编译原理 第十章》由会员分享，可在线阅读，更多相关《编译原理 第十章（72页珍藏版）》请在金锄头文库上搜索。
1、第十章 优化l优优化：对对程序进进行各种等价变换变换，使得从变变 换换后的程序出发发，能生成更有效的目标标代码码 。等价：指不改变变程序的运行结结果。有效：指目标标代码码运行时间时间短，占用的 存储储空间间小。编译前端代码优化器编译后端控制流分析数据流分析代码变换10.1 概述l优优化的目的是为为了产产生更高效的代码码。由 优优化编译编译程序提供的对对代码码的各种变换变换必 须须遵循一定的原则则：等价原则则：经过优经过优化后不应应改变变程序 运行的结结果；有效原则则：使优优化后所产产生的目标标代 码码运行时间较时间较短，占用的存储储空间较间较小；合算原则则：应应尽可能以较较低的代价取 得较较好
2、的优优化效果。10.1 概述l优优化的种类类：删删除多余运算(或称删删除公用子表达 式)代码码外提强度消弱变换变换循环环控制条件合并已知量复写传传播删删除无用赋值赋值l优优化的三个不同级别级别：局部优优化循环优环优化全局优优化void quicksort (m, n); int m, n; int i, j; int v, x; if (nv); if (i=j) break; x=a i; ai=a j; aj=x;x=ai; ai=a n; a n=x;/*fragment ends here*/quicksort (m, j); quicksort (i+1, n); q中间代码程序段
3、i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:=4*i x:=a T6 T7:=4*i T8:=4*j T9:=a T8 a T7=T9 T10:= 4*j a T10=x goto B2B5T11:=4*i x:=a T11 T12:=4*i T13:=4*n T14:=a T13 a T12=T14 T15:= 4*n a T15=xB6q中间代码程序段 i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3
4、v goto B3B3if i=j goto B6B4T6:=4*i x:=a T6 T7:=4*i T8:=4*j T9:=a T8 a T7=T9 T10:= 4*j a T10=x goto B2B5T11:=4*i x:=a T11 T12:=4*i T13:=4*n T14:=a T13 a T12=T14 T15:= 4*n a T15=xB6q删除公用子表达式后i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:= T2 x:=a T6 T7:= T6 T8:=
5、 T4 T9:=a T8 a T7=T9 T10:= T8 a T10=x goto B2B5T11:= T2 x:=a T11 T12:= T11 T13:= T1 T14:=a T13 a T12=T14 T15:= T13 a T15=xB6q复写传播i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:= T2 x:=a T6 T7:= T6 T8:= T4 T9:=a T8 a T7=T9 T10:= T8 a T10=x goto B2B5T11:= T2 x:=a
6、 T11 T12:= T11 T13:= T1 T14:=a T13 a T12=T14 T15:= T13 a T15=xB6q复写传播(一)后i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:= T2 x:=aT2 T7:= T2 T8:= T4 T9:=a T4 a T2=T9 T10:= T4 a T4=x goto B2B5T11:= T2 x:=a T2 T12:= T2 T13:= T1 T14:=a T1 a T2=T14 T15:= T1 a T1=xB6
7、q复写传播(一)后i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:= T2 x:=aT2 T7:= T2 T8:= T4 T9:=a T4 a T2=T9 T10:= T4 a T4=x goto B2B5T11:= T2 x:=a T2 T12:= T2 T13:= T1 T14:=a T1 a T2=T14 T15:= T1 a T1=xB6q复写传播(二)后i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T
8、3v goto B3B3if i=j goto B6B4T6:= T2 x:=T3 T7:= T2 T8:= T4 T9:=T5 a T2=T5 T10:= T4 a T4= T3 goto B2B5T11:= T2 x:=T3 T12:= T2 T13:= T1 T14:= v a T2=v T15:= T1 a T1= T3B6q删除无用赋值i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4T6:= T2 x:=T3 T7:= T2 T8:= T4 T9:=T5 a T2=T
9、5 T10:= T4 a T4= T3 goto B2B5T11:= T2 x:=T3 T12:= T2 T13:= T1 T14:= v a T2=v T15:= T1 a T1= T3B6q删除无用赋值后 i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B3B3if i=j goto B6B4a T2=T5 a T4= T3 goto B2B5a T2=v a T1=T3B6q强度削弱 i:=m-1 j:=n T1:=4*n v:=aT1B1i:=i+1 T2:=4*i T3:=aT2 if T3v goto B
10、3B3if i=j goto B6B4a T2=T5 a T4= T3 goto B2B5a T2=v a T1=T3B6q强度削弱后 i:=m-1 j:=n T1:=4*n v:=aT1 T2:=4*i T4:=4*jB1i:=i+1 T2:= T2+4 T3:=aT2 if T3v goto B3B3if i=j goto B6B4a T2=T5 a T4= T3 goto B2B5a T2=v a T1=T3B6q删除归纳变量i:=m-1 j:=n T1:=4*n v:=aT1 T2:=4*i T4:=4*jB1i:=i+1 T2:= T2+4 T3:=aT2 if T3v goto B
11、3B3if i=j goto B6B4a T2=T5 a T4= T3 goto B2B5a T2=v a T1=T3B6q删除归纳变量后i:=m-1 j:=n T1:=4*n v:=aT1 T2:=4*i T4:=4*jB1T2:= T2+4 T3:=aT2 if T3v goto B3B3if T2=T4 goto B6B4a T2=T5 a T4= T3 goto B2B5a T2=v a T1=T3B610.2 局部优优化l基本块块：指程序中一顺顺序执执行语语句序列，其中只 有一个入口和一个出口。入口就是其中第一个 语语句，出口就是其中最后一个语语句。T1:=a*aT2:=a*bT3:
12、=2*T2T4:=T1+T2T5:=b*bT6:=T4+T5q如果一条三地址语句为x:=y+z ，则称对x定值并引用y和z。q在一个基本块中的一个名字， 所谓在程序中的某个给定点是 活跃的，是指如果在程序中(包 括在本基本块或在其它基本块 中)它的值在该点以后被引用。10.2局部优优化l局限于基本块块范围围内的优优化称为为基本块块内的 优优化，或称局部优优化。l在一个基本块块内通常可以实实行下面的优优化:删删除公共子表达式删删除无用赋值赋值合并已知量临时变临时变量改名交换语换语句的位置代数变换变换l划分四元式程序为为基本块块的算法:1.求出四元式程序中各个基本块块的入口语语句: 1) 程序第一
13、个语语句，或 2) 能由条件转转移语语句或无条件转转移语语 句转转移到的语语句，或 3) 紧紧跟在条件转转移语语句后面的语语句。l划分四元式程序为为基本块块的算法:2. 对对以上求出的每个入口语语句，确定其所属 的基本块块。它是由该该入口语语句到下一入口语语 句(不包括该该入口语语句)、或到一转转移语语句( 包括该转该转移语语句)、或一停语语句(包括该该停语语 句)之间间的语语句序列组组成的。3. 凡未被纳纳入某一基本块块中的语语句，可以从 程序中删删除。l例：划分基本块块(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5)
14、X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) haltl例：划分基本块块(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) haltl例：划分基本块块(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) haltl例：划分基本块块(1) read X
15、 (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) haltl例：划分基本块块(1) read X (2) read Y (3) R:=X mod Y (4) if R=0 goto (8) (5) X:=Y (6) Y:=R (7) goto (3) (8) write Y (9) halt优优化措施l合并已知量T1:=2T2:=4*T1 变换变换成 T2:=8l临时变临时变量改名T:=b+c 其中T是一个临时变临时变量名。把这这个语语句改成：S:=b+c优优化措施l交换语换语句的位置T1:=b+c T2:=x+y l代数变换变换x:=x+0 或 x:=x*1x:=y*2 变换变换成 x:=y*y流图图l每个流图图以基本块为结块为结点。如果一个结结点的基 本块块的入口语语句是程序的第一条语语句，则则称此 结结点为为首结结点。如果在某个执执行顺顺序中，基本 块块B2紧紧接在基本块块B1之后执执行，则则从B1到B2有 一条有向边边。即，如果有一个条件或无条件转转移语语句从B
