第11章代码优化

第11章代码优化,源语言程序经过词法分析、语法分析、语义分析等编译前期工作，得到了不改变原来程序运行结果且与原来程序功能等价的中间代码。而生成的中间代码并不是最优的，所以要对中间代码进行优化。所谓优化，实质上是对程序进行各种等价变换，使得从变换后的程序出发，能够生成更有效的目标代码。所谓有效，无非从时间和空间两个因素来考虑，即使得变换之后的程序运行速度更快、占用存储空间更少，这两个因素需要均衡考虑。,词法分析器,语法分析器,中间代码生成器,优化段,表格管理,出错处理,目标代码生成器,优化：对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。等价：指不改变程序的运行结果。有效：指目标代码运行时间短，占用的存储空间小。,本章教学内容,优化的分类；常用的代码优化技术;局部优化；循环优化。,一、代码优化的分类,根据代码优化是否涉及具体的计算机来划分，代码优化可分为两大类。一类是与机器有关的优化，这类优化一般在目标代码上进行，需要依赖于具体的机器。具体的有对寄存器优化、多处理机的优化、特殊指令的优化等。另一类是与机器无关的优化，在中间代码上进行，我们主要讨论这一种优化。,另外根据代码优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化是对循环中的代码进行的优化，在一个程序运行时，相当多的一部分时间会花在循环上，因此，基于循环的优化非常重要。全局优化是在整个程序范围内进行的优化。,二、常用的代码优化技术,代码优化的目的是为了产生效率更高的代码。编译程序中的代码优化阶段提供的对代码的各种变换必须遵循一定的原则。（1）等价原则。经过优化后不应改变程序运行的结果。（2）有效原则。使优化后所产生的目标代码运行时间较短，占用的存储空间较小。（3）合算原则。应尽可能以较低的代价取得较好的优化效果。,为了获得更优化的程序，可以从各个环节着手。首先，在源代码这一级，程序员可以通过选择适当的算法和安排适当的实现语句来提高程序的效率。例如，进行排序时，采用“快速排序”比采用“插入排序”就要快得多。其次，在设计语义动作时，我们不仅可以考虑产生更加高效的中间代码，而且还可以为后面的优化阶段做一些可能的预备工作。例如，可以在循环语句的头和尾对应的中间代码“打上标记”，这样可以有助于后面的控制流和数据流分析；代码的分叉处和交汇处也可以打上标记，以便于识别程序流图中的直接前驱和直接后继。,对编译产生的中间代码，我们安排专门的优化阶段，进行各种等价变换，以改进代码的效率。在目标代码这一级上，我们应该考虑如何有效地利用寄存器，如何选择指令，以及进行窥孔优化等等。通常为了使优化不依赖于目标机器的特性，主要的优化工作在中间代码上进行。因此，我们着重讨论中间代码这一级上的优化。这时的问题是，优化应用于程序的哪些部分？,示例,【例101】设A,B分别为两个一维数组，其初始地址分别表示为addr(A),addr(B)。源程序段为：X0；For(i=1;i20;i+)X=X+Ai*Bi；若机器按字节编址，按照循环语句的翻译，可以得到一组中间代码。,中间代码,1.删除公共子表达式(删除多余运算),如果一个表达式E在前面已经计算过，并且在这之后E中变量的值没有改变，则称E为公共子表达式，是指在一个基本程序块内计算结果相同的子表达式。对相同的子表达式只在第一次出现时计算并且仅计算一次，其结果暂存入Ti，而不必重复计算，这样既节约了空间，又节省了时间。这种优化称为删除公共子表达式，也称为删除多余运算。,删除公共子表达式,2.代码外提,代码外提是指将循环中的不变运算提到循环体前面。处在循环体内的不变运算，不论循环体重复执行多少次都不影响其计算结果，这样的运算只会浪费代码执行时间。因此将这类运算提到循环体外并不影响程序运行结果，还可加快代码执行速度。,代码外提,3.强度削弱,强度削弱是指用执行效率较高的操作等价地替换原操作。对于非算术运算可削弱强度，如尽量使用寄存器，少访问内存（或外存）等。例如，对计算机上的二进制算术运算，做加法一般比作乘法的速度快。如果能在循环中进行这种变换，其优化效果更是显而易见。因此，推广到一般，对中间代码级的运算尽可能降低运算级别。,强度削弱,T1=T14,4.变换循环控制条件(删除归纳变量),for循环中，控制变量i的作用域是本循环体。如果在循环体内存在一个变量（或临时变量）T与循环控制变量i保持线性关系，同时在循环的后面不引用i，而删去i又不影响程序结果，则可由T取代i的控制循环次数的作用。从循环中删除i，这种方法称为变换循环控制条件，或者称为删除归纳变量。,变换循环控制条件,T180,5.合并已知变量,已知量是指常数或在编译时就能确定其值的变量。合并已知量是指在编译时就将源程序中关于已知量的表达式之值先行算出，不必生成计算该表达式的代码。,合并已知变量,4*1=4,6.复写传播,复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值，也不影响其运行结果的变量。,复写传播,T1,7.删除无用赋值,变量的最后一次引用到下次引用之前的最近一次赋值期间，可视为无用变量。在变量的无用期内，对它的任何赋值均可删除。对于那些被赋值后从未被引用的变量，对其进行赋值操作也是无用赋值，可删除。即对赋值语句XY，若在程序的任何的地方都不引用X，这是该语句执行与否对程序最终运行结果没有任何作用，这种语句称为无用赋值语句，可以删除。删除无用赋值语句可以减少程序中的无用的变量，还可以使代码更简洁。,删除无用赋值,优化后的代码序列,优化后的代码序列具有以下特点：减少了循环体内可执行代码，由12条减至10条。减少了作乘法运算的次数，由3次降为1次。减少了全程范围内使用的变量，如i,T4等变量。综上可知，经过一系列优化后的代码其执行效率明显提高。当然优化工作越多，编译系统的代价就会越大。因此，对某种程序设计语言翻译出来的中间代码要实施什么优化，就要视语言的特点具体分析，力争设计一个最适应本语言特点的代码优化方案。,三、局部优化,局部优化（local）是指基本块内的优化。对于给定的程序，我们可以把它划分为一系列的基本块。在各个基本块的范围内，分别进行优化。局限在基本块范围内的优化称为基本块内的优化，或者称为局部优化。,1.基本块的定义,所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。执行时只能从其入口语句进入，从其出口语句退出，不存在跳转和分叉汇合的情况。,2基本块的划分算法,从四元式程序中划分基本块的算法步骤如下：第一步：确定四元式程序（中间代码）中各个基本块的人口语句；所谓入口语句，严格地说来就是下述语句之一：程序的第一个语句；能够由条件转移语句或无条件转移语句转移到的目标语句；紧跟在条件转移语句后面的语句。,划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)之间的语句序列组成的。,入口语句n入口语句m,划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)之间的语句序列组成的。,入口语句n入口语句m,入口语句n转移语句m,划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。,入口语句n入口语句m,入口语句n转移语句m,入口语句n停语句m,划分四元式程序为基本块的算法:第二步：对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。第三步：凡未被纳入某一基本块的语句，都是程序中控制流程无法达到的语句，因而也是不会被执行到的语句，我们可以把它们删除。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。,例：划分基本块(1)readX(2)readY(3)R:=XmodY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)writeY(9)halt,2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。,示例,【例102】将下面的四元式序列划分为基本块：（1）（，l，_，I）（2）（j，_，_，（4）（3）（，I，1，I）（4）（j，I，N，（6）（5）（j，_，_，（9）（6）（，M，I，T）（7）（，T，_，M）（8）（j，_，_，（3）（9）,3基本块的变换,基本块的主要保结构变换是:1删除公共子表达式2删除无用赋值3重新命名临时变量4交换语句次序,4.基本块的DAG表示,DAG（DirectedAcyclicGraph）即无环有向图，它是有向图中的一种，通常用来对基本块进行优化。这种有向图是一种其结点带有下述标记或附加信息的DAG：1图的叶结点(即没有后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。,2图的内部结点（即有后继的结点）以一运算符作为标记，表示该节点代表应用该运算符对其后继结点所代表的值进行运算的结果。3图中各个结点可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。上述这种DAG可用来描述计算过程，又称为描述计算过程的DAG。在以下的讨论中，我们简称为DAG.,基本块的DAG表示,一个基本块，可用一个DAG来表示。可以利用DAG来描述四元式，如图所示，列出了各种四元式以及相对应的DAG的结点形式。图中为结点编号，结点下面的符号（运算符，标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。,四元式,（0）AB（，B，A）对应的DAG结点为：,四元式,（1）AopB（op，B，A）对应的DAG结点为：,四元式,（2）ABopC（op，B，C，A）对应的DAG结点为：,四元式,（3）ABC（，BC，A）对应的DAG结点为：,四元式,（4）ifBropCgoto（s）（jrop，B，C，（s）对应的DAG结点为：,四元式,（5）DCB（，B，DC）对应的DAG结点为：,四元式,（6）goto（s）（j，（s）对应的DAG结点为：,5.基本块的DAG构造算法,假设DAG各结点信息将用某种适当的数据结构来存放。并设有一个标识符（包括常数）A与结点NODE(A)的对应表，即用大写字母A，B等表示四元式中的变量名或常数。NODE(A)是描述这种对应关系的一个函数，即用NODE(A)表示A在DAG中的相应结点，它的值可以是一个结点的编号n或者无定义。NODE(A)n代表DAG中存在一个结点n，A是其上的标记或附加标识符。,四元式分类,把各种形式的四元式按其对应结点的后继个数分为四类。其中：0型四元式：有0个后继结点，如四元式(0)；1型四元式：有1个后继结点，如四元式(1)；2型四元式：有2个后继结点，如四元式(2)、(3)和(4)；3型四元式：有3个后继结点，如四元式(5)。,对于3型四元式，由于对数组元素赋值的情形需特殊考虑，因此暂不讨论，对四元式(6)也不涉及，下面是仅含0，1，2型四元式的基本块的DAG构造算法。假设要考虑的中间代码（四元式）包括如下三种形式：0型四元式AB1型四元式AopB2型四元式ABopC或者ABC,仅含0，1，2型四元式的基本块的DAG构造算法如下：初始时，DAG为空。对基本块中的每一条四元式，依次执行以下步骤：,1.如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点；如果当前四元式是0型，则记NODE(B)的值为n，转4。如果当前四元式是1型，则转2.(1)如果当前四元式是2型，则()如果NODE(C)无定义，则构造一标记为C的叶结点并定义NODE(C)为这个结点，()转2.(2)。,2.(1)如果NODE(B)是标记为常数的叶结点，则转2.(3)，否则转3.(1)。(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2.(4)，否则转3.(2)。(3)执行opB(即合并已知量)，令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4.。(4)执行BopC(即合并已知量)，令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)n，转4.。,3.(1)检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op(即找公共子表达式)。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4.。(2)检查DAG中是否已有一结点，其左后继为NODE(B)，右后继为NODE(C)，且标记为op(即找公共子表达式)。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n。转4.。,4.如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)n；否则先把A从NODE(A)结点上的附加标识符集中删除(注意，如果NODE(A)是叶结点，则其标记A不删除)，把A附加到新结点n上并令NODE(A)n。转处理下一四元式。,示例,【例103】试构造以下基本块G的DAG。（1）T0=3.14（2）T1=2*T0（3）T2=R+r（4）A=T1*T2（5）B=A（6）T3=2*T0（7）T4=R+r（8）T5=T3*T4（9）T6=R-r（10）B=T5*T6,6.基本块的应用,将四元式表示成相应的DAG后，可以利用DAG来进行优化。利用基本块来进行优化的主要思想是：首先将一个基本块中的每一个四元式依次表示成对应的DAG，再将这些DAG合成对于一个较大的DAG，即为该基本块的DAG。然后按照构造DAG结点的顺序重写四元式序列，就可以得到经过“合并已知量”、“删除无用赋值”、“删除公共子表达式”的等价的基本块，即为优化后的基本块。,示例,将前面的DAG按原来构造其结点的顺序，重新写成四元式，得到以下的四元式序列G：（1）T0=3.14（2）T1=6.28（3）T3=6.28（4）T2=R+r（5）T4=T2（6）A=6.28*T2（7）T5=A（8）T6=R-r（9）B=A*T6,优化后的四元式若只有A和B是出基本块之后活跃的(1)T2:=R+r(2)A:=6.28*T2(3)T6:=R-r(4)B:=A*T6(1)S1:=R+r(2)A:=6.28*S1(3)S2:=R-r(4)B:=A*S2,从DAG中还能得到其他的优化信息：在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。在基本块内被定值并且该值在基本块后面可以被引用的所有标识符，就是DAG各结点上的那些附加标识符。,四、循环优化,在程序设计语言中，循环是必不可少的控制结构之一。所谓循环，粗略地说，就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。,循环优化是指在循环体中进行的专项优化，是提高程序运行效率的主要途径。因为在一个执行n次的循环体内进行一项优化，从运行效率上来说，相当于进行了n项优化。为了进行循环优化，首先必须找出程序中的循环，为找出程序中的循环，就需要对程序的控制流程进行分析。我们将使用程序的控制流程图对所讨论的循环给出定义，并介绍怎样从程序的控制流程图中找出程序的循环。对循环中的代码段，可以进行代码外提、强度削弱和删除归纳变量等优化。,1.程序流图,一个控制流程图就是具有唯一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何结点都有一条通路的结点。一个控制流程图表示成一个三元组G(N，E，n0)，其中，N代表图中所有结点集，E代表图中所有有向边集，n0代表首结点。以下把控制流程图简称为流图。,一个程序可用一个流图来表示。流图中的有限结点集N就是程序的基本块集，流图中的结点就是程序中的基本块。流图的首结点就是包含程序第一个语句的基本块。,程序流图中的有向边集E是这样构成的：假设流图中结点i和结点j分别对应于程序的基本块i和基本块j，则当下述条件1.或2.有一个成立时，从结点i有一有向边引向结点j：1.基本块j在程序中的位置紧跟在基本块i之后，并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。2基本块i的出口语句是goto(s)或ifgoto(s)，并且(s)是基本块j的入口语句。,示例,【例10.4】为以下程序构造一个流图（1）readx（2）ready（3）z=xmody（4）ifz=0goto(8)（5）x=y（6）y=z（7）goto(3)（8）writey（9）halt,程序流图,2.循环的定义,在流图中,称具有下列性质的结点序列为一个循环：它们是强连通的。即其中任意两个结点之间，必有一条通路，而且该通路上各结点都属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。它们中间有且只有一个是入口结点。所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。循环就是流图中具有唯一入口结点的强连通子图，从循环外要进入循环，必须首先经过循环的入口结点。,示例,对此流图，根据定义，结点序列6，4，5，6，7以及2，3，4，5，6，7都是循环；而结点序列2，4，2，3，4，4，6，7以及4，5，7虽然都是强连通的，但因它们的入口结点不唯一，所以都不是上述意义下的循环。,3.循环的查找,为了查找循环，需对程序流图中各结点的控制关系进行分析，即利用控制点（dominator）查找循环。在一个已知的程序流图里，如何确定循环是由哪些结点组成的呢？仔细观察程序流图中各结点的控制关系，根据循环语句的特点和循环的定义不难发现，从循环入口即循环的首结点开始，每一个结点都有其后继结点，直至循环的出口结点。,同时从循环的出口结点一定要转向该循环的入口结点，这是由循环语句自身的功能所定。因为循环体被执行完后要判断循环条件是否成立，若成立，再重复执行循环体，体现在程序流图中就是循环出口结点至入口结点一定存在一条有向边，由这条有向边的出发结点（即循环出口结点）开始往回找前驱结点，直至循环入口结点就是循环。为了区别于其他的有向边，称上述有向边为回边，组成这条边的关键结点为必经结点。因此，查找循环的关键就是找回边及其所有与回边有关联的必经结点。,必经结点与必经结点集,【必经结点】在程序流图中，对任意两个结点a和b，若从程序流图中的首结点到某结点n的所有路径都要经过结点m，则称结点m控制了结点n，并称m是n的必经结点，记作mDOMn。【必经结点集】流图中结点m的所有必经结点的集合称为结点m的必经结点集，记为D（m）。根据定义，对任一结点n，有nDOMn；并且循环的入口结点必为循环中每个结点的必经结点。,性质,若将DOM看做流图结点集上定义的一个关系，根据以上定义，它具有以下性质：（1）自反性：对流图中任意结点a，有aDOMa。（2）传递性：对流图中任意结点a，b和c，若aDOMb和bDOMc，则aDOMc。（3）反对称性：若aDOMb和bDOMa，则ab。由上可见，关系DOM是一个偏序关系，因此，任何结点n的必经结点集是个有序集。,【例10.5】求解图中各个结点的必经结点集D(n)。,回边,【回边】设ab是流图中的一条有向边，如果bDOMa，则称ab是流图中的一条回边。对于一已知流图，只要求出各结点的必经结点集，就可以求出流图中所有的回边。利用回边可以方便地查找循环。设nd为流程图中的一条回边，则流程图中那些不经过结点d而能到达n的所有结点以及结点d和结点n本身，构成了流程图中的一个循环，且d为该循环的唯一入口。有向边ab是否都是回边呢？由定义可知，作为回边的有向边，必须满足条件：b是a的必经结点。,示例,【例10.7】计算前图中流图的所有回边。在图中，存在有向边12，但结点不是结点的必经结点，所以不是回边。对有向边66：因为D（6）1，2，4，6，所以6DOM6。74：因为D（7）1，2，4，7，所以4DOM7。42：因为D（4）1，2，4，所以2DOM4。上述三条有向边满足回边的条件，所以它们均为回边。,显然，可以验证流图中其他有向边均不满足回边的定义，所以不是回边。所以，有向边66、74、42是回边，其它有向边都不是回边。对于前面流图中的例子，很容易看出：由回边66组成的循环就是6；由回边74组成的循环是4，5，6，7；由回边42组成的循环是2，3，4，5，6，7。,利用回边查找循环的基本思想,回边确定之后，如何根据回边求循环呢？如果已知有向边ab是回边，根据循环的定义可知，该循环是由从结点b出发的，所有有通路到达结点a但该通路又不经过b的结点组成，并且b是该循环的唯一入口结点。,求由回边ab组成的循环的基本思想是：首先确定循环的出口a，判断a和b，若ab，求a的所有前驱结点（L），若前驱结点不是循环入口，再求前驱的前驱（L），直至所求出的前驱都是b为止。,示例,在前面的流图中：回边66组成的循环是：6。回边74组成的循环是：4，5，6，7，其中结点，是不经过结点而有通路到达结点的结点。回边42组成的循环是：2，3，4，5，6，7。,求回边ab组成的循环的算法,voidinsert（x）；ifx不属于LoopLoopLoopx；把x下推进栈stack；,main主函数中根据回边查找循环的算法：stack空；Loopb；insert（a）；Whilestack非空把stack的栈顶元素x出栈；forpP（x）insert（p）；其中，P（x）表示结点x的前驱结点集，stack为工作栈，Loop为所求循环中的结点集。insert为一函数。,算法的基本思想,算法的基本思想是：由于要求回边ab组成的循环，这个循环将以b为其唯一入口，a是它的一个出口。若a不同时是b，则a的所有前驱结点应属于循环。当求出a的所有前驱后，只要它们不是循环入口b，就应再求出它们的前驱，新求出的所有前驱也应属于循环。然后再对新求出的所有前驱，重复以上步骤，直到所求出的前驱是b为止。此时算法结束。,【例10.8】利用算法求前面流图中回边74组成的循环。,开始，置Loop4，stack为空。由insert把结点放到栈中，此时Loop4，7。然后出栈，求的前驱结点集P(7)5，6，把和先后放入Loop和stack中，这时Loop4，7，5，6。结点的前驱都不是，再分别求的前驱和的前驱。这时，栈顶元素是结点，所以出栈，P(6)6，4已在Loop中，故仅出栈而已。此时栈顶元素为结点，P(5)4也在Loop中，故也出栈。这是栈stack已空，算法结束，所求循环Loop4，5，6，7。所以，得到前面流图中回边74组成的循环为6，5，4，7。,3.可归约流图,一个流图被称为可归约的，当且仅当流图中除去回边外，其余的边构成一个无环路流图。可归约流图是一类非常重要的流图。从代码优化的角度来说，它具有下述重要的性质：1.图中任何直观意义下的环路，都属于我们所定义的循环。2.只要找出图中所有回边，对回边应用前述循环查找算法，就可找出流图中所有的循环。3.图中任意两个循环要么嵌套，要么不相交(除了可能有公共的入口结点)，对这类流图进行循环优化较为容易。,4.循环优化方法,在找出了程序流图中的循环之后，我们就可以针对每个循环进行优化工作。因为循环内的指令是重复执行的，故而循环中进行的优化在整个优化工作中是非常重要的。这里介绍循环优化的三种重要技术：代码外提；删除归纳变量；强度削弱。,代码外提,减少循环中程序代码数目的一个重要办法是代码外提。这种变换把循环不变运算，即运算产生的结果不受循环执行次数影响的表达式，放到循环的前面。这里，所讨论的循环只存在一个入口结点。实行代码外提时，在循环的入口结点前面建立一个新结点(基本块)，称之为循环的前置结点。循环的前置结点以循环的入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点，如图所示。,代码外提时建立一个前置结点,示例,示例,查找“不变运算”的算法,假设L为所要处理的循环。(1)依次查看L中各基本块的每个四元式，如果它的每个运算对象或为常数，或者定值点在L外，则将此四元式标记为“不变运算”；(2)重复第(3)步直至没有新的四元式被标记为“不变运算”为止；(3)依次查看尚未被标记为“不变运算”的四元式，如果它的每个运算对象或为常数，或者定值点在L之外，或只有一个到达定值点且该点上的四元式已被标记为“不变运算”。则被查看的四元式标记为“不变运算”。,代码外提算法,(1)求出循环L的所有不变运算。(2)对步骤(1)所求得的每一不变运算s：ABopC或AopB或AB，检查它是否满足以下条件(a)或(b)：(a)()s所在的结点是L的所有出口结点的必经结点。()A在L中其它地方未再定值。()L中所有A的引用点只有s中A的定值才能到达。,(b)A在离开L之后不再是活跃的，并且条件(a)的()和()成立。所谓A在离开L后不再是活跃的是指，A在L的任何出口结点的后继结点的入口处不是活跃的(从此点后不再被引用)。(3)按步骤(1)所找出的不变运算的顺序，依次把符合(2)的条件(a)或(b)的不变运算s外提到L的前置结点中。如果s的运算对象(B或C)是在L中定值的，则只有当这些定值四元式都已外提到前置结点中时，才可把s也外提到前置结点。,注意,如果把满足条件(2)(b)的不变运算ABopC外提到前置结点中。那么，执行完循环后得到的A值，可能与不进行外提的情形所得A值不同。但因为离开循环后不会引用该A值。所以不影响程序运行结果。,强度削弱与删除归纳变量,强度削弱是指把程序中执行时间较长的运算替换为执行时间较短的运算。例如把循环中的乘法运算用递归加法运算来实现。,如果循环中有I的递归赋值II土C(C为循环不变量)，并且循环中T的赋值运算可化归为TK*I土C1(K和C1为循环不变量)，则T的赋值运算可以进行强度削弱，进行强度削弱后，循环中可能出现一些新的无用赋值，如果它们在循环出口之后不是活跃变量，则可将其从循环中删除。强度削弱在某些情况下进行的优化是非常有效的。例如对于下标变量的地址计算就是如此。在循环优化中，强度削弱占很重要的地位。,删除归纳变量的优化,【基本归纳变量】如果循环中对变量I只有唯一的形如