编译原理PPT课件第六章中间代码优化

局部优化循环优化,优化目的:提高运行速度,减少存储空间.,第六章中间代码优化,内容:,第一节优化概述,2,右面为循环的中间代码:对该段中间代码,可以进行如下优化:1删除多余运算见(3),(6)两四元式的4*I,(6)可以改写为:T4:=T1,从而减少了一次乘法.参见下页四元式表,(1)PROD:=0(2)I:=1,(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*I(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)ifI=20goto(3),3,(1)PROD:=0(2)I:=1,(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=T1(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)ifI代码外提(4)与(7)每次循环其值都不变,称为循环不变量.可以放到循环前,减少循环中的运算.参见下页四元式表,4,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4,(3)T1:=4*I(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(12)ifI强度削弱由于每次循环I都增加1,因此,T1递增4,可把(3)改为T1:=T1+4,放在(11)之后,并在循环前对I赋初值T1:=4*I.(12)改为goto(5).参见下页四元式表,5,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4*I,(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)PROD:=PROD+T7(11)I:=I+1(3)T1:=T1+4(12)ifI变换控制条件由于I只用作循环控制,而T1=4*I,因此,可用T1替换I,I=20等价于T1=80,把(12)改为ifT1复写(6)中T1复制到T4,而(6)到(8)之间没有改变T1和T4,因此(8)可以改为:T6:=T5T1,从而使(6)式无用.参见下页四元式表,7,(1)PROD:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4,(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)PROD:=PROD+T7(3)T1:=T1+4(12)ifT1删除无用赋值(2)和(6)两四元式为无用四元式,可以删除.最终优化后,得到下页四元式表,8,(1)PROD:=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)PROD:=PROD+T7(3)T1:=T1+4(12)ifT1基本块的划分给定一四元式程序,可以通过如下算法,划分基本块:,10,基本块划分算法:1)求四元式程序中所有基本入口四元式,包括:a)程序的第一条四元式;b)转移语句转移到的四元式;c)条件语句之后的第一条四元式.2)对每一入口四元式,构造一个基本块:从该入口四元式到下一入口四元式之前的一条四元式,或到一转移语句,或到一停止语句之间的四元式序列组成.3)凡未纳入这些基本块的四元式,为无用四元式,可以删除.,11,示例:设四元式程序如下:(1)read(X)(2)read(Y)(3)R:=XMODY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write(Y)(9)halt,基本入口四元式包括:(1)程序第一条四元式(3)转移语句转移到的四元式(5)条件语句之后的第一条四元式(8)转移语句转移到的四元式由此可以得到四个基本块.(见下页),12,(8)write(Y)(9)halt,(1)read(X)(2)read(Y),(3)R:=XMODY(4)ifR=0goto(8),(5)X:=Y(6)Y:=R(7)goto(3),B1,B2,B3,B4,13,二基本块内的优化基本块内可以进行以下几种优化:合并已知量,删除多余运算(公共子表达式)删除无用赋值优化手段:DAG1DAG的定义DAG是有向无环路图的简称,结点的基本形式如右图:ni为结点名,val为结点值标记,op为结点的运算.,ni,ni1,ni2,op,val,14,2四元式的DAG表示考虑下面三种类型的四元式,DAG表示如右所示0型:(:=,B,A)1型:(op,B,A)2型:(op,B,C,A),ni,B,A,ni,nk,A,B,op,A,ni,ni1,ni2,B,C,op,15,3基本块的DAG构造算法及优化令NODE(A)=若DAG中存在值标记为A的结点n,则返回n;否则返回null.基本块的DAG构造算法如下:(1)令DAG=null(2)for基本块的每一四元式do若NODE(A)未被引用,或有多个值标记,则删除值标记A;/(删除无用赋值)根据四元式类型,分别转到T0,T1,T2处T0:/(:=,B,A)若NODE(B)=null生成值标记为B的叶结点n否则令n=NODE(B);把A添加在n结点的右侧;返回(2),16,T1:/(op,B,A)若B为已知量/合并已知量执行opB,得到一新常数p,若NODE(p)=null生成值标记为p的叶结点n否则令n=NODE(p);把A添加在n结点的右侧;返回(2)否则若DAG中存在型如右式的子图则把A添加在n结点的右侧;返回(2)/合并多余运算否则若NODE(B)=null生成值标记为B的叶结点n1否则令n1=NODE(B);建立一运算为op,值标记为A的结点n,从n连一边到n1,返回(2),17,T2:/(op,B,C,A)若B,C为已知量/合并已知量执行opB,得到一新常数p,若NODE(p)=null生成值标记为p的叶结点n否则令n=NODE(p);把A添加在n结点的右侧;返回(2)否则若DAG中存在型如右式的子图则把A添加在n结点的右侧;返回(2)/合并多余运算否则若NODE(B)=null生成值标记为B的叶结点n1否则令n1=NODE(B);若NODE(C)=null生成值标记为C的叶结点n2否则令n2=NODE(C);建立一运算为op,值标记为A的结点n,从n分别连边到n1,n2,返回(2),18,4示例:设基本块如下:(1)A:=x+y(2)T0:=3.14(3)T1:=2*T0(4)T2:=R+r(5)A:=T1*T2(6)B:=A(7)T3:=2*T0(8)T4:=R+r(9)T5:=T3*T4(10)T6:=R-r(11)B:=T5*T6,19,DAG如下,3,1,2,x,y,+,A,4,3.14,T0,5,6.28,T1,T3,6,R,7,r,8,T2,T4,10,T6,9,A,B,T5,11,B,+,-,*,*,20,生成DAG后,实质上已经进行了局部优化,再把DAG还原得到如下四元式:(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,21,第三节循环优化,循环是由循环语句,if及goto语句构成.为了找出中间代码程序中的所有循环,就要对程序的流程进行分析,流程是以基本块为单位的,因为基本块内无循环.一控制流程图与循环的定义1控制流程图的定义:控制流程图是具有唯一首结点的有向图,简称为流图.可表示为三元式:G=(N,E,n0)N为结点集,每一结点为一基本块;E为有向边,代表流向;n0为首结点,它包含了程序的第一条语句.,22,2流图的构造方法(1)若基本块j在程序中的位置紧跟在基本块i之后,且i的出口语句非goto(s),则:(2)若基本块i的出口语句为goto(s),或if.goto(s),而(s)是基本块j的入口语句,则:示例:,i,j,i,j,23,设四元式程序如下:(1)read(X)(2)read(Y)(3)R:=XMODY(4)ifR=0goto(8)(5)X:=Y(6)Y:=R(7)goto(3)(8)write(Y)(9)halt,(8)write(Y)(9)halt,(1)read(X)(2)read(Y),(3)R:=XMODY(4)ifR=0goto(8),(5)X:=Y(6)Y:=R(7)goto(3),B1,B2,B3,B4,流图,24,3循环的定义流图中,满足下面两条性质的结点序列称为一个循环:(1)结点序列为强连通的;(任意两点间都有通路,且通路上的结点都属于结点序列)(2)结点序列中仅有一个入口结点.,示例:右面为一流图结点序列6,4,5,6,7,2,3,4,5,6,7是满足以上定义的循环;但结点序列2,4,2,3,4,4,5,7,4,6,7不是上述意义下的循环.,1,2,4,3,6,5,7,25,二查找循环为了建立循环的查找算法,首先介绍几个基本概念:必经结点集,回边,可归约流图1必经结点集定义:若从流图首结点出发到达nj的通路都必须经过ni,则称ni为nj的必经结点,记为niDOMnj;流图中结点n的所有必经结点,称为n的必经结点集,记为D(n).,26,1,2,4,3,6,5,7,例如:右图各结点的必经结点集为:D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,27,设p1,p2.pk是n的所有前趋结点,根据定义,若所有pi(1ik)均有dDOMpi,则dDOMn,即D(n)=nD(p1)D(p2).D(pk)求D(n)的算法(1)令D(n0)=n0;D(i)=N(in0);(2)对每一个ni(in0),temp=niD(p1)D(p2).D(pk);/p1,p2.pk为ni的所有前趋结点ifD(ni)tempthenD(ni):=temp(3)重复(2),直到所有D(ni)不再改变.,d,p1,p2,pk,n,28,2回边定义:设ba是流图中一条有向边,且aD(b),则ba称是流图中的一条回边.可以从必经结点集中求出回边:forbNdoforaDOM(b)doif为一条有向边then为回边3可规约流图定义:一个流图称为可规约流图,但且仅当流图中除去回边而剩余部分构成无环路流图.,b,a,回边,DOM,29,4循环查找算法定理:若流图为可规约流图,已知有向边ba是一条回边,则由结点b,a以及有通路到达b而不经过a的所有结点序列构成流图的一个循环.查找回边ba构成的循环算法:(1)令loop:=b,a;push(S,b);(2)ifnotempty(S)thenn:=pop(s);for(minpn)do/pn为n的前趋结点集if(mnotinloop)thenloop:=loop+m;push(S,m),30,三优化信息-ud集为了进行循环优化,还应分析变量的定值及引用关系,这种关系称为引用-定值链,或称为引用-定值集.定义:若变量A在四元式d定值,并存在一条通路到达四元式u,且该通路上没有A的其它定值,则称A在d的定值到达u.定义:如在u处引用了变量A,则凡能到达u的A的所有定值点,构成了A在u处的引用-定值集,记为:udA.下面介绍如何求ud集.1到达-定值方程,31,首先定义四个基本集合:INB:代表到达基本块B入口点时的各变量的所有定值点集;OUTB:代表到达基本块B出口点时的各变量的所有定值点集;GENB:表示B中所定值的且到达B之后的定值点集;KILLB:表示属于B外的定值点,而这些定值点所定值的变量在B中又被重新定值这几个集合满足如下方程:OUTB=(INB-KILL(B)GENBINB=OUTp1OUTp2.OUTpkp1,p2.pk为B的前趋结点.该方程即为到达-定值方程,求解该方程,得到INB.,32,2求udA算法如下:若B中,变量A的引用点u之前有A的定值点d,且到达u,则udA=d;否则udA=di|diINB且di为A的定值点.这样,可以求出每个变量在引用点u的定值状况.,33,四循环的几种基本优化下面介绍三种循环优化:代码外提,强度削弱,删除归纳变量.代码外提定义:对于循环中的语句A:=BopC,若B及C均为常量,或者为循环中未改变的变量,那么每次循环A的值都一样,称A:=BopC为不变运算.对于不变运算,有可能把A:=BopC放到循环前,具体做法是:a)建立一前置结点;b)循环入口结点(唯一的)为前置结点的唯一后继;c)循环外流向入口结点的有向边,改为流向前置结点;d)把循环中可以外提的不变运算放在前置结点中.见下图:,34,循环入口结点,循环外流向前置结点,前置结点,循环入口结点,下面讨论两个问题:(1)哪些是循环中的不变运算?(2)循环中的哪些不变运算可以放到前置结点中?,循环外流向入口结点,循环内结点,循环内结点,改为,35,1不变运算的确定算法(1)察看循环中的每条四元式,若每个运算对象或为常量,或定值点在循环外的变量,则标记为不变运算;(2)察看尚未标记为不变运算的四元式,若每个运算对象或为常量,或定值点在循环外的变量,或在循环内具有唯一定值点的变量且该定值点已经标记为不变运算,则标记为不变运算;(3)重复(2),直到不产生新的不变运算.,36,2代码外提算法(1)对循环中每一不变运算(S)A:=BopC(包括A:=opC或A:=B),检查是否满足如下条件之一:a)S所在的结点是循环所有出口结点的必经结点,且S为变量A在循环中唯一定值点,且A的定值点S能到达循环中所有A的引用点;b)S为变量A在循环中唯一定值点,且A的定值点S能到达循环中所有A的引用点,且A在循环之后不再引用.(2)把循环中满足条件a)或b)的不变运算移至前置结点中,若运算对象B或C是在循环中定值,则只有当B或C的定值点四元式已放入前置结点中后,才可以把S外提.,37,强度削弱强度削弱是指循环中,把执行时间较长的运算转换为执行时间较短的运算.下面仅讨论乘法运算转换为加法运算.(注:并非每个乘运算都可以进行强度削弱)定义:若循环中对B只有唯一的递归赋值B:=B+C且C为循环不变量,则称B为循环的基本归纳变量.定义:若B为基本归纳变量,而A在循环中的定值,可以化归为B的线性函数:A:=C1*B+C2(C1,C2为循环不变量)则称A为归纳变量,并称A与B同族.,38,一般而言,若循环中有递归赋值B:=B+C(B每次循环递增常量C)而循环中对A的赋值为B的线性函数A:=C1*B+C2(C1,C2为常数)那么,循环中A:=C1*B+C2的乘运算可转换为加运算,具体做法如下:在前置结点中添加:A:=C1*