第七章中間表示代碼與代碼優(yōu)化

7.1概況7.1.1代碼優(yōu)化與代碼優(yōu)化程序

?

代碼優(yōu)化的必要性假定有下列C語言語句序列：a=b+c*d;e=a+c*d;按第六章相應(yīng)翻譯方案將生成目標(biāo)代碼(左邊)如下：MOVc,R1cR1MOVc,R0cR0MPYd,R1c*dR1MPYd,R0c*dR0MOVb,R0bR0MOVR0,R1c*dR1ADDR1,R0b+c*dR0ADDb,R0b+c*dR0MOVR0,aR0aMOVR0,ab+c*da

MOVc,R1cR1ADDR0,R1a+c*dR1MPYd,R1c*dR1MOVR1,ea+c*deMOVa,R0aR0ADDR1R0a+c*dR0（手工生成）MOVR0,ea+c*de

試比較兩者的功效。又如，設(shè)有if語句

if(a+b>0)x=(a+b)*2;elsex=(a+b)/2;按第六章相應(yīng)翻譯方案將生成下列目標(biāo)代碼：(1)MOVa,R0 (10)MOVR2,x(2)ADDb,R0 (11)GOTO(17)(3)CMPR0,#0 (12)MOVa,R3(4)CJ>(6) (13)ADDb,R3(5)GOTO(12) (14)MOVR3,R4(6)MOVa,R1 (15)DIV#2,R4(7)ADDb,R1 (16)MOVR4,x(8)MOVR1,R2 (17)(9)MPY#2,R2如果用手工編寫，將會(huì)有如下的代碼：

(1)MOVa,R0 (5)MPY#2,R0(2)ADDb,R0 (6)GOTO(8)(3)CMPR0,#0 (7)DIV#2,R0(4)CJ≤(7) (8)MOVR0,x兩者相比，前者的目標(biāo)指令數(shù)多達(dá)16條，竟是后者的兩倍，且臨時(shí)變量（寄存器）5個(gè)。編譯程序只考慮共性，不能考慮個(gè)性，生成的目標(biāo)代碼必然是質(zhì)量不高的，?改進(jìn)程序的運(yùn)行效率的途徑通常有4種：改進(jìn)算法、利用系統(tǒng)提供的庫程序、源程序級(jí)程序變換、編譯時(shí)刻代碼優(yōu)化、這里，代碼優(yōu)化指的是：編譯時(shí)刻為改進(jìn)目標(biāo)程序的質(zhì)量而進(jìn)行的代碼優(yōu)化。

代碼優(yōu)化指的是編譯時(shí)刻為改進(jìn)目標(biāo)程序質(zhì)量而進(jìn)行的各項(xiàng)工作。目的是改進(jìn)目標(biāo)程序質(zhì)量，包括減少存儲(chǔ)空間與縮短運(yùn)行時(shí)間。

代碼優(yōu)化的思路是：在語義分析時(shí)僅生成中間表示代碼,對中間表示代碼進(jìn)行優(yōu)化，從優(yōu)化了的中間表示代碼生成目標(biāo)代碼，然后再對目標(biāo)代碼進(jìn)行小范圍的優(yōu)化，即，所謂的窺孔優(yōu)化。

編譯程序中完成代碼優(yōu)化工作的部分稱為代碼優(yōu)化程序。

代碼優(yōu)化程序的輸入是語義分析階段生成的某種中間表示代碼。代碼優(yōu)化程序的輸出是改進(jìn)了的中間表示代碼。

中間表示代碼的種類包括：四元式序列三元式序列抽象語法樹逆波蘭表示重點(diǎn)討論四元式序列。7.1.2代碼優(yōu)化的分類從下列三個(gè)角度分類。

1.與機(jī)器相關(guān)性

分為：與機(jī)器相關(guān)的和與機(jī)器無關(guān)的與機(jī)器相關(guān)的優(yōu)化一般有涉及寄存器的優(yōu)化、多處理器的優(yōu)化、特殊指令的優(yōu)化及消除無用指令的優(yōu)化等4類。

2.優(yōu)化范圍

分為：局部優(yōu)化和全局優(yōu)化對基本塊的優(yōu)化(局部優(yōu)化):

合并常量計(jì)算、消除公共子表達(dá)式、削減計(jì)算強(qiáng)度、刪除無用代碼

對循環(huán)的優(yōu)化(全局優(yōu)化)：

循環(huán)不變表達(dá)式外提、歸納變量刪除、計(jì)算強(qiáng)度削減。

3.優(yōu)化語言級(jí)

分為：內(nèi)部中間表示級(jí)和目標(biāo)代碼級(jí)通常代碼優(yōu)化是在中間表示代碼一級(jí)上進(jìn)行；在目標(biāo)代碼級(jí)上進(jìn)行的優(yōu)化特稱為窺孔優(yōu)化。控制流分析數(shù)據(jù)流分析代碼變換概括起來，本章討論的重點(diǎn)是在中間表示代碼級(jí)上的、與機(jī)器無關(guān)的局部優(yōu)化和全局優(yōu)化。代碼優(yōu)化程序通常由三個(gè)部分組成，即，控制流分析、數(shù)據(jù)流分析與代碼變換。示意圖如下所示。

控制流分析：基于流圖，識(shí)別出循環(huán)結(jié)構(gòu)。數(shù)據(jù)流分析：進(jìn)行數(shù)據(jù)流信息的收集

(包括到達(dá)_定值、活躍變量與可用表達(dá)式等)

代碼變換：對中間表示代碼進(jìn)行等價(jià)變換，完成對基本塊的局部優(yōu)化、與循環(huán)相關(guān)的優(yōu)化及全局優(yōu)化，最終完成代碼優(yōu)化。7.2源程序的中間表示代碼中間表示代碼可以是：抽象語法樹、逆波蘭表示、四元式序列、三元式序列。重點(diǎn)討論四元式序列。

7.2.1四元式序列

1.表示法約定四元式：運(yùn)算符運(yùn)算分量運(yùn)算分量結(jié)果例表達(dá)式x+y*z的四元式序列是：運(yùn)算符運(yùn)算分量運(yùn)算分量結(jié)果*

+yxzt1t1t2

對于雙目運(yùn)算xopy的四元式：

OPxyt

對于單目運(yùn)算OPx：

OPxt

對于賦值語句x=y：

:=yx與&:=yx(前者是通常的賦值，后者是間接賦值)

對于轉(zhuǎn)向語句gotoL：

GOLL

對于按關(guān)系運(yùn)算符relop：

relopxyL(xrelopy為真時(shí)控制轉(zhuǎn)向L為標(biāo)號(hào)的四元式)

對于無條件控制轉(zhuǎn)移到序號(hào)為L：

GOL對于函數(shù)調(diào)用語句p(x1,x2,…,xm)：

PARAMx1

PARAMx2

…

PARAM

xm

CALLpm若是函數(shù)有返回值,則呈下形：

CALLpmt其中，t中存放回送結(jié)果。關(guān)于一維數(shù)組元素A[i]的四元式表示。例A[j]=B[k+m]的四元式表示如下：(1)+kmt2(2)=[]Bt2t3(3)[]=Ajt1(4)&:=t3t1其中，=[]表示取數(shù)組元素值之操作，而，[]=表示取數(shù)組元素地址之操作。

一般情況下還需考慮到數(shù)組元素所占存儲(chǔ)區(qū)域的大小，相對于數(shù)組首址的位移量還需乘上數(shù)組元素所占存儲(chǔ)字節(jié)數(shù)。例如，假定都是整型數(shù)組，元素大小為2，將把上述四元式序列修改如下：

(1)

+kmt3(4)*j2t1(2)*t32t4(5)[]=At1t2(3)=[]Bt4t5(6)&:=t5t22.四元式序列之例例

設(shè)有字符數(shù)組S，包含n個(gè)字符，將其內(nèi)容置為逆序的C程序如下：

j=0;

while(j<n/2){c=S[j];S[j]=S[(n1)j];S[(n1)j]=c;j=j+1;}按目標(biāo)代碼生成的翻譯方案，該循環(huán)語句將展開成下列語句：

j=0;loop:if(j<n/2){c=S[j];S[j]=S[(n1)j];S[(n1)j]=c;j=j+1;

gotoloop;}

構(gòu)造四元式序列：從前面的展開式：

j=0;loop:if(j<n/2){c=S[j];S[j]=S[(n1)j];S[(n1)j]=c;j=j+1;

gotoloop;}數(shù)組元素為字符，僅占1個(gè)存儲(chǔ)字節(jié)，相應(yīng)的四元式序列如下：

(1)

:=0j(11)&:=t6t3(2)/n2t1(12)n1t7(3)<jt1(5)(13)t7jt8(4)GO(19)(14)[]=St8t9(5)=[]Sjt2(15)&:=ct9(6):=t2c(16)+j1t10(7)n1t4(17):=t10j(8)t4jt5(18)GO(2)(9)=[]St5t6(19)(10)[]=Sjt37.2.2.生成四元式序列之翻譯方案的設(shè)計(jì)

為程序設(shè)計(jì)語言語言成分生成四元式序列之翻譯方案的設(shè)計(jì)，其思路與生成目標(biāo)代碼是一樣的，即，先確定語言成分與四元式序列的對應(yīng)關(guān)系，然后對照對應(yīng)關(guān)系來設(shè)計(jì)翻譯方案。以賦值語句文法G[A]:A::=id=EE::=E+E|E*E|E|(E)|id為例說明。生成賦值語句四元式序列的翻譯方案可如下設(shè)計(jì)，例如:

對于重寫規(guī)則E::=E+E，簡單地生成四元式：

+E左.placeE右.placeE.place為左部變量E引進(jìn)臨時(shí)變量作為E.place。因此可以有

E.place:=newtemp；newtemp表示當(dāng)前下一個(gè)臨時(shí)變量，而E左與E右是加法運(yùn)算的左右運(yùn)算分量。對于A::=id=E，簡單地生成四元式：

:=E.place

id.place其中,id.place需從符號(hào)表相應(yīng)條目中取到，因此有：

p:=lookup();id.place就是p→place。類似地考慮其他重寫規(guī)則的情況。

這時(shí)有兩種存儲(chǔ)四元式序列的方式，一種方式是把四元式序列作為屬性存儲(chǔ)，類似于E.code，引進(jìn)E.quad（四元式Quadruple)，這時(shí)引進(jìn)函數(shù)genquad，由函數(shù)調(diào)用genquad(op,x,y,z)來生成四元式：opxyz

另一種方式是立即輸出四元式，即引進(jìn)函數(shù)emitquad，由函數(shù)調(diào)用emitquad(op,x,y,z)輸出四元式:opxyz。文法G[A]的翻譯方案如下。

A::=id=E{p:=lookup();

emitquad(":=",E.place,"",p→place)}E::=E1+E2{E.place:=newtemp;

emitquad("+",E1.place,E2.place,E.place)}E::=E1*E2{E.place:=newtemp;

emitquad("*",E1.place,E2.place,E.place)}E::=E1{E.place:=newtemp;

emitquad("",E1.place,"",E.place)}E::=(E1){E.place:=E1.place}E::=id{p:=lookup();E.place:=p→place)}進(jìn)一步可為if語句設(shè)計(jì)實(shí)現(xiàn)回填的生成四元式序列的翻譯方案。

例

基于相應(yīng)的翻譯方案，可為下列if語句：

if(a>b&&c<d||e==f)x=m;elsex=n;生成下列四元式序列：

(1)>ab(3) (6)GO(9)(2)GO(5)(7):=mx(3)<cd(7) (8)GO_(4)GO(5) (9):=nx(5):=ef(7)

注意:將由外圍控制結(jié)構(gòu)進(jìn)行回填，把下一四元式序號(hào)nextpos+1=10回填入四元式(8)中。

7.2.3從四元式序列生成目標(biāo)代碼假定對于四元式的一切運(yùn)算符都有對應(yīng)的目標(biāo)機(jī)器操作碼，且寄存器個(gè)數(shù)無限制，從四元式序列生成目標(biāo)代碼的工作是容易實(shí)現(xiàn)的。重點(diǎn)關(guān)注的是運(yùn)算分量與計(jì)算結(jié)果的存取問題。核心是寄存器的使用，因?yàn)檫\(yùn)算分量是否在寄存器中，以后是否還會(huì)被使用等，對目標(biāo)指令的生成有一定的影響。代碼生成算法引進(jìn)寄存器描述符與地址描述符引進(jìn)函數(shù)GetRegister引進(jìn)簡單的代碼生成算法，它僅對基本塊生成目標(biāo)代碼。1.基本塊基本塊：連續(xù)的四元式序列，控制從其第一個(gè)四元式進(jìn)入，從其最后一個(gè)四元式離開，其中沒有停止，也不包含分支。基本塊的劃分：從一個(gè)入口四元式到下一個(gè)入口四元式之前或到出口四元式為止的一切四元式構(gòu)成一個(gè)基本塊。

入口四元式：有三類,即,

第一個(gè)四元式條件轉(zhuǎn)移或無條件轉(zhuǎn)移四元式轉(zhuǎn)移到的四元式緊隨條件轉(zhuǎn)移或無條件轉(zhuǎn)移四元式之后的四元式2.目標(biāo)代碼生成算法

重點(diǎn)是運(yùn)算分量與計(jì)算結(jié)果的存取，核心是寄存器的使用。為簡單起見，可以假定寄存器個(gè)數(shù)沒有限制，且在生成目標(biāo)指令時(shí)，盡可能使用寄存器，且盡可能長時(shí)間把計(jì)算結(jié)果保留在寄存器中，這樣將有利于功效的提高。

引進(jìn)寄存器描述符與地址描述符寄存器描述符：用來記錄每個(gè)寄存器當(dāng)前保存的是什么變量的值。地址描述符：用來記錄每個(gè)變量的當(dāng)前值存放在什么地方。四元式生成的代碼寄存器描述符地址描述符－abt1

－act2*t1

t2

t3

+t3t2t4:=t4

xMOVa,R0SUBb,R0MOVa,R1SUBc,R1MPYR1,R0ADDR1,R0MOVR0,x

R0包含t1R0包含t1R1包含t2R0包含t3R1包含t2R0包含t4R0包含x、t4t1在R0中t1在R0中t2在R1中t2在R1中t3在R0中t4在R0中x在R0和內(nèi)存單元中t4在R0中例賦值語句

x=a/(b+c)d;的四元式序列、目標(biāo)代碼及寄存器描述符與地址描述符。

簡單目標(biāo)代碼生成算法。輸入：構(gòu)成一個(gè)基本塊的四元式序列輸出：相應(yīng)的目標(biāo)代碼對每個(gè)四元式opxyz完成下列步驟：步驟1.調(diào)用函數(shù)GetRegister,確定存放xopy之計(jì)算結(jié)果z的處所L。其中，L通常是寄存器，也可能是內(nèi)存單元。步驟2.查看地址描述符，確定x值當(dāng)前的一個(gè)存放處所x′。

若x當(dāng)前值既在內(nèi)存單元中又在寄存器中,則選擇寄存器作為x′。

若x的值并不在由步驟1確定的L中，生成指令

MOVx′,L把x的值傳送到L。步驟3.生成目標(biāo)指令opy′,L,其中y′是y當(dāng)前值所在處所之一。

同樣盡可能選寄存器。

修改地址描述符，指明z之值存放在處所L。當(dāng)L是寄存器時(shí)，同時(shí)修改寄存器描述符，指明該寄存器L包含z的值。步驟4.如果x和/或y的當(dāng)前值在寄存器中，并且之后不再被引用

，甚至在基本塊的最后一個(gè)四元式之后也如此，則修改寄存器描述符，指明在執(zhí)行該四元式opxyz后，這些寄存器不再包含x和/或y的值。在基本塊的出口四元式之后是否還引用該基本塊內(nèi)的變量是無法確定的，必須結(jié)合數(shù)據(jù)流分析，因此假定基本塊中用戶定義的一切變量在該基本塊出口四元式之后還要被引用。對于值不在存儲(chǔ)字中，而僅在寄存器中的，必須用MOV指令把它們保存在存儲(chǔ)字中。

單目運(yùn)算四元式，opxz，這與上述算法步驟類似。至于賦值四元式:=xy，在生成目標(biāo)代碼時(shí)，注意不要生成MOVx,y這樣的目標(biāo)指令，其中x與y之值都在存儲(chǔ)字中。關(guān)于關(guān)系運(yùn)算符四元式與控制轉(zhuǎn)移四元式等，及其他各類四元式，不難實(shí)現(xiàn)目標(biāo)指令的生成，要點(diǎn)是確定標(biāo)號(hào)與四元式序號(hào)所相應(yīng)的目標(biāo)指令位置，應(yīng)用回填技術(shù)，引進(jìn)轉(zhuǎn)移指令表進(jìn)行回填。

3.關(guān)于數(shù)組元素之四元式的目標(biāo)代碼

設(shè)有賦值語句x=A[k]；與B[j]=y；相應(yīng)四元式分別為：

=[]Akt(1):=tx(2)與

[]=Bjt(3)&:=yt(4)當(dāng)k與j分別在寄存器Rk中與Rj時(shí)，為(1)與(2)可生成目標(biāo)指令

MOVA(Rk),R與ADDRB(Rj),R(5)MOVR,xMOVy,*R(6)當(dāng)y在寄存器Ry中時(shí)，對(5)與(6)可生成：

MOVRy,B(Rk)概括

1.概況

1)中間表示代碼引進(jìn)的目的

2)中間表示代碼的種類

2.四元式序列

1)表示法約定

2)生成四元式序列的翻譯方案之設(shè)計(jì)

3)從四元式序列生成目標(biāo)代碼

4)相關(guān)概念：基本塊

(1)

=[]

A

1

(8)GOF(11)

(7)

(2)

:=

(1)

max

(9)=[]

A

i

(3)

:=

2

i(10):=

(9)max

(4)

≤

i

n(11)

+

i

1

(5)GOF

(14)

(4)(12)

:=

(11)

i

(6)

=[]

A

i(13)

GO

(4)

(7)＞

(6)

max(14)7.2.4*

其他的中間表示代碼

1.三元式序列

三元式：運(yùn)算符運(yùn)算分量運(yùn)算分量例max=A[1];i=2;loop:if(i<=n){if(A[i]>max)max=A[i];i=i+1;gotoloop;}

可為下列if語句：

if(a>b&&c<d||e==f)x=m;elsex=n;生成下列三元式序列：

(1)>ab (7)GOF(10)(6)(2)GOF(6)(1) (8):=mx(3)<cd (9)GO(11)(4)GOF(6)(3)(10):=nx(5)GO(8) (11)(6)=e

f可見三元式與四元式在表示法上的區(qū)別主要是兩點(diǎn)：

?運(yùn)算分量位置上可以出現(xiàn)三元式序號(hào)。

?有按假轉(zhuǎn)控制轉(zhuǎn)移三元式GOF，當(dāng)?shù)诙€(gè)運(yùn)算分量的值為false時(shí)，控制轉(zhuǎn)向由第一個(gè)運(yùn)算分量指明的三元式。

可以類似于四元式序列，設(shè)計(jì)生成三元式序列的翻譯方案，并從三元式序列生成目標(biāo)代碼。

2.*

逆波蘭表示(1)概念逆波蘭表示又稱后綴表示法，特點(diǎn)是無括號(hào)。例a+b*c/(d+e)其逆波蘭表示：abc*de+/+

逆波蘭表示之定義：1)若E是變量或常量，E的逆波蘭表示是E本身；2)若E形如E1OPE2，

則E的逆波蘭表示是

E1′E2′OP3)若E是形如(E1)的表達(dá)式，則E的逆波蘭表示與E1的相同。(2)從表達(dá)式到其他結(jié)構(gòu)的擴(kuò)充1)到賦值語句V=e的擴(kuò)充:V′e′=

例t=(a+b)*c/(d－e)tab+c*de－/=A[i]=B[j+k][m]Ai[]Bjk+[]m[]=2)到條件語句if(e)StelseSf的擴(kuò)充：

e'N1GOFSt'N2GOSf'例if(a＜b)max=b;elsemax=a;的逆波蘭表示:

ab＜11GOFmaxb=14GOmaxa=3)到轉(zhuǎn)向語句gotoN的擴(kuò)充：NGOL4)到復(fù)合語句{S1S2}的擴(kuò)充：S1'S2'5)到while(E)S的的擴(kuò)充：E'N'GOFS'1GO例while(i<=10){b=f;f=f+a;a=b;}的逆波蘭表示：

i10<=19GOFbf=ffa+=ab=1GO對于do-while語句doSwhile(E)？對于for循環(huán)語句for(V=E1;E2;E3)S？

分程序復(fù)合語句{S1；S2}的逆波蘭表示是：

BLOCKS1′S2′BLOCKEND

例分程序復(fù)合語句

{inti;i=1;f=1;a=0;AGAIN:if(i＜10){b=f;f=f+a;a=b;i=i+1;gotoAGAIN;}fib=f;}

逆波蘭表示：

BLOCKi1=f1=a0=AGAIN:i10＜36GOFbf=

ffa+=ab=ii1+=AGAINGOLfibf=BLOCKEND(3)逆波蘭表示的生成按定義逐次找最低優(yōu)先級(jí)運(yùn)算符、利用抽象語法樹、結(jié)合語法分析技術(shù)、利用翻譯方案1)結(jié)合語法分析技術(shù)

?算符優(yōu)先分析技術(shù)—引進(jìn)運(yùn)算符棧

?遞歸下降分析技術(shù)

2)通常引進(jìn)運(yùn)算符棧，利用它，從中綴表達(dá)式生成逆波蘭表示。這過程大致如下。初始時(shí)，把左端標(biāo)志符號(hào)#下推入運(yùn)算符棧，#看作優(yōu)先級(jí)最低的運(yùn)算符。從左到右掃描中綴表達(dá)式，當(dāng)是運(yùn)算分量時(shí)，直接輸出，當(dāng)是運(yùn)算符時(shí)，把它與運(yùn)算符棧頂?shù)倪\(yùn)算符進(jìn)行優(yōu)先級(jí)比較。如果當(dāng)前運(yùn)算符優(yōu)先級(jí)高，把它下推入運(yùn)算符棧，如果運(yùn)算符棧頂運(yùn)算符的優(yōu)先級(jí)高，則把運(yùn)算符從運(yùn)算符棧退去，并輸出。繼續(xù)把當(dāng)前運(yùn)算符與運(yùn)算符棧頂運(yùn)算符比較優(yōu)先級(jí)，直到當(dāng)前運(yùn)算符優(yōu)先級(jí)高，把它下推入運(yùn)算符棧。如此繼續(xù)，直到掃描完整個(gè)中綴表達(dá)式。這時(shí)整個(gè)輸出便是所求的逆波蘭表示。4)生成逆波蘭表示之翻譯方案逆波蘭表示生成的翻譯方案：

?自頂向下方式

E∷=TRR∷=addopT{print(addop.lexeme)}R|εT∷=num{print(num.lexval)}?自底向上方式

E∷=E1+T{print(+)}E∷=TT∷=T1*F{print(*)}T∷=FF∷=（E）

F∷=id{print（）}5)從逆波蘭表示生成目標(biāo)代碼算符優(yōu)先分析技術(shù),設(shè)立運(yùn)算分量棧與運(yùn)算符棧例

從逆波蘭表示

ab＜11GOFmaxb=14GOmaxa=

生成目標(biāo)代碼:MOVa,R0CMPR0,bCJ＜*+8GOTO_MOVb,R1MOVR1，maxGOTO_MOVa,R2MOVR2，max如何從逆波蘭表示復(fù)原到通常的中綴表示法？

例

從逆波蘭表示

abc+*

生成:MOVb,R0ADDc,R0MOVa,R1MPYR0，R1從逆波蘭表示生成目標(biāo)代碼。基本處理思想如下：設(shè)置一個(gè)運(yùn)算分量棧，用來存放還不能生成目標(biāo)指令的運(yùn)算分量。初始時(shí)，運(yùn)算分量棧為空。然后從左到右逐個(gè)符號(hào)地掃描逆波蘭表示，是運(yùn)算分量，把它下推入運(yùn)算分量棧，是運(yùn)算符，則根據(jù)運(yùn)算符是幾目運(yùn)算符，從運(yùn)算分量棧取出相應(yīng)個(gè)數(shù)的運(yùn)算分量,生成目標(biāo)指令，這時(shí)把所取運(yùn)算分量從運(yùn)算分量棧退去，并把存放相應(yīng)運(yùn)算結(jié)果的寄存器下推入運(yùn)算分量棧，再繼續(xù)掃描逆波蘭表示。直到處理完整個(gè)逆波蘭表示。對于上述逆波蘭表示生成目標(biāo)指令的過程如下圖所示。

運(yùn)算分量棧:6cR0bbR1deaaaR2R3R4xxxxxx(a)(b)(c)(d)(e)(f)生成目標(biāo)指令：

-

時(shí)*時(shí)+時(shí)/時(shí)+時(shí)=時(shí)MOVc,R0MOVb,R1MOVa,R2MOVR2,R3MOVR3,R4MOVR4,xSUB#6,R0MPYR0,R1ADDR1,R2DIVd,R3ADDe,R4把運(yùn)算分量棧與運(yùn)算符棧結(jié)合起來，可以從中綴表達(dá)式直接生成目標(biāo)指令。這實(shí)質(zhì)上是算符優(yōu)先分析技術(shù)的應(yīng)用。

3.*

抽象語法樹

(1)抽象語法一切規(guī)則中棄去非本質(zhì)部分而得到的規(guī)則之集合對于條件語句與賦值語句的抽象語法規(guī)則：條件語句表達(dá)式語句語句賦值語句左部表達(dá)式(2)抽象語法樹語法分析樹抽象語法樹重寫規(guī)則語義規(guī)則

S∷=id=E

E∷=E1+TE∷=TT∷=T1*FT∷=FF∷=(E)F∷=idF∷=numS.nptr:=mknode("assign",mkleaf(id,id.entry),E.nptr)E.nptr:=mknode("+",E1.nptr,T.nptr)E.nptr:=T.nptrT.nptr:=mknode("*",T1.nptr,F.nptr)T.nptr:=F.nptrF.nptr:=E.nptrF.nptr:=mkleaf(id,id.entry)F.nptr:=mkleaf2(num,num.lexval)(3)產(chǎn)生抽象語法樹的語法制導(dǎo)定義其中，mknode(op,left,right)建立一結(jié)點(diǎn),并回送該結(jié)點(diǎn)的指針mkleaf(id,entry)為id建立標(biāo)識(shí)符(葉)結(jié)點(diǎn),回送結(jié)點(diǎn)指針mkleaf2(num,val)與mkleaf(id,entry)類似，為num建立數(shù)結(jié)點(diǎn)7.3

基本塊的代碼優(yōu)化

7.3

.1基本塊優(yōu)化的種類

基本塊優(yōu)化的種類

?合并常量計(jì)算

?消除公共子表達(dá)式

?削減計(jì)算強(qiáng)度

?刪除無用代碼

1.合并常量計(jì)算運(yùn)行時(shí)刻的常量運(yùn)算，在編譯時(shí)刻計(jì)算好值。

CONSTpi=3.1416；

l=2*pi*r;四元式序列：(1)*23.1416t1或(1)*2pit1(2)*t1rt2(2)*t1rt2(3):=t2l(3):=t2l經(jīng)合并常量計(jì)算后將優(yōu)化為:(1)*6.2832rt2(2):=t2l2.消除公共子表達(dá)式

?

概念：一個(gè)表達(dá)式，在先前已計(jì)算過，且計(jì)算以后該表達(dá)式中涉及的變量之值均未被改變，則這次出現(xiàn)稱為公共子表達(dá)式。

?公共子表達(dá)式無需重復(fù)計(jì)算值。

基本塊：＋bca

－adb

＋bcc

－add改變?yōu)椋?=bd例x+y*t－a*(x+y*t)/(y*t)例對x+y*t－a*(x+y*t)/(y*t)消除公共子表達(dá)式優(yōu)化前：優(yōu)化后：(1)*ytt1(1)*ytt1(2)+xt1t2(2)+xt1t2(3)*ytt3(3)*at2t5(4)+xt3t4(4)/t5t1t7(5)*at4t5(5)－

t2t7t8(6)*ytt6(7)/t5t6t7

－

t2t7t8

請注意公共子表達(dá)式必須是第二次或以后的出現(xiàn)，且其中的變量都不被改變值。3.削減計(jì)算強(qiáng)度削減計(jì)算強(qiáng)度：由編譯程序用運(yùn)算速度較快的計(jì)算代替運(yùn)算速度較慢的計(jì)算之優(yōu)化。幾種典型的情況是：

·用x*x代替x**2，**是乘冪運(yùn)算符

·用x+x代替2*x·用x*0.5代替x/2·用移位代替2的冪次之計(jì)算問:y=anxn+an-1xn－1+…+a1x+a0，按下式計(jì)算

y=((…((anx+an-1)x+an-2)…)x+a1)x+a0

(霍納方案)是否是計(jì)算強(qiáng)度削減？答：否

4.刪除無用代碼無用代碼：計(jì)算的值決不被引用的四元式復(fù)寫傳播：當(dāng)消去公共子表達(dá)式時(shí)，引進(jìn)如下的賦值四元式，如：(3′):=t1t3，稱這種賦值為復(fù)寫。對公共子表達(dá)式值t3的一切引用，都代之以對t1的引用，稱復(fù)寫傳播。這時(shí)顯然這賦值四元式成為無用代碼。7.3.2基本塊優(yōu)化的實(shí)現(xiàn)引進(jìn)所謂的無環(huán)路有向圖(DirectedAcyclicGraphic),簡稱dag。引進(jìn)的目的是消除公共子表達(dá)式。

1.基本塊之dag的構(gòu)造法基于dag進(jìn)行基本塊的優(yōu)化。

dag是為基本塊四元式序列構(gòu)造的無環(huán)路有向圖。

dag中兩類結(jié)點(diǎn)：

?葉結(jié)點(diǎn)：常量、初值

用本身標(biāo)記，可以有附加標(biāo)識(shí)符表

?內(nèi)結(jié)點(diǎn)：用運(yùn)算符標(biāo)記，可以有附加標(biāo)識(shí)符表

dag作用：

?

確定基本塊中的公共子表達(dá)式

?確定哪些名字在基本塊中引用但在塊外計(jì)算

?確定基本塊中哪些四元式計(jì)算的值可在塊外引用結(jié)點(diǎn)序號(hào)標(biāo)記左子結(jié)點(diǎn)右子結(jié)點(diǎn)附加標(biāo)識(shí)符鏈1a2b3+124d5346+15例DAG之例

基本塊

+abc-cdb

+abe-cdf使用dag為什么能進(jìn)行消除公共子表達(dá)式的優(yōu)化？

6+e5-b,f

3+c4d0

1a0

2b0

(a)

c^

b

f^

e^(b)例設(shè)有表達(dá)式x+y*z+2*(x+y*z)/(y*z)，試為其相應(yīng)四元式序列構(gòu)造dag。該表達(dá)式的相應(yīng)四元式序列如下。⑴

*

yzt1⑸

*2t4t5⑵+xt1t2⑹

*yzt6⑶

*yzt3⑺/t5t6t7⑷+xt3t4⑻+t2t7t8這是一個(gè)基本塊，可為其構(gòu)造dag如下圖所示。^

9+t88/t7

7*t5

625+t2,t4

3*t1,t3,t64z0

1x0

2y0

(a)t2

t4

^t1

t3

t6

^t5

^t7^t8^1y0

^2z0

3*12

4x0

^5+43

62

7*65

8/73

9+58

^^(b)例內(nèi)積計(jì)算程序prod=0;i=1；do{prod=prod+a[i]*b[i];每個(gè)數(shù)組元素占用一個(gè)字，

i=i+1;即4個(gè)字節(jié)}while(i<=20);相應(yīng)四元式序列如下。(1):=

0prod(7)*

t2

t4

t5(2):=

1

i(8)

+prod

t5

t6(3)*

4

i

t1(9)

:=

t6prod(4)=[]

a

t1

t2(10)

+

i

1

t7(5)*

4

i

t3(11)

:=

t7

i(6)=[]

b

t3

t4(12)

≤

i

20(3)每個(gè)數(shù)組元素占用一個(gè)字，即4個(gè)字節(jié)(1):=

0prod(7)

*

t2

t4

t5(2):=

1

i(8)

+prod

t5

t6(3)

*

4

i

t1(9):=

t6prod(4)=[]

at1

t2(10)

+

i

1

t7(5)

*

4

i

t3(11):=

t7

i(6)=[]

bt3

t4(12)≤

i

20(3)2.從dag重建四元式序列根據(jù)不同類型的結(jié)點(diǎn)，生成相應(yīng)的四元式。要點(diǎn)：記住結(jié)點(diǎn)的生成次序(利用結(jié)點(diǎn)信息表)

依照dag中結(jié)點(diǎn)生成的順序，依次逐個(gè)結(jié)點(diǎn)地分析，還原成四元式序列。1)若是葉結(jié)點(diǎn),且附加標(biāo)識(shí)符表為空,則不生成四元式；2)若是葉結(jié)點(diǎn)，標(biāo)記為x，且附加的標(biāo)識(shí)符為z，則生成賦值四元式:=xz；3)若是內(nèi)結(jié)點(diǎn)，附加標(biāo)識(shí)符是z，則根據(jù)其標(biāo)記op及子結(jié)點(diǎn)個(gè)數(shù)生成相應(yīng)的四元式。

3)若是內(nèi)部結(jié)點(diǎn)，附加標(biāo)識(shí)符是z，則根據(jù)其標(biāo)記op及子結(jié)點(diǎn)個(gè)數(shù)生成相應(yīng)的四元式。

?標(biāo)記op不是=[]或[]=，也不是relop，有葉結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)作為其左右子結(jié)點(diǎn)，則生成下列四元式：

opxyz?標(biāo)記op是=[]或[]=，則生成下列四元式：

=[]xyz

或

[]=xyz?標(biāo)記op是relop，則生成下列四元式：

relopxyz

其中z是四元式序號(hào)。可能原有四元式序號(hào)已被改變，此四元式序號(hào)應(yīng)相應(yīng)變化。

?若內(nèi)部結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)，則生成下列四元式：

opxz

4)若是內(nèi)部結(jié)點(diǎn)，但無附加標(biāo)識(shí)符，則為該結(jié)點(diǎn)添加一個(gè)局部于本基本塊的臨時(shí)性附加標(biāo)識(shí)符，然后按步驟3）生成相應(yīng)四元式。

5）結(jié)點(diǎn)的附加標(biāo)識(shí)符表中包含多個(gè)標(biāo)識(shí)符z1、z2、…、zm時(shí)，

?若結(jié)點(diǎn)是葉結(jié)點(diǎn),標(biāo)記是z,則生成一列賦值四元式::=zz1:=zz2…:=zzm?若結(jié)點(diǎn)是內(nèi)部結(jié)點(diǎn)，附加標(biāo)識(shí)符表中第一個(gè)標(biāo)識(shí)符是z1，則生成一列賦值四元式：

:=z1z2:=z1z3…:=z1

zm例利用dag對表達(dá)式

x+y*z+2*(x+y*z)/(y*z)進(jìn)行優(yōu)化。該表達(dá)式的相應(yīng)四元式序列如下。⑴*

yzt1⑸*2t4t5⑵+xt1t2⑹*yzt6⑶*yzt3⑺/t5t6t7⑷+xt3t4⑻+t2t7t81

y0

^2

z0

^3

*124

x0

^5+436

2

^7

*658/739+58

+t8

/t7

*t5

+t2,t4

*t1,t3,t52x0y0z0

dag

t1

t3

t6^t2t4^t5^t7^t8^結(jié)點(diǎn)信息表當(dāng)應(yīng)用上述步驟于上例中生成的dag，可重建如下四元式序列：⑴*yzt1⑸:=t2t4⑵:=t1t3⑹*2t2t5⑶:=t1t6⑺/t5t1t7⑷+xt1t2⑻+t2t7t8可刪除四元式(2)、(3)與(5)。還可以進(jìn)行什么優(yōu)化？3.應(yīng)用dag于基本塊的其他優(yōu)化在dag的應(yīng)用中強(qiáng)調(diào)了公共子表達(dá)式的消除，它也可應(yīng)用于：

合并常量計(jì)算計(jì)算強(qiáng)度削減刪除無用代碼還可以獲得可用于全局優(yōu)化的下列信息：

·本基本塊內(nèi)引用其值的標(biāo)識(shí)符

·在本基本塊外能引用它所計(jì)算之值的四元式

dag確實(shí)是實(shí)現(xiàn)基本塊優(yōu)化的有效工具。dag應(yīng)用之例。例設(shè)有程序如下。i=m－