第7章：代码优化

第7章代码优化词法分析器语法分析器中间代码生成器优化段源程序单词符号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码

7.1

优化概述优化是一种等价的、有效的程序变换。优化的目的是为了产生更高效的代码。由优化的编译程序提供的对代码的各种变换必须遵循下面的原则：等价原则：是指经过优化后不应改变源程序运行的结果。有效原则：经优化后所产生的目标代码运行时间较短，占用存储空间较小。合算原则：应尽可能以较低的代价取得较好的优化效果。编译前端代码优化器编译后端控制流分析数据流分析代码变换优化技术分类代码优化实际上是对代码进行等价变换，由一组代码变成运行结果相同的另一组代码。源程序一级的优化：对中间代码的优化，与机器无关,面向各种语言.主要包括：局部优化、循环优化、全局优化目标代码的优化：与具体机器有关.主要包括对寄存器的优化，多处理机的优化、特殊指令的优化等优化技术分类局部优化:程序中顺序执行的语句序列循环优化:程序中循环语句的优化全局优化:整个程序范围内的优化优化的种类：删除多余运算(或称删除公用子表达式)代码外提强度消弱变换循环控制条件合并已知量复写传播删除无用赋值中间代码优化举例设Ａ、Ｂ为两个一维数组，他们的初始地址分别为addr(A),addr(B),源程序段是S=0FOR(i=1,i<=20;i++)S=S+A[i]+B[i]假设机器按字节编制根据程序流向的特点,分为B1,B2两块.B1是循环体外的语句,B2是可重复执行的循环语句序列原则:通过等价变换,将尽量减少循环体中的语句,同时尽可能减少无实际意义的重复计算与赋值,尽可能降低机器运算强度,运算的级别.１．删除公共子表达式(删除多余运算)公共子表达式是指在一个基本程序块内计算结果相同的子表达式．２．代码外提是指把循环不变的运算提到循环体前面优化前的中间代码经删除公共子表达式和代码外提后的中间代码3.降低运算强度

主要指不改变运算结果的前提下,将程序执行时间长的运算替换成执行时间短的运算降低运算级别经强度削弱后的中间代码4.变换循环控制变量(删除归纳变量)如果在循环体内存在一个变量(或临时变量)T与循环控制变量i保持线性关系,同时在循环后面不引用I,而除去i又不影响程序运行结果,则可由T取代循环控制变量变量I,这种方法称为变换循环控制变量(删除归纳变量)5.合并已知量合并已知量是指若参加运算的两个对象在编译时都是已知量,则可以在编译时直接计算出它们的运算结果6.复写传播是指尽量不引用那些在程序中仅仅只传递信息而不改变其值,也不影响其运行结果的变量.经变换循环控制变量,合并已知量,复写传播后的中间代码7,删除无用赋值减少无用的变量,使代码更简洁假(1)S=0(4)T2=addr(A)-4(7)T5=addr(B)-4(3)T1=4(5)T3=T2[T1](8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7(3’)T1=T1+4(12)ifT1≤80goto(5)B2B1真经删除无用赋值后的中间代码经过优化后,代码具有以下特点:(1)减少了循环体内可执行代码:10条→6条(2)减少了乘法运算次数:3次→1次(3)减少了全程范围内使用的变量:i,T47.2 局部优化合并已知量：运算对象是已知量，编译时直接计算它们的值，而不必等到程序运行时再计算。删除公共子表达式：如果一个表达式E的值，前面已经算过，并且在这之后E的值没有改变，则E称为公共子表达式，则可以避免它的重复运算，称为删除公共子表达式。（删除多余运算）删除无用赋值：如果一些变量的值在整个程序中不再被使用，则这些变量的赋值对程序的运算结果没有任何作用，则可以删除对这些变量赋值的代码，称为删除无用赋值。

局部优化基本块：一个基本块是指程序中一顺序执行的语句序列。其中只有一个入口和一个出口，入口就是其中第一个语句，出口就是最后一条语句。对于一个基本块来说，执行时只能从其入口进入，从出口退出。局限于基本块范围内的优化称为基本块内的优化，或称局部优化。划分四元式程序为基本块的算法:1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。入口语句n……入口语句m入口语句n……转移语句m入口语句n……停语句m3.凡未被纳入某一基本块中的语句，都是程序不可到达的语句,可以从程序中删除。例：划分基本块(1) readX(2) readY(3) C:=XmodY(4) ifC=0goto(8)(5) X:=Y(6) Y:=C(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各个基本块的入口语句:1)程序第一个语句，或2)能由条件转移语句或无条件转移语句转移到的语句，或3)紧跟在条件转移语句后面的语句。例：划分基本块(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt2.对以上求出的每个入口语句，确定其所属的基本块。它是由该入口语句到下一入口语句(不包括该入口语句)、或到一转移语句(包括该转移语句)、或一停语句(包括该停语句)之间的语句序列组成的。

程序流图:(8)writeY(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=XmodY(4)ifR=0goto(8)(1)readX(2)readYB1B2B3B4程序流图以基本块作为结点，控制程序流向作为有向弧，画出的图，称为程序流图。流图G=（N，E，n0）N：表示流图的有限结点集合，每一个结点对应一个基本块。E：流图的有向边集合；n0：表示唯一的首结点，包含程序第一个语句的基本块。程序流图每个流图以基本块为结点。如果一个结点的基本块的入口语句是程序的第一条语句，则称此结点为首结点。如果在某个执行顺序中，基本块B2紧接在基本块B1之后执行，则从B1到B2有一条有向边。即，如果有一个条件或无条件转移语句从B1的最后一条语句转移到B2的第一条语句；或者在程序的序列中，B2紧接在B1的后面，并且B1的最后一条语句不是一个无条件转移语句。我们就说B1是B2的前驱，B2是B1的后继。(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt(8)writeY(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=XmodY(4)ifR=0goto(8)(1)readX(2)readYB1B2B3B4对下面的程序段划分基本块,构造程序的控制流图→(1)readc*/1(2)a:=0←(3)b:=1→(4)a:=a+b*/2←(5)ifb≥c

goto(10)→(6)b:=b+1*/3←(7)goto(4)(8)a:=a+1(9)b:=a+2→(10)writea*/4←(1)halt

基本块划分块号bfirstbLastb

sucbpredb1(1)(3)2_2(4)(5)3、41、33(6)(7)224(10)(11)_2(1)readc1(2)a:=0(3)b:=1L1:(4)a:=a+b

2(5)ifb≥c

gotoL2(6)b:=b+13(7)gotoL1L2:(10)writeA4(11)halt

程序流图:基本块的DAG图DAG(DirectedAcyclicGraph)是一种有向图,常常用来对基本块进行优化。基本块中的语句的计算过程可以用一张图表示出来，即一个基本块可用一个DAG图表示。

图表示法图表示法DAG抽象语法树无循环有向图(DirectedAcyclicGraph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点

a:=b*(-c)+b*(-c)的图表示法

assigna+*buminuscDAGassigna+*buminusc抽象语法树*buminusc抽象语法树对应的代码：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象语法树*buminuscDAG对应的代码：

T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象语法树对应的代码：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5描述计算过程的DAG是一种带有下述标记或附加信息的DAG:n13.14n3n4Rrn5+T2,T4图的叶结点以一标识符或常数作为标记，表示该结点代表该变量或常数的值;图的内部结点以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果;图中各个结点上可能附加一个或多个标识符(称附加标识符)表示这些变量具有该结点所代表的值。借助DAG进行优化利用DAG来进行优化的主要思想：将一基本块中的每一个四元式依次表示成对应的一个DAG，再按原来构造DAG结点的顺序重写四元式序列，便可得到“合并已知常量”、“删除无用赋值”、“删除多余运算”后的等价基本块——优化了的基本块。

基本块的DAG表示及应用一个基本块，可用一个DAG来表示与各四元式相对应的DAG结点形式:四元式 DAG图(0)0型:A:=B(:=，B，-，A)

n1AB四元式 DAG图(1)1型:A:=opB(op，B，-，A)n1ABn2op(2)2型:A:=BopC(op，B，C，A)n2ABn1opn3C四元式 DAG图(3)2型:A:=B[C]

(=[]，B[C]，-，A)n2ABn1=[]n3C(4)2型:ifBropCgoto(s)(jrop，B，C，(s))n2(s)Bn1ropn3C四元式 DAG图(5)3型:D[C]:=B

([]=，B，-，D[C])(6)0型:goto(s)(j，-，-，(s))(s)n1n2Bn1[]=n4Cn3D例：赋值语句T4:=A+B-（E-（C+D））四元式序列G

T1:=A+B

T2:=C+D

T3:=E-T2

T4:=T1-T3

ABE

CDn9n3n8n1n2n7n6n4n5

T4

T1

T3

T2

+

-

-

+

DAG:例7.3 试构造以下基本块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(1)T0:=3.14(1)T0:=3.14(2)T1:=2*T0(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(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(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(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(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(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*B(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*T6T6优化