资源目录
压缩包内文档预览：(预览前20页/共59页)
编号：21836409
类型：共享资源
大小：13.06MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
编译
原理
实用教程
杨德芳
课件
ppt
- 资源描述：
-
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
- 内容简介：
-
第八章 代码优化,本章学习目标,源程序经过词法分析、语法分析、语义分析等阶段的编译后，就得到和与源程序等价的中间代码。但是，此时的中间代码是“机械”生成的，有很多冗余代码，降低了效率，因此，需要进行代码的优化。代码优化的目的是为了提高目标程序的质量。 优化可以分为局部优化、循环优化和全局优化。本章要点： 局部优化 循环优化 全局优化,8.1优化的概念,8.1.1 优化概述 所谓优化，一般是指为提高目标程序的质量而进行的各项工作。即对程序或中间代码进行各种等价的变换，使得从变换后的程序出发，能生成更有效的目标代码。这里所说的质量，通常就是指目标程序所占的存储空间的大小和运行目标程序所需要的时间的多少。优化的目的在于，既要设法缩小存储空间，又要尽量提高运行速度，而且常常偏重于提高运行速度。,代码涉及面很广，从优化与机器的关系出发，可将优化分为与机器无关的优化和与机器相关的优化。与机器无关的优化可以在源程序或中间语言程序一级上进行。这类优化主要包括常数合并公共表达式的消除循环中不变式的外提运算强度的削弱等。,此外，从优化与源程序的关系而言，可以把优化分为局部优化和全局优化。局部优化通常指只有一个入口（即程序段的第一条代码）和一个出口（即程序段的最后一条代码）的基本块上的优化。因为只有一个出口和一个入口，所以是线性的，处理起来比较简单，但是效果较差。全局优化是指在非线性程序块上的优化，由于程序块是非线性的，因此需要分析比基本块更大的程序块乃至整个源程序的控制流程，需要考虑较多的因素。这样的优化比较复杂，开销大，但是效果较好。,与机器相关的优化是在目标机上进行的，这类优化主要包括寄存器的优化并行分支优化窥孔优化等。与机器相关的优化依赖于机器。,8.1.2 优化技术的简介 为了说明问题，我们来看下面的例子，源程序如下： p：=0 for I:=1 to 20 do p:=p+AI*BI,1删除多余的运算（删除公共子表达式） 优化的目的是在于使目标代码的执行速度较快。图中（3）和（6）是一个重复的运算，有一个是多余的。将（6）变为T4=T1；这种优化的方式为删除公共子表达式。,2代码外提 代码外提为了减少循环中代码的总数。这种方法就是把循环中不变的运算提到循环的外面，使之只在循环外计算一次。经过删除和循环外提后得到的中间代码变如图8-3所示。,3强度削弱 强度削弱就是把强度大的运算换算成强度小的运算，例如把乘法运算换算成加法运算等。例如：（3）T1:=4*I和（11）I=I+1变为T1:=T1+4 中间代码就变为图8-4。 4变换循环控制条件 将上面的循环控制条件变为： (12)if I20 goto(3)改为T180，这样整个程序的运行结果不变。这种变换称为变换循环控制条件，经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）可以从循环中删除，如图8-5所示。,5合并已知量与复写传播 （2）和（3）合并在一起，使得T1=4。这种变换称为合并已知量。同时把T1的值传递给T4，而（6）和（8）之间并没有改变T4和T1的值。这种方法叫复写传播。四元式序列变为图8-6所示。,6删除无用的赋值语句。 在图8-5中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，于是中间代码就变成图8-6所示。从上面的各个图我们能看出，经过优化后的代码条数明显减少，执行效率提高了很多。,8.2局部优化,局部优化是对代码的每一个线性部分进行优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分称之为基本块。 8.2 .1基本块的划分方法 所谓基本块，就是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是指该序列的第一条语句，出口就是该序列的最后一条语句。对于一个基本块来说，执行时只能从其入口进入，从其出口退出。对一个给定的程序，可以把它划分为一系列基本块，在各个基本块范围内进行的优化称为局部的优化。划分基本块的关键问题是准确定义入口和出口语句。下面给出划分四元式程序的基本块的算法： (1)从四元式的序列中确定满足以下条件的入口语句,1）四元式序列的第一条语句。 2）由条件转移语句或无条件转移语句转移到的语句。 3）紧跟在条件转移语句后面的语句。 （2）确定满足以下条件的出口语句 1）下一个入口语句的前导语句。 2）转移语句（包括转移语句自身）。 3）停语句（包括停语句自身。） 例如：考察下面求最大公因子的三地址代码程序。 （1）read x （2）read y （3）R=X%Y （4）IF R=0 goto (8) （5）x=y （6）y=R （7）goto (3) （8）write y （9）halt 根据基本块的划分原则可以确定为：（1）、（3）、（5）、（8）是入口语句，基本块的图示如图8-7所示。,8.2 2基本块的DAG表示,DAG（directed acyclic graph）是一种有向图，常常用来对基本块进行优化。一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。 （1）图的结点是以标识符或常数作为标记，表示该结点代表常数或变量值。如果叶结点表示一个变量的地址，则用addr(A)作为该结点的标记。 （2）图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其直接后继结点所代表的值进行运算的结果。 （3）图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。 一个基本块由一个四元式序列组成，且每一个四元式都有相应的DAG结点表示。,2利用DAG进行基本块优化的基本思想 首先按照基本块内的四元式顺序将所有的四元式构造成一个DAG，然后按构造结点的次序DAG还原为四元式序列，由于在构造DAG的同时已做了局部优化，所以最后所得到的是优化过的四元式序列。 四元式对应结点的分类。 0型结点：后继结点的个数为0个，如图8-8（a）所示。 1型结点：后继结点的个数为1个，如图8-8（b）所示。 2型结点：后继结点的个数为2个，如图8-8（c）和（d）（e）所示。 3型结点：后继结点的个数为3个，如图8.8（f）所示。,首先设DAG为空，对于基本块的每一个四元式，依次执行： （1）如果NODE(B)无定义，则构造一标记为B的叶结点并定义NODE(B)为这个结点； 1）如果当前四元式是0型，则记NODE(B)的值为n，转（4）。 2）如果当前四元式是1型，则转（2）的第1）步。 3）如果当前四元式是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）执行op B（即合并已知量），得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它；如果NODE(P)无定义，则构造一个用P做标记的叶结点n，并置NODE(P)=n；转（4）。,)执行op(即合并已知量)，令得到的新常数为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)，且标记为op。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转（4） （4）如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先从NODE(A)的附加标识符集中删除，把A附加到新结点n 上令NODE(A)=n，转处理下一个四元式，并令node(A)=n。,例8.1 试构造以下基本块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 处理每一个四元式，构造出DAG图如图8-9所示。,8.2.3用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,比较优化后的四元式序列和未优化之前的四元式序列可以看到： （1）中的四元式（）和（）都是已知量和已知量的运算，优化后合并。 （2）G中四元式（5）是一种无用赋值，在构造DAG时将它删除。 （3）G中四元式（3）和（7）的R+r是公共子表达式，G只对它们计算了一次，即删除了多余的R+r。 因此，G是对G实现上述三种优化的结果。 通过观察图8-9中的所有的叶结点和内部结点以及其上的附加标识符，还可以得出以下的结论： （1）在基本块外被定值，并在基本块内被引用的所有标识符就是DAG中相应的叶结点上标记的标识符。 （2）在基本块内被定值且该值能在基本块后面被引用的标识符就是DAG各个结点上的附加标识符。,这两条结论可以引导优化工作的进一步深入，尤其无用赋值的优化，即： （1）如果DAG中某结点上的标识符在该基本块之后不会被引用，就可以不生成对该标识符赋值的四元式。 （2）如果某结点ni也没有前驱结点，这表明在基本块内和基本块之后都不会引用ni的值，那么就不生成计算ni结点值的四元式。 （3）如果有两个相邻的四元式A=C OP D和B=A，其中第一条代码计算出来的A值仅在第二个四元式中被引用，则将DAG中相应结点重写成四元式，原来的两个四元式可以优化为B=C op D。,8.3循环优化,在编译程序的优化工作中，循环优化占有十分重要的地位。这是因为，对于循环次数为n的一个循环，每节省循环体内一条目标指令，运行时就可以少执行n条指令；特别是对于k重循环的内循环而言，每节省一条目标指令，运行时就可以少执行n1n2nk条指令，因此，从省时的角度看，循环优化的效果尤为显著。,此外，在高级语言的源程序中，数组元素的使用频率较高，且数组元素的使用通常是与循环相关联的。对于编译程序而言，就得在循环中计算数组元素的地址，而每次直接按数组元素的地址计算公式来计算数组元素的地址，其效率是很低的。特别是当数组元素位于多循环的内循环中时，由于其计算量很大，运行时间就会大大增加。,8.3.1程序流图,首先引入控制流程图的概念。一个控制流程图就是具有惟一首结点的有向图。所谓首结点就是从它开始到控制流程图中任何结点都有一条通路的结点。 例8.2构造以下程序的流图。 （1）read x （2）read y （3）R=X%Y （4）IF R=0 goto (8) （5）x=y （6）y=R （7）goto (3) （8）write y （9）halt 【解】首先我们将程序划分成基本块，然后构造有向边，得到程序流图如下图8-10所示。,画出了流程图8-10后，给出循环结构定义。在流程图中，我们称具有下列性质的结点序列为一个循环： （1）它们是强连通的，其中任意两个结点之间必须有一条通路，而且该通路上各结点都属于该结点序列；如果序列只包含一个结点，则必有一条有向边从该结点引到它的自身。 （2）它们中间有一个而且只有一个是入口的结点。所谓入口结点就是指序列中具有下述性质的结点：从序列外某结点有一条有向边引到它，或者它就是程序流图的首结点。,例如图8-10所示的程序流程图，该流程图中，B2，B3是程序中的一个循环 ，其中B2是循环的一个入口结点。 例如图8-11中，结点序列6因其只有一个结点且有一条有向边引到自身，并且只有惟一的入口结点6，故是我们所定义的循环；而2，3，4，5，6，7中任意两个结点之间都存在通路（强连通），且有惟一的入口结点2，故也是我们所定义的循环；此外，4，5，6，7也是强连通且有惟一入口结点4，虽然入口结点4的有向边不止一条，但仍然是我们所定义的循环。而2，4和2，3，4，它们虽然是强连通的，但是存在两个入口2、4，故不是我们所定义的循环；4，5，7和4，6，7也因其存在两个入口结点4、7而不是我们所定义的循环。,8.3.2循环的查找,为了找出程序流程图中的循环，需要分析流程图中结点的控制关系，为此引入必经结点和必经结点集的定义。 1必经结点 在程序流程图中，对任意两个结点m和n 而言，如果从流图的首结点出发，到达 n的任一通路都要经过m ，则称m是n的必经结点，记为m DOM n。 流程图中结点n的所有必经结点的集合，称为结点n的必经结点的集合，记为D(n)。,显然，循环的入口结点是循环中所有结点的必经结点；此外，对于任何结点n来说都有nMODn。 如果把DOM看作流程结点集上定义的一个关系，则由定义容易看出它具有下面的性质： （1）自反性：对于流程图中的任意结点a，都有a DOM a。 （2）传递性：对于流程图中的任意结点a、b、c ，若存在a DOM b和b DOM c，则必有a DOM c。 （3）反对称性：若存在a DOM b和b DOM a，则必有a=b。,例8.3求出图8-11中各结点的D(n). 【解答】考察图8-11的流图并由必经结点的定义容易看出,首结点1是所有结点的必经结点；结点2是除去结点1之外所有结点的必经结点；结点4是结点4、5、6、7的必经结点；而结点3、5、6、7都是其自身的必经结点；因此，直接由定义和DOM的性质可以求得： D(1)=1 D(2)=1,2 D(3)=1,2,3 D(4)=1,2,4 D(5)=1,2,4,5,D(6)=1,2,4,6 D(7)=1,2,4,7 2根据结点集找循环 我们求出结点的集合后，根据结点的集合就可以求回边。利用回边，我们就可以找出流图的循环。 假设ab 是流图的一条有向边，如果b DOM a，则称 ab是流图的一条回边。 对于任何已知的流图，只要求出各结点的必经结点集，就可以求出流图中的一条回边。,例8.4有向边66、74、42是回边，因为6 DOM 6，4 DOM 7和2 DOM 4的关系存在，其它的有向边都不是回边。 如果已知有向边ab是回边，那么就可以求出由它组成的循环。该循环就是由结点b、结点a以及有通路到达a而该通路不经过b的所有结点组成，并且b是该循环的唯一的入口结点。 例8.5由回边66组成的循环是6，由回边74组成的回边的循环是4，5，6，7；由回边42组成的循环是2，3，4，5，6，7。,8.3.3循环优化 找出了程序流图中的循环后，可以对循环进行优化。因为循环内的指令是重复执行的，因此循环的优化在整个优化工作中是非常重要的。主要介绍循环优化的三种重要技术：代码外提；删除归纳变量；强度削弱。 1代码外提 减少循环中代码数目的一个重要的办法就是代码外提。这种方法就是把循环不变运算，即产生的结果独立于循环执行次数的表达式，放到循环的前面，这里所讨论的循环只有一个入口。 。,在实施代码外提时，在循环的入口结点前建立一个新的结点（基本块），称为循环的前置结点。循环的前置结点是以循环的入口结点为其惟一的后继结点。原来以循环入口结点为入口的有向边改为以前置结点为入口。如图8-12所示，入口结点是惟一的，所以前置结点也是惟一的。循环中外提的代码统统外提到前置结点中。但是，循环中的不变运算并不是在任何情况下都可以外提；对于循环体L中的不变运算S：A=B op C或A= op B或A=B，要求满足下述条件： （1）S所在的结点是L的所有出口结点的必经结点； （2）A在L中的其他的地方未再定值。 （3）L中所有A的引用点只有S中A的定值才能到达,查找所需要处理的循环L中的不变运算和代码外提的算法如下： （1）依次查看L中各基本块的每个四元式，如果它的每个运算对象为常数或定值点在L之外，则将此四元式标记为“不变运算”。 （2）依次查看尚未被标记为“不变运算”的四元式，如果它的每个运算对象为常数或定值点在L之外，或只有一个到达一定值点且该点上的四元式已标记为“不变运算”，则把被查看的四元式标记为“不变运算”。 （3）重复第（2）步直到没有新的四元式被标记为“不变运算”为止。 找出了循环不变运算就可以进行代码外提了。代码外提的算法如下： （1）求出循环L的所有的不变运算。 （2）对第1步所求得的每一不变运算S：A=B op C或A=op B或A=B，检查它是否满足以下的条件：,1）S所在的结点是L的所有出口结点和必经结点。 2）A在L的其他地方未再定值。 3）L中所有A的引用点只有S中A的定值才能到达。 4）A在离开L后不再是活跃的，并且条件（2）和（3）两条成立。所谓A在离开L后不再是活跃的是指A在L的任何出口结点的后继结点的入口处不是活跃的。 5）按第1步所找到的不变运算的顺序，依次把第2步中满足条件的不变运算S外提到L的前置结点中。,2强度削弱和删除归纳变量 前面已经介绍了强度削弱的概念，强度削弱在某些情况下进行的优化是非常有效的。例如在计算下标变量的地址时非常有效。在循环优化中，强度削弱占据很重要的位置。 下面介绍基本归纳变量和归纳变量的优化。如果循环中对变量I只有惟一的形如I=I+C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。如果I是循环中一基本归纳变量，J在循环中的定值总是可以划归为I的同一线性函数，也即J=C1*I+ C2，其中C1 和C2都是循环不变量，则称J为归纳变量，并称它与I同族。一个基本归纳变量也是一个归纳变量。,一个归纳变量除用于自身的递归定值外，往往只在循环中用来计算其它归纳变量以及用来控制循环的进行。这时，我们就可以用与循环控制条件中的基本归纳变量同族的某一归纳变量来替换。进行这些变换后就可以将基本归纳变量的递归定值作为无用赋值来删除。,删除归纳变量是在强度削弱之后进行的。下面我们给出强度削弱和删除归纳变量的算法。 （1）利用循环不变运算信息，找出循环中的所有的基本归纳变量。 （2）找出所有其他归纳变量A，并找出A与已知基本归纳变量X的同族线性函数关系FA(x) 。 （3）对于（2）中找出的每一个归纳变量A进行强度削弱。 （4）删除对归纳变量的无用赋值。 （5）删除基本归纳变量。如果基本归纳变量B在循环出口之后不是活跃的，并且在循环中，除在其自身的递归赋值中被引用外，只在形如if B rop Y goto Z 中被引用，则选取一个与B同族的归纳变量M来替换B进行条件控制并删除循环中对B递归赋值的四元式。 例题8.6对于图8-13（a）所给定的程序流程图进行强度削弱优化。 【解】将图8-13(a)的图进行强度削弱后，为图8-13(b)所示。,8.3.4窥孔优化 即使对中间代码进行了优化，所产生的目标代码仍然会存在一些指令和可再优化的结构。这是因为，编译程序的目标代码生成部分只能按照一般情况来生成目标代码。 窥孔优化是对目标代码进行局部改进的简单而有效的技术，它只考虑目标代码中很短的指令序列，只要有可能，就代之以更短或更快
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号