第七章 目標(biāo)代碼的生成

1、第七章第七章 目標(biāo)代碼的生成目標(biāo)代碼的生成一個(gè)簡單代碼生成器一個(gè)簡單代碼生成器 目標(biāo)代碼生成目標(biāo)代碼生成在編譯程序中的邏輯位置在編譯程序中的邏輯位置詞法分析詞法分析語法分析語法分析語義分析和中間代碼生成語義分析和中間代碼生成機(jī)器無關(guān)的代碼優(yōu)化機(jī)器無關(guān)的代碼優(yōu)化針對機(jī)器的代碼優(yōu)化針對機(jī)器的代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成字符流字符流單詞流單詞流語法分析樹語法分析樹中間表示中間表示優(yōu)化的中間表示優(yōu)化的中間表示目標(biāo)代碼目標(biāo)代碼優(yōu)化的目標(biāo)代碼優(yōu)化的目標(biāo)代碼從中間表示從中間表示獲取的流圖獲取的流圖改進(jìn)的流圖改進(jìn)的流圖指令調(diào)度指令調(diào)度寄存器分配寄存器分配窺孔優(yōu)化窺孔優(yōu)化 目標(biāo)目標(biāo)代碼生成要考慮的主要問題代

2、碼生成要考慮的主要問題 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法 由上述算法由上述算法從從 DAG 生成代碼生成代碼 基于樹重寫的代碼生成基于樹重寫的代碼生成 簡單的圖著色物理寄存器分配算法簡單的圖著色物理寄存器分配算法 代碼生成要考慮的主要問題代碼生成要考慮的主要問題- 指令選擇指令選擇 目標(biāo)機(jī)指令集的性質(zhì)和中間代碼的形式?jīng)Q定目標(biāo)機(jī)指令集的性質(zhì)和中間代碼的形式?jīng)Q定 指令選擇的難易指令選擇的難易- 寄存器分配寄存器分配 充分、高效地使用寄存器充分、高效地使用寄存器- 指令調(diào)度指令調(diào)度 選擇好計(jì)算的次序，充分利用目標(biāo)機(jī)的特點(diǎn)選擇好計(jì)算的次序，充分利用目標(biāo)機(jī)的特點(diǎn) 指令選擇指令選擇- 任務(wù)任務(wù)

3、 為每條中間語言語句選擇恰當(dāng)?shù)哪繕?biāo)機(jī)指令或指令序列為每條中間語言語句選擇恰當(dāng)?shù)哪繕?biāo)機(jī)指令或指令序列- 原則原則 首先要保證語義的一致性；若目標(biāo)機(jī)指令系統(tǒng)比較完首先要保證語義的一致性；若目標(biāo)機(jī)指令系統(tǒng)比較完 備，為中間語言語句找到語義一致的指令序列模板是備，為中間語言語句找到語義一致的指令序列模板是 很直接的（不必考慮執(zhí)行效率的情形下）很直接的（不必考慮執(zhí)行效率的情形下） 其次要權(quán)衡所生成代碼的效率（考慮時(shí)間其次要權(quán)衡所生成代碼的效率（考慮時(shí)間/空間代價(jià)）空間代價(jià)） 這一點(diǎn)較難做到，因?yàn)閳?zhí)行效率往往與該語句的上下這一點(diǎn)較難做到，因?yàn)閳?zhí)行效率往往與該語句的上下 文以及目標(biāo)機(jī)體系結(jié)構(gòu)（如流水線）有關(guān)

4、文以及目標(biāo)機(jī)體系結(jié)構(gòu)（如流水線）有關(guān) 指令選擇舉例指令選擇舉例- 為為TAC 語句語句選擇指令模板選擇指令模板 假設(shè)一個(gè)目標(biāo)機(jī)指令系統(tǒng)（一個(gè)簡單匯編語言）假設(shè)一個(gè)目標(biāo)機(jī)指令系統(tǒng)（一個(gè)簡單匯編語言）- 例例 TAC 語句語句 a:=b+c 可轉(zhuǎn)換為如下代碼序列可轉(zhuǎn)換為如下代碼序列 MOVb, R0 /* b 裝入寄存器裝入寄存器 R0 */ ADDc, R0 /* c 加到加到 R0 */ MOVR0, a /* 存存 R0 到到 a */ （其他算術(shù)和邏輯運(yùn)算的（其他算術(shù)和邏輯運(yùn)算的TAC 語句與此類似，只是選語句與此類似，只是選 擇不同的目標(biāo)指令，如減運(yùn)算選擇指令擇不同的目標(biāo)指令，如減運(yùn)算選

5、擇指令“SUB”， ） 指令選擇指令選擇- 選擇指令模板時(shí)可考慮選擇指令模板時(shí)可考慮指令的代價(jià)指令的代價(jià)（cost） 例例 TAC 語句語句 a:=b+c 的幾種轉(zhuǎn)換方式的幾種轉(zhuǎn)換方式（1）MOV b, R0 ADD c, R0 MOV R0, a cost=6（2）MOV b, a ADD c, a cost=6（3）假定假定 R0, R1 和和 R2中分別中分別 存放了存放了a, b 和和 c 的地址的地址 MOV *R1, *R0 ADD *R2, *R0 cost=2（4）假定假定R1和和R2中分別包含中分別包含b 和和c的值的值, 并且并且b的值在這的值在這 個(gè)賦值以后不再需要個(gè)賦值

6、以后不再需要 ADD R2, R1 MOV R1, a cost=3 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法- 基本塊內(nèi)基本塊內(nèi) TAC 語句序列的簡單代碼生成語句序列的簡單代碼生成 在基本塊范圍內(nèi)考慮如何充分利用寄存器的問題在基本塊范圍內(nèi)考慮如何充分利用寄存器的問題 原則：原則： 盡可能地讓變量的值保留在寄存器中盡可能地讓變量的值保留在寄存器中 盡可能引用變量在寄存器中的值盡可能引用變量在寄存器中的值 借助于在基本塊范圍內(nèi)建立變量的借助于在基本塊范圍內(nèi)建立變量的待用信息鏈待用信息鏈和和 活躍信息鏈活躍信息鏈 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法- 待用信息待用信息 在一個(gè)基本塊

7、中，四元式在一個(gè)基本塊中，四元式i對變量對變量A定值，如果定值，如果i后面后面的四元式的四元式j(luò)要引用要引用A，且從，且從i到到j(luò)的四元式?jīng)]有其它對的四元式?jīng)]有其它對A的的定值點(diǎn)，則稱定值點(diǎn)，則稱j是四元式是四元式i中對變量中對變量A的的待用信息待用信息，同時(shí)，同時(shí)也稱也稱A是是活躍活躍的。的。 如果如果A被多處引用，則構(gòu)成了被多處引用，則構(gòu)成了A的待用信息鏈和活躍的待用信息鏈和活躍信息鏈。信息鏈。 為了取得每個(gè)變量在基本塊內(nèi)的待用信息和活躍信為了取得每個(gè)變量在基本塊內(nèi)的待用信息和活躍信息，可從基本塊的出口由后向前掃描，對每個(gè)變量建息，可從基本塊的出口由后向前掃描，對每個(gè)變量建立相應(yīng)的待用信息

8、鏈與活躍信息鏈。立相應(yīng)的待用信息鏈與活躍信息鏈。n計(jì)算待用信息的算法計(jì)算待用信息的算法（1 1）對各基本塊的符號表中的）對各基本塊的符號表中的“待用信息待用信息”欄欄和和“活躍信息活躍信息”欄置初值，即把欄置初值，即把“待用信息待用信息”欄置欄置“非待用非待用”，對，對“活躍信息活躍信息”欄按在基本欄按在基本塊出口處是否為活躍而置成塊出口處是否為活躍而置成“活躍活躍”或或“非活非活躍躍”。這里假定變量都是活躍的，臨時(shí)變量都。這里假定變量都是活躍的，臨時(shí)變量都是非活躍的。是非活躍的。（2 2）從基本塊出口到基本塊入口由后向前依次）從基本塊出口到基本塊入口由后向前依次處理每個(gè)四元式。對每個(gè)四元式處

9、理每個(gè)四元式。對每個(gè)四元式i: A:=B op Ci: A:=B op C，依次執(zhí)行下述步驟：依次執(zhí)行下述步驟：a) a) 把符號表中變量把符號表中變量A A的待用信息和活躍信息附加到四的待用信息和活躍信息附加到四元式元式i i上。上。b) b) 把符號表中變量把符號表中變量A A的待用信息欄和活躍信息欄分別的待用信息欄和活躍信息欄分別置為置為“非待用非待用”和和“非活躍非活躍”。（由于在。（由于在i i中對中對A A的的定值只能在定值只能在i i以后的四元式才能引用，因而對以后的四元式才能引用，因而對i i以前以前的四元式來說的四元式來說A A是不活躍也不可能是待用的）是不活躍也不可能是待用

10、的）c) c) 把符號表中變量把符號表中變量B B和和C C的待用信息和活躍信息附加到的待用信息和活躍信息附加到四元式四元式i i上。上。d) d) 把符號表中變量把符號表中變量B B和和C C的待用信息欄置為的待用信息欄置為“i”i”，活，活躍信息欄置為躍信息欄置為“活躍活躍”。注意，以上注意，以上a a）和）和b b），），c c）和）和d d）的次序不能顛倒。）的次序不能顛倒?！纠咳粲谩纠咳粲肁 A，B B，C C，D D表示變量，用表示變量，用T T，U U，V V表示表示中間變量，有四元式如下：中間變量，有四元式如下： （1）T=A-B （2）U=A-C （3）V=T+U （4）

11、D=V+U 其名字表中的待用信息和活躍信息如下表，用其名字表中的待用信息和活躍信息如下表，用“F”F”表示表示“非待用非待用”“”“非活躍非活躍”，用，用“L”L”表示活躍。表示活躍。 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法- 寄存器描述數(shù)組和變量地址描述數(shù)組寄存器描述數(shù)組和變量地址描述數(shù)組 RVALUER 描述寄存器描述寄存器 R 當(dāng)前對應(yīng)哪個(gè)變量當(dāng)前對應(yīng)哪個(gè)變量 AVALUEA 表示變量表示變量 A 的值存放在哪個(gè)寄存器中的值存放在哪個(gè)寄存器中 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法- 基本塊內(nèi)基本塊內(nèi) TAC 語句序列的簡單代碼生成語句序列的簡單代碼生成 （假設(shè)只有形如（假設(shè)

12、只有形如 A:=B op C 的的TAC 語句序列）語句序列） step1：對每個(gè)對每個(gè)TAC 語句語句i: A:=B op C，依次執(zhí)行下述步驟：依次執(zhí)行下述步驟： 以以 i: A:=B op C 為參數(shù)，調(diào)用為參數(shù)，調(diào)用 getreg(i: A:=B op C); 從從 getreg 返返 回時(shí)，得到一寄存器回時(shí)，得到一寄存器 R（這里先假定（這里先假定 R 為偽寄存器），用它作存為偽寄存器），用它作存 放放 A 現(xiàn)行值的寄存器；（函數(shù)現(xiàn)行值的寄存器；（函數(shù) getreg 稍后介紹）。稍后介紹）。 利用利用 AVALUEB 和和 AVALUEC，確定出，確定出 B 和和 C 現(xiàn)行值存放位置

13、現(xiàn)行值存放位置 B 和和 C，如果其現(xiàn)行值在寄存器中，則把寄存器取作，如果其現(xiàn)行值在寄存器中，則把寄存器取作B 和和 C。 如如 BR，則生成目標(biāo)代碼，則生成目標(biāo)代碼 MOV B, R OP C, R 否則，生成目標(biāo)代碼否則，生成目標(biāo)代碼 OP C, R 如如 B 或或 C 為為R，則刪除，則刪除 AVALUEB 或或 AVALUEC 中的中的 R 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法- 基本塊的代碼生成算法基本塊的代碼生成算法 （續(xù)前頁（續(xù)前頁） 令令 AVALUEA=R，并令，并令 RVALUER=A，以表示變量，以表示變量 A 的現(xiàn)行的現(xiàn)行值只在值只在 R 中并且中并且 R 中的

14、值只代表中的值只代表 A 的現(xiàn)行值的現(xiàn)行值 。 如如 B 或或 C 的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出的現(xiàn)行值在基本塊中不再被引用，它們也不是基本塊出口之后的活躍變量（由語句口之后的活躍變量（由語句 i 上的附加信息知道），并且其現(xiàn)行值在某上的附加信息知道），并且其現(xiàn)行值在某個(gè)寄存器個(gè)寄存器 Rk 中，則刪除中，則刪除 RVALUERk 中的中的 B 或或C 以及以及 AVALUEB 或或 AVALUEC 中的中的 Rk ，使該寄存器不再為，使該寄存器不再為 B 或或 C 所占用。所占用。 step2: : 處理完基本塊中所有處理完基本塊中所有TAC 語句之后，對現(xiàn)行值在語句之后

15、，對現(xiàn)行值在 某寄存器某寄存器 R 中的每個(gè)變量中的每個(gè)變量 M，若它在出口之后是活躍，若它在出口之后是活躍 的，則生成的，則生成 MOV R, M，將其存入主存將其存入主存- 函數(shù)函數(shù) getreg（以（以 i: A:=B op C 為參數(shù)，為參數(shù)， 返回一個(gè)偽寄存器返回一個(gè)偽寄存器） 步驟步驟： 若若 RVALUER=B ，且在語句，且在語句 i 之后之后 B 在基本塊中不再被引用，同在基本塊中不再被引用，同 時(shí)也不是基本塊出口之后的活躍變量（由時(shí)也不是基本塊出口之后的活躍變量（由 i 上的附加信息可知道），上的附加信息可知道）， 則返回則返回 R； 否則否則，返回一個(gè)新的偽寄存器，返回一

16、個(gè)新的偽寄存器R注：注：這里的這里的 getreg 返回偽寄存器（可以利用隨后介紹的圖著色寄存返回偽寄存器（可以利用隨后介紹的圖著色寄存 器分配算法將它們對應(yīng)到真實(shí)寄存器或內(nèi)存地址）。器分配算法將它們對應(yīng)到真實(shí)寄存器或內(nèi)存地址）。 其實(shí)也可以不是返回偽寄存器，而是在寄存器不夠時(shí)返回一個(gè)內(nèi)其實(shí)也可以不是返回偽寄存器，而是在寄存器不夠時(shí)返回一個(gè)內(nèi) 存地址。存地址。 一個(gè)一個(gè)簡單的代碼生成算法簡單的代碼生成算法舉例舉例- 對于右圖的基本塊對于右圖的基本塊 （假定只有（假定只有d在基本塊的在基本塊的 出口是活躍的），利用上述算法可生成如下出口是活躍的），利用上述算法可生成如下 代碼序列：代碼序列：t:

17、=a-b u:=a-c v:=t+u d:=v+u 由上述算法由上述算法從從 DAG 生成代碼生成代碼- 從某個(gè)基本塊的從某個(gè)基本塊的 DAG 表示得到的兩段表示得到的兩段 TAC 代碼代碼 - - + + a0T1T1:=a+bT2:=c+dT3:=e-T2T4:=T1-T3T4c0d0T3T2b0e0 - -T2:=c+dT3:=e-T2T1:=a+bT4:=T1-T3- 將上述簡單的代碼生成算法應(yīng)用于如下兩個(gè)基本塊將上述簡單的代碼生成算法應(yīng)用于如下兩個(gè)基本塊 比較比較其結(jié)果（這里假設(shè)基本塊出口處只有其結(jié)果（這里假設(shè)基本塊出口處只有T4是活躍的）是活躍的）T1:=a+bT2:=c+dT3:

18、=e-T2T4:=T1-T3T2:=c+dT3:=e-T2T1:=a+bT4:=T1-T3MOV a,R0ADD b,R0MOV c,R1ADD d,R1MOV e,R2SUB R1,R2SUB R2,R0MOV R0,T4MOV c,R0ADD d,R0MOV e,R1SUB R0,R1MOV a,R0ADD b,R0SUB R1,R0MOV R0,T4第二段代碼較優(yōu)第二段代碼較優(yōu)（少用了寄存器）（少用了寄存器） 由上述算法由上述算法從從 DAG 生成代碼生成代碼- 例例 a i := b 的一個(gè)可能的中間表示樹的一個(gè)可能的中間表示樹 基于樹重寫的代碼生成基于樹重寫的代碼生成- 樹重寫（樹重

19、寫（Tree Rewriting）規(guī)則形如）規(guī)則形如 replacement template cost = action 其中其中 replacement 代表樹的單個(gè)節(jié)點(diǎn)代表樹的單個(gè)節(jié)點(diǎn) template 代表一棵樹代表一棵樹 cost 是用來計(jì)算相應(yīng)于該是用來計(jì)算相應(yīng)于該template代價(jià)的代碼片段代價(jià)的代碼片段 action 是使用該規(guī)則進(jìn)行樹重寫時(shí)執(zhí)行的代碼片段是使用該規(guī)則進(jìn)行樹重寫時(shí)執(zhí)行的代碼片段 基于樹重寫的代碼生成基于樹重寫的代碼生成- 例例 若干若干VAX指令對應(yīng)的樹重寫規(guī)則指令對應(yīng)的樹重寫規(guī)則 基于樹重寫的代碼生成基于樹重寫的代碼生成- 例例 若干若干VAX指令對應(yīng)的樹重

20、寫規(guī)則指令對應(yīng)的樹重寫規(guī)則 基于樹重寫的代碼生成基于樹重寫的代碼生成- 從中間表示樹生成代碼從中間表示樹生成代碼 基于樹重寫的代碼生成基于樹重寫的代碼生成 思路思路 根據(jù)樹重寫規(guī)則對中間表示樹的子樹逐步進(jìn)行歸根據(jù)樹重寫規(guī)則對中間表示樹的子樹逐步進(jìn)行歸 約，直至單個(gè)節(jié)點(diǎn)為止，該過程的所有子樹集合構(gòu)約，直至單個(gè)節(jié)點(diǎn)為止，該過程的所有子樹集合構(gòu) 成中間表示樹的一種成中間表示樹的一種覆蓋覆蓋（cover）。）。 某個(gè)某個(gè)覆蓋的代價(jià)覆蓋的代價(jià)是相應(yīng)樹重寫規(guī)則的附加代價(jià)之和是相應(yīng)樹重寫規(guī)則的附加代價(jià)之和 找到一種代價(jià)最小的覆蓋。找到一種代價(jià)最小的覆蓋。 根據(jù)最小代價(jià)的覆蓋進(jìn)行代碼生成。根據(jù)最小代價(jià)的覆蓋進(jìn)

21、行代碼生成。 簡單的圖著色物理寄存器分配算法簡單的圖著色物理寄存器分配算法- 兩遍的通用寄存器分配算法兩遍的通用寄存器分配算法 第一遍先假定可用的通用寄存器是無限數(shù)量的，完第一遍先假定可用的通用寄存器是無限數(shù)量的，完 成指令選擇成指令選擇 例如：前面介紹的簡單代碼生成算法中的例如：前面介紹的簡單代碼生成算法中的 getreg 函數(shù)返回一個(gè)偽寄存器（不管物理寄存器的個(gè)數(shù)）函數(shù)返回一個(gè)偽寄存器（不管物理寄存器的個(gè)數(shù)） 第二遍將物理寄存器分配到偽寄存器。第二遍將物理寄存器分配到偽寄存器。 物理寄存器數(shù)量不足時(shí)，會將一些偽寄存器泄露到物理寄存器數(shù)量不足時(shí)，會將一些偽寄存器泄露到 （spilled into）內(nèi)存，圖著色算法的核心任務(wù)是使）內(nèi)存，圖著色算法的核心任務(wù)是使 得泄露的偽寄存器數(shù)目最少。得泄露的偽寄存器數(shù)目最少。- 基于寄存器相干圖基于寄存器相干圖（register-interference graph） 的圖著色寄存器分配算法的圖著色寄存器分配算法 構(gòu)造寄存器構(gòu)造寄存器相干圖相干圖 結(jié)點(diǎn)結(jié)點(diǎn)：每一個(gè)偽寄存器為一個(gè)結(jié)點(diǎn)。：每一個(gè)偽寄存器為一個(gè)結(jié)點(diǎn)。 邊邊：如果程序中存在某點(diǎn)，一個(gè)結(jié)點(diǎn)在該點(diǎn)被定義，：如果程序中存在某點(diǎn)，一個(gè)結(jié)點(diǎn)在該點(diǎn)被定義， 而另一個(gè)結(jié)點(diǎn)在該點(diǎn)是活躍的，則在