編譯原理第12章 代碼生成

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

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

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

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

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

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

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

8、型指令形式指令形式意義（設意義（設op是二目運算符）是二目運算符） 直接地址型直接地址型 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 模型機主要指令的意義模型機主要指令的意義 指令指令意義意義指令指令意義意義 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單元。單元。 模型機尋址方式模型機尋址方式 編碼編碼名名 稱稱助記符助記符含含 義義匯編后的情況匯編后的情況 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ù)單元地址在本 指令之后的單元中指令之后的單元中 生成目標代碼衡量指標生成目標代碼衡量指標 v目標程序（指令條數(shù)）；目標程序（指令條數(shù)）； v執(zhí)行目標程序所占的機器時間；執(zhí)行目標程序所占的機器時間； v目標程序所有指令

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

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

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

14、”欄按在基本塊出口處是否為活躍而置成欄按在基本塊出口處是否為活躍而置成“活躍活躍”或或“非非 活躍活躍”。這里假定變量都是活躍的，臨時變量都是非活躍的。這里假定變量都是活躍的，臨時變量都是非活躍的。 v(2)從基本塊出口到基本塊入口由后向前依次處理每個四元式從基本塊出口到基本塊入口由后向前依次處理每個四元式 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)的次序不能顛倒。的次序不能顛倒。 計算變量待用信息的示例計算變量待用信息的示例 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待用信息和活躍信息在待用信息和活躍信息在四元式上的標記四元式上的標記 四元式的序號 四元式上的標記四元式上的標記 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)行 值是存放在某個寄存器中，還是在某個主存單元中，或者值是存放在某個寄存器中，還是在某個主存單元中，或者 既在寄存器中又在主存中。既在寄存器中又在主存中。 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，當然也意味著給出了語句，當然也意味著給出了語句 P處的待用信息、活躍信息及當時各寄存器描述處的待用信息、活躍信息及當時各寄存器描述 數(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是同是同 一標識符，或一標識符，或B在該四元式后不會再被引用，則可選取在該四元式后不會再被引用，則可選取Ri為所需的寄存器為所需的寄存器R， 并轉(zhuǎn)并轉(zhuǎn)(4)。 v(2)如果有尚未分配的寄存器，則從中選用一個如果有尚未分配的寄存器，則從中選用一個Ri為所需的寄存器為所需的寄存器R，并轉(zhuǎn)，并轉(zhuǎn)(4)。 v(3)從已分配的寄存器中選取一個從已分配的寄存器中選取一個Ri作為所需寄存器作為所需寄存

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

21、ALUE M =M，否則，令，否則，令AVALUEM=M，R。 c)刪除刪除RVALURi 中的中的M。 v(4)給出給出R，返回。，返回。 v這樣，一旦得到了一個為四元式運算的操作寄存器這樣，一旦得到了一個為四元式運算的操作寄存器R，就可以進行代碼生成，就可以進行代碼生成， 而當目標代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。而當目標代碼生成完成后，則又需修改寄存器的使用信息和地址描述信息。 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)，設返回的寄存器為，設返回的寄存器為R，供，供x存放現(xiàn)行值。存放現(xiàn)行值。 v(2) 由變量地址描述數(shù)組由變量地址描述數(shù)組AVALUEy、AVALUEz確定變量確定變量y、z的現(xiàn)行值的現(xiàn)行值 存放位置存放位置y，z，當現(xiàn)行值在寄存器中時，便將該寄存器作為，當現(xiàn)行值在寄存器中時，便將該寄存器作為y或或z。 v(3) 如果如果yR，生成目標代碼，生成目標代碼 MOV y R op R z 否則只生成目標代碼否則只生成目標代碼 op R z。 當當y或或z為為R時，刪除時，刪除AVALUEy或或AVALUEz中的中的

24、R。 v(4) 修改兩個描述數(shù)組，修改兩個描述數(shù)組， 表示表示x 占用占用R， 即含即含AVALUEx=R ， RVALUER=x。 v(5) 如果在如果在P點點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? 生成目標碼生成目標碼 op R C 生成目標碼生成目標碼 LD R，B op R C 修改寄存器使用的信息修改寄存器使用的信息 和地址描述信息和地址描述信息 Y N 全局寄存器分配全局寄存器分配 v四元式的目標代碼形式四元式的目標代碼形式 v分配寄存器的原則：分配寄存器的原則： 降低目標代碼執(zhí)行代價。降低目標代碼執(zhí)行代價。 v分配寄存器的策略分配寄存器的策略 v計算目標代碼執(zhí)行代價的方法計算目標代碼執(zhí)行代價的方法 v執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行循環(huán)一次所節(jié)省的執(zhí)行代價總數(shù)執(zhí)行代價總數(shù) v計算執(zhí)行代價需考慮因素計算執(zhí)行代價

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

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

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

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

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

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

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

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

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

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