您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 编译原理_chapter10
第十章代码优化SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重点:代码优化的任务,局部优化、循环优化、全局优化的基本方法。难点:控制流分析,数据流分析。2020/2/172第10章代码优化10.1优化的种类10.2控制流分析10.3局部优化10.4循环优化10.5全局优化10.6本章小结2020/2/173第10章代码优化代码优化就是为了提高目标程序的效率,对程序进行等价变换,亦即在保持功能不变的前提下,对源程序进行合理的变换,使得目标代码具有更高的时间效率和/或空间效率。空间效率和时间效率有时是一对矛盾,有时不能兼顾。优化的要求:必须是等价变换(保持功能)为优化的努力必须是值得的。有时优化后的代码的效率反而会下降。2020/2/174代码优化程序的结构控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集,主要是变量的值的获得和使用情况的数据流信息。到达-定义分析;活跃变量分析;可用表达式分析.代码变换:根据上面的分析,对中间代码进行等价变换.控制流分析数据流分析代码变换2020/2/17510.1优化的种类机器相关性机器相关优化:寄存器优化,多处理器优化,特殊指令优化,无用指令消除等。机器无关优化:优化范围局部优化:单个基本块范围内的优化,常量合并优化,公共子表达式删除,计算强度削弱和无用代码删除。全局优化:主要是基于循环的优化:循环不变优化,归纳变量删除,计算强度削减。优化语言级优化语言级:针对中间代码,针对机器语言。2020/2/176程序例子本节所用的例子i=m1;j=n;v=a[n];(1)i:=m1while(1){(2)j:=ndoi=i+1;while(a[i]v);(3)t1:=4*ndoj=j1;while(a[j]v);(4)v:=a[t1]if(i=j)break;(5)i:=i+1x=a[i];a[i]=a[j];a[j]=x;(6)t2:=4*i}(7)t3:=a[t2]x=a[i];a[i]=a[n];a[n]=x;(8)ift3vgoto(5)2020/2/177程序例子本节所用的例子i=m1;j=n;v=a[n];(9)j:=j1while(1){(10)t4:=4*jdoi=i+1;while(a[i]v);(11)t5:=a[t4]doj=j1;while(a[j]v);(12)ift5vgoto(9)if(i=j)break;(13)ifi=jgoto(23)x=a[i];a[i]=a[j];a[j]=x;(14)t6:=4*i}(15)x:=a[t6]x=a[i];a[i]=a[n];a[n]=x;...i=m-1j=nt1=4*nv=a[t1]i=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[12]=t14t15=4*na[15]=xt6=4*ix=a[t6]t7=4*it8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]xgotob2程序流图B1B6B5B4B3B22020/2/17910.1.1公共子表达式删除局部公共子表达式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB22020/2/171010.1.1公共子表达式删除局部公共子表达式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB22020/2/171110.1.1公共子表达式删除局部公共子表达式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB22020/2/171210.1.1公共子表达式删除全局公共子表达式B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgotoB2i=i+1t2=4*it3=a[t2]Ift3vgotoB2j=j-1t4=4*jt5=a[t4]Ift5vgotoB32020/2/171310.1.1公共子表达式删除B5x=a[i];a[i]=a[j];a[j]=x;t6:=4*ix:=a[t6]t7:=4*it8:=4*jt9:=a[t8]a[t7]:=t9t10:=4*ja[t10]:=xgotoB2t6:=4*ix:=a[t6]t8:=4*jt9:=a[t8]a[t6]:=t9a[t8]:=xgotoB2x:=a[t2]t9:=a[t4]a[t2]:=t9a[t4]:=xgotoB2x:=t3a[t2]:=t5a[t4]:=xgotoB2j=j-1t4=4*jt5=a[t4]Ift5vgotoB3i=i+1t2=4*it3=a[t2]Ift3vgotoB22020/2/171410.1.1公共子表达式删除B6x=a[i];a[i]=a[n];a[n]=x;t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=x2020/2/171510.1.1公共子表达式删除B6x=a[i];a[i]=a[n];a[n]=x;a[t1]能否作为公共子表达式?t11:=4*ix:=a[t11]t12:=4*it13:=4*nt14:=a[t13]a[t12]:=t14t15:=4*na[t15]:=xx:=t3t14:=a[t1]a[t2]:=t14a[t1]:=xi=m-1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]Ift3vgotoB2j=j-1t4=4*jt5=a[t4]Ift5vgotoB3Ifi=jgotob6B1B6B5B4B3B2把a[t1]作为公共子表达式是不稳妥的:控制离开B1进入B6之前可能进入B5,而B5有对a的赋值x:=t3t14:=a[t1]a[t2]:=t14a[t1]:=xx:=t3a[t2]:=t5a[t4]:=xgotoB22020/2/171710.1.2复制传播形如f:=g的赋值语句叫做复制语句优化过程中会大量引入复制t:=d+ea:=t删除局部公共子表达式期间引进复制t:=d+eb:=tc:=tc:=d+eb:=d+ea:=d+e2020/2/171810.1.2复制传播复制传播变换的思想是在复制语句f:=g之后尽可能用g代替f复制传播变换本身并不是优化,但它给其它优化带来机会无用代码删除x:=t3a[t2]:=t5a[t4]:=t3gotoB2x:=t3a[t2]:=t5a[t4]:=xgotoB22020/2/171910.1.3无用代码删除例:复制传播可能会引入无用代码x:=t3a[t2]:=t5a[t4]:=t3gotoB2a[t2]:=t5a[t4]:=t3gotoB22020/2/172010.1.3无用代码删除无用代码是指计算结果以后不被引用的语句一些优化变换可能会引入无用代码例:debug:=true;debug:=false;...测试后改成...if(debug)print…if(debug)print…2020/2/172110.1.4代码外提结果独立于循环执行次数的表达式称为循环不变计算。如果将循环不变计算从循环中移出到循环的前面,将会减少循环执行的代码总数,大大提高代码的执行效率。这种与循环有关的优化方法称为代码外提。2020/2/172210.1.4代码外提例如,下面的while语句中,1imit-2就是循环不变计算。while(i=limit-2){/*假设循环体中的语句不改变limit的值*/}代码外提将生成如下的等价语句:t:=limit-2;while(i=t){/*假设循环体中的语句不改变limit或t*/}2020/2/172310.1.5强度削弱实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。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+a02020/2/172410.1.5强度削弱i:=m-1j:=nt1:=4*nv:=a[t1]j:=j-1t4:=4*jt5:=a[t4]ift5vgotoB3ifi=jgotoB6B1B2B3B4B5B6(a)变换前i:=m-1j:=nt1:=4*nv:=a[t1]j:=j-1t4:=t4-4t5:=a[t4]ift5vgotoB3ifi=jgotoB6B1B3B4B5B6(a)变换后t4:=4*jB2图10.5将强度削弱应用到块B3中的4*j2020/2/172510.1.6归纳变量删除在围绕B3的循环的每次迭代中,j和t4的值总是同步变化,每次j的值减l,t4的值就减4,这是因为4*j赋给了t4,我们将这样的变量称为归纳变量如果循环中存在两个或更多的归纳变量,也许可以只保留一个,而去掉其余的,以便提高程序的运行效率。t2=t2+4t3=a[t2]ift3vgotoB2t4=t4-4t5=a[t4]ift5vgotoB3i=i+1t2=t2+4t3=a[t2]ift3vgotoB2j=j-1t4=t4-4t5=a[t4]ift5vgotoB3ift2=t4gotob610.1.6归纳变量删除2020/2/172710.1.6归纳变量删除i:=m-1j:=nt1:=4*nv:=a[t1]t2:=4*it4:=4*jt2:=t2+4t3:=a[t2]ift3vgotoB2t4:=t4-4t5:=a[t4]ift5vgotoB3ift2=t4gotoB6B1B2B3B4t14:=a[t1]a[t2]:=t14a[t1]:=t3B6B5a[t2]:=t5a[t4]:=t3gotoB2图10.7归纳变量删除后的流图10.1.7.循环不变式外提(代码外提)有些表达式位于循环之内,但是该表达式的值不随着循环的重复执行而改变,该表达式被称为循环的不变表达式。如果按照前面讲的代码生成方案,每一次循环都将计算一次。如果把这个表达式提取到循环外面,该计算就只被执行一次。从而可以获得更加好的效率。10.1.7.循环不变式的例子计算半径为r的从10度到360度的扇形的面积:for(n=1;n36;n++){S:=10/360*pi*r*r*n;printf(“Areais%f”,S);}显然,表达式10/360*pi*r*r中的各个量在循环过程中不改变。可以修改程序如下:C=10/360*pi*r*r;for(n=1;n36;n++){S:=C*n;printf(“Areais%f”,S);}修改后的程序中,C的值只需要被计算一次,而原来的程
本文标题:编译原理_chapter10
链接地址:https://www.777doc.com/doc-3854774 .html