編譯原理 代碼生成

第九章代碼生成學(xué)習(xí)內(nèi)容目標(biāo)機(jī)器存儲(chǔ)管理基本塊、流圖簡(jiǎn)單代碼生成算法寄存器分配窺孔優(yōu)化基本塊dag表示、從dag生成代碼9.1設(shè)計(jì)中的問(wèn)題輸入前端生成的中間表示形式線性化表示：后綴表示形式四元式表示：三地址碼虛擬機(jī)表示：抽象棧機(jī)器代碼圖形化表示：語(yǔ)法樹(shù)、DAG符號(hào)表信息類(lèi)型檢查、類(lèi)型轉(zhuǎn)換已完成輸入是無(wú)錯(cuò)誤的設(shè)計(jì)中的問(wèn)題（續(xù)）目標(biāo)程序絕對(duì)機(jī)器語(yǔ)言固定內(nèi)存地址，可直接執(zhí)行可重定位機(jī)器語(yǔ)言多模塊連接靈活、分別編譯匯編語(yǔ)言簡(jiǎn)單——符號(hào)指令、宏的使用設(shè)計(jì)中的問(wèn)題（續(xù)）內(nèi)存管理名字?jǐn)?shù)據(jù)地址，與前端協(xié)作符號(hào)表標(biāo)號(hào)指令地址backpatching技術(shù)設(shè)計(jì)中的問(wèn)題（續(xù)）指令選擇指令集特性一致性、完整性指令速度、機(jī)器特性代碼質(zhì)量：速度、大小豐富的指令集多種代碼生成方式選擇最高效方式設(shè)計(jì)問(wèn)題（續(xù)）寄存器分配allocation、assignment最優(yōu)化assignment——NP-完全問(wèn)題register-pair計(jì)算順序調(diào)整計(jì)算順序提高效率NP-完全問(wèn)題設(shè)計(jì)問(wèn)題（續(xù)）代碼生成方法正確性是第一位的設(shè)計(jì)目標(biāo)：易于實(shí)現(xiàn)、測(cè)試、維護(hù)9.6節(jié)：生成算法，9.9節(jié)：窺孔優(yōu)化9.7節(jié)：寄存器使用算法——控制流9.10、9.11節(jié)：代碼選擇9.12節(jié)：代碼生成——樹(shù)重構(gòu)9.2目標(biāo)機(jī)器寄存器：R0，R1，…，Rn-1指令：opsource,destination尋址方式MOVR0,MMOV4(R0),MMOV*4(R0),M尋址方式形式地址額外開(kāi)銷(xiāo)絕對(duì)MM1寄存器RR0索引c(R)c+contents(R)1間接寄存器*Rcontents(R)0間接索引*c(R)contents(c+contents(R))1指令開(kāi)銷(xiāo)長(zhǎng)度MOVR0,R1：開(kāi)銷(xiāo)1MOVR5,M：開(kāi)銷(xiāo)2ADD#1,R3：開(kāi)銷(xiāo)2SUB4(R0),*12(R1)：開(kāi)銷(xiāo)3指令開(kāi)銷(xiāo)——翻譯方法a=b+cMOVb,R0

開(kāi)銷(xiāo)6

ADDc,R0

MOVR0,aMOVb,a 開(kāi)銷(xiāo)6

ADDc,aMOV*R1,*R0 開(kāi)銷(xiāo)2

ADD*R2,*R0ADDR2,R1 開(kāi)銷(xiāo)3

MOVR1,aR0：a的地址

R1：b的地址

R2：c的地址R1：b的值

R2：c的值9.3運(yùn)行時(shí)存儲(chǔ)管理靜態(tài)分配，棧分配翻譯如下三地址碼callreturnhaltaction9.3.1靜態(tài)分配call翻譯為MOV#here,callee.static_areaGOTOcallee.code_areareturn翻譯為GOTO*callee.static_area當(dāng)前代碼地址被調(diào)用函數(shù)的靜態(tài)區(qū)域被調(diào)用函數(shù)的代碼區(qū)域例9.1三地址碼/*c的代碼

*/action1callpaction2halt/*p的代碼*/action1returnc的活動(dòng)記錄

（64字節(jié)）0:returnaddress8:arr56:i60:jp的活動(dòng)記錄

（64字節(jié)）0:returnaddress8:buf84:n例9.1（續(xù)）100: ACTION1120: MOV#140,364132: GOTO200140: ACTION2160: HALT …200: ACTION3220: GOTO*364 … /*300-363:c的活動(dòng)記錄*/300: /*返回地址*/304: /*局部數(shù)據(jù)*/ …

/*364-451:p的活動(dòng)記錄*/364: /*返回地址*/368: /*局部數(shù)據(jù)*/9.3.2棧分配使用相對(duì)活動(dòng)記錄起始的偏移活動(dòng)記錄的地址——棧寄存器，SP“第一個(gè)過(guò)程”

MOV#stackstart,SP

第一個(gè)過(guò)程的代碼

HALT棧分配——函數(shù)調(diào)用和返回調(diào)用ADD#caller.recordsize,SP /*指向被調(diào)函數(shù)活 動(dòng)記錄*/MOV#here+16,*SP /*保存返回地址*/GOTOcallee.code_area返回GOTO*0(SP)棧寄存器調(diào)整回調(diào)用者的活動(dòng)記錄SUB#caller.recordsize,SP例9.2三地址碼/*s的代碼*/action1callqaction2halt/*p的代碼*/action3return/*q的代碼*/action4callpaction5callqaction6callqreturn例9.2（續(xù)） /*s的代碼*/100: MOV#600,SP /*初始化棧*/108: ACTION1128: ADD#ssize,SP /*調(diào)用序列開(kāi)始*/136: MOV#152,*SP /*返回地址壓棧*/144: GOTO300 /*callq*/152: SUB#ssize,SP /*恢復(fù)棧*/160: ACTION2180: HALT …

/*p的代碼*/200: ACTION3220: GOTO*0(SP) /*return*/ …例9.2（續(xù)） /*q的代碼*/300: ACTION4 /*條件轉(zhuǎn)移到456*/320: ADD#qsize,SP328: MOV#344,*SP /*返回地址壓棧*/336: GOTO200 /*callp*/344: SUB#qsize,SP352: ACTION5372: ADD#qsize,SP380: MOV#396,*SP /*返回地址壓棧*/388: GOTO300 /*callq*/396: SUB#qsize,SP404: ACTION6424: ADD#qsize,SP432: MOV#448,*SP /*返回地址壓棧*/440: GOTO300 /*callq*/448: SUB#qsize,SP456: GOTO*0(SP) /*return*/ …600:9.3.3運(yùn)行時(shí)名字的地址x:=0相對(duì)地址12位于靜態(tài)分配區(qū)域，地址staticstatic[12]:=0static=100MOV#0,112display方式，地址在寄存器R3中t1:=12+R3

*t1:=0MOV#0,12(R3)9.4基本塊和流圖9.4.1基本塊，basicblock連續(xù)語(yǔ)句序列，執(zhí)行過(guò)程中沒(méi)有分支t1:=a*a

t2:=a*b

t3:=2*t2

t4:=t1+t3

t5:=b*b

t6:=t4+t5x:=y+z：定義x，使用（引用）y、z算法9.1基本塊的劃分輸入 三地址碼序列輸出 劃分后的基本塊方法首先確定入口語(yǔ)句（leader，基本塊的第一個(gè)語(yǔ)句）集，確定規(guī)則：程序的第一條語(yǔ)句條件轉(zhuǎn)移或無(wú)條件轉(zhuǎn)移語(yǔ)句的目的語(yǔ)句條件轉(zhuǎn)移或無(wú)條件轉(zhuǎn)移語(yǔ)句之后的語(yǔ)句每個(gè)leader對(duì)應(yīng)的基本塊：

leader——下個(gè)leader（或程序尾）例9.3begin prod:=0 i:=1 dobegin prod:=prod+a[i]*b[i]; i:=i+1 end whilei<=20end例9.3（續(xù)）prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*it4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi<=20goto(3)9.4.2基本塊的變換基本塊進(jìn)行表達(dá)式計(jì)算等價(jià)——計(jì)算相同的表達(dá)式變換——不改變計(jì)算的表達(dá)式集合提高代碼質(zhì)量保結(jié)構(gòu)變換

structure-preservingtransformation代數(shù)變換

algebraictransformation9.4.3保結(jié)構(gòu)變換公共子表達(dá)式刪除a:=b+cb:=a–dc:=b+cd:=a–d a:=b+cb:=a–dc:=b+cd:=bd與b相同c與a不同！保結(jié)構(gòu)變換（續(xù)）無(wú)用代碼刪除x:=y+zx在后續(xù)代碼中未被使用，則可將此語(yǔ)句刪除重命名臨時(shí)變量t:=b+c，t——臨時(shí)變量u:=b+c，u——新臨時(shí)變量，對(duì)t的引用對(duì)u的引用，基本塊結(jié)果不變定義臨時(shí)變量的語(yǔ)句都定義新的臨時(shí)變量基本塊等價(jià)變換，范式基本塊保結(jié)構(gòu)變換（續(xù)）語(yǔ)句交換t1:=b+ct2:=x+y兩個(gè)語(yǔ)句交換位置不影響運(yùn)算結(jié)果x、y都不是t1，b、c都不是t2注意：范式基本塊允許所有可能的語(yǔ)句交換9.4.4代數(shù)變換允許改變表達(dá)式——代數(shù)上等價(jià)x:=x+0——?jiǎng)h除x:=x*1——?jiǎng)h除x:=y**2x:=y*y——提高性能9.4.5流圖基本塊間添加控制流信息程序流圖，flowgraph節(jié)點(diǎn)——基本塊首（initial）節(jié)點(diǎn)——該基本塊的入口語(yǔ)句就是程序的第一條語(yǔ)句流圖的構(gòu)造基本塊B1到B2有一條有向邊代碼執(zhí)行序列中B2緊跟在B1之后：B1的最后一條語(yǔ)句（無(wú)）條件轉(zhuǎn)向到B2的第一條語(yǔ)句程序中B2緊跟在B1之后，且B1的最后一條語(yǔ)句不是無(wú)條件轉(zhuǎn)移語(yǔ)句B1——B2的前驅(qū)，B2——B1的后繼例9.4prod:=0i:=1t1:=4*it2:=a[t1]t3:=4*it4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi<=20goto(3)9.4.6基本塊的表示記錄計(jì)數(shù)器：四元組（三地址碼語(yǔ)句）數(shù)目指向leader的指針指向前驅(qū)基本塊和后繼基本塊的指針優(yōu)化時(shí)代碼改變或移動(dòng)跳轉(zhuǎn)到語(yǔ)句號(hào)跳轉(zhuǎn)到基本塊9.4.7循環(huán)（loop）什么是循環(huán)？如何找到循環(huán)？循環(huán)——滿(mǎn)足如下條件的一組節(jié)點(diǎn)這組節(jié)點(diǎn)是強(qiáng)連通的——任何兩個(gè)節(jié)點(diǎn)間都存在一條（完全包含在循環(huán)內(nèi)的）路徑這組節(jié)點(diǎn)具有唯一的一個(gè)入口（entry）——從循環(huán)外的節(jié)點(diǎn)到達(dá)循環(huán)內(nèi)的節(jié)點(diǎn)，唯一的途徑是先到達(dá)入口節(jié)點(diǎn)內(nèi)部不包含其他循環(huán)的循環(huán)——內(nèi)層循環(huán)，innerloop9.5下次引用信息next-useinformation名字的使用（use）三地址碼語(yǔ)句i為x賦值語(yǔ)句j將x作為運(yùn)算對(duì)象，而i到j(luò)的控制流路徑中無(wú)其他對(duì)x賦值的語(yǔ)句語(yǔ)句j使用了語(yǔ)句i計(jì)算的x值對(duì)語(yǔ)句x:=yopz，確定x、y、z下次使用的位置，以決定寄存器可否釋放由后向前掃描基本塊9.5.1計(jì)算下次引用信息基本方法每個(gè)變量記錄下次引用信息和活躍信息假定每個(gè)臨時(shí)變量在基本塊出口后非活躍非臨時(shí)變量在出口后活躍若臨時(shí)變量跨基本塊，假定其活躍算法：當(dāng)掃描到語(yǔ)句i：x:=yopz將x、y、z的下次引用信息和活躍信息附加在語(yǔ)句i之上設(shè)置x為“非活躍”和“沒(méi)有下次引用”設(shè)置y、z為“活躍”，下次引用信息設(shè)置為i不可交換！9.5.2臨時(shí)名字的存儲(chǔ)分配兩個(gè)臨時(shí)名字活躍期不重疊相同地址利用下次使用信息t1:=a*a

t2:=a*b

t3:=2*t2

t4:=t1+t3

t5:=b*b

t6:=t4+t5t1:=a*a

t2:=a*b

t2:=2*t2

t1:=t1+t2

t2:=b*b

t1:=t1+t2t5t4t3t1t29.6一個(gè)簡(jiǎn)單的代碼生成器每個(gè)中間語(yǔ)言指令目標(biāo)語(yǔ)言指令計(jì)算結(jié)果盡量保存在寄存器，除非需要用寄存器進(jìn)行其他計(jì)算下面語(yǔ)句是函數(shù)調(diào)用、轉(zhuǎn)移或標(biāo)號(hào)

基本塊結(jié)束！a:=b+cRi=b,Rj=cADDRj,Ri——開(kāi)銷(xiāo)1Ri=bADDc,Ri——開(kāi)銷(xiāo)2

或MOVc,Rj ADDRj,Ri——開(kāi)銷(xiāo)39.6.1寄存器描述符和地址描述符代碼生成程序用來(lái)保存寄存器內(nèi)容和名字的地址寄存器描述符：

當(dāng)前每個(gè)寄存器內(nèi)容，分配新寄存器時(shí)用

初始：所有寄存器均空

代碼生成過(guò)程中：保存0個(gè)或多個(gè)名字值地址描述符：

名字的當(dāng)前值保存在何處？

寄存器、棧位置或是內(nèi)存地址

可能在多個(gè)位置9.6.2代碼生成算法輸入：基本塊，對(duì)每個(gè)語(yǔ)句x:=yopz：為計(jì)算結(jié)果分配位置L——getreg提取y的值查詢(xún)y的位置y’——地址描述符，寄存器優(yōu)先y’<>L——MOVy’,L生成計(jì)算指令查詢(xún)z的位置z’OPz’,L更新x的地址描述符和L的寄存器描述符若y、z不再被引用，從寄存器描述符刪除特殊情況一元運(yùn)算：省略z的部分x:=y，根據(jù)y的位置寄存器L：修改寄存器描述符和地址描述符x也（僅）在L中內(nèi)存：getreg，得到的寄存器保存x和yx不再被引用：MOVy,x特殊情況基本塊出口，將活躍名字值存入內(nèi)存寄存器描述符哪些名字保存在寄存器中地址描述符名字對(duì)應(yīng)的內(nèi)存地址活躍信息是否需要保存9.6.3getreg算法x:=yopz，為x分配位置L，效率高低與y占用相同寄存器y的寄存器r不包含其他名字y不再活躍、不再被引用1）失敗，尋找一個(gè)空寄存器2）失敗，寄存器替換x還會(huì)被引用，或op操作需要使用寄存器——數(shù)組索引尋找已用寄存器R，x替換其中變量R中變量引用位置最遠(yuǎn)，或已保存在內(nèi)存中x不再被引用，或無(wú)合適寄存器——內(nèi)存例9.5d:=(a–b)+(a–c)+(a–c)三地址碼目標(biāo)代碼寄存器描述符地址描述符寄存器均為空t:=a–bMOVa,R0SUBb,R0R0包含tt在R0中u:=a–cMOVa,R1SUBc,R1R0包含tR1包含ut在R0中u在R1中v:=t+uADDR1,R0R0包含vR1包含uu在R1中v在R0中d:=v+uADDR1,R0MOVR0,dR0包dd在R0中d在R0和

內(nèi)存中9.6.4其他類(lèi)型語(yǔ)句的代碼生成數(shù)組和指針語(yǔ)句i在寄存器Ri中i在內(nèi)存Mi中i在棧中代碼開(kāi)銷(xiāo)代碼開(kāi)銷(xiāo)代碼開(kāi)銷(xiāo)a:=b[i]MOVb(Ri),R2MOVMi,RMOVb(R),R4MOVSi(A),RMOVb(R),R4a[i]:=bMOVb,a(Ri)3MOVMi,RMOVb,a(R)5MOVSi(A),RMOVb,a(R)5語(yǔ)句p在寄存器Rp中p在內(nèi)存Mp中p在棧中代碼開(kāi)銷(xiāo)代碼開(kāi)銷(xiāo)代碼開(kāi)銷(xiāo)a:=*pMOV*Rp,a2MOVMp,RMOV*R,R3MOVSp(A),RMOV*R,R3*p:=aMOVa,*Rp2MOVMp,RMOVa,*R4MOVa,RMOVR,*Sp(A)59.6.5條件轉(zhuǎn)移語(yǔ)句兩種實(shí)現(xiàn)方式寄存器值符合六個(gè)條件之一：負(fù)數(shù)、零、正數(shù)、非負(fù)數(shù)、非零、非正數(shù)

ifx<ygotozx–y，if負(fù)數(shù)gotoz條件代碼

ifx<ygotoz CMPx,y CJ<z x:=y+z MOVy,R0 ifx<0gotoz ADDz,R0 MOVR0,x CJ< z9.7寄存器分配和指定寄存器操作比內(nèi)存操作代碼短，速度快分配：確定哪些值保存在寄存器中指定：確定每個(gè)值具體保存在哪個(gè)寄存器中寄存器分組基地址、數(shù)學(xué)運(yùn)算、棧地址…簡(jiǎn)單、低效9.7.1全局寄存器分配9.6節(jié)，基本塊出口，寄存器內(nèi)存避免復(fù)制，將最常用的變量保持在寄存器中跨越基本塊邊界——全局循環(huán)使用固定一組寄存器保存每個(gè)內(nèi)存循環(huán)中最活躍的變量C運(yùn)行程序員指定寄存器分配9.7.2引用計(jì)數(shù)假定訪問(wèn)寄存器比訪問(wèn)內(nèi)存節(jié)省開(kāi)銷(xiāo)1循環(huán)L，定義x9.6節(jié)：定義之后若有引用，x將保留在寄存器中，而定義之前的引用需訪問(wèn)內(nèi)存優(yōu)化：x一直保存在寄存器中，定義之前的引用訪問(wèn)寄存器，節(jié)省開(kāi)銷(xiāo)1節(jié)省開(kāi)銷(xiāo)（續(xù)）塊結(jié)束時(shí)變量活躍，在塊中被定義，后繼塊中被引用9.6節(jié)：保存至內(nèi)存，后繼塊又需讀出到寄存器優(yōu)化：無(wú)需保存和讀出，節(jié)省開(kāi)銷(xiāo)2例9.6a:=b+c

d:=d–b

e:=a+fB1acdefb:=d+f

e:=a–cacdfbcdeff:=a–dacdecdefb:=d+ccdefbcdefbdef活躍bcdef活躍bcdfB2B3B4例9.6（續(xù)）R0，R1，R2對(duì)變量a只在B1出口活躍，use(a,B1)=use(a,B4)=0,

use(a,B2)=use(a,B3)=1總共節(jié)省4b,c,d,e,f——6,3,6,4,4可將a、b、d保存在R0、R1、R2中例9.6（續(xù)）MOVR1,R0 MOVR0,R3

ADDc,R0 ADDf,R3

SUBR1,R2 MOVR3,eB1MOVR2,R1 SUBc,R3

ADDf,R1 MOVR3,e

MOVR0,R3 MOVR3,eMOVR0,R3

SUBR2,R3

MOVR3,fMOVR2,R1

ADDc,R1B2B3B4MOVR1,b

MOVR2,dMOVb,R1

MOVd,R2MOVR1,b

MOVR2,d9.7.3外層循環(huán)的寄存器分配內(nèi)層循環(huán)相同思想L1包含L2，x在L2中分配了寄存器，則在L1–L2不必再分配x在L1中分配了寄存器，而L2中沒(méi)有，則在L2入口需保存，出口需讀出x在L2中分配了寄存器，而L1中沒(méi)有，則在L2入口需讀取，出口需保存9.7.4圖著色法進(jìn)行寄存器分配兩次掃描假定寄存器數(shù)目是無(wú)限的，選擇目標(biāo)機(jī)器指令翻譯中間代碼——每個(gè)變量一個(gè)寄存器，符號(hào)寄存器分配物理寄存器寄存器沖突圖，register-interferencegraph節(jié)點(diǎn)——符號(hào)寄存器，R1—R2，R2定義的位置上R1活躍k——可用物理寄存器數(shù)，用k個(gè)顏色為圖著色相鄰節(jié)點(diǎn)不同顏色——干擾變量使用不同寄存器啟發(fā)式算法n鄰居數(shù)<k，去掉nG’，G’可k著色G可k著色最終——空?qǐng)D（成功）或所有節(jié)點(diǎn)鄰居數(shù)>=n（失敗）9.8基本塊的DAG表示構(gòu)造方法葉：標(biāo)記變量或常量

左值/右值

初始值——下標(biāo)0內(nèi)部節(jié)點(diǎn)：標(biāo)記為運(yùn)算符為節(jié)點(diǎn)標(biāo)記標(biāo)識(shí)符——計(jì)算結(jié)果保存在標(biāo)識(shí)符中例9.7t1:=4*it2:=a[t1]t3:=4*it4:=b[t3]t5:=t2*t4t6:=prod+t5prod:=t6t7:=i+1i:=t7ifi<=20goto(1)9.8.1dag的構(gòu)造算法9.2：輸入 一個(gè)基本塊輸出 基本塊對(duì)應(yīng)的dag，包含如下信息：每個(gè)節(jié)點(diǎn)有一個(gè)標(biāo)記，葉節(jié)點(diǎn)標(biāo)記為標(biāo)識(shí)符，內(nèi)部節(jié)點(diǎn)標(biāo)記為操作符每個(gè)節(jié)點(diǎn)有一個(gè)附著標(biāo)識(shí)符列表算法9.2：dag的構(gòu)造（續(xù)）方法：node(identifier)：標(biāo)識(shí)符identifier相關(guān)聯(lián)的節(jié)點(diǎn)對(duì)基本塊每個(gè)語(yǔ)句做步驟(1)-(3)初始，沒(méi)有節(jié)點(diǎn)，node函數(shù)均為未定義三種語(yǔ)句： (i)x:=yopz

(ii)x:=opy (iii)x:=y創(chuàng)建孩子節(jié)點(diǎn)若node(y)未定義，創(chuàng)建一個(gè)葉節(jié)點(diǎn)，標(biāo)記為y，node(y)的值設(shè)置為此節(jié)點(diǎn)。對(duì)(i)類(lèi)語(yǔ)句，z同樣處理算法9.2：dag的構(gòu)造（續(xù)）創(chuàng)建父節(jié)點(diǎn)對(duì)(i)類(lèi)語(yǔ)句，檢查是否有節(jié)點(diǎn)標(biāo)記為op，且左孩子為node(y)，右孩子為node(z)（檢查公共子表達(dá)式），若沒(méi)有，創(chuàng)建這樣的節(jié)點(diǎn)。令n表示此節(jié)點(diǎn)。對(duì)(ii)類(lèi)語(yǔ)句，檢查是否有標(biāo)記為op的節(jié)點(diǎn)，其單一孩子節(jié)點(diǎn)為node(y)，若沒(méi)有，創(chuàng)建這樣的節(jié)點(diǎn)。令n表示此節(jié)點(diǎn)。對(duì)(iii)類(lèi)語(yǔ)句，令n=node(y)附著列表的更新將x從節(jié)點(diǎn)node(x)的附著列表刪除，添加到n的附著列表中，并將node(x)的值設(shè)置為n例9.89.8.2dag的應(yīng)用公共子表達(dá)式的自動(dòng)檢查哪些標(biāo)識(shí)符在基本塊中被使用步驟(1)，創(chuàng)建的葉節(jié)點(diǎn)對(duì)應(yīng)的標(biāo)識(shí)符哪些語(yǔ)句S，其計(jì)算的變量值可能在基本塊外被使用S對(duì)x賦值，創(chuàng)建節(jié)點(diǎn)n，x附著在n上（步驟2）dag構(gòu)造完畢后，若仍有node(x)==n，則S計(jì)算的x值在基本塊外可被使用例9.9例9.8中所有所有語(yǔ)句都滿(mǎn)足3dag的其他應(yīng)用提取公共子表達(dá)式、x:=y避免不必要的復(fù)制——重新構(gòu)造優(yōu)化的三地址碼對(duì)每個(gè)節(jié)點(diǎn)關(guān)聯(lián)的標(biāo)識(shí)符，選定一個(gè)例9.10t1:=4*it2:=a[t1]t4:=b[t1]t5:=t2*t4prod:=prod+t5i:=i+1ifi<=20goto(1)9.8.3數(shù)組、指針和函數(shù)調(diào)用x:=a[i] x:=a[i]

a[j]:=y z:=x

z:=a[i] a[j]:=y

若i=j，y≠a[i]，錯(cuò)誤！注銷(xiāo)[]節(jié)點(diǎn)，不附加額外的標(biāo)識(shí)符*p:=w，類(lèi)似，可能需要注銷(xiāo)所有節(jié)點(diǎn)函數(shù)調(diào)用，注銷(xiāo)所有節(jié)點(diǎn)額外邊——保持原三地址碼語(yǔ)句順序哪些語(yǔ)句順序應(yīng)予以保持前：數(shù)組元素的賦值語(yǔ)句

后：同一數(shù)組的元素的計(jì)算、賦值語(yǔ)句前：數(shù)組元素的計(jì)算語(yǔ)句

后：同一數(shù)組的元素的賦值語(yǔ)句前：函數(shù)調(diào)用、利用指針間接賦值

后：使用任何標(biāo)識(shí)符前：任何標(biāo)識(shí)符的計(jì)算

后：函數(shù)調(diào)用、利用指針間接賦值9.9窺孔（Peephole）優(yōu)化窺孔：目標(biāo)代碼一個(gè)小的、移動(dòng)的窗口

更小、更快的代碼消除冗余指令控制流優(yōu)化代數(shù)優(yōu)化利用機(jī)器的特性9.9.1冗余的Load和Store指令MOVR0,aMOVa,R0刪除(2)例外：(2)有標(biāo)號(hào)保證(1)、(2)在同一個(gè)基本塊9.9.2不可達(dá)代碼#definedebug0 ifdebug=1gotoL1… gotoL2if(debug){ L1:打印調(diào)試信息 打印調(diào)試信息} L2: ifdebug<>1gotoL2

打印調(diào)試信息

L2: if0<>1gotoL2

打印調(diào)試信息

L2：可刪除9.9.3控制流優(yōu)化gotoL1 gotoL2… …L1:gotoL2 L1:gotoL2ifa<bgotoL1 ifa<bgotoL2… …L1:gotoL2 L1:gootL2gotoL1 ifa<bgotoL2… gotoL3L1:ifa<bgotoL2 …L3: L3:其他優(yōu)化方法9.9.4代數(shù)優(yōu)化x:=x+0，x:=x*19.9.5強(qiáng)度削弱開(kāi)銷(xiāo)高的指令等價(jià)的開(kāi)銷(xiāo)低的指令x2：乘方函數(shù)x*x9.9.6利用機(jī)器特性特殊機(jī)器指令高效實(shí)現(xiàn)某些操作i:=i+1inci9.10利用dag生成目標(biāo)代碼9.10.1重排順序：(a+b)–(e–(c+d))t1:=a+b

t2:=c+d

t3:=e–t2

t4:=t1–t3MOVa,R0

ADDb,R0

MOVc,R1

ADDd,R1

MOVR0,t1

MOVe,R0

SUBR1,R0

MOVt1,R1

SUBR0,R1

MOVR1,t4重排順序（續(xù)）t2:=c+d

t3:=e–t2

t1:=a+b

t4:=t1–t3MOVc,R0

ADDd,R0

MOVe,R1

SUBR0,R1

MOVa,R0

ADDb,R0

SUBR1,R0

MOVR0,t49.10.2一個(gè)啟發(fā)式重排序算法計(jì)算緊接在左孩子之后（t4，t1）——共用一個(gè)寄存器算法（按逆序給出重排之后的順序）：while

存在未列出的內(nèi)部節(jié)點(diǎn)do

begin選擇一個(gè)未列出的節(jié)點(diǎn)n，其父節(jié)點(diǎn)都已列出;列出n;whilen的最左孩子m的所有父節(jié)點(diǎn)都已列出，且它不

是葉節(jié)點(diǎn)dobegin

列出m;n:=m;

end

end例9.11t8:=d+et6:=a+bt5:=t6–ct4:=t5*t8t3:=t4–et2:=t6+t4t1:=t2*t3

9.10.3樹(shù)結(jié)構(gòu)的最優(yōu)排序dag樹(shù)，計(jì)算最優(yōu)順序的算法自底向上為每個(gè)節(jié)點(diǎn)標(biāo)記一個(gè)整數(shù)——不存儲(chǔ)中間結(jié)果的條件下，計(jì)算所需最少寄存器數(shù)目由標(biāo)記確定順序，對(duì)樹(shù)進(jìn)行遍歷，生成目標(biāo)代碼9.10.4標(biāo)記算法ifn為葉節(jié)點(diǎn)then

ifn為其父節(jié)點(diǎn)的最左孩子thenlabel(n):=1

elselabel(n):=0

elsebegin

令n1,n2,…,nk是n的孩子按標(biāo)號(hào)排序后的結(jié)果，即label(n1)>=label(n2)>=…>=label(nk)label(n):=max(label(ni)+i–1),1<i<k

end例9.129.10.5利用標(biāo)記樹(shù)生成代碼gencode(n)：生成以n為根的標(biāo)記樹(shù)T的代碼，結(jié)果在寄存器R0中rstack：可用寄存器棧，R0,R1,…,R(r-1)swap(rstack)：交換棧頂兩個(gè)寄存器tstack：臨時(shí)存儲(chǔ)棧，T0,T1,T2,…算法處理的幾種情況：算法gencode(n){ if(n為表示運(yùn)算對(duì)象name的左葉節(jié)點(diǎn)且為其父節(jié)點(diǎn)的最左孩子)

print‘MOV’||name||‘,’||top(rstack); elseif(n是內(nèi)部節(jié)點(diǎn)，運(yùn)算符為op，左、右孩子為n1、n2) { if(label(n2)==0){ /*情況1*/ 令name為n2表示的運(yùn)算對(duì)象;

gencode(n1); printop||name||‘,’||top(rstack); }elseif(1<=label(n1)<label(n2)andlabel(n1)<r){/*情況2*/

swap(rstack);

gencode(n2); R=pop(rstack); /*n2的值在R中*/

gencode(n1); printop||R||‘,’||top(rstack); push(rstack,R); swap(rstack);算法（續(xù)） }elseif(1<=label(n2)<=label(n1)andlabel(n2)<r){/*情況3*/

gencode(n1); R=pop(rstack); /*n1的值在R中*/

gencode(n2); printop||top(rstack)||‘,’||R; push(rstack,R); }else{/*情況4*/

gencode(n2); T=pop(tstack); print‘MOV’||top(rstack)||‘,’||T;

gencode(n1); push(tstack,T); printop||T||‘,’||top(rstack); } }}例9.13gencode(t4)[R1R0]

情況2

gencode(t3)[R0R1]

情況3

gencode(e)[R0R1]

情況0

printMOVe,R1

gencode(t2)[R0]情況1

gencode(c)[R0]

情況0

printMOVc,R0printADDd,R0printSUBR0,R1

gencode(t1)[R0]

情況1

gencode(a)[R0]情況0

printMOVa,R0printADDb,R0printSUBR1,R09.10.6多寄存器運(yùn)算乘、除、函數(shù)調(diào)用修改標(biāo)記算法“寄存器對(duì)”情況避免使用swap——情況29.10.7利用代數(shù)特性?xún)?yōu)化9.10.8公共子表達(dá)式的處理NP-完全問(wèn)題dag森林，只有葉節(jié)點(diǎn)可為共享節(jié)點(diǎn)9.11動(dòng)態(tài)規(guī)劃代碼生成算法一條指令使用兩個(gè)以上寄存器Ri:=EE包含一個(gè)或多個(gè)寄存器，有一個(gè)是RiADDR0,R1R1:=R1+R0

ADD*R0,R1R1:=R1+indR0load指令：Ri:=Mstore指令：M:=Ri寄存器間拷貝：Ri:=Rj9.11.2動(dòng)態(tài)規(guī)劃算法原理E=E1+E2，E的最優(yōu)程序可由E1、E2的最優(yōu)程序組合而成連續(xù)特性T1、T2的計(jì)算是連續(xù)的、完整的，不交叉9.11.4動(dòng)態(tài)規(guī)劃算法對(duì)表達(dá)式樹(shù)T的每個(gè)節(jié)點(diǎn)n，計(jì)算以n為根的子樹(shù)（子表達(dá)式）的最優(yōu)計(jì)算開(kāi)銷(xiāo)C[i]：利用i個(gè)寄存器計(jì)算表達(dá)式的開(kāi)銷(xiāo)R:=E考慮所有子表達(dá)式的不同計(jì)算順序“＋”E的指令的計(jì)算開(kāi)銷(xiāo)開(kāi)銷(xiāo)最小者C[i]遍歷T，根據(jù)C[i]確定哪些子表達(dá)式結(jié)果必須保存到內(nèi)存生成代碼例9.14目標(biāo)機(jī)器兩個(gè)寄存器R0、R1指令集（開(kāi)銷(xiāo)均為1）：Ri:=MjRi:=RiopRjRi:=RiopMjRi:=RjMi:=Rj例9.14（續(xù)）葉節(jié)點(diǎn)a結(jié)果