编译原理第九章代码优化

第9章代码优化9.1代码优化概述9.2局部优化9.3控制流程分析和循环优化9.4数据流分析9.1代码优化概述代码优化代码优化的层次代码优化的评价代码优化实例代码优化：时空寄存器、多处理器、特殊指令优化等代码优化的层次窥孔优化：目标代码级别，滑动窗口局部优化：中间代码级别，以基本块为单位循环优化：目标代码级别，针对循环全局优化：中间代码级别，过程内代码优化评价优化效率：优化前后代码性能的提高基准测试程序，相同运行环境优化开销：优化所花费的代价：时间、存储空间等不同方法对不同程序的优化效果不同取决于程序本身的算法不同优化方法同时使用可能有副作用合并已知量常数传播代数化简强度削弱复写传播删除多余运算循环不变代码外提变换循环控制条件删除无用赋值基本优化技术常数合并a=10*5-b;_tmp0=10;_tmp1=5;_tmp2=_tmp0*_tmp1;_tmp3=_tmp2–b;a=_tmp3;_tmp0=56;_tmp1=_tmp0–b;a=_tmp1;常数传播_tmp3=0;f0=_tmp3;f0=0;代数化简x+0=x0+x=xx*1=x1*x=x0/x=0x-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*tmp1;tmp5=tmp3*tmp1;(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)优化技术实例:P:=0forI:=1to20doP:=P+A[I]*B[I]①删除多余运算(6)T4:=T1②代码外提(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4③强度削弱(3’)T1:=T1+4(3)T1:=4④变换循环控制条件(12)ifT1=80goto(5)⑤复写传播(8)T6:=T5[T1]⑥删除无用赋值(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3‘)T1:=T1+4(12)ifT1=80goto(5)代码优化的理论基础相关的描述工具：中间表示：四元式DAG图控制流图数据流方程问题复杂度：往往是NP完全或NP难简化，小规模问题优化算法…代码优化的基本过程代码的描述数据流分析(data-flowanalysis)控制流分析(control-flowanalysis)变换(transformations)基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：程序的第一个语句；或者，条件转移语句或无条件转移语句的转移目标语句；或者紧跟在条件转移语句后面的语句。划分基本块的算法：求出四元式程序之中各个基本块的入口语句。对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括），或到一转移语句（包括），或到一停语句（包括）之间的语句序列组成的。凡未被纳入某一基本块的语句，把它们删除。9.2局部优化：基本块内的优化(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt基本块内实行的优化:合并已知量删除多余运算删除无用赋值DAG(DirectedAcyclicGraph):无环有向图基本块的DAG是在结点上带有标记的DAG:一个基本块＝一个DAG（体现基本块内各语句的联系）niXA，B，…结点形式：运算符（OP）---内部结点标识符常数叶结点标记编号变量A，…具有所代表的值基本块的DAG表示及其应用利用DAG进行基本块优化的基本思想是：四元式序列=DAG=四元式序列四类四元式：0型四元式：后继结点个数为0，如图(1)所示；1型四元式：有一个后继结点，如图(2)所示；2型四元式：有两个后继结点，如图(3)(4)(5)3型四元式：有三个后继结点，如图(6)所示。n1BA(1)A=Bn2n1ABop(2)A=opBn1Bn2Cn3opA(3)A=BopCn1Bn2Cn3=[](4)A=B[C]n1Bn2Cn3rop(S)(5)ifBropCgotoSn1Dn3n4(6)D[C]=Bn2[]=CBn1(S)(7)gotoS图5–1四元式与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=R−r(10)B=T5*T6n6n1n2T0T1,T3n3n4n5n7n8B*A,T5T6T2,T4*+-3.146.28Rr(10)B:=T5*T6(9)T6:=R-rn6n1n2T0T1,T3n3n4n5A,B,T5T2,T4*+3.146.28Rr(8)T5:=T3*T4n6n1n2T0T1,T3n3n4n5n7A,B,T5T6T2,T4*+-3.146.28Rrn6n1n2T0T1,T3n3n4n5A,BT2,T4*+3.146.28Rr(7)T4:=R+r(6)T3:=2*T0n6n1n2T0T1n3n4n5A,BT2*+3.146.28Rr(5)B:=An6n1n2T0T1,T3n3n4n5A,BT2*+3.146.28Rrn6n1n2T0T1n3n4n5AT2*+3.146.28Rr(4)A:=T1*T2(3)T2:=R+rn1T0n1n2T13.143.14(2)T1:=2*T0n1n2T0T1n3n4n5T2+3.146.28Rr6.28(1)T0:=3.14(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=R−r(9) B=A*T6若T0、T1、…、T6在基本快后面不被引用，则：(1) T2=R+r(2) A=6.28*T2(3) T6=R−r(4) B=A*T69.3控制流分析和循环优化一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何一个结点都有一条通路的结点。有向边①基本块j在程序的位置紧跟在i后,且i的出口语句不是转移或停语句②i的出口是goto(S)或ifgoto(S),而(S)是j的入口语句ij例如，考察下面求最大公因子的三地址代码程序：*(1) readX(2) readY*(3) R=X%Y(4) if(R==0)goto(8)*(5) X=Y(6) Y=R(7) goto(3)*(8) writeY(9) halt1243(1) readX(2) readY(3) R=X%Y(4) if(R==0)goto(8)(5) X=Y(6) Y=R(7) goto(3)(8) writeY(9) haltB1B2B3B4循环的查找循环优化寻找循环循环定义直观上循环的构成==直观上，入口结点是循环中其它结点的必经结点。在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为mDOMn(a,aDOMa)结点n的所有必经结点的集合,称为结点n的必经结点集D(n).入口---唯一性返回到入口的反向边---回边结点互通1243576D(1)={1}D(2)={1，2}D(3)={1，2，3}D(4)={1，2，4}D(5)={1，2，4，5}D(6)={1，2，4，6}D(7)={1，2，4，7}回边：a→b是流图中的一条有向边，如果bDOMa。回边：6-6、7-4、4-2循环：回边a→b组成的循环是由结点b、a以及有通路到达a而该通路不经过b的所有结点组成，并且b是该循环的唯一入口结点。dnk回边：nd循环Ld----入口nkkn*不经d{6}{4,5,6,7}{2,3,4,5,6,7}前置结点循环L入口结点¡循环L入口结点¡图5–8给循环建立前置结点9.3代码优化示例通过一个快速排序子程序来了解代码优化的全过程。voidquicksort(intm,intn){inti,j,v,x;if(n=m)return;/*fragmentbeginshere*/i=m−1;j=n;v=a[n];while(1){doi=i+1;while(a[i]v);doj=j−1;while(a[j]v);if(i=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;/*fragmentendshere*/quicksort(m,j);quicksort(i+1,n);}图5–21给出了程序中两个注解行之间的语句翻译成中间代码序列后所对应的程序流图，其代码优化如下。1．删除公共子表达式在B5中分别把公共子表达式4*i和4*j的值赋给T7和T10，因此这种重复计算可以消除，即B5中的代码变换成：B5:T6=4*ix=a[T6]T7=T6T8=4*jT9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB2可以在更大范围内来考虑删除公共子表达式的问题，即利用B3中的四元式T4= 4*j可以把B5中的代码T8= 4*j替换为T8= T4。同样，可以把B5中的代码T6= 4*i替换为T6=T2。对于B6也可以同样考虑，最后，删除公共子表达式后的程序流图如图5–22所示。图5–21程序流图T6=4*ix=a[T6]T7=4*iT8=4*jT9=a[T8]a[T7]=T9T10=4*ja[T10]=xgotoB2i=m-1j=nT1=4*nv=a[T1]B1i=i+1T2=4*iT3=a[T2]ifT3vgotoB2j=j-1T4=4*jT5=a[T4]ifT5vgotoB3ifi=jgotoB6T11=4*ix=a[T11]T12=4*iT13=4*nT14=a[T13]a[T12]=T14T15=4*na[T15]=xB2B3B4B5B6FTFFTTT6=T2x=a[T6]T7=T6T8=T4T9=a[T8]a[T7]=T9T10=T8a[T10]=xgotoB2T11=T2x=a[T11]T12=T11T13=T1T14=a[T13]a[T12]=T14T15=T1a[T15]=x图5–22删除公共子表达式后的程序流图2．复写传播图5–22中的B5还可以把x=a[T6]变换为x=a[T2]。这种变换称为复写传播。B5变为：T6=T2x=a[T2]T7=T2T8=T4T9=a[T4]a[T2]=T9T10=T4a[T4]=xgotoB2进一步，在B5中可把x=a[T2]替换为x=T3，并继续通过复写传播，把B5中的a[T4]=x替换为a[T4]=T3。同样，把B5中的T9=a[T4]替换为T9=T5，a[T2]=T9替换为a[T2]=T5。B5变为：T6=T2x=T3T7=T2T8=T4T9=T5a[T2]=T5T10=T4a[T4]=T3gotoB23．删除无用赋值进行了复写传播后的B5，其中的变量x及临时变量T6、T7、T8、T9、T10在整个程序中不再使用，故可以删除对这些变量赋值的四元式。B5变为：a[T2]=T5a[T4]=T3gotoB2对B6进行相同的处理后变为：a[T2]=va[T1]=T3复写传播和删除无