第7章：代碼優(yōu)化

第7章代碼優(yōu)化詞法分析器語(yǔ)法分析器中間代碼生成器優(yōu)化段源程序單詞符號(hào)語(yǔ)法單位四元式表格管理出錯(cuò)處理目標(biāo)代碼生成器四元式目標(biāo)代碼

7.1

優(yōu)化概述優(yōu)化是一種等價(jià)的、有效的程序變換。優(yōu)化的目的是為了產(chǎn)生更高效的代碼。由優(yōu)化的編譯程序提供的對(duì)代碼的各種變換必須遵循下面的原則：等價(jià)原則：是指經(jīng)過(guò)優(yōu)化后不應(yīng)改變?cè)闯绦蜻\(yùn)行的結(jié)果。有效原則：經(jīng)優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時(shí)間較短，占用存儲(chǔ)空間較小。合算原則：應(yīng)盡可能以較低的代價(jià)取得較好的優(yōu)化效果。編譯前端代碼優(yōu)化器編譯后端控制流分析數(shù)據(jù)流分析代碼變換優(yōu)化技術(shù)分類(lèi)代碼優(yōu)化實(shí)際上是對(duì)代碼進(jìn)行等價(jià)變換，由一組代碼變成運(yùn)行結(jié)果相同的另一組代碼。源程序一級(jí)的優(yōu)化：對(duì)中間代碼的優(yōu)化，與機(jī)器無(wú)關(guān),面向各種語(yǔ)言.主要包括：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化目標(biāo)代碼的優(yōu)化：與具體機(jī)器有關(guān).主要包括對(duì)寄存器的優(yōu)化，多處理機(jī)的優(yōu)化、特殊指令的優(yōu)化等優(yōu)化技術(shù)分類(lèi)局部?jī)?yōu)化:程序中順序執(zhí)行的語(yǔ)句序列循環(huán)優(yōu)化:程序中循環(huán)語(yǔ)句的優(yōu)化全局優(yōu)化:整個(gè)程序范圍內(nèi)的優(yōu)化優(yōu)化的種類(lèi)：刪除多余運(yùn)算(或稱(chēng)刪除公用子表達(dá)式)代碼外提強(qiáng)度消弱變換循環(huán)控制條件合并已知量復(fù)寫(xiě)傳播刪除無(wú)用賦值中間代碼優(yōu)化舉例設(shè)Ａ、Ｂ為兩個(gè)一維數(shù)組，他們的初始地址分別為addr(A),addr(B),源程序段是S=0FOR(i=1,i<=20;i++)S=S+A[i]+B[i]假設(shè)機(jī)器按字節(jié)編制根據(jù)程序流向的特點(diǎn),分為B1,B2兩塊.B1是循環(huán)體外的語(yǔ)句,B2是可重復(fù)執(zhí)行的循環(huán)語(yǔ)句序列原則:通過(guò)等價(jià)變換,將盡量減少循環(huán)體中的語(yǔ)句,同時(shí)盡可能減少無(wú)實(shí)際意義的重復(fù)計(jì)算與賦值,盡可能降低機(jī)器運(yùn)算強(qiáng)度,運(yùn)算的級(jí)別.１．刪除公共子表達(dá)式(刪除多余運(yùn)算)公共子表達(dá)式是指在一個(gè)基本程序塊內(nèi)計(jì)算結(jié)果相同的子表達(dá)式．２．代碼外提是指把循環(huán)不變的運(yùn)算提到循環(huán)體前面優(yōu)化前的中間代碼經(jīng)刪除公共子表達(dá)式和代碼外提后的中間代碼3.降低運(yùn)算強(qiáng)度

主要指不改變運(yùn)算結(jié)果的前提下,將程序執(zhí)行時(shí)間長(zhǎng)的運(yùn)算替換成執(zhí)行時(shí)間短的運(yùn)算降低運(yùn)算級(jí)別經(jīng)強(qiáng)度削弱后的中間代碼4.變換循環(huán)控制變量(刪除歸納變量)如果在循環(huán)體內(nèi)存在一個(gè)變量(或臨時(shí)變量)T與循環(huán)控制變量i保持線(xiàn)性關(guān)系,同時(shí)在循環(huán)后面不引用I,而除去i又不影響程序運(yùn)行結(jié)果,則可由T取代循環(huán)控制變量變量I,這種方法稱(chēng)為變換循環(huán)控制變量(刪除歸納變量)5.合并已知量合并已知量是指若參加運(yùn)算的兩個(gè)對(duì)象在編譯時(shí)都是已知量,則可以在編譯時(shí)直接計(jì)算出它們的運(yùn)算結(jié)果6.復(fù)寫(xiě)傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值,也不影響其運(yùn)行結(jié)果的變量.經(jīng)變換循環(huán)控制變量,合并已知量,復(fù)寫(xiě)傳播后的中間代碼7,刪除無(wú)用賦值減少無(wú)用的變量,使代碼更簡(jiǎn)潔假(1)S=0(4)T2=addr(A)-4(7)T5=addr(B)-4(3)T1=4(5)T3=T2[T1](8)T6=T5[T1](9)T7=T3*T6(10)S=S+T7(3’)T1=T1+4(12)ifT1≤80goto(5)B2B1真經(jīng)刪除無(wú)用賦值后的中間代碼經(jīng)過(guò)優(yōu)化后,代碼具有以下特點(diǎn):(1)減少了循環(huán)體內(nèi)可執(zhí)行代碼:10條→6條(2)減少了乘法運(yùn)算次數(shù):3次→1次(3)減少了全程范圍內(nèi)使用的變量:i,T47.2 局部?jī)?yōu)化合并已知量：運(yùn)算對(duì)象是已知量，編譯時(shí)直接計(jì)算它們的值，而不必等到程序運(yùn)行時(shí)再計(jì)算。刪除公共子表達(dá)式：如果一個(gè)表達(dá)式E的值，前面已經(jīng)算過(guò)，并且在這之后E的值沒(méi)有改變，則E稱(chēng)為公共子表達(dá)式，則可以避免它的重復(fù)運(yùn)算，稱(chēng)為刪除公共子表達(dá)式。（刪除多余運(yùn)算）刪除無(wú)用賦值：如果一些變量的值在整個(gè)程序中不再被使用，則這些變量的賦值對(duì)程序的運(yùn)算結(jié)果沒(méi)有任何作用，則可以刪除對(duì)這些變量賦值的代碼，稱(chēng)為刪除無(wú)用賦值。

局部?jī)?yōu)化基本塊：一個(gè)基本塊是指程序中一順序執(zhí)行的語(yǔ)句序列。其中只有一個(gè)入口和一個(gè)出口，入口就是其中第一個(gè)語(yǔ)句，出口就是最后一條語(yǔ)句。對(duì)于一個(gè)基本塊來(lái)說(shuō)，執(zhí)行時(shí)只能從其入口進(jìn)入，從出口退出。局限于基本塊范圍內(nèi)的優(yōu)化稱(chēng)為基本塊內(nèi)的優(yōu)化，或稱(chēng)局部?jī)?yōu)化。劃分四元式程序?yàn)榛緣K的算法:1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。2.對(duì)以上求出的每個(gè)入口語(yǔ)句，確定其所屬的基本塊。它是由該入口語(yǔ)句到下一入口語(yǔ)句(不包括該入口語(yǔ)句)、或到一轉(zhuǎn)移語(yǔ)句(包括該轉(zhuǎn)移語(yǔ)句)、或一停語(yǔ)句(包括該停語(yǔ)句)之間的語(yǔ)句序列組成的。入口語(yǔ)句n……入口語(yǔ)句m入口語(yǔ)句n……轉(zhuǎn)移語(yǔ)句m入口語(yǔ)句n……停語(yǔ)句m3.凡未被納入某一基本塊中的語(yǔ)句，都是程序不可到達(dá)的語(yǔ)句,可以從程序中刪除。例：劃分基本塊(1) readX(2) readY(3) C:=XmodY(4) ifC=0goto(8)(5) X:=Y(6) Y:=C(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt1.求出四元式程序中各個(gè)基本塊的入口語(yǔ)句:1)程序第一個(gè)語(yǔ)句，或2)能由條件轉(zhuǎn)移語(yǔ)句或無(wú)條件轉(zhuǎn)移語(yǔ)句轉(zhuǎn)移到的語(yǔ)句，或3)緊跟在條件轉(zhuǎn)移語(yǔ)句后面的語(yǔ)句。例：劃分基本塊(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt2.對(duì)以上求出的每個(gè)入口語(yǔ)句，確定其所屬的基本塊。它是由該入口語(yǔ)句到下一入口語(yǔ)句(不包括該入口語(yǔ)句)、或到一轉(zhuǎn)移語(yǔ)句(包括該轉(zhuǎn)移語(yǔ)句)、或一停語(yǔ)句(包括該停語(yǔ)句)之間的語(yǔ)句序列組成的。

程序流圖:(8)writeY(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=XmodY(4)ifR=0goto(8)(1)readX(2)readYB1B2B3B4程序流圖以基本塊作為結(jié)點(diǎn)，控制程序流向作為有向弧，畫(huà)出的圖，稱(chēng)為程序流圖。流圖G=（N，E，n0）N：表示流圖的有限結(jié)點(diǎn)集合，每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)基本塊。E：流圖的有向邊集合；n0：表示唯一的首結(jié)點(diǎn)，包含程序第一個(gè)語(yǔ)句的基本塊。程序流圖每個(gè)流圖以基本塊為結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的基本塊的入口語(yǔ)句是程序的第一條語(yǔ)句，則稱(chēng)此結(jié)點(diǎn)為首結(jié)點(diǎn)。如果在某個(gè)執(zhí)行順序中，基本塊B2緊接在基本塊B1之后執(zhí)行，則從B1到B2有一條有向邊。即，如果有一個(gè)條件或無(wú)條件轉(zhuǎn)移語(yǔ)句從B1的最后一條語(yǔ)句轉(zhuǎn)移到B2的第一條語(yǔ)句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語(yǔ)句不是一個(gè)無(wú)條件轉(zhuǎn)移語(yǔ)句。我們就說(shuō)B1是B2的前驅(qū)，B2是B1的后繼。(1) readX(2) readY(3) R:=XmodY(4) ifR=0goto(8)(5) X:=Y(6) Y:=R(7) goto(3)(8) writeY(9) halt(8)writeY(9)halt(5)X:=Y(6)Y:=R(7)goto(3)(3)R:=XmodY(4)ifR=0goto(8)(1)readX(2)readYB1B2B3B4對(duì)下面的程序段劃分基本塊,構(gòu)造程序的控制流圖→(1)readc*/1(2)a:=0←(3)b:=1→(4)a:=a+b*/2←(5)ifb≥c

goto(10)→(6)b:=b+1*/3←(7)goto(4)(8)a:=a+1(9)b:=a+2→(10)writea*/4←(1)halt

基本塊劃分塊號(hào)bfirstbLastb

sucbpredb1(1)(3)2_2(4)(5)3、41、33(6)(7)224(10)(11)_2(1)readc1(2)a:=0(3)b:=1L1:(4)a:=a+b

2(5)ifb≥c

gotoL2(6)b:=b+13(7)gotoL1L2:(10)writeA4(11)halt

程序流圖:基本塊的DAG圖DAG(DirectedAcyclicGraph)是一種有向圖,常常用來(lái)對(duì)基本塊進(jìn)行優(yōu)化?；緣K中的語(yǔ)句的計(jì)算過(guò)程可以用一張圖表示出來(lái)，即一個(gè)基本塊可用一個(gè)DAG圖表示。

圖表示法圖表示法DAG抽象語(yǔ)法樹(shù)無(wú)循環(huán)有向圖(DirectedAcyclicGraph，簡(jiǎn)稱(chēng)DAG)對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)

a:=b*(-c)+b*(-c)的圖表示法

assigna+*buminuscDAGassigna+*buminusc抽象語(yǔ)法樹(shù)*buminusc抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象語(yǔ)法樹(shù)*buminuscDAG對(duì)應(yīng)的代碼：

T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5描述計(jì)算過(guò)程的DAG是一種帶有下述標(biāo)記或附加信息的DAG:n13.14n3n4Rrn5+T2,T4圖的葉結(jié)點(diǎn)以一標(biāo)識(shí)符或常數(shù)作為標(biāo)記，表示該結(jié)點(diǎn)代表該變量或常數(shù)的值;圖的內(nèi)部結(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所代表的值進(jìn)行運(yùn)算的結(jié)果;圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符(稱(chēng)附加標(biāo)識(shí)符)表示這些變量具有該結(jié)點(diǎn)所代表的值。借助DAG進(jìn)行優(yōu)化利用DAG來(lái)進(jìn)行優(yōu)化的主要思想：將一基本塊中的每一個(gè)四元式依次表示成對(duì)應(yīng)的一個(gè)DAG，再按原來(lái)構(gòu)造DAG結(jié)點(diǎn)的順序重寫(xiě)四元式序列，便可得到“合并已知常量”、“刪除無(wú)用賦值”、“刪除多余運(yùn)算”后的等價(jià)基本塊——優(yōu)化了的基本塊。

基本塊的DAG表示及應(yīng)用一個(gè)基本塊，可用一個(gè)DAG來(lái)表示與各四元式相對(duì)應(yīng)的DAG結(jié)點(diǎn)形式:四元式 DAG圖(0)0型:A:=B(:=，B，-，A)

n1AB四元式 DAG圖(1)1型:A:=opB(op，B，-，A)n1ABn2op(2)2型:A:=BopC(op，B，C，A)n2ABn1opn3C四元式 DAG圖(3)2型:A:=B[C]

(=[]，B[C]，-，A)n2ABn1=[]n3C(4)2型:ifBropCgoto(s)(jrop，B，C，(s))n2(s)Bn1ropn3C四元式 DAG圖(5)3型:D[C]:=B

([]=，B，-，D[C])(6)0型:goto(s)(j，-，-，(s))(s)n1n2Bn1[]=n4Cn3D例：賦值語(yǔ)句T4:=A+B-（E-（C+D））四元式序列G

T1:=A+B

T2:=C+D

T3:=E-T2

T4:=T1-T3

ABE

CDn9n3n8n1n2n7n6n4n5

T4

T1

T3

T2

+

-

-

+

DAG:例7.3 試構(gòu)造以下基本塊G的DAG(1) T0:=3.14(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8) T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6(1)T0:=3.14(1)T0:=3.14(2)T1:=2*T0(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(1)T0:=3.14(2)T1:=2*T0(3)T2:=R+r(4)A:=T1*T2(5)B:=A(6)T3:=2*T0(7)T4:=R+r(8)T5:=T3*T4(9)T6:=R-r(1) T0:=3.14n13.14T0n26.28T1n3n4Rrn5+T2n6*A,B,T3,T4,T5n7T6-n8*B(2) T1:=2*T0(3) T2:=R+r(4) A:=T1*T2(5) B:=A(6) T3:=2*T0(7) T4:=R+r(8)T5:=T3*T4(9) T6:=R-r(10) B:=T5*T6T6優(yōu)化