第8章 代码优化

《第8章 代码优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章代码优化优化处理是指产生更高效的目标代码所做的工作。8.1优化的分类8.2局部优化8.2.1常见的局部优化方法8.2.2基本块及其划分8.2.3基于DAG的局部优化方法【内容提要】目标代码所占空间和执行速度8.1优化的分类(1)与机器无关的优化(在源代码或中间代码级上进行)；又分三种：①全局优化—针对整个源程序。②局部优化—除全局优化外皆属此类。③循环优化—对循环语句实施的优化。(2)与机器有关的优化(目标代码级上的优化)：包括：①寄存器分配的优化；②消除无用代码。※根据代码优化是否涉及具体的计算机来划分：8.2.1常见的局部优化方法1.常值表达式节省(常数合并)如：a=5+3;b=

2、a+1;…….5+3,a+1皆为常值表达式！则可优化为a=8;b=9;2.公共子表达式节省(删除多余运算)3.删除无用赋值如：a=b+c;x=d-e;y=b;a=e-h/5;则a=b+c为无用赋值！则可优化为x=d-e;y=b;a=e-h/5;a未有应用！！若：a=5+3;…;a=x…;a=a+1;注则a+1不是常值表达式！如：a=b*d+1;e=b*d-2;……b*d是公共表达式!则可优化为t=b*d;a=t+1;e=t-2;若：b=b*d+1;e=b*d-2;则b*d不是公共表达式！注8.2.1常见的局部优化方法(续1)4.不变表达式外提（循环优化之一）即把循环不变运算，提到循环外。5

3、.消减运算强度（循环优化之二）即把强度大的运算换算成强度小的运算。如：i=1;while(i<100){x=(k+a)/i;…;i++;}则可优化为i=1;t=k+a;while(i<100){x=t/i;…;i++;}循环不变表达式如：i=1;while(i<100){t=4*i;b=a↑2;…;i++;}则可优化为i=1;t=0;while(i<100){t=t+4;b=a*a;…;i++;}t,i线性关系8.2.2基本块及其划分※局部优化算法是以基本块为单位进行的，基本块也是目标代码生成的基本单位。【定义】基本块是程序中一段顺序执行的语句序列，其中只有一个入口和一个出口。1．确定基本

4、块的入口语句，它们是：(1)程序的第一个语句或转向语句转移到的语句；(2)紧跟在转向语句后面的语句。2．确定基本块的出口语句，它们是：(1)下一个入口语句的前导语句；(2)转向语句(包括转向语句本身)；(3)停语句(包括停语句本身)；基本块划分算法：【例8.1】设有源程序片段如下，划分出基本块；※以基本块为结点的程序流图，如下所示：对应的四元式序列x=1;a:r=x*5;if(x<10){x=x+1;gotoa;}r=0;(1)x=1(4)r=t1(5)t2=x<10(6)if(t2)_(7)t3=x+1(8)x=t3(9)gta(10)ie_(2)lba(3)t1=x*5(11)r=0x

5、=1(2)lba(3)t1=x*5(4)r=t1(5)t2=x<10(6)if(t2)_(7)t3=x+1(8)x=t3(9)gta(11)r=0(10)ie_B1B2B3B4四个基本块8.2.2基本块及其划分(续1)※基本块内四元式的局部优化过程示例【例8.2】设有语句片断：B=5;A=2*3.14/(R+r);B=2*3.14/(R+r)*(R-r);A=2*3.14/(R+r);B=A*(R-r);(2)(*23.14_t1)(3)(+Rrt2)(4)(/t1t2t3)(5)(=t3_A)(6)(*23.14t4)(7)(+Rrt5)(8)(/t4t5t6)(9)(-Rrt7)(1)

6、(=5_B)(10)(*t6t7t8)(11)(=t8_B)(3)(+Rrt2)(4)(/6.28t2t3)(5)(=t3_A)(9)(-Rrt7)(10)(*t3t7t8)(11)(=t8_B)t1=6.28t4≡t1t5≡t2t6≡t3t1t2优化后(1)(=5_B)B没有引用！…优化的基本内容和方法：常值表达式节省(例8.2中的(2)(6))：方法：①先进行常值计算；②将常值的变量以常值代替；公共子表达式节省(例8.2中的(7)(8))：方法：①找公共表达式，建立结果变量等价关系；②等价变量以老变量代替新变量；删除无用赋值(例8.2中的(1))：方法：①确认一个变量两个赋值点间无引用

7、点；②前一赋值点为无用赋值；※基本块内四元式的局部优化过程示例8.2.3基于DAG的局部优化方法Ⅰ.四元式序列的DAG表示DAG(DirectedAcyclicGraph)是指无环有向图；这里用来对基本块内的四元式序列进行优化。1.DAG的结点内容及其表示：DAGn1n2n3n4n5ni:结点的编码;:运算符;M:主标记（运算结果变量，叶结点时，是变量或常数的初值）;Ai:附加标记（运算结果变量，表示它具有该节点所代表