《编译原理课程教案》第7章：代码优化.ppt

《《编译原理课程教案》第7章：代码优化.ppt》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第7章：代码优化.ppt（56页珍藏版）》请在三一办公上搜索。

1、代码优化,第十章,本章要求,主要内容：代码优化的主要功能，局部优化、全局优化和循环优化的相关概念，各种优化技术重点掌握：代码优化技术，基本块、流图、DAG的概念，必经结点、回边、循环的概念，各种优化技术。,代码优化所地位和作用：,7.1 概述,实际上很多地方可以对代码的执行效率进行改进，主要讲对中间代码的优化,代码优化：对程序进行等价变换，使得从变换后的程序出发，能够生成更有效的目标代码。,优化分类,按阶段分:与机器无关的优化-对中间代码进行 依赖于机器的优化-对目标代码进行根据优化所涉及的程序范围分成:(1)局部优化:(基本块)(2)循环优化:对循环中的代码进行优化(3)全局优化:大范围的优

2、化,优化的原则等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果 宗旨：获得较好性能的代码（时间，空间）等价意图、结果之间要权衡,中间代码优化技术,优化工作 数据流分析(control-flow analysis)控制流分析(data-flow analysis)变换(transformations),快速排序程序,void quicksort(int m,int n)int i,j,v,x;if(nv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;quicksort(m,j);quicksor

3、t(i+1,n);,中间代码,7.2 基本块的优化,基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句，入口是其第一个语句，出口是其最后一个语句 如果x:=y+z 则称对x定值,引用y和z 在一个基本块内的一个名字,在程序中的某个给定点是活跃的，是指如果在程序中它的值在该点之后被引用.,入口语句：1程序的第一个语句；或者，2条件转移语句或无条件转移语句的转移目标语句（此处的转移语句包括各种控制的转向，如call，return，end，stop等）；或者3紧跟在条件转移语句后面的语句。,执行：对于一个基本块，执行时只能从其入口进入，从其出口退出,划分基本块的算法,求出四元

4、式程序之中各个基本块的入口语句对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。一般把过程调用语句作为一个单独的基本块,例：*(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,流图：有向图。将控制流的信息增加到基本块的集合上来表示一个程序

5、。流图以基本块为单位。如果按顺序执行，就画一条有向边。基本块间的关系:(前驱,后继)B1是B2的前驱，B2是B1的后继:有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者 在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个无条件转移语句。,*(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,练习,f0=0 f1=1 if m=1 goto L3 i=2L1:if i=m goto L3L2:f2=f0+f1 f0=f1

6、 f1=f2 i=i+1 goto L1L3:return m,1,2,3,4,5,以快速排序的C代码为例：,void quicksort(int m,int n)int i,j,v,x;if(nv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;quicksort(m,j);quicksort(i+1,n);,各种代码优化技术：,快速排序程序的中间代码,i=m-1;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;,优化技术1删除公共子

7、表达式,如果表达式E已经在前面计算过，并在计算之后E的值没有改变，则称该表达式为公共子表达式。可以避免重复计算。,T6:=4*ix=aT6T7:=4*iT8:=4*jT9=aT8aT7:=T9T10:=4*jaT10:=xgoto B2,T6:=4*ix=aT6T7:=T6T8:=4*jT9=aT8aT7:=T9T10:=T8aT10:=xgoto B2,4*i，4*j重复计算,在更大的范围内删除4*i,4*j的计算，得到：,优化技术2复写传播,T6:=T2x=T3T7:=T2T8:=T4T9=T5aT2:=T5T10:=T4aT4:=T3goto B2,T6:=T2x=aT6T7:=T6T8

8、:=T4T9=aT8aT7:=T9T10:=T8aT10:=xgoto B2,T6:=T2，x=aT6，之间没有改变T6,因此，可以直接写x=aT2,在B2中T3:=aT2因此，x=T3,优化技术3删除无用代码,aT2:=T5aT4:=T3goto B2,T6:=T2x=T3T7:=T2T8:=T4T9=T5aT2:=T5T10:=T4aT4:=T3goto B2,某些变量的赋值无用，在后面的程序中不再有用,aT2:=vaT1:=T3,B5,B6,优化技术4对程序进行代数恒等变换（降低运算强度）,a)i*2=2*i=i+i=i2b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2

9、.0*f=f+fe)f/2.0=f*0.5,优化技术简介对程序进行代数恒等变换（代数简化）,x+0=x0+x=xx*1=x1*x=x0/x=0 x-0=xb&true=bb&false=falseb|true=trueb|false=b,优化技术简介对程序进行代数恒等变换（合并已知量）,T1:=2T2:=4*T1,T1:=2T2:=8,优化技术5代码外提,对循环中的有些代码，如果它产生的结果在循环中是不变的，可以提到循环外面,while(i=limit-2).,t=limit-2while(i=t).,优化技术6强度削弱,j:=j-1T4=4*jT5=aT4if T5v goto B3,T4=

10、T4-4T5=aT4if T5v goto B3,B3,J每次减1后再做乘4操作,改为先赋值后，T4的计算用减法运算,T4=4*j,优化技术7删除归纳变量,当进行强度削弱后，B4中i,j的比较可以使用T2,T4,If T2=T4 goto B6,基本块的DAG表示及其应用,DAG Directed Acyclic Graph有向无环路图基本块的DAG是在结点上带有标记的DAGDAG表示了基本块的计算过程叶结点表示标识符或常数的值，以标识符或常数作为标记内部结点以运算符作为标记，表示运算结果边表示了操作间的前驱和后继的关系每个结点：附加标识符标记，可以是一个或多个标识符都具有该结点代表的值,用D

11、AG进行基本块的优化,(0)x:=y,(1)x:=op y,(2)x:=y op z,基本块的DAG构造算法:,首先，DAG为空。对基本块的每一四元式，依次执行1，2，3，4步：1.如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2(1)。如果当前四元式是2型，则：(1)如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点；(2)转2(2),2.(1)如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3(1)。(2)如果NODE(B)和NOD

12、E(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（即找公共子表达式）。如果没有

13、，则构造该结点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重新生成原基本块的一个优化的代码序列。,例：求下列基本块的DAG,(1

14、)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:=

15、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,DAG的应用,根据DAG图，可以更进一步实现优化：合并已知量，如T1，T3删除冗余赋值，如B的第一次赋值公共子表达式的提取，如T2和T4在基本块

16、外被定值并在基本块内被引用的所有标识符，就是作为叶结点上标记的那些标识符在基本块内被定值且该值能在基本块后面被引用的所有标识符，就是DAG各结点上的那些附加标识符,(1)T1:=R+r(2)A:=6.28*T1(3)T2:=R-r(4)B:=S*T2,简化后的代码序列,循环：程序中可能反复执行的代码序列,也是优化的重点,7.3 循环优化,程序流图中结点间的关系m DOM n 定义 在程序流图中,对任意两个结点m和n,如果从流图的首结点出发,到达n的任意通路都要经过m,则称m是n的必经结点,记为m DOM n 每个结点是它本身的必经结点；循环的入口是循环中所有结点的必经结点。必经结点集定义 结点

17、n的所有必经结点的集合,称为结点n的必经结点集,记为D(n).,例：,D(1)=1D(2)=1，2D(3)=1，2，3。D(4)=1，2，4D(5)=1，2，4，5 D(6)=1，2，4，6 D(7)=1，2，4，7,循环的查找算法,回边：假设ab是流图中的一条有向边，如果b DOM a，则称ab是流图中的一条回边。,循环的查找,如果有向边nd是回边，组成的循环是由结点d，结点 n以及有通路到达n而该通路不经过d的所有结点组成，并且d是该循环的唯一入口结点。,回边 6 6 循环6 7 4 4,5,6,7 4 2 2,3,4,5,6,7循环(结点序列的性质)1.强连通的(任意两结点间,必有一条通

18、路,且该通路上各结点都属于该结点序列)2.它们中间有且只有一个是入口结点。,循环优化,循环优化的关键哪些基本块构成一个循环循环优化的方法代码外提强度削弱删除归纳变量,循环的性质,两个循环的关系：图中任意两个循环要么是嵌套的，要么不相交（可能有公共的入口结点）内循环：不包含任何其它循环的循环如果两个自然循环有相同的首结点，且两个循环不是一个嵌在另一个里面时，可以考虑将二者合并，当成是一个循环,变量A在某点d的定值到达另一点u，是指流图中从d由一通路到达u且该通路上没有A的其他定值,代码外提,把循环不变计算提到循环外面，在入口结点的前面创建一个新的基本块，叫做前置结点。前置结点唯一的后继是L的首结

19、点将原来从L外到达L首结点的边都改成进入前置结点从L内到达入口结点的边不变,for I:=1 to 10 do AI,2*J:=AI,2*J+1,并不是所有情况下，循环中的不变运算都可以外提。右图中的B3块中的I:=2是不变运算，但不能外提，因为它并不是所有结点的必经结点。,强度削弱,是指把程序中执行时间长的运算替换为执行时间较短的运算,强度削弱的方法？,删除归纳变量,基本归纳变量：如果循环中对变量I只有唯一的形如I:=I c的赋值，c是循环不变量归纳变量：如果I是循环中的基本归纳变量，J在循环中的赋值总是可以化为I的同一线性函数，即J:=C1*I c2。同时称J与I同族,一个基本归纳变量除用于自身的递归定值外，一般在循环中用来计算其他归纳变量及控制循环的进行，此时，可以用与它同族的某一归纳变量来控制循环的进行删除归纳变量一般是在强度削弱以后进行的,