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

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

7.1

優(yōu)化概述優(yōu)化是一種等價的、有效的程序變換。優(yōu)化的目的是為了產(chǎn)生更高效的代碼。由優(yōu)化的編譯程序提供的對代碼的各種變換必須遵循下面的原則：等價原則：是指經(jīng)過優(yōu)化后不應(yīng)改變源程序運(yùn)行的結(jié)果。有效原則：經(jīng)優(yōu)化后所產(chǎn)生的目標(biāo)代碼運(yùn)行時間較短，占用存儲空間較小。合算原則：應(yīng)盡可能以較低的代價取得較好的優(yōu)化效果。編譯前端代碼優(yōu)化器編譯后端控制流分析數(shù)據(jù)流分析代碼變換優(yōu)化技術(shù)分類代碼優(yōu)化實(shí)際上是對代碼進(jìn)行等價變換，由一組代碼變成運(yùn)行結(jié)果相同的另一組代碼。源程序一級的優(yōu)化：對中間代碼的優(yōu)化，與機(jī)器無關(guān),面向各種語言.主要包括：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化目標(biāo)代碼的優(yōu)化：與具體機(jī)器有關(guān).主要包括對寄存器的優(yōu)化，多處理機(jī)的優(yōu)化、特殊指令的優(yōu)化等優(yōu)化技術(shù)分類局部優(yōu)化:程序中順序執(zhí)行的語句序列循環(huán)優(yōu)化:程序中循環(huán)語句的優(yōu)化全局優(yōu)化:整個程序范圍內(nèi)的優(yōu)化優(yōu)化的種類：刪除多余運(yùn)算(或稱刪除公用子表達(dá)式)代碼外提強(qiáng)度消弱變換循環(huán)控制條件合并已知量復(fù)寫傳播刪除無用賦值中間代碼優(yōu)化舉例設(shè)Ａ、Ｂ為兩個一維數(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)體外的語句,B2是可重復(fù)執(zhí)行的循環(huán)語句序列原則:通過等價變換,將盡量減少循環(huán)體中的語句,同時盡可能減少無實(shí)際意義的重復(fù)計(jì)算與賦值,盡可能降低機(jī)器運(yùn)算強(qiáng)度,運(yùn)算的級別.１．刪除公共子表達(dá)式(刪除多余運(yùn)算)公共子表達(dá)式是指在一個基本程序塊內(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í)行時間長的運(yùn)算替換成執(zhí)行時間短的運(yùn)算降低運(yùn)算級別經(jīng)強(qiáng)度削弱后的中間代碼4.變換循環(huán)控制變量(刪除歸納變量)如果在循環(huán)體內(nèi)存在一個變量(或臨時變量)T與循環(huán)控制變量i保持線性關(guān)系,同時在循環(huán)后面不引用I,而除去i又不影響程序運(yùn)行結(jié)果,則可由T取代循環(huán)控制變量變量I,這種方法稱為變換循環(huán)控制變量(刪除歸納變量)5.合并已知量合并已知量是指若參加運(yùn)算的兩個對象在編譯時都是已知量,則可以在編譯時直接計(jì)算出它們的運(yùn)算結(jié)果6.復(fù)寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值,也不影響其運(yùn)行結(jié)果的變量.經(jīng)變換循環(huán)控制變量,合并已知量,復(fù)寫傳播后的中間代碼7,刪除無用賦值減少無用的變量,使代碼更簡潔假(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)刪除無用賦值后的中間代碼經(jīng)過優(yōu)化后,代碼具有以下特點(diǎn):(1)減少了循環(huán)體內(nèi)可執(zhí)行代碼:10條→6條(2)減少了乘法運(yùn)算次數(shù):3次→1次(3)減少了全程范圍內(nèi)使用的變量:i,T47.2 局部優(yōu)化合并已知量：運(yùn)算對象是已知量，編譯時直接計(jì)算它們的值，而不必等到程序運(yùn)行時再計(jì)算。刪除公共子表達(dá)式：如果一個表達(dá)式E的值，前面已經(jīng)算過，并且在這之后E的值沒有改變，則E稱為公共子表達(dá)式，則可以避免它的重復(fù)運(yùn)算，稱為刪除公共子表達(dá)式。（刪除多余運(yùn)算）刪除無用賦值：如果一些變量的值在整個程序中不再被使用，則這些變量的賦值對程序的運(yùn)算結(jié)果沒有任何作用，則可以刪除對這些變量賦值的代碼，稱為刪除無用賦值。

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

程序流圖:(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)，控制程序流向作為有向弧，畫出的圖，稱為程序流圖。流圖G=（N，E，n0）N：表示流圖的有限結(jié)點(diǎn)集合，每一個結(jié)點(diǎn)對應(yīng)一個基本塊。E：流圖的有向邊集合；n0：表示唯一的首結(jié)點(diǎn)，包含程序第一個語句的基本塊。程序流圖每個流圖以基本塊為結(jié)點(diǎn)。如果一個結(jié)點(diǎn)的基本塊的入口語句是程序的第一條語句，則稱此結(jié)點(diǎn)為首結(jié)點(diǎn)。如果在某個執(zhí)行順序中，基本塊B2緊接在基本塊B1之后執(zhí)行，則從B1到B2有一條有向邊。即，如果有一個條件或無條件轉(zhuǎn)移語句從B1的最后一條語句轉(zhuǎn)移到B2的第一條語句；或者在程序的序列中，B2緊接在B1的后面，并且B1的最后一條語句不是一個無條件轉(zhuǎn)移語句。我們就說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對下面的程序段劃分基本塊,構(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

基本塊劃分塊號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)是一種有向圖,常常用來對基本塊進(jìn)行優(yōu)化。基本塊中的語句的計(jì)算過程可以用一張圖表示出來，即一個基本塊可用一個DAG圖表示。

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

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

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

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

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

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

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

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

基本塊的DAG表示及應(yīng)用一個基本塊，可用一個DAG來表示與各四元式相對應(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例：賦值語句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)化