中間代碼優化第一頁，共二十四頁，編輯于2023年，星期四8.1中間代碼優化概述為什么在中間代碼上進行優化？有些優化只在中間代碼一級進行優化的目標最小的代價，提高目標程序運行速度是否優化，優化到何種程度取決于編譯器設計者中間代碼優化的分類按照優化范圍：分為局部優化和非局部優化(循環優化和全局優化)按照優化方法：分為常量表達式優化，公共子表達式優化，循環不變量外提優化第二頁，共二十四頁，編輯于2023年，星期四8.1中間代碼優化概述常量表達式優化(合并常數)v=a*b+c,若a=2,b=3,c=5則可用v=11替換u=v+3;u替換成14公共子表達式節省(消除重復操作)t=b*c;e=b*c+b*c;c=b*c+10;d=b*c+d;t=b*c;e=t+t;c=b*c+10;d=b*c+d;循環不變量外提while(k<10){a[k]=b*c;k=k+1}t=b*c;while(k<10){a[k]=t;k=k+1;}第三頁，共二十四頁，編輯于2023年，星期四8.2基本塊劃分基本塊是指程序的一組順序執行的語句序列，其中只有一個出口和一個入口。入口：基本塊的第一條語句；出口：基本塊的最后一條語句；語句1語句2語句n語句1語句2語句n語句1語句2語句n第四頁，共二十四頁，編輯于2023年，星期四8.2基本塊劃分基本塊劃分方法：第一條四元式作為第一個基本塊的入口；當遇到標號性四元式時，結束當前基本塊，該標號性四元式作為新基本塊的入口；當遇到轉移性四元式時，結束當前基本塊，并把該轉移性四元式作為當前基本塊的出口；當遇到賦值四元式(ASSIG,A,_,x)，且x為變參時，結束當前基本塊，并把該四元式作為當前基本塊的出口。第五頁，共二十四頁，編輯于2023年，星期四8.2基本塊劃分標號性四元式：(LABEL,-,-,L)(ENTRY,Lf,size,Level)(WHILE,-,-,-)(ENDIF,-,-,-)轉移性四元式：(JMP/JMP0/JMP1,-,-,L)(THEN,E,-,-)(ELSE,-,-,-)(DO,E,-,-)(ENDWHILE,-,-,-)(ENDFUNC,-,-,-)第六頁，共二十四頁，編輯于2023年，星期四設有源程序如下：

y=1;L:ifAandBthenx=0elsey=0;x=x+1;y=y-1;whilex+y>0dox=x-1;z=0;(ASSIG,1,-,y)(LABEL,-,-,L)(AND,A,B,t)(THEN,t,-,-)(ASSIG,0,-,x)(ELSE,-,-,-)(ASSIG,0,-,y)(ENDIF,-,-,-)(ADDI,x,1,t1)(ASSIG,t1,-,x)(SUBI,y,1,t2)(ASSIG,t2,-,y)(WHILE,-,-,-)(ADDI,x,y,t3)(GT,t3,0,t4)(DO,t4,-,-)(SUBI,x,1,t5)(ASSIG,t5,-,x)(ENDWHILE,-,-,-)(ASSIG,0,-,z)第七頁，共二十四頁，編輯于2023年，星期四(ASSIG,1,-,y)(LABEL,-,-,L)(AND,A,B,t)(THEN,t,-,-)(ASSIG,0,-,x)(ELSE,-,-,-)(ASSIG,0,-,y)(ENDIF,-,-,-)(ADDI,x,1,t1)(ASSIG,t1,-,x)(SUBI,y,1,t2)(ASSIG,t2,-,y)(WHILE,-,-,-)(ADDI,x,y,t3)(GT,t3,0,t4)(DO,t4,-,-)(SUBI,x,1,t5)(ASSIG,t5,-,x)(ENDWHILE,-,-,-)(ASSIG,0,-,z)B1B2B3B4B5B6B7B8第八頁，共二十四頁，編輯于2023年，星期四程序流圖：以基本塊為結點的有向圖在一個基本塊上進行的優化稱為局部優化在多個基本塊上進行的優化稱為非局部優化循環優化(多個基本塊)全局優化(整個程序流圖)B2B5B3B4B1B6B7B8第九頁，共二十四頁，編輯于2023年，星期四8.3常量表達式的局部優化常量表達式：任何時候都取固定常數值的表達式優化方法：用常量值替換原來的運算i=30;j=2*i;k=i*j;可用k=1800代替優化的關鍵：知道哪些量取常數值方法：建立常量定義表ConDef(id,value)優化算法：在入口處，ConDef為空；讀取一個四元式tuple,對tuple中的分量進行值替換得newtuple;若newtuple是(,A,B,t)情形：且A,B都是常數值，則計算AB的值v，并在ConDef中填入(t,v),同時刪除四元式(,A,B,t)；若newtuple是(ASSIG,A,-,B)情形：若A是常數，則把(B,A)填入ConDef中(若已有B的表項，則只需修改B的值)；否則，從ConDef中刪除B的表項。重復2-4直到基本塊結束第十頁，共二十四頁，編輯于2023年，星期四x=10y=x+1;x=a;z=y+5;(ASSIG,10,-x)(ADDI,x,1,t1)(ASSIG,t1,-,y)(ASSIG,a,-,x)(ADDI,y,5,t2)(ASSIG,t2,-,z)ConDefx10t111y11t216z161116第十一頁，共二十四頁，編輯于2023年，星期四8.4公共表達式的局部優化等價四元式:兩個運算型四元式(1,A1,B1,t1)和(2,A2,B2,t2)，若1=2,A1和A2的值相同，B1和B2的值相同，則稱這兩個四元式等價公共表達式節省：當一個基本塊中出現多個等價四元式時，除第一個四元式以外，其他的均可節省。關鍵：判斷四元式等價方法：建立可用表達式表UsableExpr

建立值編碼表ValuNum(id,Vno)

建立臨時變量等價表PAIR:(ti,tj)第十二頁，共二十四頁，編輯于2023年，星期四在基本塊入口處，置ValuNum,UsableExpr,PAIR為空逐條掃描基本塊的中間代碼。對當前四元式tuple中運算分量進行等價替換(用PAIR替換)，設所得代碼為newtuple.如果newtuple是dj:(,A’,B’,tj)，進行如下操作：若A’是首次出現，則把(A’,NewVN)填入ValuNum;若B’是首次出現，則把(B’,NewVN)填入ValuNum;若存在di:(,A,B,ti)UsableExpr,使得dj代碼是di代碼的公共表達式，則刪除tuple,將(ti,tj)填入PAIR，同時(tj)=(ti);否則，把(tj,NewVN)填入ValuNum中，把dj加到UsableExpr中；如果newtuple是dj:(ASSIG,A’,-,B’)，進行如下操作：從UsableExpr中刪除含B’的所有可用表達式代碼；若A’是首次出現，則把(A’,NewVN)填入ValuNum； 令(B’)=(A’);第十三頁，共二十四頁，編輯于2023年，星期四1.(*,b,c,t1)2.(*,b,c,t2)3.(+,t1,t2,t3)4.(:=,t3,-,a)5.(:=,b,-,d)6.(*,d,c,t4)7.(*,b,c,t5)8.(+t4,t5,t6)9.(:=,t6,-,e)ValuNumUsableExprPAIR(b,1)(c,2)(t1,3)1(t2,t1)(t2,3)(t3,4)3(a,4)(d,1)(t4,3)(t4,t1)(t5,3)(t5,t1)(t6,4)(t6,t3)(e,4)t1t1t1t3第十四頁，共二十四頁，編輯于2023年，星期四8.5循環不變式外提優化思想:將值在循環里不發生改變的表達式運算提到循環外面進行i=1;whilei<1000doa[i]=x*y;i=1;t=x*y;whilei<1000doa[i]=t;關鍵：識別循環結構(循環入口，循環體，循環出口)判斷循環不變式判斷循環不變量方法：識別循環：(WHILE,-,-,-)–入口

(DO,e.form,-,-)–循環體開始

(ENDWHILE,-,-,-)–出口識別循環不變量：建立循環定義表LoopDef第十五頁，共二十四頁，編輯于2023年，星期四8.5循環不變式外提優化外提對象:除法運算不外提whileedo ify=0thenx=y; elsex=a/y;賦值不外提:(賦值操作的左部和右部都是循環不變式)外提策略：凡是循環不變式都外提只外提一定被執行的循環不變式第十六頁，共二十四頁，編輯于2023年，星期四8.5循環不變式外提優化生成中間代碼過程中構造本層循環的LoopDef;當結束一層循環的中間代碼時，做如下操作：掃描本層循環的一個中間代碼，設(,A,B,t)若不是可外提操作碼，則轉1掃描下一代碼；若是外提操作碼，則檢查A,B是否屬于本層LoopDef，若都不屬于，則轉4，否則轉1；若A和B都是本層循環不變量，則作：將(,A,B,t)外提到本層循環入口處；把t從本層LoopDef移到外層LoopDef.刪除原(,A,B,t)。重復1-4直到本層循環結束。第十七頁，共二十四頁，編輯于2023年，星期四i=1;whilei<=100dobeginz=i*k*5;a=2*k+2*k*2;i=i+1;end(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,t5)(ADDI,t4,t5,t6)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(ENDWHILE,-,-,-)第十八頁，共二十四頁，編輯于2023年，星期四(ASSIG,1,-i)(WHILE,-,-,-)(LE,i,100,t1)(DO,t1,-,-)(MULTI,i,k,t2)(MULTI,t2,5,t3)(ASSIG,t3,-,z)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(ENDWHILE,-,-,-)1……j-1jt1t2t3zt4t5t6at7i………………LoofDefi(ASSIG,1,-i)(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)(WHILE,-,-,-)(LE,i,100,t1)(DO,t1,-,-)(MULTI,i,k,t2)(MULTI,t2,5,t3)(ASSIG,t3,-,z)(ASSIG,t6,-,a)(ADDI,i,1,t7)(ASSIG,t7,-,i)(ENDWHILE,-,-,-)循環不變式外提應從最內層循環開始！(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)第十九頁，共二十四頁，編輯于2023年，星期四8.6其他各類優化介紹消減運算強度：用強度低的運算代替強度高的運算forj=1to100doa[j]=j*3+10m=13