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

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

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

e=d*c+b*c序號中間代碼映像abcdet1t2t3t4t5t6等價表優(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)不變式:如果一個表達式E在一個循環(huán)中不改變其值，則稱它為該循環(huán)的不變表達式。循環(huán)不變式外提：將循環(huán)不變式提到循環(huán)外面進行.例如，假設(shè)有程序段：i:=1;//t=x*y;whilei<=1000dobegina[i]:=x*y//t;i:=i+1end;則x*y是該循環(huán)的不變表達式，可以把它提到循環(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、k循環(huán)無關(guān)，c[i][j]地址的計算與k循環(huán)無關(guān)循環(huán)不變式外提解決兩個問題檢查循環(huán)體中哪些變量的值被改變過根據(jù)這個結(jié)果來看哪些表達式是不變的表達式建立變量定值表，將循環(huán)體中值被改變的變量都填到表里，若某運算型四元式中兩個運算分量都不出現(xiàn)在這個表里，就說明其值不發(fā)生改變，可以進行外提。循環(huán)不變式外提對循環(huán)體四元式進行第一遍掃描，把有定值的變量填到變量定值表中，若它是一個運算型四元式(ω1,A1,B1,t1)，則把t1填到表中，若為賦值型四元式(=，a，-，b)則把b填入表中循環(huán)不變式外提為第二遍掃描，每遇到一個運算型四元式(ω1,A1,B1,t1)，若A1、B1都不在變量定值表中，則將其提到循環(huán)體外，同時在變量定值表中刪去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)不變式外提中注意的問題多層循環(huán)問題中，一個四元式從里層開始可以被外提若干次，里層變量定值表屬于外層變量定值表除法不外提賦值絕不外提非良性循環(huán)（函數(shù)調(diào)用和地址應(yīng)用型參數(shù)賦值）不做外提優(yōu)化例子例2:已知:a:array[1..10][1..1000]ofinteger;設(shè)有如下循環(huán)語句：

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,