編譯原理 代碼生成

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

開銷6

ADDc,R0

MOVR0,aMOVb,a 開銷6

ADDc,aMOV*R1,*R0 開銷2

ADD*R2,*R0ADDR2,R1 開銷3

MOVR1,aR0：a的地址

R1：b的地址

R2：c的地址R1：b的值

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

*/action1callpaction2halt/*p的代碼*/action1returnc的活動記錄

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

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

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

MOV#stackstart,SP

第一個過程的代碼

HALT棧分配——函數(shù)調(diào)用和返回調(diào)用ADD#caller.recordsize,SP /*指向被調(diào)函數(shù)活 動記錄*/MOV#here+16,*SP /*保存返回地址*/GOTOcallee.code_area返回GOTO*0(SP)棧寄存器調(diào)整回調(diào)用者的活動記錄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)用序列開始*/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運行時名字的地址x:=0相對地址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ù)語句序列，執(zhí)行過程中沒有分支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基本塊的劃分輸入 三地址碼序列輸出 劃分后的基本塊方法首先確定入口語句（leader，基本塊的第一個語句）集，確定規(guī)則：程序的第一條語句條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句的目的語句條件轉(zhuǎn)移或無條件轉(zhuǎn)移語句之后的語句每個leader對應(yīng)的基本塊：

leader——下個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基本塊的變換基本塊進行表達式計算等價——計算相同的表達式變換——不改變計算的表達式集合提高代碼質(zhì)量保結(jié)構(gòu)變換

structure-preservingtransformation代數(shù)變換

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

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

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

當前每個寄存器內(nèi)容，分配新寄存器時用

初始：所有寄存器均空

代碼生成過程中：保存0個或多個名字值地址描述符：

名字的當前值保存在何處？

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

可能在多個位置9.6.2代碼生成算法輸入：基本塊，對每個語句x:=yopz：為計算結(jié)果分配位置L——getreg提取y的值查詢y的位置y’——地址描述符，寄存器優(yōu)先y’<>L——MOVy’,L生成計算指令查詢z的位置z’OPz’,L更新x的地址描述符和L的寄存器描述符若y、z不再被引用，從寄存器描述符刪除特殊情況一元運算：省略z的部分x:=y，根據(jù)y的位置寄存器L：修改寄存器描述符和地址描述符x也（僅）在L中內(nèi)存：getreg，得到的寄存器保存x和yx不再被引用：MOVy,x特殊情況基本塊出口，將活躍名字值存入內(nèi)存寄存器描述符哪些名字保存在寄存器中地址描述符名字對應(yīng)的內(nèi)存地址活躍信息是否需要保存9.6.3getreg算法x:=yopz，為x分配位置L，效率高低與y占用相同寄存器y的寄存器r不包含其他名字y不再活躍、不再被引用1）失敗，尋找一個空寄存器2）失敗，寄存器替換x還會被引用，或op操作需要使用寄存器——數(shù)組索引尋找已用寄存器R，x替換其中變量R中變量引用位置最遠，或已保存在內(nèi)存中x不再被引用，或無合適寄存器——內(nèi)存例9.5d:=(a–b)+(a–c)+(a–c)三地址碼目標代碼寄存器描述符地址描述符寄存器均為空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其他類型語句的代碼生成數(shù)組和指針語句i在寄存器Ri中i在內(nèi)存Mi中i在棧中代碼開銷代碼開銷代碼開銷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語句p在寄存器Rp中p在內(nèi)存Mp中p在棧中代碼開銷代碼開銷代碼開銷a:=*pMOV*Rp,a2MOVMp,RMOV*R,R3MOVSp(A),RMOV*R,R3*p:=aMOVa,*Rp2MOVMp,RMOVa,*R4MOVa,RMOVR,*Sp(A)59.6.5條件轉(zhuǎn)移語句兩種實現(xiàn)方式寄存器值符合六個條件之一：負數(shù)、零、正數(shù)、非負數(shù)、非零、非正數(shù)

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

ifx<ygotoz CMPx,y CJ<z x:=y+z MOVy,R0 ifx<0gotoz ADDz,R0 MOVR0,x CJ< z9.7寄存器分配和指定寄存器操作比內(nèi)存操作代碼短，速度快分配：確定哪些值保存在寄存器中指定：確定每個值具體保存在哪個寄存器中寄存器分組基地址、數(shù)學(xué)運算、棧地址…簡單、低效9.7.1全局寄存器分配9.6節(jié)，基本塊出口，寄存器內(nèi)存避免復(fù)制，將最常用的變量保持在寄存器中跨越基本塊邊界——全局循環(huán)使用固定一組寄存器保存每個內(nèi)存循環(huán)中最活躍的變量C運行程序員指定寄存器分配9.7.2引用計數(shù)假定訪問寄存器比訪問內(nèi)存節(jié)省開銷1循環(huán)L，定義x9.6節(jié)：定義之后若有引用，x將保留在寄存器中，而定義之前的引用需訪問內(nèi)存優(yōu)化：x一直保存在寄存器中，定義之前的引用訪問寄存器，節(jié)省開銷1節(jié)省開銷（續(xù)）塊結(jié)束時變量活躍，在塊中被定義，后繼塊中被引用9.6節(jié)：保存至內(nèi)存，后繼塊又需讀出到寄存器優(yōu)化：無需保存和讀出，節(jié)省開銷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對變量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中沒有，則在L2入口需保存，出口需讀出x在L2中分配了寄存器，而L1中沒有，則在L2入口需讀取，出口需保存9.7.4圖著色法進行寄存器分配兩次掃描假定寄存器數(shù)目是無限的，選擇目標機器指令翻譯中間代碼——每個變量一個寄存器，符號寄存器分配物理寄存器寄存器沖突圖，register-interferencegraph節(jié)點——符號寄存器，R1—R2，R2定義的位置上R1活躍k——可用物理寄存器數(shù)，用k個顏色為圖著色相鄰節(jié)點不同顏色——干擾變量使用不同寄存器啟發(fā)式算法n鄰居數(shù)<k，去掉nG’，G’可k著色G可k著色最終——空圖（成功）或所有節(jié)點鄰居數(shù)>=n（失?。?.8基本塊的DAG表示構(gòu)造方法葉：標記變量或常量

左值/右值

初始值——下標0內(nèi)部節(jié)點：標記為運算符為節(jié)點標記標識符——計算結(jié)果保存在標識符中例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：輸入 一個基本塊輸出 基本塊對應(yīng)的dag，包含如下信息：每個節(jié)點有一個標記，葉節(jié)點標記為標識符，內(nèi)部節(jié)點標記為操作符每個節(jié)點有一個附著標識符列表算法9.2：dag的構(gòu)造（續(xù)）方法：node(identifier)：標識符identifier相關(guān)聯(lián)的節(jié)點對基本塊每個語句做步驟(1)-(3)初始，沒有節(jié)點，node函數(shù)均為未定義三種語句： (i)x:=yopz

(ii)x:=opy (iii)x:=y創(chuàng)建孩子節(jié)點若node(y)未定義，創(chuàng)建一個葉節(jié)點，標記為y，node(y)的值設(shè)置為此節(jié)點。對(i)類語句，z同樣處理算法9.2：dag的構(gòu)造（續(xù)）創(chuàng)建父節(jié)點對(i)類語句，檢查是否有節(jié)點標記為op，且左孩子為node(y)，右孩子為node(z)（檢查公共子表達式），若沒有，創(chuàng)建這樣的節(jié)點。令n表示此節(jié)點。對(ii)類語句，檢查是否有標記為op的節(jié)點，其單一孩子節(jié)點為node(y)，若沒有，創(chuàng)建這樣的節(jié)點。令n表示此節(jié)點。對(iii)類語句，令n=node(y)附著列表的更新將x從節(jié)點node(x)的附著列表刪除，添加到n的附著列表中，并將node(x)的值設(shè)置為n例9.89.8.2dag的應(yīng)用公共子表達式的自動檢查哪些標識符在基本塊中被使用步驟(1)，創(chuàng)建的葉節(jié)點對應(yīng)的標識符哪些語句S，其計算的變量值可能在基本塊外被使用S對x賦值，創(chuàng)建節(jié)點n，x附著在n上（步驟2）dag構(gòu)造完畢后，若仍有node(x)==n，則S計算的x值在基本塊外可被使用例9.9例9.8中所有所有語句都滿足3dag的其他應(yīng)用提取公共子表達式、x:=y避免不必要的復(fù)制——重新構(gòu)造優(yōu)化的三地址碼對每個節(jié)點關(guān)聯(lián)的標識符，選定一個例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]，錯誤！注銷[]節(jié)點，不附加額外的標識符*p:=w，類似，可能需要注銷所有節(jié)點函數(shù)調(diào)用，注銷所有節(jié)點額外邊——保持原三地址碼語句順序哪些語句順序應(yīng)予以保持前：數(shù)組元素的賦值語句

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

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

后：使用任何標識符前：任何標識符的計算

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

更小、更快的代碼消除冗余指令控制流優(yōu)化代數(shù)優(yōu)化利用機器的特性9.9.1冗余的Load和Store指令MOVR0,aMOVa,R0刪除(2)例外：(2)有標號保證(1)、(2)在同一個基本塊9.9.2不可達代碼#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強度削弱開銷高的指令等價的開銷低的指令x2：乘方函數(shù)x*x9.9.6利用機器特性特殊機器指令高效實現(xiàn)某些操作i:=i+1inci9.10利用dag生成目標代碼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一個啟發(fā)式重排序算法計算緊接在左孩子之后（t4，t1）——共用一個寄存器算法（按逆序給出重排之后的順序）：while

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

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

是葉節(jié)點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樹結(jié)構(gòu)的最優(yōu)排序dag樹，計算最優(yōu)順序的算法自底向上為每個節(jié)點標記一個整數(shù)——不存儲中間結(jié)果的條件下，計算所需最少寄存器數(shù)目由標記確定順序，對樹進行遍歷，生成目標代碼9.10.4標記算法ifn為葉節(jié)點then

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

elselabel(n):=0

elsebegin

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

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

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

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多寄存器運算乘、除、函數(shù)調(diào)用修改標記算法“寄存器對”情況避免使用swap——情況29.10.7利用代數(shù)特性優(yōu)化9.10.8公共子表達式的處理NP-完全問題dag森林，只有葉節(jié)點可為共享節(jié)點9.11動態(tài)規(guī)劃代碼生成算法一條指令使用兩個以上寄存器Ri:=EE包含一個或多個寄存器，有一個是RiADDR0,R1R1:=R1+R0

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