圖染色法的寄存器分配

1、圖染色法的寄存器分配計(jì)算機(jī)科學(xué)與技術(shù)系98級(jí)吳漢唐摘要本文講述了寄存器分配的圖染色法理論。Chaitin 和他的同伴，在IBM 的Yorktown Heights研究中心，實(shí)現(xiàn)了第一個(gè)基于圖染色法的全局的寄存器分配器。后來(lái)，Rice 大學(xué)的Preston Briggs對(duì)Chaitin的算法進(jìn)行了改進(jìn)和擴(kuò)展。Chaitin的算法悲觀地假設(shè)任何高度數(shù)的結(jié)點(diǎn)都不能被染色，只能被拋出（spilled）。Briggs的算法樂(lè)觀地認(rèn)為高度數(shù)的結(jié)點(diǎn)有可能被染色，從而獲得更低的拋出開(kāi)銷（spill costs），和更快的代碼。一 介紹（一） 編譯器和優(yōu)化一個(gè)優(yōu)化編譯器分為三個(gè)層次：l 前端把源語(yǔ)言轉(zhuǎn)換為中間代

2、碼。這個(gè)轉(zhuǎn)換依賴于源語(yǔ)言的結(jié)構(gòu)，需要幾遍掃描（pass）代碼才能完成。編譯時(shí)的錯(cuò)誤檢查就在這一層。我們可以理想地認(rèn)為前端是只與語(yǔ)言有關(guān)的、與機(jī)器無(wú)關(guān)的。l 優(yōu)化器包含幾遍的掃描（pass）， 每一遍掃描對(duì)中間代碼執(zhí)行特定的轉(zhuǎn)換。我們感興趣的是全局優(yōu)化，就是從整個(gè)函數(shù)搜集有用信息，再去做優(yōu)化。一般的全局優(yōu)化包括強(qiáng)度削減（strength reduction），循環(huán)不變量移動(dòng)（loop-invariant code motion）和公共子表達(dá)式消除（common subexpression elimination）。優(yōu)化器最好是與語(yǔ)言和機(jī)器都無(wú)關(guān)的。l 后端把中間代碼轉(zhuǎn)換為針對(duì)特定機(jī)器的目標(biāo)代碼。

3、這個(gè)轉(zhuǎn)換過(guò)程又稱為代碼生成，也需要幾遍掃描才能完成。這幾遍掃描包括指令選擇（instruction selection）,指令調(diào)度（instruction scheduling）,寄存器分配（register allocation）。后端在很大程度上是與語(yǔ)言無(wú)關(guān)的，與機(jī)器有關(guān)的。這個(gè)劃分簡(jiǎn)化了每一個(gè)層次的開(kāi)發(fā)和維護(hù)，使得在不同的編譯器中復(fù)用每個(gè)層次成為可能。例如，一個(gè)完全與機(jī)器無(wú)關(guān)的FORTRAN語(yǔ)言前端可以用到為不同機(jī)器設(shè)計(jì)的編譯器中。當(dāng)然，這還是一個(gè)理想的觀點(diǎn)。在實(shí)際中，每個(gè)層次都表現(xiàn)出既與語(yǔ)言相關(guān)又與機(jī)器相關(guān)。這些相關(guān)限制復(fù)用和維護(hù)，也成為編譯器設(shè)計(jì)人員努力要克服的難關(guān)。（二）優(yōu)化和寄存

4、器分配寄存器是位于CPU內(nèi)部的少量的高速存儲(chǔ)器。寄存器與內(nèi)存有很大的不同：l 寄存器很少。一個(gè)寄存器可以用幾個(gè)比特直接定位。內(nèi)存空間很大。內(nèi)存的定位一般是通過(guò)間接的“尋址方式”，其中可能包含一個(gè)或多個(gè)對(duì)寄存器的引用。l 寄存器很快。在一個(gè)周期內(nèi)，可以同時(shí)讀兩個(gè)寄存器，寫(xiě)第三個(gè)寄存器。內(nèi)存要慢些，一次訪問(wèn)就需要幾個(gè)周期。因?yàn)榧拇嫫鞯膫€(gè)數(shù)受限和高速度，它們成為大多數(shù)計(jì)算機(jī)體系結(jié)構(gòu)中的關(guān)鍵資源之一。寄存器分配器作為后端的一個(gè)模塊，控制寄存器的分配和使用。寄存器很重要。最簡(jiǎn)單的情況，每條機(jī)器指令的操作數(shù)要放在寄存器里。在計(jì)算復(fù)雜表達(dá)式的過(guò)程中產(chǎn)生的中間結(jié)果也要在寄存器里。更復(fù)雜的編譯器會(huì)把經(jīng)常使用的變

5、量放在寄存器里，來(lái)避免反復(fù)地存取。如果是一個(gè)帶優(yōu)化的編譯器，它會(huì)把公共子表達(dá)式消除或者循環(huán)不變量移動(dòng)以后的重用值，放在寄存器里。分配寄存器的任務(wù)有幾個(gè)層次l 寄存器只在一個(gè)表達(dá)式的范圍內(nèi)分配。這是一項(xiàng)為了減少寄存器需求量的指令調(diào)度的技術(shù)。l 更先進(jìn)的分配器可以在一個(gè)基本塊的范圍內(nèi)管理寄存器。l 全局分配器在一個(gè)函數(shù)的范圍內(nèi)工作。Chaitin 的分配器就在這樣的例子。l 程序間的寄存器分配是對(duì)一些函數(shù)工作，通常是一個(gè)完整的程序。為了支持全局的優(yōu)化，全局的寄存器分配是必須的。（三）寄存器分配和圖染色法實(shí)現(xiàn)好的寄存器分配總是很困難。即使是最簡(jiǎn)單的實(shí)現(xiàn)也會(huì)因?yàn)闄C(jī)器的特殊細(xì)節(jié)變得復(fù)雜。可靠的分配器必要

6、能很好地對(duì)付復(fù)雜的程序和稀少的寄存器的情況。圖染色法提供了一種簡(jiǎn)化的抽象。它建立一張表示分配過(guò)程中的各種限制的沖突圖（interference graph），并對(duì)它染色，把許多表面上各異的細(xì)節(jié)納入統(tǒng)一的模式。圖中的結(jié)點(diǎn)代表生命期（live range），邊代表生命期之間的沖突關(guān)系。一般說(shuō)來(lái)，如果兩個(gè)生命期在函數(shù)的某一點(diǎn)是同時(shí)活躍（live）的，它們就相互沖突，不能占有同一個(gè)寄存器。假設(shè)k 就是機(jī)器中可供分配的寄存器數(shù)目，如果圖中的所有結(jié)點(diǎn)可以用k 種或者更少的顏色染色，有邊相連的一對(duì)頂點(diǎn)接受不同的顏色，那么這種圖染色方案對(duì)應(yīng)一種寄存器分配方案。如果找不到一種k染色方案，只好修改代碼重新染色。1

7、. 使寄存器使用率最小寄存器分配的目標(biāo)是使不得不執(zhí)行的load 和store指令的數(shù)目最小。把寄存器分配問(wèn)題化歸到圖染色問(wèn)題巧妙地轉(zhuǎn)移了目標(biāo)：以前是最小化存取內(nèi)存的開(kāi)銷，變成最小化寄存器使用率。2. 使被拋出代碼最少即使有最好的染色算法和大量的寄存器，有時(shí)候也不得不把某些值拋到內(nèi)存里。這樣就產(chǎn)生了幾個(gè)難題。首先我們希望插入load 和store 指令的動(dòng)態(tài)開(kāi)銷最小。我們必須設(shè)法選擇拋出某些生命期，使得拋出開(kāi)銷低，又能減輕圖中寄存器分配的壓力。還有，我們考慮最好在哪里插入load 和store 指令。所有這些問(wèn)題都很復(fù)雜，而且是互相關(guān)聯(lián)的。二 背景(一)用圖染色法來(lái)分配寄存器我們假設(shè)分配器工作在

8、一種類似匯編代碼的低級(jí)的中間代碼上。這種代碼被優(yōu)化器處理過(guò)，尋址模式和執(zhí)行順序是確定的。當(dāng)然，這些假設(shè)忽略了分配器和編譯器其他部件之間可能的協(xié)同關(guān)聯(lián)。為了以后討論的簡(jiǎn)化，我們還假設(shè)機(jī)器是loadstore的體系結(jié)構(gòu)。在分配以前，中間代碼可以引用無(wú)限數(shù)目的寄存器。我們把這些分配之前的不受限制的寄存器叫做“虛擬寄存器”。分配的目標(biāo)就是重寫(xiě)中間代碼，使它只使用目標(biāo)機(jī)器提供的寄存器機(jī)器寄存器 。在寄存器分配中我們關(guān)心的是賦值（definition）和生命期（live range）。一個(gè)生命期是由共同的使用（use）連接的一個(gè)或多個(gè)賦值。所有組成一個(gè)生命期的賦值將用同一個(gè)虛擬寄存器命名。在分配之后，任意

9、一個(gè)機(jī)器寄存器通常對(duì)應(yīng)幾個(gè)生命期。為了把寄存器分配轉(zhuǎn)化為圖染色的模型，編譯器首先構(gòu)造一個(gè)沖突圖G。G中的結(jié)點(diǎn)代表生命期，邊代表沖突關(guān)系。這樣，在圖G中結(jié)點(diǎn)i與結(jié)點(diǎn)j有一條邊相連當(dāng)且僅當(dāng)生命期l i 與生命期l j 沖突，就是它們?cè)谀骋稽c(diǎn)同時(shí)是活躍的。與一個(gè)生命期li 沖突的那些生命期被稱為l i的鄰居。在圖中鄰居的數(shù)目就是l i 的度數(shù)，記做 l io 為了找到圖G的一種寄存器分配，編譯器首先尋找圖G的一種k染色方案。如果機(jī)器寄存器的數(shù)目是k，我們就找到一種切實(shí)可行的寄存器分配方案。因?yàn)闉槿我庖粋€(gè)圖找到k染色方案是一個(gè)NP結(jié)問(wèn)題，只能采用啟發(fā)式算法來(lái)尋找染色方案，這就不能保證為每個(gè)可以k染色的

10、圖找到k染色方案。(二)Yorktown 分配器Chaitin和他的同事在IBM的Yorktown Heights研究中心為PL8 編譯器實(shí)現(xiàn)的分配器，是基于圖染色法的全局的寄存器分配器的第一個(gè)實(shí)現(xiàn)。下圖顯示了Yorktown 分配器的流程。圖 （1）Renumber 這個(gè)階段找到函數(shù)中的所有生命期，并給它們以唯一的編號(hào)。Build 這一步要建立沖突圖G。為了保證效率，G同時(shí)有兩種表示形式：一個(gè)三角矩陣和一個(gè)相鄰向量表。Coalesce 在這個(gè)階段分配器刪去不要的復(fù)制賦值，從代碼中去掉對(duì)應(yīng)的復(fù)制語(yǔ)句，合并源生命期和目標(biāo)生命期。刪去一個(gè)復(fù)制的前提是源和目標(biāo)互相不沖突。我們把結(jié)點(diǎn)l i 和 l j

11、 的合并記為 l ij 。刪去復(fù)制指令必然會(huì)改變沖突圖，我們要重復(fù)build 和 coalesce直到再?zèng)]有復(fù)制賦值。Spill Costs 在染色之前，對(duì)每個(gè)生命期 l 都要計(jì)算它的拋出開(kāi)銷。l 的拋出開(kāi)銷是對(duì)拋出l 后插入的load 和store指令造成的開(kāi)銷的評(píng)估。每條指令的開(kāi)銷用10 d加權(quán)，而d是這條指令的循環(huán)嵌套深度。Simplify 這個(gè)階段，還有select ，一起對(duì)沖突圖染色。simplify 反復(fù)地檢查G中的結(jié)點(diǎn)，刪去所有度數(shù)小于k的結(jié)點(diǎn)。當(dāng)一個(gè)結(jié)點(diǎn)被刪去時(shí)，與它關(guān)聯(lián)的邊也被刪去，然后這個(gè)點(diǎn)被壓入棧s。如果遇到G中剩下的每個(gè)結(jié)點(diǎn)的度數(shù)都大于k，就要選擇其中一個(gè)拋出。但不會(huì)立

12、刻把結(jié)點(diǎn)對(duì)應(yīng)的生命期拋出（也就是立刻更新代碼和沖突圖），只是把那個(gè)結(jié)點(diǎn)從G中刪去，并標(biāo)記為spilling。最后G會(huì)成為空?qǐng)D。如果有些結(jié)點(diǎn)被標(biāo)記spilling，它們?cè)趕pill code 階段會(huì)被拋出，整個(gè)分配過(guò)程要重新來(lái)。否則，棧s被傳遞到select階段。Select 按照在simplify階段確定的順序，把顏色分配給每一個(gè)結(jié)點(diǎn)。按順序，每個(gè)結(jié)點(diǎn)從棧s中彈出來(lái)，重新插入到G中，并分配一個(gè)與它的鄰居不同的顏色。Spill Code 以前我們假設(shè)了loadstore 體系結(jié)構(gòu)，就要在每個(gè)被拋出的生命期的引用前面插入一條load指令，在每個(gè)被拋出的生命期的賦值后面插入一條store指令。1.

13、識(shí)別生命期(Discovering Live Ranges)在一個(gè)函數(shù)里，變量i 可能被多次使用，每次都有不同的意義。然而，沒(méi)有必要讓分配器為那些分離的使用（雖然有同樣的變量名，卻被分配了不同的虛擬寄存器）都安排同一個(gè)機(jī)器寄存器。事實(shí)上，這種行為還會(huì)限制可能的染色方案。每個(gè)分離的（對(duì)虛擬寄存器的）使用就是一個(gè)唯一的生命期，它們等待分配器來(lái)染色。因此，分配器的首要任務(wù)是識(shí)別函數(shù)中的生命期。在實(shí)現(xiàn)中，每個(gè)生命期被給予一個(gè)唯一的索引，按照生命期索引重寫(xiě)中間代碼，代替原來(lái)的虛擬寄存器號(hào)。識(shí)別生命期首先要找到可以合并的def-use鏈。一根def-use鏈把一個(gè)虛擬寄存器的賦值和它所有的使用串聯(lián)起來(lái)。如

14、果幾根def-use鏈共享同一個(gè)使用（換句話說(shuō)，幾個(gè)賦值可以到達(dá)一個(gè)使用），這幾根def-use鏈?zhǔn)强梢院喜⒌?。?dāng)然，那些從一個(gè)給定的賦值出發(fā)的鏈都是可以合并的。2. 沖突(Interference)理解沖突的概念是理解圖染色法分配器的關(guān)鍵。只要把兩個(gè)生命期分配到同一個(gè)寄存器會(huì)改變程序的語(yǔ)義，這兩個(gè)生命期就沖突。Chaitin給出了一些判斷沖突的條件：如果兩個(gè)生命期互相沖突，那么在函數(shù)中存在某些點(diǎn)滿足下列的條件：1. 兩個(gè)生命期都被賦值，2. 兩個(gè)生命期都會(huì)被使用，而且3. 兩個(gè)生命期有不同的值。這些條件不是獨(dú)立，要聯(lián)合起來(lái)使用。Chaitin 最終的辦法是看在每一個(gè)表達(dá)式里那些生命期是既活躍

15、又可使用的。我們稱一個(gè)關(guān)于變量v的生命期l在某條語(yǔ)句s是活躍的，如果存在一條路徑從s到v的其他使用，而且在這條路徑上不存在對(duì)v的賦值。類似的，稱l在s是可使用的如果存在一條路徑從v的賦值到s。事實(shí)上，可使用性和活躍性對(duì)應(yīng)了上面的條件1和條件2。條件3要求小心地處理復(fù)制指令。復(fù)制賦值中的源生命期和目的生命期會(huì)有相同的值，它們就不會(huì)沖突。為了在以后能夠合并（coalesce），它們也不應(yīng)該沖突。但是，如果它們因?yàn)槠渌脑驔_突，比如在函數(shù)中另外一點(diǎn)沖突關(guān)系被添到?jīng)_突圖中，合并要被禁止。3. 沖突圖(The Interference Graph)在Yorktown 分配器中一個(gè)核心數(shù)據(jù)結(jié)構(gòu)就是沖突圖

16、。沖突圖要提供5個(gè)操作。new(n) 返回一個(gè)n個(gè)結(jié)點(diǎn)的圖，但是沒(méi)有邊。add(g,x,y) 返回圖g，并在結(jié)點(diǎn)x和y之間添加一條邊。interfere(g,x,y) 如果圖g中結(jié)點(diǎn)x和y之間存在一條邊就返回真。degree(g,x) 返回圖g中結(jié)點(diǎn)x的度數(shù)。neighbors(g,x,f) 對(duì)圖g中結(jié)點(diǎn)x的各個(gè)鄰居應(yīng)用函數(shù)f。在實(shí)現(xiàn)中，沖突圖有兩種表現(xiàn)形式：三角矩陣和相鄰向量表。比特矩陣可以支持常數(shù)時(shí)間的add和interfere操作，而相鄰向量表可以使neighbors更加有效率。構(gòu)造沖突圖是用兩遍掃描完成，相鄰表存儲(chǔ)在一個(gè)連續(xù)的數(shù)組里。1. 開(kāi)始，為比特矩陣分配空間和清零。對(duì)整個(gè)代碼做一

17、遍掃描，填充比特矩陣并計(jì)算每個(gè)結(jié)點(diǎn)的度數(shù)。2. 知道每個(gè)結(jié)點(diǎn)的度數(shù)以后，為相鄰表分配空間，重新初始化比特矩陣。在第二遍掃描時(shí)，沖突關(guān)系被記入比特矩陣和相鄰表。每一遍合并以后，沖突圖要重建。第二步會(huì)多次重復(fù)。我們實(shí)現(xiàn)的時(shí)候，每一遍對(duì)流圖中的每個(gè)基本塊逆向掃描，動(dòng)態(tài)維護(hù)一個(gè)當(dāng)前活躍并且可使用的生命期的集合。每遇到一處賦值，為被賦值的生命期和s中的所有元素在圖中添加邊。徹底完成buildcoalesce循環(huán)后，比特矩陣占據(jù)的空間可以被釋放。相鄰表在以后的階段simplify 和select中還需要。4. 合并(Coalescing)建立沖突圖以后，我們就要執(zhí)行合并。對(duì)每個(gè)復(fù)制指令，我們檢查它的源生命

18、期和目的生命期是否沖突；若不沖突，它們可以被合并，復(fù)制指令也被刪去。為了合并兩個(gè)生命期l x和l y 成為l xy，我們?cè)谟玫絣 x、l y每個(gè)地方用l xy代替。當(dāng)兩個(gè)生命期l x和l y被合并，我們必須更新沖突圖，使得l xy和l x、l y的鄰居沖突。合并階段對(duì)中間代碼做一遍完全的掃描，盡可能地合并，更新沖突圖。任一個(gè)復(fù)制語(yǔ)句被刪去，都會(huì)導(dǎo)致重建沖突圖，并引起更多的合并。這個(gè)周期一直重復(fù)到?jīng)]有更多的復(fù)制語(yǔ)句被刪去才停止。5拋出(Spilling)最粗糙的對(duì)拋出的處理方案就是：拋出一個(gè)生命期l，然后在l的每處賦值后面插入store指令，在l的每處使用前面插入load指令。Chaitin在他

19、的論文提供了兩種重要的改善。首先，某些生命期是很容易重新計(jì)算的；比如，一個(gè)是常數(shù)的生命期。這些生命期不必被寫(xiě)入內(nèi)存又重新讀出來(lái)；相反，在每次使用之前可以重新計(jì)算。其次，不必要在用到這個(gè)生命期的每處都拋出。Chaitin 描述了幾種情況。l 如果被拋出的生命期的兩個(gè)使用是緊相鄰的，就不必要為第二次使用從內(nèi)存中重新讀入；為這兩個(gè)使用分配同一個(gè)寄存器就行了。l 如果一個(gè)使用緊跟在被拋出的生命期的賦值的后面，也就不必要在使用前重新讀入了。l 類似的，如果一個(gè)生命期的所有使用都緊跟著對(duì)它的賦值，這個(gè)生命期也不必被拋出。6. 染色(Coloring)Yorktown 分配器的核心就是它的染色算法。Chai

20、tin的算法分為兩個(gè)部分simplify和select。Simplify不斷地把結(jié)點(diǎn)從圖中刪去，壓入棧中。在select階段，結(jié)點(diǎn)被從棧中彈出來(lái)，重新加到圖中去。當(dāng)結(jié)點(diǎn)l i的度數(shù)小于k時(shí)，它被從圖中移入棧中。以后l i從棧中移回圖中時(shí)，它的鄰居數(shù)目仍然小于k。顯然l i 在圖中是可以著色的。在simplify階段，只有確認(rèn)一個(gè)結(jié)點(diǎn)在當(dāng)前圖中會(huì)被染色，才把它刪去。當(dāng)每一個(gè)生命期被刪去時(shí)，它的鄰居的度數(shù)就會(huì)降低。在select階段，結(jié)點(diǎn)按照被刪去的逆序分配顏色。如果在simplify階段遇到一個(gè)圖中所有的結(jié)點(diǎn)的度數(shù)都大于k，有一個(gè)結(jié)點(diǎn)將被選中拋出。這個(gè)拋出結(jié)點(diǎn)被從圖中刪去，并被標(biāo)記為spilli

21、ng。一個(gè)處理方案是在程序中的這一點(diǎn)立刻插入代碼，重建沖突圖，尋找新的染色方案。這個(gè)方案雖然精確但開(kāi)銷巨大。Chaitin提到另一種不很精確的處理方案：在選擇拋出結(jié)點(diǎn)后，繼續(xù)簡(jiǎn)化（simplification）直到走完這一遍，標(biāo)記出所有的拋出結(jié)點(diǎn)。三 Briggs的改進(jìn)（一）兩個(gè)難題Chaitin的啟發(fā)式算法是有缺陷的，它產(chǎn)生了不必要的拋出。兩個(gè)例子，一小一大，可以展示算法的缺陷。假設(shè)我們要為圖（2）找到一個(gè)2染色方案。顯然存在這樣的方案；比如，x和y染紅色，w和z染綠色。圖 （2）如果運(yùn)用Chaitin的算法，因?yàn)閳D中沒(méi)有度數(shù)小于2的結(jié)點(diǎn)，必然有一個(gè)結(jié)點(diǎn)要被拋出。再看下一個(gè)例圖 （3）。圖

22、（3）SVD的結(jié)構(gòu)圖Briggs用上圖的例程做測(cè)試的時(shí)候，發(fā)現(xiàn)分配器總是把小而短的生命期（M，N，I，J）拋出去，而不是大而長(zhǎng)的生命期。盡管當(dāng)時(shí)還有可分配的寄存器，但循環(huán)計(jì)數(shù)變量和循環(huán)計(jì)數(shù)的上界被拋出了。最后的結(jié)果就是：那段復(fù)制數(shù)組的循環(huán)代碼幾乎就沒(méi)有利用寄存器。（二）改進(jìn)的染色Briggs對(duì)Chaitin的算法做了兩處修正：1. 在simplify階段只要發(fā)現(xiàn)剩下的結(jié)點(diǎn)的度數(shù)都不小于k，就從中間選擇一個(gè)拋出。這個(gè)結(jié)點(diǎn)被從圖中刪去，但是并沒(méi)有被標(biāo)記為spilling。它被壓入棧，以后有可能獲得一個(gè)顏色。2. 在select階段發(fā)現(xiàn)不能為某些結(jié)點(diǎn)染色時(shí)，就放棄那個(gè)結(jié)點(diǎn)，繼續(xù)對(duì)下面的結(jié)點(diǎn)染色。那些

23、被放棄的結(jié)點(diǎn)在Chaitin的算法中一定被拋出。Briggs改進(jìn)后的分配器的流程見(jiàn)下圖。圖 （4）這樣就可以解決前面提到的兩個(gè)難題。推遲拋出產(chǎn)生兩個(gè)結(jié)果。首先，它消除了一些無(wú)效的拋出。在Chaitin的方法中，拋出是在染色以前的simplify階段就決定了。一旦一個(gè)結(jié)點(diǎn)被拋出，它對(duì)應(yīng)的生命期也被拋出。在Briggs的方法中，那些結(jié)點(diǎn)放在棧里只是拋出的候選者，由select階段才決定它們是否真的被拋出。其次，它提供了一個(gè)更強(qiáng)大的染色算法。在為結(jié)點(diǎn)x選擇顏色的時(shí)候，它檢查x的當(dāng)前所有鄰居的顏色。如果有兩個(gè)或者多個(gè)x的鄰居收到同樣的顏色，即使x的度數(shù)不小于k，它也可以被染色。這就比Chaitin簡(jiǎn)單

24、地用“x的度數(shù)是否小于k”作為判據(jù)要準(zhǔn)確。這樣實(shí)現(xiàn)的分配器可以為圖（2）產(chǎn)生一個(gè)2染色方案。再考慮圖（3）的SVD例程。生命期I，J，M和N較早成為拋出的候選者，因?yàn)樗鼈兊膾伋鲩_(kāi)銷小。然而，拋出它們并不會(huì)減輕循環(huán)內(nèi)部的寄存器分配的壓力。分配器應(yīng)該拋出那些大而長(zhǎng)的生命期。等到這些小的生命期從棧中彈出來(lái)，已經(jīng)有些大的生命期被拋出了。分配器很容易地為在循環(huán)中的小生命期分配顏色。Briggs只對(duì)Chaitin的算法做了些許的改動(dòng)，沒(méi)有增加它的實(shí)現(xiàn)難度，卻取得顯著的效果。致謝程旭老師是我的指導(dǎo)老師。他在實(shí)驗(yàn)室倡導(dǎo)的團(tuán)隊(duì)合作的精神，營(yíng)造的勤奮上進(jìn)的氛圍，讓我很受熏陶。他幾次和我的談話，都給了我深刻的啟發(fā)。

25、我想向他表示誠(chéng)摯的感謝和崇高的尊敬。我衷心地感謝兩位師兄，朱德新博士和韓果凌碩士。他們具體管理和指導(dǎo)了我的工作，并在方法上給出了很中肯的意見(jiàn)。我曾經(jīng)在中期報(bào)告中提到我實(shí)際上在一個(gè)小組中，后來(lái)關(guān)于寄存器分配的工作也不是我獨(dú)自承擔(dān)的。我衷心地向曾和我合作的高翊同學(xué)、陳江楓同學(xué)、聶書(shū)忻同學(xué)表示感謝，正是大家的討論和協(xié)作促進(jìn)了工作的進(jìn)展。最后，我要感謝這個(gè)實(shí)驗(yàn)室的其他老師、研究生和本科實(shí)習(xí)同學(xué)。他們雖然與我的工作沒(méi)有關(guān)系，但是他們形成的氛圍對(duì)我產(chǎn)生了很深的影響。參考文獻(xiàn)（1） Preston Briggs, Register Allocation via Grapth Coloring, April

26、1992;（2） Steven S. Muchnick, Advanced compiler design implementation;作者簡(jiǎn)介吳漢唐，男。1998年從湖南省考入北京大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系學(xué)習(xí)，屬于計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)。2000年11月接受“北京大學(xué)泰兆大學(xué)生科學(xué)研究獎(jiǎng)助金”的資助，在北京大學(xué)微處理器研究開(kāi)發(fā)中心（它的前身是北京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系系統(tǒng)結(jié)構(gòu)教研室）工作。先后參與對(duì)SUIF系統(tǒng)的分析工作，針對(duì)JBCore32編譯器的寄存器分配優(yōu)化算法的實(shí)現(xiàn)工作。我學(xué)習(xí)勤奮，主動(dòng)思考，本專業(yè)約130名學(xué)生，我在三年的績(jī)點(diǎn)排名中是第41名，已經(jīng)順利保送本系讀研究生。感悟與寄語(yǔ)我的前一部分工作是分析SUIF系統(tǒng)。在搜集資料的過(guò)程中，我看到了美國(guó)在編譯領(lǐng)域的最新進(jìn)展，他們已經(jīng)建立NCI（國(guó)家編譯基礎(chǔ)設(shè)施），并在這個(gè)基礎(chǔ)上開(kāi)展了一系列的教學(xué)、實(shí)習(xí)、研究工作。反觀國(guó)內(nèi)編譯研究的聲勢(shì)不大。后來(lái)我參加實(shí)現(xiàn)寄存器分配算法。雖然編譯理論、優(yōu)化算法已經(jīng)成熟，但實(shí)現(xiàn)一個(gè)優(yōu)化編譯器仍是困難的事，需要一個(gè)大團(tuán)隊(duì)持久不懈的工作。實(shí)現(xiàn)寄存器分配算法時(shí)候的難點(diǎn)不是圖染色法，而是怎么完善地處理與目標(biāo)機(jī)器、編譯器前端相關(guān)的細(xì)節(jié)問(wèn)題。編譯器的研究總是與微處理器、操作系統(tǒng)的發(fā)展相同步，祝愿我國(guó)能早日在