相連多寄存器組體系結(jié)構(gòu)上的寄存器分配技術(shù).pdf

1、寄存器分配是編譯器后端一個(gè)十分重要的階段。寄存器分配的有效性直接影響著編譯器的優(yōu)化效果和處理器性能的發(fā)揮。隨著計(jì)算機(jī)體系結(jié)構(gòu)的發(fā)展，為了支持多核多線程、異步訪存以及減少寄存器件讀寫端口，出現(xiàn)了一類相連多寄存器組結(jié)構(gòu)的處理器。在這類處理器上分配好寄存器是對編譯器的一大挑戰(zhàn)。本文對相連多寄存器組體系結(jié)構(gòu)上的寄存器分配關(guān)鍵技術(shù)進(jìn)行了研究。本文的主要貢獻(xiàn)如下： 1．提出了一種相連多寄存器組結(jié)構(gòu)上的寄存器分配方法。傳統(tǒng)通用處理器的寄存器組

2、之間相互獨(dú)立，各自存放不同類型數(shù)據(jù)，指令的操作數(shù)只能來自唯一一個(gè)寄存器組。在這種獨(dú)立寄存器組結(jié)構(gòu)上只須分別對每個(gè)寄存器組使用目前流行的Chaitin方法即可。但在相連寄存器組結(jié)構(gòu)的處理器上，各寄存器組字長相同并有數(shù)據(jù)通路相連，能存放相同的數(shù)據(jù)，指令的操作數(shù)可來自多個(gè)寄存器組。出現(xiàn)了需要確定變量的寄存器組屬性及解決寄存器組沖突的新問題，使得Chaitin方法不再直接適用。我們通過提出寄存器組劃分圖的概念以及對它相應(yīng)的建立、化簡和分裂方法，

3、解決了上述問題。 2．提出了三種雙操作數(shù)沖突解決技術(shù)。為了減少寄存器堆的讀寫端口個(gè)數(shù)，進(jìn)而提高寄存器的訪問速度，有的處理器要求所有二元操作指令的兩個(gè)源操作數(shù)必須來自不同的寄存器組。隨之出現(xiàn)的新問題是，我們既要為變量指派寄存器組，又要為其分配寄存器，兩者之間互相影響。我們提出了沖突圖概念，并把這種雙操作數(shù)沖突約束下的寄存器分配問題分解為二個(gè)子問題：組指派子問題和寄存器分配子問題。前者通過對沖突圖2一著色解決，后者通過對干涉圖K-著

4、色解決。根據(jù)解決這二個(gè)子問題的次序，提出了三種方法：先于寄存器分配的組指派、后于寄存器分配的組指派、結(jié)合式寄存器分配與組指派。 3．提出了一種復(fù)寫合并與活躍區(qū)域分裂相結(jié)合的寄存器分配方法。Chaitin方法的一個(gè)缺陷是溢出一個(gè)活躍區(qū)域時(shí)會(huì)全程溢出，代價(jià)較大。我們的方法是事先把活躍區(qū)域分裂成多個(gè)碎片，然后依賴復(fù)寫合并激進(jìn)地合并碎片。如果合并后的活躍區(qū)域出現(xiàn)分配失敗，就按原來的裂痕進(jìn)行反合并。由此我們獲得了一種在溢出全部活躍區(qū)域、溢

5、出部分活躍區(qū)域、用拷貝指令換取溢出之間做出更好選擇的能力。 4．為開放源碼編譯器ORC增添了新的基礎(chǔ)設(shè)施。ORC被國內(nèi)外多所著名大學(xué)和研究機(jī)構(gòu)采用，做為其研究平臺(tái)。我們在ORC中實(shí)現(xiàn)了多種圖著色寄存器分配方法以及ORC后端的SSA表示。例如Chaitin方法、Briggs樂觀式著色方法、George迭代式合并方法和我們提出的新方法。與ORC原有方法相比，我們在253.perlbmk、186.craRy上分別取得了3.4％和13.