編譯原理 代碼生成

第九章代碼生成學習內容目標機器存儲管理基本塊、流圖簡單代碼生成算法寄存器分配窺孔優化基本塊dag表示、從dag生成代碼9.1設計中的問題輸入前端生成的中間表示形式線性化表示：后綴表示形式四元式表示：三地址碼虛擬機表示：抽象棧機器代碼圖形化表示：語法樹、DAG符號表信息類型檢查、類型轉換已完成輸入是無錯誤的設計中的問題（續）目標程序絕對機器語言固定內存地址，可直接執行可重定位機器語言多模塊連接靈活、分別編譯匯編語言簡單——符號指令、宏的使用設計中的問題（續）內存管理名字數據地址，與前端協作符號表標號指令地址backpatching技術設計中的問題（續）指令選擇指令集特性一致性、完整性指令速度、機器特性代碼質量：速度、大小豐富的指令集多種代碼生成方式選擇最高效方式設計問題（續）寄存器分配allocation、assignment最優化assignment——NP-完全問題register-pair計算順序調整計算順序提高效率NP-完全問題設計問題（續）代碼生成方法正確性是第一位的設計目標：易于實現、測試、維護9.6節：生成算法，9.9節：窺孔優化9.7節：寄存器使用算法——控制流9.10、9.11節：代碼選擇9.12節：代碼生成——樹重構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運行時存儲管理靜態分配，棧分配翻譯如下三地址碼callreturnhaltaction9.3.1靜態分配call翻譯為MOV#here,callee.static_areaGOTOcallee.code_areareturn翻譯為GOTO*callee.static_area當前代碼地址被調用函數的靜態區域被調用函數的代碼區域例9.1三地址碼/*c的代碼

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

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

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

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

MOV#stackstart,SP

第一個過程的代碼

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

/*p的代碼*/200: ACTION3220: GOTO*0(SP) /*return*/ …例9.2（續） /*q的代碼*/300: ACTION4 /*條件轉移到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位于靜態分配區域，地址staticstatic[12]:=0static=100MOV#0,112display方式，地址在寄存器R3中t1:=12+R3

*t1:=0MOV#0,12(R3)9.4基本塊和流圖9.4.1基本塊，basicblock連續語句序列，執行過程中沒有分支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，基本塊的第一個語句）集，確定規則：程序的第一條語句條件轉移或無條件轉移語句的目的語句條件轉移或無條件轉移語句之后的語句每個leader對應的基本塊：

leader——下個leader（或程序尾）例9.3begin prod:=0 i:=1 dobegin prod:=prod+a[i]*b[i]; i:=i+1 end whilei<=20end例9.3（續）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基本塊的變換基本塊進行表達式計算等價——計算相同的表達式變換——不改變計算的表達式集合提高代碼質量保結構變換

structure-preservingtransformation代數變換

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

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

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

當前每個寄存器內容，分配新寄存器時用

初始：所有寄存器均空

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

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

寄存器、棧位置或是內存地址

可能在多個位置9.6.2代碼生成算法輸入：基本塊，對每個語句x:=yopz：為計算結果分配位置L——getreg提取y的值查詢y的位置y’——地址描述符，寄存器優先y’<>L——MOVy’,L生成計算指令查詢z的位置z’OPz’,L更新x的地址描述符和L的寄存器描述符若y、z不再被引用，從寄存器描述符刪除特殊情況一元運算：省略z的部分x:=y，根據y的位置寄存器L：修改寄存器描述符和地址描述符x也（僅）在L中內存：getreg，得到的寄存器保存x和yx不再被引用：MOVy,x特殊情況基本塊出口，將活躍名字值存入內存寄存器描述符哪些名字保存在寄存器中地址描述符名字對應的內存地址活躍信息是否需要保存9.6.3getreg算法x:=yopz，為x分配位置L，效率高低與y占用相同寄存器y的寄存器r不包含其他名字y不再活躍、不再被引用1）失敗，尋找一個空寄存器2）失敗，寄存器替換x還會被引用，或op操作需要使用寄存器——數組索引尋找已用寄存器R，x替換其中變量R中變量引用位置最遠，或已保存在內存中x不再被引用，或無合適寄存器——內存例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和

內存中9.6.4其他類型語句的代碼生成數組和指針語句i在寄存器Ri中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在內存Mp中p在棧中代碼開銷代碼開銷代碼開銷a:=*pMOV*Rp,a2MOVMp,RMOV*R,R3MOVSp(A),RMOV*R,R3*p:=aMOVa,*Rp2MOVMp,RMOVa,*R4MOVa,RMOVR,*Sp(A)59.6.5條件轉移語句兩種實現方式寄存器值符合六個條件之一：負數、零、正數、非負數、非零、非正數

ifx<ygotozx–y，if負數gotoz條件代碼

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

d:=d–b

e:=a+fB1acdefb:=d+f

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

use(a,B2)=use(a,B3)=1總共節省4b,c,d,e,f——6,3,6,4,4可將a、b、d保存在R0、R1、R2中例9.6（續）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外層循環的寄存器分配內層循環相同思想L1包含L2，x在L2中分配了寄存器，則在L1–L2不必再分配x在L1中分配了寄存器，而L2中沒有，則在L2入口需保存，出口需讀出x在L2中分配了寄存器，而L1中沒有，則在L2入口需讀取，出口需保存9.7.4圖著色法進行寄存器分配兩次掃描假定寄存器數目是無限的，選擇目標機器指令翻譯中間代碼——每個變量一個寄存器，符號寄存器分配物理寄存器寄存器沖突圖，register-interferencegraph節點——符號寄存器，R1—R2，R2定義的位置上R1活躍k——可用物理寄存器數，用k個顏色為圖著色相鄰節點不同顏色——干擾變量使用不同寄存器啟發式算法n鄰居數<k，去掉nG’，G’可k著色G可k著色最終——空圖（成功）或所有節點鄰居數>=n（失敗）9.8基本塊的DAG表示構造方法葉：標記變量或常量

左值/右值

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

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

a[j]:=y z:=x

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

若i=j，y≠a[i]，錯誤！注銷[]節點，不附加額外的標識符*p:=w，類似，可能需要注銷所有節點函數調用，注銷所有節點額外邊——保持原三地址碼語句順序哪些語句順序應予以保持前：數組元素的賦值語句

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

后：同一數組的元素的賦值語句前：函數調用、利用指針間接賦值

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

后：函數調用、利用指針間接賦值9.9窺孔（Peephole）優化窺孔：目標代碼一個小的、移動的窗口

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

打印調試信息

L2: if0<>1gotoL2

打印調試信息

L2：可刪除9.9.3控制流優化gotoL1 gotoL2… …L1:gotoL2 L1:gotoL2ifa<bgotoL1 ifa<bgotoL2… …L1:gotoL2 L1:gootL2gotoL1 ifa<bgotoL2… gotoL3L1:ifa<bgotoL2 …L3: L3:其他優化方法9.9.4代數優化x:=x+0，x:=x*19.9.5強度削弱開銷高的指令等價的開銷低的指令x2：乘方函數x*x9.9.6利用機器特性特殊機器指令高效實現某些操作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重排順序（續）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一個啟發式重排序算法計算緊接在左孩子之后（t4，t1）——共用一個寄存器算法（按逆序給出重排之后的順序）：while

存在未列出的內部節點do

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

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

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

elselabel(n):=0

elsebegin

令n1,n2,…,nk是n的孩子按標號排序后的結果，即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的代碼，結果在寄存器R0中rstack：可用寄存器棧，R0,R1,…,R(r-1)swap(rstack)：交換棧頂兩個寄存器tstack：臨時存儲棧，T0,T1,T2,…算法處理的幾種情況：算法gencode(n){ if(n為表示運算對象name的左葉節點且為其父節點的最左孩子)

print‘MOV’||name||‘,’||top(rstack); elseif(n是內部節點，運算符為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);算法（續） }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多寄存器運算乘、除、函數調用修改標記算法“寄存器對”情況避免使用swap——情況29.10.7利用代數特性優化9.10.8公共子表達式的處理NP-完全問題dag森林，只有葉節點可為共享節點9.11動態規劃代碼生成算法一條指令使用兩個以上寄存器Ri:=EE包含一個或多個寄存器，有一個是RiADDR0,R1R1:=R1+R0

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