[科普中國(guó)]-寄存器分配

簡(jiǎn)介寄存器分配原因

寄存器分配是編譯器中一個(gè)歷久彌新的問(wèn)題，因?yàn)樗蔷幾g器在輸出匯編代碼前必須經(jīng)歷的階段。寄存器分配算法的好壞，關(guān)系著生成代碼的性能，大小。為了追求極致性能，很多編譯器都在寄存器分配上做了很多文章，不惜引入非常復(fù)雜的算法。另一方面寄存器分配算法本身的性能也很關(guān)鍵， 在諸多的JIT編譯器(Just-In-Time compiler)中，編譯器的性能同時(shí)也是程序本身的性能，因此在JIT編譯器中還需要關(guān)注寄存器分配算法本身的效率問(wèn)題。另外，寄存器分配作為將無(wú)限多的邏輯單元映射到有限多的物理單元的典型問(wèn)題，深入了解它也有助于對(duì)其他相關(guān)問(wèn)題的理解，如操作系統(tǒng)中的頁(yè)著色問(wèn)題(Page Coloring)。

實(shí)際編譯器中的寄存器分配問(wèn)題在實(shí)際編譯器中，為了盡可能的榨取性能，提升編譯器的分配效率，寄存器分配算法都很復(fù)雜。萬(wàn)變不離其宗。不管是GCC，Open64還是LLVM，寄存器分配基本都是在靠近匯編代碼輸出階段。Open64中在寄存器分配之后，幾乎沒(méi)有什么優(yōu)化了。GCC中，在寄存器分配之后，還存在大約7個(gè)PASS(基本塊重排序、收集用于調(diào)試的變量保存位置相關(guān)信息、延遲槽調(diào)度、長(zhǎng)跳轉(zhuǎn)轉(zhuǎn)換、針對(duì)86387浮點(diǎn)寄存器的寄存器到棧變換、匯編代碼輸出、調(diào)試信息輸出)，也沒(méi)有優(yōu)化了。LLVM不清楚，歡迎有了解的朋友補(bǔ)充。

這三個(gè)工業(yè)界級(jí)別的編譯器中，到了寄存器分配階段都已經(jīng)從語(yǔ)法樹形式的中間表示轉(zhuǎn)換成了三地址形式的中間表示。 在GCC中，已經(jīng)從GIMPLE轉(zhuǎn)換成了RTL；在Open64中，已經(jīng)從WHIRL轉(zhuǎn)換成了CGIR；在LLVM中，已經(jīng)從Clang階段的AST(Abstract Syntax Tree,抽象語(yǔ)法樹)轉(zhuǎn)換成了LLVM IR。 在轉(zhuǎn)換成三地址碼之前，操作之間的操作數(shù)、結(jié)果的依賴關(guān)系都可以通過(guò)樹形結(jié)構(gòu)表達(dá)，展開成三地址形式之后，就需要大量創(chuàng)建臨時(shí)變量來(lái)表達(dá)這種依賴關(guān)系。此時(shí)所有的變量(包括臨時(shí)變量和原程序中的變量)，都會(huì)被分配偽寄存器(Pseudo Register偽寄存器和物理寄存器除了數(shù)量有區(qū)別：無(wú)限多個(gè)/有限多個(gè)外，其他都相同)。

寄存器分配即將這些偽寄存器映射到實(shí)際的物理寄存器上 ， 因此在寄存器分配之前，要保證指令序列基本不再變化。所以實(shí)際編譯器中的寄存器分配階段，基本都在最后階段，此時(shí)都基本完成了幾乎所有的底層次優(yōu)化，如三地址形式的循環(huán)優(yōu)化、指令調(diào)度、冗余代碼刪除、其他窺孔優(yōu)化等等。但也有例外，比如寄存器分配時(shí)，需要額外增加一些訪存指令，因此在寄存器分配結(jié)束后，可能還需要一些調(diào)整1。

寄存器分配原則寄存器分配的原則是：
1、當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中，直到寄存器不夠分配時(shí)為止。
2、當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié)點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口前存放的寄存器可能不同，或沒(méi)有定值，所以應(yīng)在出口前把寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。
3、對(duì)于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。2

寄存器分配相關(guān)算法圖著色算法圖著色(graph coloring)方法是解決寄存器分配問(wèn)題最常用的方法。
利用相交圖（interference graph）來(lái)表示程序變量的生命期是否相交，將寄存器分配給變量的問(wèn)題，可以近似地看成是給相交圖著色：相交圖中，相交的節(jié)點(diǎn)不能著同一顏色；每一種顏色對(duì)應(yīng)一個(gè)寄存器。Chaitin等人最早提出了基于圖著色的寄存器分配方法其著色思路采用了Kempe的著色方法，即任意一個(gè)鄰居節(jié)點(diǎn)數(shù)目少于k的節(jié)點(diǎn)，都能夠被k著色。判斷一個(gè)圖是否能夠被k(k>=3)種顏色著色，即k著色問(wèn)題，被Karp證明是一個(gè)NP-complete問(wèn)題。
但是，寄存器分配不僅僅是圖著色的問(wèn)題。當(dāng)寄存器數(shù)目不足以分配某些變量時(shí)，就必須將這些變量溢出到內(nèi)存中，該過(guò)程成為spill。最小化溢出代價(jià)的問(wèn)題，也是一個(gè)NP-complete問(wèn)題。如果簡(jiǎn)化該問(wèn)題——假設(shè)所有溢出代價(jià)相等，那么最小化溢出代價(jià)的問(wèn)題，等價(jià)于k著色問(wèn)題，仍然是NP-complete問(wèn)題。
此外，如果兩個(gè)變量的生命期僅僅因?yàn)槌霈F(xiàn)在同一個(gè)拷貝指令中而相鄰，那么，通過(guò)將這兩個(gè)變量分配到同一個(gè)寄存器，就可以消除該拷貝指令，成為coalescing。這個(gè)方向的努力在Chaitin的文章以后的1/4個(gè)世紀(jì)，成為推動(dòng)寄存器分配的主要?jiǎng)恿χ?，涌現(xiàn)出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，將兩個(gè)變量分配到同一個(gè)寄存器，等價(jià)于將這兩個(gè)變量合并成同一個(gè)變量，生命期合并，因而會(huì)加劇相交圖的聚簇現(xiàn)象，降低相交圖的可著色性。Bouchez等人證明了目前的coalescing問(wèn)題都是NP-complete的。

為了降低相交圖的聚簇現(xiàn)象，提高相交圖的可著色性，可以通過(guò)將變量拷貝給一個(gè)臨時(shí)變量，并將以后對(duì)該變量的使用替換成對(duì)該臨時(shí)變量的使用，從而將一個(gè)變量的生命期分解成兩個(gè)變量的生命期，稱為live range splitting。顯然，這是一個(gè)與coalescing的作用相反的過(guò)程。Bouchez等人考慮了該方法的復(fù)雜度。
此外，寄存器分配還需要考慮寄存器別名(aliasing)和預(yù)著色(pre-coloring)的問(wèn)題。寄存器別名是指，在某些體系結(jié)構(gòu)中，一個(gè)寄存器的賦值可能會(huì)影響到另外一個(gè)寄存器。比如，在x86中，對(duì)AX寄存器的賦值，會(huì)影響AL和AH寄存器。預(yù)著色是指，某些變量必須被分配到特定的寄存器。比如，許多體系結(jié)構(gòu)會(huì)采用特定寄存器來(lái)傳遞函數(shù)參數(shù)。
George和Appel發(fā)展了Chaitin的算法，更好地考慮了coalescing過(guò)程和賦值過(guò)程，以及各過(guò)程之間的迭代，在基于圖著色的寄存器分配方法中具有廣泛的影響。2

線性掃描算法線性掃描算法是寄存器分配最快的算法。

線性掃描算法(linear scan)最早由Poletto和Sarkar提出，具有很大的影響力，在gcc、llvm和Java HotSpot編譯器中得到了實(shí)現(xiàn)。線性掃描算法簡(jiǎn)化了基于圖著色的分配問(wèn)題，考慮的是對(duì)一個(gè)有序的生命期序列的著色，提高了寄存器分配的速度（線性速度），而沒(méi)有過(guò)度降低對(duì)寄存器的利用。

整數(shù)線性規(guī)劃算法Goodwin和Wilken提出了最早的對(duì)寄存器分配問(wèn)題的整數(shù)線性規(guī)劃算法(integer linear programming),雖然在最壞情況下具有指數(shù)級(jí)復(fù)雜度，但是能夠更充分的利用寄存器。

PBQP算法在編譯器領(lǐng)域，Partitioned Boolean Quadratic Problem被用于解決指令選擇和寄存器分配問(wèn)題。對(duì)于寄存器分配而言，PBQP算法的復(fù)雜度為VK^3，其中V是變量的數(shù)目，K是寄存器的數(shù)目。Hames等人的實(shí)驗(yàn)表明，他們的PBQP實(shí)現(xiàn)能夠?yàn)镾PEC CPU 2000中的97.4%的函數(shù)找到最優(yōu)寄存器分配方案。

Multi-Flow Commodities算法Koes和Goldstein等人最先將寄存器分配視為Multi-Flow Commodities問(wèn)題加以解決。

基于SSA的寄存器分配SSA是Static Single Assignment的簡(jiǎn)寫。寄存器分配問(wèn)題的一個(gè)重要突破發(fā)生在2005年，當(dāng)時(shí)3個(gè)研究團(tuán)隊(duì)獨(dú)立的證明了，采用SSA表示的程序的相交圖是弦圖（chordal graph）。而弦圖是能夠在多項(xiàng)式時(shí)間內(nèi)著色的。基于SSA形式的寄存器分配方法，可以從三個(gè)方面獲益：更小的寄存器壓力；spilling和寄存器賦值過(guò)程之間的分離；更簡(jiǎn)單的寄存器賦值算法。2