编译原理第7章代码优化.ppt

1、第七章代码优化,某些编译程序在中间代码或目标代码生成之后要对生成的代码进行优化。,本章主要介绍：,优化基本概念,基本块内的局部优化,基于循环的优化,7.1优化概述,什么是代码优化:,对程序实施各种等价变换,使得变换后程序能生成高效率的目标代码。,高效率的目标代码是指:目标代码占用的存储空间少,目标代码运行时间短,7.1优化概述,1.等价原则:保证等价性。,2.有效原则:有明显的效果。,3.合算原则:较低的代价取得较好的优化效果。,代码优化的原则,7.1优化概述,代码优化的种类：,根据是否涉及具体的计算机分为:,与机器有关的优化,(优化工作主要在目标代码级上进行),对寄存器的优化,多处理机的优化

2、,特殊指令的优化等,7.1优化概述,与机器无关的优化,(优化工作主要在中间代码级上进行),根据优化对象所涉及的程序范围分为:,局部优化,循环优化,全局优化,7.1优化概述,局部优化,是指局限于程序基本块范围内的一种优化。,局部优化包括:,合并已知量,删除公共子表达式(删除多余的运算),删除无用赋值,7.1优化概述,循环优化,是指对循环中的代码进行优化。,循环优化包括:,代码外提,删除归纳变量,强度削弱,7.1优化概述,是在整个程序范围内进行的优化,需进行数据流分析,花费代价很高。,全局优化,7.1优化概述,S=0；for(i=1;i=20;i+)S=S+Ai*Bi；,优化处理,例如设有一个计算

3、两个向量内积的源程序段:,7.1优化概述,编译程序对其进行词法分析、语法分析、语义分析和中间代码的生成,得到如下一组三地址语句序列表示的中间代码：,说明:,=+I1=addr(A)1+I,addr(A)1T2地址计算的不变部分,IT1地址计算的可变部分,用T2T1表示数组元素的地址,若一个机器字有四个字节,按字节编址:,T1=4*IT2=addr(A)4*1,B1,B2,7.1优化概述,在上图所示的中间代码中，根据程序流向的特点，分为B1、B2两块:,B1是循环体外的语句序列,B2是可重复执行的循环体语句序列,7.1优化概述,1.删除公共子表达(删除多余运算),公共子表达式是指在一个基本块内计

4、算结果相同的子表达式。,对相同的子表达式只在第一次出现时计算且仅计算一次，将重复计算的表达式删除。,图B2中公共子表达式4*I出现在四元式(3)和(6)中，而从(3)到(6)之间没有对子表达式中的变量I重新赋值，因此T1=T4，第二个4*I是多余的运算，可以删去，将原四元式改为:(6)T4=T1。,7.1优化概述,7.1优化概述,2.代码外提,代码外提是指将循环中的不变运算提到循环体前面。,图B2中，四元式,(4)T2=addr(A)4(7)T5=addr(B)4,7.1优化概述,由于addr(A)，addr(B)已知，T2，T5的值不随循环的执行而变化，因此将四元式(4)，(7)提到B2前面

5、，得到下图:,7.1优化概述,3.强度削弱,强度削弱是指在不改变运算结果的前提下，将程序中执行时间长的运算替换成执行时间短的运算。,对计算机上的二进制算术运算，作加法一般比作乘法的速度快。,7.1优化概述,图中四元式(3)T1=4*I中，I是循环控制变量，每循环一次，I增加一个步长值即I值加1,而T1的值增加4,将(3)T1=4*I提到循环外,循环体内改为(3)T1=T1+4,得到下图。,7.1优化概述,7.1优化概述,4.变换循环控制条件(删除归纳变量),在B2中存在变量T与循环控制变量I保持线性关系，则可由T取代I,因此对三地址语句(12)中的循环控制条件,7.1优化概述,称这种变换为变换

6、循环控制条件,或称为删除归纳变量。,变换循环控制条件后，三地址语句(11)I=I+1可删除。,因为变量I是引用I值来计算I值,称为对I递归赋值,I称为循环中的归纳变量。,7.1优化概述,5.合并已知量,已知量是指常数或在编译时就能确定其值的变量。,合并已知量是指若参加运算的两个对象在编译时都是已知量，则可以在编译时直接计算出它们的运算结果，不必生成目标。,7.1优化概述,图B1中，四元式(2)I=1，其后的两个四元式中没有改变I值，这时四元式(3)T1=4*I中参加运算的两个运算量均为已知,因此将(3)变换为：T1=4，得到下图：,7.1优化概述,6.复写传播,复写传播是指尽量不引用那些在程序

7、中仅仅只传递信息而不改变其值，也不影响其运行结果的变量。,图中,T4就是这样一种变量。,7.1优化概述,四元式(6)T4=T1，下一个四元式(8)T6=T5T4，这之间T4的值没有变化，因此将(8)变换为:T6=T5T1。,这时T4成为无用的赋值。,7.1优化概述,7.删除无用赋值,对赋值语句X=Y，若在程序的任何地方都不引用X，这时该语句执行与否对程序运行结果没有任何作用，这种语句称为无用赋值语句，可以删除。,7.1优化概述,(1)S=0(4)T2=addr(A)4(7)T5=addr(B)4(3)T1=4,(5)T3=T2T1(8)T6=T5T1(9)T7=T3*T6(10)S=S+T7(

8、3)T1=T1+4(12)ifT180goto(5),B1,B2,7.1优化概述,比较优化前后的代码序列可以发现经过优化后最终得到的代码序列具有以下特点:,减少了循环体内可执行代码，由10条减至6条。,减少了作乘法运算的次数，由3次降为1次。,减少了全程范围内使用的变量，如I，T4等变量。,7.1优化概述,由此可知，经过一系列优化后的代码其执行效率明显提高。当然优化工作越多，编译系统的代价就会越大。因此，对某种程序设计语言翻译要实施什么优化，就要视语言的特点具体分析，力争设计一个最适应本语言特点的优化策略。,7.2局部优化,局部优化是指局限于程序基本块范围内的一种优化。,基本块,所谓基本块是指

9、程序中一组顺序执行的语句序列,其中只有一个入口语句和一个出口语句。,7.2.1划分基本块的方法,1.从四元式序列确定基本块的入口语句：,(1)四元式序列的第一个语句,(2)由条件转移语句或无条件转移语句转移到的语句,(3)紧跟在条件转移语句后面的语句。,2.确定基本块的出口语句：,(1)下一个入口语句的前导语句,(2)转移语句(包括转移语句本身),(3)停语句(包括停语句本身),入口语句和出口语句之间组成一个基本块。,3.删去那些不属于任何基本块的语句，因为控制流无法到达这些语句。,7.2.1划分基本块的方法,例给以下四元式序列划分基本块。,（1）readC（2）A=0（3）B=1（4）L1:

10、A=A+b（5）ifBCgotoL2（6）B=B+1（7）gotoL1（8）L2:writeA（9）halt,7.2.1划分基本块的方法,根据划分基本块的算法可以确定四元式(1)(4)(6)(8)是入口语句;(3)(5)(7)(9)是出口语句，因此分为四个基本块,7.2.2基本块的DAG表示,利用DAG实现局部优化的思想：,首先对一个基本块构造一个DAG，然后按构造结点的次序将DAG还原成四元式序列。,DAG(无环路有向图),7.2.2基本块的DAG表示,结点带有标记的DAG：,OP,7.2.2基本块的DAG表示,基本块的DAG表式：,(1)A=B,(2)A=opB,(3)A=BopC,(4)

11、A=BC,四元式与DAG,7.2.2基本块的DAG表示,(5)ifBropCgoto(S),(6)DC=B,(7)Goto(S),四元式与DAG,7.2.2基本块的DAG表示,例构造以下基本块的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,7.2.3利用DAG实现局部优化,对四元式(4)A=T1*T2有：,(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)T

12、5=T3*T4(9)T6=R-r(10)B=T5*T6,7.2.3基本块上的优化处理,对四元式(5)B=A有：,(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,B,7.2.3基本块上的优化处理,对四元式(6)T3=2*T0有：,(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,T3,7.2.3基本块上的优化处理,

13、对四元式(7)T4=R+r有：,(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,T4,7.2.3基本块上的优化处理,对四元式(8)T5=T3*T4有：,(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,T5,7.2.3基本块上的优化处理,对四元式(9)T6=R-r中,(1)T0=3.14(2)T1=2*T0(3)

14、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,7.2.3基本块上的优化处理,对四元式(10)B=T5*T6,(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,7.2.3基本块上的优化处理,按照构造DAG结点的顺序，对每一个结点写出其相应的四元式表示。,(1)T0=3.14(2)T1=6.28(3)T3=6.28(4)T2=R+r(5)T4=T2(6)A=6

15、.28*T2(7)T5=A(8)T6=R-r(9)B=A*T6,7.2.3基本块上的优化处理,(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)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,7.2.3基本块上的优化处理,设优化后的上述一组四元式序列为G，G较之优化前的一组四元式G，不但代码总数减少，而且对G中四元式(2)T1=2*T

16、0和(6)T3=2*T0，在G中已被优化为T1=6.28，T3=6.28，这是合并已知量的结果；对G中四元式(5)B=A，直至在下一个B被赋值时都没有被引用，,7.2.3基本块上的优化处理,显然是无用赋值，G中已被删除；对G中具有公共子表达式的四元式(3)T2=R+r，(7)T4=R+r，G中被优化为直接赋值T4=T2，避免了对公共子表达式R+r的重复计算。综上所述，利用DAG可以很方便地进行基本块内的优化处理。,7.2.3基本块上的优化处理,7.3循环优化,对循环语句,因为循环需要反复执行，所以对循环实施优化无疑会显著提高目标代码的执行效率。,循环优化包括：,代码外提,强度削弱,删除归纳变量

17、,7.3.1程序流图与循环,一个程序的控制流程图（简称为程序流图或流图）G是一个三元组G=(N，n0，E)。其中：,控制流程图,N表示流图的有限结点集，流图中每一个结点对应程序中的一个基本块，因此，N实质上就是一个程序的基本块集。,n0表示唯一的首结点，流图的首结点是包含程序第一个语句的基本块。,E表示流图的有向边集。,7.3.1程序流图与循环,7.3.2循环查找,为了找出流图中的循环，需分析流图中结点间的控制关系。因此引入必经结点和必经结点集的概念。,7.3.2循环查找,必经结点,在程序流图中，对任意两个结点a和b，若从流图的首结点出发，到达a的任一通路都要经过b，则称b是a的必经结点，记为

18、bDOMa。,必经结点集,流图中结点a的所有必经结点的集合称为结点a的必经结点集，记为D(a),7.3.2循环查找,求流图中所有结点n的必经结点集D(n)的算法思想：,结点nn的所有前驱结点的必经结点的交，即如果某结点d是结点n的所有前驱结点的必经结点，则d为n的必经结点。,7.3.2循环查找,D(B8)=B1,B2,B7,B8,流图中各结点的必经结点集：,例,D(B1)=B1,D(B2)=B1,B2,D(B3)=B1,B2,B3,D(B4)=B1,B2,B3,B4,D(B5)=B1,B2,B3,B5,D(B6)=B1,B2,B3,B6,D(B7)=B1,B2,B7,求流图中的回边,设ab是流

19、图中的一条有向边，若bDOMa，则称ab是流图中的一条回边。,7.3.2循环查找,流图中的回边：,因为B2DOMB7，所以B7B2是流图中的回边，且是流图中的唯一回边。,7.3.2循环查找,求循环的算法思想：,回边n到d组成的循环:d是循环的入口，n是循环的出口，循环出口n的前驱属于循环，前驱不是d，再求前驱,直到入口d为止。,7.3.2循环查找,流图中的循环：,由回边B7B2组成的循环是B2,B3,B4,B5,B6,B7,7.3.2循环查找,本章小结,1.掌握优化的基本概念,(1)什么是代码优化,(2)什么是局部优化、循环优化,本章小结,局部优化,是指局限于程序基本块范围内的一种优化。,局部优化包括:,合并已知量,删除公共子表达式(删除多余的运算),删除无用赋值,本章小结,循环优化,是指对循环中的代码进行优化。,循环优化包括:,代码外提,删除归纳变量,强度削弱,本章小结,(1)划