第十章代码优化哈工大王宏志.ppt
117页
第十章第十章 代码优化代码优化 优化的概念优化的概念n编译时刻为改进目标程序的质量而进行的各项工编译时刻为改进目标程序的质量而进行的各项工作n空间效率空间效率n时间效率时间效率n空间效率和时间效率有时是一对矛盾，有时不能空间效率和时间效率有时是一对矛盾，有时不能兼顾n优化的要求：优化的要求：n必须是等价变换必须是等价变换n为优化的努力必须是值得的为优化的努力必须是值得的n有时优化后的代码的效率反而会下降有时优化后的代码的效率反而会下降 优化的分类优化的分类n机器相关性：机器相关性：n机器相关优化：寄存器优化，多处理器优化，特殊机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等指令优化，无用指令消除等n无关的优化：无关的优化：n优化优化范围：范围：n局部优化：单个基本块范围内的优化，常量合并优局部优化：单个基本块范围内的优化，常量合并优化，公共子表达式删除，计算强度削弱和无用代码化，公共子表达式删除，计算强度削弱和无用代码删除n全局优化：主要是基于循环的优化：循环不变优化，全局优化：主要是基于循环的优化：循环不变优化，归纳变量删除，计算强度削减归纳变量删除，计算强度削减。
n优化语言级：优化语言级：n优化语言级：针对中间代码，针对机器语言优化语言级：针对中间代码，针对机器语言 代码优化程序的结构代码优化程序的结构n控制流分析的主要目的是分析出程序的循环结控制流分析的主要目的是分析出程序的循环结构循环结构中的代码的效率是整个程序的效构循环结构中的代码的效率是整个程序的效率的关键率的关键n数据流分析进行数据流信息的收集，主要是变数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息量的值的获得和使用情况的数据流信息n到达到达- -定义分析；活跃变量；可用表达式；定义分析；活跃变量；可用表达式；n代码变换：根据上面的分析，对内部中间代码变换：根据上面的分析，对内部中间代码进行等价变换代码进行等价变换控制流分析控制流分析数据流分析数据流分析代码变换代码变换 基本块和流图基本块和流图n基本块中，控制流是由第一个四元式进基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开入，到达最后一个四元式离开n流图：把一个程序的中间表示中所有的流图：把一个程序的中间表示中所有的基本块作为节点集合有边从节点基本块作为节点集合有边从节点n n到节到节点点n’n’当且仅当控制流可能从当且仅当控制流可能从n n的最后的的最后的一个四元式到达一个四元式到达n’n’的第一个四元式。
的第一个四元式n首节点：对应的基本块的第一个四元式首节点：对应的基本块的第一个四元式是程序的第一个四元式是程序的第一个四元式 流图的构造流图的构造n以所有的基本块为节点集合以所有的基本块为节点集合n有有B1B1到到B2B2的边（的边（B2B2是是B1B1的后继）当且仅的后继）当且仅当：当：nB1B1的最后一个四元式有条件或无条件地转移的最后一个四元式有条件或无条件地转移到到B2B2的第一个四元式的第一个四元式nB2B2是紧紧跟随在是紧紧跟随在B1B1后面的四元式，且后面的四元式，且B1B1的最的最后四元式不是无条件转向语句后四元式不是无条件转向语句 流图的例子流图的例子n在转移语句中，目标标号转变称为基本块的编号，在转移语句中，目标标号转变称为基本块的编号，可以避免因为四元式的变动而引起的麻烦可以避免因为四元式的变动而引起的麻烦1_i=1_f=0_a>=i10B4=f_b+fat1=t1_f=b_a+i1t2=t2_iGOB2=ffibB1B2B3B4 基本块的优化基本块的优化n常量合并常量合并n公共子表达式删除公共子表达式删除n强度削弱强度削弱n无用代码删除无用代码删除 常量合并常量合并n例子：例子：l = 2*3.14*rl = 2*3.14*rn* *2 23.143.14 t1t1n* *t1t1r rt2t2n= =t2t2l ln2*3.14159262*3.1415926的值在编译时刻就可以确定。
的值在编译时刻就可以确定n* *6.286.28 r rt2t2n= =t2t2l l 公共子表达式删除公共子表达式删除n+ +b bc ca a- -a ad db bn+ +b bc cc c- -a ad dd dn显然，第显然，第2 2和和4 4个四元式计算的是同一个值，所以第四个四元式个四元式计算的是同一个值，所以第四个四元式可以修改为可以修改为= =b b_ _d dn对于第对于第1 1和和3 3个四元式，虽然都是计算个四元式，虽然都是计算b+cb+c，但是他们的值其实，但是他们的值其实是不同的，所以不能完成处理是不同的，所以不能完成处理n公共子表达式：如果某个表达式先前已经计算，且从上次计算公共子表达式：如果某个表达式先前已经计算，且从上次计算到现在，到现在，E E中的变量的值没有改变那么中的变量的值没有改变那么E E的这次出现就称为公的这次出现就称为公共子表达式共子表达式n利用先前的计算结果，可以避免对公共子表达式的重复计算利用先前的计算结果，可以避免对公共子表达式的重复计算 例子例子nx+y*t-a*(x+y*t)/(y*t)x+y*t-a*(x+y*t)/(y*t)n* *y yt tt1t1+ +x xt1t1t2t2n* *y yt tt3t3+ +x xt3t3t4t4n* *a at4t4t5t5* *y yt tt6t6n/ /t5t5t1t1t7t7- -t2t2t7t7t8t8n消除公共子表达式之后：消除公共子表达式之后：n* *y yt tt1t1+ +x xt1t1t2t2n* *a at2t2t5t5/ /t5t5t1t1t7t7n- -t2t2t7t7t8t8 强度削弱强度削弱n实现同样的运算可以有多种方式。
用计算实现同样的运算可以有多种方式用计算较快的运算代替较慢的运算较快的运算代替较慢的运算nX X2 2变成变成x*xx*xn2*x2*x或或2.0*x2.0*x变成变成x+xx+xnx/2x/2变成变成x*0.5x*0.5na an nx xn n+a+an-1n-1x xn-1n-1+…+a+…+a1 1x+ax+a0 0变成变成n((…(a((…(an nx+ax+an-1n-1)x+ a)x+ an-2n-2)…)x+a)…)x+a1 1)x+a)x+a0 0 无用代码删除无用代码删除n如果四元式如果四元式opopx xy yz z之后，之后，z z的值的值再也没有被使用到，那么这个四元式是无再也没有被使用到，那么这个四元式是无用的n无用的四元式往往意味着程序的错误，一无用的四元式往往意味着程序的错误，一般不会出现在正确的程序里面般不会出现在正确的程序里面n多数无用四元式是由优化引起的多数无用四元式是由优化引起的n= =t1t1t3t3，如果我们尽量用，如果我们尽量用t1t1替代替代t3t3，可能使，可能使t3t3不被使用，从而这个四元式称不被使用，从而这个四元式称为无用的四元式。
为无用的四元式 等价变换的分类等价变换的分类n保结构等价变换保结构等价变换n删除公共子表达式和删除无用代码，重新命名临删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等时变量和交换独立四元式的顺序等n+ +x xy yt t变成变成+ +x xy yu un+ +a ab bt1t1+ +x xy yt2t2变成变成n+ +x xy yt2t2+ +a ab bt1t1n代数等价变换利用了代数恒等性质，代数等价变换利用了代数恒等性质，n强度削弱强度削弱2x=x+x, B and true = B.2x=x+x, B and true = B.n需要考虑双目运算符的可交换特性需要考虑双目运算符的可交换特性 基本块优化的实现基本块优化的实现n基本块内部优化的实现的主要工具为基本块内部优化的实现的主要工具为DAGDAG图n用用DAGDAG图表示各个值的计算图表示各个值的计算/ /依赖关系依赖关系n图中的标记：图中的标记：n叶子节点的标记为标识符（变量名）或常数作为唯一的标叶子节点的标记为标识符（变量名）或常数作为唯一的标记叶子节点是标识符时，用下标记叶子节点是标识符时，用下标0 0表示它时初值。
表示它时初值n内部节点用运算符号作为标记，表示计算的值每个节点内部节点用运算符号作为标记，表示计算的值每个节点的值都可以用关于变量初始值的表达式表示的值都可以用关于变量初始值的表达式表示n各节点可能附加有一个或者多个标识符同一个节点的标各节点可能附加有一个或者多个标识符同一个节点的标识符表示相同的值识符表示相同的值 DAGDAG图的例子图的例子n+ bcan-adbn+ bccn-add+-+b0c0d0b,da 四元式的分类四元式的分类n0 0型：型：= =x x_ _y yn1 1型：型：opopx x_ _y(y(单目运算）单目运算）n2 2型：型：opopx xy yz zreloprelopx xy yz(zz(z是序号是序号) ) 基本块基本块DAGDAG图构造算法图构造算法n输入：一个基本块输入：一个基本块输出：相应输出：相应DAGDAG图图n算法说明：算法说明：n通过逐个扫描四元式来逐步建立通过逐个扫描四元式来逐步建立DAGDAG图n函数函数node(x)node(x)表示和标识符表示和标识符x x相应的最近建立的节点他代表相应的最近建立的节点他代表扫描到当前的四元式的时候，标识符扫描到当前的四元式的时候，标识符x x的值对应的节点。
的值对应的节点n步骤步骤1 1：初始化：无任何节点，：初始化：无任何节点，nodenode对任何标识符无定义对任何标识符无定义n步骤步骤2 2：依次对基本块中的每个四元式：依次对基本块中的每个四元式op x y zop x y z执行如下步骤执行如下步骤n如果如果node(x)node(x)没有定义，建立叶子节点，标记为没有定义，建立叶子节点，标记为x x，让，让node(x) node(x) 等于这个节点如果等于这个节点如果node(y)node(y)没有定义，为没有定义，为y y建立节点建立节点n如果四元式为如果四元式为0 0型，型，n=node(x);n=node(x);n如果四元式为如果四元式为1 1型，寻找标记为型，寻找标记为opop且子节点为且子节点为node(x)node(x)的节点，的节点，如果找不到，建立这样的节点如果找不到，建立这样的节点n n 基本块基本块DAGDAG图构造算法（续）图构造算法（续）n对于对于2 2型四元式，查看是否存在标记为型四元式，查看是否存在标记为opop的节点，且其左右的节点，且其左右子节点分别为子节点分别为node(x)node(x)和和node(y)node(y)。
如果找不到，建立这样如果找不到，建立这样的节点的节点n nn步骤步骤3 3：如果：如果z z为标识符，从为标识符，从node(z)node(z)中删除标识符中删除标识符z z，并把，并把z z加加入到找到或者建立的节点入到找到或者建立的节点n n的标识符表中，并设置的标识符表中，并设置node(z)node(z)为为n nn说明：说明：n处理处理2 2型四元式的时候，如果型四元式的时候，如果opop是可交换的运算符，是可交换的运算符，可以允许其左右节点可以互换可以允许其左右节点可以互换 生成生成DAGDAG图的例子图的例子n*4it1=[]at1t2n*4it3=[]bt3t4n*t2t4t5+prodt5t6n=t6prod+i1t7n=t7i<=i20(3)a4i*=[]=[]b*+prod01+20<= DAGDAG图的应用图的应用n公共子表达式：构造中，寻找是否有标记为公共子表达式：构造中，寻找是否有标记为opop且子节点为且子节点为node(x), node(y)node(x), node(y)的节点时，自然的节点时，自然完成了公共子表达式的寻找完成了公共子表达式的寻找n在基本块中，其值被引用的标识符：构造了叶在基本块中，其值被引用的标识符：构造了叶子节点的标识符。
子节点的标识符n结果能够在基本块外被引用的四元式结果能够在基本块外被引用的四元式op x y zop x y z设它对应的节点为设它对应的节点为n n，如果，如果DAGDAG图构造结束的时图构造结束的时候，候，n n的标志符表不为空的标志符表不为空 []=[]=和和&=&=运算符的处理运算符的处理n对数组的赋值需要特别的处理，这是因为数组的下标是变量对数组的赋值需要特别的处理，这是因为数组的下标是变量对于数组元素的赋值可能改变数组中任何一个元素的值对于数组元素的赋值可能改变数组中任何一个元素的值n=[]=[] A Ai it1t1 []=[]=A Aj jt2t2n&=&=y yt2t2t2t2=[]=[]A Ai it3t3nA[i]A[i]并不是公共子表达式并不是公共子表达式n在处理对数组在处理对数组A A的元素的赋值四元式的时候，应该注销所有以的元素的赋值四元式的时候，应该注销所有以= =[][]为标记，为标记，A A为左节点的节点从而不可能在此节点的标识符为左节点的节点从而不可能在此节点的标识符表中再附上其他的标识符表中再附上其他的标识符n处理对指针所指空间的赋值的时候，同样要注销相应的节点。
处理对指针所指空间的赋值的时候，同样要注销相应的节点如果不能确定指针指向的范围，那么，需要注销所有的节点如果不能确定指针指向的范围，那么，需要注销所有的节点Ai=[]j[]=t1t2y&==[] 从从DAGDAG图到四元式序列图到四元式序列n在在DAGDAG图中，有些运算已经进行了合并图中，有些运算已经进行了合并n如果不考虑如果不考虑[]=[]=和和&=&=算符，可以依照算符，可以依照DAGDAG图中的拓扑排序得到的次序进行但是，图中的拓扑排序得到的次序进行但是，有了有了[]=[]=和和&=&=算符之后，计算的次序必须算符之后，计算的次序必须修正n实际上，我们可以按照各个节点生成的实际上，我们可以按照各个节点生成的顺序来从顺序来从DAGDAG图生成四元式序列图生成四元式序列 从从DAGDAG重建四元式序列算法重建四元式序列算法n按照按照DAGDAG图中各个节点的生成次序对每个节点作如下处理：图中各个节点的生成次序对每个节点作如下处理：n若是叶子节点，且附加标识符表为空，不生成四元式若是叶子节点，且附加标识符表为空，不生成四元式n若是叶子节点，标记为若是叶子节点，标记为x x，附加标识符为，附加标识符为z z，生成，生成= = x z x z。
n若是内部节点，附加标识符为若是内部节点，附加标识符为z z，根据其标记，根据其标记opop和子节点和子节点数目，生成下列数目，生成下列4 4种形式的四元式种形式的四元式nOpOp不是不是=[]=[]或者或者[]=[]=，也不是，也不是reloprelop，有两个子节点，，有两个子节点，生成生成 opopx xy yz zn如果是如果是=[]=[]或者或者[]=[]=，生成，生成opopx xy yz zn如果是如果是reloprelop，生成，生成reloprelop x xy yz z，，z z是是基本块序号基本块序号n只有一个子节点，生成只有一个子节点，生成opopx x_ _z z 从从DAGDAG重建四元式序列算法重建四元式序列算法( (续续) )n若是内部节点，且无附加标识符，则添加一个局部于本基本若是内部节点，且无附加标识符，则添加一个局部于本基本块的临时性附加标识符，按照上一情况生成块的临时性附加标识符，按照上一情况生成n如果节点的标识符重包含多个附加标识符如果节点的标识符重包含多个附加标识符z1,z2,…,z1,z2,…,zkzk时：时：n若是叶子节点，标记为若是叶子节点，标记为z z，生成一系列四元式，生成一系列四元式n= =z zz1z1n= =z zz2z2n………………n= =z zznznn不是叶子节点，生成四元式序列：不是叶子节点，生成四元式序列：n= =z zz2z2n………………n= =z zznzn 使用使用DAGDAG图进行优化的例子图进行优化的例子( (四元式序列四元式序列) )n四元式序列片断四元式序列片断: :n* *4 4i it10t10=[]=[]A At10t10t11t11n= =t11t11x x* *4 4i it12t12n[]=[]=A At12t12t13t13* *4 4j jt14t14n=[]=[]A At14t14t15t15&=&=t15t15t13t13t13t13n* *4 4j jt16t16[]=[]=A At16t16t17t17n&=&= x xt17t17t17t17<
生成2pir0 与循环有关的优化与循环有关的优化n循环不变表达式外提循环不变表达式外提n归纳变量删除归纳变量删除n计算强度削弱计算强度削弱 循环不变式（代码）外提循环不变式（代码）外提n有些表达式位于循环之内，但是该表达有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，式的值不随着循环的重复执行而改变，该表达式被称为循环的不变表达式该表达式被称为循环的不变表达式n如果按照前面讲的代码生成方案，每一如果按照前面讲的代码生成方案，每一次循环都讲计算一次次循环都讲计算一次n如果把这个表达式提取到循环外面，该如果把这个表达式提取到循环外面，该计算就只被执行一次从而可以获得更计算就只被执行一次从而可以获得更加好的效率加好的效率 循环不变式的例子循环不变式的例子n计算半径为计算半径为r r的从的从1010度到度到360360度的扇形的面积：度的扇形的面积：nfor(n=1; n<36; n++)for(n=1; n<36; n++)n{S:=10/360*pi*r*r*n; {S:=10/360*pi*r*r*n; printf(“Areaprintf(“Area is %f”, S); } is %f”, S); }n显然，表达式显然，表达式10/360*pi*r*r10/360*pi*r*r中的各个量在循环过程中不改中的各个量在循环过程中不改变。
可以修改程序如下：变可以修改程序如下：nC= 10/360*pi*r*r*n; C= 10/360*pi*r*r*n; nfor(n=1; n<36; n++)for(n=1; n<36; n++)n{S:=C*n; {S:=C*n; printf(“Areaprintf(“Area is %f”, S); } is %f”, S); }n修改后的程序中，修改后的程序中，C C的值只需要被计算一次，而原来的程序的值只需要被计算一次，而原来的程序需要计算需要计算3636次 四元式的循环不变式四元式的循环不变式n(1)=(1)= 1 1n n (2)> (2)>n n3636(21)(21)n(3)GOF(3)GOF(4)(4)(4)(4)/ /1010360360tltln(5)*(5)* tltlpipit2t2(6)*(6)*t2t2r rt3t3n(7)*(7)* t3 t3r rt4t4(8)*(8)*t4t4n nt5t5n(9)=(9)= t5 t5S S……………………n(18)+ n(18)+ n1 1t9t9(19)=(19)=t9t9n nn(20)GO(20)GO(4)(4)(21)(21)n其中，四元式其中，四元式4,5,6,74,5,6,7是循环不变四元式。
是循环不变四元式 循环不变四元式的相对性循环不变四元式的相对性n对于多重嵌套的循环，循环不变四元式是相对于某个对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的可能对于更加外层的循环，它就不是循循环而言的可能对于更加外层的循环，它就不是循环不变式环不变式n例子：例子：for(i = 1; i<10; i++)for(i = 1; i<10; i++)for(n=1; n<360/(5*i); n++)for(n=1; n<360/(5*i); n++){S:=(5*i)/360*pi*r*r*n;...}{S:=(5*i)/360*pi*r*r*n;...}n5*i5*i和和(5*i)/360*pi*r*r(5*i)/360*pi*r*r对于对于n n的循环（内层循环）是的循环（内层循环）是不变表达式，但是对于外层循环，它们不是循环不变不变表达式，但是对于外层循环，它们不是循环不变表达式 循环不变表达式优化需要循环不变表达式优化需要解决的问题解决的问题n如何识别循环中的不变表达式？如何识别循环中的不变表达式？n把循环表达式外提到什么地方？把循环表达式外提到什么地方？n什么条件下，不变表达式可以外提？什么条件下，不变表达式可以外提？ 归纳变量的删除（例子）归纳变量的删除（例子）n例子：例子：Prod=0; i = 1;Prod=0; i = 1;for(i = 1; i<= 20; i++)for(i = 1; i<= 20; i++)prod += prod+A[4*i]*B[4*i];prod += prod+A[4*i]*B[4*i];n*4it1=[]at1t2* 4it3=[]bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i<= i20B2ni i作为计数器。
每次重复，作为计数器每次重复，i i的值增加的值增加1 1，而，而A[i], B[i]A[i], B[i]对应的地址对应的地址t1, t3t1, t3增加增加4 4n我们可以删除我们可以删除i i，而使用，而使用t1t1或者或者t3t3进行循环结束条件的测试进行循环结束条件的测试 归纳变量的删除归纳变量的删除n在循环中，如果变量在循环中，如果变量i i的值随着循环的每的值随着循环的每次重复都固定地增加或者减少某个常量，次重复都固定地增加或者减少某个常量，则称则称i i为循环的归纳变量为循环的归纳变量n如果在一个循环中有多个归纳变量，归如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少纳变量的个数往往可以减少，甚至减少到到1 1个减少归纳变量的优化称为归纳变个减少归纳变量的优化称为归纳变量的删除量的删除 归纳变量的删除（四元式例子）归纳变量的删除（四元式例子）=0prod=li*4it1=[]at1t2*4it3=[]bt3t4*t2t4t5+prodt5t6=t6prod+i1t7=t7i<=i20B2=0prod=0t1+4t1t1+4t3t3=[]at1t2=[]bt3t4*t2t4t5+prodt5t6=t6prod<=t180B2 归纳变量的删除归纳变量的删除n归纳变量的删除一方面可以删除变量，归纳变量的删除一方面可以删除变量，减少四元式，另外，删除归纳变量同时减少四元式，另外，删除归纳变量同时也削减了计算强度。
也削减了计算强度n为了进行归纳变量删除优化，必要的是为了进行归纳变量删除优化，必要的是找出归纳变量找出归纳变量 计算强度削弱计算强度削弱n在删除归纳变量的过程中在删除归纳变量的过程中, ,已经将一些乘已经将一些乘法运算转换成为加法运算法运算转换成为加法运算n还有一类经常可以被应用的是对于下标还有一类经常可以被应用的是对于下标变量地址的计算变量地址的计算 计算强度削减（下标变量）计算强度削减（下标变量）n对于数组对于数组T Ta[n1][n2]…[nm]a[n1][n2]…[nm]，其下标变量，其下标变量a[i1][i2][i3]…[a[i1][i2][i3]…[imim] ]的地址计算如下：的地址计算如下：nbase+dbase+d；其中；其中basebase为为a[0][0]…[0]a[0][0]…[0]的地址nd=((…((i1*n2+i2)*n3+i3)…)*d=((…((i1*n2+i2)*n3+i3)…)*nm+imnm+im)*)*sizeof(Tsizeof(T););n当满足某些情况的时候，地址的计算可以使用当满足某些情况的时候，地址的计算可以使用加法来代替乘法加法来代替乘法。
下标变量计算强度的削减（例子）下标变量计算强度的削减（例子）nfor(v1=v10; v1 被重置）n显然我们可以这样计算显然我们可以这样计算A[i1][i2][i3]A[i1][i2][i3]的地址：的地址：n在循环开始的时候，设置初值在循环开始的时候，设置初值d1=(base+C0’)+C1’*V10;d1=(base+C0’)+C1’*V10;n在进入外层循环后，进入内存循环前，设置在进入外层循环后，进入内存循环前，设置d2=d1+C2’*V20d2=d1+C2’*V20n在内存循环，使用在内存循环，使用d2d2作为地址获取作为地址获取A[i1][i2][i3]A[i1][i2][i3]的值n内存循环体每次运行结束之前，将内存循环体每次运行结束之前，将d2d2的值增加的值增加C2’C2’n每次外层循环体运行结束之前，将每次外层循环体运行结束之前，将d1d1的值增加的值增加C1’C1’n显然，对于显然，对于A[i1][i2][i3]A[i1][i2][i3]的地址计算变成了加法运算的地址计算变成了加法运算 下标变量计算强度的削减结果下标变量计算强度的削减结果D1 = base+C0+C1’*V10;for(v1=v10; v1 都是常量n下标变量中的下标表达式是循环控制变下标变量中的下标表达式是循环控制变量的线性表达式量的线性表达式n满足上述条件的称为可优化下标变量满足上述条件的称为可优化下标变量n在在C C语言中，要求循环控制变量每次循环语言中，要求循环控制变量每次循环的变动是常数的变动是常数 循环优化的实现循环优化的实现n循环结构的识别循环结构的识别n数据流分析数据流分析n代码转换代码转换 循环结构的识别循环结构的识别n对于源程序来说，识别循环是比较方便的但是代码对于源程序来说，识别循环是比较方便的但是代码的优化是针对四元式序列的，所以识别循环必须针对的优化是针对四元式序列的，所以识别循环必须针对流图进行流图进行n定义定义8.38.3如果流图中，从某个初始节点出发，每一如果流图中，从某个初始节点出发，每一条到达节点条到达节点n n的路径都必须经过的路径都必须经过m m，那么称，那么称m m是节点是节点n n的的必经节点记为必经节点记为m m domdom n nn任何节点都是自己的必经节点任何节点都是自己的必经节点nm m为为n n的前驱，的前驱，n n为为m m的后继n直接必经节点：从初始节点到达直接必经节点：从初始节点到达n n的所有路径上，节点的所有路径上，节点n n的最后一个必经节点称为直接必经节点。 的最后一个必经节点称为直接必经节点 循环满足的条件循环满足的条件n循环必须有唯一的入口节点，称为首节点循环必须有唯一的入口节点，称为首节点n对于循环中任何一个节点，必定至少有一个对于循环中任何一个节点，必定至少有一个路径回到首节点路径回到首节点 回边和自然循环回边和自然循环n定义定义8.4 8.4 假定流图中存在两个节点假定流图中存在两个节点M M和和N N满足满足M M domdom N N如果存在从节点如果存在从节点N N到到M M的有向边的有向边N-N->M>M，那么这条边称为回边那么这条边称为回边n定义定义8.5 8.5 在流图中，给定一个回边在流图中，给定一个回边N->MN->M，对，对应与这个回边的自然循环为：应与这个回边的自然循环为：M M，以及所有，以及所有可以不经过可以不经过M M而到达而到达N N的节点M M为该循环的为该循环的首节点n用节点的集合表示自然循环用节点的集合表示自然循环 自然循环的例子自然循环的例子n3 3 domdom 4 4n回边回边4->34->3n4 4 domdom 7 7n回边回边7->47->4n10->710->7的自然循环的自然循环{7{7，，8 8，，10}10}n7->47->4的自然循环的自然循环{4,5,6,7,8,10}{4,5,6,7,8,10}n4->34->3，，8->38->3的自的自然循环然循环{3,4,5,6,7,8,10{3,4,5,6,7,8,10} }12345678910 回边寻找算法回边寻找算法n首先列出所有从首节点开始，不带圈的首先列出所有从首节点开始，不带圈的路径。 路径n节点节点N N的必经节点的集合为满足以下条件的必经节点的集合为满足以下条件的节点的节点M M：：n所有包含所有包含N N的路径的路径P, MP, M都在都在N N的前面出现的前面出现n回边集合如下：回边集合如下：n{N-->M | N{N-->M | N是一个节点，是一个节点，M M在在N N的必经节点集的必经节点集合中合中} } 寻找自然循环的算法寻找自然循环的算法n输入输入: :回边回边{N->M}; {N->M}; 输出输出: : 回边对应的自然循环回边对应的自然循环. .n算法算法: :设置设置loop={N,M};loop={N,M};push(stack, N);push(stack, N);while non-empty(stack) dowhile non-empty(stack) do{m = top(stack); pop(stack);{m = top(stack); pop(stack);for mfor m的每个前驱节点的每个前驱节点p p {if p is_not_in loop then {if p is_not_in loop then {loop += p; push(stack,p);{loop += p; push(stack,p);} }} } 算法的说明算法的说明n节点节点M M在初始时刻已经在在初始时刻已经在looploop中所以中所以, M, M的前驱不可能被加入到的前驱不可能被加入到looploop中。 中n如果如果N->MN->M不是回边，那么，首节点会被不是回边，那么，首节点会被加入到加入到looploop中此时算法不能得到自然中此时算法不能得到自然循环 相关概念相关概念n通常，循环互不相交，或者一个在另外一个里面通常，循环互不相交，或者一个在另外一个里面n内循环：不包含其他循环的循环称为内循环内循环：不包含其他循环的循环称为内循环n如果两个循环具有相同的首节点，那么很难说一个包如果两个循环具有相同的首节点，那么很难说一个包含另外一个此时把两个循环合并含另外一个此时把两个循环合并B0B1B2B3 可归约流图可归约流图n可归约流图：删除了其中回边之后，可归约流图：删除了其中回边之后，可以构成无环有向图的流图可以构成无环有向图的流图n特性：不存在循环外向循环内部特性：不存在循环外向循环内部的转移，进入循环必须通过其首的转移，进入循环必须通过其首节点n实际的程序对应的流图一般都是可实际的程序对应的流图一般都是可归约的流图归约的流图n没有没有gotogoto语句的结构化程序的流图语句的结构化程序的流图总是可归约的一般使用总是可归约的一般使用gotogoto语句语句的程序也是可归约的的程序也是可归约的。 B1B2B3 数据流分析相关概念数据流分析相关概念n变量获得值的方式：变量获得值的方式：n通过赋值语句；通过赋值语句；n通过输入语句；通过输入语句；n通过过程形式参数；通过过程形式参数；n点：流图基本块中的位置，包括：第一个四元式之前，两点：流图基本块中的位置，包括：第一个四元式之前，两个相邻四元式之间，和最后的四元式之间个相邻四元式之间，和最后的四元式之间n定值：使变量定值：使变量x x获得值的四元式称为对获得值的四元式称为对x x的定值，一般用四的定值，一般用四元式的位置表示元式的位置表示n引用点：引用某个变量引用点：引用某个变量x x的四元式的位置称为的四元式的位置称为x x的引用点的引用点 数据流分析的种类数据流分析的种类n到达到达- -定义数据流方程定义数据流方程n活跃变量数据流方程活跃变量数据流方程n可用表达式数据流方程可用表达式数据流方程 到达到达- -定义数据流方程定义数据流方程n到达到达- -定义：假定定义：假定x x有定义有定义d d，如果存在一个路径，从紧，如果存在一个路径，从紧随随d d的点到达某点的点到达某点p p，并且此路径上面没有被注销，则，并且此路径上面没有被注销，则称称x x的定义的定义d d到达到达p p。 这表明，在这表明，在p p点使用变量点使用变量x x的时候，的时候，x x的值可能是由的值可能是由d d点赋予的点赋予的n引用引用- -定义链：设变量定义链：设变量x x有一个引用点有一个引用点u u，变量，变量x x的所有的所有能过到达能过到达u u的一切定义称为的一切定义称为x x在在u u点处的引用点处的引用- -定义链，定义链，简称简称udud链n显然，通过变量显然，通过变量x x在引用点在引用点u u的的udud链，可以判断链，可以判断x x是否循是否循环不变的环不变的 到达定义数据流方程（记号）到达定义数据流方程（记号）nIN[B]: IN[B]: 表示基本块表示基本块B B的入口点处各个变量的定点集合的入口点处各个变量的定点集合n如果如果B B中点中点p p之前有之前有x x的定义点的定义点d d，且这个定义能够到达，且这个定义能够到达p p，则点，则点p p处处x x的的udud链是链是{d}{d}n否则，点否则，点p p处处x x的的udud链就是链就是IB[B]IB[B]中关于中关于x x的定义点的集合的定义点的集合nP[B]P[B]：：B B的所有前驱基本块的集合。 的所有前驱基本块的集合nGEN[B]GEN[B]：各个变量在：各个变量在B B内定义，并能够到达内定义，并能够到达B B的出口点的所的出口点的所有定义的集合有定义的集合nOUT[B]OUT[B]：各个变量的能够到达基本块：各个变量的能够到达基本块B B的出口点的所有定的出口点的所有定义的集合义的集合nKILL[B]KILL[B]：是各个变量在基本块：是各个变量在基本块B B中重新定义，即在此块内中重新定义，即在此块内部被注销的定义点的集合部被注销的定义点的集合 到达定义数据流方程到达定义数据流方程nIN[B] = ∪IN[B] = ∪OUT[pOUT[p] where p ] where p isinisin P[B] P[B]nOUT[B] = GEN[B]∪(IN[B]-KILL[B])OUT[B] = GEN[B]∪(IN[B]-KILL[B])n其中：其中：nGEN[B]GEN[B]可以从基本块中求出：使用可以从基本块中求出：使用DAGDAG图就可以得图就可以得到nKILL[B]KILL[B]中，对于整个流图中的所有中，对于整个流图中的所有x x的定义点，如的定义点，如果果B B中有对中有对x x的定义，那么该定义点在的定义，那么该定义点在KILL[B]KILL[B]中。 中 方程求解算法方程求解算法n使用迭代方法使用迭代方法初始值设置为：初始值设置为：IN[Bi]=IN[Bi]=空；空；OUT[B]=GEN[Bi];OUT[B]=GEN[Bi];change = TRUE;change = TRUE;while(change)while(change){ {change = FALSE;change = FALSE;for each B dofor each B do{IN[B] = {IN[B] = ∪∪OUT[pOUT[p] where p ] where p isinisin P[B]; P[B]; OUT[B] = GEN[B] OUT[B] = GEN[B]∪∪(IN[B]-KILL[B]);(IN[B]-KILL[B]); oldoutoldout = OUT[B]; = OUT[B]; if(OUT[B] != if(OUT[B] != oldoutoldout) change = TRUE;}) change = TRUE;}} } 算法例子算法例子nGEN[B1]={d1,d2,d3}nKILL[B1]={d4,d5,d6,d7}nGEN[B2]={d4,d5}nKILL[B2]={d1,d2,d7}nGEN[B3]={d6}nKILL[B3]={d3}nGEN[B4]={d7}nKILL[B4]={d1,d4}d1: -m1id2: =njd3: =u2ad4: +i1id5: -j1jd6: =u2ad7: =u3iB1B2B3B4 计算过程计算过程n初始化：初始化：nIN[B1] = IN[B2] = IN[B3] = IN[B4] =IN[B1] = IN[B2] = IN[B3] = IN[B4] =空空nOUT[B1]={d1,d2,d3}, OUT[B2]={d4,d5}OUT[B1]={d1,d2,d3}, OUT[B2]={d4,d5}nOUT[B3]={d6}, OUT[B4]={d7}.OUT[B3]={d6}, OUT[B4]={d7}.n第一次循环：第一次循环：nIN[B1]=IN[B1]=空空; IN[B2] ={d1,d2,d3,d7}; IN[B3]={d4,d5};; IN[B2] ={d1,d2,d3,d7}; IN[B3]={d4,d5};nIN[B4]={d4,d5,d6}; OUT[B1]={d1,d2,d3};IN[B4]={d4,d5,d6}; OUT[B1]={d1,d2,d3};nOUT[B2]={d3,d4,d5}…OUT[B2]={d3,d4,d5}…n结果：结果：nIN[B1]=IN[B1]=空；空；OUT[B1]={d1,d2,d3};OUT[B1]={d1,d2,d3};nIN[B2]={d1,d2,d3,d5,d6,d7}; OUT[B2]={d3,d4,d5,d6};IN[B2]={d1,d2,d3,d5,d6,d7}; OUT[B2]={d3,d4,d5,d6};nIN[B3]={d3,d4,d5,d6};IN[B3]={d3,d4,d5,d6};OUT[B3]={d4,d5,d6};OUT[B3]={d4,d5,d6};nIN[B4]={d3,d4,d5,d6}; OUT[B4]={d3,d5,d6,d7};IN[B4]={d3,d4,d5,d6}; OUT[B4]={d3,d5,d6,d7}; 活跃变量数据流方程活跃变量数据流方程n判断在基本块出口之后，变量的值是否还被引用的这判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为活跃变量分析。 种判断工作称为活跃变量分析n消除复写四元式的依据就是对活跃变量的分析如果消除复写四元式的依据就是对活跃变量的分析如果某个变量的值在以后不被引用，那么该复写四元式可某个变量的值在以后不被引用，那么该复写四元式可以被消除以被消除n对于变量对于变量x x和流图上的某个点和流图上的某个点p p，存在一条从，存在一条从p p开始的开始的路径，在此路径上在对路径，在此路径上在对x x定值之前引用变量定值之前引用变量x x的值，则的值，则称变量称变量x x在点在点p p是活跃变量，否则称是活跃变量，否则称x x在点在点p p不活跃n无用赋值：对于无用赋值：对于x x在点在点p p的定值，在所有基本块内不被的定值，在所有基本块内不被引用，且在基本块出口之后又是不活跃的，那么引用，且在基本块出口之后又是不活跃的，那么x x在在点点p p的定义是无用的的定义是无用的 记号记号nL_IN[B]: L_IN[B]: 基本块基本块B B的入口点的活跃变量集合的入口点的活跃变量集合nL_OUT[B]: L_OUT[B]: 是在基本块是在基本块B B的出口点的活跃变量集的出口点的活跃变量集合nL_DEF[B]: L_DEF[B]: 是在基本块是在基本块b b内的定值，但是在定义内的定值，但是在定义前在前在B B中没有被引用的变量的集合。 中没有被引用的变量的集合nL_USE[B]: L_USE[B]: 表示在基本块中引用，但是引用前表示在基本块中引用，但是引用前在在B B中没有被定义的变量集合中没有被定义的变量集合n其中，其中，L_DEF[B]L_DEF[B]和和L_USE[B]L_USE[B]是可以从基本块是可以从基本块B B中中直接求得的量，因此在方程中作为已知量直接求得的量，因此在方程中作为已知量 活跃变量数据流方程活跃变量数据流方程nL_IN[B] = L_USE[B]∪(L_OUT[B]-L_DEF[B])L_IN[B] = L_USE[B]∪(L_OUT[B]-L_DEF[B])nL_OUT[B] = ∪L_OUT[B] = ∪L_IN[sL_IN[s] ]，其中，其中s s遍历遍历B B的所有后继的所有后继n变量在某点活跃，表示变量在该点的值在以后会被使用变量在某点活跃，表示变量在该点的值在以后会被使用n第一个方程表示：第一个方程表示：n如果某个变量在如果某个变量在B B中没有定义就使用了，显然，变量在在中没有定义就使用了，显然，变量在在入口处的值会被使用入口处的值会被使用n如果这个变量在如果这个变量在B B的出口处活跃，并且的出口处活跃，并且B B中没有对他进行定中没有对他进行定义，那么变量在入口处也是活跃的。 义，那么变量在入口处也是活跃的n第二个方程表示：第二个方程表示：n在在B B的某个后记中会使用该后继的入口处的值，那么他其的某个后记中会使用该后继的入口处的值，那么他其实也可能使用实也可能使用B B的出口处的值的出口处的值 活跃变量数据流方程求解活跃变量数据流方程求解n设置初值：设置初值：L_IN[Bi]=L_IN[Bi]=空空; ;n重复执行一下步骤直到重复执行一下步骤直到L_IN[Bi]L_IN[Bi]不再改变：不再改变：for(i=1; i 第三次循环各个值不再改变，完成求解 可用表达式数据流方程可用表达式数据流方程n如果一个流图的首节点到达点如果一个流图的首节点到达点p p的每个路径上面都有对的每个路径上面都有对x x op yop y的计算，并且在最后一个这样的计算到点的计算，并且在最后一个这样的计算到点p p之间没之间没有对有对x,yx,y进行定值，那么表达式进行定值，那么表达式x op yx op y在点在点p p是可用的是可用的n表达式可用的直观意义：在点表达式可用的直观意义：在点p p上，上，x op yx op y已经在之前已经在之前被计算过，不需要重新计算被计算过，不需要重新计算n注意：如果对于有间接赋值四元式的情况，需要保证最注意：如果对于有间接赋值四元式的情况，需要保证最后的计算后的计算x op yx op y的点之间不会间接改变的点之间不会间接改变x,x,或者或者y y的值：的值：比如指针不会指向比如指针不会指向x x或者或者y y的存储区域，特别是当的存储区域，特别是当x x为某为某个数组的时候个数组的时候n书上的讲解是针对没有间接赋值四元式的情况处理的书上的讲解是针对没有间接赋值四元式的情况处理的。 概念概念n对表达式的注销：如果某个基本块对表达式的注销：如果某个基本块B B对对x x或者或者y y定值，且以后没有重新计算定值，且以后没有重新计算x op yx op y，那么称，那么称B B注销表达式注销表达式x op yx op yn表达式的产生：如果某个基本块表达式的产生：如果某个基本块B B对对x op yx op y进进行计算，而以后并没有在对行计算，而以后并没有在对x x或者或者y y重新定值，重新定值，那么称那么称B B产生表达式产生表达式x op yx op yn表达式的全集：在计算某个流图中的可用表达表达式的全集：在计算某个流图中的可用表达式的时候，表达式的讨论范围被限定在该出现式的时候，表达式的讨论范围被限定在该出现在流图中的四元式对应的表达式在流图中的四元式对应的表达式 记号记号nE_OUT[B]E_OUT[B]：在基本块出口处的可用表达式集合在基本块出口处的可用表达式集合nE_IN[B]E_IN[B]：在基本块入口处的可用表达式集合在基本块入口处的可用表达式集合nE_GEN[B]E_GEN[B]：基本块：基本块B B所产生的可用表达式的集合所产生的可用表达式的集合。 nE_KILL[B]E_KILL[B]：基本块：基本块B B所注销掉的可用表达式的集合所注销掉的可用表达式的集合nE_GEN[B]E_GEN[B]和和E_KILL[B]E_KILL[B]的值可以直接从流图计算出来的值可以直接从流图计算出来因此在数据流方程中，可以将因此在数据流方程中，可以将E_GEN[B]E_GEN[B]和和E_KILL[B]E_KILL[B]当作已知量看待当作已知量看待 E_GEN[B]E_GEN[B]的计算的计算n对于一个基本块对于一个基本块B B，，E_GEN[B]E_GEN[B]的计算过程的计算过程如下：如下：n初始设置：初始设置：E_GEN[B]=E_GEN[B]=空；空；n顺序扫描每个四元式：顺序扫描每个四元式：n对于四元式对于四元式op x y zop x y z，把，把x op yx op y加入加入E_GEN[B]E_GEN[B]，，n从从E_GEN[B]E_GEN[B]中删除和中删除和z z相关的表达式相关的表达式n最后的最后的E_GEN[B]E_GEN[B]就是相应的集合就是相应的集合 E_KILL[B]E_KILL[B]的计算的计算n设流图的表达式全集为设流图的表达式全集为E;E;n初始设置：初始设置：EK = EK = 空；空；n顺序扫描基本块的每个四元式：顺序扫描基本块的每个四元式：n对于四元式对于四元式op x y zop x y z，把表达式，把表达式x op yx op y从从EKEK中消除；中消除；n把把E E中所有和中所有和z z相关的四元式加入到相关的四元式加入到EKEK中。 中n扫描完所有的四元式之后，扫描完所有的四元式之后，EKEK就是所求的就是所求的E_KILL[B]E_KILL[B] 数据流方程数据流方程1.1.E_OUT[B]=(E_IN[B]-E_KILL[B])U E_GEN[B]E_OUT[B]=(E_IN[B]-E_KILL[B])U E_GEN[B]2.2.E_IN[B]= ∩E_OUT[p] B!=B1, pE_IN[B]= ∩E_OUT[p] B!=B1, p是是B B的前驱3.3.E_IN[B1]=E_IN[B1]=空集空集n说明：说明：n在程序开始的时候，无可用表达式在程序开始的时候，无可用表达式3)(3)n一个表达式在某个基本块的入口点可用，必一个表达式在某个基本块的入口点可用，必须要求它在所有前驱的出口点也可用须要求它在所有前驱的出口点也可用2 2））n一个表达式在某个基本块的出口点可用，或一个表达式在某个基本块的出口点可用，或者该表达式是由它的产生的；或者该表达式者该表达式是由它的产生的；或者该表达式在入口点可用，且没有被注销掉在入口点可用，且没有被注销掉1 1））Bp2p1p3INOUTGEN-KILL 方程求解算法方程求解算法n迭代算法迭代算法n初始化：初始化：E_IN[B1]=E_IN[B1]=空空; ; E_OUT[B1]=E_GEN[B1];E_OUT[Bi]=U-E_OUT[B1]=E_GEN[B1];E_OUT[Bi]=U-E_KILL[Bi](i>=2)E_KILL[Bi](i>=2)n重复执行下列算法直到重复执行下列算法直到E_OUTE_OUT稳定稳定: :FORFOR（（i=2; i<=n ;i++)i=2; i<=n ;i++){ {E_IN[Bi]= ∩E_OUT[p], pE_IN[Bi]= ∩E_OUT[p], p是是BiBi的前驱；的前驱；E_OUT[Bi]=E_GEN[Bi] ∪(E_IN[Bi]-E_KILL[Bi]);E_OUT[Bi]=E_GEN[Bi] ∪(E_IN[Bi]-E_KILL[Bi]);} } 算法说明算法说明n初始化值和前面的两个算法不同。 初始化值和前面的两个算法不同E_OUT[Bi]E_OUT[Bi]的初值大于实际的值的初值大于实际的值n在迭代的过程中，在迭代的过程中，E_OUT[Bi]E_OUT[Bi]的值逐渐缩的值逐渐缩小直到稳定小直到稳定nU U表示四元式的全集，就是四元式序列中表示四元式的全集，就是四元式序列中所有表达式所有表达式x op yx op y的集合 寻找循环不变表达式算法寻找循环不变表达式算法n输入：循环输入：循环L L，已经建立的，已经建立的UDUD链链n输出：不变四元式输出：不变四元式n步骤步骤1 1：若四元式的运算分量或者是常数，或者其：若四元式的运算分量或者是常数，或者其所有定义点在循环外部，则标记此四元式为不变所有定义点在循环外部，则标记此四元式为不变n步骤步骤2 2：重复执行下面的步骤：：重复执行下面的步骤：n如果一个四元式没有被加过标记，且运算分量要么是常如果一个四元式没有被加过标记，且运算分量要么是常数，要么其数，要么其UDUD链中的定义点在循环外，或者该定义点已链中的定义点在循环外，或者该定义点已经被加过标记，则标记此四元式为不变经被加过标记，则标记此四元式为不变n说明：一个四元式的是不变的，当且仅当其分量在说明：一个四元式的是不变的，当且仅当其分量在循环中是不变的。 主要有三种情况：常量，定义点循环中是不变的主要有三种情况：常量，定义点在循环外部，或者定义点的四元式也是不变的在循环外部，或者定义点的四元式也是不变的 不变四元式外提方法不变四元式外提方法n对于不变四元式，可对于不变四元式，可以在进入循环之前首以在进入循环之前首先计算该四元式的值，先计算该四元式的值，然后在循环内部使用然后在循环内部使用该值n可以将四元式的值外可以将四元式的值外体到紧靠循环之前体到紧靠循环之前首节点 首节点 前置节点 代码外提不合法的情况（代码外提不合法的情况（1 1））= 1 i< u v B3= 2 i+ u 1 u- v 1 v<= v 20 B5 =ij= 1 i< u v B3+ u 1 u- v 1 v<= v 20 B5 =ij= 2 i 代码外提不合法的情况（代码外提不合法的情况（2 2））= 1 i= 3 i< u v B3= 2 i+ u 1 u- v 1 v<= v 20 B5 =ij= 1 i= 3 i< u v B3= 2 i+ u 1 u- v 1 v<= v 20 B5 =ij 代码外提不合法的情况（代码外提不合法的情况（3 3））= 1 i= 0 k< u v B3= i k+ u 1 u= 2 i- v 1 v<= v 20 B5 =ij= 1 i= 0 k= 2 i< u v B3= i k+ u 1 u- v 1 v<= v 20 B5 =ij 不变四元式外提的条件不变四元式外提的条件n不变四元式不变四元式s=op x y zs=op x y z可以外提的可以外提的条件：条件：ns s所在的基本块节点是循环所有出口节点的必所在的基本块节点是循环所有出口节点的必经节点。 出口节点是指有后继节点在循环外的经节点出口节点是指有后继节点在循环外的节点反例：情况节点反例：情况1 1））n循环中循环中z z没有其他的定值点反例：情况没有其他的定值点反例：情况2 2））n循环中循环中z z的引用点仅由的引用点仅由s s到达反例：情况到达反例：情况3 3）） 外提算法外提算法n步骤步骤1 1：寻找一切不变四元式寻找一切不变四元式n步骤步骤2 2：对于找到的每个循环，检查是否：对于找到的每个循环，检查是否满足上面说的三个条件满足上面说的三个条件n步骤步骤3 3：按照不变四元式找出的次序，把：按照不变四元式找出的次序，把所找到的满足上述条件的四元式外提到所找到的满足上述条件的四元式外提到前置节点中前置节点中n如果四元式有分量在循环中定值，只有将定如果四元式有分量在循环中定值，只有将定值点外提后，该四元式才可以外提值点外提后，该四元式才可以外提 循环不变式外提的例子循环不变式外提的例子= 1 i= 0 k1) + 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 =ij1)+ i 1 k2)* 2 k t 关于归纳变量的优化关于归纳变量的优化n基本归纳变量：如果循环中，对于基本归纳变量：如果循环中，对于i i的定值只的定值只有形状如有形状如i = i + ci = i + c的定值，那么的定值，那么i i称为循环的称为循环的基本归纳变量。 基本归纳变量n归纳变量族：如果循环中对变量归纳变量族：如果循环中对变量j j的定值都是的定值都是形状如形状如j=C1*i+C2j=C1*i+C2，且，且i i为基本归纳变量，那么为基本归纳变量，那么称称j j为归纳变量，且属于为归纳变量，且属于i i族i i属于属于i i族n对于定值为对于定值为C1*i+C2C1*i+C2的的i i族归纳变量族归纳变量j j，我们用，我们用(i,C1, C2)(i,C1, C2)来表示n对于对于i i族的归纳变量族的归纳变量(i,C1, C2)(i,C1, C2)，要求循环内，要求循环内部对此变量进行定值的时候，一定是赋给部对此变量进行定值的时候，一定是赋给C1*i+C2C1*i+C2 例子（源程序）例子（源程序）for(i = 0; i<100; i++)for(i = 0; i<100; i++){ {j = 4*i;j = 4*i; printf(“%iprintf(“%i”, j);”, j);} }n i i是基本归纳变量是基本归纳变量j j是是i i族归纳变量，可以表示为族归纳变量，可以表示为(i, 4, 0)(i, 4, 0) 寻找循环的归纳变量算法寻找循环的归纳变量算法n步骤步骤1 1：扫描循环的四元式，找出所有基本归纳变量。 对应：扫描循环的四元式，找出所有基本归纳变量对应于每个基本归纳变量的三元组如于每个基本归纳变量的三元组如(i,1,0)(i,1,0)n步骤步骤2 2：寻找循环中只有一个赋值的变量：寻找循环中只有一个赋值的变量k k，且对它的定值，且对它的定值为如下形式，为如下形式，k=j*b, k=b*j, k=j/b, k=j+(-)b, k=b+(-)jk=j*b, k=b*j, k=j/b, k=j+(-)b, k=b+(-)j其中其中j j为基本归纳变量，或者已经找到的归纳变量为基本归纳变量，或者已经找到的归纳变量n如果如果j j为基本归纳变量，那么为基本归纳变量，那么k k属于属于j j族k k对应的三元式对应的三元式可以确定可以确定n如果如果j j不是基本归纳变量，且属于不是基本归纳变量，且属于i i族，那么我们还要求：族，那么我们还要求：n循环中对循环中对j j的赋值以及和对的赋值以及和对k k的赋值之间没有对的赋值之间没有对i i的赋的赋值，且值，且n没有没有j j在循环外的定值可以到达在循环外的定值可以到达k k的这个定值点的这个定值点j j的三元式可以相应确定的三元式可以相应确定 算法说明算法说明n关于关于j j不是基本归纳变量的时候，算法中不是基本归纳变量的时候，算法中的两个要求实际上是保证：对的两个要求实际上是保证：对k k进行赋值进行赋值的时候，的时候，j j变量当时的值一定等于变量当时的值一定等于C1*C1*（（i i当时的值）当时的值）+C2+C2。 归纳变量的计算强度削弱算法归纳变量的计算强度削弱算法n对于每个基本归纳变量对于每个基本归纳变量i i，对其族中的每个归纳，对其族中的每个归纳变量变量j(i, c, d)j(i, c, d)执行下列步骤：执行下列步骤：n建立新的临时变量建立新的临时变量t tn用用= =t tj j四元式代替对四元式代替对j j的赋值n对于每个定值对于每个定值i=i+ni=i+n之后，添加之后，添加t=t+c*nt=t+c*nn在前置节点的末尾，添加四元式在前置节点的末尾，添加四元式* * c i tc i t和和+ + t d tt d t使得在循环开始的时候使得在循环开始的时候, t=c*i+t, t=c*i+tn当两个归纳变量具有同样的三元式的时候，可以当两个归纳变量具有同样的三元式的时候，可以只建立一个临时变量只建立一个临时变量 算法的说明算法的说明n在优化过程中，为在优化过程中，为j(i,c,d)j(i,c,d)引入的变量引入的变量t t保证了在任何时刻保证了在任何时刻( (不包括在对不包括在对i i新定值新定值后并且在后并且在t t重新定值前，但是由于两者的重新定值前，但是由于两者的四元式时紧连的）都满足四元式时紧连的）都满足t=c*i+dt=c*i+d。 n如果在某些情况下，程序运行时对如果在某些情况下，程序运行时对j j的定的定值的次数远远少于对值的次数远远少于对i i的定值，经过优化的定值，经过优化的程序需要对的程序需要对t t多次赋值，实际的效率可多次赋值，实际的效率可能降低 归纳变量的删除归纳变量的删除n有些归纳变量的作用就是控制循环的次有些归纳变量的作用就是控制循环的次数如果循环出口处的判断可以使用其数如果循环出口处的判断可以使用其它的变量代替，那么可以删除这些归纳它的变量代替，那么可以删除这些归纳变量 归纳变量的删除算法归纳变量的删除算法n步骤步骤1 1：对于每个基本归纳变量，取：对于每个基本归纳变量，取i i族的某个归纳变量族的某个归纳变量j j（尽（尽量使得量使得c,dc,d简单）把每个对简单）把每个对i i的测试修改称为用的测试修改称为用j j代替nreloprelop i x B i x B修改为修改为reloprelop i c*x+d B i c*x+d Bnreloprelop i1 i2 B i1 i2 B，如果能够找到三元组，如果能够找到三元组(i1, c,d)(i1, c,d)和和(i2,c,d)(i2,c,d)，那么可以将其修改为，那么可以将其修改为reloprelop j1 j2 B( j1 j2 B(假设假设c>0)c>0)。 n如果归纳变量不再被引用，那么可以删除和它相关的四元如果归纳变量不再被引用，那么可以删除和它相关的四元式n如果基本归纳变量在循环出口处活跃，上面的算法不可以如果基本归纳变量在循环出口处活跃，上面的算法不可以直接使用直接使用n步骤步骤2 2：考虑对：考虑对j j的赋值的赋值= t j= t j如果每次对如果每次对j j引用和这个赋引用和这个赋值四元式之间没有任何对值四元式之间没有任何对t t的赋值（此时，每次使用的赋值（此时，每次使用j j的时候都的时候都有有t=j)t=j)，可以在引用，可以在引用j j的地方用的地方用t t代替，同时删除四元式代替，同时删除四元式= t = t j j（如果（如果j j在循环的出口处活跃，需要增加在循环的出口处活跃，需要增加= t j= t j） 全局公共子表达式表达式消除n对于循环中某个四元式对于循环中某个四元式op x y zop x y z，如果在所有到达，如果在所有到达这个四元式的路径上，已经计算了这个四元式的路径上，已经计算了x op yx op y，且计算，且计算之后之后x,yx,y的值再没有修改过，那么显然我们可以使的值再没有修改过，那么显然我们可以使用以前计算得到的值。 用以前计算得到的值n可用表达式表达的就是这个概念可用表达式表达的就是这个概念n如果有四元式如果有四元式op x y zop x y z，且在四元式前，表达式，且在四元式前，表达式x x op yop y可用，那么我们可以用下面的方法优化：在前可用，那么我们可以用下面的方法优化：在前面不同的地方计算面不同的地方计算x op yx op y时，把值记录到同一个临时，把值记录到同一个临时变量时变量u u里面把这个四元式改变为里面把这个四元式改变为= u = u z z 全局公共子表达式删除全局公共子表达式删除n对于四元式对于四元式Q(op x y z)Q(op x y z)，如果，如果x op yx op y再再Q Q之前可用，那么执行如下步骤：之前可用，那么执行如下步骤：n从从Q Q开始逆向寻找，找到所有离开始逆向寻找，找到所有离Q Q最近的计算最近的计算了了x op yx op y四元式n建立新的临时变量建立新的临时变量u un把步骤把步骤1 1中找到的四元式中找到的四元式op x y top x y t用下列用下列四元式代替：四元式代替：op x y uop x y u和和= u = u t t。 n用用= u t= u t替代替代Q Q 全局公共子表达式消除全局公共子表达式消除( (图示图示) )… …* x y t… …… …* x y k… …… …* x y l… …… …* x y u= u k… …… …= u l… …… …* x y u= u t… … 复制四元式的消除复制四元式的消除n中间代码的生成可能产生四元式中间代码的生成可能产生四元式n消除公共子表达式和删除归纳变量的时候，也会产消除公共子表达式和删除归纳变量的时候，也会产生复制四元式生复制四元式n通过复制四元式传播的变量大多数是临时变量而通过复制四元式传播的变量大多数是临时变量而对临时变量可以使用复制传播来消除复制四元式对临时变量可以使用复制传播来消除复制四元式n原理：原理：= x y= x y的效果是的效果是x x和和y y的值相等。 如果的值相等如果某个引用某个引用y y的四元式运行的时候，的四元式运行的时候，x x和和y y的值一定相等的值一定相等那么我们可以使用对那么我们可以使用对y y的引用来替代对的引用来替代对x x的引用这的引用这样做有时可以消除复制四元式样做有时可以消除复制四元式= x y= x y 消除复制四元式的条件消除复制四元式的条件n对于复制四元式对于复制四元式d: = x yd: = x y，如果，如果对对y y对应于对应于d d点的一切引用点点的一切引用点u u满足下列条满足下列条件，那么我们可以删除件，那么我们可以删除d d，并且在这些引，并且在这些引用点上用对用点上用对x x的引用代替对的引用代替对y y的引用n此定义点是此定义点是d d到达到达u u的唯一的的唯一的y y的定义n从从d d到达到达u u的路径（可以包含圈和多个的路径（可以包含圈和多个u u，但，但是不包含多个是不包含多个d d）上，没有对）上，没有对x x的定义n这两个条件实际上是说，当程序运行到这两个条件实际上是说，当程序运行到达达u u点的时候，点的时候，x x和和y y的值总是相等。 的值总是相等 记号记号nC_GEN[B]C_GEN[B]：在基本块：在基本块B B中的所有复制四元式中的所有复制四元式= x y= x y，并且从该四元式开始到，并且从该四元式开始到B B的出口，的出口，x x和和y y都没有再定义都没有再定义nC_KILL[B]C_KILL[B]：包含了所有在流图中出现并且满足下列条：包含了所有在流图中出现并且满足下列条件的复制四元式件的复制四元式= x y= x y：：B B中存在对中存在对x x或者或者y y的定义，并且之后在没有复制四元式的定义，并且之后在没有复制四元式= x y= x y出出现nC_IN[B]C_IN[B]：表示在：表示在B B的入口点，有效的复制四元式的入口点，有效的复制四元式= x = x y y的集合，也就是到达入口的路径上都要经过的集合，也就是到达入口的路径上都要经过= x = x y y并且之后没有对并且之后没有对x x或者或者y y定义nC_OUT[B]C_OUT[B]：表示在：表示在B B的出口点有效的复制四元式的集合。 的出口点有效的复制四元式的集合 数据流方程数据流方程nC_OUT[B] = C_GEN[B] ∪(C_IN[B]-C_OUT[B] = C_GEN[B] ∪(C_IN[B]-C_KILL[B])C_KILL[B])nC_IN[B] = ∩E_OUT[p]C_IN[B] = ∩E_OUT[p]；其中；其中B B不等于不等于B1B1，，p p是是B B的前驱nC_IN[B1] = C_IN[B1] = 空集n其中其中C_GEN[B]C_GEN[B]和和C_IN[B]C_IN[B]可以直接从流图得可以直接从流图得到，所以在方程中作为已知量处理到，所以在方程中作为已知量处理n求解方法和可用表达式的求解相同求解方法和可用表达式的求解相同 复制传播算法复制传播算法n对于每个复制四元式对于每个复制四元式d: = x yd: = x y执行执行下列步骤下列步骤n找出该找出该y y定义所能够到达的那些对定义所能够到达的那些对y y的引用n确定是否对于每个这样的确定是否对于每个这样的y y，，d d都在都在C_IN[B]C_IN[B]中，中，B B是包含这个引用的基本块，而且是包含这个引用的基本块，而且B B中该中该引用的前面没有引用的前面没有x x或者或者y y的定义。 的定义n如果如果d d满足条件满足条件(2)(2)，删除，删除d d，且把步骤，且把步骤1 1中找中找到的的对到的的对y y的引用用的引用用x x代替 复制传播算法的例子复制传播算法的例子= x y* y 2 t= x y* y 3 t2+ x 1 y 循环优化的例子循环优化的例子( (原始流图）原始流图）B2- m 1 t1= t1 i= n j* 4 n t2=[] A t2 t3= t3 v+ i 1 t4= t4 i* 4 i t5=[] A t5 t6< t9 v B3- j 1 t7= t7 j* 4 j t8=[] A t8 t9> t9 v B3>= i j B6* 4 i t10=[] A t10 t11= t11 x* 4 i t12[]= A t12 t13 … … … …< i j B2* 4 i t18=[] A t18 t19= t19 x* 4 i t20[]= A t20 t21* 4 n t22=[] A t22 t23&= t23 t21 t21* 4 n t24[]= A t24 t25&= x t25 t25B1B3B4B5B6B7 寻找回边以及自然循环寻找回边以及自然循环n回边有：回边有：B2B2B2, B3B2, B3B3, B6B3, B6B2B2。 nB2B2B2B2对应的循环是对应的循环是{B2}{B2}nB3B3B3B3对应的循环是对应的循环是{B3}{B3}nB6B6B2B2对应的循环是对应的循环是{B2,B3,B4,B5,B6}{B2,B3,B4,B5,B6}n删除回边之后，得到的图是无回路的，删除回边之后，得到的图是无回路的，所以这个流图是可归纳流图所以这个流图是可归纳流图 寻找公共子表达式寻找公共子表达式n4*i4*i：在：在B5B5，，B7B7入口处可用入口处可用(U1)(U1)nA[4*i]A[4*i]：在：在B5B5，，B7B7的入口处可用的入口处可用(U2)(U2)n4*j4*j：在：在B5B5的入口处可用的入口处可用(U3)(U3)nA[4*j]A[4*j]：在：在B5B5的入口处可用的入口处可用(U4)(U4)n4*n4*n：在：在B7B7的入口处可用的入口处可用(U5)(U5)n A[4*n]A[4*n]：在：在B7B7的入口处可用的入口处可用(U6)(U6) 公共子表达式的优化公共子表达式的优化- m 1 t1= t1 i= n j* 4 n u5= u5 t2=[] A t2 u6= u6 t3= t3 v+ i 1 t4= t4 i* 4 i u1= u1 t5=[] A t5 u2 = u2 t6< t9 v B3- j 1 t7= t7 j* 4 j u3= u3 t8=[] A t8 u4= u4 t9> t9 v B3>= i j B6= u1 t10= u2 t11= t11 x* 4 i t12[]= A t12 t13 … … … …< i j B2= u1 t18= u2 t19= t19 x= u1 t20[]= A t20 t21= u5 t22= u6 t23&= t23 t21 t21= u5 t24[]= A t24 t25&= x t25 t25B1B3B4B5B6B7 寻找归纳变量寻找归纳变量n基本归纳变量有基本归纳变量有i i，，j j。 n归纳变量有：归纳变量有：nu1u1：：i i族，族，(i, 4, 0)(i, 4, 0)nu2u2：：j j族，族，(j, 4, 0)(j, 4, 0)n如果分析得更加深入，会发现如果分析得更加深入，会发现[]= []= 四元式得到四元式得到的地址也是归纳变量但是，由于我们不考虑的地址也是归纳变量但是，由于我们不考虑对间接赋值的优化，同时地址的处理也不在范对间接赋值的优化，同时地址的处理也不在范围之内，所以我们没有列出围之内，所以我们没有列出 归纳变量的优化归纳变量的优化- 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+ i 1 t4= t4 i+ u1 4 u1=[] A u1 u2 = u2 t6< t9 v B3- j 1 t7= t7 j- 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 t25B1B3B4B5B6B7 优化结果优化结果- 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 t25B1B3B4B5B6B7 窥孔优化窥孔优化n是指对代码局部进行改进的简单有效的是指对代码局部进行改进的简单有效的技术。 只考虑目标代码中的指令序列，技术只考虑目标代码中的指令序列，把可能的指令序列替换成为更短更快的把可能的指令序列替换成为更短更快的指令n冗余指令删除冗余指令删除n控制流优化控制流优化n代数化简代数化简n特殊指令使用特殊指令使用 冗余指令删除冗余指令删除n多余存取指令的删除：多余存取指令的删除：nMOV b R0MOV b R0nADD c R0ADD c R0nMOV R0 aMOV R0 anMOV a R0MOV a R0nSUB d R0SUB d R0nMOV R0 cMOV R0 cn第四条指令没有任何效果，可以删除第四条指令没有任何效果，可以删除n如果有标号转向第四条指令，则不可以删除如果有标号转向第四条指令，则不可以删除 冗余指令删除冗余指令删除n无用代码删除：无用代码删除：n将不会被执行的代码删除将不会被执行的代码删除n如果目标代码中有无条件转移指令，且其后的指令如果目标代码中有无条件转移指令，且其后的指令标号，那么后面的指令可以删除。 标号，那么后面的指令可以删除n产生无用代码的原因可以是调试信息，或者优产生无用代码的原因可以是调试信息，或者优化的结果化的结果n对于条件转移指令，如果其条件永远成立或者对于条件转移指令，如果其条件永远成立或者永远不成立，可以转换成为等价的无条件转移永远不成立，可以转换成为等价的无条件转移指令 控制流优化控制流优化n在代码中出现转移指令到转移指令的情况时，在代码中出现转移指令到转移指令的情况时，某些条件下可以使用一个转移指令来代替某些条件下可以使用一个转移指令来代替n转移到转移转移到转移nGOTO L1;GOTO L1;n… …… …nL1: GOTO L2;L1: GOTO L2;n显然第一个转移指令可以替代为显然第一个转移指令可以替代为GOTO L2.GOTO L2.n如果在没有其他的指令转移到如果在没有其他的指令转移到L1L1，那么第二个，那么第二个指令可以被删除指令可以被删除 控制流优化（续）控制流优化（续）n转移到条件转移：转移到条件转移：nL0: GOTO L1 … …L0: GOTO L1 … …nL1: IF b THEN GOTO L2;L1: IF b THEN GOTO L2;nL3: … … L3: … … n如果只有一个转移指令到达如果只有一个转移指令到达L1L1，且，且L1L1前面是无条件转前面是无条件转移指令，那么可以修改成为：移指令，那么可以修改成为：nIF b THEN GOTO L2;IF b THEN GOTO L2;nGOTO L3GOTO L3nL3: … …L3: … … 控制流优化（续）控制流优化（续）n条件转移到转移条件转移到转移nIFIF b bTHEN GOTO L1THEN GOTO L1n… … … … nGOTO L3GOTO L3n可以被修改为可以被修改为nIF b THEN GOTO L3IF b THEN GOTO L3n… …… …nGOTO L3GOTO L3 代数化简代数化简n利用代数规则来优化代码。 利用代数规则来优化代码n例如：例如：n利用利用x=x+0x=x+0和和x=x*1x=x*1来删除相应的指令来删除相应的指令n利用利用x x2 2=x*x=x*x来削减计算强度来削减计算强度 特殊指令的使用特殊指令的使用n充分利用目标系统的某些高效的特殊指充分利用目标系统的某些高效的特殊指令来提高代码效率令来提高代码效率n这些指令只可以在某些情况下使用而这些指令只可以在某些情况下使用而识别这样的情况是优化的基础识别这样的情况是优化的基础n例如：例如：INCINC指令可以用来替代加指令可以用来替代加1 1的操作。
