1、第九章目標(biāo)代碼生成，以源程序的中間代碼作為輸入，產(chǎn)生等價(jià)的目標(biāo)代碼作為輸出，如圖所示。代碼生成器的輸入包括中間代碼和符號(hào)表中的信息；代碼生成是將語(yǔ)義分析或優(yōu)化后的中間代碼轉(zhuǎn)換成目標(biāo)代碼。9.1概述，1。代碼生成器的輸入：源程序的中間表示；如三個(gè)地址碼；符號(hào)表中的信息：數(shù)據(jù)區(qū)2中的相對(duì)地址。目標(biāo)程序：絕對(duì)機(jī)器語(yǔ)言代碼；可重定位的機(jī)器語(yǔ)言代碼；匯編語(yǔ)言程序。代碼生成關(guān)注兩個(gè)問題：(優(yōu)化)，如何使生成的目標(biāo)代碼更短；如何充分利用寄存器，減少目標(biāo)代碼訪問存儲(chǔ)單元的次數(shù)。9.1概述，9.2假設(shè)的目標(biāo)機(jī)器模型，使用一個(gè)模型作為目標(biāo)機(jī)器：1。有了多個(gè)寄存器，regs可以用作累加器或索引器；有四種類型的指令形

2、式，操作符操作包括：加法、SUB、MUL、DIV等。2、其他指令的含義：9.3簡(jiǎn)單代碼生成器，功能：依次將每個(gè)中間代碼轉(zhuǎn)換成目標(biāo)代碼，并考慮充分利用基本塊內(nèi)的寄存器。例如：A=(B C)*D E，中間代碼：t1=b c T2=t1 * d a=t 2e，(1) LD r，b (2) add r，c (3) ST r，t1，(4) LD r，t1 (5) mul r，d (6 E (9)ST R，A，示例：(1) LD R，B (2) Add R，C (3) ST R，T1 (4) LD R，T1 (5) Mul R，D (6) ST R，T2 (7) LD R， T2 (8) Add C (5

3、) MUL R，D (8)ADD R，E (9)ST R，A，優(yōu)化，為了進(jìn)行上述優(yōu)化，代碼生成器必須知道一些信息：9.3.1備用信息和活動(dòng)信息，可變備用信息在基本塊中：從基本塊的出口從前到后掃描，并為每個(gè)變量建立相應(yīng)的備用信息鏈和活動(dòng)變量信息鏈。 簡(jiǎn)化：基本塊中的所有臨時(shí)變量在基本塊退出后都被視為非活動(dòng)變量；在基本塊退出后，所有非臨時(shí)變量都被視為活動(dòng)變量。變量備用信息的計(jì)算算法：例如，基本塊(1) T=A-B (2) U=A-C (3) V=T U (4) W=V U，(1)開始時(shí)，符號(hào)表中的每個(gè)變量都是“非備用”，退出后變量是否是活動(dòng)的填入活動(dòng)信息列；(2)從基本塊的出口到入口依次處理每個(gè)中

4、間代碼。對(duì)于每個(gè)代碼i: A:=B操作C，執(zhí)行以下步驟：將符號(hào)表中變量A的非活動(dòng)和活動(dòng)信息附加到中間代碼I；將符號(hào)表中A的無效和有效信息設(shè)置為“無效”和“無效”；將符號(hào)表中變量B.C的無效和有效信息附加到中間代碼I上；將符號(hào)表中的備用信息設(shè)置為“1”，活動(dòng)信息設(shè)置為“活動(dòng)”。寄存器描述和可變地址描述；1.在代碼生成過程中，建立寄存器描述數(shù)組RVALUE，動(dòng)態(tài)記錄每個(gè)寄存器是空閑的、分配給某個(gè)變量的還是分配給某個(gè)變量的。2.在代碼生成過程中，創(chuàng)建變量地址描述數(shù)組AVALUE，并動(dòng)態(tài)記錄每個(gè)變量當(dāng)前值的存儲(chǔ)位置：在一個(gè)寄存器中，在一個(gè)主存儲(chǔ)單元中，或者在一個(gè)寄存器和主存儲(chǔ)單元中。9.3.2代碼生成

5、算法，假設(shè)基本塊中每個(gè)中間代碼的形式為a=b op c。依次對(duì)每個(gè)中間代碼i:A=B op C執(zhí)行以下步驟：(1)調(diào)用函數(shù)getreg(I : a=B op C)；(2)使用地址描述數(shù)組AVALUEB和AVALUEC來確定變量b和c的當(dāng)前值存儲(chǔ)位置b和c；(3)如果是BR，生成目標(biāo)代碼： LD R，B op R，C；否則，生成目標(biāo)代碼。如果b或c是r，在AVALUEB或AVALUEC中刪除r。(4)讓阿瓦魯=右，右魯爾=右；(5)如果B和C的當(dāng)前值在基本塊中不再被引用，則釋放被占用的RK(即，在右值RK中刪除B或C，在右值RK中刪除RK)。對(duì)應(yīng)于每個(gè)中間代碼的目標(biāo)代碼是：注意：處理完所有代碼后

6、，當(dāng)前值僅在reg中，活動(dòng)變量在基本塊退出后。ST指令應(yīng)該用于將值存儲(chǔ)在主存儲(chǔ)單元中。9.3.3寄存器分配，有效利用寄存器，生成更高效的目標(biāo)代碼。指令的執(zhí)行成本：指令訪問主存儲(chǔ)單元的次數(shù)是1。例如，執(zhí)行成本是1，執(zhí)行成本是2，執(zhí)行成本是2，執(zhí)行成本是3。當(dāng)變量A的值被調(diào)用到一個(gè)寄存器中時(shí)，為了更快的計(jì)算，應(yīng)該替換哪個(gè)寄存器？對(duì)于循環(huán)，可用的寄存器被固定地分配給最節(jié)省執(zhí)行成本的變量。計(jì)算成本節(jié)約的公式是：USE(M，B) 2*LIVE(M，B) BL，其中USE(M，B)=在基本塊B中設(shè)置M的值之前對(duì)M的引用次數(shù)；LIVE(M，B)=1(當(dāng)M在B中固定且在B退出后激活時(shí))，0(在其他情況下)，并

7、且在分配寄存器后，可以生成目標(biāo)代碼。與簡(jiǎn)單代碼生成器的不同之處在于：(1)具有固定寄存器的變量由相應(yīng)的reg表示；(2)將存儲(chǔ)在前節(jié)點(diǎn)中的值循環(huán)到寄存器；(3)將存儲(chǔ)在出口節(jié)點(diǎn)中的值循環(huán)到主存儲(chǔ)單元；(4)在循環(huán)中每個(gè)基本塊的出口處，具有不固定寄存器的變量根據(jù)需要存儲(chǔ)回主存儲(chǔ)單元，而具有固定寄存器的變量不存儲(chǔ)回主存儲(chǔ)單元。ldr0，d ldr1，b，str0，d str1，b，str0，d str1，b，B0，b5，B6，5dag?；緣K中的中間代碼序列將以什么順序生成目標(biāo)代碼？以下中間代碼序列g(shù) : t1=ab T2=CD T3=e-t2t 4=t1-T3被視為以下中間代碼序列g(shù) : T2=

8、CD T3=e-t2t 1=ab T4=t1-T3、目標(biāo)代碼Dag和目標(biāo)代碼g: 1 LD R0、A 2 ADD R0、B 3 LD R1。c4addr1、d5str0、t16ldr0、e7subr0、r18ldr1、t19subr1、r010str1、t4、g的目標(biāo)代碼為1ldr0、c2addr0、d3ldr1、e4subr1、r05ldr0。a6ADR0，B 7 SUB R0，R1 8 ST R0，T4，省略ST R0，T1 LD R1，T1，結(jié)論：并評(píng)估表達(dá)式X=A * B C * D，從右向左計(jì)算的目標(biāo)代碼更好。使用基本塊的DAG，基本塊的中間代碼序列被重新排列。重排序DAG中N個(gè)內(nèi)部節(jié)點(diǎn)的算法：從第：頁(yè)繼續(xù)，設(shè)置初始值；K=1至N=0；I=N；當(dāng)有一個(gè)未在t中列出的內(nèi)部節(jié)點(diǎn)DO BEGIN時(shí)，選擇一個(gè)未在t中列出但其所有父節(jié)點(diǎn)都已進(jìn)入t或沒有父節(jié)點(diǎn)的內(nèi)部節(jié)點(diǎn)n；Ti=n。I=I-1；雖然n的最左邊的子節(jié)點(diǎn)m不是葉節(jié)點(diǎn)，并且它的所有父節(jié)點(diǎn)都已輸入t，DO BEgin Ti=m；I=I-1；n=m END END在第：頁(yè)，根據(jù)上述算法給出的節(jié)點(diǎn)順序，t1、T2、TN、DAG可以被重新生成為等效的中間代碼序列。根據(jù)新序列中的中間代碼順序，前一代碼生成算法生成的目標(biāo)代碼更好。9.4代碼生成器的自動(dòng)生成技術(shù)，問題：機(jī)器架構(gòu)不統(tǒng)一，自動(dòng)生成代碼的質(zhì)量和生成速度與