寄存器分配是編譯器后端一個十分重要的階段。寄存器分配的有效性直接影響著編譯器的優(yōu)化效果和處理器性能的發(fā)揮。隨著計算機體系結(jié)構(gòu)的發(fā)展,為了支持多核多線程、異步訪存以及減少寄存器件讀寫端口,出現(xiàn)了一類相連多寄存器組結(jié)構(gòu)的處理器。在這類處理器上分配好寄存器是對編譯器的一大挑戰(zhàn)。本文對相連多寄存器組體系結(jié)構(gòu)上的寄存器分配關(guān)鍵技術(shù)進行了研究。本文的主要貢獻如下: 1.提出了一種相連多寄存器組結(jié)構(gòu)上的寄存器分配方法。傳統(tǒng)通用處理器的寄存器組之間相互獨立,各自存放不同類型數(shù)據(jù),指令的操作數(shù)只能來自唯一一個寄存器組。在這種獨立寄存器組結(jié)構(gòu)上只須分別對每個寄存器組使用目前流行的Chaitin方法即可。但在相連寄存器組結(jié)構(gòu)的處理器上,各寄存器組字長相同并有數(shù)據(jù)通路相連,能存放相同的數(shù)據(jù),指令的操作數(shù)可來自多個寄存器組。出現(xiàn)了需要確定變量的寄存器組屬性及解決寄存器組沖突的新問題,使得Chaitin方法不再直接適用。我們通過提出寄存器組劃分圖的概念以及對它相應的建立、化簡和分裂方法,解決了上述問題。 2.提出了三種雙操作數(shù)沖突解決技術(shù)。為了減少寄存器堆的讀寫端口個數(shù),進而提高寄存器的訪問速度,有的處理器要求所有二元操作指令的兩個源操作數(shù)必須來自不同的寄存器組。隨之出現(xiàn)的新問題是,我們既要為變量指派寄存器組,又要為其分配寄存器,兩者之間互相影響。我們提出了沖突圖概念,并把這種雙操作數(shù)沖突約束下的寄存器分配問題分解為二個子問題:組指派子問題和寄存器分配子問題。前者通過對沖突圖2-著色解決,后者通過對干涉圖K-著色解決。根據(jù)解決這二個子問題的次序,提出了三種方法:先于寄存器分配的組指派、后于寄存器分配的組指派、結(jié)合式寄存器分配與組指派。 3.提出了一種復寫合并與活躍區(qū)域分裂相結(jié)合的寄存器分配方法。Chaitin方法的一個缺陷是溢出一個活躍區(qū)域時會全程溢出,代價較大。我們的方法是事先把活躍區(qū)域分裂成多個碎片,然后依賴復寫合并激進地合并碎片。如果合并后的活躍區(qū)域出現(xiàn)分配失敗,就按原來的裂痕進行反合并。由此我們獲得了一種在溢出全部活躍區(qū)域、溢出部分活躍區(qū)域、用拷貝指令換取溢出之間做出更好選擇的能力。 4.為開放源碼編譯器ORC增添了新的基礎(chǔ)設施。ORC被國內(nèi)外多所著名大學和研究機構(gòu)采用,做為其研究平臺。我們在ORC中實現(xiàn)了多種圖著色寄存器分配方法以及ORC后端的SSA表示。例如Chaitin方法、Briggs樂觀式著色方法、George迭代式合并方法和我們提出的新方法。與ORC原有方法相比,我們在253.perlbmk、186.crafty上分別取得了3.4%和13.3%的性能加速比。圖著色寄存器分配和SSA表示是編譯研究中二個重要的基礎(chǔ)設施,我們的實現(xiàn)為ORC平臺添加了新的資源。 上面提到的前兩點在ORC/IXP編譯器中實現(xiàn),第三點在ORC/龍芯MIPS編譯器中實現(xiàn)。
【學位單位】：中國科學院研究生院（計算技術(shù)研究所）
【學位級別】：博士
【學位年份】：2005
【中圖分類】：TP333

【引證文獻】

相關(guān)碩士學位論文 前1條

1 余之航;IXP網(wǎng)絡處理器寄存器分配的關(guān)鍵技術(shù)[D];上海交通大學;2009年

本文編號：2819264