编译原理代码优化

第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=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.消减运算强度（循环优化之二）即把强度大的运算换算成强度小的运算。

如：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．确定基本块的入口语句，它们是：(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=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)(=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))：

方法：①确认一个变量两个赋值点间无引用点；②前一赋值点为无用赋值；※

基本块内四元式的局部优化过程示例8.2.3基于DAG的局部优化方法Ⅰ.

四元式序列的DAG表示

DAG(DirectedAcyclicGraph)是指无环有向图；这里用来对基本块内的四元式序列进行优化。1.DAG的结点内容及其表示：DAGn1n2n3n4n5ni:结点的编码;:运算符;M:主标记（运算结果变量，叶结点时，是变量或常数的初值）;Ai:附加标记（运算结果变量，表示它具有该节点所代表的值，可设置多个）i=1,2,3,…。前驱后继M|A1,A2,A3,…ni2.单个四元式的DAG表示：niB|A双目运算(BCA)或A=BCn3An1n2BCn2An1B转向(

[B]_A)n2An1BniAn3An1n2[]BCA=B[C]B[C]=Dn3Dn1n2BCn4可选数组变量赋值运算赋值(=B_A)或A=B或A=B单目运算(B_A)8.2.3基于DAG的局部优化方法

(2)若常值表达式A=C1C2或A=C1;

(1)若赋值四元式A=B1.构造基本块内优化的DAG:【假设】(1)ni

为已有结点号；n为新结点号；①DAG置空；依次读取一四元式A=BC；

②分别定义B,C结点(若已定义过，则免)；①

计算常值C=C1C2

;

②若C在n1已定义过，则:n1C|…

③若A在n2已定义过，则：

否则申请新结点，且：

②若A在n2已定义过，则:n2…|…A…①

把A

附加于B上：n1…B…【开始】,A,AAnC|

(2)访问各结点信息时，按结点号逆序进行；n2…|…A…Ⅱ.基于DAG的局部优化算法删除无用赋值常值表达式节省(3)若其它表达式A=BC

或A=B;①

若在n1存在公共表达式:BCn1…ni…B…n1…ninj…B……C…

n1…②若不存在公共表达式，则申请新结点n:ninj…B……C…③若A在n2已定义过，则删除之：,AnA或B则把A附加于n1上：或ni…B…nA

n2…|…A…8.2.3基于DAG的局部优化方法删除公共表达式q1:Ai=B(i=1,2,…)(1)若n1

为带有附加标记的叶结点：n1B|A1,A2,…

若Ai为非临时变量，则生成：n1A|A1,A2,…

ninjB|…C|…

①

生成q1:A=BC或生成q1:A=B

q2:Ai=A

(i=1,2,…)

②若Ai为非临时变量，则生成：(2)若n1

为带有附加标记的非叶结点：2.根据基本块内优化的DAG，重组四元式：【开始】按结点编码顺序，依次读取每一结点n1

信息：【假设】(1)临时变量的作用域是基本块内；(2)非临时变量的作用域可以是基本块外。以主标记参加运算8.2.3基于DAG的局部优化方法(1)t2=R+r(3)t7=R-r(1)B=5(2)t1=2*3.14(3)t2=R+r(4)t3=t1*t2(5)A=t3(6)t4=2*3.14(7)t5=R+r(8)t6=t4*t5(9)t7=R-r(10)t8=t6/t7(11)B=t8【例8.3】对下述语句片断进行基于DAG的优化：B=5;A=2*3.14*(R+r);B=2*3.14*(R+r)/(R-r);1.

根据四元式序列构造优化的DAG:15|B3R26.28|t14r5+t27-t7|t5,t4|A|B/t882.根据优化的DAG重组四元式:*t3A|t36,t6B|t8(2)A=6.28*t2(4)B=A/t7为什么要位置交换？8.2.3基于DAG的局部优化方法基于DAG的局部优化练习对以下基本块

T1=2

T2=A-B

T3