圖染色法的寄存器分配

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

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

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

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

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

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

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

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

9、一個機器寄存器通常對應幾個生命期。為了把寄存器分配轉化為圖染色的模型，編譯器首先構造一個沖突圖G。G中的結點代表生命期，邊代表沖突關系。這樣，在圖G中結點i與結點j有一條邊相連當且僅當生命期l i 與生命期l j 沖突，就是它們在某一點同時是活躍的。與一個生命期li 沖突的那些生命期被稱為l i的鄰居。在圖中鄰居的數(shù)目就是l i 的度數(shù)，記做 l io 為了找到圖G的一種寄存器分配，編譯器首先尋找圖G的一種k染色方案。如果機器寄存器的數(shù)目是k，我們就找到一種切實可行的寄存器分配方案。因為為任意一個圖找到k染色方案是一個NP結問題，只能采用啟發(fā)式算法來尋找染色方案，這就不能保證為每個可以k染色的

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

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

12、刻把結點對應的生命期拋出（也就是立刻更新代碼和沖突圖），只是把那個結點從G中刪去，并標記為spilling。最后G會成為空圖。如果有些結點被標記spilling，它們在spill code 階段會被拋出，整個分配過程要重新來。否則，棧s被傳遞到select階段。Select 按照在simplify階段確定的順序，把顏色分配給每一個結點。按順序，每個結點從棧s中彈出來，重新插入到G中，并分配一個與它的鄰居不同的顏色。Spill Code 以前我們假設了loadstore 體系結構，就要在每個被拋出的生命期的引用前面插入一條load指令，在每個被拋出的生命期的賦值后面插入一條store指令。1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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