资源描述
第六章：中间代码优化（2）2公共表达式节省w 设有下列语句：t:=b*c;e:=b*c+b*c;c:=b*c+10;d:=b*c+d;w 优化后，可得到下列语句：t:=b*c;e:=t+t;c:=t+10;d:=b*c+d;3公共表达式节省w 公共表达式：是指两个表达式中的子表达式他们的计算结果相同。w 公共表达式节省在局部进行的时候都是针对基本块的。v相似性方法*v编码方法4基于相似性的公共表达式节省w 必经代码：称di代码为dj代码的必经代码，如果执行dj代码时di代码一定已经被执行过了，在一个基本块中若ij则di代码是dj代码的必经代码w 活跃代码：称di:(,A,B,t1)在dj处是活跃的，如果di是dj的必经代码，且从di到dj期间均不改变A、B的值5基于相似性的公共表达式节省w ECC代码（可节省的公共代码）：称一个运算代码dj是可节省的代码并记为ECC，如果存在其一个必经活跃代码di，并且计算结果相同。（值得注意的是即使di和dj代码完全相同，dj也不一定是可节省的）w 相似代码：如果di和dj运算符、运算分量都相同，则称di和dj为相似代码6基于相似性的公共表达式节省w ECC定理：假设当前代码为运算代码dj：(1,A1,B1,t1)，如果存在相似的必经活跃代码，则dj一定是ECC代码，例如基本块：1:(+,A,B,T1)2:(+,A,B,T2)3:(*,T1,T2,T3)这是判定ECC的充分条件，而不是充要条件优化为：1:(+,A,B,T1)3:(*,T1,T1,T3)7w 判断dj为相似性ECC的两个要点：v判断是否存在其相似的必经活跃代码di，相似、必经很容易判断，构建活跃代码表来判定di在dj处是否活跃；v等价替换，当dj代码被节省后，dj的结果tj在后续代码中均被替换为ti，因此需要建立等价变量表，其元素具有形式(ti,tj)；基于相似性的公共表达式节省8w 算法流程1.以基本块为单位2.创建：活跃运算代码表、等价变量表3.每当扫描新代码，首先根据等价变量表进行等价替换4.若当前代码是运算代码，则进行判断和优化工作，并更新等价变量表5.若当前代码为赋值代码，则进行注销活跃运算代码工作基于相似性的公共表达式节省例子：d=d+c*ba=d+c*bc=d+c*ba=d+c*b序号序号优化前优化前优化后优化后活跃代码表活跃代码表等价变量表等价变量表1(*,c,b,t1)(*,c,b,t1)12(+,d,t1,t2)(+,d,t1,t2)1 23(=,t2,-,d)(=,t2,-,d)14(*,c,b,t3)1(t1,t3)5(+,d,t3,t4)(+,d,t1,t4)1 5(t1,t3)6(=,t4,-,a)(=,t4,-,a)1 5(t1,t3)7(*,c,b,t5)1 5(t1,t3)(t1,t5)8(+,d,t5,t6)1 5(t1,t3)(t1,t5)(t4,t6)9(=,t6,-,c)(=,t4,-,c)510(*,c,b,t7)(*,c,b,t7)5 1011(+,d,t7,t8)(+,d,t7,t8)5 10 1112(=,t8,-,d)(=,t8,-,d)5 10 1110基于值编码的公共表达式节省w 扩大ECC：将相似代码的定义扩充为不局限于分量的名字相同。例如：a=b*c;d=b;d=d*c尽管b*c和d*c看起来不同，但是实际上具有相同的值，故应处理为ECC11基于值编码的公共表达式节省w 值编码优化方法的主要思想:对中间代码中出现的每个分量（常量和变量）确定一个值编码，使得具有相同值的分量编码值相等.12基于值编码的公共表达式节省w 编码原理：w 用到一张值编码表，表示分量当前值编码w 若当前考察的代码为dk：(,u1,u2,u3)：n若值编码表中已有(u1,mi)则令dk:ui的值编码为mi,i=1,2,3n否则为dk:ui创建一个新编码m填入编码表w 若考察代码为dk：(,u1,u2)：nu1的处理处理与之前相同n令dk:u2的编码与dk:u1的编码相同13基于值编码的公共表达式节省w 值编码性质1.不同分量上的相同常量一定具有相同值编码2.不同分量上的相同变量未必具有相同编码3.不同常量的编码值一定不同，对变量来说并非如此4.每当一个变量x被赋值，x将得到一个新的编码，使得后面代码中的x分量取编码值n，直至x再被赋值14基于值编码的公共表达式节省w 在分析的过程中对应每条四元式还要生成一个编码四元式。w(x)表示任意运算分量x的值编码；w 把(,(A),(B),(t)叫作(,A,B,t)的映象码；15基于值编码的公共表达式节省算法流程：从基本块的第一条四元式开始1.等价变量表替换2.对四元式中的分量进行编码3.值编码表替换，生成编码四元式4.遇到运算型四元式，往前查编码四元式中与当前编码四元式运算符、运算分量都相同的，若有则说明确定ECC，删去当前四元式，把等价的名字填入等价表5.遇到赋值(=,a,-,b),b的编码赋值为a的编码例：a=b*c+b*c;d=b；e=d*c+b*c序号序号中间代码中间代码映映像像abcdet1t2t3t4t5t6等价等价表表优化后优化后1*,b,c,t1123123不变2*,b,c,t21233(t1,t2)节省3+,t1,t2,t33344+,t1,t1,t34=,t3,-,a4不变5=,b,-,d1不变6*,d,c,t41233(t1,t4)节省7*,b,c,t51233(t1,t5)节省8+,t4,t5,t63344(t3,t6)节省9=,t6,-,e=,t3,-,e17循环不变式外提u循环不变式:如果一个表达式E在一个循环中不改变其值，则称它为该循环的不变表达式。u循环不变式外提：将循环不变式提到循环外面进行.例如，假设有程序段：i:=1;/t=x*y;while i=1000 do begin ai:=x*y/t;i:=i+1 end;则x*y是该循环的不变表达式，可以把它提到循环外边矩阵乘法：有a，b为10*10数组for(i=110)for(j=110)for(k=110)cij=cij+aik*bkj;ai地址的计算与j、k循环无关，cij地址的计算与k循环无关19循环不变式外提w 解决两个问题v检查循环体中哪些变量的值被改变过v根据这个结果来看哪些表达式是不变的表达式w 建立变量定值表，将循环体中值被改变的变量都填到表里，若某运算型四元式中两个运算分量都不出现在这个表里，就说明其值不发生改变，可以进行外提。20循环不变式外提u对循环体四元式进行第一遍扫描，把有定值的变量填到变量定值表中，若它是一个运算型四元式(1,A1,B1,t1)，则把t1填到表中，若为赋值型四元式(=，a，-，b)则把b填入表中u循环不变式外提为第二遍扫描，每遇到一个运算型四元式(1,A1,B1,t1)，若A1、B1都不在变量定值表中，则将其提到循环体外，同时在变量定值表中删去t1优化前四元式序列：1.1.(ASSIG,1,i)(ASSIG,1,i)2.2.(WHILE,(WHILE,，)3.3.(LE,i,100,t1)(LE,i,100,t1)4.4.(DO,t1,(DO,t1,，)5.5.(MULT(MULTI I,i,k,t2),i,k,t2)6.6.(MULT(MULTI I,t2,5,t3),t2,5,t3)7.7.(ASSIG,t3,z)(ASSIG,t3,z)8.8.(MULT(MULTI I,2,k,t4),2,k,t4)9.9.(MULT(MULTI I,2,k,t,2,k,t5 5)10.10.(MULT(MULTI I,t,t5 5,2 2,t,t6 6)11.11.(ADADDIDI,t t4 4,t,t6 6,t,t7 7)12.12.(ASSIG,t(ASSIG,t7 7,a),a)13.13.(ADD(ADDI I,i,1,t,i,1,t8 8)14.14.(ASSIG,t(ASSIG,t8 8,i),i)15.15.(ENDWHILE,(ENDWHILE,，)i:=1while i=100 dobegin z:=i*k*5;a:=2*k+2*k*2;i:=i+1;endt4LoopDef=t1,t2,t3,z,t4,t5,t6,t7,a,t8,i循环优化前四元式序列：循环优化前四元式序列：1.1.(ASSIG,1,i)(ASSIG,1,i)2.2.(WHILE,(WHILE,-，-，-)3.3.(LE,i,100,t1)(LE,i,100,t1)4.4.(DO,t1,(DO,t1,-，-)5.5.(MULT(MULTI I,i,k,t2),i,k,t2)6.6.(MULT(MULTI I,t2,5,t3),t2,5,t3)7.7.(ASSIG,t3,(ASSIG,t3,-,z),z)8.8.(MULT(MULTI I,2,k,t4),2,k,t4)9.9.(MULT(MULTI I,t,t4 4,2 2,t,t6 6)10.10.(AD(ADDIDI,t t4 4,t,t6 6,t,t7 7)11.11.(ASSIG,t(ASSIG,t7 7,a),a)12.12.(ADD(ADDI I,i,1,t,i,1,t8 8)13.13.(ASSIG,t(ASSIG,t8 8,i),i)14.14.(ENDWHILE,(ENDWHILE,-，-，-)LoopDef=t1,t2,t3,z,t4,t6,t7,a,t8,i循环优化前四元式序列：循环优化前四元式序列：1.(ASSIG,1,i)2.(WHILE,-，-，-)3.(LE,i,100,t1)4.(DO,t1,，)5.(MULTI,i,k,t2)6.(MULTI,t2,5,t3)7.(ASSIG,t3,z)8.(MULTI,2,k,t4)9.(MULTI,t4,2,t6)10.(ADDI,t4,t6,t7)11.(ASSIG,t7,a)12.(ADDI,i,1,t8)13.(ASSIG,t8,i)14.(ENDWHILE,-，-，-)循环优化后四元式序列：循环优化后四元式序列：1.(ASSIG,1,i)2.(MULTI,2,k,t4)3.(MULTI,t4,2,t6)4.(ADDI,t4,t6,t7)5.(WHILE,-，-，-)6.(LE,i,100,t1)7.(DO,t1,，)8.(MULTI,i,k,t2)9.(MULTI,t2,5,t3)10.(ASSIG,t3,z)11.(ASSIG,t7,a)12.(ADDI,i,1,t8)13.(ASSIG,t8,i)14.(ENDWHILE,，-，-)24循环不变式外提中注意的问题1.多层循环问题中，一个四元式从里层开始可以被外提若干次，里层变量定值表属于外层变量定值表2.除法不外提3.赋值绝不外提4.非良性循环（函数调用和地址应用型参数赋值）不做外提优化25例子例2:已知:a:array1.101.1000 of integer;设有如下循环语句：j:=1while j=1000 dobegin aij:=0;j:=j+1;end;优化后的四元式序列：优化后的四元式序列：(ASSIG,1,j)(ASSIG,1,j)(SUBI,i,1,t2)(SUBI,i,1,t2)(MULTI,t2,1000,t3)(MULTI,t2,1000,t3)(AADD,a,t3,t4)(AADD,a,t3,t4)(WHILE,)(WHILE,)(LE,j,1000,t1)(LE,j,1000,t1)(DO,t1,)(DO,t1,)(SUBI,j,1,t5)(SUBI,j,1,t5)(MULTI,t5,1,t6)(MULTI,t5,1,t6)(AADD,t4,t6,t7)(AADD,t4,t6,t7)(ASSIG,0,t7)(ASSIG,0,t7)(ADDI,j,1,t8)(ADDI,j,1,t8)(ASSIG,t8,j)(ASSIG,t8,j)(ENDWHILE,)(ENDWHILE,)LoopDef=t1,t5,t6,t7,t8优化前的四元式序列：优化前的四元式序列：(ASSIG,1,j)(ASSIG,1,j)(WHILE,)(WHILE,)(LE,j,1000,t1)(LE,j,1000,t1)(DO,t1,)(DO,t1,)(SUBI,i,1,t2)(SUBI,i,1,t2)(MULTI,t2,1000,t3)(MULTI,t2,1000,t3)(AADD,a,t3,t4)(AADD,a,t3,t4)(SUBI,j,1,t5)(SUBI,j,1,t5)(MULTI,t5,1,t6)(MULTI,t5,1,t6)(AADD,t4,t6,t7)(AADD,t4,t6,t7)(ASSIG,0,t7)(ASSIG,0,t7)(ADDI,j,1,t8)(ADDI,j,1,t8)(ASSIG,t8,j)(ASSIG,t8,j)(ENDWHILE,)(ENDWHILE,)LoopDefLoopDef=t1,t2,t3,=t1,t2,t3,t4,t5,t6,t7,t8,jt4,t5,t6,t7,t8,j j:=1while j=1000 dobegin aij:=0;j:=j+1;end;
展开阅读全文