编译原理 Chapter10[1]

1第十章代码优化2-优化的定义:对程序进行各种等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大，或占用存储空间减少，或两者都有。空间效率和时间效率有时是一对矛盾，有时不能兼顾。-三条优化原则-等价:是指不改变程序的运行结果；-有效:主要指优化后的目标代码运行时间较短,以及占用的存储空间较小。-合算:应尽可能以较低的代价取得较好的优化效果。10.1概述3-优化的时机-优化可在编译的各个阶段进行。最主要的时机是在语法、语义分析生成中间代码之后，在中间代码上进行。这一类优化不依赖于具体的计算机，而取决于语言的结构。另一类优化则是在生成目标程序时进行的，它在很大程度上与具体的计算机有关。-按所涉及的程序范围可分为三种级别-局部优化、-循环优化、-全局优化。45变量的引用点和定值点点：某一四元式的位置。引用点(使用点):在该点使用了该变量。如:表达式中的变量。定值点(定义点):在该点变量被赋值或输入值。如：赋值语句左部的变量。例1：x:=x+1;例2:x:＝y＋z称为对x定值并引用y和z。引用点定值点6基本块内的变换为局部优化。基本块定义:程序中一顺序执行的语句序列:其中只有一个入口语句(第一条语句),一个出口语句(最后一条语句)。执行时只能从入口语句进入，从出口语句退出，中途没有停止或分枝。例如：t1:＝a*at2:＝a*bt3:＝2*t2t4:＝t1+t2t5:＝b*bt6:＝t4+t510.2局部优化优点：将基本块作为优化要考虑的主要范围这一原则为优化决策提供了基础，在一般情况下，将会产生更高质量的代码。7一、基本块的划分三地址语句序列=基本块表1.入口语句：采用如下规则确定：(a)代码序列的第一个语句。(b)条件或无条件转移语句的转移目标语句。(c)紧跟在无条件转移语句或条件转移语句后面的语句。8算法:划分四元式程序形成基本块－输入：一个四元式语句序列。－输出：一个基本块表,其中每一条四元式语句仅在一个块中。－方法:1.确定各个基本块的入口语句。2.对每一个入口语句。构造其所属的基本块:–(1)由该入口语句到下一入口语句(不包括)–(2)由该入口语句到一个转移语句(包括)–(3)由该入口语句到一个停语句(包括)。由(1)或(2)或(3)之间的语句序列组成。3.未被纳入某一基本块中间的语句,要删除。9例：(1)readx(2)ready(3)r:=xmody(4)ifr=0goto(8)(5)x:=y(6)y:=r(7)goto(3)(8)writey(9)halt10(1)P:=0(2)I:=1(3)T1:=4*I(4)T2:=addr(A)-4(5)T3:=T2[T1](6)T4:=4*I(7)T5:=addr(B)－4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I＋1(12)ifI＜＝20goto(3)P:=0;例forI:=1to20doP:=P＋A[i]*B[i];11二.基本块的变换1.删除公共子表达式2.复写传播3.删除无用代码4.重新命名临时变量5.交换语句次序6.合并已知量12公共子表达式:①子表达式E先前已计算过。②且从上次计算到现在，E中的变量的值没有改变。优点:避免重复计算。t1:=b*c;t2:=x+t1;x:=t2;t3:=b*c;t4:=x+t3;y:=t4;例如：x:=x+b*c;y:=x+b*c;t3:=t1;X1X2复写传播t4:=x+t1;1.删除公共子表达式(多余运算)：结果：t1:=b*c;t2:=x+t1;x:=t2;t3:=t1;t4:=x+t1;y:=t4;132.复写传播-形成为f:=g的赋值叫做复写语句。-优化过程中会大量引入复写。-复写传播变换的做法是在复写语句f:=g后，尽可能用g代表f。-复写传播变换本身并不是优化，但它给其它优化带来机会。-常量合并-死代码删除14(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)－4(3)T1:=4*I(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)I:=I＋1(3’)T1:=T1+4(12)ifI＜＝20goto(5)T1例如图11.4153.删除无用代码四元式t1:=xopy;t1不再被引用，则无用。例如:①A:=B；…；{未引用A}A:=C*D则①A:=B；为无用代码，可删除4.重新命名临时变量例如:t:=b+cu:=b+c16(1)P:=0(2)I:=1(4)T2:=addr(A)-4(7)T5:=addr(B)－4(3)T1:=4(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)I:=I＋1(3’)T1:=T1+4(12)ifT1＜＝80goto(5)无用代码175.交换语句次序目的：减少临时变量例如:相邻两个语句t1:=b+ct2:=x+yt2:=x+yt1:=b+c186.合并已知量是将能在编译时计算出值的表达式用其相应的值替代，即如果在编译时，编译程序能知道这一个表达式的所有操作数的值，则此表达式就可由其计算出的值替代。A:=BopCA:=opB若B与C为已知量(在编译时可以计算出值),则计算出BopC或opB的值t,改写为A:=t;19例子：下面的程序段PI=3.141592R=2S=PI*R*R可重写为：PI=3.141592R=2S=3.141592*2*2进一步的合并，则最终产生：PI=3.141592R=2S=12.566368注意∶在所有后继的语句中，PI或S的每一次出现都可由它的对应值替代，直到该变量被一个语句重新定义为止。20三、基本块优化的实现（DAG的使用）基本块优化的实现：从四元式序列构造DAG，然后再从DAG重写四元式。DAG(directedacyclicgraph的缩写)：有向非循环图,也称无环路有向图。DAG:如果有向图中任一通路都不是环路,则称该有向图为无环路有向图，简称DAG。21P240图11.8DAGP240图11.7非DAGn1n2n3n4n2n3n5n1n7n8n9n6n422DAG图中结点的特点：1.叶结点标记:标识符名(变量名)或常数,写在结点下面代表:该结点代表该变量或常数的值。地址的表示：Addr(A)通常将其标识符加上下标0,表示该变量的初值2.内部结点标记:一个运算符号。写在结点下面。代表:利用后续结点运算出来的值。3．图中各个结点可能附加一个或多个标识符,表示这些标识符具有该结点所代表的值，写在结点右面。23(0)A:=B0型四元式相应的DAG：按后续结点个数分类(0)n1AB(1)n2Aopn1B(2)n3An1Bopn2C(3)n3An1B=[]n2C(4)n3(s)n1Bropn2C(5)n4n1D[]=n3Cn2B(6)n1(s)(1)A:=opB1型(2)A:=BopC2型(3)A:=B[C]2型(4)ifBropCgoto(s)2型(5)D[C]:=B3型(6)goto(s)24算法：构造一个DAG输入:一个基本块。输出:此基本块的一个DAG,其中包含如下的信息：1.每个结点都有一个标记。叶结点的标记是一个标识符(允许是常数),内部结点的标记是一个运算符号。2.在每个结点上有一个附加的标识符表(可能为空),这里的标识符不允许是常数。方法:假定存在一个函数node(identifierA),当我们在建立DAG时,它将返回最新建的结点,值或为结点编号或者无定义。假设:要考虑的四元式语句包括如下三种形式:(0)A:=B0型(1)A:=opB1型(2)A:=BopC2型ifi=20goto－可当作(1)型,其中A无定义。25仅含0,1,2型四元式的基本块的DAG构造算法:首先，DAG为空。对基本块的每一四元式，依次执行：1.-如果NODE（B）无定义，则构造一标记为B的叶结点并定义NODE（B）为这个结点；-如果当前四元式是0型，则记NODE(B)的值为n，转4。-如果当前四元式是1型，则转2(1）。-如果当前四元式是2型，则：(I)如果NODE(1)无定义，则构造一标记为C的叶结点并定义NODE(1)为这个结点；(II)转2(2)262．(1)如果NODE(B)是标记为常数的叶结点，则转2(3)，否则转3(1)。(2)如果NODE(B)和NODE(C)都是标记为常数的叶结点，则转2(4)，否则转3(2)。(3)执行opB(即合并已知量)，令得到的新常数为P。如果NODE(B)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。(4)执行BopC(即合并已知量)，令得到的新常数为P。如果NODE(B)或NODE(C)是处理当前四元式时新构造出来的结点，则删除它。如果NODE(P)无定义，则构造一用P做标记的叶结点n。置NODE(P)=n，转4。273(1)检查DAG中是否已有一结点，其唯一后继为NODE(B)，且标记为op(即找公共子表达式)。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。(2)检查中DAG中是否已有一结点，其左后继为NODE(B)，其右后继为NODE(C)，且标记为op(即找公共子表达式)。如果没有，则构造该结点n，否则就把已有的结点作为它的结点并设该结点为n，转4。284.如果NODE(A)无定义，则把A附加在结点n上并令NODE(A)=n；否则先把A从NODE(A)结点上附加标识符集中删除（注意，如果NODE(A)是叶结点，则其标记A不删除），把A附加到新结点n上并令NODE(A)=n。转处理下一四元式。而后，我们可由DAG重新生成原基本块的一个优化的代码序列。29(1)型A:=opB仅含0,1,2型四元式的基本块的DAG构造算法:首先：假定DAG为空，即没有任何结点。对基本块中的每一四元式依次执行：1.4(0)型A:=B2.12.3合并已知量3.1B是一标记为常数的叶结点否(2)型A:=BopC2.22.4合并已知量3.2NODE(A)和NODE(B)是标记为常数的叶结点。否30T2n1T03.14n2T16.28n5n3R+n4rA*,Bn6,T3,T4,T5n7-T6n8*例如：(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*T6B31DAG的应用(用于优化)步2:合并已知量。步3:检查公共子表达式，可用于消除公共子表达式。步4:删除无用赋值。T2n1T03.14n2T16.28n5n3R+n4rA*,Bn6,T3,T4,T5n7-T6n8*B合并已知量公共子表达式无用赋值32DAG的优化并生成四元式：P244按照DAG中结点生成的顺序还原四元式。(1)叶结点,B:标记,A:附加标识符生成A:=B;(2)内部结点，A:附加标识符,op:标记①标记是op不是rop,两个子结点：A:=BopC一个子结点：A:=opB(3)多个附加标识符A1,A2,……,AK①叶结点，标记为A(消除公共子表达式)A1:=AA2:=AAK:=A②内部结点，(消除公共子表达式)A1:=BopCA2:=A1AK:=A1同时，消除无用赋值、合并已知量。33例如：(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(删除无用代码)叶结点:基本块外被定值,块内引用。内部结点:基本块内被定值,块外可引用。T2n1T03.14n2T16.28n5n3R+n4rA*,Bn6,T3,T4,T5n7-T6n8*B合并已知量公共子表达式无