编译原理 第11章(清华大学)

第11章代码优化11．1什么是代码优化11．2局部优化11．3控制流程分析和循环11．4数据流分析举例何谓代码优化：宗旨：获得较好性能的代码等价意图，结果，权衡阶段：sourcefrontI.Rcodetargetcodeendgeneratorcode用户中间代码优化目标代码优化intarr[10000];voidBinky(){inti;for(i=0;i10000;i++)arr[i]=1;}intarr[10000];voidWinky(){registerint*p;for(p=arr;parr+10000;p++)*p=1;}优化分类按阶段分:与机器无关的优化---对中间代码进行依赖于机器的优化--对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作数据流分析(control-flowanalysis)控制流分析(data-flowanalysis)变换(transformations)优化技术简介—常数合并a=10*5+6-b;_tmp0=10;_tmp1=5;_tmp2=_tmp0*_tmp1;_tmp3=6;_tmp4=_tmp2+_tmp3;_tmp5=_tmp4–b;a=_tmp5;_tmp0=56;_tmp1=_tmp0–b;a=_tmp1;优化技术简介—常数传播_tmp4=0;f0=_tmp4;_tmp5=1;f1=_tmp5;_tmp6=2;i=_tmp6;f0=0;f1=1;i=2;优化技术简介—代数简化x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb||true=trueb||false=b优化技术简介—代数简化b=5+a+10;_tmp0=5;_tmp1=_tmp0+a;_tmp2=_tmp1+10;b=_tmp2;_tmp0=15;_tmp1=a+_tmp0;b=_tmp1;优化技术简介—降低运算强度a)i*2=2*i=i+i=i2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5优化技术简介—复写传播tmp2=tmp1;tmp3=tmp2*tmp1;tmp4=tmp3;tmp5=tmp3*tmp2;c=tmp5+tmp4;tmp3=tmp1*tmp1;tmp5=tmp3*tmp1;c=tmp5+tmp3;main(){intx,y,z;x=(1+20)*-x;y=x*x+(x/y);y=z=(x/y)/(x*x);}tmp1=1+20;tmp2=-x;x=tmp1*tmp2;tmp3=x*x;tmp4=x/y;y=tmp3+tmp4;tmp5=x/y;tmp6=x*x;z=tmp5/tmp6;y=z;优化技术简介1.删除多余运算2.循环不变代码外提3.强度削弱4.变换循环控制条件5.合并已知量与复写传播6.删除无用赋值P:=0forI:=1to20doP:=P+A[I]*B[I](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)(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2[T1](8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T1(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)ifI=20goto(3)•(1)P:=0•(2)I:=1•(4)T2:=addr(A)-4•(7)T5:=addr(B)-4•(5)T3:=T2[T1]•(6)T4:=T1•(8)T6:=T5[T4]•(9)T7:=T3*T6•(10)P:=P+T7•(11)I:=I+1•(12)ifI=20goto(5)(3)T1:=4*I(3‘)T1:=T1+4(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifI=20goto(5)(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)if=80goto(5)(3)T1:=4T1T1(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3’)T1:=T1+4(12)ifT1=80goto(5)(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)11.2局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：1．程序的第一个语句；或者，2．条件转移语句或无条件转移语句的转移目标语句；或者3．紧跟在条件转移语句后面的语句。划分基本块的算法：1．求出四元式程序之中各个基本块的入口语句。2．对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。3．凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。(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划分成四个基本块B1，B2，B3，B4B1(1)(2)(3)基本块内实行的优化:合并已知量删除多余运算B2(4)删除无用赋值(5)B3(6)(7)B4(8)(9)基本块的DAG表示及其应用DAGDirectedAcyclicGraph无环路有向图基本块的DAG是在结点上带有标记的DAG叶结点独特的标识符(名字,常数)标记内部结点运算符号标记各个结点附加标识符标记用DAG进行基本块的优化四元式DAG结点0型：A:=B(:=,B,—,A)n1AB1型:A:=opB(op,B,—,A)n2Aopn1B2型:A:=BopC(op,B,C,A)n3Aopn1n2BCn1n2n1n3n1n2仅含0，1，2型四元式的基本块的DAG构造算法:首先，DAG为空。对基本块的每一四元式，依次执行：1．如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1）。如果当前四元式是2型，则：(I)如果NODE(1)无定义，则构造一标记为C的叶结点并定义NODE(1)为这个结点；(II)转2(2)2．（1）如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3（1）。（2）如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2（4），否则转3（2）。（3）执行opB（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。（4）执行BopC（即合并已知量），令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。3．（1）检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。（2）检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op（即找公共子表达式）。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。4.如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。而后，我们可由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*T6To3.14(a)n1T0T13.146.28(b)n2n1T2+T0T13.146.28Rr(c)n2n5n3n1n4A*T2+T0T13.146.28Rr(d)n2n5n3n1n4n6A,B*T2+T0T13.146.28Rr(e)n2n5n3n1n4n6A,B*T2+T0T1,T33.146.28Rr(f)n2n5n3n1n4n6A,B*T2,T4+T0T1,T33.146.28Rr(g)n2n5n3n1n4n6A,B,T5*T2,T4+T0T1,T33.146.28Rr(h)n2n5n3n1n4n6A,B,T5*T2,T4T6+-T0T1,T33.146.28Rrn2n5n3n7n1n4n6B*A,T5*T2,T4T6+-T0T1,T33.146.28Rr(j)n2n5n3n7n1n4n6n8(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*T611．3控制流分析和循环控制流程图（流图）：具有唯一首结点的有向图G=（N，E，n0）N：结点集基本块集E：有向边集n0：首结点包含程序第一个语句的基本块有向边①基本块j在程序的位置紧跟在i后,且i的出口语句不是转移或停语句②i的出口是goto(S)或ifgoto(S),而(S)是j的入口语句ij例：*(1)readx(20ready*(3)r:=xmody(4)ifr=0goto(8)*(5)x:=y(6)y:=r(7)goto(3)*(8)writey(9)halt(1)readxB1(2)ready(3)r:=xmodyB2(4)ifr=0goto(8)(5)x:=y(8)writeyB4(6)y:=rB3(9)halt(7)goto(3)1243分析程序流图中结点间的关系mDOMn定义在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为mDOMn(a,aMODa)必经结点集定义结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).