【教学课件】第十章代码优化.ppt

第十章 代码优化,10,1,什么是代码优化,10,2,局部优化,10,3,控制流程分析和循环,10,4,数据流分析举例,宗旨：,获得较好性能的代码,阶段：,source front I.R code target,code end generator code,用户,中间代码优化,目标代码优化,10.1 什么是代码优化,例：,int arr10000;void Binky()int i;for(i=0;i 10000;i+)arri=1;,int arr10000;void Winky()register int*p;for(p=arr;p arr+10000;p+)*p=1;,10.2 优化分类,按阶段分:与机器无关的优化-对中间代码进行依赖于机器的优化-对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优化优化工作 数据流分析(control-flow analysis)控制流分析(data-flow analysis)变换(transformations),10.2.1 优化技术简介(a)常数合并,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;,优化技术简介(b)常数传播,_tmp4=0;f0=_tmp4;_tmp5=1;f1=_tmp5;_tmp6=2;i=_tmp6;,f0=0;f1=1;i=2;,优化技术简介(c)代数简化,x+0=x0+x=xx*1=x1*x=x0/x=0 x-0=x,b&true=bb&false=falseb|true=trueb|false=b,优化技术简介代数简化,_tmp0=5;_tmp1=_tmp0+a;_tmp2=_tmp1+10;b=_tmp2;_tmp0=15;_tmp1=a+_tmp0;b=_tmp1;,例：b=5+a+10;,优化技术简介(d)降低运算强度,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,优化技术简介(e)复写传播,tmp2=tmp1;tmp3=tmp2*tmp1;tmp4=tmp3;tmp5=tmp3*tmp2;c=tmp5+tmp4;,tmp3=tmp1*tmp1;tmp5=tmp3*tmp1;c=tmp5+tmp3;,例：main()int x,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:=0 for I:=1 to 20 do P:=P+AI*BI,(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),(1)P:=0(2)I:=1(3)T1:=4*I(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(6)T4:=T1,P:=0for I:=1 to 20 do P:=P+AI*BI,(4)T2:=addr(A)-4(7)T5:=addr(B)-4,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(3),(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(12)if I=20 goto(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:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if I=20 goto(5),(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if=80 goto(5),(3)T1:=4,T1,(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11)I:=I+1(3)T1:=T1+4(12)if T1=80 goto(5),(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=80 goto(5),基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。入口语句：1.程序的第一个语句；或者，2.条件转移语句或无条件转移语句的转移目标语句；或者3.紧跟在条件转移语句后面的语句。,10.2 局部优化：基本块内的优化,基本块内的语句要么全执行，要么全不执行，而不能只执行一部分。,划分基本块的算法：1求出四元式程序之中各个基本块的入口语句。2对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。3.凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。,例：划分基本块(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)if B=C goto L2(6)B:=B+1(7)goto L1(8)L2:write(A)(9)halt,划分成四个基本块B1，B2，B3，B4,(1)(2)(3),(4)(5),(6)(7),(8)(9),基本块内实行的优化：合 并 已 知 量删除多余运算删除无用赋值,B1B2B3B4,(1)read(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)if B=C goto L2(6)B:=B+1(7)goto L1(8)L2:write(A)(9)halt,基本块的DAG表示及其应用,有向无环图(DAG-Directed Acyclic Graph)基本块的DAG是在结点上带有标记的DAG 叶结点：独特的标识符(名字,常数)标记 内部结点：运算符号标记 各个结点：附加标识符标记,用,DAG,进行基本块的优化,四元式,DAG,结点,0,型：,A:=B(:=,B,A),n1,A,B,1,型,:A:=op B(op,B,A),A,op,B,2,型,:A:=B op C(op,B,C,A),A,op,n1,n2,B,C,n1,n2,n1,n3,n1,n2,仅含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）执行op B（即合并已知量），令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。（4）执行B op C（即合并已知量），令得到的新常数为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*T6,例：(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*T6,To 3.14(a),n1,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*T6,例：(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*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:=R-r(9)B:=A*T6,10,3,控制流分析和循环,控制流程图,（流图）：具有唯一首结点的有向图,G=,（,N,，,E,，,n,0,）,N,：结点集,基本块集,E,：有向边集,n0:,首结点包含程序第一个语句的基本块,i,j,有向边 基本块j在程序的位置紧跟在i后,且i的出口语句不是转移或停语句 i的出口是goto(S)或 if goto(S),而(S)是j的入口语句,例：*(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,分析程序流图中结点间的关系m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n(a,a DOM a)必经结点集 定义 结点n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).,例,:,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,1,必经结点必经结点集,D(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,3,循环的查找,循环的查找算法,回边：假设a b是流图中的一条有向边，如果b DOM a，则称a b是流图中的一条回边。,有向边nd是回边，组成的循环是由结点d，结点n以及有通路到达n而该通路不经过d而所有结点组成，并且d是该循环的唯一入口结点。,回边 6 6循环6 7 4 4,5,6,7 7 2 2,3,4,5,6,7循环(结点序列的性质)1.强连通的(任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点.,例,:,6,7,3,4,1,2,3,5,7,6,1,2,1,2,1,2,3,1,有向边nd是回边，组成的循环是由结点d，结点n以及有通路到达n而该通路不经过d而所有结点组成，并且d是该循环的唯一入口结点。,10.4 数据流分析,1.活跃变量数据流方程2.到达-定值数据流方程3.讨论 数据流问题分类 路径 数据流方程解不唯一,10.4.1 活跃变量的数据流分析,所谓活跃变量就是它的当前值还将被引用（在赋予一个新值之前）。在全局范围来分析的话，一个变量是活跃的，即如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用。通过全局活跃变量分析，识别出其当前值不再活跃（即，它的值已经死了）的那些变量。死变量的值在基本块的出口处不需要保存。,令B为一个基本块，定义LiveIn(B)为在基本块B入口处为活跃的变量的集合。定义LiveOut(B)为基本块B的出口处的活跃变量的集合。LiveIn和LiveOut并不是相互独立的，令S（B）为流图中基本块B的后继的集合，则有 LiveOut(B)=LiveIn(i)iS(B)如果基本块没有后继，则其LiveOut为空令LiveUse(B)为B中被定值之前要引用变量的集合。这个集合由基本块B中的语句唯一确定。容易看出，如果vLiveUse(B)，则vLiveIn(B)；即LiveIn(B)LiveUse(B)。令Def(B)为在B中定值的变量集合。如果一个变量在基本块B的出口处为活跃的且vDef(B)，则它在B的入口处也是活跃的，即：LiveIn(B)LiveOut(B)-Def(B)因此有：LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)即：一个变量在基本块入口处为活跃的，则一定有：或者它在基本块的LiveUse集中，或者它在基本块的出口处为活跃的且在基本块中没有重新定值,例：a:=1;if a=b then b:=1 else c:=1endif;d:=a+b,提取Def和LiveUse集合,Def(B)为在B中定值的变量集合LiveUse(B)为B中被定值之前要引用变量的集合,从最后一个基本块开始由后往前计算，可以得到一定的解 LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B)LiveOut(B)=LiveIn(i)iS(B),LiveOut(B4)=，因此：LiveIn(B4)=LiveUse(B4)=a,b-d现在LiveOut(B2)=LiveIn(B4)=a,b-dLiveOut(B3)=LiveIn(B4)=a,b-dLiveIn(B2)=LiveOut(B2)-Def(B2)=a,b-b-d=a-dLiveIn(B3)=LiveOut(B3)-Def(B3)=a,b c-d=a,b c-dLiveOut(B1)=LiveIn(B2)LiveIn(B3)=a a,b-d=a,b-d c 最后:LiveIn(B1)=LiveUse(B1)(LiveOut(B1)-Def(B1)=b(a,b c-d a)=b-d c,B1,B2,B3,B4,b:=1,a:=1if a=b goto B2,c:=1,d:=a+b,分析程序中所有变量的定值和引用之间的关系,到达-定值数据流方程OUTB=(INB-KILLB)GENBINB=OUTp pPB PB:B的所有前驱基本块GENB:B中定值并到达B出口之后的所有定值点集.KILLB:B之外的那些定值点集,其定值的变量在B中 又重新定值.INB:到B入口之前(紧)的各变量的所有定值点集OUTB:到达B出口之后(紧)各变量的所有定值点集.,B,3,0111100,0011000,B,4,0011000,0010100,B,5,0011100,0011100,入口结点 循环L,前置结点 入口结点 循环L,B1,B2,B3,B5,(2)if x y goto B3,(7)j:=i,(3)i:=2(4)x:=x+1,(5)y:=y-1(6)if y=20 gotoB5,(1)i:=1,B4,1,2,3,4,5,B1,B2,B3,B5,if x y goto B3,j:=i,i:=2x:=x+1,y:=y-1if y=20 gotoB5,i:=2,B4,i:=1,B2,B,1,B,2,B,3,B,5,I:=3;(2)if xy goto(3),(3)I:=2,(4)x:=x+1,(5)y:=y-1,(6)if y,=20,goto B,2,(7)J:=I,B4,(1)I:=1,B,1,B,2,B,3,B,4,B,5,(1)I:=1,(2)if xy goto(3),(3)I:=2,(4)x:=x+1,(5)k:=I;y:=y-1,(6)if y,=20,goto B,2,(7)J:=I,当把循环中的不变运算s:A:=B op C外提时注意：,（,2,）,要求循环中其它地方不再有A的定值点。,（3,）,要求循环中A的所有引用点都是而且仅仅是这个定值所能达到的,（1）要求s所在结点是循环的所有出口结点的必经结点,（4）要求A在离开循环之后不再是活跃的,数据流问题的讨论合流问题,向前流（forward-flow)(信息流的方向与控制流是一致的)和向后流（backward flow）对每个基本块有一个IN集合和一个Out集合,在同一基本块中，In和Out集合的关系对于向前流问题：Out(B)=Used(B)(In(B)Killed(B)对于向后流问题：In(B)=Used(B)(Out(B)Killed(B)作为一个边界条件，向前流问题中的起始基本块的In和向后流问题中最后一个基本块的Out集合必须指明，通常，这些边界条件集或者为空，或者包含所有可能的值，因问题而定。如：到达-定值数据流方程 OUTB=(INB-KILLB)GENB活跃变量数据流方程LiveIn(B)=LiveUse(B)(LiveOut(B)-Def(B),数据流问题的讨论路径问题,任意路径数据流分析讨论的数据流假定这么一个性质，即某条路径为真，（如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值，则就认为这个变量是被定值的）。这种数据流问题被称为任意路径问题。任意路径问题的解不能保证所需的性质一定会满足，仅仅是可能满足。全路径数据流分析数据流问题也可以用全路径（all-path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。,数据流问题的解不一定唯一,考察图10.20的流图，其中有一个简单的循环。在这个流图中，没有对任何变量定值，a在B4中被引用。应用向后流方法传播可以得到一个最明显的解，即四个基本块的LiveIn集合均为a。但是，不太合理的解也是可能的。,若Def(B1)=Def(B2)=Def(B3)=Def(B4)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=Liveuse(B1)=a则最明显的解：LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=LiveIn(B1)=a,B1,B2,B3,B4,例如，下面解是满足数据流方程的：,注意b没有在任何基本块中被引用！问题所在是基本块B2和B3互为祖先；而且，因为b从未定值（所有Def集为空），一旦b被包括在LiveIn集合中，它就永远消除不了,