第十章代码优化哈工大王宏志.ppt

第十章 代码优化,优化的概念,编译时刻为改进目标程序的质量而进行的各项工作。空间效率时间效率空间效率和时间效率有时是一对矛盾，有时不能兼顾。优化的要求：必须是等价变换为优化的努力必须是值得的。有时优化后的代码的效率反而会下降。,优化的分类,机器相关性：机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。无关的优化：优化范围：局部优化：单个基本块范围内的优化，常量合并优化，公共子表达式删除，计算强度削弱和无用代码删除。全局优化：主要是基于循环的优化：循环不变优化，归纳变量删除，计算强度削减。优化语言级：优化语言级：针对中间代码，针对机器语言。,代码优化程序的结构,控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。到达-定义分析；活跃变量；可用表达式；代码变换：根据上面的分析，对内部中间代码进行等价变换。,控制流分析,数据流分析,代码变换,基本块和流图,基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n当且仅当控制流可能从n的最后的一个四元式到达n的第一个四元式。首节点：对应的基本块的第一个四元式是程序的第一个四元式。,流图的构造,以所有的基本块为节点集合。有B1到B2的边（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.28rt2=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*at2t5/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不被使用，从而这个四元式称为无用的四元式。,等价变换的分类,保结构等价变换删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。+xyt变成+xyu+abt1+xyt2变成+xyt2+abt1代数等价变换利用了代数恒等性质，强度削弱。2x=x+x,B and true=B.需要考虑双目运算符的可交换特性。,基本块优化的实现,基本块内部优化的实现的主要工具为DAG图。用DAG图表示各个值的计算/依赖关系。图中的标记：叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标0表示它时初值。内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。,DAG图的例子,+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建立节点。如果四元式为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+prodt5t6=t6prod+i1t7=t7i=i20(3),DAG图的应用,公共子表达式：构造中，寻找是否有标记为op且子节点为node(x),node(y)的节点时，自然完成了公共子表达式的寻找。在基本块中，其值被引用的标识符：构造了叶子节点的标识符。结果能够在基本块外被引用的四元式op x y z。设它对应的节点为n，如果DAG图构造结束的时候，n的标志符表不为空。,=和&=运算符的处理,对数组的赋值需要特别的处理，这是因为数组的下标是变量。对于数组元素的赋值可能改变数组中任何一个元素的值。=Ait1=Ajt2&=yt2t2=Ait3Ai并不是公共子表达式。在处理对数组A的元素的赋值四元式的时候，应该注销所有以=为标记，A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。处理对指针所指空间的赋值的时候，同样要注销相应的节点。如果不能确定指针指向的范围，那么，需要注销所有的节点。,A,i,=,j,=,t1,t2,y,&=,=,从DAG图到四元式序列,在DAG图中，有些运算已经进行了合并。如果不考虑=和&=算符，可以依照DAG图中的拓扑排序得到的次序进行。但是，有了=和&=算符之后，计算的次序必须修正。实际上，我们可以按照各个节点生成的顺序来从DAG图生成四元式序列。,从DAG重建四元式序列算法,按照DAG图中各个节点的生成次序对每个节点作如下处理：若是叶子节点，且附加标识符表为空，不生成四元式。若是叶子节点，标记为x，附加标识符为z，生成=x z。若是内部节点，附加标识符为z，根据其标记op和子节点数目，生成下列4种形式的四元式。Op不是=或者=，也不是relop，有两个子节点，生成opxyz如果是=或者=，生成opxyz。如果是relop，生成relopxyz，z是基本块序号。只有一个子节点，生成opx_z。,从DAG重建四元式序列算法(续),若是内部节点，且无附加标识符，则添加一个局部于本基本块的临时性附加标识符，按照上一情况生成。如果节点的标识符重包含多个附加标识符z1,z2,zk时：若是叶子节点，标记为z，生成一系列四元式=zz1=zz2=zzn不是叶子节点，生成四元式序列：=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)=At10t11(5):=t11x(5)=At10t13(6)*4jt14(8)=At14t15(9)&=t15t13t13(10)=At14t17(11)&=xt17t17(12)ijB2(13),DAG的其他应用,常量合并:*2pit1*t1rt2=t2l无用代码删除:对于=t10t12，如果t12不需要使用，那么，这个四元式不需要生成。,与循环有关的优化,循环不变表达式外提。归纳变量删除。计算强度削弱,循环不变式（代码）外提,有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，该表达式被称为循环的不变表达式。如果按照前面讲的代码生成方案，每一次循环都讲计算一次。如果把这个表达式提取到循环外面，该计算就只被执行一次。从而可以获得更加好的效率。,循环不变式的例子,计算半径为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)/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的循环（内层循环）是不变表达式，但是对于外层循环，它们不是循环不变表达式。,循环不变表达式优化需要解决的问题,如何识别循环中的不变表达式？把循环表达式外提到什么地方？什么条件下，不变表达式可以外提？,归纳变量的删除（例子）,例子：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为循环的归纳变量。如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少到1个。减少归纳变量的优化称为归纳变量的删除。,归纳变量的删除（四元式例子）,=0prod=li,*4it1=at1t2*4it3=bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i=i20B2,=0prod=0t1,+4t1t1+4t3t3=at1t2=bt3t4*t2t4t5+prodt5t6=t6prod=t180B2,归纳变量的删除,归纳变量的删除一方面可以删除变量，减少四元式，另外，删除归纳变量同时也削减了计算强度。为了进行归纳变量删除优化，必要的是找出归纳变量。,计算强度削弱,在删除归纳变量的过程中,已经将一些乘法运算转换成为加法运算。还有一类经常可以被应用的是对于下标变量地址的计算。,计算强度削减（下标变量）,对于数组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);Ai1i2i3的地址为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。显然，对于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语言中，要求循环控制变量每次循环的变动是常数。,循环优化的实现,循环结构的识别数据流分析代码转换,循环结构的识别,对于源程序来说，识别循环是比较方便的。但是代码的优化是针对四元式序列的，所以识别循环必须针对流图进行。定义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，对应与这个回边的自然循环为：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(stack,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,可归约流图,可归约流图：删除了其中回边之后，可以构成无环有向图的流图。特性：不存在循环外向循环内部的转移，进入循环必须通过其首节点。实际的程序对应的流图一般都是可归约的流图。没有goto语句的结构化程序的流图总是可归约的。一般使用goto语句的程序也是可归约的。,B1,B2,B3,数据流分析相关概念,变量获得值的方式：通过赋值语句；通过输入语句；通过过程形式参数；点：流图基本块中的位置，包括：第一个四元式之前，两个相邻四元式之间，和最后的四元式之间。定值：使变量x获得值的四元式称为对x的定值，一般用四元式的位置表示。引用点：引用某个变量x的四元式的位置称为x的引用点。,数据流分析的种类,到达-定义数据流方程活跃变量数据流方程可用表达式数据流方程,到达-定义数据流方程,到达-定义：假定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的ud链就是IBB中关于x的定义点的集合。PB：B的所有前驱基本块的集合。GENB：各个变量在B内定义，并能够到达B的出口点的所有定义的集合。OUTB：各个变量的能够到达基本块B的出口点的所有定义的集合。KILLB：是各个变量在基本块B中重新定义，即在此块内部被注销的定义点的集合。,到达定义数据流方程,INB=OUTp where p isin PBOUTB=GENB(INB-KILLB)其中：GENB可以从基本块中求出：使用DAG图就可以得到。KILLB中，对于整个流图中的所有x的定义点，如果B中有对x的定义，那么该定义点在KILLB中。,方程求解算法,使用迭代方法。初始值设置为：INBi=空；OUTB=GENBi;change=TRUE;while(change)change=FALSE;for each B doINB=OUTp where p isin PB;OUTB=GENB(INB-KILLB);oldout=OUTB;if(OUTB!=oldout)change=TRUE;,算法例子,GENB1=d1,d2,d3KILLB1=d4,d5,d6,d7GENB2=d4,d5KILLB2=d1,d2,d7GENB3=d6KILLB3=d3GENB4=d7KILLB4=d1,d4,B1,B2,B3,B4,计算过程,初始化：INB1=INB2=INB3=INB4=空OUTB1=d1,d2,d3,OUTB2=d4,d5OUTB3=d6,OUTB4=d7.第一次循环：INB1=空;INB2=d1,d2,d3,d7;INB3=d4,d5;INB4=d4,d5,d6;OUTB1=d1,d2,d3;OUTB2=d3,d4,d5结果：INB1=空；OUTB1=d1,d2,d3;INB2=d1,d2,d3,d5,d6,d7;OUTB2=d3,d4,d5,d6;INB3=d3,d4,d5,d6;OUTB3=d4,d5,d6;INB4=d3,d4,d5,d6;OUTB4=d3,d5,d6,d7;,活跃变量数据流方程,判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为活跃变量分析。消除复写四元式的依据就是对活跃变量的分析。如果某个变量的值在以后不被引用，那么该复写四元式可以被消除。对于变量x和流图上的某个点p，存在一条从p开始的路径，在此路径上在对x定值之前引用变量x的值，则称变量x在点p是活跃变量，否则称x在点p不活跃。无用赋值：对于x在点p的定值，在所有基本块内不被引用，且在基本块出口之后又是不活跃的，那么x在点p的定义是无用的。,记号,L_INB:基本块B的入口点的活跃变量集合。L_OUTB:是在基本块B的出口点的活跃变量集合。L_DEFB:是在基本块b内的定值，但是在定义前在B中没有被引用的变量的集合。L_USEB:表示在基本块中引用，但是引用前在B中没有被定义的变量集合。其中，L_DEFB和L_USEB是可以从基本块B中直接求得的量，因此在方程中作为已知量。,活跃变量数据流方程,L_INB=L_USEB(L_OUTB-L_DEFB)L_OUTB=L_INs，其中s遍历B的所有后继。变量在某点活跃，表示变量在该点的值在以后会被使用。第一个方程表示：如果某个变量在B中没有定义就使用了，显然，变量在在入口处的值会被使用。如果这个变量在B的出口处活跃，并且B中没有对他进行定义，那么变量在入口处也是活跃的。第二个方程表示：在B的某个后记中会使用该后继的入口处的值，那么他其实也可能使用B的出口处的值。,活跃变量数据流方程求解,设置初值：L_INBi=空;重复执行一下步骤直到L_INBi不再改变：for(i=1;in;i+)L_OUTBi=L_INs;s是Bi的后继；L_INBi=L_USEBi(L_OUTBi-L_DEFBi);,活跃变量数据流方程例子,L_DEFB1=i,j,aL_USEB1=m,n,u1L_DEFB2=空L_USEB2=i,jL_DEFB3=aL_USEB3=u2L_DEFB4=iL_USEB4=u3,迭代过程,第一次循环：L_OUTB1=空L_INB1=m,n,u1L_OUTB2=空L_INB2=i,jL_OUTB3=i,jL_INB3=i,j,u2L_OUTB4=i,j,u2 L_INB4=j,u2,u3第二次循环：L_OUTB1=i,j,u2,u3L_INB1=m,n,u1,u2,u3L_OUTB2=i,j,u2,u3L_INB2=i,j,u2,u3L_OUTB3=i,j,u2,u3L_INB3=i,j,u2,u3L_OUTB4=i,j,u2,u3 L_INB4=j,u2,u3第三次循环各个值不再改变，完成求解。,可用表达式数据流方程,如果一个流图的首节点到达点p的每个路径上面都有对x op y的计算，并且在最后一个这样的计算到点p之间没有对x,y进行定值，那么表达式x op y在点p是可用的。表达式可用的直观意义：在点p上，x op y已经在之前被计算过，不需要重新计算。注意：如果对于有间接赋值四元式的情况，需要保证最后的计算x op y的点之间不会间接改变x,或者y的值：比如指针不会指向x或者y的存储区域，特别是当x为某个数组的时候。书上的讲解是针对没有间接赋值四元式的情况处理的。,概念,对表达式的注销：如果某个基本块B对x或者y定值，且以后没有重新计算x op y，那么称B注销表达式x op y。表达式的产生：如果某个基本块B对x op y进行计算，而以后并没有在对x或者y重新定值，那么称B产生表达式x op y。表达式的全集：在计算某个流图中的可用表达式的时候，表达式的讨论范围被限定在该出现在流图中的四元式对应的表达式。,记号,E_OUTB：在基本块出口处的可用表达式集合。E_INB：在基本块入口处的可用表达式集合。E_GENB：基本块B所产生的可用表达式的集合。E_KILLB：基本块B所注销掉的可用表达式的集合。E_GENB和E_KILLB的值可以直接从流图计算出来。因此在数据流方程中，可以将E_GENB和E_KILLB当作已知量看待。,E_GENB的计算,对于一个基本块B，E_GENB的计算过程如下：初始设置：E_GENB=空；顺序扫描每个四元式：对于四元式op x y z，把x op y加入E_GENB，从E_GENB中删除和z相关的表达式。最后的E_GENB就是相应的集合。,E_KILLB的计算,设流图的表达式全集为E;初始设置：EK=空；顺序扫描基本块的每个四元式：对于四元式op x y z，把表达式x op y从EK中消除；把E中所有和z相关的四元式加入到EK中。扫描完所有的四元式之后，EK就是所求的E_KILLB。,数据流方程,E_OUTB=(E_INB-E_KILLB)U E_GENBE_INB=E_OUTp B!=B1,p是B的前驱。E_INB1=空集说明：在程序开始的时候，无可用表达式。(3)一个表达式在某个基本块的入口点可用，必须要求它在所有前驱的出口点也可用。（2）一个表达式在某个基本块的出口点可用，或者该表达式是由它的产生的；或者该表达式在入口点可用，且没有被注销掉。（1）,方程求解算法,迭代算法初始化：E_INB1=空;E_OUTB1=E_GENB1;E_OUTBi=U-E_KILLBi(i=2)重复执行下列算法直到E_OUT稳定:FOR（i=2;i=n;i+)E_INBi=E_OUTp,p是Bi的前驱；E_OUTBi=E_GENBi(E_INBi-E_KILLBi);,算法说明,初始化值和前面的两个算法不同。E_OUTBi的初值大于实际的值。在迭代的过程中，E_OUTBi的值逐渐缩小直到稳定。U表示四元式的全集，就是四元式序列中所有表达式x op y的集合。,寻找循环不变表达式算法,输入：循环L，已经建立的UD链输出：不变四元式步骤1：若四元式的运算分量或者是常数，或者其所有定义点在循环外部，则标记此四元式为不变。步骤2：重复执行下面的步骤：如果一个四元式没有被加过标记，且运算分量要么是常数，要么其UD链中的定义点在循环外，或者该定义点已经被加过标记，则标记此四元式为不变。说明：一个四元式的是不变的，当且仅当其分量在循环中是不变的。主要有三种情况：常量，定义点在循环外部，或者定义点的四元式也是不变的。,不变四元式外提方法,对于不变四元式，可以在进入循环之前首先计算该四元式的值，然后在循环内部使用该值。可以将四元式的值外体到紧靠循环之前。,首节点,前置节点,代码外提不合法的情况（1）,=1 i,u v B3,+u 1 u,-v 1 v=v 20 B5,=ij,=2 i,代码外提不合法的情况（2）,=1 i=3 i,u v B3,=2 i+u 1 u,-v 1 v=v 20 B5,=ij,代码外提不合法的情况（3）,不变四元式外提的条件,不变四元式s=op x y z可以外提的条件：s所在的基本块节点是循环所有出口节点的必经节点。出口节点是指有后继节点在循环外的节点。（反例：情况1）循环中z没有其他的定值点。（反例：情况2）循环中z的引用点仅由s到达。（反例：情况3）,外提算法,步骤1：寻找一切不变四元式。步骤2：对于找到的每个循环，检查是否满足上面说的三个条件。步骤3：按照不变四元式找出的次序，把所找到的满足上述条件的四元式外提到前置节点中。如果四元式有分量在循环中定值，只有将定值点外提后，该四元式才可以外提。,循环不变式外提的例子,=1 i=0 k,1)+i 1 k2)*2 k t u v B3,+u 1 u,-v 1 v=v 20 B5,=ij,=1 i=0 k,u v B3,+u 1 u,-v 1 v=v 20 B5,=ij,1)+i 1 k2)*2 k t,关于归纳变量的优化,基本归纳变量：如果循环中，对于i的定值只有形状如i=i+c的定值，那么i称为循环的基本归纳变量。归纳变量族：如果循环中对变量j的定值都是形状如j=C1*i+C2，且i为基本归纳变量，那么称j为归纳变量，且属于i族。i属于i族。对于定值为C1*i+C2的i族归纳变量j，我们用(i,C1,C2)来表示。对于i族的归纳变量(i,C1,C2)，要求循环内部对此变量进行定值的时候，一定是赋给C1*i+C2。,例子（源程序）,for(i=0;i100;i+)j=4*i;printf(“%i”,j);i是基本归纳变量。j是i族归纳变量，可以表示为(i,4,0)。,寻找循环的归纳变量算法,步骤1：扫描循环的四元式，找出所有基本归纳变量。对应于每个基本归纳变量的三元组如(i,1,0)。步骤2：寻找循环中只有一个赋值的变量k，且对它的定值为如下形式，k=j*b,k=b*j,k=j/b,k=j+(-)b,k=b+(-)j。其中j为基本归纳变量，或者已经找到的归纳变量。如果j为基本归纳变量，那么k属于j族。k对应的三元式可以确定。如果j不是基本归纳变量，且属于i族，那么我们还要求：循环中对j的赋值以及和对k的赋值之间没有对i的赋值，且没有j在循环外的定值可以到达k的这个定值点。j的三元式可以相应确定。,算法说明,关于j不是基本归纳变量的时候，算法中的两个要求实际上是保证：对k进行赋值的时候，j变量当时的值一定等于C1*（i当时的值）+C2。,归纳变量的计算强度削弱算法,对于每个基本归纳变量i，对其族中的每个归纳变量j(i,c,d)执行下列步骤：建立新的临时变量t。用=tj四元式代替对j的赋值。对于每个定值i=i+n之后，添加t=t+c*n。在前置节点的末尾，添加四元式*c i t和+t d t。使得在循环开始的时候,t=c*i+t。当两个归纳变量具有同样的三元式的时候，可以只建立一个临时变量。,算法的说明,在优化过程中，为j(i,c,d)引入的变量t保证了在任何时刻(不包括在对i新定值后并且在t重新定值前，但是由于两者的四元式时紧连的）都满足t=c*i+d。如果在某些情况下，程序运行时对j的定值的次数远远少于对i的定值，经过优化的程序需要对t多次赋值，实际的效率可能降低。,归纳变量的删除,有些归纳变量的作用就是控制循环的次数。如果循环出口处的判断可以使用其它的变量代替，那么可以删除这些归纳变量。,归纳变量的删除算法,步骤1：对于每个基本归纳变量，取i族的某个归纳变量j（尽量使得c,d简单）。把每个对i的测试修改称为用j代替。relop i x B修改为relop i c*x+d B。relop i1 i2 B，如果能够找到三元组(i1,c,d)和(i2,c,d)，那么可以将其修改为relop j1 j2 B(假设c0)。如果归纳变量不再被引用，那么可以删除和它相关的四元式。如果基本归纳变量在循环出口处活跃，上面的算法不可以直接使用。步骤2：考虑对j的赋值=t j。如果每次对j引用和这个赋值四元式之间没有任何对t的赋值（此时，每次使用j的时候都有t=j)，可以在引用j的地方用t代替，同时删除四元式=t j（如果j在循环的出口处活跃，需要增加=t j）。,全局公共子表达式消除,对于循环中某个四元式op x y z，如果在所有到达这个四元式的路径上，已经计算了x op y，且计算之后x,y的值再没有修改过，那么显然我们可以使用以前计算得到的值。可用表达式表达的就是这个概念。如果有四元式op x y z，且在四元式前，表达式x op y可用，那么我们可以用下面的方法优化：在前面不同的地方计算x op y时，把值记录到同一个临时变量u里面。把这个四元式改变为=u z。,全局公共子表达式删除,对于四元式Q(op x y z)，如果x op y再Q之前可用，那么执行如下步骤：从Q开始逆向寻找，找到所有离Q最近的计算了x op y四元式。建立新的临时变量u。把步骤1中找到的四元式op x y t用下列四元式代替：op x y u和=u t。用=u t替代Q。,全局公共子表达式消除(图示),复制四元式的消除,中间代码的生成可能产生四元式。消除公共子表达式和删除归纳变量的时候，也会产生复制四元式。通过复制四元式传播的变量大多数是临时变量。而对临时变量可以使用复制传播来消除复制四元式。原理：=x y的效果是x和y的值相等。如果某个引用y的四元式运行的时候，x和y的值一定相等。那么我们可以使用对y的引用来替代对x的引用。这样做有时可以消除复制四元式=x y。,消除复制四元式的条件,对于复制四元式d:=x y，如果对y对应于d点的一切引用点u满足下列条件，那么我们可以删除d，并且在这些引用点上用对x的引用代替对y的引用。此定义点是d到达u的唯一的y的定义。从d到达u的路径（可以包含圈和多个u，但是不包含多个d）上，没有对x的定义。这两个条件实际上是说，当程序运行到达u点的时候，x和y的值总是相等。,记号,C_GENB：在基本块B中的所有复制四元式=x y，并且从该四元式开始到B的出口，x和y都没有再定义。C_KILLB：包含了所有在流图中出现并且满足下列条件的复制四元式=x y：B中存在对x或者y的定义，并且之后在没有复制四元式=x y出现。C_INB：表示在B的入口点，有效的复制四元式=x y的集合，也就是到达入口的路径上都要经过=x y并且之后没有对x或者y定义。C_OUTB：表示在B的出口点有效的复制四元式的集合。,数据流方程,C_OUTB=C_GENB(C_INB-C_KILLB)C_INB=E_OUTp；其中B不等于B1，p是B的前驱。C_INB1=空集。其中C_GENB和C_INB可以直接从流图得到，所以在方程中作为已知量处理。求解方法和可用表达式的求解相同。,复制传播算法,对于每个复制四元式d:=x y执行下列步骤。找出该y定义所能够到达的那些对y的引用。确定是否对于每个这样的y，d都在C_INB中，B是包含这个引用的基本块，而且B中该引用的前面没有x或者y的定义。如果d满足条件(2)，删除d，且把步骤1中找到的的对y的引用用x代替。,复制传播算法的例子,循环优化的例子(原始流图）,B2,寻找回边以及自然循环,回边有：B2B2,B3B3,B6B2。B2B2对应的循环是B2B3B3对应的循环是B3B6B2对应的循环是B2,B3,B4,B5,B6删除回边之后，得到的图是无回路的，所以这个流图是可归纳流图。,寻找公共子表达式,4*i：在B5，B7入口处可用(U1)。A4*i：在B5，B7的入口处可用(U2)。4*j：在B5的入口处可用(U3)。A4*j：在B5的入口处可用(U4)。4*n：在B7的入口处可用(U5)。A4*n：在B7的入口处可用(U6)。,公共子表达式的优化,寻找归纳变量,基本归纳变量有i，j。归纳变量有：u1：i族，(i,4,0)u2：j族，(j,4,0)如果分析得更加深入，会发现=四元式得到的地址也是归纳变量。但是，由于我们不考虑对间接赋值的优化，同时地址的处理也不在范围之内，所以我们没有列出。,归纳变量的优化,优化结果,-m 1 t1=t1 i=n j*4 n u5=u5 t2=A t2 u6=u6 t3=t3 v*4 i u1*4 j u3,+u1 4 u1=A u1 u2=u2 t6 t9 v B3,-u3 4 u3=A u3 u4=u4 t9 t9 v B3,=u1 u3 B6,=u2 t11=t11 x=u1 t12=A t12 t13,u1 u3 B2,=u2 t19=t19 x=u1 t20=A t20 t21=u5 t22=u6 t23&=t23 t21 t21=u5 t24=A t24 t25&=x t25 t25,B1,B3,B4,B5,B6,B7,窥孔优化,是指对代码局部进行改进的简单有效的技术。只考虑目标代码中的指令序列，把可能的指令序列替换成为更短更快的指令。冗余指令删除。控制流优化代数化简特殊指令使用,冗余指令删除,多余存取指令的删除：MOV b R0ADD c R0MOV R0 aMOV a R0SUB d R0MOV R0 c第四条指令没有任何效果，可以删除。如果有标号转向第四条指令，则不可以删除。,冗余指令删除,无用代码删除：将不会被执行的代码删除。如果目标代码中有无条