编译原理第九章代码优化

1、第9章 代码优化9.1 代码优化概述代码优化概述9.2 局部优化局部优化9.3 控制流程分析和循环优化控制流程分析和循环优化9.4 数据流分析数据流分析寄存器、多处理器、寄存器、多处理器、特殊指令优化等特殊指令优化等v合并已知量v常数传播v代数化简v强度削弱v复写传播v删除多余运算v循环不变代码外提v变换循环控制条件v删除无用赋值基本优化技术基本优化技术常数合并a = 10 * 5 - b; _tmp0 = 10 ; _tmp1 = 5 ; _tmp2 = _tmp0 * _tmp1 ; _tmp3 = _tmp2 b; a = _tmp3 ; _tmp0 = 56 ; _tmp1 = _tm

2、p0 b ; a = _tmp1 ;常数传播_tmp3 = 0 ;f0 = _tmp3 ; f0 = 0 ;代数化简x+0 = x0+x = xx*1 = x1*x = x0/x = 0 x-0 = xb & true = bb & false = falseb | true = trueb | false = b削弱运算强度a) i*2 = 2*i = i+i = i2b) i/2 = (int)(i*0.5)c) f*2 = 2.0 * f = f + f复写传播tmp2 = tmp1 ;tmp3 = tmp2 * tmp1;tmp5 = tmp3 * tmp2 ; tmp3 = tmp1

3、 * tmp1 ; tmp5 = tmp3 * tmp1 ; (1) P:=0(2) I:=1(3) T1:=4*I(4) T2:=addr(A)-4(5) T3:=T2T1(6) T4:=4*I(7) T5:=addr(B)-4(8) T6:=T5T4(9) T7:=T3*T6(10) P:=P+T7(11) I:=I+1(12) if I=20 goto(3)优化技术实例:P:=0for I:=1 to 20 do P:=P+AI*BI删除多余运算删除多余运算(6) T4:=T1代码外提代码外提(1) P:=0(2) I:=1(4) T2:=addr(A)-4(7) T5:=addr(B)

4、-4强度削弱强度削弱(3) T1:= T1+4(3) T1:=4变换循环控制条件变换循环控制条件(12) if T1=80 goto(5)复写传播复写传播(8) T6:= T5T1删除无用赋值删除无用赋值(1) P:=0(4) T2:=addr(A)-4(7) T5:=addr(B)-4(3) T1:=4(5) T3:=T2T1(8) T6:=T5T1(9) T7:=T3*T6(10) P:=P+T7(3)T1:=T1+4(12) if T1= C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本块内实行的优化基本块内实行的优化:

5、合并已知量合并已知量 删除多余运算删除多余运算 删除无用赋值删除无用赋值 DAG(Directed Acyclic Graph): 无环有向图无环有向图基本块的基本块的DAG是在结点上带有标记的是在结点上带有标记的DAG:一个基本块一个基本块一个一个DAG（体现基本块内各语句的联系）（体现基本块内各语句的联系）niXA，B，结点形式：结点形式：运算符（运算符（OP）-内部结点内部结点标识符标识符常数常数叶结点叶结点标记标记编号编号变量变量A，具具有所代表的值有所代表的值基本块的DAG表示及其应用v利用DAG进行基本块优化的基本思想是： 四元式序列 = DAG = 四元式序列v四类四元式：0型四

6、元式：后继结点个数为0，如图 (1)所示；1型四元式：有一个后继结点，如图(2)所示；2型四元式：有两个后继结点，如图(3)(4)(5)3型四元式：有三个后继结点，如图(6)所示。图51 四元式与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= Rr (10) B=T5*T6(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6= Rr (9) B=A

7、*T6若T0、T1、T6在基本快后面不被引用，则：(1) T2=R+r(2) A=6.28*T2(3) T6= Rr (4) B=A*T69.3 9.3 控制流分析和循环优化控制流分析和循环优化一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何一个结点都有一条通路的结点。有向边有向边 基本块基本块 j j 在程序的位置紧跟在在程序的位置紧跟在i i 后后, ,且且 i i 的出口语句不是转的出口语句不是转移或停语句移或停语句 i i 的出口是的出口是 goto(S)goto(S)或或 if goto(S), if goto(S),而而( (S S)

8、 )是是 j j 的入口语句的入口语句 i j 例如，考察下面求最大公因子的三地址代码程序：*(1) read X (2) read Y*(3) R=X % Y (4) if(R=0) goto(8)*(5) X=Y (6) Y=R (7) goto(3)*(8) write Y (9) halt(1) read X(2) read Y(3) R=X % Y(4) if (R=0) goto(8)(5) X=Y(6) Y=R(7) goto(3)(8) write Y(9) haltB1B2B3B4循环的查找循环的查找循环优化循环优化寻找循环寻找循环循环定义循环定义直观上循环的构成直观上循环的

9、构成=直观上，入口结点是循环中其它结点的必经结点。在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n (a,a DOM a)结点n的所有的集合,称为结点n的必经结点集D(n).入口入口-唯一性唯一性返回返回到入口到入口的反向边的反向边-回边回边结点互通结点互通1243576D(1)=1D(2)=1，2D(3)=1，2，3D(4)=1，2，4D(5)=1，2，4，5D(6)=1，2，4，6D(7)=1，2，4，7回边：回边：abab是流图中的一条有向边，如果是流图中的一条有向边，如果b DOM a b DOM a 。回

10、边：6 -6、7-4、4-2循环：循环：回边abab组成的循环是由结点b b、a a以及有通路到达以及有通路到达a a而该通而该通路不经过路不经过b b的所有结点组成，并且的所有结点组成，并且b b是该循环的唯一入口结点。是该循环的唯一入口结点。dnk回边：回边：nd循环循环Ld-入口入口nkkn*不经不经d64,5,6,72,3,4,5,6,7图58 给循环建立前置结点9.3 代码优化示例通过一个快速排序子程序来了解代码优化的全过程。void quicksort (int m, int n)int i, j, v, x; if(n=m) return; /*fragment begins h

11、ere*/ i=m1; j=n; v=an; while(1) do i=i+1; while(aiv); if(i=j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x; /*fragment ends here*/ quicksort(m, j); quicksort(i+1,n);图521给出了程序中两个注解行之间的语句翻译成中间代码序列后所对应的程序流图，其代码优化如下。1删除公共子表达式v在B5中分别把公共子表达式4*i和4*j的值赋给T7和T10，因此这种重复计算可以消除，即B5中的代码变换成：B5:T6=4*i x=aT6 T7=T6 T8

12、=4*j T9=aT8 aT7=T9 T10=T8 aT10=x goto B2v可以在更大范围内来考虑删除公共子表达式的问题，即利用B3中的四元式T4=4*j可以把B5中的代码T8=4*j替换为T8=T4。v同样，可以把B5中的代码T6=4*i替换为T6=T2。对于B6也可以同样考虑，最后，删除公共子表达式后的程序流图如图522所示。图521 程序流图 T6=4*i x=aT6T7=4*i T8=4*jT9=aT8 aT7 = T9T10=4*j aT10 =xgoto B2i=m-1 j=nT1=4*n v=aT1B1i=i+1 T2=4*iT3=aT2if T3v goto B3if i

13、=j goto B6T11=4*i x=aT11T12=4*i T13=4*nT14=aT13 aT12 = T14T15=4*naT15 =xB2B3B4B5B6FTFFTTT6=T2 x=aT6T7=T6 T8=T4T9=aT8 aT7 = T9T10=T8 aT10 =xgoto B2T11=T2 x=aT11T12=T11 T13=T1T14=aT13 aT12 = T14T15=T1aT15 =x图522 删除公共子表达式后的程序流图2复写传播v图522中的B5还可以把x=aT6变换为x=aT2。这种变换称为复写传播。B5变为：T6=T2x=aT2T7=T2T8=T4T9=aT4aT

14、2= T9T10=T4aT4=xgoto B2v进一步，在B5中可把x=aT2替换为x=T3，并继续通过复写传播，把B5中的aT4=x替换为aT4 =T3。同样，把B5中的T9=aT4替换为T9=T5，aT2=T9替换为 aT2=T5。B5变为：T6=T2x= T3T7=T2T8=T4T9=T5aT2= T5 T10=T4aT4= T3goto B23删除无用赋值v进行了复写传播后的B5，其中的变量x及临时变量T6、T7、T8、T9、T10在整个程序中不再使用，故可以删除对这些变量赋值的四元式。B5变为： aT2= T5 aT4= T3 goto B2v对B6进行相同的处理后变为： aT2=

15、v aT1= T3v复写传播和删除无用赋值后的程序流图如图5-23所示。图523 复写传播和删除无用赋值后的程序流图aT2 = T5aT4 = T3goto B2i=m-1 j=nT1=4*n v=aT1B1i=i+1 T2=4*iT3=aT2if T3v goto B3if i=j goto B6aT2 = vaT1 =T3B2B3B4B5B6FTFFTT4代码外提：没有可外提到循环之外的不变运算。 5强度削弱v观察图523的内循环B3，可以把循环中计算T4值的乘法运算变为在循环前进行一次乘法运算而在循环中进行减法运算。同样，对循环B2中的T2=4*i也可以进行强度削弱。经过强度削弱后的程序流图如图5-24所示。6删除归纳变量v由图524可知，B2中T2与i之间保持着T2=4*i的线性关系；而B3中T4与j之间保持着T4=4*j的线性关系。在对T2=4*i和T4=4*j进行了强度削弱后，i和j仅出现在条件句if Ij goto B6中。因此，可以变换归纳变量而把此条件