第5章编译原理代码优化.ppt
《第5章编译原理代码优化.ppt》由会员分享,可在线阅读,更多相关《第5章编译原理代码优化.ppt(135页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第5 5章章 代码优化代码优化 第第5章章 代码优化代码优化 5.1 局部优化局部优化 5.2 循环优化循环优化 5.3 代码优化示例代码优化示例 第第5 5章章 代码优化代码优化 5.1 局局 部部 优优 化化局部优化是指对代码的每一个线性部分所进行的优化,使得在这个线性部分只存在一个入口和一个出口,而这个线性部分我们称之为基本块。第第5 5章章 代码优化代码优化 5.1.1基本块的划分方法所谓基本块,是指程序中一顺序执行的语句序列,其中只有一个入口和一个出口,入口就是该序列的第一个语句,出口就是该序列的最后一个语句。对一个基本块来说,执行时只能从其入口进入,从其出口退出。对一个给定的程序
2、,我们可以把它划分为一系列基本块,在各个基本块范围内进行的优化称为局部优化。第第5 5章章 代码优化代码优化 划分基本块的关键问题是准确定义入口和出口语句。下面我们给出划分四元式程序为基本块的算法:(1)从四元式序列确定满足以下条件的入口语句:四元式序列的第一个语句;能由条件转移语句或无条件转移语句转移到的语句;紧跟在条件转移语句后面的语句。第第5 5章章 代码优化代码优化 (2)确定满足以下条件的出口语句:下一个入口语句的前导语句;转移语句(包括转移语句自身);停语句(包括停语句自身)。第第5 5章章 代码优化代码优化 例如,考察下面求最大公因子的三地址代码程序:(1)readX(2)rea
3、dY(3)R=X%Y(4)ifR=0goto(8)(5)X=Y(6)Y=R(7)goto(3)(8)writeY(9)halt第第5 5章章 代码优化代码优化 5.1.2基本块的DAG表示DAG(DirectedAcyclicGraph)是一种有向图,常常用来对基本块进行优化。一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG:(1)图的叶结点(无后继的结点)以一标识符(变量名)或常数作为标记,表示该结点代表该变量或常数的值。如果叶结点用来表示一变量A的地址,则用addr(A)作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0,以表示它是该变量的初值。第第5 5章章 代码优化
4、代码优化 (2)图的内部结点(有后继的结点)以一运算符作为标记,表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。(3)图中各个结点上可能附加一个或多个标识符,表示这些变量具有该结点所代表的值。第第5 5章章 代码优化代码优化 一个基本块由一个四元式序列组成,且每一个四元式都可以用相应的DAG结点表示。图51给出了不同四元式和与其对应的DAG结点形式。图中,各结点圆圈中的ni是构造DAG过程中各结点的编号,而各结点下面的符号(运算符、标识符或常数)是各结点的标记,各结点右边的标识符是结点上的附加标识符。除了对应转移语句的结点右边可附加一语句位置来指示转移目标外,其余各类结点的
5、右边只允许附加标识符。除对应于数组元素赋值的结点(标记为=)有三个后继外,其余结点最多只有两个后继。第第5 5章章 代码优化代码优化 图51四元式与DAG结点第第5 5章章 代码优化代码优化 利用DAG进行基本块优化的基本思想是:首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG,然后按构造结点的次序将DAG还原成四元式序列。由于在构造DAG的同时已作了局部优化,所以最后所得到的是优化过的四元式序列。为了DAG构造算法的需要,我们将图51中的四元式按照其对应结点的后继结点个数分为四类:第第5 5章章 代码优化代码优化 (1)0型四元式:后继结点个数为0,如图51(1)所示;(2)1型
6、四元式:有一个后继结点,如图51(2)所示;(3)2型四元式:有两个后继结点,如图51(3)、(4)、(5)所示;(4)3型四元式:有三个后继结点,如图51(6)所示。第第5 5章章 代码优化代码优化 我们规定:用大写字母(如A、B等)表示四元式中的变量名(或常数);用函数Node(A)表示A在DAG中的相应结点,其值可为n或者无定义,并用n表示DAG中的一个结点值。这样,每个基本块仅含0、1、2型四元式的DAG构造算法如下(对基本块的每一个四元式依次执行该算法):第第5 5章章 代码优化代码优化 (1)若Node(B)无定义,则构造一标记为B的叶结点并定义Node(B)为这个结点,然后根据下
7、列情况做不同处理:若当前四元式是0型,则记Node(B)的值为n,转(4)。若当前四元式是1型,则转(2)。若当前四元式是2型,则:i.如果Node(C)无定义,则构造一标记为C的叶结点,并定义Node(C)为这个结点;ii.转(2)。第第5 5章章 代码优化代码优化 (2)若Node(B)是以常数标记的叶结点,则转(2),否则转(3)。若Node(B)和Node(C)都是以常数标记的叶结点,则转(2),否则转(3)。执行opB(即合并已知量),令得到的新常数为P。若Node(B)是处理当前四元式时新建立的结点,则删除它;若Node(P)无定义,则构造一用P做标记的叶结点n并置Node(P)=
8、n;转(4)。第第5 5章章 代码优化代码优化 执行BopC(即合并已知量),令得到的新常数为P。若Node(B)或Node(C)是处理当前四元式时新建立的结点,则删除它;若Node(P)无定义,则构造一用P做标记的叶结点n并置Node(P)=n;转(4)。(3)检查DAG中是否有标记为op且以Node(B)为惟一后继的结点(即查找公共子表达式)。若有,则把已有的结点作为它的结点并设该结点为n;若没有,则构造一个新结点;转(4)。第第5 5章章 代码优化代码优化 检查DAG中是否有标记为op且其左后继为Node(B)、右后继为Node(C)的结点(即查找公共子表达式)。若有,则把已有的结点作为
9、它的结点并设该结点为n;若没有,则构造一个新结点;转(4)。(4)若Node(A)无定义,则把A附加在结点n上并令Node(A)=n;否则,先从Node(A)的附加标识符集中将A删去(注意,若Node(A)是叶结点,则不能将A删去),然后再把A附加到新结点n上,并令Node(A)=n。解答按照算法顺序处理每一四元式后构造出的DAG如图52所示,其中每一子图(1)、(2)、(10)分别对应四元式(1)(10)的DAG构造。第第5 5章章 代码优化代码优化 图52DAG第第5 5章章 代码优化代码优化 构造过程说明如下:(1)对应图52(2),四元式T1=2*T0首先执行算法中的步骤(1),因No
10、de(B)无定义,所以构造一个标记为2的叶结点并定义Node(2)为这个结点;因当前四元式是2型且Node(C)已有定义(此时为Node(T0),转算法步骤(2);因Node(B)=Node(2)和Node(C)=Node(T0)都是标记为常数的叶结点,则执行BopC并令新结点为P(=6.28);由于Node(P)无定义,故构造Node(P)=Node(6.28);第第5 5章章 代码优化代码优化 此外,因Node(B)=Node(2)是处理当前四元式时新构造出来的结点,故删除n2;接下来执行算法步骤(4),因Node(A)无 定 义 而 将 T1附 加 在 结 点 n3上,并 令Node(T
11、1)=6.28;最后DAG生成了2个结点n1和n3,因结点n2被删除而将n3改名为n2。图52(2)的形成过程实际上也是合并已知量的优化过程。(2)图52(4)中T1、T2已有定义,则仅生成一个新结点n6并将A附加在n6上。图5-2(5)中结点B已有定义,故直接附加在n6上。第第5 5章章 代码优化代码优化 (3)图52(6)的处理过程与图52(2)略同,但在生成P时因其已在DAG中(即Node(6.28),故不生成新结点而直接将T3附加在结点6.28上。(4)图52(7)的生成过程实质上是删除多余运算(删除公共子表达式)的优化。因为DAG中已有叶结点R与叶结点r,并且执行op操作后得到的新结
12、点T2也已经在DAG中,故执行算法步骤(4)时因T4无定义而将T4附加在结点n5上。第第5 5章章 代码优化代码优化 (5)图52(9)中,变量R和r已在DAG中有相应的结点,执行“”操作后,产生的新结点P无定义,故仅生成一个新结点n7并将T6标记于其上。(6)图52(10)中,对当前四元式B=T5*T6,DAG中已有结点T5和T6;执行算法步骤(4)时因结点B已有定义且不是叶结点,故先将原B从DAG中删除,然后生成一个新结点n8,将B附加其上并令Node(B)=n8。这一处理过程实质上是删除了无用赋值B=A。第第5 5章章 代码优化代码优化 5.1.3利用DAG进行基本块的优化处理利用DAG
13、进行基本块优化处理的基本思想是:按照构造DAG结点的顺序,对每一个结点写出其相应的四元式表示。我们根据例5.1DAG结点的构造顺序,按照图52(10)写出四元式序列G如下:第第5 5章章 代码优化代码优化 (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(9)B=A*T6第第5 5章章 代码优化代码优化 将G和原基本块G相比,我们看到:(1)G中四元式(2)和(6)都是已知量和已知量的运算,G已合并;(2)G中四元式(5)是一种无用赋值,G已将它删除;(3)G中四元式(3)和(7)的R+r是公共
14、子表达式,G只对它们计算了一次,即删除了多余的R+r运算。因此,G是对G实现上述三种优化的结果。第第5 5章章 代码优化代码优化 通过观察图52(10)中的所有叶结点和内部结点以及其上的附加标识符,还可以得出以下结论:(1)在基本块外被定值并在基本块内被引用的所有标识符就是DAG中相应叶结点上标记的标识符;(2)在基本块内被定值且该值能在基本块后面被引用的标识符就是DAG各结点上的附加标识符。第第5 5章章 代码优化代码优化 这些结论可以引导优化工作的进一步深入,尤其是无用赋值的优化,也即:(1)如果DAG中某结点上的标识符在该基本块之后不会被引用,就可以不生成对该标识符赋值的四元式。(2)如
15、果某结点ni上没有任何附加标识符,或者ni上的附加标识符在该基本块之后不会被引用,而且ni也没有前驱结点,这表明在基本块内和基本块之后都不会引用ni的值,那么就不生成计算ni结点值的四元式。第第5 5章章 代码优化代码优化 (3)如果有两个相邻的四元式A=CopD和B=A,其中第一条代码计算出来的A值仅在第二个四元式中被引用,则将DAG中相应结点重写成四元式时,原来的两个四元式可以优化为B=CopD。假设例5.1中T0、T1、T2、T3、T4、T5和T6在基本块后都不会被引用,则图5-2(10)中的DAG就可重写为如下的四元式序列:第第5 5章章 代码优化代码优化 (1)S1=R+r/*S1、
16、S2为存放中间结果的临时变量*/(2)A=6.28*S1(3)S2=Rr(4)B=A*S2第第5 5章章 代码优化代码优化 以上把DAG重写成四元式序列时,是按照原来构造DAG结点的顺序(即n5、n6、n7、n8)依次进行的。实际上,我们还可以采用其它顺序(如自下而上)重写,只要其中的任何一个内部结点是在其后继结点之后被重写并且转移语句(如果有的话)仍然是基本块的最后一个语句即可。第第5 5章章 代码优化代码优化 5.1.4DAG构造算法的进一步讨论当基本块中有数组元素引用、指针和过程调用时,构造DAG算法就较为复杂。例如,考虑如下的基本块G:(1)x=ai(2)aj=y(3)z=ai第第5
17、5章章 代码优化代码优化 如果我们用构造DAG的算法来构造上述基本块的DAG,则ai就是一个公共子表达式;且由所构造的DAG重写出优化后的四元式序列G如下:(1)x=ai(2)z=x(3)ai=y第第5 5章章 代码优化代码优化 如果ij,则G与G是等效的。但是,如果i=j且yai,则将y值赋给aj的同时也改变了ai的值(因i=j);这时z值应为改变后的ai值(即y值),与x不等。为了避免这种情况的发生,当我们构造对数组a的元素赋值句的结点时,就“注销”所有标记为且左边变量是a(可加上或减去一个常数)的结点。我们认为对这样的结点再添加附加标识符是非法的,从而取消了它作为公共子表达式的资格。第第
18、5 5章章 代码优化代码优化 对指针赋值语句*p=w(其中p是一个指针)也会产生同样的问题,如果我们不知道p可能指向哪一个变量,那么就认为它可能改变基本块中任何一个变量的值。当构造这种赋值句的结点时,就需要把DAG各结点上所有标识符(包括作为叶结点上标记的标识符)都予以注销,这也就意味着DAG中所有的结点也都被注销。在一个基本块中的一个过程调用将注销所有的结点,因为对被调用过程的情况缺乏了解,我们必须假定任何变量都可能因产生副作用而发生变化。第第5 5章章 代码优化代码优化 此外,当把DAG重写成四元式时,如果我们不是按照原来构造DAG结点的顺序进行重写,那么DAG中的某些结点必须遵守一定的顺
19、序。例如,在上述基本块G中,z=ai必须跟在aj=y之后,而aj=y则必须跟在x=ai之后。下面,我们根据上述讨论把重写四元式时DAG中结点间必须遵守的顺序归纳如下:第第5 5章章 代码优化代码优化 (1)对数组a中任何元素的引用或赋值,都必须跟在原来位于其前面的(如果有的话,下同)对数组a任何元素的赋值之后;对数组a任何元素的赋值,都必须跟在原来位于其前面的对数组a任何元素的引用之后。(2)对任何标识符的引用或赋值,都必须跟在原来位于其前面的任何过程调用或通过指针的间接赋值之后;任何过程调用或通过指针的间接赋值,都必须跟在原来位于其前面的任何标识符的引用或赋值之后。第第5 5章章 代码优化代
20、码优化 5.2 循循 环环 优优 化化5.2.1程序流图与循环为了进行循环优化,必须先找出程序中的循环。由程序语言的循环语句形成的循环是不难找出的,但由条件转移语句和无条件转移语句同样可以形成程序中的循环,并且其结构可能更加复杂。因此,为了找出程序中的循环,就需要对程序中的控制流程进行分析。我们应用程序的控制流程图来给出循环的定义并找出程序中的循环。第第5 5章章 代码优化代码优化 一个控制流程图(简称流图)就是具有惟一首结点的有向图。所谓首结点,就是从它开始到控制流程图中任何一个结点都有一条通路的结点。我们可以把控制流程图表示成一个三元组G=(N,E,n0);其中,N代表图中所有结点集,E代
21、表图中所有有向边集,n0代表首结点。第第5 5章章 代码优化代码优化 一个程序可用一个流图来表示。流图的有限结点集N就是程序的基本块集,流图中的结点就是程序的基本块,流图的首结点就是包含程序第一个语句的基本块。流图的有向边集E是这样构成的:假设流图中结点i和结点j分别对应于程序的基本块i和基本块j,则当下述条件有一个成立时,从结点i有一条有向边引到结点j:第第5 5章章 代码优化代码优化 (1)基本块j在程序中的位置紧跟在基本块i之后,并且基本块i的出口语句不是无条件转移语句goto(s)或停语句。(2)基本块i的出口语句是goto(s)或ifgoto(s),并且(s)是基本块j的入口语句。在
22、以后的讨论中,我们所涉及的流图都是程序流图。程序流图和基本块的DAG是不同的概念。程序流图是对整个程序而言的,它表示了各基本块(对应流图中的一个结点)之间的控制关系,图中可以出现环路;DAG是对基本块而言的,是局限于该基本块内的无环路有向图,它表示了这个基本块内各四元式的操作及相互关系。第第5 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第第5 5章章 代码优化代码优化 图53求最大公因子的程序流图第
23、第5 5章章 代码优化代码优化 我们知道,该程序的基本块分别为:(1)(2),(3)(4),(5)(6)(7)和(8)(9),按构造流图结点间有向边的方法,我们得到该程序的程序流图如图53所示。有了程序流图,我们就可以对所要讨论的循环结构给出定义。在程序流图中,我们称具有下列性质的结点序列为一个循环:第第5 5章章 代码优化代码优化 (1)它们是强连通的,其中任意两个结点之间必有一条通路,而且该通路上各结点都属于该结点序列;如果序列只包含一个结点,则必有一条有向边从该结点引到其自身。(2)它们中间有一个而且只有一个是入口结点。所谓入口结点,是指序列中具有下述性质的结点:从序列外某结点有一条有向
24、边引到它,或者它就是程序流图的首结点。第第5 5章章 代码优化代码优化 例如,对图53所示的程序流图,由上述循环的定义可知,结点序列B2,B3是程序中的一个循环,其中,B2是循环的惟一入口结点。对图54所示的程序流图,结点序列6因其只有一个结点且有一有向边引到自身,并且只有惟一的入口结点6,故是我们所定义的循环;而2,3,4,5,6,7中的任意两个结点之间都存在通路(即为强连通),且有惟一的入口结点2,故也是我们所定义的循环;此外,4,5,6,7也是强连通且有惟一入口结点4,虽然到入口结点4的有向边不止一条,但仍然是我们所定义的循环。第第5 5章章 代码优化代码优化 图54程序流图第第5 5章
25、章 代码优化代码优化 而2,4和2,3,4,它们虽然是强连通的,但却存在两个入口结点2、4,故不是我们所定义的循环;4,5,7和4,6,7也因其存在两个入口结点4、7而不是我们所定义的循环。第第5 5章章 代码优化代码优化 5.2.2循环的查栈1必经结点集为了找出程序流图中的循环,需要分析流图中结点的控制关系,为此我们引入必经结点和必经结点集的定义。在程序流图中,对任意结点m和n,如果从流图的首结点出发,到达n的任一通路都要经过m,则称m是n的必经结点,记为mDOMn;流图中结点n的所有必经结点的集合称为结点n的必经结点集,记为D(n)。第第5 5章章 代码优化代码优化 显然,循环的入口结点是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第5章 编译原理代码优化 编译 原理 代码 优化
限制150内