課件演示文稿第十章

1、 什么是代碼優(yōu)化優(yōu)化技術(shù)簡(jiǎn)介第十章代碼優(yōu)化第十章代碼優(yōu)化某些編譯程序在中間代碼或目標(biāo)代碼生成之后要對(duì)生成的代碼進(jìn)行優(yōu)化。所謂優(yōu)化，實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加大或占用存儲(chǔ)空間少，或兩者都有。優(yōu)化可在編譯的不同階段進(jìn)行，對(duì)同一階段，涉及的程序范圍也不同，在同一范圍內(nèi)，可進(jìn)行多種優(yōu)化 優(yōu)化分類優(yōu)化分類: :按階段分按階段分與機(jī)器無(wú)關(guān)的優(yōu)化與機(jī)器無(wú)關(guān)的優(yōu)化 對(duì)中間代碼進(jìn)行對(duì)中間代碼進(jìn)行 依賴于機(jī)器的優(yōu)化依賴于機(jī)器的優(yōu)化 對(duì)目標(biāo)代碼進(jìn)行對(duì)目標(biāo)代碼進(jìn)行根據(jù)優(yōu)化所涉及的程序范圍分成:(1)局部?jī)?yōu)化:(基本塊)(2)循環(huán)優(yōu)化:對(duì)循環(huán)中的代碼進(jìn)行優(yōu)

2、化(3)全局優(yōu)化:大范圍的優(yōu)化優(yōu)化工作 數(shù)據(jù)流分析 控制流分析 優(yōu)化技術(shù)簡(jiǎn)介1.刪除多余運(yùn)算2.循環(huán)不變代碼外提3.強(qiáng)度削弱4.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播6.刪除無(wú)用賦值例：P:=0for :=1 to 20 do P:=P+A*B(1)P:=0(2):=1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)1.刪除多余運(yùn)算2.循環(huán)不變代碼外提(1)P:=0(2):=1(3)T1:=4*(4)

3、T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(1)P:=0(2):=1(3)T1:=4*(5)T3:=T2T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(4)T2:=addr(A)-4(7)T5:=addr(B)-4(6)T4:=T13.強(qiáng)度削弱(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:

4、=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(3)(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if =20 goto(5)(3)T1:=4*I(3)T1:=T1+44.變換循環(huán)控制條件5.合并已知量與復(fù)寫傳播(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T

5、1:=4*(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T4(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if =20 goto(5)(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1 (9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if T1 =80 goto(5)(3)T1:=46.刪除無(wú)用賦值(1)P:=0(2):=1(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)

6、T1:=4(5)T3:=T2T1(6)T4:=T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(11):=+1(3)T1:=T1+4(12)if T1=80 goto(5)(1)P:=0(4)T2:=addr(A)-4(7)T5:=addr(B)-4(3)T1:=4(5)T3:=T2T1(8)T6:=T5T1(9)T7:=T3*T6(10)P:=P+T7(3)T1:=T1+4(12)if T1=80 goto(5)局部?jī)?yōu)化：基本塊內(nèi)的優(yōu)化基本塊：是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句。入口語(yǔ)句：、程序的第一個(gè)語(yǔ)句；或者，、條件轉(zhuǎn)移語(yǔ)句或無(wú)條件

7、轉(zhuǎn)移語(yǔ)句的轉(zhuǎn)移目 標(biāo)語(yǔ)句；或者、緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。 劃分基本塊的算法：、求出四元式程序之中各個(gè)基本塊的入口語(yǔ) 句。、對(duì)每一入口語(yǔ)句，構(gòu)造其所屬的基本塊。 它是由該語(yǔ)句到下一入口語(yǔ)句（不包括下 一入口語(yǔ)句），或到一轉(zhuǎn)移語(yǔ)句（包括該 轉(zhuǎn)移語(yǔ)句），或到一停語(yǔ)句（包括該停語(yǔ) 句）之間的語(yǔ)句序列組成的。、凡未被納入某一基本塊的語(yǔ)句，都是程序 中控制流程無(wú)法到達(dá)的語(yǔ)句，因而也是不 會(huì)被執(zhí)行到的語(yǔ)句，我們可以把它們刪除。 (1)P:=0(2):=1B1(3)T1:=4*(4)T2:=addr(A)-4(5)T3:=T2T1(6)T4:=4*(7)T5:=addr(B)-4(8)T6:=T5T4

8、B2(9)T7:=T3*T6(10)P:=P+T7(11):=+1(12)if = C goto L2(6) B:=B+1(7) goto L1(8) L2: write (A)(9) halt基本塊的基本塊的DAG表示表示DAG Directed Acyclic Graph 無(wú)環(huán)路有向圖n1n2n3n4n1n2n3n5n4n6n7n8n9在一個(gè)有向圖中，我們稱任一有向邊ninj（或表示為有序?qū)Γ╪i,nj）中的結(jié)點(diǎn)ni為結(jié)點(diǎn)nj的前驅(qū)（父結(jié)），結(jié)點(diǎn)nj為結(jié)點(diǎn)ni的后繼（子結(jié)）。又稱任一有向邊序列n1n2, n2n3,nk1nk為從結(jié)點(diǎn)n1到結(jié)點(diǎn)nk的一條通路。如果其中n1=nk，則稱通路為環(huán)

9、路。該結(jié)點(diǎn)序列也記為（n1 ,n2,nk）。n1n2n3n4n1n2n3n5n4n6n7n8n9圖中有向圖的通路（n2 ,n2）和（n3 ,n4 ,n3）就是環(huán)路。如果有向圖中任一通路都不是環(huán)路，則稱該有向圖為無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。 有向圖就是一個(gè)DAG。在DAG中，如果（n1 ,n2, nk）是其中一條通路，則稱結(jié)點(diǎn)n1為結(jié)點(diǎn)nk的祖先，結(jié)點(diǎn)nk為結(jié)點(diǎn)n1的后代。我們這一節(jié)中要用到的有向圖，是一種其結(jié)點(diǎn)帶有標(biāo)記或附加信息的DAG： 1、圖的葉結(jié)點(diǎn)，即無(wú)后繼的結(jié)點(diǎn)，以一標(biāo)識(shí)符（變量名）或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值。如果葉結(jié)點(diǎn)用來(lái)代表某變量A的地址，則用addr（A）作為該

10、結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo)0，以表示它是該變量的初值。2、圖的內(nèi)部結(jié)點(diǎn)，即有后繼的結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果。3、圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。 上述這種DAG可用來(lái)描述計(jì)算過程，又稱描述計(jì)算過程的DAG。在以下的討論中，我們簡(jiǎn)稱DAG。一個(gè)基本塊，可用一個(gè)DAG來(lái)表示。下面列出各種四元式及相對(duì)應(yīng)的DAG的結(jié)點(diǎn)形式。1、圖中ni為結(jié)點(diǎn)編號(hào)2、結(jié)點(diǎn)下面的符號(hào)（運(yùn)算符、標(biāo)識(shí)符或常 數(shù)）是各結(jié)點(diǎn)的標(biāo)記3、各結(jié)點(diǎn)右邊的標(biāo)識(shí)符是結(jié)點(diǎn)的附加標(biāo)識(shí)符。 基本塊的基本塊的DAG表示與構(gòu)

11、造表示與構(gòu)造DAG結(jié)點(diǎn)結(jié)點(diǎn)n1 A B n2 A op n1 B四元式四元式0型：型：A:=B(:=,B,A) 1型型: A:=op B(op,B,A)2型型: A:=B op C(op, B, C,A) n3 Aop n1 n2B Cn1n2n1n3n1n2用DAG進(jìn)行基本塊的優(yōu)化僅含0，1，2型四元式的基本塊的DAG構(gòu)造算法:首先，DAG為空。對(duì)基本塊的每一四元式，依次執(zhí)行：DAG構(gòu)造算法構(gòu)造算法、如果NODE（B）無(wú)定義，則構(gòu)造一標(biāo)記為B的葉結(jié)點(diǎn)并定義NODE（B）為這個(gè)結(jié)點(diǎn)；如果當(dāng)前四元式是0型，則記NODE(B)的值為n，轉(zhuǎn)4。如果當(dāng)前四元式是1型，則轉(zhuǎn)2(1）。如果當(dāng)前四元式是2型

12、，則：()如果NODE(1)無(wú)定義，則構(gòu)造一標(biāo)記為C的葉結(jié)點(diǎn)并定義NODE(C) 為這個(gè)結(jié)點(diǎn)；() 轉(zhuǎn)2 .(2)。2、（1）如果NODE(B)是標(biāo)記為常數(shù)的葉結(jié)點(diǎn) ，則轉(zhuǎn)2(3)，否則轉(zhuǎn)3.（1）。（2）如果NODE(B)和NODE(C)都是標(biāo)記為常數(shù)的葉結(jié)點(diǎn)，則轉(zhuǎn)2.（4），否則轉(zhuǎn)3.（2）。（3）執(zhí)行op B（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)是處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4.。（4）執(zhí)行B op C（即合并已知量），令得到的新常數(shù)為P。如果NODE(B)或NODE(C)是

13、處理當(dāng)前四元式時(shí)新構(gòu)造出來(lái)的結(jié)點(diǎn)，則刪除它。如果NODE(P)無(wú)定義，則構(gòu)造一用P做標(biāo)記的葉結(jié)點(diǎn)n。置NODE(P)=n，轉(zhuǎn)4。3、（1）檢查DAG中是否已有一結(jié)點(diǎn)，其唯一 后 繼為NODE(B)，且標(biāo)記為op（即找公共子表 達(dá)式）。如果沒有，則構(gòu)造該結(jié)點(diǎn)n，否則就 把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè)該結(jié)點(diǎn)為n，轉(zhuǎn)4.（2）檢查中DAG中是否已有一結(jié)點(diǎn)，其左后繼 為NODE(B)，其右后繼為NODE(C)，且標(biāo)記為 op（即找公共子表達(dá)式）。如果沒有，則構(gòu)造該 結(jié)點(diǎn)n，否則就把已有的結(jié)點(diǎn)作為它的結(jié)點(diǎn)并設(shè) 該結(jié)點(diǎn)為n，轉(zhuǎn)4.。 4、 如果NODE（A）無(wú)定義，則把A附加在結(jié)點(diǎn)n上并令NODE（A）=

14、n；否則先把A從NODE（A）結(jié)點(diǎn)上的附加標(biāo)識(shí)符集中刪除（注意，如果NODE（A）是葉結(jié)點(diǎn)，則其標(biāo)記A不刪除），把A附加到新結(jié)點(diǎn)n上并令NODE（A）= n。轉(zhuǎn)處理下一四元式。 而后，我們可由DAG重新生成原基本塊的一優(yōu)化的代碼序列。 構(gòu)造以下基本塊構(gòu)造以下基本塊G的的DAG。 To 3.14 (a)n1T0:=3.14 T0 T1 3.14 6.28 (b)n2n1T0:=3.14T1:=2*T0 T2 + T0 T1 3.14 6.28 R r (c)n2n5n3n1n4T0:=3.14T1:=2*T0T2:=R+r A * T2 + T0 T1 3.14 6.28 R r (d)n2n5

15、n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2 A,B * T2 + T0 T1 3.14 6.28 R r (e)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=A A,B * T2 + T0 T1,T3 3.14 6.28 R r (f)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0 A,B * T2,T4 + T0 T1,T3 3.14 6.28 R r (g)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:

16、=AT3:=2*T0T4:=R+r A,B,T5 * T2,T4 + T0 T1,T3 3.14 6.28 R r (h)n2n5n3n1n4n6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rT0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6DAG的應(yīng)用我們將四元式表示成DAG后，可以利用DAG進(jìn)

17、行優(yōu)化首先由DAG構(gòu)造優(yōu)化的四元式序列在構(gòu)造相應(yīng)的DAG的過程中已經(jīng)進(jìn)行了一些基本的優(yōu)化工作而后，可由DAG重新生成原基本塊的一個(gè)優(yōu)化的代碼序列T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=6.28T3:=6.28T2:=R+rT4:=T2A:=6.28*T2T5:=AT6:=R-rB:=A*T6T0:=3.14T1:=2*T0T2:=R+rA:=T1*T2B:=AT3:=2*T0T4:=R+rT5:=T3*T4T6:=R-rB:=T5*T6優(yōu)化后：優(yōu)化后：例：賦值語(yǔ)句例：賦值語(yǔ)句 T

18、4:=A+B-(E-(C+D)四元式序列四元式序列GT1：=A+BT2：=C+DT3：=E-T2T4：=T1-T3DAG： A B E C Dn9n3n8n1n2n7n6n4n5 T4 T1 T3 T2 + - - + 控制流分析和循環(huán)優(yōu)化：控制流程圖（流圖）：具有唯一首結(jié)點(diǎn)的有向圖G=（N，E，n0） N：結(jié)點(diǎn)集 基本塊集 E：有向邊集 n0：首結(jié)點(diǎn) 包含程序第一個(gè)語(yǔ)句的基本塊分析程序流圖中結(jié)點(diǎn)間的關(guān)系m DOM n 定義（定義（必經(jīng)結(jié)點(diǎn)） 在程序流圖中,對(duì)任意兩個(gè)結(jié)點(diǎn)m和n,如果從流圖的首結(jié)點(diǎn)出發(fā),到達(dá)n的任意通路都要經(jīng)過m,則稱m是n的必經(jīng)結(jié)點(diǎn),記為m DOM n集集 定義定義 結(jié)點(diǎn)結(jié)點(diǎn)n的