黄州广场高清监控安装摄像机方案

第十章代码优化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=m1;j=n;v=a[n];(1)i:=m1while(1){(2)j:=ndoi=i+1;while(a[i]v);(3)t1:=4*ndoj=j1;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=m1;j=n;v=a[n];(9)j:=j1while(1){(10)t4:=4*jdoi=i+1;while(a[i]v);(11)t5:=a[t4]doj=j1;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+xx/2变成x*0.5anxn+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+4t3=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的值只需要被计算一次，而原来的程