編譯原理第12章 代碼生成

編譯原理之

代碼生成華東交通大學(xué)軟件學(xué)院萬(wàn)仲保代碼生成概述目標(biāo)代碼的主要目標(biāo)目標(biāo)代碼的主要形式生成目標(biāo)代碼衡量指標(biāo)計(jì)算機(jī)模型簡(jiǎn)單的代碼生成器全局寄存器分配代碼生成概述代碼生成是把經(jīng)過(guò)語(yǔ)法分析或優(yōu)化后的中間代碼作為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語(yǔ)言或匯編語(yǔ)言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器。代碼生成的任務(wù)是在編譯前端生成的中間代碼的基礎(chǔ)上，生成等價(jià)有效的目標(biāo)代碼，這也是一種程序變換，變換的結(jié)果是產(chǎn)生目標(biāo)代碼。等價(jià)是任一種程序變換的基本要求，因此討論將集中在目標(biāo)代碼和如何產(chǎn)生有效的目標(biāo)代碼上。有效，是指目標(biāo)代碼占用的空間要省，運(yùn)行的時(shí)間要短，這涉及充分利用寄存器和生成優(yōu)化的代碼序列的問(wèn)題。目標(biāo)代碼的主要目標(biāo)第一．使所生成的目標(biāo)代碼盡可能地短。第二，能較充分地發(fā)揮目標(biāo)計(jì)算機(jī)可用資源的效率，如盡可能地使用執(zhí)行速度較快的指令；充分利用計(jì)算機(jī)的寄存器或變址器，以節(jié)省訪問(wèn)內(nèi)存的時(shí)間，等等。目標(biāo)代碼的主要形式具有絕對(duì)地址的機(jī)器語(yǔ)言程序可浮動(dòng)的機(jī)器語(yǔ)言程序匯編語(yǔ)言形式的程序絕對(duì)地址的機(jī)器語(yǔ)言程序優(yōu)點(diǎn)：最為有效，因?yàn)樗鼈冊(cè)诖鎯?chǔ)空間中有固定的位置，一旦產(chǎn)生出此種形式的目標(biāo)程序之后，便可直接投入運(yùn)行。缺點(diǎn)：不能獨(dú)立地完成源程序各程序塊的編譯，即使是供源程序調(diào)用的子程序也必須同時(shí)進(jìn)行編譯，因而靈活性較差。通常是在程序較短，而調(diào)試工作量較大的情況下，采用此種方式。可浮動(dòng)的機(jī)器語(yǔ)言程序有較大的靈活性，故為許多編譯程序所采用，只有執(zhí)行連接裝入程序本身需耗費(fèi)一些時(shí)間。目標(biāo)程序由若干個(gè)目的模塊組成，各個(gè)模塊中都包含目標(biāo)程序中的一部分代碼，且這些代碼可在存儲(chǔ)空間進(jìn)行浮動(dòng)(即可將它們裝入到存儲(chǔ)空間的任何位置)。此外，在各目的模塊中還含有一些連接信息(如本模塊需引用的其它模塊中的符號(hào)名或子程序入口名)。對(duì)此種形式的目標(biāo)代碼，需經(jīng)過(guò)連接裝入程序把它們和所需的運(yùn)行子程序的目的模塊連接起來(lái)之后，才能投入運(yùn)行。匯編語(yǔ)言形式的程序匯編語(yǔ)言形式較容易實(shí)現(xiàn)一些，但需在編譯完畢之后額外增加一個(gè)匯編目標(biāo)程序的階段。盡管此種方式有某些優(yōu)點(diǎn)，但并不是一種最好的方案。計(jì)算機(jī)模型假定一個(gè)計(jì)算機(jī)具有n個(gè)通用寄存器為R0，R1，…，Rn-l。它們既可作為累加器又可作為變址器，設(shè)定：用“op”表示運(yùn)算符；用“M”表示內(nèi)存單元；用變量名表示該變量所在的單元；“C”表示常量；“*”表示間址方式存取。模型機(jī)的指令形式模型機(jī)主要指令的意義模型機(jī)尋址方式模型機(jī)的指令形式類型指令形式意義（設(shè)op是二目運(yùn)算符）直接地址型opRi,M(Ri)opM?Ri寄存器型opRi,Rj(Ri)op(Rj)?Ri變址型opRi,c(Rj)(Ri)op((Rj)+c)?Ri間接型opRi,*M(Ri)op(M)?RiopRi,*Rj(Ri)op((Rj))?RiopRi,*c(Rj)(Ri)op(((Rj)+c))?Ri模型機(jī)主要指令的意義指令意義指令意義LDRi，B把B單元的內(nèi)容取到寄存器R，即(B)?RiJ<XJ≤X如CT＝0轉(zhuǎn)X單元。如CT=0或CT＝1轉(zhuǎn)X單元。STRi，B把寄存器Ri的內(nèi)容存到B單元，即(Ri)?BJ=X如CT＝1轉(zhuǎn)X單元。JB無(wú)條件轉(zhuǎn)向X單元J≠X如CT≠1轉(zhuǎn)X單元。CMPA，B把A單元和B單元的值進(jìn)行比較，并根據(jù)比較情況把機(jī)器內(nèi)部特征寄存器CT置成相應(yīng)狀態(tài)。根據(jù)A＜B或A＝B或A>B分別置CT為0或1或2。J>X

J≥X如CT＝2轉(zhuǎn)X單元。如CT＝2或CT=1轉(zhuǎn)X單元。模型機(jī)尋址方式編碼名稱助記符含義匯編后的情況1寄存器模式R(R)為操作數(shù)2間接寄存模式*R(R)為操作數(shù)地址3變址模式X(R)(R)+X為操作數(shù)地址X之值在本指令之后的單元中4間接變址模式*X(R)(R)+X為存放操作數(shù)地址的單元地址X之值在本指令之后的單元中5直接操作數(shù)#XX為操作數(shù)文字常數(shù)X在本指令之后的單元中6絕對(duì)地址XX為符號(hào)名，其值為操作數(shù)X的數(shù)據(jù)單元地址在本指令之后的單元中7間接地址*XX為符號(hào)名，其值為操作數(shù)地址X的數(shù)據(jù)單元地址在本指令之后的單元中生成目標(biāo)代碼衡量指標(biāo)目標(biāo)程序（指令條數(shù)）；執(zhí)行目標(biāo)程序所占的機(jī)器時(shí)間；目標(biāo)程序所有指令執(zhí)行代價(jià)的總和。簡(jiǎn)單的代碼生成器寄存器分配的原則待用信息鏈表法代碼生成算法寄存器分配的原則(1)當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中直到寄存器不夠分配時(shí)為止，這樣引用變量值時(shí)可減少對(duì)內(nèi)存的存取次數(shù)，以提高運(yùn)行速度。(2)當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié)點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口前存放的R可能不同，或沒(méi)有定值，所以應(yīng)在出口前把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。(3)對(duì)于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。待用信息鏈表法待用信息：在基本塊B中，變量A在i點(diǎn)的值，j點(diǎn)引用，并且i→j的通路上沒(méi)有A的其他定值和引用，則j為i處A的下一個(gè)引用點(diǎn)，即待用信息。計(jì)算變量待用信息的步驟示例計(jì)算變量待用信息的步驟(1)對(duì)各基本塊的符號(hào)表中的“待用信息”欄和“活躍信息”欄置初值，即把“待用作息”欄置“非待用”，對(duì)“活躍信息”欄按在基本塊出口處是否為活躍而置成“活躍”或“非活躍”。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。(2)從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式i：A：=BopC，依次執(zhí)行下述步驟：a)把符號(hào)表中變量A的待用信息和活躍信息附加到四元式i上。b)把符號(hào)表中變量A的待用信息欄和活躍信息欄分別置為“非待用”和“非活躍”。(由于在i中對(duì)A的定值只能在i以后的四元式才能引用，因而對(duì)i以前的四元式卻說(shuō)，A是不活躍也不可能是待用的）c)把符號(hào)表中B和C的待用信息和活躍信息附加到四元式i上。d)把符號(hào)表中B和C的待用信息欄置為“i”，活躍信息欄置為“活躍”。注意，以上a)和b)，c)和d)的次序不能顛倒。計(jì)算變量待用信息的示例例若用A，B，C，D表示變量，用T，U，V表示中間變量，有四元式如下：(1)T：=A-B(2)U：=A-C(3)V：=T+U(4)D：=V+U待用信息和活躍信息在四元式上的標(biāo)記四元式的序號(hào)四元式上的標(biāo)記(1)T(3)L：=A(2)L-BFL

(2)U(3)L：=AFL-CFL(3)V(4)L：=TFF+U(4)L

(4)DFL：=VFF+UFF代碼生成算法寄存器描述:為了在代碼生成中充分利用寄存器，生成盡可能簡(jiǎn)短的代碼，將使用寄存器描述數(shù)組RVALUE[Ri]記錄寄存器Ri是空閑著，還是已分配給某些變量。地址描述：將使用變量地址描述數(shù)組AVALUE[A]來(lái)記錄變量A的現(xiàn)行值是存放在某個(gè)寄存器中，還是在某個(gè)主存單元中，或者既在寄存器中又在主存中。相關(guān)約定GETREG分配寄存器的算法代碼生成算法相關(guān)約定過(guò)程函數(shù)GETREG(P:x:=yopz)給出參數(shù)P：x:=yopz，當(dāng)然也意味著給出了語(yǔ)句P處的待用信息、活躍信息及當(dāng)時(shí)各寄存器描述數(shù)組和變量地址描述數(shù)組，據(jù)此，為變量x分配寄存器R，以R作為函數(shù)值返回。RVALUE[Ri]＝{A，C}表示Ri的現(xiàn)行值是變量A，C的值。VALUE[A]＝{A}表示A的值在內(nèi)存中。AVALUE[A]＝{Ri，A}表示A的值在寄存器Ri中又在內(nèi)存中。AVALUE[A]＝{Ri}表示變量A的值在寄存器Ri中。GETREG分配寄存器的算法(1)如果B的現(xiàn)行值在某寄存器Ri中，且該寄存器只包含B的值，或者B與A是同一標(biāo)識(shí)符，或B在該四元式后不會(huì)再被引用，則可選取Ri為所需的寄存器R，并轉(zhuǎn)(4)。(2)如果有尚未分配的寄存器，則從中選用一個(gè)Ri為所需的寄存器R，并轉(zhuǎn)(4)。(3)從已分配的寄存器中選取一個(gè)Ri作為所需寄存器R，其選擇原則為：占用該寄存器的變量值同時(shí)在主存中，或在基本塊中引用的位置最遠(yuǎn)。這樣對(duì)寄存器Ri所含的變量和變量在主存中的情況必須先做如下調(diào)整：即對(duì)RVALU[Ri]中的每一變量M，如果M不是A且AVALUE[M]不包含M，則需完成以下處理：a)生成目標(biāo)代碼STRi，M；即把不是A的變量值由Ri中送入內(nèi)存中。b)如果M不是B，則令A(yù)VALUE[M]={M}，否則，令A(yù)VALUE[M]={M，R}。c)刪除RVALU[Ri]中的M。(4)給出R，返回。這樣，一旦得到了一個(gè)為四元式運(yùn)算的操作寄存器R，就可以進(jìn)行代碼生成，而當(dāng)目標(biāo)代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。算法的流程圖GETREG算法的流程圖開(kāi)始B’=R?C’=R?B’是否待用?B’=Ri?C’是否待用?C’=Ri?修改B的地址描述AVALUE[B]：=AVALUE[B]-{R}修改C的地址描述AVALUE[C]：=AVALUE[C]-{R}修改A的地址描述AVALUE[A]：={R}AVALUE[R]：={A}釋放B所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{B}AVALUE[B]：=AVALUE[B]-{Ri}釋放C所占用的寄存器RiRVALUE[Ri]：=RVALUE[Ri]-{C}AVALUE[C]：=AVALUE[C]-{Ri}結(jié)束YNYYYNNNNYY代碼生成算法對(duì)于語(yǔ)句P：x:=yopz，執(zhí)行下列步驟：(1)調(diào)用GETREG(P：x:=yopz)，設(shè)返回的寄存器為R，供x存放現(xiàn)行值。(2)由變量地址描述數(shù)組AVALUE[y]、AVALUE[z]確定變量y、z的現(xiàn)行值存放位置y′，z′，當(dāng)現(xiàn)行值在寄存器中時(shí)，便將該寄存器作為y′或z′。(3)如果y′≠R，生成目標(biāo)代碼MOVy′RopRz′否則只生成目標(biāo)代碼opRz′。當(dāng)y′或z′為R時(shí)，刪除AVALUE[y]或AVALUE[z]中的R。(4)修改兩個(gè)描述數(shù)組，表示x占用R，即含AVALUE[x]={R}，RVALUE[R]={x}。

(5)如果在P點(diǎn)y或z不再被引用(不待用，不活躍)，并且其現(xiàn)行值占用某寄存器R′，則釋放該寄存器R′，即從RVALUE[R′]中刪去y或z，從AVALUE[y]或AVALUE[z]中刪去R′。代碼生成算法的流程圖開(kāi)始結(jié)束分配操作寄存器R：GETREG（i：A：=BopC）取B，C現(xiàn)行存放的位置B’，C’B：=AVALUE[B]C：=AVALUE[C]B’=R?生成目標(biāo)碼opRC’生成目標(biāo)碼LDR，B’opRC’修改寄存器使用的信息和地址描述信息YN全局寄存器分配四元式的目標(biāo)代碼形式分配寄存器的原則：降低目標(biāo)代碼執(zhí)行代價(jià)。分配寄存器的策略計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù)計(jì)算執(zhí)行代價(jià)需考慮因素示例四元式的目標(biāo)代碼形式四元式指令說(shuō)明A：=BMOVB，R若當(dāng)前B的值在其一寄存器R中，則不必產(chǎn)生目標(biāo)代碼，而只須把A添加到R的描述符中，并把A的地址描述符置為R(即指明A的當(dāng)前值僅在R中)即可。當(dāng)B在塊中不再被引用且在塊的出口之后不活躍時(shí)，還應(yīng)從R的描述符中刪去B，從B的地址描述符中刪去R。但若B的當(dāng)前值只在內(nèi)存單元中，如果僅簡(jiǎn)單地把A的地址描述符置為B的內(nèi)存地址，那么，若不對(duì)A的值采取保護(hù)措施，A的值就會(huì)為B的再定值所影響?？梢?jiàn)，在此情況下，還是為它產(chǎn)生一條形如MOVB，R的指令較為穩(wěn)妥。R是分配給A的寄存器。A：=opB對(duì)它的處理與對(duì)二元運(yùn)算的處理極為類似。A：=B[I]MOVI，RMOVB(R),R執(zhí)行代價(jià)為5，I的當(dāng)前值不在寄存器中，則產(chǎn)生之。MOVB(Ri),R執(zhí)行代價(jià)為3，I的當(dāng)前值在某一寄存器Ri中時(shí)，則僅產(chǎn)生之。A[T]:=BMOVI,RMOVB,A(Ri)執(zhí)行代價(jià)為6，I的當(dāng)前值不在寄存器中，則產(chǎn)生之。MOVB,A(Ri)執(zhí)行代價(jià)為4，I的當(dāng)前值在某一寄存器Ri中時(shí)，則僅產(chǎn)生之。四元式的目標(biāo)代碼形式(二)四元式指令說(shuō)明A:=P↑MOV*P,A執(zhí)行代價(jià)為4MOVP,RMOV*R,R執(zhí)行代價(jià)為4MOV*Ri,R2，特別，當(dāng)P的當(dāng)前值在某一寄存器R6中時(shí)，可產(chǎn)生的指令。如果A的當(dāng)前值在塊內(nèi)還會(huì)被引用，且此時(shí)尚有未被占用的寄存器R供A使用，則最好按第二或第三種形式產(chǎn)生目標(biāo)代碼。P↑:=AMOVA,*PMOVA,RMOVR,*PMOVA,*RgotoXBRX’X’是序號(hào)為X的四元式的目標(biāo)代碼首址。IfAropbgotoXCMPA,BJropX’X’是序號(hào)為X的四元式的目標(biāo)代碼首址。如果A和(或)B的當(dāng)前值在寄存器中，則在產(chǎn)生目標(biāo)代碼時(shí)，應(yīng)盡可能用寄存器尋址模式。分配寄存器的策略首先，所考慮的范圍需從一個(gè)基本塊擴(kuò)大至一個(gè)循環(huán)L，故對(duì)于在L的某基本塊B中定值的變量V，如果它已占用一個(gè)固定的寄存器，而且V在B的出口之后活躍，則不必再把V的值存放到內(nèi)存單元之中。其次，對(duì)于循環(huán)中的每一變量V，還需估計(jì)當(dāng)它獨(dú)占一個(gè)寄存器時(shí)，對(duì)于降低執(zhí)行代價(jià)的效果有多大。顯然，應(yīng)將寄存器優(yōu)先分配給那些降低執(zhí)行代價(jià)效果最為顯著的一些變量。計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法如果V在B中被定值，且V的定值點(diǎn)之后有其引用點(diǎn)，則按生成代碼算法為B生成代碼時(shí)，一般是把V的當(dāng)前值保留在某一寄存器R中。如果在整個(gè)循環(huán)L中，把R作為V的一個(gè)獨(dú)占寄存器，則對(duì)于基本塊B而言，不僅V的定值點(diǎn)之后的引用點(diǎn)可引用R中之值，而且其前的V的引用點(diǎn)也可以引用(甚至在L的其它基本塊中也同樣可以引用，如果該V的定值能到達(dá)這些引用點(diǎn)的話)。然而，在生成代碼算法中，僅考慮了前一情況，而對(duì)后一情況卻未加以考慮(因?yàn)樯纱a算法并未把R作為V的一個(gè)獨(dú)占寄存器)，因此，在現(xiàn)在的情況下，對(duì)于B中V的定值點(diǎn)之前的那些四元式，如果在為它們生成目標(biāo)代碼時(shí)，也把對(duì)v的引用處理為對(duì)R內(nèi)容的引用，則使其中的每一個(gè)對(duì)V的引用都節(jié)省了執(zhí)行代價(jià)1。由于現(xiàn)在已為B中的變量V分配了固定的寄存器，因此，當(dāng)V在B的出口之后活躍時(shí)，也就不必把V的值送入內(nèi)存，這樣一來(lái)，就使執(zhí)行代價(jià)又節(jié)省了2。執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù)對(duì)于循環(huán)L中的某一變量，當(dāng)給它分配了一個(gè)固定的寄存器之后，則每執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù)(相對(duì)于按代碼生成算法生成的代碼)為：

＝(USE(V，B)+2*LIVE(V，B))（B?L）其中：USE(V，B)為基本塊B中V的定值點(diǎn)之前對(duì)V引用的次數(shù)；1當(dāng)V在B中定值，且V在B的出口之后活躍LIVE（V，B）＝0其它計(jì)算執(zhí)行代價(jià)需考慮因素1．若V在L的入口之前是活躍的，且在L中已給V分配了固定的寄存器R，則應(yīng)在L的前置結(jié)點(diǎn)中，產(chǎn)生將V之值從內(nèi)存單元取至R的指令，故所增加的執(zhí)行代價(jià)為2。此外，對(duì)于循環(huán)的每一出口塊B，設(shè)B’是B在循環(huán)外的一個(gè)直接后繼塊，若V在B’前活躍，則當(dāng)由B退出循環(huán)時(shí)，應(yīng)將V的當(dāng)前值由R送入內(nèi)存，由此可能增加的執(zhí)行代價(jià)為2，好在上述兩方面的操作僅分別在循環(huán)的入口之前和退出循環(huán)時(shí)執(zhí)行一次，故將它們略去不計(jì)將不會(huì)對(duì)之值產(chǎn)生太大的影響。2．執(zhí)行代價(jià)計(jì)算公式是在這樣的假定下推出的，即每循環(huán)一次都遍及循環(huán)中的各個(gè)基本塊，然而實(shí)際情況并非總是如此，有時(shí)甚至?xí)?/p>