第十章代码优化哈工大王宏志.ppt
《第十章代码优化哈工大王宏志.ppt》由会员分享,可在线阅读,更多相关《第十章代码优化哈工大王宏志.ppt(117页珍藏版)》请在三一办公上搜索。
1、第十章 代码优化,优化的概念,编译时刻为改进目标程序的质量而进行的各项工作。空间效率时间效率空间效率和时间效率有时是一对矛盾,有时不能兼顾。优化的要求:必须是等价变换为优化的努力必须是值得的。有时优化后的代码的效率反而会下降。,优化的分类,机器相关性:机器相关优化:寄存器优化,多处理器优化,特殊指令优化,无用指令消除等。无关的优化:优化范围:局部优化:单个基本块范围内的优化,常量合并优化,公共子表达式删除,计算强度削弱和无用代码删除。全局优化:主要是基于循环的优化:循环不变优化,归纳变量删除,计算强度削减。优化语言级:优化语言级:针对中间代码,针对机器语言。,代码优化程序的结构,控制流分析的主
2、要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集,主要是变量的值的获得和使用情况的数据流信息。到达-定义分析;活跃变量;可用表达式;代码变换:根据上面的分析,对内部中间代码进行等价变换。,控制流分析,数据流分析,代码变换,基本块和流图,基本块中,控制流是由第一个四元式进入,到达最后一个四元式离开。流图:把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n当且仅当控制流可能从n的最后的一个四元式到达n的第一个四元式。首节点:对应的基本块的第一个四元式是程序的第一个四元式。,流图的构造,以所有的基本块为节点集合。有B1到B2
3、的边(B2是B1的后继)当且仅当:B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。B2是紧紧跟随在B1后面的四元式,且B1的最后四元式不是无条件转向语句。,流图的例子,在转移语句中,目标标号转变称为基本块的编号,可以避免因为四元式的变动而引起的麻烦。,=1_i=1_f=0_a,=i10B4,=f_b+fat1=t1_f=b_a+i1t2=t2_iGOB2,=ffib,B1,B2,B3,B4,基本块的优化,常量合并公共子表达式删除强度削弱无用代码删除,常量合并,例子:l=2*3.14*r*23.14t1*t1rt2=t2l2*3.1415926的值在编译时刻就可以确定。*6.28r
4、t2=t2l,公共子表达式删除,+bca-adb+bcc-add显然,第2和4个四元式计算的是同一个值,所以第四个四元式可以修改为=b_d。对于第1和3个四元式,虽然都是计算b+c,但是他们的值其实是不同的,所以不能完成处理。公共子表达式:如果某个表达式先前已经计算,且从上次计算到现在,E中的变量的值没有改变。那么E的这次出现就称为公共子表达式。利用先前的计算结果,可以避免对公共子表达式的重复计算。,例子,x+y*t-a*(x+y*t)/(y*t)*ytt1+xt1t2*ytt3+xt3t4*at4t5*ytt6/t5t1t7-t2t7t8消除公共子表达式之后:*ytt1+xt1t2*at2t
5、5/t5t1t7-t2t7t8,强度削弱,实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。X2变成x*x。2*x或2.0*x变成x+xx/2变成x*0.5anxn+an-1xn-1+a1x+a0变成(anx+an-1)x+an-2)x+a1)x+a0,无用代码删除,如果四元式opxyz之后,z的值再也没有被使用到,那么这个四元式是无用的。无用的四元式往往意味着程序的错误,一般不会出现在正确的程序里面。多数无用四元式是由优化引起的。=t1t3,如果我们尽量用t1替代t3,可能使t3不被使用,从而这个四元式称为无用的四元式。,等价变换的分类,保结构等价变换删除公共子表达式和删除无用代
6、码,重新命名临时变量和交换独立四元式的顺序等。+xyt变成+xyu+abt1+xyt2变成+xyt2+abt1代数等价变换利用了代数恒等性质,强度削弱。2x=x+x,B and true=B.需要考虑双目运算符的可交换特性。,基本块优化的实现,基本块内部优化的实现的主要工具为DAG图。用DAG图表示各个值的计算/依赖关系。图中的标记:叶子节点的标记为标识符(变量名)或常数作为唯一的标记。叶子节点是标识符时,用下标0表示它时初值。内部节点用运算符号作为标记,表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。,DAG图
7、的例子,+bca-adb+bcc-add,四元式的分类,0型:=x_y1型:opx_y(单目运算)2型:opxyzrelopxyz(z是序号),基本块DAG图构造算法,输入:一个基本块输出:相应DAG图算法说明:通过逐个扫描四元式来逐步建立DAG图。函数node(x)表示和标识符x相应的最近建立的节点。他代表扫描到当前的四元式的时候,标识符x的值对应的节点。步骤1:初始化:无任何节点,node对任何标识符无定义。步骤2:依次对基本块中的每个四元式op x y z执行如下步骤。如果node(x)没有定义,建立叶子节点,标记为x,让node(x)等于这个节点。如果node(y)没有定义,为y建立节
8、点。如果四元式为0型,n=node(x);如果四元式为1型,寻找标记为op且子节点为node(x)的节点,如果找不到,建立这样的节点n。,基本块DAG图构造算法(续),对于2型四元式,查看是否存在标记为op的节点,且其左右子节点分别为node(x)和node(y)。如果找不到,建立这样的节点n。步骤3:如果z为标识符,从node(z)中删除标识符z,并把z加入到找到或者建立的节点n的标识符表中,并设置node(z)为n。说明:处理2型四元式的时候,如果op是可交换的运算符,可以允许其左右节点可以互换。,生成DAG图的例子,*4it1=at1t2*4it3=bt3t4*t2t4t5+prodt5
9、t6=t6prod+i1t7=t7i=i20(3),DAG图的应用,公共子表达式:构造中,寻找是否有标记为op且子节点为node(x),node(y)的节点时,自然完成了公共子表达式的寻找。在基本块中,其值被引用的标识符:构造了叶子节点的标识符。结果能够在基本块外被引用的四元式op x y z。设它对应的节点为n,如果DAG图构造结束的时候,n的标志符表不为空。,=和&=运算符的处理,对数组的赋值需要特别的处理,这是因为数组的下标是变量。对于数组元素的赋值可能改变数组中任何一个元素的值。=Ait1=Ajt2&=yt2t2=Ait3Ai并不是公共子表达式。在处理对数组A的元素的赋值四元式的时候,
10、应该注销所有以=为标记,A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。处理对指针所指空间的赋值的时候,同样要注销相应的节点。如果不能确定指针指向的范围,那么,需要注销所有的节点。,A,i,=,j,=,t1,t2,y,&=,=,从DAG图到四元式序列,在DAG图中,有些运算已经进行了合并。如果不考虑=和&=算符,可以依照DAG图中的拓扑排序得到的次序进行。但是,有了=和&=算符之后,计算的次序必须修正。实际上,我们可以按照各个节点生成的顺序来从DAG图生成四元式序列。,从DAG重建四元式序列算法,按照DAG图中各个节点的生成次序对每个节点作如下处理:若是叶子节点,且附加标识
11、符表为空,不生成四元式。若是叶子节点,标记为x,附加标识符为z,生成=x z。若是内部节点,附加标识符为z,根据其标记op和子节点数目,生成下列4种形式的四元式。Op不是=或者=,也不是relop,有两个子节点,生成opxyz如果是=或者=,生成opxyz。如果是relop,生成relopxyz,z是基本块序号。只有一个子节点,生成opx_z。,从DAG重建四元式序列算法(续),若是内部节点,且无附加标识符,则添加一个局部于本基本块的临时性附加标识符,按照上一情况生成。如果节点的标识符重包含多个附加标识符z1,z2,zk时:若是叶子节点,标记为z,生成一系列四元式=zz1=zz2=zzn不是叶
12、子节点,生成四元式序列:=zz2=zzn,使用DAG图进行优化的例子(四元式序列),四元式序列片断:*4it10=At10t11=t11x*4it12=At12t13*4jt14=At14t15&=t15t13t13*4jt16=At16t17&=xt17t17ijB2,使用DAG图进行优化的例子(DAG图),在第10个节点生成后,node(t11)变成无定义.,1:4,2:i,3:*,t10,4:A,t12,5:=,t11,6:=,t13,8:*,7:j,t14,9:=,t15,10:&=,t16,11:=,t17,12:&=,13:,B2,x,从DAG图到四元式序列,*4it10(3)=A
13、t10t11(5):=t11x(5)=At10t13(6)*4jt14(8)=At14t15(9)&=t15t13t13(10)=At14t17(11)&=xt17t17(12)ijB2(13),DAG的其他应用,常量合并:*2pit1*t1rt2=t2l无用代码删除:对于=t10t12,如果t12不需要使用,那么,这个四元式不需要生成。,与循环有关的优化,循环不变表达式外提。归纳变量删除。计算强度削弱,循环不变式(代码)外提,有些表达式位于循环之内,但是该表达式的值不随着循环的重复执行而改变,该表达式被称为循环的不变表达式。如果按照前面讲的代码生成方案,每一次循环都讲计算一次。如果把这个表达
14、式提取到循环外面,该计算就只被执行一次。从而可以获得更加好的效率。,循环不变式的例子,计算半径为r的从10度到360度的扇形的面积:for(n=1;n36;n+)S:=10/360*pi*r*r*n;printf(“Area is%f”,S);显然,表达式10/360*pi*r*r中的各个量在循环过程中不改变。可以修改程序如下:C=10/360*pi*r*r*n;for(n=1;n36;n+)S:=C*n;printf(“Area is%f”,S);修改后的程序中,C的值只需要被计算一次,而原来的程序需要计算36次。,四元式的循环不变式,(1)=1n(2)n36(21)(3)GOF(4)(4)
15、/10360tl(5)*tlpit2(6)*t2rt3(7)*t3rt4(8)*t4nt5(9)=t5S(18)+n1t9(19)=t9n(20)GO(4)(21)其中,四元式4,5,6,7是循环不变四元式。,循环不变四元式的相对性,对于多重嵌套的循环,循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环,它就不是循环不变式。例子:for(i=1;i10;i+)for(n=1;n360/(5*i);n+)S:=(5*i)/360*pi*r*r*n;.5*i和(5*i)/360*pi*r*r对于n的循环(内层循环)是不变表达式,但是对于外层循环,它们不是循环不变表达式。,循环不变表达式优
16、化需要解决的问题,如何识别循环中的不变表达式?把循环表达式外提到什么地方?什么条件下,不变表达式可以外提?,归纳变量的删除(例子),例子:Prod=0;i=1;for(i=1;i=20;i+)prod+=prod+A4*i*B4*i;*4it1=at1t2*4it3=bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i=i20B2i作为计数器。每次重复,i的值增加1,而Ai,Bi对应的地址t1,t3增加4。我们可以删除i,而使用t1或者t3进行循环结束条件的测试。,归纳变量的删除,在循环中,如果变量i的值随着循环的每次重复都固定地增加或者减少某个常量,则称i为循环的归纳变
17、量。如果在一个循环中有多个归纳变量,归纳变量的个数往往可以减少,甚至减少到1个。减少归纳变量的优化称为归纳变量的删除。,归纳变量的删除(四元式例子),=0prod=li,*4it1=at1t2*4it3=bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i=i20B2,=0prod=0t1,+4t1t1+4t3t3=at1t2=bt3t4*t2t4t5+prodt5t6=t6prod=t180B2,归纳变量的删除,归纳变量的删除一方面可以删除变量,减少四元式,另外,删除归纳变量同时也削减了计算强度。为了进行归纳变量删除优化,必要的是找出归纳变量。,计算强度削弱,在删除归纳
18、变量的过程中,已经将一些乘法运算转换成为加法运算。还有一类经常可以被应用的是对于下标变量地址的计算。,计算强度削减(下标变量),对于数组Tan1n2nm,其下标变量ai1i2i3im的地址计算如下:base+d;其中base为a000的地址。d=(i1*n2+i2)*n3+i3)*nm+im)*sizeof(T);当满足某些情况的时候,地址的计算可以使用加法来代替乘法。,下标变量计算强度的削减(例子),for(v1=v10;v1v1f;v1+)for(v2=v20;v2v2f;v2+)Ai1i2i3i1,i2,i3都可以表示成为:Ck0+Ck1*V1+Ck2*V2(k=1,2,3);Ai1i2
19、i3的地址为base+d;d=(i1*n2*n3+i2*n3+i3);将i1,i2,i3的表达式代入d的表达式,可以得到d=C0+C1*V1+C2*V2.,下标变量计算强度的削减(例子),显然,在上面的例子中,每次内循环d的值增加C2;每次外循环,d的值增加C1(但是V2被重置)。显然我们可以这样计算Ai1i2i3的地址:在循环开始的时候,设置初值d1=(base+C0)+C1*V10;在进入外层循环后,进入内存循环前,设置d2=d1+C2*V20在内存循环,使用d2作为地址获取Ai1i2i3的值。内存循环体每次运行结束之前,将d2的值增加C2。每次外层循环体运行结束之前,将d1的值增加C1。
20、显然,对于Ai1i2i3的地址计算变成了加法运算。,下标变量计算强度的削减结果,D1=base+C0+C1*V10;for(v1=v10;v1v1f;v1+)D2=D1+C2*V20;for(v2=v20;v2v2f;v2+)*D2;D2+=C2;D1+=C1;,下标地址优化计算的条件,相应的数组是常界数组:数组的上下界都是常量。下标变量中的下标表达式是循环控制变量的线性表达式。满足上述条件的称为可优化下标变量。在C语言中,要求循环控制变量每次循环的变动是常数。,循环优化的实现,循环结构的识别数据流分析代码转换,循环结构的识别,对于源程序来说,识别循环是比较方便的。但是代码的优化是针对四元式序
21、列的,所以识别循环必须针对流图进行。定义8.3如果流图中,从某个初始节点出发,每一条到达节点n的路径都必须经过m,那么称m是节点n的必经节点。记为m dom n。任何节点都是自己的必经节点。m为n的前驱,n为m的后继。直接必经节点:从初始节点到达n的所有路径上,节点n的最后一个必经节点称为直接必经节点。,循环满足的条件,循环必须有唯一的入口节点,称为首节点。对于循环中任何一个节点,必定至少有一个路径回到首节点。,回边和自然循环,定义8.4 假定流图中存在两个节点M和N满足M dom N。如果存在从节点N到M的有向边N-M,那么这条边称为回边。定义8.5 在流图中,给定一个回边N-M,对应与这个
22、回边的自然循环为:M,以及所有可以不经过M而到达N的节点。M为该循环的首节点。用节点的集合表示自然循环。,自然循环的例子,3 dom 4回边4-34 dom 7回边7-410-7的自然循环7,8,107-4的自然循环4,5,6,7,8,104-3,8-3的自然循环3,4,5,6,7,8,10,回边寻找算法,首先列出所有从首节点开始,不带圈的路径。节点N的必经节点的集合为满足以下条件的节点M:所有包含N的路径P,M都在N的前面出现。回边集合如下:N-M|N是一个节点,M在N的必经节点集合中,寻找自然循环的算法,输入:回边N-M;输出:回边对应的自然循环.算法:设置loop=N,M;push(st
23、ack,N);while non-empty(stack)dom=top(stack);pop(stack);for m的每个前驱节点p if p is_not_in loop then loop+=p;push(stack,p);,算法的说明,节点M在初始时刻已经在loop中所以,M的前驱不可能被加入到loop中。如果N-M不是回边,那么,首节点会被加入到loop中。此时算法不能得到自然循环。,相关概念,通常,循环互不相交,或者一个在另外一个里面。内循环:不包含其他循环的循环称为内循环。如果两个循环具有相同的首节点,那么很难说一个包含另外一个。此时把两个循环合并。,B0,B1,B2,B3,可
24、归约流图,可归约流图:删除了其中回边之后,可以构成无环有向图的流图。特性:不存在循环外向循环内部的转移,进入循环必须通过其首节点。实际的程序对应的流图一般都是可归约的流图。没有goto语句的结构化程序的流图总是可归约的。一般使用goto语句的程序也是可归约的。,B1,B2,B3,数据流分析相关概念,变量获得值的方式:通过赋值语句;通过输入语句;通过过程形式参数;点:流图基本块中的位置,包括:第一个四元式之前,两个相邻四元式之间,和最后的四元式之间。定值:使变量x获得值的四元式称为对x的定值,一般用四元式的位置表示。引用点:引用某个变量x的四元式的位置称为x的引用点。,数据流分析的种类,到达-定
25、义数据流方程活跃变量数据流方程可用表达式数据流方程,到达-定义数据流方程,到达-定义:假定x有定义d,如果存在一个路径,从紧随d的点到达某点p,并且此路径上面没有被注销,则称x的定义d到达p。这表明,在p点使用变量x的时候,x的值可能是由d点赋予的。引用-定义链:设变量x有一个引用点u,变量x的所有能过到达u的一切定义称为x在u点处的引用-定义链,简称ud链。显然,通过变量x在引用点u的ud链,可以判断x是否循环不变的。,到达定义数据流方程(记号),INB:表示基本块B的入口点处各个变量的定点集合。如果B中点p之前有x的定义点d,且这个定义能够到达p,则点p处x的ud链是d。否则,点p处x的u
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 代码 优化 哈工大 王宏志
链接地址:https://www.31ppt.com/p-6005020.html