編譯原理及實(shí)現(xiàn)技術(shù)：24-中間代碼優(yōu)化2

第六章：中間代碼優(yōu)化（2）

公共表達(dá)式節(jié)省設(shè)有下列語(yǔ)句：t:=b*c;e:=b*c+b*c;c:=b*c+10;d:=b*c+d;優(yōu)化后，可得到下列語(yǔ)句：t:=b*c;e:=t+t;c:=t+10;d:=b*c+d;公共表達(dá)式節(jié)省公共表達(dá)式：是指兩個(gè)表達(dá)式中的子表達(dá)式他們的計(jì)算結(jié)果相同。公共表達(dá)式節(jié)省在局部進(jìn)行的時(shí)候都是針對(duì)基本塊的。相似性方法*編碼方法基于相似性的公共表達(dá)式節(jié)省必經(jīng)代碼：稱di代碼為dj代碼的必經(jīng)代碼，如果執(zhí)行dj代碼時(shí)di代碼一定已經(jīng)被執(zhí)行過(guò)了，在一個(gè)基本塊中若i<j則di代碼是dj代碼的必經(jīng)代碼活躍代碼：稱di:(ω,A,B,t1)在dj處是活躍的，如果di是dj的必經(jīng)代碼，且從di到dj期間均不改變A、B的值基于相似性的公共表達(dá)式節(jié)省ECC代碼（可節(jié)省的公共代碼）：稱一個(gè)運(yùn)算代碼dj是可節(jié)省的代碼并記為ECC，如果存在其一個(gè)必經(jīng)活躍代碼di，并且計(jì)算結(jié)果相同。（值得注意的是即使di和dj代碼完全相同，dj也不一定是可節(jié)省的）相似代碼：如果di和dj運(yùn)算符、運(yùn)算分量都相同，則稱di和dj為相似代碼基于相似性的公共表達(dá)式節(jié)省ECC定理：假設(shè)當(dāng)前代碼為運(yùn)算代碼dj：(ω1,A1,B1,t1)，如果存在相似的必經(jīng)活躍代碼，則dj一定是ECC代碼，例如基本塊：1:(+,A,B,T1)2:(+,A,B,T2)3:(*,T1,T2,T3)這是判定ECC的充分條件，而不是充要條件優(yōu)化為：1:(+,A,B,T1)3:(*,T1,T1,T3)判斷dj為相似性ECC的兩個(gè)要點(diǎn)：判斷是否存在其相似的必經(jīng)活躍代碼di，相似、必經(jīng)很容易判斷，構(gòu)建活躍代碼表來(lái)判定di在dj處是否活躍；等價(jià)替換，當(dāng)dj代碼被節(jié)省后，dj的結(jié)果tj在后續(xù)代碼中均被替換為ti，因此需要建立等價(jià)變量表，其元素具有形式(ti,tj)；基于相似性的公共表達(dá)式節(jié)省算法流程以基本塊為單位創(chuàng)建：活躍運(yùn)算代碼表、等價(jià)變量表每當(dāng)掃描新代碼，首先根據(jù)等價(jià)變量表進(jìn)行等價(jià)替換若當(dāng)前代碼是運(yùn)算代碼，則進(jìn)行判斷和優(yōu)化工作，并更新等價(jià)變量表若當(dāng)前代碼為賦值代碼，則進(jìn)行注銷活躍運(yùn)算代碼工作基于相似性的公共表達(dá)式節(jié)省例子：d=d+c*ba=d+c*bc=d+c*ba=d+c*b序號(hào)優(yōu)化前優(yōu)化后活躍代碼表等價(jià)變量表1(*,c,b,t1)(*,c,b,t1)12(+,d,t1,t2)(+,d,t1,t2)123(=,t2,-,d)(=,t2,-,d)14(*,c,b,t3)——1(t1,t3)5(+,d,t3,t4)(+,d,t1,t4)15(t1,t3)6(=,t4,-,a)(=,t4,-,a)15(t1,t3)7(*,c,b,t5)——15(t1,t3)(t1,t5)8(+,d,t5,t6)——15(t1,t3)(t1,t5)(t4,t6)9(=,t6,-,c)(=,t4,-,c)5"10(*,c,b,t7)(*,c,b,t7)510"11(+,d,t7,t8)(+,d,t7,t8)51011"12(=,t8,-,d)(=,t8,-,d)51011"基于值編碼的公共表達(dá)式節(jié)省擴(kuò)大ECC：將相似代碼的定義擴(kuò)充為不局限于分量的名字相同。例如：a=b*c;d=b;d=d*c盡管b*c和d*c看起來(lái)不同，但是實(shí)際上具有相同的值，故應(yīng)處理為ECC基于值編碼的公共表達(dá)式節(jié)省值編碼優(yōu)化方法的主要思想:對(duì)中間代碼中出現(xiàn)的每個(gè)分量（常量和變量）確定一個(gè)值編碼，使得具有相同值的分量編碼值相等.基于值編碼的公共表達(dá)式節(jié)省編碼原理：用到一張值編碼表，表示分量當(dāng)前值編碼若當(dāng)前考察的代碼為dk：(ω,u1,u2,u3)：若值編碼表中已有(u1,mi)則令dk:ui的值編碼為mi,i=1,2,3否則為dk:ui創(chuàng)建一個(gè)新編碼m填入編碼表若考察代碼為dk：(＝,u1,－,u2)：u1的處理處理與之前相同令dk:u2的編碼與dk:u1的編碼相同基于值編碼的公共表達(dá)式節(jié)省值編碼性質(zhì)不同分量上的相同常量一定具有相同值編碼不同分量上的相同變量未必具有相同編碼不同常量的編碼值一定不同，對(duì)變量來(lái)說(shuō)并非如此每當(dāng)一個(gè)變量x被賦值，x將得到一個(gè)新的編碼，使得后面代碼中的x分量取編碼值n，直至x再被賦值基于值編碼的公共表達(dá)式節(jié)省在分析的過(guò)程中對(duì)應(yīng)每條四元式還要生成一個(gè)編碼四元式。μ(x)表示任意運(yùn)算分量x的值編碼；把(ω,μ(A),μ(B),μ(t))叫作(ω,A,B,t)的映象碼；基于值編碼的公共表達(dá)式節(jié)省算法流程：從基本塊的第一條四元式開(kāi)始等價(jià)變量表替換對(duì)四元式中的分量進(jìn)行編碼值編碼表替換，生成編碼四元式遇到運(yùn)算型四元式，往前查編碼四元式中與當(dāng)前編碼四元式運(yùn)算符、運(yùn)算分量都相同的，若有則說(shuō)明確定ECC，刪去當(dāng)前四元式，把等價(jià)的名字填入等價(jià)表遇到賦值(=,a,-,b),b的編碼賦值為a的編碼例：a=b*c+b*c;d=b；

e=d*c+b*c序號(hào)中間代碼映像abcdet1t2t3t4t5t6等價(jià)表優(yōu)化后1*,b,c,t1123123不變2*,b,c,t21233(t1,t2)節(jié)省3+,t1,t2,t33344+,t1,t1,t34=,t3,-,a4不變5=,b,-,d1不變6*,d,c,t41233(t1,t4)節(jié)省7*,b,c,t51233(t1,t5)節(jié)省8+,t4,t5,t63344(t3,t6)節(jié)省9=,t6,-,e=,t3,-,e循環(huán)不變式外提循環(huán)不變式:如果一個(gè)表達(dá)式E在一個(gè)循環(huán)中不改變其值，則稱它為該循環(huán)的不變表達(dá)式。循環(huán)不變式外提：將循環(huán)不變式提到循環(huán)外面進(jìn)行.例如，假設(shè)有程序段：i:=1;//t=x*y;whilei<=1000dobegina[i]:=x*y//t;i:=i+1end;則x*y是該循環(huán)的不變表達(dá)式，可以把它提到循環(huán)外邊矩陣乘法：有a，b為10*10數(shù)組for(i=1~10)for(j=1~10)for(k=1~10)c[i][j]=c[i][j]+a[i][k]*b[k][j];a[i]地址的計(jì)算與j、k循環(huán)無(wú)關(guān)，c[i][j]地址的計(jì)算與k循環(huán)無(wú)關(guān)循環(huán)不變式外提解決兩個(gè)問(wèn)題檢查循環(huán)體中哪些變量的值被改變過(guò)根據(jù)這個(gè)結(jié)果來(lái)看哪些表達(dá)式是不變的表達(dá)式建立變量定值表，將循環(huán)體中值被改變的變量都填到表里，若某運(yùn)算型四元式中兩個(gè)運(yùn)算分量都不出現(xiàn)在這個(gè)表里，就說(shuō)明其值不發(fā)生改變，可以進(jìn)行外提。循環(huán)不變式外提對(duì)循環(huán)體四元式進(jìn)行第一遍掃描，把有定值的變量填到變量定值表中，若它是一個(gè)運(yùn)算型四元式(ω1,A1,B1,t1)，則把t1填到表中，若為賦值型四元式(=，a，-，b)則把b填入表中循環(huán)不變式外提為第二遍掃描，每遇到一個(gè)運(yùn)算型四元式(ω1,A1,B1,t1)，若A1、B1都不在變量定值表中，則將其提到循環(huán)體外，同時(shí)在變量定值表中刪去t1優(yōu)化前四元式序列：

(ASSIG,1,─,i) (WHILE,—，—，—) (LE,i,100,t1) (DO,t1,—，—) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,─,z) (MULTI,2,k,t4)

(MULTI,2,k,t5)

(MULTI,t5,2,t6)

(ADDI,t4,t6,t7) (ASSIG,t7,─,a) (ADDI,i,1,t8) (ASSIG,t8,─,i) (ENDWHILE,—，—，—)i:=1whilei<=100do begin

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}循環(huán)優(yōu)化前四元式序列：

(ASSIG,1,─,i)

(WHILE,-，-，-) (LE,i,100,t1)

(DO,t1,-，-) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,-,z) (MULTI,2,k,t4)

(MULTI,t4,2,t6)

(ADDI,t4,t6,t7) (ASSIG,t7,─,a) (ADDI,i,1,t8) (ASSIG,t8,─,i)

(ENDWHILE,-，-，-)LoopDef={t1,t2,t3,z,t4,t6,t7,

a,t8,i}循環(huán)優(yōu)化前四元式序列：

(ASSIG,1,─,i)

(WHILE,-，-，-) (LE,i,100,t1)

(DO,t1,—，—) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,─,z) (MULTI,2,k,t4)

(MULTI,t4,2,t6)

(ADDI,t4,t6,t7) (ASSIG,t7,─,a) (ADDI,i,1,t8) (ASSIG,t8,─,i)

(ENDWHILE,-，-，-)循環(huán)優(yōu)化后四元式序列：

(ASSIG,1,─,i) (MULTI,2,k,t4)

(MULTI,t4,2,t6)

(ADDI,t4,t6,t7)

(WHILE,-，-，-) (LE,i,100,t1)

(DO,t1,—，—) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,─,z) (ASSIG,t7,─,a) (ADDI,i,1,t8) (ASSIG,t8,─,i)

(ENDWHILE,，-，-)循環(huán)不變式外提中注意的問(wèn)題多層循環(huán)問(wèn)題中，一個(gè)四元式從里層開(kāi)始可以被外提若干次，里層變量定值表屬于外層變量定值表除法不外提賦值絕不外提非良性循環(huán)（函數(shù)調(diào)用和地址應(yīng)用型參數(shù)賦值）不做外提優(yōu)化例子例2:已知:a:array[1..10][1..1000]ofinteger;設(shè)有如下循環(huán)語(yǔ)句：

j:=1 whilej<=1000do begina[i][j]:=0;j:=j+1;end;優(yōu)化后的四元式序列：(ASSIG,1,─,j)(SUBI,i,1,t2)(MULTI,t2,1000,t3)(AADD,a,t3,t4)(WHILE,─,─,─)(LE,j,1000,t1)(DO,t1,─,─)(SUBI,j,1,t5)(MULTI,t5,1,t6)(AADD,t4,t6,t7)(ASSIG,0,─,t7)(ADDI,j,1,t8)(ASSIG,t8,─,j)(ENDWHILE,─,─,─)LoopDef={t1,t5,t6,t7,t8}優(yōu)化前的四元式序列：(ASSIG,1,─,j)(WHILE,─,─,─)(LE,j,1000,t1)(DO,t1,─,─)(SUBI,i,1,t2)(MULTI,t2,1000,t3)(AADD,a,t3,t4)(SUBI,j,1,t5)(MULTI,t5,