【正文】 的 56 （ 2）相鄰列表表示： ?相鄰列表用具有 6個(gè)成分的數(shù)組表示： ?color：為一整數(shù)，其值為該結(jié)點(diǎn)所選顏色的值 ,初始值－ ∞ ?disp：用于寄存器 spilling，表示相應(yīng)符號(hào)寄存器 spill到某 個(gè)棧的偏移地址，初始值－ ∞ ?spcost： spill開銷，對(duì)符號(hào)寄存器 ,初值為 0對(duì)實(shí)際寄存器， 初值為 ∞ ?nint：圖中余下的與之相鄰的結(jié)點(diǎn)數(shù) ?adjnds：圖中余下的與之相鄰的結(jié)點(diǎn)列表 ?rmvadj：已從圖中去掉的相鄰結(jié)點(diǎn)列表 57 ?優(yōu)點(diǎn)：能比較方便地確定有多少結(jié)點(diǎn)與給定的結(jié)點(diǎn)相鄰， 且有哪些結(jié)點(diǎn)與之相鄰 ?相鄰矩陣主要用于寄存器合并，相鄰列表主要用于實(shí)際的 著色過程 ?因此，一般情況下，首先建立相鄰矩陣，并在寄存器合并 過程中對(duì)其進(jìn)行不斷修改，然后根據(jù)相鄰矩陣建立相應(yīng)的 相鄰列表 58 ： ?寄存器合并是一種復(fù)寫傳播變換，用于消除從一個(gè)寄存器 到另一個(gè)寄存器的拷貝 ?查找寄存器拷貝指令的中間代碼，即 sj si，若 sj與 si不 相互干擾，則查找向 si寫數(shù)據(jù)的指令，對(duì)其進(jìn)行修改，并 將其中相應(yīng)數(shù)據(jù)寫到寄存器 sj中，移去拷貝指令；且在干 擾圖中將 sj與 si合并為一個(gè)結(jié)點(diǎn)。分別將塊 B4中的 s7和 s5 spilling 到內(nèi)存中，其基址寄存器為 r10，偏移量 disp分別為 0和 4。通過本 章學(xué)習(xí)，僅為學(xué)生初步了解一個(gè)高級(jí)程序設(shè)計(jì)語言編譯程序目 標(biāo)代碼生成需要考慮的問題和解決這些問題的基本原則和方法 ，為今后應(yīng)用打下初步基礎(chǔ)。 代碼生成程序的自動(dòng)化構(gòu)造 ?在 20世紀(jì) 70年代和 80年代，開始出現(xiàn)了編譯后端的自動(dòng)構(gòu) 造技術(shù)，開發(fā)了一系列代碼生成程序的構(gòu)造器，如： BEG 、 iburg、 twig、 MBURG等 ?研究聲明，這種利用聲明性描述構(gòu)造代碼生成程序要比手 工編寫容易，而且需要的工作量少，但其產(chǎn)生代碼的執(zhí)行 效率往往還不足手工開發(fā)的十分之一，從而很難為廣大用 戶所接受 81 ?如圖 ，代碼生成程序的構(gòu)造器的輸入是代碼生成 描述，輸出是代碼生成程序： 82 一 .模式匹配與動(dòng)態(tài)規(guī)劃 ?這種方法是由 Aho、 Ganapathi和 Tjiang開發(fā)的 ?基本思想： 將目標(biāo)機(jī)指令 用樹重寫規(guī)則 表示，機(jī)器指令集 合表示為一個(gè)樹模式集合，且將描述不同指令的樹模式賦 予相對(duì)權(quán)值以表示執(zhí)行該指令的相對(duì)代價(jià)，然后利用動(dòng)態(tài) 規(guī)劃技術(shù)選擇最優(yōu)的指令集合來計(jì)算相應(yīng)的 中間表示樹 。 spcost用于計(jì) 算 spilling相應(yīng)符號(hào)寄存器所需要的開銷 ?spill一個(gè) web的開銷可表示為： ?其中， def、 use、 copy是 web的單個(gè)定義、使用和拷貝： defwt 、 usewt和 copywt相對(duì)權(quán)值 66 ?在計(jì)算 spill開銷的過程中，應(yīng)該考慮下述因素： （ 1）若重新計(jì)算一個(gè) web的值比重新裝載更有效，可對(duì)其 進(jìn)行重新計(jì)算，因此，選擇重新計(jì)算的開銷 （ 2）若 spill了某條拷貝指令的源操作數(shù)或目的操作數(shù)，則 可以不再考慮該指令 （ 3）若在同一基本塊中，某個(gè)被 spill的值需要多次使用， 且直到最后一次使用，重新裝載的值一直是活躍的，則在該 基本塊中，只需做一次取操作 67 ： （ 1） degreeR規(guī)則： ?結(jié)點(diǎn)的度 degree表示與之相鄰結(jié)點(diǎn)的個(gè)數(shù) ?基本思想： 對(duì)給定包含一個(gè)度小于 R的結(jié)點(diǎn)的干擾圖是 R 可著色的，當(dāng)且僅當(dāng)不包含該結(jié)點(diǎn)的干擾圖是可著色的 ?當(dāng)然，這種規(guī)則并不是對(duì)所有的干擾圖都適用。所采用的方法為 degreeR和消極試探法 （ 7）寄存器賦值。1 第十二章 代碼生成 ?第一節(jié) 代碼生成概述 ?第二節(jié) 一個(gè)簡單的代碼生成程序 ?第三節(jié) 幾種常用的代碼生成程序的開發(fā)方法 ?第四節(jié) 全局寄存器分配（圖著色法） ?第五節(jié) 代碼生成程序的自動(dòng)化構(gòu)造 2 知識(shí)結(jié)構(gòu) 3 167。從干擾圖的相鄰列表中排除結(jié)點(diǎn)及其 相應(yīng)的邊。該結(jié)點(diǎn)的度為為結(jié)點(diǎn) sj和 si度的并集 59 ?保證合并后為 R可著色的情況下，才進(jìn)行合并，為此需要 兩條安全策略： （ 1）若合并后所得結(jié)點(diǎn) (a,b)具有小于 R個(gè)度大于或等于 R的 鄰居，則結(jié)點(diǎn) a和結(jié)點(diǎn) b是可以合并的 （ 2）對(duì)結(jié)點(diǎn) a的每個(gè)鄰居 t,要么 t與結(jié)點(diǎn) b已是相互干擾的， 要么 t的度小于 R，則這種合并是安全的 60 ?寄存器合并是一種功能強(qiáng)大的變換，其主要作用在于： （ 1）簡化編譯過程，如消除不必要的拷貝操作 （ 2）在過程調(diào)用之前，保證參數(shù)值被移到合適的寄存器中 （ 3）對(duì)源和目的操作數(shù)有特殊要求的機(jī)器指令，使其操作 數(shù)和結(jié)果在適當(dāng)?shù)奈恢? （ 4）對(duì)操作數(shù)或結(jié)果值需要使用寄存器對(duì)的指令，保證能 夠?yàn)槠浞峙浼拇嫫鲗?duì)，等等 61 ： ?spilling的結(jié)果可能會(huì)將一個(gè) web分解為兩個(gè)或多個(gè) web， 從而減少干擾圖中的干擾 ?例如 ,通過將圖 ,如圖 ： 62 63 ?這樣 web w1被分成 4個(gè) web: w w w w8： ?web Components ?w2 def x in B5, use x in B6 ?w3 def y in B2, use y in B4 ?w4 def y in B1, use y in B3 ?w5 def x in B2, tmp x in B2 ?w6 def x in B3, tmp x in B3 ?w7 x tmp in B4, use x in B4 ?w8 x tmp in B5, use x in B5 64 ?所得的干擾圖如圖 ： 65 ?干擾圖的相鄰列表中每項(xiàng)有一個(gè)成分 spcost。 所得的代碼的片斷如圖 ： 77 78 ?重新為其建立干擾圖，如圖 ： 79 ?利用 degreeR規(guī)則對(duì)其進(jìn)行修剪，并將實(shí)際寄存器賦給與 之具有相同顏色的符號(hào)寄存器，所得的代碼片斷如圖 ： 80 167。 108 第 12章 習(xí)題 第 1題：一個(gè)編譯程序的代碼生成要著重考慮哪些問題 ? 第 2題：決定目標(biāo)代碼的因素有哪些？ 第 3題：為什么在代碼生成時(shí)要考慮充分利用寄存器？ 第 4題：寄存器分配的原則是什么？ 109 第 12章 作業(yè)題 P301： 1.