第五章 代码优化

第五章

代码优化5.1局部优化5.2循环优化优化的概念代码优化对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。空间效率和时间效率有时是一对矛盾，有时不能兼顾。优化要求必须是等价变换(保持功能)为优化的努力必须是值得的机器相关性机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。机器无关优化：对中间代码的优化。优化范围局部优化：单个基本块范围内的优化，包括常量合并、公共子表达式删除、计算强度削弱和无用代码删除等。全局优化：主要是基于循环的优化，包括循环不变量代码外提、删除归纳变量、计算强度削弱等。优化语言级优化语言级：针对中间代码，针对机器语言。代码优化的分类控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。到达-定义分析；活跃变量分析；可用表达式分析；代码变换：根据上面的分析，对内部中间代码进行等价变换。控制流分析数据流分析代码变换代码优化主要完成的工作5.1局部优化指基本块内的优化。基本块：是指程序（本课本中假设已经是四元式表示的程序了）中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。5.1.1基本块的划分入口语句（1）四元式语句序列的第一个语句；（2）条件转移语句或无条件转移语句转移到的目标语句；（3）紧跟在条件转移语句后面的语句。出口语句（1）下一个入口语句的前导语句；（2）转移语句（包括其自身）；（3）停语句（包括其自身）。基本块的划分1、求出四元式程序之中各个基本块的入口语句。2、对每一入口语句，构造其所属的基本块。即由该入口语句到出口语句之间的语句序列。3、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。(1)read(C)(2)A=0(3)B=1(4)L1:A=A+B(5)ifB>=CgotoL2(6)B=B+1(7)gotoL1(8)L2:write(A)(9)halt为其划分基本块。【例】有四元式代码程序如下：5.1.2基本块的DAG表示DAG

指有向无环图（DirectedAcyclicGraph

），常用来对基本块进行优化。基本块的DAG是在结点上带有标记的DAG。

叶结点代表名字的初值，以唯一的标识符（变量名字或常数）标记。通常用x0表示变量名字x的初值。

内部结点用运算符作为标记。

所有结点都可有一个或多个附加标识符，表示这些变量具有该结点所代表的值。

（其他四元式的

DAG

结点形式参见教材P131图5-1）DAG

结点

ABAopBop

n1n2BCn1n2n1n3n1n2四元式A=BA=opBA=BopCA运算符标记四元式和与其对应的DAG结点形式

基本块DAG表示的构造算法设A=B,A=opB,A=BopC分别为第0、1、2型四元式，设函数Node(name)返回最近创建的关联于name的结点。首先，置DAG为空。

对基本块的每一个四元式，依次执行下列步骤：

若Node(B)无定义，则创建一个标记为B的叶结点，并令Node(B)为这个结点；

(1)对于2型四元式，若Node(C)无定义，再创建标记为C的叶结点，并令Node(C)为这个结点。若Node(B)和Node(C)都是标记为常数的叶结点，执行BopC，令得到的新常数为p。若Node(p)无定义，则构造一个用p做标记的叶结点n,置Node(p)=n。

若Node(B)或Node(C)是处理当前语句时新构造出来的结点，则删除它。（这一步有合并已知量的作用）若Node(B)

或Node(C)不是标记为常数的叶结点，则检查是否存在某个标记为op的结点，其左孩子是Node(B)

，而右孩子是Node(C)

？若无，则创建这样的结点。若有，则把已有的结点作为它的结点并且无论有无，都令该结点为n。（这一步有删除多余运算的作用）(2)对于1型四元式若Node(B)

是标记为常数的叶结点，则执行opB，令得到的新常数为p.若Node(p)无定义，则构造一个用p

做标记的叶结点n，置node(p)=n。若Node(B)

是处理当前语句时新构造出来的结点，则删除它。（这一步有合并已知量的作用）若Node(B)

不是标记为常数的叶结点，则检查是否存在某个标记为op的结点，其唯一的孩子是Node(B)？若无，则创建这样的结点;若有，则把已有的结点作为它的结点；并且无论有无，都令该结点为n。

（这一步有删除多余运算的作用）若Node(A)无定义，则把A附加在叶结点n上并令Node(A)=n；否则，先从Node(A)的附加标识符集中将A删去（如果Node(A)是叶结点，则不能将A删去），然后再把A附加到新结点n上，并令Node(A)=n。（这一步有删除无用赋值的作用）

基本块DAG表示的构造举例（P132例5.1）T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6

n13.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6

n1

n23.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1R0r0+T2*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B

n6

n5

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,B,T5-T6

n8

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B

从基本块的DAG表示可得到等价的基本块从下图的DAG可得到右边的新的基本块（经拓扑排序及添加适当的复写语句）

n8

n6

n5

n7

n1

n2

n3

n43.14T0T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T66.28T1,T3R0r0+T2,T4*A,T5-T6*B

从基本块的DAG表示可得到等价的基本块

比较变换前后的基本块T0=3.14T1=6.28T3=6.28T2=R+rT4=T2A=6.28*T2T5=AT6=R-rB=A*T6T0=3.14T1=2*T0T2=R+rA=T1*T2B=AT3=2*T0T4=R+rT5=T3*T4T6=R-rB=T5*T6所作的优化合并已知量删除多余运算删除无用赋值利用DAG进行基本块优化的基本思想：首先按基本块内的四元式序列顺序将所有的四元式构造成一个DAG，然后按照构造结点的次序将DAG还原成四元式序列。注意：由于在构造DAG的同时已经做了局部优化，所以最后所得到的就是经过优化过的四元式序列。5.2循环优化循环体是优化的重点控制流图具有惟一首结点的有向图。用来给出循环的定义。给出找出程序中循环的算法。循环的定义具有唯一入口结点的强连通子图。强连通子图任意两结点间的通路上各结点属于子图。循环的查找方法见课本P138第5.2.2小节！5.2.3循环优化代码外提强度削弱删除归纳变量方法1：代码外提将循环不变运算移到循环外。【例】有程序如下，试对其进行优化。i=0;while(i<20){x=4*i;i++;y=z*6+x;}(3)x=4*i(4)i=i+1(5)t1=z*6(6)y=t1+x(7)goto(2)(4)x=4*i(5)i=i+1(6)y=t1+x(7)goto(3)(1)i=0(1)i=0(2)t1=z*6(2)ifi>=20goto(8)(3)ifi>=20goto(8)循环不变运算的定义：P142查找循环中不变运算的算法描述：P144代码外提算法描述：P144方法2：强度削弱把程序中执行时间较长的运算替换为执行时间较短的运算。X:=K*i+Y 相关计算i=i+C 归纳变量（K、C、Y为循环不变量）改为X=X+K*C（设X的初值=Y-K*C）(4)x=4*i(5)i=i+1(6)y=t1+x(7)goto(3)(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(1)i=0(2)t1=z*6(1)i=0(2)t1=z*6(3)x=-4(3)ifi>=20goto(8)(4)ifi>=20goto(9)方法3:消除归纳变量利用归纳变量相关的计算代替归纳变量的计算条件表达式的修改无用语句的删除(5)x=x+4(6)i=i+1(7)y=t1+x(8)goto(4)(4)x=x+4(5)y=t1+x(6)goto(3)(1)i=0(2)t1=z*6(3)x=-4(1)t1=z*6(2)x=-4(4)ifi>=20goto(9)(3)ifx>=76

goto(7)强度削弱和删除归纳变量的算法描述：

P147代码优化示例本节所用的例子i=m1;(1)i=m1j=n;(2)j=nv=a[n];(3)t1=4*n (4)v=a[t1]while(1){ doi=i+1;while(a[i]<v);(5)i=i+1(6)t2=4*i(7)t3=a[t2](8)ift3<vgoto(5)doj=j1;while(a[j]>v);(9)j=j1(10)t4=4*j(11)t5=a[t4] (12)ift5>vgoto(9)if(i>=j)break;(13)ifi>=jgoto(23)x=a[i];(14)t6=4*i(15)x=a[t6]a[i]=a[j];(16)t7=4*i(17)t8=4*j(18)t9=a[t8](19)a[t7]=t9

a[j]=x;(20)t10=4*j(21)a[t10]=x(22)goto(5)}

x=a[i];(23)t11=4*i(24)x=a[t11]a[i]=a[n];(25)t12=4*i(26)t13=4*n(27)t14=a[t13](28)a[t12]=t14a[n]=x; (29)t15=4*n(30)a[t15]=xi=m1j=nt1=4*nv=a[t1]i=i+1t2=4*it3=a[t2]ift3<vgoto

B2B1B2j=j1t4=4*jt5=a[t4]ift5>vgoto

B3ifi>=jgoto

B6B4B3B5B61、删除公共子表达式、复写传播B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*it8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*ix=a[t6]t8=4*jt9=a[t8]a[t6]=t9a[t8]=xgoto

B2B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*it8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*ix=a[t6]t8=4*jt9=a[t8]a[t6]=t9a[t8]=xgoto

B2x=a[t2]t9=a[t4]a[t2]=t9a[t4]=xgoto

B22、删除无用赋值B5x=a[i];a[i]=a[j];a[j]=x;t6=4*ix=a[t6]t7=4*i

t8=4*jt9=a[t8]a[t7]=t9t10=4*ja[t10]=xgoto

B2t6=4*i