編譯原理第12章 代碼生成

1、編譯原理之編譯原理之 代碼生成代碼生成 華東交通大學(xué)軟件學(xué)院華東交通大學(xué)軟件學(xué)院 萬仲保萬仲保 代碼生成代碼生成 v概述概述 v目標(biāo)代碼的主要目標(biāo)目標(biāo)代碼的主要目標(biāo) v目標(biāo)代碼的主要形式目標(biāo)代碼的主要形式 v生成目標(biāo)代碼衡量指標(biāo)生成目標(biāo)代碼衡量指標(biāo) v計(jì)算機(jī)模型計(jì)算機(jī)模型 v簡單的代碼生成器簡單的代碼生成器 v全局寄存器分配全局寄存器分配 代碼生成概述代碼生成概述 v代碼生成是把經(jīng)過語法分析或優(yōu)化后的中間代碼作代碼生成是把經(jīng)過語法分析或優(yōu)化后的中間代碼作 為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語言或匯編語為輸入，將其轉(zhuǎn)換成特定機(jī)器的機(jī)器語言或匯編語 言作為輸出，這樣的轉(zhuǎn)換程序稱為代碼生成器。言作為輸

2、出，這樣的轉(zhuǎn)換程序稱為代碼生成器。 v代碼生成的任務(wù)是在編譯前端生成的中間代碼的基代碼生成的任務(wù)是在編譯前端生成的中間代碼的基 礎(chǔ)上，生成等價(jià)有效的目標(biāo)代碼，這也是一種程序礎(chǔ)上，生成等價(jià)有效的目標(biāo)代碼，這也是一種程序 變換，變換的結(jié)果是產(chǎn)生目標(biāo)代碼。變換，變換的結(jié)果是產(chǎn)生目標(biāo)代碼。 v等價(jià)是任一種程序變換的基本要求，因此討論將集等價(jià)是任一種程序變換的基本要求，因此討論將集 中在目標(biāo)代碼和如何產(chǎn)生有效的目標(biāo)代碼上。中在目標(biāo)代碼和如何產(chǎn)生有效的目標(biāo)代碼上。 v有效，是指目標(biāo)代碼占用的空間要省，運(yùn)行的時(shí)間有效，是指目標(biāo)代碼占用的空間要省，運(yùn)行的時(shí)間 要短，這涉及充分利用寄存器和生成優(yōu)化的代碼序要短，

3、這涉及充分利用寄存器和生成優(yōu)化的代碼序 列的問題。列的問題。 目標(biāo)代碼的主要目標(biāo)目標(biāo)代碼的主要目標(biāo) v第一使所生成的目標(biāo)代碼盡可能地短。第一使所生成的目標(biāo)代碼盡可能地短。 v第二，能較充分地發(fā)揮目標(biāo)計(jì)算機(jī)可用資源第二，能較充分地發(fā)揮目標(biāo)計(jì)算機(jī)可用資源 的效率，如盡可能地使用執(zhí)行速度較快的指的效率，如盡可能地使用執(zhí)行速度較快的指 令；充分利用計(jì)算機(jī)的寄存器或變址器，以令；充分利用計(jì)算機(jī)的寄存器或變址器，以 節(jié)省訪問內(nèi)存的時(shí)間，等等。節(jié)省訪問內(nèi)存的時(shí)間，等等。 目標(biāo)代碼的主要形式目標(biāo)代碼的主要形式 v具有絕對地址的機(jī)器語言程序具有絕對地址的機(jī)器語言程序 v可浮動的機(jī)器語言程序可浮動的機(jī)器語言程序

4、v匯編語言形式的程序匯編語言形式的程序 絕對地址的機(jī)器語言程序絕對地址的機(jī)器語言程序 v優(yōu)點(diǎn)：最為有效，因?yàn)樗鼈冊诖鎯臻g中有優(yōu)點(diǎn)：最為有效，因?yàn)樗鼈冊诖鎯臻g中有 固定的位置，一旦產(chǎn)生出此種形式的目標(biāo)程固定的位置，一旦產(chǎn)生出此種形式的目標(biāo)程 序之后，便可直接投入運(yùn)行。序之后，便可直接投入運(yùn)行。 v缺點(diǎn)：不能獨(dú)立地完成源程序各程序塊的編缺點(diǎn)：不能獨(dú)立地完成源程序各程序塊的編 譯，即使是供源程序調(diào)用的子程序也必須同譯，即使是供源程序調(diào)用的子程序也必須同 時(shí)進(jìn)行編譯，因而靈活性較差。時(shí)進(jìn)行編譯，因而靈活性較差。 v通常是在程序較短，而調(diào)試工作量較大的情通常是在程序較短，而調(diào)試工作量較大的情 況下，

5、采用此種方式。況下，采用此種方式。 可浮動的機(jī)器語言程序可浮動的機(jī)器語言程序 v有較大的靈活性，故為許多編譯程序所采用，只有有較大的靈活性，故為許多編譯程序所采用，只有 執(zhí)行連接裝入程序本身需耗費(fèi)一些時(shí)間。執(zhí)行連接裝入程序本身需耗費(fèi)一些時(shí)間。 v目標(biāo)程序由若干個(gè)目的模塊組成，各個(gè)模塊中都包目標(biāo)程序由若干個(gè)目的模塊組成，各個(gè)模塊中都包 含目標(biāo)程序中的一部分代碼，且這些代碼可在存儲含目標(biāo)程序中的一部分代碼，且這些代碼可在存儲 空間進(jìn)行浮動空間進(jìn)行浮動(即可將它們裝入到存儲空間的任何位即可將它們裝入到存儲空間的任何位 置置)。 v此外，在各目的模塊中還含有一些連接信息此外，在各目的模塊中還含有一些連

6、接信息(如本模如本模 塊需引用的其它模塊中的符號名或子程序入口名塊需引用的其它模塊中的符號名或子程序入口名)。 v對此種形式的目標(biāo)代碼，需經(jīng)過連接裝入程序把它對此種形式的目標(biāo)代碼，需經(jīng)過連接裝入程序把它 們和所需的運(yùn)行子程序的目的模塊連接起來之后，們和所需的運(yùn)行子程序的目的模塊連接起來之后， 才能投入運(yùn)行。才能投入運(yùn)行。 匯編語言形式的程序匯編語言形式的程序 v匯編語言形式較容易實(shí)現(xiàn)一些，但匯編語言形式較容易實(shí)現(xiàn)一些，但 需在編譯完畢之后額外增加一個(gè)匯需在編譯完畢之后額外增加一個(gè)匯 編目標(biāo)程序的階段。編目標(biāo)程序的階段。 v盡管此種方式有某些優(yōu)點(diǎn)，但并不盡管此種方式有某些優(yōu)點(diǎn)，但并不 是一種最好

7、的方案。是一種最好的方案。 計(jì)算機(jī)模型計(jì)算機(jī)模型 v 假定一個(gè)計(jì)算機(jī)具有假定一個(gè)計(jì)算機(jī)具有n個(gè)通用寄存器為個(gè)通用寄存器為R0，R1， R n-l。它們既可作為累加器又可作為變址器，設(shè)定：。它們既可作為累加器又可作為變址器，設(shè)定： 用用“op”表示運(yùn)算符；表示運(yùn)算符； 用用“M”表示內(nèi)存單元；表示內(nèi)存單元； 用變量名表示該變量所在的單元；用變量名表示該變量所在的單元； “C”表示常量；表示常量； “*”表示間址方式存取。表示間址方式存取。 v 模型機(jī)的指令形式模型機(jī)的指令形式 v 模型機(jī)主要指令的意義模型機(jī)主要指令的意義 v 模型機(jī)尋址方式模型機(jī)尋址方式 模型機(jī)的指令形式模型機(jī)的指令形式 類型類

8、型指令形式指令形式意義（設(shè)意義（設(shè)op是二目運(yùn)算符）是二目運(yùn)算符） 直接地址型直接地址型 op Ri,M(Ri)opM Ri 寄存器型寄存器型 op Ri, Rj(Ri)op(Rj) Ri 變址型變址型 op Ri, c(Rj)(Ri)op(Rj)+c) Ri 間接型間接型 op Ri,*M(Ri)op(M) Ri op Ri, *Rj(Ri)op(Rj) Ri op Ri, *c(Rj) (Ri)op(Rj)+c) Ri 模型機(jī)主要指令的意義模型機(jī)主要指令的意義 指令指令意義意義指令指令意義意義 LD Ri，B把把B單元的內(nèi)容取到寄單元的內(nèi)容取到寄 存器存器R，即，即(B) Ri J B分別

9、置分別置CT 為為0或或1或或2。 J X J X 如如CT2 轉(zhuǎn)轉(zhuǎn)X單元。單元。 如如CT2或或CT=1 轉(zhuǎn)轉(zhuǎn)X單元。單元。 模型機(jī)尋址方式模型機(jī)尋址方式 編碼編碼名名 稱稱助記符助記符含含 義義匯編后的情況匯編后的情況 1寄存器模式寄存器模式R(R)為操作數(shù)為操作數(shù) 2 間接寄存間接寄存 模式模式 * R(R)為操作數(shù)地址為操作數(shù)地址 3變址模式變址模式X(R)(R)+X為操作數(shù)地址為操作數(shù)地址 X之值在本指令之后的之值在本指令之后的 單元中單元中 4 間接變址間接變址 模式模式 *X(R) (R)+X為存放操作數(shù)為存放操作數(shù) 地址的單元地址地址的單元地址 X之值在本指令之后的之值在本指令

10、之后的 單元中單元中 5直接操作數(shù)直接操作數(shù)#XX為操作數(shù)為操作數(shù) 文字常數(shù)文字常數(shù)X在本指令之在本指令之 后的單元中后的單元中 6絕對地址絕對地址X X為符號名，其值為為符號名，其值為 操作數(shù)操作數(shù) X的數(shù)據(jù)單元地址在本的數(shù)據(jù)單元地址在本 指令之后的單元中指令之后的單元中 7間接地址間接地址*X X為符號名，其值為為符號名，其值為 操作數(shù)地址操作數(shù)地址 X的數(shù)據(jù)單元地址在本的數(shù)據(jù)單元地址在本 指令之后的單元中指令之后的單元中 生成目標(biāo)代碼衡量指標(biāo)生成目標(biāo)代碼衡量指標(biāo) v目標(biāo)程序（指令條數(shù)）；目標(biāo)程序（指令條數(shù)）； v執(zhí)行目標(biāo)程序所占的機(jī)器時(shí)間；執(zhí)行目標(biāo)程序所占的機(jī)器時(shí)間； v目標(biāo)程序所有指令

11、執(zhí)行代價(jià)的總和。目標(biāo)程序所有指令執(zhí)行代價(jià)的總和。 簡單的代碼生成器簡單的代碼生成器 v寄存器分配的原則寄存器分配的原則 v待用信息鏈表法待用信息鏈表法 v代碼生成算法代碼生成算法 寄存器分配的原則寄存器分配的原則 v(1)當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或 計(jì)算結(jié)果保留在寄存器中直到寄存器不夠分配時(shí)為計(jì)算結(jié)果保留在寄存器中直到寄存器不夠分配時(shí)為 止，這樣引用變量值時(shí)可減少對內(nèi)存的存取次數(shù)，止，這樣引用變量值時(shí)可減少對內(nèi)存的存取次數(shù)， 以提高運(yùn)行速度。以提高運(yùn)行速度。 v(2)當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，當(dāng)?shù)交緣K出口時(shí)，將變量的值

12、存放在內(nèi)存中， 因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié)因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié) 點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口 前存放的前存放的R可能不同，或沒有定值，所以應(yīng)在出口前可能不同，或沒有定值，所以應(yīng)在出口前 把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口 的變量值都在內(nèi)存中。的變量值都在內(nèi)存中。 v(3)對于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占對于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占 用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。用的寄存器應(yīng)盡早釋放，以提高寄存器的利用

13、效率。 待用信息鏈表法待用信息鏈表法 v待用信息：待用信息： 在基本塊在基本塊B中，變量中，變量A在在i點(diǎn)的值，點(diǎn)的值，j點(diǎn)引用，并且點(diǎn)引用，并且 ij的通路上沒有的通路上沒有A的其他定值和引用，則的其他定值和引用，則j為為i處處 A的下一個(gè)引用點(diǎn)，即待用信息。的下一個(gè)引用點(diǎn)，即待用信息。 v計(jì)算變量待用信息的步驟計(jì)算變量待用信息的步驟 v示例示例 計(jì)算變量待用信息的步驟計(jì)算變量待用信息的步驟 v(1)對各基本塊的符號表中的對各基本塊的符號表中的“待用信息待用信息”欄和欄和“活躍信息活躍信息” 欄置初值，即把欄置初值，即把“待用作息待用作息”欄置欄置“非待用非待用”，對，對“活躍信活躍信 息息

14、”欄按在基本塊出口處是否為活躍而置成欄按在基本塊出口處是否為活躍而置成“活躍活躍”或或“非非 活躍活躍”。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。 v(2)從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式 i：A：=B op C，依次執(zhí)行下述步驟：，依次執(zhí)行下述步驟： a)把符號表中變量把符號表中變量A的待用信息和活躍信息附加到四元式的待用信息和活躍信息附加到四元式i上。上。 b)把符號表中變量把符號表中變量A的待用信息欄和活躍信息欄分別置為的待用信息欄和活躍信息欄分別置為“非待用非待用”

15、和和“非活躍非活躍”。(由于在由于在i中對中對A的定值只能在的定值只能在i以后的四元式才能引用，以后的四元式才能引用， 因而對因而對i以前的四元式卻說，以前的四元式卻說，A是不活躍也不可能是待用的）是不活躍也不可能是待用的） c)把符號表中把符號表中B和和C的待用信息和活躍信息附加到四元式的待用信息和活躍信息附加到四元式i上。上。 d)把符號表中把符號表中B和和C的待用信息欄置為的待用信息欄置為“i”，活躍信息欄置為，活躍信息欄置為“活躍活躍”。 v注意，以上注意，以上a)和和b)，c)和和d)的次序不能顛倒。的次序不能顛倒。 計(jì)算變量待用信息的示例計(jì)算變量待用信息的示例 v例例 若用若用A，

16、B，C，D表示變量，用表示變量，用T，U，V表表 示中間變量，有四元式如下：示中間變量，有四元式如下： v(1)T：=A-B (2)U：=A-C v(3)V：=T+U (4)D：=V+U v待用信息和活躍信息在待用信息和活躍信息在四元式上的標(biāo)記四元式上的標(biāo)記 四元式的序號 四元式上的標(biāo)記四元式上的標(biāo)記 v(1)T(3)L：=A(2)L -BFL v(2)U(3)L ：=AFL-CFL v(3)V(4)L ：=TFF+U(4)L v(4)DFL：=VFF+UFF 代碼生成算法代碼生成算法 v寄存器描述寄存器描述: 為了在代碼生成中充分利用寄存器，生成盡可能簡短的代為了在代碼生成中充分利用寄存器，

17、生成盡可能簡短的代 碼，將使用寄存器描述數(shù)組碼，將使用寄存器描述數(shù)組RVALUERi記錄寄存器記錄寄存器Ri是是 空閑著，還是已分配給某些變量?？臻e著，還是已分配給某些變量。 v地址描述：地址描述： 將使用變量地址描述數(shù)組將使用變量地址描述數(shù)組AVALUEA來記錄變量來記錄變量A的現(xiàn)行的現(xiàn)行 值是存放在某個(gè)寄存器中，還是在某個(gè)主存單元中，或者值是存放在某個(gè)寄存器中，還是在某個(gè)主存單元中，或者 既在寄存器中又在主存中。既在寄存器中又在主存中。 v相關(guān)約定相關(guān)約定 vGETREG分配寄存器的算法分配寄存器的算法 v代碼生成算法代碼生成算法 相關(guān)約定相關(guān)約定 v過程函數(shù)過程函數(shù)GETREG(P:x:

18、=y op z) 給出參數(shù)給出參數(shù)P：x:=y op z，當(dāng)然也意味著給出了語句，當(dāng)然也意味著給出了語句 P處的待用信息、活躍信息及當(dāng)時(shí)各寄存器描述處的待用信息、活躍信息及當(dāng)時(shí)各寄存器描述 數(shù)組和變量地址描述數(shù)組，據(jù)此，為變量數(shù)組和變量地址描述數(shù)組，據(jù)此，為變量x分配寄分配寄 存器存器R，以，以R作為函數(shù)值返回。作為函數(shù)值返回。 RVALUERiA，C表示表示Ri的現(xiàn)行值是變量的現(xiàn)行值是變量A，C的值。的值。 VALUEAA表示表示A的值在內(nèi)存中。的值在內(nèi)存中。 AVALUEA Ri，A表示表示A的值在寄存器的值在寄存器Ri中又在內(nèi)存中。中又在內(nèi)存中。 AVALUEA Ri表示變量表示變量A的

19、值在寄存器的值在寄存器Ri中。中。 GETREG分配寄存器的算法分配寄存器的算法 v(1)如果如果B的現(xiàn)行值在某寄存器的現(xiàn)行值在某寄存器Ri中，且該寄存器只包含中，且該寄存器只包含B的值，或者的值，或者B與與A是同是同 一標(biāo)識符，或一標(biāo)識符，或B在該四元式后不會再被引用，則可選取在該四元式后不會再被引用，則可選取Ri為所需的寄存器為所需的寄存器R， 并轉(zhuǎn)并轉(zhuǎn)(4)。 v(2)如果有尚未分配的寄存器，則從中選用一個(gè)如果有尚未分配的寄存器，則從中選用一個(gè)Ri為所需的寄存器為所需的寄存器R，并轉(zhuǎn)，并轉(zhuǎn)(4)。 v(3)從已分配的寄存器中選取一個(gè)從已分配的寄存器中選取一個(gè)Ri作為所需寄存器作為所需寄存

20、器R，其選擇原則為：，其選擇原則為： 占用該寄存器的變量值同時(shí)在主存中，或在基本塊中引用的位置最遠(yuǎn)。占用該寄存器的變量值同時(shí)在主存中，或在基本塊中引用的位置最遠(yuǎn)。 這樣對寄存器這樣對寄存器Ri所含的變量和變量在主存中的情況必須先做如下調(diào)整：所含的變量和變量在主存中的情況必須先做如下調(diào)整： 即對即對RVALURi 中的每一變量中的每一變量M，如果，如果M不是不是A且且AVALUEM不包含不包含M，則需完成，則需完成 以下處理：以下處理： a)生成目標(biāo)代碼生成目標(biāo)代碼ST Ri ，M；即把不是；即把不是A的變量值由的變量值由Ri中送入內(nèi)存中。中送入內(nèi)存中。 b)如果如果M不是不是B，則令，則令A(yù)V

21、ALUE M =M，否則，令，否則，令A(yù)VALUEM=M，R。 c)刪除刪除RVALURi 中的中的M。 v(4)給出給出R，返回。，返回。 v這樣，一旦得到了一個(gè)為四元式運(yùn)算的操作寄存器這樣，一旦得到了一個(gè)為四元式運(yùn)算的操作寄存器R，就可以進(jìn)行代碼生成，就可以進(jìn)行代碼生成， 而當(dāng)目標(biāo)代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。而當(dāng)目標(biāo)代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。 v算法的流程圖算法的流程圖 G E T R E G 算算 法法 的的 流流 程程 圖圖 開始開始 B=R? C=R? B是否是否 待用待用? B=Ri? C是否是否 待用待用? C=Ri?

22、 修改修改B的地址描述的地址描述 AVALUEB：=AVALUEB-R 修改修改C的地址描述的地址描述 AVALUEC：=AVALUEC-R 修改修改A的地址描述的地址描述 AVALUEA：= R AVALUER：=A 釋放釋放B所占用的寄存器所占用的寄存器Ri RVALUERi：=RVALUERi-B AVALUEB：= AVALUEB-Ri 釋放釋放C所占用的寄存器所占用的寄存器Ri RVALUERi：=RVALUERi-C AVALUEC：= AVALUEC-Ri 結(jié)束結(jié)束 Y N Y Y Y N N N N Y Y 代碼生成算法代碼生成算法 v對于語句對于語句P：x:=y op z，執(zhí)

23、行下列步驟：，執(zhí)行下列步驟： v(1) 調(diào)用調(diào)用GETREG(P：x:=y op z)，設(shè)返回的寄存器為，設(shè)返回的寄存器為R，供，供x存放現(xiàn)行值。存放現(xiàn)行值。 v(2) 由變量地址描述數(shù)組由變量地址描述數(shù)組AVALUEy、AVALUEz確定變量確定變量y、z的現(xiàn)行值的現(xiàn)行值 存放位置存放位置y，z，當(dāng)現(xiàn)行值在寄存器中時(shí)，便將該寄存器作為，當(dāng)現(xiàn)行值在寄存器中時(shí)，便將該寄存器作為y或或z。 v(3) 如果如果yR，生成目標(biāo)代碼，生成目標(biāo)代碼 MOV y R op R z 否則只生成目標(biāo)代碼否則只生成目標(biāo)代碼 op R z。 當(dāng)當(dāng)y或或z為為R時(shí)，刪除時(shí)，刪除AVALUEy或或AVALUEz中的中的

24、R。 v(4) 修改兩個(gè)描述數(shù)組，修改兩個(gè)描述數(shù)組， 表示表示x 占用占用R， 即含即含AVALUEx=R ， RVALUER=x。 v(5) 如果在如果在P點(diǎn)點(diǎn)y或或z不再被引用不再被引用(不待用，不活躍不待用，不活躍)，并且其現(xiàn)行值占用，并且其現(xiàn)行值占用 v某寄存器某寄存器R，則釋放該寄存器，則釋放該寄存器R，即從，即從RVALUER中刪去中刪去y或或 vz，從，從AVALUEy 或或AVALUEz中刪去中刪去R。 代代 碼碼 生生 成成 算算 法法 的的 流流 程程 圖圖 開始開始 結(jié)束結(jié)束 分配操作寄存器分配操作寄存器 R：GETREG（i：A：=B op C） 取取B，C現(xiàn)行存放的位

25、置現(xiàn)行存放的位置B，C B：=AVALUEB C：=AVALUEC B=R? 生成目標(biāo)碼生成目標(biāo)碼 op R C 生成目標(biāo)碼生成目標(biāo)碼 LD R，B op R C 修改寄存器使用的信息修改寄存器使用的信息 和地址描述信息和地址描述信息 Y N 全局寄存器分配全局寄存器分配 v四元式的目標(biāo)代碼形式四元式的目標(biāo)代碼形式 v分配寄存器的原則：分配寄存器的原則： 降低目標(biāo)代碼執(zhí)行代價(jià)。降低目標(biāo)代碼執(zhí)行代價(jià)。 v分配寄存器的策略分配寄存器的策略 v計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法 v執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù)執(zhí)行代價(jià)總數(shù) v計(jì)算執(zhí)行代價(jià)需考慮因素計(jì)算執(zhí)行代價(jià)

26、需考慮因素 v示例示例 四元式的目標(biāo)代碼形式四元式的目標(biāo)代碼形式 四元式四元式指令指令說明說明 A：=BMOV B，R 若當(dāng)前若當(dāng)前B的值在其一寄存器的值在其一寄存器R中，則不必產(chǎn)生目標(biāo)代碼，而只中，則不必產(chǎn)生目標(biāo)代碼，而只 須把須把A添加到添加到R的描述符中，并把的描述符中，并把A的地址描述符置為的地址描述符置為R(即指即指 明明A的當(dāng)前值僅在的當(dāng)前值僅在R中中)即可。即可。 當(dāng)當(dāng)B在塊中不再被引用且在塊的出口之后不活躍時(shí)，還應(yīng)從在塊中不再被引用且在塊的出口之后不活躍時(shí)，還應(yīng)從R 的描述符中刪去的描述符中刪去B，從，從B的地址描述符中刪去的地址描述符中刪去R。 但若但若B的當(dāng)前值只在內(nèi)存單元

27、中，如果僅簡單地把的當(dāng)前值只在內(nèi)存單元中，如果僅簡單地把A的地址描的地址描 述符置為述符置為B的內(nèi)存地址，那么，若不對的內(nèi)存地址，那么，若不對A的值采取保護(hù)措施，的值采取保護(hù)措施， A的值就會為的值就會為B的再定值所影響?？梢姡诖饲闆r下，還是為的再定值所影響?？梢?，在此情況下，還是為 它產(chǎn)生一條形如它產(chǎn)生一條形如 MOV B，R的指令較為穩(wěn)妥。的指令較為穩(wěn)妥。 R是分配給是分配給A的寄存器。的寄存器。 A：=op B對它的處理與對二元運(yùn)算的處理極為類似。對它的處理與對二元運(yùn)算的處理極為類似。 A：=BI MOV I，R MOV B(R),R 執(zhí)行代價(jià)為執(zhí)行代價(jià)為5，I的當(dāng)前值不在寄存器中，則

28、產(chǎn)生之。的當(dāng)前值不在寄存器中，則產(chǎn)生之。 MOV B(Ri),R執(zhí)行代價(jià)為執(zhí)行代價(jià)為3，I的當(dāng)前值在某一寄存器的當(dāng)前值在某一寄存器Ri中時(shí)，則僅產(chǎn)生之。中時(shí)，則僅產(chǎn)生之。 AT:=B MOV I,R MOV B,A(Ri) 執(zhí)行代價(jià)為執(zhí)行代價(jià)為6，I的當(dāng)前值不在寄存器中，則產(chǎn)生之。的當(dāng)前值不在寄存器中，則產(chǎn)生之。 MOV B,A(Ri)執(zhí)行代價(jià)為執(zhí)行代價(jià)為4，I的當(dāng)前值在某一寄存器的當(dāng)前值在某一寄存器Ri中時(shí)，則僅產(chǎn)生之。中時(shí)，則僅產(chǎn)生之。 四元式的目標(biāo)代碼形式四元式的目標(biāo)代碼形式(二二) 四元式四元式指令指令說明說明 A:=P MOV *P,A執(zhí)行代價(jià)為執(zhí)行代價(jià)為4 MOV P,R MOV

29、*R,R 執(zhí)行代價(jià)為執(zhí)行代價(jià)為4 MOV *Ri,R 2，特別，當(dāng)，特別，當(dāng)P的當(dāng)前值在某一寄存器的當(dāng)前值在某一寄存器R6中時(shí)，可中時(shí)，可 產(chǎn)生的指令。如果產(chǎn)生的指令。如果A的當(dāng)前值在塊內(nèi)還會被引用，的當(dāng)前值在塊內(nèi)還會被引用， 且此時(shí)尚有未被占用的寄存器且此時(shí)尚有未被占用的寄存器R供供A使用，則最好使用，則最好 按第二或第三種形式產(chǎn)生目標(biāo)代碼。按第二或第三種形式產(chǎn)生目標(biāo)代碼。 P:=A MOV A,*P MOV A,R MOV R,*P MOV A,*R goto XBR XX是序號為是序號為X的四元式的目標(biāo)代碼首址。的四元式的目標(biāo)代碼首址。 If A rop b goto X CMP A,B

30、 Jrop X X是序號為是序號為X的四元式的目標(biāo)代碼首址。如果的四元式的目標(biāo)代碼首址。如果A和和 (或或)B的當(dāng)前值在寄存器中，則在產(chǎn)生目標(biāo)代碼時(shí)，的當(dāng)前值在寄存器中，則在產(chǎn)生目標(biāo)代碼時(shí)， 應(yīng)盡可能用寄存器尋址模式。應(yīng)盡可能用寄存器尋址模式。 分配寄存器的策略分配寄存器的策略 v首先，所考慮的范圍需從一個(gè)基本塊擴(kuò)大至首先，所考慮的范圍需從一個(gè)基本塊擴(kuò)大至 一個(gè)循環(huán)一個(gè)循環(huán)L，故對于在，故對于在L的某基本塊的某基本塊B中定值中定值 的變量的變量V，如果它已占用一個(gè)固定的寄存器，如果它已占用一個(gè)固定的寄存器， 而且而且V在在B的出口之后活躍，則不必再把的出口之后活躍，則不必再把V的的 值存放到內(nèi)

31、存單元之中。值存放到內(nèi)存單元之中。 v其次，對于循環(huán)中的每一變量其次，對于循環(huán)中的每一變量V，還需估計(jì)當(dāng)，還需估計(jì)當(dāng) 它獨(dú)占一個(gè)寄存器時(shí)，對于降低執(zhí)行代價(jià)的它獨(dú)占一個(gè)寄存器時(shí)，對于降低執(zhí)行代價(jià)的 效果有多大。效果有多大。 v顯然，應(yīng)將寄存器優(yōu)先分配給那些降低執(zhí)行顯然，應(yīng)將寄存器優(yōu)先分配給那些降低執(zhí)行 代價(jià)效果最為顯著的一些變量。代價(jià)效果最為顯著的一些變量。 計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法計(jì)算目標(biāo)代碼執(zhí)行代價(jià)的方法 v如果如果V在在B中被定值，且中被定值，且V的定值點(diǎn)之后有其引用點(diǎn)，則按生的定值點(diǎn)之后有其引用點(diǎn)，則按生 成代碼算法為成代碼算法為B生成代碼時(shí)，一般是把生成代碼時(shí)，一般是把V的當(dāng)前值保留

32、在某一的當(dāng)前值保留在某一 寄存器寄存器R中。如果在整個(gè)循環(huán)中。如果在整個(gè)循環(huán)L中，把中，把R作為作為V的一個(gè)獨(dú)占寄的一個(gè)獨(dú)占寄 存器，則對于基本塊存器，則對于基本塊B而言，不僅而言，不僅V的定值點(diǎn)之后的引用點(diǎn)可的定值點(diǎn)之后的引用點(diǎn)可 引用引用R中之值，而且其前的中之值，而且其前的V的引用點(diǎn)也可以引用的引用點(diǎn)也可以引用(甚至在甚至在L的的 其它基本塊中也同樣可以引用，如果該其它基本塊中也同樣可以引用，如果該V的定值能到達(dá)這些的定值能到達(dá)這些 引用點(diǎn)的話引用點(diǎn)的話)。然而，在生成代碼算法中，僅考慮了前一情況，。然而，在生成代碼算法中，僅考慮了前一情況， 而對后一情況卻未加以考慮而對后一情況卻未加以

33、考慮(因?yàn)樯纱a算法并未把因?yàn)樯纱a算法并未把R作為作為 V的一個(gè)獨(dú)占寄存器的一個(gè)獨(dú)占寄存器)，因此，在現(xiàn)在的情況下，對于，因此，在現(xiàn)在的情況下，對于B中中V的的 定值點(diǎn)之前的那些四元式，如果在為它們生成目標(biāo)代碼時(shí)，定值點(diǎn)之前的那些四元式，如果在為它們生成目標(biāo)代碼時(shí)， 也把對也把對v的引用處理為對的引用處理為對R內(nèi)容的引用，則使其中的每一個(gè)對內(nèi)容的引用，則使其中的每一個(gè)對 V的引用都節(jié)省了執(zhí)行代價(jià)的引用都節(jié)省了執(zhí)行代價(jià)1。 v由于現(xiàn)在已為由于現(xiàn)在已為B中的變量中的變量V分配了固定的寄存器，因此，當(dāng)分配了固定的寄存器，因此，當(dāng)V 在在B的出口之后活躍時(shí)，也就不必把的出口之后活躍時(shí)，也就不必把

34、V的值送入內(nèi)存，這樣一的值送入內(nèi)存，這樣一 來，就使執(zhí)行代價(jià)又節(jié)省了來，就使執(zhí)行代價(jià)又節(jié)省了2。 執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù)執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價(jià)總數(shù) v對于循環(huán)對于循環(huán)L中的某一變量，當(dāng)給它分配了一個(gè)中的某一變量，當(dāng)給它分配了一個(gè) 固定的寄存器之后，則每執(zhí)行循環(huán)一次所節(jié)固定的寄存器之后，則每執(zhí)行循環(huán)一次所節(jié) 省的執(zhí)行代價(jià)總數(shù)省的執(zhí)行代價(jià)總數(shù)(相對于按代碼生成算法生相對于按代碼生成算法生 成的代碼成的代碼)為：為： (USE(V，B)+2*LIVE(V，B) （B L） v其中：其中： USE(V，B)為基本塊為基本塊B中中V的定值點(diǎn)之前對的定值點(diǎn)之前對V引用的次數(shù)；引用的次數(shù)；

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