编译原理教程05代码优化.ppt

《编译原理教程05代码优化.ppt》由会员分享，可在线阅读，更多相关《编译原理教程05代码优化.ppt（139页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章代码优化 5.1 局部优化局部优化 5.2 循环优化循环优化*5.3 全局优化概述全局优化概述*5.4 代码优化示例代码优化示例 习题五习题五 第第5章代章代 码码 优优 化化第5章代码优化 代码优化的含义代码优化的含义进行代码优化的时间进行代码优化的时间代码优化的种类代码优化的种类第5章代码优化 源源程程序序经经过过词词法法分分析析、语语法法分分析析、语语义义分分析析等等阶阶段段的的编编译译工工作作，得得到到了了与与源源程程序序功功能能等等价价的的中中间间代代码码。但但是是，由由于于这这种种中中间间代代码码是是“机机械械生生成成”的的结结果果，因因而而必必然然存存在在效效率率不不高高和

2、和有有冗冗余余代代码码的现象，还需进行的现象，还需进行代码优化代码优化。代代码码优优化化的的含含义义是是：对对代代码码进进行行等等价价变变换换，使使得得变变换换后后的的代代码码具具有有更更高高的的时时间间效效率率和和空空间间效效率率。代代码码优优化化的的目目的的是是提提高高目目标标程序的质量。程序的质量。1.代码优化的含义代码优化的含义第5章代码优化 优优化化可可以以在在编编译译的的不不同同阶阶段段进进行行，但但最最主主要要的的一一类类优优化化是是在在目目标标代代码码生生成成以以前前进进行行的的，即即对对语语义义分分析析后后的的中中间间代代码码进进行行优优化化，这种优化的这种优化的优点优点是不

3、依赖于具体的计算机。是不依赖于具体的计算机。另另一一类类重重要要的的优优化化是是在在生生成成目目标标代代码码时时进进行行的的，它它在在很很大大程程度度上上依依赖赖于于具具体体的的计计算算机机。本本章章讨讨论论前前一一种种与与机机器器无无关关的的中中间间代代码优化。码优化。2.进行代码优化的时间进行代码优化的时间第5章代码优化 根据优化对象所根据优化对象所涉及涉及的程序范围，优化又分为的程序范围，优化又分为 局部优化局部优化、循环优化循环优化和和全局优化全局优化。一一个个程程序序从从结结构构上上看看，作作为为结结点点的的基基本本块块是是其其基基础础。因因为为基基本本块块的的结结构构最最简简单单、

4、因因素素最最单单纯纯，所所以以它它也也是是优优化化的的基基础础，对对基基本块本块的优化就是局部优化。的优化就是局部优化。循循环环是是程程序序中中要要反反复复执执行行的的部部分分，优优化化的的效效益益当当然然很很大大，所所以循环优化是优化工作的一个重点。以循环优化是优化工作的一个重点。针针对对整整个个程程序序的的优优化化即即全全局局优优化化，它它涉涉及及到到对对程程序序数数据据流流分分析的问题。析的问题。3.代码优化的种类代码优化的种类第5章代码优化 5.1 局局 部部 优优 化化基本块的划分方法基本块的划分方法基本块的基本块的DAG表示表示第5章代码优化 5.1.1 基本块的划分方法基本块的划

5、分方法所谓基本块，是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是该序列的第一个语句，出口就是该序列的最后一个语句。对一个基本块来说，执行时只能从其入口进入，从其出口退出。对一个给定的程序，我们可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部优化。划分基本块的关键问题是准确定义入口和出口语句。下面我们给出划分四元式程序为基本块的算法：(1)从四元式序列确定满足以下条件的入口语句：四元式序列的第一个语句；能由条件转移语句或无条件转移语句转移到的语句；紧跟在条件转移语句后面的语句。第5章代码优化(2)确定满足以下条件的出口语句：下一个入口语句的前导语句；转移语句

6、(包括转移语句自身)；停语句(包括停语句自身)。第5章代码优化 例如，考察下面求最大公因子的三地址代码程序：(1)readX(2)readY(3)R=X%Y(4)ifR=0goto(8)(5)X=Y(6)Y=R(7)goto(3)(8)writeY(9)halt根据上述划分基本块的算法可确定四元式(1)、(3)、(5)、(8)是入口语句，而四个基本块分别是：(1)(2)，(3)(4)，(5)(6)(7)，(8)(9)。第5章代码优化 5.1.2 基本块的基本块的DAG表示表示DAG(DirectedAcyclicGraph)是一种有向图，常常用来对基本块进行优化。一个基本块的DAG是一种其结点

7、带有下述标记或附加信息的DAG：(1)图的叶结点(无后继的结点)以一标识符(变量名)或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来表示一变量A的地址，则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。(2)图的内部结点(有后继的结点)以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。第5章代码优化(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。一个基本块由一个四元式序列组成，且每一个四元式都可以用相应的DAG结点表示。图51给出了不同四元式和与其对应的DAG

8、结点形式。图中，各结点圆圈中的ni是构造DAG过程中各结点的编号，而各结点下面的符号(运算符、标识符或常数)是各结点的标记，各结点右边的标识符是结点上的附加标识符。除了对应转移语句的结点右边可附加一语句位置来指示转移目标外，其余各类结点的右边只允许附加标识符。除对应于数组元素赋值的结点(标记为=)有三个后继外，其余结点最多只有两个后继。第5章代码优化 图51四元式与DAG结点第5章代码优化 利用DAG进行基本块优化的基基本本思思想想是：首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已做了局部优化，所以最后所得到

9、的是优化过的四元式序列。为了DAG构造算法的需要，我们将图51中的四元式按照其对应结点的后继结点个数分为四类：(1)0型四元式：后继结点个数为0，如图51(1)所示；(2)1型四元式：有一个后继结点，如图51(2)所示；(3)2型四元式：有两个后继结点，如图51(3)、(4)、(5)所示；(4)3型四元式：有三个后继结点，如图51(6)所示。第5章代码优化 我们规定：用大写字母(如A、B等)表示四元式中的变量名(或常数)；用函数Node(A)表示A在DAG中的相应结点，其值可为n或者无定义，并用n表示DAG中的一个结点值。这样，每个基本块仅含0、1、2型四元式的DAG构构造造算算法法如下(对基

10、本块的每一个四元式依次执行该算法)：(1)若Node(B)无定义，则构造一标记为B的叶结点并定义Node(B)为这个结点，然后根据下列情况做不同处理：若当前四元式是0型，则记Node(B)的值为n，转(4)。若当前四元式是1型，则转(2)。若当前四元式是2型，则：i.如果Node(C)无定义，则构造一标记为C的叶结点，并定义Node(C)为这个结点；ii.转(2)。第5章代码优化(2)若Node(B)是以常数标记的叶结点，则转(2)，否则转(3)。若Node(B)和Node(C)都是以常数标记的叶结点，则转(2)，否则转(3)。执行op B(即合并已知量)，令得到的新常数为P。若Node(B)

11、是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)=n；转(4)。执行BopC(即合并已知量)，令得到的新常数为P。若Node(B)或Node(C)是处理当前四元式时新建立的结点，则删除它；若Node(P)无定义，则构造一用P做标记的叶结点n并置Node(P)=n；转(4)。第5章代码优化(3)检查DAG中是否有标记为op且以Node(B)为惟一后继的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。检查DAG中是否有标记为op且其左后继为Node(B)、右后继为Node

12、(C)的结点(即查找公共子表达式)。若有，则把已有的结点作为它的结点并设该结点为n；若没有，则构造一个新结点；转(4)。(4)若Node(A)无定义，则把A附加在结点n上并令Node(A)=n；否则，先从Node(A)的附加标识符集中将A删去(注意，若Node(A)是叶结点，则不能将A删去)，然后再把A附加到新结点n上，并令Node(A)=n。第5章代码优化 注意：算法中步骤(2)的、用于判断结点是否为常数，而步骤(2)的、则是对常数的处理。对任何一个四元式，如果其中参与运算的对象都是编译时的已知量，那么(2)并不生成计算该结点值的内部结点，而是执行该运算并用计算出的常数生成一个叶结点，所以(

13、2)的作用是实现合并已知量。步骤(3)的作用是检查公共子表达式。对具有公共子表达式的所有四元式，它只产生一个计算该表达式值的内部结点，而把那些被赋值的变量标识符附加到该结点上。这样，当把该结点重新写为四元式时，就删除了多余运算。第5章代码优化 步骤(4)的功能是将(1)(3)的操作结果赋给变量A，也即将标识符A标识在操作结果的结点n上，而执行把A从Node(A)上的附加标识符集中删除的操作则意味着删除了无用赋值(对A赋值后但在该A值引用之前又重新对A进行了赋值，则前一个赋值为无用赋值)。综上所述，DAG可以在基本块内实现合并已知量、删除无用赋值和删除多余运算的优化。第5章代码优化 例5.1试构

14、造以下基本块的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=Rr(10)B=T5*T6解答按照算法顺序处理每一四元式后构造出的DAG如图52所示，其中每一子图(1)、(2)、(10)分别对应四元式(1)(10)的DAG构造。第5章代码优化 DAG构造过程(1)T0=3.14(2)T1=2*T0第5章代码优化 DAG构造过程(3)T2=R+r第5章代码优化 DAG构造过程(4)A=T1*T2第5章代码优化 DAG构造过程(5)B=A第5章代码优化 DAG构造过程(6)T3=

15、2*T0第5章代码优化 DAG构造过程(7)T4=R+r第5章代码优化 DAG构造过程(8)T5=T3*T4第5章代码优化 DAG构造过程(9)T6=R-r第5章代码优化 DAG构造过程(10)B=T5*T6第5章代码优化 图52DAG第5章代码优化 构造过程说明如下：(1)对应图52(2)，四元式T1=2*T0首先执行算法中的步骤(1)，因Node(B)无定义，所以构造一个标记为2的叶结点并定义Node(2)为这个结点。因当前四元式是2型且Node(C)已有定义(此时 为 Node(T0)，转 算 法 步 骤(2)。因 Node(B)=Node(2)和 Node(C)=Node(T0)都是标

16、记为常数的叶结点，则执行B op C并令新结点为P(=6.28)。由于Node(P)无定义，故构造Node(P)=Node(6.28)。此外，因Node(B)=Node(2)是处理当前四元式时新构造出来的结点，故删除n2。接下来执行算法步骤(4)，因Node(A)无定义而将T1附加在结点n3上，并令Node(T1)=6.28；最后DAG生成了2个结点n1和n3，因结点n2被删除而将n3改名为n2。图52(2)的形成过程实际上也是合并已知量的优化过程。第5章代码优化(2)图52(4)中T1、T2已有定义，则仅生成一个新结点n6并将A附加在n6上。图5-2(5)中结点B已有定义，故直接附加在n6上

17、。(3)图52(6)的处理过程与图52(2)略同，但在生成P时因其已在DAG中(即Node(6.28)，故不生成新结点而直接将T3附加在结点6.28上。(4)图52(7)的生成过程实质上是删除多余运算(删除公共子表达式)的优化。因为DAG中已有叶结点R与叶结点r，并且执行op操作后得到的新结点T2也已经在DAG中，故执行算法步骤(4)时因T4无定义而将T4附加在结点n5上。第5章代码优化(5)图52(9)中，变量R和r已在DAG中有相应的结点，执行“”操作后，产生的新结点P无定义，故仅生成一个新结点n7并将T6标记于其上。(6)图52(10)中，对当前四元式B=T5*T6，DAG中已有结点T5

18、和T6；执行算法步骤(4)时因结点B已有定义且不是叶结点，故先将原B从DAG中删除，然后生成一个新结点n8，将B附加其上并令Node(B)=n8。这一处理过程实质上是删除了无用赋值B=A。第5章代码优化 5.1.3 利用利用DAG进行基本块的优化处理进行基本块的优化处理利用DAG进行基本块优化处理的基本思想是：按照构造DAG结点的顺序，对每一个结点写出其相应的四元式表示。我们根据例5.1DAG结点的构造顺序，按照图52(10)写出四元式序列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=Rr

19、(9)B=A*T6第5章代码优化 将G和原基本块G相比，我们看到：(1)G中四元式(2)和(6)都是已知量和已知量的运算，G已合并；(2)G中四元式(5)是一种无用赋值，G已将它删除；(3)G中四元式(3)和(7)的R+r是公共子表达式，G只对它们计算了一次，即删除了多余的R+r运算。因此，G是对G实现上述三种优化的结果。第5章代码优化 通过观察图52(10)中的所有叶结点和内部结点以及其上的附加标识符，还可以得出以下结论：(1)在基本块外被定值并在基本块内被引用的所有标识符就是DAG中相应叶结点上标记的标识符；(2)在基本块内被定值且该值能在基本块后面被引用的标识符就是DAG各结点上的附加标

20、识符。第5章代码优化 这些结论可以引导优化工作的进一步深入，尤其是无用赋值的优化，也即：(1)如果DAG中某结点上的标识符在该基本块之后不会被引用，就可以不生成对该标识符赋值的四元式；(2)如果某结点ni上没有任何附加标识符，或者ni上的附加标识符在该基本块之后不会被引用，而且ni也没有前驱结点，这表明在基本块内和基本块之后都不会引用ni的值，那么就不生成计算ni结点值的四元式；(3)如果有两个相邻的四元式A=CopD和B=A，其中第一条代码计算出来的A值仅在第二个四元式中被引用，则将DAG中相应结点重写成四元式时，原来的两个四元式可以优化为B=CopD。第5章代码优化 假设例5.1中T0、T

21、1、T2、T3、T4、T5和T6在基本块后都不会被引用，则图5-2(10)中的DAG就可重写为如下的四元式序列：(1)S1=R+r/*S1、S2为存放中间结果的临时变量*/(2)A=6.28*S1(3)S2=Rr(4)B=A*S2以上把DAG重写成四元式序列时，是按照原来构造DAG结点的顺序(即n5、n6、n7、n8)依次进行的。实际上，我们还可以采用其它顺序(如自下而上)重写，只要其中的任何一个内部结点是在其后继结点之后被重写并且转移语句(如果有的话)仍然是基本块的最后一个语句即可。第5章代码优化 5.1.4 DAG构造算法的进一步讨论构造算法的进一步讨论当基本块中有数组元素引用、指针和过程

22、调用时，构造DAG算法就较为复杂。例如，考虑如下的基本块G：(1)x=ai(2)aj=y(3)z=ai第5章代码优化 如果我们用构造DAG的算法来构造上述基本块的DAG，则ai就是一个公共子表达式；且由所构造的DAG重写出优化后的四元式序列G如下：(1)x=ai(2)z=x(3)aj=y如果ij，则G与G是等效的。但是，如果i=j且yai，则将y值赋给aj的同时也改变了ai的值(因i=j)；这时z值应为改变后的ai值(即y值)，与x不等。为了避免这种情况的发生，当我们构造对数组a的元素赋值句的结点时，就“注销”所有标记为且左边变量是a(可加上或减去一个常数)的结点。我们认为对这样的结点再添加附

23、加标识符是非法的，从而取消了它作为公共子表达式的资格。第5章代码优化 对指针赋值语句*p=w(其中p是一个指针)也会产生同样的问题，如果我们不知道p可能指向哪一个变量，那么就认为它可能改变基本块中任何一个变量的值。当构造这种赋值句的结点时，就需要把DAG各结点上的所有标识符(包括作为叶结点上标记的标识符)都予以注销，这也就意味着DAG中所有的结点也都被注销。在一个基本块中的一个过程调用将注销所有的结点，因为对被调用过程的情况缺乏了解，所以我们必须假定任何变量都可能因产生副作用而发生变化。第5章代码优化 此外，当把DAG重写成四元式时，如果我们不是按照原来构造DAG结点的顺序进行重写，那么DAG

24、中的某些结点必须遵守一定的顺序。例如，在上述基本块G中，z=ai必须跟在aj=y之后，而aj=y则必须跟在x=ai之后。下面，我们根据上述讨论把重写四元式时DAG中结点间必须遵守的顺序归纳如下：(1)对数组a中任何元素的引用或赋值，都必须跟在原来位于其前面的(如果有的话，下同)对数组a任何元素的赋值之后；对数组a任何元素的赋值，都必须跟在原来位于其前面的对数组a任何元素的引用之后。第5章代码优化(2)对任何标识符的引用或赋值，都必须跟在原来位于其前面的任何过程调用或通过指针的间接赋值之后；任何过程调用或通过指针的间接赋值，都必须跟在原来位于其前面的任何标识符的引用或赋值之后。总之，当对基本块重

25、写时，任何数组a的引用不允许互相调换次序，并且任何语句不得跨越一个过程调用语句或者通过指针的间接赋值。第5章代码优化 5.2 循循 环环 优优 化化5.2.1 程序流图与循环程序流图与循环为了进行循环优化，必须先找出程序中的循环。由程序语言的循环语句形成的循环是不难找出的，但由条件转移语句和无条件转移语句同样可以形成程序中的循环，并且其结构可能更加复杂。因此，为了找出程序中的循环，就需要对程序中的控制流程进行分析。我们应用程序的控制流程图来给出循环的定义并找出程序中的循环。一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点，就是从它开始到控制流程图中任何一个结点都有一条通路的结点

26、。我们可以把控制流程图表示成一个三元组G=(N,E,n0)；其中，N代表图中所有结点集，E代表图中所有有向边集，n0代表首结点。第5章代码优化 一个程序可用一个流图来表示。流图的有限结点集N就是程序的基本块集，流图中的结点就是程序的基本块，流图的首结点就是包含程序第一个语句的基本块。流图的有向边集E是这样构成的：假设流图中结点i和结点j分别对应于程序的基本块i和基本块j，则当下述条件有一个成立时，从结点i有一条有向边引到结点j：(1)基本块j在程序中的位置紧跟在基本块i之后，并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。第5章代码优化(2)基本块i的出口语句是goto(s)或

27、ifgoto(s)，并且(s)是基本块j的入口语句。在以后的讨论中，我们所涉及的流图都是程序流图。程序流图和基本块的DAG是不同的概念。程序流图是对整个程序而言的，它表示了各基本块(对应流图中的一个结点)之间的控制关系，图中可以出现环路；DAG是对基本块而言的，是局限于该基本块内的无环路有向图，它表示了这个基本块内各四元式的操作及相互关系。第5章代码优化 我们仍以下面求最大公因子的三地址代码程序为例来求其程序流图：(1)readX(2)readY(3)R=X%Y(4)ifR=0goto(8)(5)X=Y(6)Y=R(7)goto(3)(8)writeY(9)halt我们知道，该程序的基本块分别

28、为(1)(2)，(3)(4)，(5)(6)(7)和(8)(9)。按构造流图结点间有向边的方法，我们得到该程序的程序流图如图53所示。第5章代码优化 图53求最大公因子的程序流图第5章代码优化 有了程序流图，我们就可以对所要讨论的循环结构给出定义。在程序流图中，我们称具有下列性质的结点序列为一个循环：(1)它们是强连通的，其中任意两个结点之间必有一条通路，而且该通路上各结点都属于该结点序列；如果序列只包含一个结点，则必有一条有向边从该结点引到其自身。(2)它们中间有一个而且只有一个是入口结点。所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点有一条有向边引到它，或者它就是程序流图的首结点

29、。第5章代码优化 注意：此处定义的循环就是程序流图中具有惟一入口结点的强连通子图。从循环外要进入循环，必须先经过循环的入口结点。对于性质(1)，任意两个结点之间必有一条通路，即通路上的尾结点到首结点之间也有一条通路(实际上可认为无首尾之分)，这就构成了一个环形通路。该通路上的各结点都属于该结点序列，即从通路上的任何结点开始所构成的序列都包含该通路上的所有结点，这仍然构成了一个环形通路。因此，性质(1)是任何一种循环结构所必须具备的，否则该结点序列必有一部分是不可能反复执行的。性质(2)出于对循环优化的考虑，当需要把循环中某些代码(如不随循环反复执行而改变的运算)提到循环之外时，可以将代码提到循

30、环结构的惟一入口结点的前面。第5章代码优化 例如，对图53所示的程序流图，由上述循环的定义可知，结点序列B2，B3是程序中的一个循环，其中，B2是循环的惟一入口结点。对图54所示的程序流图，结点序列6因其只有一个结点且有一有向边引到自身，并且只有惟一的入口结点6，故是我们所定义的循环。而2,3,4,5,6,7中的任意两个结点之间都存在通路(即为强连通)，且有惟一的入口结点2，故也是我们所定义的循环。此外，4,5,6,7也是强连通且有惟一入口结点4，虽然到入口结点4的有向边不止一条，但仍然是我们所定义的循环。而2,4和2,3,4，它们虽然是强连通的，但却存在两个入口结点2、4，故不是我们所定义的

31、循环。4,5,7和4,6,7也因其存在两个入口结点4、7而不是我们所定义的循环。第5章代码优化 图54程序流图第5章代码优化 5.2.2 循环的查找循环的查找1必经结点集必经结点集为了找出程序流图中的循环，需要分析流图中结点的控制关系，为此我们引入必经结点和必经结点集的定义。在程序流图中，对任意结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为mDOMn；流图中结点n的所有必经结点的集合称为结点n的必经结点集，记为D(n)。显然，循环的入口结点是循环中所有结点的必经结点；此外，对任何结点n来说都有nDOMn。第5章代码优化 如果把DOM看作流图结点集上定

32、义的一个关系，则由定义容易看出它具有下述性质：(1)自反性：对流图中任意结点a，都有aDOMa。(2)传递性：对流图中任意结点a、b、c，若存在aDOMb和bDOMc,则必有aDOMc。(3)反对称性：若存在aDOMb和bDOMa，则必有a=b。因此，关系DOM是一个偏序关系，任何结点n的必经结点集是一个有序集。例5.2求图54中流图各结点的D(n)。第5章代码优化 解答考察图54的流图并由必经结点的定义容易看出：首结点1是所有结点的必经结点；结点2是除去结点1之外所有结点的必经结点；结点4是结点4、5、6、7的必经结点；而结点3、5、6、7都只是其自身的必经结点。因此，直接由定义和DOM的性

33、质可求得：D(1)=1D(2)=1，2D(3)=1，2，3D(4)=1，2，4D(5)=1，2，4，5D(6)=1，2，4，6D(7)=1，2，4，7下面我们给出求流图G=(N，E，n0)的所有结点n的必经结点集D(n)的算法；其中，P(n)代表结点n的前驱结点集，它可以从边集E中直接求出。第5章代码优化 D(n0)=n0;for(nNn0)D(n)=N;/*置初值*/change=true;while(change)change=false;for(nNn0)第5章代码优化 if(new!=D(n)change=true;D(n)=new;第5章代码优化 注意：由于算法中是利用所有前驱信息进

34、行运算来获得某结点对应的必经结点集的，因此迭代初值D(ni)必须取最大值，即全集N。此外，由知表示结点n的所有前驱(即父结点)的必经结点集的交集即为n的必经结点集。由图55可看出，ni为nj的必经结点(ni为结点nj所有前驱nk1nkn必经结点集的交集)，而nk1nkn都不是nj的必经结点。另一点要说明的是，因程序流图中有循环情况，所以后面计算的结点其必经结点集D(nj)的改变可能要影响到前面所计算的D(ni)值。因此，在一次迭代计算结束时，只要发现某一个D(nk)被改变，就必须进行下一次迭代来计算各结点的D(n)(即算法中的while循环继续执行)，直至全部结点的D(n)都不改变为止(即算法

35、中的change值为false才结束算法的执行)。第5章代码优化 图55ni为nj的必经结点示意第5章代码优化 例5.3应用求流图必经结点集的算法求图54所示程序流图各结点n的D(n)。解答算法求解过程如下：首先置初值：D(1)=1D(2)=D(3)=D(4)=D(5)=D(6)=D(7)=1,2,3,4,5,6,7置change为false，然后从结点2到结点7依次执行第二个for循环。对结点2，因new=2D(1)D(4)=211,2,3,4,5,6,7=21=1,2但迭代前D(2)=1,2,3,4,5,6,7，故D(2)new，因此置change=true并令D(2)=1,2。对结点3，

36、因new=3D(2)=31,2=1,2,3但迭代前D(3)=1,2,3,4,5,6,7，故D(3)new，因此令D(3)=1,2,3。第5章代码优化 其余各结点按照上述步骤可求出：D(4)=4D(2)D(3)D(7)=41,21,2,31,2,3,4,5,6,7=1,2,4D(5)=5D(4)=1,2,4,5D(6)=6D(4)=1,2,4,6D(7)=7D(5)D(6)=71,2,4,51,2,4,6=1,2,4,7一次迭代完毕后，因change为true，故还要进行下一次迭代。先令change为false，然后继续从结点2到结点7依次执行第二个for循环。第5章代码优化 对结点2，因new

37、=2D(1)D(4)=211,2,4=21=1,2而迭代前D(2)=1,2，所以D(2)=new，故D(2)不变。对结点3，因new=3D(2)=31,2=1,2,3及迭代前D(3)=1,2,3，所以D(3)=new，故D(3)不变。对其余结点n(n=47)求出的new均有D(n)=new，所以第二次迭代后change为false，迭代结束，第一次迭代求出的各个D(n)就是最后的结果。第5章代码优化 2回边查找循环的方法是：首先应用必经结点集来求出流图中的回边，然后利用回边找出流图中的循环。回边的定义如下：假设ab是流图中一条有向边，如果bDOMa，则称ab是流图中的一条回边。对于一已知流图G

38、，只要求出各结点n的必经结点集，就可以立即求出流图中的所有回边。在求出流图G中的所有回边后，就可以求出流图中的循环。如果已知有向边nd是一条回边，则由它组成的循环就是由结点d、结点n以及有通路到达n但该通路不经过d的所有结点组成的。第5章代码优化 例5.4求出图54所示程序流图的所有回边。解答(1)已知D(6)=1,2,4,6，因存在66且6DOM6，故66是回边；(2)已知D(7)=1,2,4,7，因存在74且4DOM7，故74是回边；(3)已知D(4)=1,2,4，因存在42且2DOM4，故42是回边。容易看出，其它有向边都不是回边。第5章代码优化 寻找由回边组成循环的算法如下：main(

39、)stack=空;/*stack是一个工作栈*/loop=d;/*loop是所求的循环*/insert(m);while(stack非空)弹出stack栈顶元素m;for(pP(m)/*P(m)为结点m的前驱结点集*/insert(p);第5章代码优化 voidinsert(m)if(mloop)loop=loopm;把m压入栈stack;此算法中求回边nd组成循环的所有结点的方法是：由于循环以d为其惟一入口，n是循环的一个出口，因而只要n不同时是循环入口d，那么n的所有前驱就应属于循环。在求出n的所有前驱之后，只要它们不是循环入口d，就应再继续求出它们的前驱，而这些新求出的所有前驱也应属于循

40、环。然后再对新求出的所有前驱重复上述过程，直到所求出的前驱都是d为止。第5章代码优化 3可归约流图一个流图被称为可归约的，当且仅当流图中除去回边之外，其余的边构成一个无环路流图。例如，图54中的流图就是一个可归约流图，而图56则是一个不可归约流图，因为图56中虽然有23，但没有3DOM2，即23不是一个回边，对32也是如此。如果程序流图是可归约的，那么程序中任何可能反复执行的代码都会被求回边的算法纳入到一个循环当中。第5章代码优化 图56不可归约流图第5章代码优化 可归约流图是一类非常重要的流图，从代码优化的角度来说，它具有下述重要的性质：(1)图中任何直观意义下的环路都属于我们所定义的循环。

41、(2)只要找出图中的所有回边，对回边应用查找循环的方法，就可以找出流图中的所有循环。(3)图中任意两个循环要么嵌套，要么不相交(除了可能有公共的入口结点)，对这类流图进行循环优化较为容易。应用结构程序设计原则写出的程序，其流图总是可归约的；而应用高级语言写出的程序，其流图往往也是可归约的。第5章代码优化 例5.5四元式序列如下：(1)J=0；(2)L1：I=0；(3)ifI8gotoL3;(4)L2：A=B+C；(5)B=D*C;(6)L3：ifB=0gotoL4;(7)writeB;(8)gotoL5;(9)L4：I=I+1;(10)ifI8gotoL2;(11)L5：J=J+1;(12)i

42、fJ3gotoL1;(13)halt画出该四元式序列的程序流图G并求出G中的回边与循环。第5章代码优化 解答该四元式序列的基本块与程序流图如图57所示。图57中各结点的必经结点集如下：D(B1)=B1D(B5)=B1,B2,B4,B5D(B2)=B1,B2D(B6)=B1,B2,B4,B6D(B3)=B1,B2,B3D(B7)=B1,B2,B4,B7D(B4)=B1,B2,B4D(B8)=B1,B2,B4,B7,B8考察流图中的有向边B7B2且已知D(B7)=B1,B2,B4,B7，所以有B2DOMB7，即B7B2是流图中的回边。容易看出，其它有向边都不是回边。因B7B2是一条回边，则在流图中

43、能够不经过结点B2且有通路到达结点B7的结点只有B3、B4、B5和B6，故由回边B7B2组成的循环是：B2,B3,B4,B5,B6,B7。第5章代码优化 图57例5.5的程序流图第5章代码优化 5.2.3 循环优化循环优化对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。1代码外提循环中的代码要随着循环反复执行，但其中某些运算的结果并不因循环而改变，对于这种不随循环变化的运算，可以将其外提到循环外。这样，程序的运行结果仍保持不变，但程序的运行效率却提高了。我们称这种优化为代码外提。实行代码外提时，在循环入口结点前面建立一个新结点(基本块)，称为循环的前置结点。循环前置结点以循环入口

44、结点为其惟一后继，原来流图中从循环外引到循环入口结点的有向边改成引到循环前置结点，如图58所示。第5章代码优化 图58给循环建立前置结点第5章代码优化 因为在我们所定义的循环结构中，其入口结点是惟一的，所以前置结点也是惟一的。循环中外提的代码将统统外提到前置结点中。但是，循环中的不变运算并不是在任何情况下都可以外提的。对循环L中的不变运算S：A=BopC或A=opB或A=B，要求满足下述条件(A在离开L后仍是活跃的)：(1)S所在的结点是L的所有出口结点的必经结点；(2)A在L中其它地方未再定值；(3)L中的所有A的引用点只有S中A的定值才能到达。第5章代码优化 图59代码外提的程序流图示例对

45、上述三个条件，我们给出图59所示的三种流图予以说明。第5章代码优化(1)对图59(a)，先将B3中的循环不变运算I=2外提到循环前置结点B2中，如图510所示。由图59(a)可知，B3并不是出口结点B4的必经结点。如果令X=30，Y=25，则按图59(a)的程序流图，B3是不会执行的；于是，当执行到B5时，I的值是1。但是，如果按图510执行，则执行到B5时，I的值总是2，因此图510改变了原来程序运行的结果。出现以上问题是因为B3不是循环出口结点B4的必经结点，因此当把一不变运算外提到循环前置结点时，要求该不变运算所在的结点是循环所有出口结点的必经结点。第5章代码优化 图510将图58(a)

46、中的I=2外提后的程序流图第5章代码优化(2)考查图59(b)，现在I=3所在的结点B2是循环出口结点的必经结点，但循环中除B2外，B3也对I定值。如果把B2中的I=3外提到循环前置结点中，且循环前X=21和Y=22，程序此时执行的顺序是B2B3B4B2B4B5，则到达B5时I值为2；但如果不把B2中的I=3外提，则经过以上执行顺序到达B5时，I值为3。由此可知，当把循环中的不变运算A=BopC外提时，要求循环中其它地方不再有A的定值点。第5章代码优化(3)考查图59(c)，不变运算I=2所属结点B4本身就是出口结点，而且此循环只有一个出口结点，同时循环中除B4外其它地方没有I的定值点；因此，

47、它满足外提的条件(1)、(2)。我们注意到，对循环中B3的I的引用点，不仅B4中I的定值能够到达，而且B1中I的定值也能到达。现在考虑进入循环前X=0和Y=2时的情况，此时循环的执行顺序为B2B3B4B2B4B5，当到达B5时A值为2；但如果把B4中的I=2外提，则到达B5时A值为3。因此当把循环不变运算A=BopC外提时，要求循环中A的所有引用点都是而且仅仅是该定值所能到达的。第5章代码优化 根据以上讨论，给出查找所需处理的循环L中的不变运算和代码外提的算法如下：(1)依次查看L中各基本块的每个四元式，如果它的每个运算对象为常数或者定值点在L外，则将此四元式标记为“不变运算”。(2)依次查看

48、尚未被标记为“不变运算”的四元式，如果它的每个运算对象为常数或定值点在L之外，或只有一个到达一定值点且该点上的四元式已标记为“不变运算”，则把被查看的四元式标记为“不变运算”。(3)重复第(2)步直至没有新的四元式被标记为“不变运算”为止。例如，循环中的A=3已标记为“不变运算”，则对循环中A=3定值点可惟一到达的X=A+2也标记为“不变运算”。第5章代码优化 找出了循环的不变运算就可以进行代码外提了。代码外提算法如下：(1)求出循环L的所有不变运算。(2)对步骤(1)所求得的每一不变运算S：A=BopC或A=opB或A=B，检查它是否满足以下条件：i.S所在的结点是L的所有出口结点的必经结点

49、；ii.A在L中其它地方未再定值；iii.L中所有A的引用点只有S中A的定值才能到达。A在离开L后不再是活跃的(即离开L后不会引用该A值)，并且条件的ii.和iii.两条成立。所谓A在离开L后不再是活跃的，是指A在L的任何出口结点的后继结点(当然是指那些不属于L的后继)的入口处不是活跃的。第5章代码优化(3)按步骤(1)所找出的不变运算的顺序，依次把步骤(2)中满足条件的不变运算S外提到L的前置结点中。但是，如果S的运算对象(B或C)是在L中定值的，那么只有当这些定值四元式都已外提到前置结点中时，才可把S也外提到前置结点中(B、C的定值四元式提到前置结点后，S的运算对象B、C就属于定值点在L之

50、外了，因此也就是真正的“不变运算”了)。注意：如果把满足条件(2)的不变运算A=B op C外提到前置结点中，则执行完循环后得到的A值可能与不进行外提的情形所得的A值不同，但因为离开循环后不会引用该A值，所以这不影响程序的运行结果。第5章代码优化 例5.6试对图511给定的程序流图进行代码外提优化。解答确定不变运算的原则是依次查看循环中各基本块的每个四元式，如果它的每个运算对象为常数或者定值点在循环外，则将此四元式标记为“不变运算”。查看图511所示的程序流图，可以找出的不变运算是B3中的I=2和B4中的J=M+N。进行代码外提时，只能将J=M+N提到循环前置结点。因为B3中的I=2虽然是不变